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