dict/scan.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2011 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 #include <stdlib.h>
  22 #include <string.h>
  23 #include <stdio.h>
  24 #include <assert.h>
  25
  26 #include "dict-p.h"
  27
  28 static void scan_direction(Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
  29                            int start, int *count, void *client,
  30                            int (*userfunc)(char *, const char *, int, void *),
  31                            int dir)
  32 {
  33     int lo, hi, j;
  34     void *p;
  35     short *indxp;
  36     char *info;
  37
  38     dict_bf_readp(dict->dbf, ptr, &p);
  39     hi = DICT_nodir(p)-1;
  40     if (start != -1)
  41         lo = start;
  42     else
  43     {
  44         if (dir == -1)
  45             lo = hi;
  46         else
  47             lo = 0;
  48     }
  49     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  50
  51     while (lo <= hi && lo >= 0 && *count > 0)
  52     {
  53         if (indxp[-lo] > 0)
  54         {
  55             /* string (Dict_char *) DICT_EOS terminated */
  56             /* unsigned char        length of information */
  57             /* char *               information */
  58
  59             info = (char*)p + indxp[-lo];
  60             for (j = 0; info[j] != DICT_EOS; j++)
  61                 str[pos+j] = info[j];
  62             str[pos+j] = DICT_EOS;
  63             if ((*userfunc)((char*) str, info+(j+1)*sizeof(Dict_char),
  64                             *count * dir, client))
  65             {
  66                 *count = 0;
  67             }
  68             else
  69                 --(*count);
  70         }
  71         else
  72         {
  73             Dict_char dc;
  74             Dict_ptr subptr;
  75
  76             /* Dict_ptr             subptr */
  77             /* Dict_char            sub char */
  78             /* unsigned char        length of information */
  79             /* char *               information */
  80
  81             info = (char*)p - indxp[-lo];
  82             memcpy(&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  83             str[pos] = dc;
  84             memcpy(&subptr, info, sizeof(Dict_ptr));
  85             if (dir>0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  86             {
  87                 str[pos+1] = DICT_EOS;
  88                 if ((*userfunc)((char*) str,
  89                                 info+sizeof(Dict_ptr)+sizeof(Dict_char),
  90                                 *count * dir, client))
  91                 {
  92                     *count = 0;
  93                 }
  94                 else
  95                     --(*count);
  96             }
  97             if (*count>0 && subptr)
  98             {
  99                 scan_direction(dict, subptr, pos+1, str, -1, count,
 100                                client, userfunc, dir);
 101                 dict_bf_readp(dict->dbf, ptr, &p);
 102                 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 103             }
 104             if (*count>0 && dir<0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 105             {
 106                 str[pos+1] = DICT_EOS;
 107                 if ((*userfunc)((char*) str,
 108                                 info+sizeof(Dict_ptr)+sizeof(Dict_char),
 109                                 *count * dir, client))
 110                 {
 111                     *count = 0;
 112                 }
 113                 else
 114                     --(*count);
 115             }
 116         }
 117         lo += dir;
 118     }
 119 }
 120
 121 void dict_scan_r(Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
 122                  int *before, int *after, void *client,
 123                  int (*userfunc)(char *, const char *, int, void *))
 124 {
 125     int cmp = 0, mid, lo, hi;
 126     void *p;
 127     short *indxp;
 128     char *info;
 129
 130     dict_bf_readp(dict->dbf, ptr, &p);
 131     if (!p)
 132         return;
 133     mid = lo = 0;
 134     hi = DICT_nodir(p)-1;
 135     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 136     while (lo <= hi)
 137     {
 138         mid = (lo+hi)/2;
 139         if (indxp[-mid] > 0)
 140         {
 141             /* string (Dict_char *) DICT_EOS terminated */
 142             /* unsigned char        length of information */
 143             /* char *               information */
 144             info = (char*)p + indxp[-mid];
 145             cmp = dict_strcmp((Dict_char*) info, str + pos);
 146             if (!cmp)
 147             {
 148                 if (*after)
 149                 {
 150                     if ((*userfunc)((char *) str, info+
 151                                     (dict_strlen((Dict_char*) info)+1)
 152                                     *sizeof(Dict_char),
 153                                     *after, client))
 154                     {
 155                         *after = 0;
 156                     }
 157                     else
 158                         --(*after);
 159                 }
 160                 break;
 161             }
 162         }
 163         else
 164         {
 165             Dict_char dc;
 166             Dict_ptr subptr;
 167
 168             /* Dict_ptr             subptr */
 169             /* Dict_char            sub char */
 170             /* unsigned char        length of information */
 171             /* char *               information */
 172             info = (char*)p - indxp[-mid];
 173             memcpy(&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 174             cmp = dc - str[pos];
 175             if (!cmp)
 176             {
 177                 memcpy(&subptr, info, sizeof(Dict_ptr));
 178                 if (str[pos+1] == DICT_EOS)
 179                 {
 180                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 181                     {
 182                         if (*after)
 183                         {
 184                             if ((*userfunc)((char*) str,
 185                                             info+sizeof(Dict_ptr)+
 186                                             sizeof(Dict_char),
 187                                             *after, client))
 188                             {
 189                                 *after = 0;
 190                             }
 191                             else
 192                                 --(*after);
 193                         }
 194                     }
 195                     if (*after && subptr)
 196                         scan_direction(dict, subptr, pos+1, str, -1,
 197                                        after, client, userfunc, 1);
 198                 }
 199                 else if (subptr)
 200                 {
 201                     dict_scan_r(dict, subptr, pos+1, str, before, after,
 202                                 client, userfunc);
 203                 }
 204                 break;
 205             }
 206         }
 207         if (cmp < 0)
 208             lo = mid+1;
 209         else
 210             hi = mid-1;
 211     }
 212     if (lo>hi && cmp < 0)
 213         ++mid;
 214     if (*after)
 215         scan_direction(dict, ptr, pos, str, cmp ? mid : mid+1, after,
 216                        client, userfunc, 1);
 217     if (*before && mid > 0)
 218         scan_direction(dict, ptr, pos, str, mid-1, before,
 219                        client, userfunc, -1);
 220 }
 221
 222 int dict_scan(Dict dict, char *str, int *before, int *after, void *client,
 223               int (*f)(char *name, const char *info, int pos, void *client))
 224 {
 225     int i;
 226
 227     yaz_log(YLOG_DEBUG, "dict_scan");
 228     for (i = 0; str[i]; i++)
 229     {
 230         yaz_log(YLOG_DEBUG, "start_term pos %d %3d  %c", i, str[i],
 231                 (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
 232     }
 233     if (!dict->head.root)
 234         return 0;
 235     dict_scan_r(dict, dict->head.root, 0, (Dict_char *) str,
 236                 before, after, client, f);
 237     return 0;
 238 }
 239 /*
 240  * Local variables:
 241  * c-basic-offset: 4
 242  * c-file-style: "Stroustrup"
 243  * indent-tabs-mode: nil
 244  * End:
 245  * vim: shiftwidth=4 tabstop=8 expandtab
 246  */
 247