dict/lookupec.c

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