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