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