dict/scan.c

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