dict/scan.c

   1 /*
   2  * Copyright (C) 1994-2002, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Id: scan.c,v 1.14 2002-01-14 01:52:22 adam Exp $
   7  */
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <stdio.h>
  11 #include <assert.h>
  12
  13 #include <dict.h>
  14
  15 int dict_scan_trav (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
  16                     int start, int *count, void *client,
  17                     int (*userfunc)(char *, const char *, int, void *),
  18                     int dir)
  19 {
  20     int lo, hi, j;
  21     void *p;
  22     short *indxp;
  23     char *info;
  24
  25     dict_bf_readp (dict->dbf, ptr, &p);
  26     hi = DICT_nodir(p)-1;
  27     if (start != -1)
  28         lo = start;
  29     else
  30     {
  31         if (dir == -1)
  32             lo = hi;
  33         else
  34             lo = 0;
  35     }
  36     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  37
  38     while (lo <= hi && lo >= 0 && *count > 0)
  39     {
  40         if (indxp[-lo] > 0)
  41         {
  42             /* string (Dict_char *) DICT_EOS terminated */
  43             /* unsigned char        length of information */
  44             /* char *               information */
  45
  46             info = (char*)p + indxp[-lo];
  47             for (j = 0; info[j] != DICT_EOS; j++)
  48                 str[pos+j] = info[j];
  49             str[pos+j] = DICT_EOS;
  50             (*userfunc)((char*) str, info+(j+1)*sizeof(Dict_char),
  51                             *count * dir, client);
  52             --(*count);
  53         }
  54         else
  55         {
  56             Dict_char dc;
  57             Dict_ptr subptr;
  58
  59             /* Dict_ptr             subptr */
  60             /* Dict_char            sub char */
  61             /* unsigned char        length of information */
  62             /* char *               information */
  63
  64             info = (char*)p - indxp[-lo];
  65             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  66             str[pos] = dc;
  67             memcpy (&subptr, info, sizeof(Dict_ptr));
  68             if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  69             {
  70                  str[pos+1] = DICT_EOS;
  71                  if ((*userfunc)((char*) str,
  72                                  info+sizeof(Dict_ptr)+sizeof(Dict_char),
  73                                  *count * dir, client))
  74                      return 1;
  75                  --(*count);
  76             }
  77             if (*count > 0 && subptr)
  78             {
  79                 dict_scan_trav (dict, subptr, pos+1, str, -1, count,
  80                                 client, userfunc, dir);
  81                 dict_bf_readp (dict->dbf, ptr, &p);
  82                 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  83             }
  84         }
  85         lo += dir;
  86     }
  87     return 0;
  88 }
  89
  90 int dict_scan_r (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
  91                  int *before, int *after, void *client,
  92                  int (*userfunc)(char *, const char *, int, void *))
  93 {
  94     int cmp = 0, mid, lo, hi;
  95     void *p;
  96     short *indxp;
  97     char *info;
  98
  99     dict_bf_readp (dict->dbf, ptr, &p);
 100     if (!p)
 101         return 0;
 102     mid = lo = 0;
 103     hi = DICT_nodir(p)-1;
 104     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 105     while (lo <= hi)
 106     {
 107         mid = (lo+hi)/2;
 108         if (indxp[-mid] > 0)
 109         {
 110             /* string (Dict_char *) DICT_EOS terminated */
 111             /* unsigned char        length of information */
 112             /* char *               information */
 113             info = (char*)p + indxp[-mid];
 114             cmp = dict_strcmp ((Dict_char*) info, str + pos);
 115             if (!cmp)
 116             {
 117                 if (*after)
 118                 {
 119                     (*userfunc)((char *) str, info+
 120                                 (dict_strlen((Dict_char*) info)+1)
 121                                 *sizeof(Dict_char),
 122                                 *after, client);
 123                     --(*after);
 124                 }
 125                 break;
 126             }
 127         }
 128         else
 129         {
 130             Dict_char dc;
 131             Dict_ptr subptr;
 132
 133             /* Dict_ptr             subptr */
 134             /* Dict_char            sub char */
 135             /* unsigned char        length of information */
 136             /* char *               information */
 137             info = (char*)p - indxp[-mid];
 138             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 139             cmp = dc - str[pos];
 140             if (!cmp)
 141             {
 142                 memcpy (&subptr, info, sizeof(Dict_ptr));
 143                 if (str[pos+1] == DICT_EOS)
 144                 {
 145                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 146                     {
 147                         if (*after)
 148                         {
 149                             (*userfunc)((char*) str,
 150                                         info+sizeof(Dict_ptr)+
 151                                         sizeof(Dict_char),
 152                                         *after, client);
 153                             --(*after);
 154                         }
 155                     }
 156                     if (*after && subptr)
 157                         if (dict_scan_trav (dict, subptr, pos+1, str, -1,
 158                                             after, client, userfunc, 1))
 159                             return 1;
 160                 }
 161                 else if (subptr)
 162                 {
 163                     if (dict_scan_r (dict, subptr, pos+1, str, before, after,
 164                                      client, userfunc))
 165                         return 1;
 166                 }
 167                 break;
 168             }
 169         }
 170         if (cmp < 0)
 171             lo = mid+1;
 172         else
 173             hi = mid-1;
 174     }
 175     if (lo>hi && cmp < 0)
 176         ++mid;
 177     if (*after)
 178         if (dict_scan_trav (dict, ptr, pos, str, cmp ? mid : mid+1, after,
 179                             client, userfunc, 1))
 180             return 1;
 181     if (*before && mid > 0)
 182         if (dict_scan_trav (dict, ptr, pos, str, mid-1, before,
 183                             client, userfunc, -1))
 184             return 1;
 185     return 0;
 186 }
 187
 188 int dict_scan (Dict dict, char *str, int *before, int *after, void *client,
 189                int (*f)(char *name, const char *info, int pos, void *client))
 190 {
 191     int i;
 192
 193     logf (LOG_DEBUG, "dict_scan");
 194     for (i = 0; str[i]; i++)
 195     {
 196         logf (LOG_DEBUG, " %3d  %c", str[i],
 197               (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
 198     }
 199     if (!dict->head.root)
 200         return 0;
 201     return dict_scan_r (dict, dict->head.root, 0, (Dict_char *) str,
 202                         before, after, client, f);
 203 }