Happy new year.
[idzebra-moved-to-github.git] / dict / scan.c
1 /* This file is part of the Zebra server.
2    Copyright (C) 1994-2011 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
21 #include <stdlib.h>
22 #include <string.h>
23 #include <stdio.h>
24 #include <assert.h>
25
26 #include "dict-p.h"
27
28 static void scan_direction(Dict dict, Dict_ptr ptr, int pos, Dict_char *str, 
29                            int start, int *count, void *client,
30                            int (*userfunc)(char *, const char *, int, void *),
31                            int dir)
32 {
33     int lo, hi, j;
34     void *p;
35     short *indxp;
36     char *info;
37
38     dict_bf_readp(dict->dbf, ptr, &p);
39     hi = DICT_nodir(p)-1;
40     if (start != -1)
41         lo = start;
42     else
43     {
44         if (dir == -1)
45             lo = hi;
46         else
47             lo = 0;
48     }
49     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short)); 
50
51     while (lo <= hi && lo >= 0 && *count > 0)
52     {
53         if (indxp[-lo] > 0)
54         {
55             /* string (Dict_char *) DICT_EOS terminated */
56             /* unsigned char        length of information */
57             /* char *               information */
58
59             info = (char*)p + indxp[-lo];
60             for (j = 0; info[j] != DICT_EOS; j++)
61                 str[pos+j] = info[j];
62             str[pos+j] = DICT_EOS;
63             if ((*userfunc)((char*) str, info+(j+1)*sizeof(Dict_char),
64                             *count * dir, client))
65             {
66                 *count = 0;
67             }
68             else
69                 --(*count);
70         }
71         else
72         {
73             Dict_char dc;
74             Dict_ptr subptr;
75
76             /* Dict_ptr             subptr */
77             /* Dict_char            sub char */
78             /* unsigned char        length of information */
79             /* char *               information */
80
81             info = (char*)p - indxp[-lo];
82             memcpy(&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
83             str[pos] = dc;
84             memcpy(&subptr, info, sizeof(Dict_ptr));
85             if (dir>0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
86             {
87                 str[pos+1] = DICT_EOS;
88                 if ((*userfunc)((char*) str,
89                                 info+sizeof(Dict_ptr)+sizeof(Dict_char),
90                                 *count * dir, client))
91                 {
92                     *count = 0;
93                 }
94                 else
95                     --(*count);
96             }
97             if (*count>0 && subptr)
98             {
99                 scan_direction(dict, subptr, pos+1, str, -1, count, 
100                                client, userfunc, dir);
101                 dict_bf_readp(dict->dbf, ptr, &p);
102                 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short)); 
103             }
104             if (*count>0 && dir<0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
105             {
106                 str[pos+1] = DICT_EOS;
107                 if ((*userfunc)((char*) str,
108                                 info+sizeof(Dict_ptr)+sizeof(Dict_char),
109                                 *count * dir, client))
110                 {
111                     *count = 0;
112                 }
113                 else
114                     --(*count);
115             }
116         }
117         lo += dir;
118     }
119 }
120
121 void dict_scan_r(Dict dict, Dict_ptr ptr, int pos, Dict_char *str, 
122                  int *before, int *after, void *client,
123                  int (*userfunc)(char *, const char *, int, void *))
124 {
125     int cmp = 0, mid, lo, hi;
126     void *p;
127     short *indxp;
128     char *info;
129
130     dict_bf_readp(dict->dbf, ptr, &p);
131     if (!p)
132         return;
133     mid = lo = 0;
134     hi = DICT_nodir(p)-1;
135     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
136     while (lo <= hi)
137     {
138         mid = (lo+hi)/2;
139         if (indxp[-mid] > 0)
140         {
141             /* string (Dict_char *) DICT_EOS terminated */
142             /* unsigned char        length of information */
143             /* char *               information */
144             info = (char*)p + indxp[-mid];
145             cmp = dict_strcmp((Dict_char*) info, str + pos);
146             if (!cmp)
147             {
148                 if (*after)
149                 {
150                     if ((*userfunc)((char *) str, info+
151                                     (dict_strlen((Dict_char*) info)+1)
152                                     *sizeof(Dict_char), 
153                                     *after, client))
154                     {
155                         *after = 0;
156                     }
157                     else
158                         --(*after);
159                 }
160                 break;
161             }
162         }
163         else
164         {
165             Dict_char dc;
166             Dict_ptr subptr;
167
168             /* Dict_ptr             subptr */
169             /* Dict_char            sub char */
170             /* unsigned char        length of information */
171             /* char *               information */
172             info = (char*)p - indxp[-mid];
173             memcpy(&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
174             cmp = dc - str[pos];
175             if (!cmp)
176             {
177                 memcpy(&subptr, info, sizeof(Dict_ptr));
178                 if (str[pos+1] == DICT_EOS)
179                 {
180                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
181                     {
182                         if (*after)
183                         {
184                             if ((*userfunc)((char*) str,
185                                             info+sizeof(Dict_ptr)+
186                                             sizeof(Dict_char),
187                                             *after, client))
188                             {
189                                 *after = 0;
190                             }
191                             else
192                                 --(*after);
193                         }
194                     }
195                     if (*after && subptr)
196                         scan_direction(dict, subptr, pos+1, str, -1, 
197                                        after, client, userfunc, 1);
198                 }
199                 else if (subptr)
200                 {
201                     dict_scan_r(dict, subptr, pos+1, str, before, after,
202                                 client, userfunc);
203                 }
204                 break;
205             }
206         }
207         if (cmp < 0)
208             lo = mid+1;
209         else
210             hi = mid-1;
211     }
212     if (lo>hi && cmp < 0)
213         ++mid;
214     if (*after)
215         scan_direction(dict, ptr, pos, str, cmp ? mid : mid+1, after,
216                        client, userfunc, 1);
217     if (*before && mid > 0)
218         scan_direction(dict, ptr, pos, str, mid-1, before, 
219                        client, userfunc, -1);
220 }
221
222 int dict_scan(Dict dict, char *str, int *before, int *after, void *client,
223               int (*f)(char *name, const char *info, int pos, void *client))
224 {
225     int i;
226
227     yaz_log(YLOG_DEBUG, "dict_scan");
228     for (i = 0; str[i]; i++)
229     {
230         yaz_log(YLOG_DEBUG, "start_term pos %d %3d  %c", i, str[i],
231                 (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
232     }
233     if (!dict->head.root)
234         return 0;
235     dict_scan_r(dict, dict->head.root, 0, (Dict_char *) str,
236                 before, after, client, f);
237     return 0;
238 }
239 /*
240  * Local variables:
241  * c-basic-offset: 4
242  * c-file-style: "Stroustrup"
243  * indent-tabs-mode: nil
244  * End:
245  * vim: shiftwidth=4 tabstop=8 expandtab
246  */
247