Put local variables footer in all c, h files.
[idzebra-moved-to-github.git] / 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