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