dict/scan.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) Index Data
   3
   4    Zebra is free software; you can redistribute it and/or modify it under
   5    the terms of the GNU General Public License as published by the Free
   6    Software Foundation; either version 2, or (at your option) any later
   7    version.
   8
   9    Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10    WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12    for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20
  21 #if HAVE_CONFIG_H
  22 #include <config.h>
  23 #endif
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <stdio.h>
  27 #include <assert.h>
  28
  29 #include "dict-p.h"
  30
  31 static void scan_direction(Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
  32                            int start, int *count, void *client,
  33                            int (*userfunc)(char *, const char *, int, void *),
  34                            int dir)
  35 {
  36     int lo, hi, j;
  37     void *p;
  38     short *indxp;
  39     char *info;
  40
  41     dict_bf_readp(dict->dbf, ptr, &p);
  42     hi = DICT_nodir(p)-1;
  43     if (start != -1)
  44         lo = start;
  45     else
  46     {
  47         if (dir == -1)
  48             lo = hi;
  49         else
  50             lo = 0;
  51     }
  52     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  53
  54     while (lo <= hi && lo >= 0 && *count > 0)
  55     {
  56         if (indxp[-lo] > 0)
  57         {
  58             /* string (Dict_char *) DICT_EOS terminated */
  59             /* unsigned char        length of information */
  60             /* char *               information */
  61
  62             info = (char*)p + indxp[-lo];
  63             for (j = 0; info[j] != DICT_EOS; j++)
  64                 str[pos+j] = info[j];
  65             str[pos+j] = DICT_EOS;
  66             if ((*userfunc)((char*) str, info+(j+1)*sizeof(Dict_char),
  67                             *count * dir, client))
  68             {
  69                 *count = 0;
  70             }
  71             else
  72                 --(*count);
  73         }
  74         else
  75         {
  76             Dict_char dc;
  77             Dict_ptr subptr;
  78
  79             /* Dict_ptr             subptr */
  80             /* Dict_char            sub char */
  81             /* unsigned char        length of information */
  82             /* char *               information */
  83
  84             info = (char*)p - indxp[-lo];
  85             memcpy(&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  86             str[pos] = dc;
  87             memcpy(&subptr, info, sizeof(Dict_ptr));
  88             if (dir>0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  89             {
  90                 str[pos+1] = DICT_EOS;
  91                 if ((*userfunc)((char*) str,
  92                                 info+sizeof(Dict_ptr)+sizeof(Dict_char),
  93                                 *count * dir, client))
  94                 {
  95                     *count = 0;
  96                 }
  97                 else
  98                     --(*count);
  99             }
 100             if (*count>0 && subptr)
 101             {
 102                 scan_direction(dict, subptr, pos+1, str, -1, count,
 103                                client, userfunc, dir);
 104                 dict_bf_readp(dict->dbf, ptr, &p);
 105                 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 106             }
 107             if (*count>0 && dir<0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 108             {
 109                 str[pos+1] = DICT_EOS;
 110                 if ((*userfunc)((char*) str,
 111                                 info+sizeof(Dict_ptr)+sizeof(Dict_char),
 112                                 *count * dir, client))
 113                 {
 114                     *count = 0;
 115                 }
 116                 else
 117                     --(*count);
 118             }
 119         }
 120         lo += dir;
 121     }
 122 }
 123
 124 void dict_scan_r(Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
 125                  int *before, int *after, void *client,
 126                  int (*userfunc)(char *, const char *, int, void *))
 127 {
 128     int cmp = 0, mid, lo, hi;
 129     void *p;
 130     short *indxp;
 131     char *info;
 132
 133     dict_bf_readp(dict->dbf, ptr, &p);
 134     if (!p)
 135         return;
 136     mid = lo = 0;
 137     hi = DICT_nodir(p)-1;
 138     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 139     while (lo <= hi)
 140     {
 141         mid = (lo+hi)/2;
 142         if (indxp[-mid] > 0)
 143         {
 144             /* string (Dict_char *) DICT_EOS terminated */
 145             /* unsigned char        length of information */
 146             /* char *               information */
 147             info = (char*)p + indxp[-mid];
 148             cmp = dict_strcmp((Dict_char*) info, str + pos);
 149             if (!cmp)
 150             {
 151                 if (*after)
 152                 {
 153                     if ((*userfunc)((char *) str, info+
 154                                     (dict_strlen((Dict_char*) info)+1)
 155                                     *sizeof(Dict_char),
 156                                     *after, client))
 157                     {
 158                         *after = 0;
 159                     }
 160                     else
 161                         --(*after);
 162                 }
 163                 break;
 164             }
 165         }
 166         else
 167         {
 168             Dict_char dc;
 169             Dict_ptr subptr;
 170
 171             /* Dict_ptr             subptr */
 172             /* Dict_char            sub char */
 173             /* unsigned char        length of information */
 174             /* char *               information */
 175             info = (char*)p - indxp[-mid];
 176             memcpy(&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 177             cmp = dc - str[pos];
 178             if (!cmp)
 179             {
 180                 memcpy(&subptr, info, sizeof(Dict_ptr));
 181                 if (str[pos+1] == DICT_EOS)
 182                 {
 183                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 184                     {
 185                         if (*after)
 186                         {
 187                             if ((*userfunc)((char*) str,
 188                                             info+sizeof(Dict_ptr)+
 189                                             sizeof(Dict_char),
 190                                             *after, client))
 191                             {
 192                                 *after = 0;
 193                             }
 194                             else
 195                                 --(*after);
 196                         }
 197                     }
 198                     if (*after && subptr)
 199                         scan_direction(dict, subptr, pos+1, str, -1,
 200                                        after, client, userfunc, 1);
 201                 }
 202                 else
 203                 {
 204                     if (subptr)
 205                         dict_scan_r(dict, subptr, pos+1, str, before, after,
 206                                     client, userfunc);
 207                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 208                     {
 209                         if (*before)
 210                         {
 211                             str[pos+1] = DICT_EOS;
 212                             if ((*userfunc)((char*) str,
 213                                             info+sizeof(Dict_ptr)+
 214                                             sizeof(Dict_char),
 215                                             - *before, client))
 216                             {
 217                                 *before = 0;
 218                             }
 219                             else
 220                                 --(*before);
 221                         }
 222                     }
 223                 }
 224                 break;
 225             }
 226         }
 227         if (cmp < 0)
 228             lo = mid+1;
 229         else
 230             hi = mid-1;
 231     }
 232     if (lo>hi && cmp < 0)
 233         ++mid;
 234     if (*after)
 235         scan_direction(dict, ptr, pos, str, cmp ? mid : mid+1, after,
 236                        client, userfunc, 1);
 237     if (*before && mid > 0)
 238         scan_direction(dict, ptr, pos, str, mid-1, before,
 239                        client, userfunc, -1);
 240 }
 241
 242 int dict_scan(Dict dict, char *str, int *before, int *after, void *client,
 243               int (*f)(char *name, const char *info, int pos, void *client))
 244 {
 245     int i;
 246
 247     yaz_log(YLOG_DEBUG, "dict_scan");
 248     for (i = 0; str[i]; i++)
 249     {
 250         yaz_log(YLOG_DEBUG, "start_term pos %d %3d  %c", i, str[i],
 251                 (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
 252     }
 253     if (!dict->head.root)
 254         return 0;
 255     dict_scan_r(dict, dict->head.root, 0, (Dict_char *) str,
 256                 before, after, client, f);
 257     return 0;
 258 }
 259 /*
 260  * Local variables:
 261  * c-basic-offset: 4
 262  * c-file-style: "Stroustrup"
 263  * indent-tabs-mode: nil
 264  * End:
 265  * vim: shiftwidth=4 tabstop=8 expandtab
 266  */
 267