Happy new year
[idzebra-moved-to-github.git] / 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