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