dict/lookupec.c

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