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