dict/scan.c

   1 /* $Id: scan.c,v 1.25 2007-01-15 15:10:15 adam Exp $
   2    Copyright (C) 1995-2007
   3    Index Data ApS
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 */
  22
  23
  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 if (subptr)
 203                 {
 204                     dict_scan_r(dict, subptr, pos+1, str, before, after,
 205                                 client, userfunc);
 206                 }
 207                 break;
 208             }
 209         }
 210         if (cmp < 0)
 211             lo = mid+1;
 212         else
 213             hi = mid-1;
 214     }
 215     if (lo>hi && cmp < 0)
 216         ++mid;
 217     if (*after)
 218         scan_direction(dict, ptr, pos, str, cmp ? mid : mid+1, after,
 219                        client, userfunc, 1);
 220     if (*before && mid > 0)
 221         scan_direction(dict, ptr, pos, str, mid-1, before,
 222                        client, userfunc, -1);
 223 }
 224
 225 int dict_scan(Dict dict, char *str, int *before, int *after, void *client,
 226               int (*f)(char *name, const char *info, int pos, void *client))
 227 {
 228     int i;
 229
 230     yaz_log(YLOG_DEBUG, "dict_scan");
 231     for (i = 0; str[i]; i++)
 232     {
 233         yaz_log(YLOG_DEBUG, "start_term pos %d %3d  %c", i, str[i],
 234                 (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
 235     }
 236     if (!dict->head.root)
 237         return 0;
 238     dict_scan_r(dict, dict->head.root, 0, (Dict_char *) str,
 239                 before, after, client, f);
 240     return 0;
 241 }
 242 /*
 243  * Local variables:
 244  * c-basic-offset: 4
 245  * indent-tabs-mode: nil
 246  * End:
 247  * vim: shiftwidth=4 tabstop=8 expandtab
 248  */
 249