dict/lookupec.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2009 Index Data
   3
   4 Zebra is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include <stdio.h>
  23 #include <assert.h>
  24
  25 #include "dict-p.h"
  26
  27 typedef unsigned MatchWord;
  28
  29 typedef struct {
  30     MatchWord *s;
  31     int m;
  32 } MatchInfo;
  33
  34 #define SH(x) (((x)<<1)+1)
  35
  36 static int lookup_ec(Dict dict, Dict_ptr ptr,
  37                      MatchInfo *mi, MatchWord *ri_base,
  38                      int pos, int (*userfunc)(char *), int range,
  39                      Dict_char *prefix)
  40 {
  41     int lo, hi;
  42     void *p;
  43     short *indxp;
  44     char *info;
  45     MatchWord match_mask = 1<<(mi->m-1);
  46
  47     dict_bf_readp (dict->dbf, ptr, &p);
  48     lo = 0;
  49     hi = DICT_nodir(p)-1;
  50     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  51     while (lo <= hi)
  52     {
  53         if (indxp[-lo] > 0)
  54         {
  55             /* string (Dict_char *) DICT_EOS terminated */
  56             /* unsigned char        length of information */
  57             /* char *               information */
  58             MatchWord *ri = ri_base, sc;
  59             int i, j;
  60             info = (char*)p + indxp[-lo];
  61             for (j=0; ; j++)
  62             {
  63                 Dict_char ch;
  64
  65                 memcpy(&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
  66                 prefix[pos+j] = ch;
  67                 if (ch == DICT_EOS)
  68                 {
  69                     if (ri[range] & match_mask)
  70                         (*userfunc)((char*) prefix);
  71                     break;
  72                 }
  73                 if (j+pos >= mi->m+range)
  74                     break;
  75                 sc = mi->s[ch & 255];
  76                 ri[1+range] = SH(ri[0]) & sc;
  77                 for (i=1; i<=range; i++)
  78                     ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
  79                         | SH(ri[i+range]) | ri[i-1];
  80                 ri += 1+range;
  81                 if (!(ri[range] & (1<<(pos+j))))
  82                     break;
  83             }
  84         }
  85         else
  86         {
  87             Dict_char ch;
  88             MatchWord *ri = ri_base, sc;
  89             int i;
  90
  91             /* Dict_ptr             subptr */
  92             /* Dict_char            sub char */
  93             /* unsigned char        length of information */
  94             /* char *               information */
  95             info = (char*)p - indxp[-lo];
  96             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
  97             prefix[pos] = ch;
  98
  99             sc = mi->s[ch & 255];
 100             ri[1+range] = SH(ri[0]) & sc;
 101             for (i=1; i<=range; i++)
 102                 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
 103                     | SH(ri[i+range]) | ri[i-1];
 104             ri += 1+range;
 105             if (ri[range] & (1<<pos))
 106             {
 107                 Dict_ptr subptr;
 108                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)] &&
 109                     (ri[range] & match_mask))
 110                 {
 111                     prefix[pos+1] = DICT_EOS;
 112                     (*userfunc)((char*) prefix);
 113                 }
 114                 memcpy(&subptr, info, sizeof(Dict_ptr));
 115                 if (subptr)
 116                 {
 117                     lookup_ec(dict, subptr, mi, ri, pos+1,
 118                               userfunc, range, prefix);
 119                     dict_bf_readp(dict->dbf, ptr, &p);
 120                     indxp = (short*) ((char*) p +
 121                                       DICT_bsize(p)-sizeof(short));
 122                 }
 123             }
 124         }
 125         lo++;
 126     }
 127     return 0;
 128 }
 129
 130 static MatchInfo *prepare_match(Dict_char *pattern)
 131 {
 132     int i;
 133     MatchWord *s;
 134     MatchInfo *mi;
 135
 136     mi = (MatchInfo *) xmalloc(sizeof(*mi));
 137     mi->m = dict_strlen (pattern);
 138     mi->s = s = (MatchWord *) xmalloc(sizeof(*s)*256);  /* 256 !!! */
 139     for (i = 0; i < 256; i++)
 140         s[i] = 0;
 141     for (i = 0; pattern[i]; i++)
 142         s[pattern[i]&255] += 1<<i;
 143     return mi;
 144 }
 145
 146 int dict_lookup_ec(Dict dict, char *pattern, int range,
 147                    int (*userfunc)(char *name))
 148 {
 149     MatchInfo *mi;
 150     MatchWord *ri;
 151     int ret, i;
 152     Dict_char prefix[2048];
 153
 154     if (!dict->head.root)
 155         return 0;
 156
 157     mi = prepare_match((Dict_char*) pattern);
 158
 159     ri = (MatchWord *) xmalloc((dict_strlen((Dict_char*) pattern)+range+2)
 160                                * (range+1)*sizeof(*ri));
 161     for (i = 0; i <= range; i++)
 162         ri[i] = (2<<i)-1;
 163
 164     ret = lookup_ec(dict, dict->head.root, mi, ri, 0, userfunc,
 165                     range, prefix);
 166     xfree(ri);
 167     return ret;
 168 }
 169
 170 /*
 171  * Local variables:
 172  * c-basic-offset: 4
 173  * indent-tabs-mode: nil
 174  * End:
 175  * vim: shiftwidth=4 tabstop=8 expandtab
 176  */
 177