dict/lookupec.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: lookupec.c,v $
   7  * Revision 1.3  1994-09-26 16:31:06  adam
   8  * Minor changes.
   9  *
  10  * Revision 1.2  1994/09/22  14:43:57  adam
  11  * First functional version of lookup with error correction. A 'range'
  12  * specified the maximum number of insertions+deletions+substitutions.
  13  *
  14  * Revision 1.1  1994/09/22  10:43:44  adam
  15  * Two versions of depend. Type 1 is the tail-type compatible with
  16  * all make programs. Type 2 is the GNU make with include facility.
  17  * Type 2 is default. depend rule chooses current rule.
  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 typedef unsigned MatchWord;
  28
  29 typedef struct {
  30     MatchWord *s;
  31     int m;
  32 } MatchInfo;
  33
  34 #define SH(x) (((x)<<1)+1)
  35
  36 int dict_look_ec (Dict dict, Dict_ptr ptr, MatchInfo *mi, MatchWord *ri_base,
  37                   int pos, int (*userfunc)(Dict_char *),
  38                   int range, Dict_char *prefix)
  39 {
  40     int lo, hi;
  41     void *p;
  42     short *indxp;
  43     char *info;
  44     MatchWord match_mask = 1<<(mi->m-1);
  45
  46     dict_bf_readp (dict->dbf, ptr, &p);
  47     lo = 0;
  48     hi = DICT_nodir(p)-1;
  49     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
  50     while (lo <= hi)
  51     {
  52         if (indxp[-lo] > 0)
  53         {
  54             /* string (Dict_char *) DICT_EOS terminated */
  55             /* unsigned char        length of information */
  56             /* char *               information */
  57             MatchWord *ri = ri_base, sc;
  58             int i, j;
  59             info = (char*)p + indxp[-lo];
  60             for (j=0; ; j++)
  61             {
  62                 Dict_char ch;
  63
  64                 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
  65                 prefix[pos+j] = ch;
  66                 if (ch == DICT_EOS)
  67                 {
  68                     if (ri[range] & match_mask)
  69                         (*userfunc)(prefix);
  70                     break;
  71                 }
  72                 if (j+pos >= mi->m+range)
  73                     break;
  74                 sc = mi->s[ch & 255];
  75                 ri[1+range] = SH(ri[0]) & sc;
  76                 for (i=1; i<=range; i++)
  77                     ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
  78                         | SH(ri[i+range]) | ri[i-1];
  79                 ri += 1+range;
  80                 if (!(ri[range] & (1<<(pos+j))))
  81                     break;
  82             }
  83         }
  84         else
  85         {
  86             Dict_char ch;
  87             MatchWord *ri = ri_base, sc;
  88             int i;
  89
  90             /* Dict_ptr             subptr */
  91             /* Dict_char            sub char */
  92             /* unsigned char        length of information */
  93             /* char *               information */
  94             info = (char*)p - indxp[-lo];
  95             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
  96             prefix[pos] = ch;
  97
  98             sc = mi->s[ch & 255];
  99             ri[1+range] = SH(ri[0]) & sc;
 100             for (i=1; i<=range; i++)
 101                 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
 102                     | SH(ri[i+range]) | ri[i-1];
 103             ri += 1+range;
 104             if (ri[range] & (1<<pos))
 105             {
 106                 Dict_ptr subptr;
 107                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)] &&
 108                     (ri[range] & match_mask))
 109                 {
 110                     prefix[pos+1] = DICT_EOS;
 111                     (*userfunc)(prefix);
 112                 }
 113                 memcpy (&subptr, info, sizeof(Dict_ptr));
 114                 if (subptr)
 115                 {
 116                     dict_look_ec (dict, subptr, mi, ri, pos+1,
 117                                   userfunc, range, prefix);
 118                     dict_bf_readp (dict->dbf, ptr, &p);
 119                     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 120                 }
 121             }
 122         }
 123         lo++;
 124     }
 125     return 0;
 126 }
 127
 128 static MatchInfo *prepare_match (Dict_char *pattern)
 129 {
 130     int i;
 131     MatchWord *s;
 132     MatchInfo *mi;
 133
 134     mi = xmalloc (sizeof(*mi));
 135     mi->m = dict_strlen (pattern);
 136     mi->s = s = xmalloc (sizeof(*s)*256);  /* 256 !!! */
 137     for (i=0; i<256; i++)
 138         s[i] = 0;
 139     for (i=0; pattern[i]; i++)
 140         s[pattern[i]&255] += 1<<i;
 141     return mi;
 142 }
 143
 144 int dict_lookup_ec (Dict dict, Dict_char *pattern, int range,
 145                     int (*userfunc)(Dict_char *name))
 146 {
 147     MatchInfo *mi;
 148     MatchWord *ri;
 149     int i;
 150     Dict_char prefix[2048];
 151
 152     if (dict->head.last == 1)
 153         return 0;
 154
 155     mi = prepare_match (pattern);
 156
 157 #if 1
 158     ri = xmalloc ((dict_strlen(pattern)+range+2)*(range+1)*sizeof(*ri));
 159 #else
 160     ri = xmalloc (2048 * (range+1) * sizeof(*ri));
 161 #endif
 162
 163     for (i=0; i<=range; i++)
 164         ri[i] = (2<<i)-1;
 165
 166     i = dict_look_ec (dict, 1, mi, ri, 0, userfunc, range, prefix);
 167     xfree (ri);
 168     return i;
 169 }
 170
 171
 172
 173