dict/scan.c

   1 /* $Id: scan.c,v 1.17 2004-12-07 20:04:39 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   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 Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <stdio.h>
  27 #include <assert.h>
  28
  29 #include <dict.h>
  30
  31 int dict_scan_trav (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             (*userfunc)((char*) str, info+(j+1)*sizeof(Dict_char),
  67                             *count * dir, client);
  68             --(*count);
  69         }
  70         else
  71         {
  72             Dict_char dc;
  73             Dict_ptr subptr;
  74
  75             /* Dict_ptr             subptr */
  76             /* Dict_char            sub char */
  77             /* unsigned char        length of information */
  78             /* char *               information */
  79
  80             info = (char*)p - indxp[-lo];
  81             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  82             str[pos] = dc;
  83             memcpy (&subptr, info, sizeof(Dict_ptr));
  84             if (dir>0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  85             {
  86                  str[pos+1] = DICT_EOS;
  87                  if ((*userfunc)((char*) str,
  88                                  info+sizeof(Dict_ptr)+sizeof(Dict_char),
  89                                  *count * dir, client))
  90                      return 1;
  91                  --(*count);
  92             }
  93             if (*count>0 && subptr)
  94             {
  95                 dict_scan_trav (dict, subptr, pos+1, str, -1, count,
  96                                 client, userfunc, dir);
  97                 dict_bf_readp (dict->dbf, ptr, &p);
  98                 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  99             }
 100             if (*count>0 && dir<0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 101             {
 102                  str[pos+1] = DICT_EOS;
 103                  if ((*userfunc)((char*) str,
 104                                  info+sizeof(Dict_ptr)+sizeof(Dict_char),
 105                                  *count * dir, client))
 106                      return 1;
 107                  --(*count);
 108             }
 109         }
 110         lo += dir;
 111     }
 112     return 0;
 113 }
 114
 115 int dict_scan_r (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
 116                  int *before, int *after, void *client,
 117                  int (*userfunc)(char *, const char *, int, void *))
 118 {
 119     int cmp = 0, mid, lo, hi;
 120     void *p;
 121     short *indxp;
 122     char *info;
 123
 124     dict_bf_readp (dict->dbf, ptr, &p);
 125     if (!p)
 126         return 0;
 127     mid = lo = 0;
 128     hi = DICT_nodir(p)-1;
 129     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 130     while (lo <= hi)
 131     {
 132         mid = (lo+hi)/2;
 133         if (indxp[-mid] > 0)
 134         {
 135             /* string (Dict_char *) DICT_EOS terminated */
 136             /* unsigned char        length of information */
 137             /* char *               information */
 138             info = (char*)p + indxp[-mid];
 139             cmp = dict_strcmp ((Dict_char*) info, str + pos);
 140             if (!cmp)
 141             {
 142                 if (*after)
 143                 {
 144                     (*userfunc)((char *) str, info+
 145                                 (dict_strlen((Dict_char*) info)+1)
 146                                 *sizeof(Dict_char),
 147                                 *after, client);
 148                     --(*after);
 149                 }
 150                 break;
 151             }
 152         }
 153         else
 154         {
 155             Dict_char dc;
 156             Dict_ptr subptr;
 157
 158             /* Dict_ptr             subptr */
 159             /* Dict_char            sub char */
 160             /* unsigned char        length of information */
 161             /* char *               information */
 162             info = (char*)p - indxp[-mid];
 163             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 164             cmp = dc - str[pos];
 165             if (!cmp)
 166             {
 167                 memcpy (&subptr, info, sizeof(Dict_ptr));
 168                 if (str[pos+1] == DICT_EOS)
 169                 {
 170                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 171                     {
 172                         if (*after)
 173                         {
 174                             (*userfunc)((char*) str,
 175                                         info+sizeof(Dict_ptr)+
 176                                         sizeof(Dict_char),
 177                                         *after, client);
 178                             --(*after);
 179                         }
 180                     }
 181                     if (*after && subptr)
 182                         if (dict_scan_trav (dict, subptr, pos+1, str, -1,
 183                                             after, client, userfunc, 1))
 184                             return 1;
 185                 }
 186                 else if (subptr)
 187                 {
 188                     if (dict_scan_r (dict, subptr, pos+1, str, before, after,
 189                                      client, userfunc))
 190                         return 1;
 191                 }
 192                 break;
 193             }
 194         }
 195         if (cmp < 0)
 196             lo = mid+1;
 197         else
 198             hi = mid-1;
 199     }
 200     if (lo>hi && cmp < 0)
 201         ++mid;
 202     if (*after)
 203         if (dict_scan_trav (dict, ptr, pos, str, cmp ? mid : mid+1, after,
 204                             client, userfunc, 1))
 205             return 1;
 206     if (*before && mid > 0)
 207         if (dict_scan_trav (dict, ptr, pos, str, mid-1, before,
 208                             client, userfunc, -1))
 209             return 1;
 210     return 0;
 211 }
 212
 213 int dict_scan (Dict dict, char *str, int *before, int *after, void *client,
 214                int (*f)(char *name, const char *info, int pos, void *client))
 215 {
 216     int i;
 217
 218     yaz_log (YLOG_DEBUG, "dict_scan");
 219     for (i = 0; str[i]; i++)
 220     {
 221         yaz_log (YLOG_DEBUG, " %3d  %c", str[i],
 222               (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
 223     }
 224     if (!dict->head.root)
 225         return 0;
 226     return dict_scan_r (dict, dict->head.root, 0, (Dict_char *) str,
 227                         before, after, client, f);
 228 }