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