2e300b645f12142b44f35e6ab3ab281bcdc7847e
[idzebra-moved-to-github.git] / dict / scan.c
1 /* $Id: scan.c,v 1.19 2005-01-15 19:38:24 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 int dict_scan_trav (Dict dict, Dict_ptr ptr, int pos, Dict_char *str, 
32                     int start, int *count, void *client,
33                     int (*userfunc)(char *, const char *, int, void *),
34                     int dir)
35 {
36     int lo, hi, j;
37     void *p;
38     short *indxp;
39     char *info;
40
41     dict_bf_readp (dict->dbf, ptr, &p);
42     hi = DICT_nodir(p)-1;
43     if (start != -1)
44         lo = start;
45     else
46     {
47         if (dir == -1)
48             lo = hi;
49         else
50             lo = 0;
51     }
52     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short)); 
53
54     while (lo <= hi && lo >= 0 && *count > 0)
55     {
56         if (indxp[-lo] > 0)
57         {
58             /* string (Dict_char *) DICT_EOS terminated */
59             /* unsigned char        length of information */
60             /* char *               information */
61
62             info = (char*)p + indxp[-lo];
63             for (j = 0; info[j] != DICT_EOS; j++)
64                 str[pos+j] = info[j];
65             str[pos+j] = DICT_EOS;
66             (*userfunc)((char*) str, info+(j+1)*sizeof(Dict_char),
67                             *count * dir, client);
68             --(*count);
69         }
70         else
71         {
72             Dict_char dc;
73             Dict_ptr subptr;
74
75             /* Dict_ptr             subptr */
76             /* Dict_char            sub char */
77             /* unsigned char        length of information */
78             /* char *               information */
79
80             info = (char*)p - indxp[-lo];
81             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
82             str[pos] = dc;
83             memcpy (&subptr, info, sizeof(Dict_ptr));
84             if (dir>0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
85             {
86                  str[pos+1] = DICT_EOS;
87                  if ((*userfunc)((char*) str,
88                                  info+sizeof(Dict_ptr)+sizeof(Dict_char),
89                                  *count * dir, client))
90                      return 1;
91                  --(*count);
92             }
93             if (*count>0 && subptr)
94             {
95                 dict_scan_trav (dict, subptr, pos+1, str, -1, count, 
96                                 client, userfunc, dir);
97                 dict_bf_readp (dict->dbf, ptr, &p);
98                 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short)); 
99             }
100             if (*count>0 && dir<0 && info[sizeof(Dict_ptr)+sizeof(Dict_char)])
101             {
102                  str[pos+1] = DICT_EOS;
103                  if ((*userfunc)((char*) str,
104                                  info+sizeof(Dict_ptr)+sizeof(Dict_char),
105                                  *count * dir, client))
106                      return 1;
107                  --(*count);
108             }
109         }
110         lo += dir;
111     }
112     return 0;
113 }
114
115 int dict_scan_r (Dict dict, Dict_ptr ptr, int pos, Dict_char *str, 
116                  int *before, int *after, void *client,
117                  int (*userfunc)(char *, const char *, int, void *))
118 {
119     int cmp = 0, mid, lo, hi;
120     void *p;
121     short *indxp;
122     char *info;
123
124     dict_bf_readp (dict->dbf, ptr, &p);
125     if (!p)
126         return 0;
127     mid = lo = 0;
128     hi = DICT_nodir(p)-1;
129     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
130     while (lo <= hi)
131     {
132         mid = (lo+hi)/2;
133         if (indxp[-mid] > 0)
134         {
135             /* string (Dict_char *) DICT_EOS terminated */
136             /* unsigned char        length of information */
137             /* char *               information */
138             info = (char*)p + indxp[-mid];
139             cmp = dict_strcmp ((Dict_char*) info, str + pos);
140             if (!cmp)
141             {
142                 if (*after)
143                 {
144                     (*userfunc)((char *) str, info+
145                                 (dict_strlen((Dict_char*) info)+1)
146                                 *sizeof(Dict_char), 
147                                 *after, client);
148                     --(*after);
149                 }
150                 break;
151             }
152         }
153         else
154         {
155             Dict_char dc;
156             Dict_ptr subptr;
157
158             /* Dict_ptr             subptr */
159             /* Dict_char            sub char */
160             /* unsigned char        length of information */
161             /* char *               information */
162             info = (char*)p - indxp[-mid];
163             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
164             cmp = dc - str[pos];
165             if (!cmp)
166             {
167                 memcpy (&subptr, info, sizeof(Dict_ptr));
168                 if (str[pos+1] == DICT_EOS)
169                 {
170                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
171                     {
172                         if (*after)
173                         {
174                             (*userfunc)((char*) str,
175                                         info+sizeof(Dict_ptr)+
176                                         sizeof(Dict_char),
177                                         *after, client);
178                             --(*after);
179                         }
180                     }
181                     if (*after && subptr)
182                         if (dict_scan_trav (dict, subptr, pos+1, str, -1, 
183                                             after, client, userfunc, 1))
184                             return 1;
185                 }
186                 else if (subptr)
187                 {
188                     if (dict_scan_r (dict, subptr, pos+1, str, before, after,
189                                      client, userfunc))
190                         return 1;
191                 }
192                 break;
193             }
194         }
195         if (cmp < 0)
196             lo = mid+1;
197         else
198             hi = mid-1;
199     }
200     if (lo>hi && cmp < 0)
201         ++mid;
202     if (*after)
203         if (dict_scan_trav (dict, ptr, pos, str, cmp ? mid : mid+1, after,
204                             client, userfunc, 1))
205             return 1;
206     if (*before && mid > 0)
207         if (dict_scan_trav (dict, ptr, pos, str, mid-1, before, 
208                             client, userfunc, -1))
209             return 1;
210     return 0;
211 }
212
213 int dict_scan (Dict dict, char *str, int *before, int *after, void *client,
214                int (*f)(char *name, const char *info, int pos, void *client))
215 {
216     int i;
217
218     yaz_log (YLOG_DEBUG, "dict_scan");
219     for (i = 0; str[i]; i++)
220     {
221         yaz_log (YLOG_DEBUG, " %3d  %c", str[i],
222               (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
223     }
224     if (!dict->head.root)
225         return 0;
226     return dict_scan_r (dict, dict->head.root, 0, (Dict_char *) str,
227                         before, after, client, f);
228 }