dict/scan.c

   1 /* $Id: scan.c,v 1.15 2002-08-02 19:26:55 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 (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         }
 101         lo += dir;
 102     }
 103     return 0;
 104 }
 105
 106 int dict_scan_r (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
 107                  int *before, int *after, void *client,
 108                  int (*userfunc)(char *, const char *, int, void *))
 109 {
 110     int cmp = 0, mid, lo, hi;
 111     void *p;
 112     short *indxp;
 113     char *info;
 114
 115     dict_bf_readp (dict->dbf, ptr, &p);
 116     if (!p)
 117         return 0;
 118     mid = lo = 0;
 119     hi = DICT_nodir(p)-1;
 120     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 121     while (lo <= hi)
 122     {
 123         mid = (lo+hi)/2;
 124         if (indxp[-mid] > 0)
 125         {
 126             /* string (Dict_char *) DICT_EOS terminated */
 127             /* unsigned char        length of information */
 128             /* char *               information */
 129             info = (char*)p + indxp[-mid];
 130             cmp = dict_strcmp ((Dict_char*) info, str + pos);
 131             if (!cmp)
 132             {
 133                 if (*after)
 134                 {
 135                     (*userfunc)((char *) str, info+
 136                                 (dict_strlen((Dict_char*) info)+1)
 137                                 *sizeof(Dict_char),
 138                                 *after, client);
 139                     --(*after);
 140                 }
 141                 break;
 142             }
 143         }
 144         else
 145         {
 146             Dict_char dc;
 147             Dict_ptr subptr;
 148
 149             /* Dict_ptr             subptr */
 150             /* Dict_char            sub char */
 151             /* unsigned char        length of information */
 152             /* char *               information */
 153             info = (char*)p - indxp[-mid];
 154             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 155             cmp = dc - str[pos];
 156             if (!cmp)
 157             {
 158                 memcpy (&subptr, info, sizeof(Dict_ptr));
 159                 if (str[pos+1] == DICT_EOS)
 160                 {
 161                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 162                     {
 163                         if (*after)
 164                         {
 165                             (*userfunc)((char*) str,
 166                                         info+sizeof(Dict_ptr)+
 167                                         sizeof(Dict_char),
 168                                         *after, client);
 169                             --(*after);
 170                         }
 171                     }
 172                     if (*after && subptr)
 173                         if (dict_scan_trav (dict, subptr, pos+1, str, -1,
 174                                             after, client, userfunc, 1))
 175                             return 1;
 176                 }
 177                 else if (subptr)
 178                 {
 179                     if (dict_scan_r (dict, subptr, pos+1, str, before, after,
 180                                      client, userfunc))
 181                         return 1;
 182                 }
 183                 break;
 184             }
 185         }
 186         if (cmp < 0)
 187             lo = mid+1;
 188         else
 189             hi = mid-1;
 190     }
 191     if (lo>hi && cmp < 0)
 192         ++mid;
 193     if (*after)
 194         if (dict_scan_trav (dict, ptr, pos, str, cmp ? mid : mid+1, after,
 195                             client, userfunc, 1))
 196             return 1;
 197     if (*before && mid > 0)
 198         if (dict_scan_trav (dict, ptr, pos, str, mid-1, before,
 199                             client, userfunc, -1))
 200             return 1;
 201     return 0;
 202 }
 203
 204 int dict_scan (Dict dict, char *str, int *before, int *after, void *client,
 205                int (*f)(char *name, const char *info, int pos, void *client))
 206 {
 207     int i;
 208
 209     logf (LOG_DEBUG, "dict_scan");
 210     for (i = 0; str[i]; i++)
 211     {
 212         logf (LOG_DEBUG, " %3d  %c", str[i],
 213               (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
 214     }
 215     if (!dict->head.root)
 216         return 0;
 217     return dict_scan_r (dict, dict->head.root, 0, (Dict_char *) str,
 218                         before, after, client, f);
 219 }