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