added more instructions to DOM filter docs, spell checked both DOM and Alvis filter...
[idzebra-moved-to-github.git] / dict / delete.c
1 /* $Id: delete.c,v 1.14 2007-01-15 15:10:15 adam Exp $
2    Copyright (C) 1995-2007
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 this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20
21 */
22
23 #include <stdlib.h>
24 #include <string.h>
25 #include <stdio.h>
26 #include <assert.h>
27
28 #include "dict-p.h"
29
30 static void dict_del_subtree (Dict dict, Dict_ptr ptr,
31                               void *client, 
32                               int (*f)(const char *, void *))
33 {
34     void *p = 0;
35     short *indxp;
36     int i, hi;
37     
38     if (!ptr)
39         return;
40         
41     dict_bf_readp (dict->dbf, ptr, &p);
42     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
43     hi = DICT_nodir(p)-1;
44     for (i = 0; i <= hi; i++)
45     {
46         if (indxp[-i] > 0)
47         {
48             /* string (Dict_char *) DICT_EOS terminated */
49             /* unsigned char        length of information */
50             /* char *               information */
51             char *info = (char*)p + indxp[-i];
52             if (f)
53                 (*f)(info + (dict_strlen((Dict_char*) info)+1)
54                      *sizeof(Dict_char), client);
55         }
56         else
57         {
58             Dict_ptr subptr;
59             
60             /* Dict_ptr             subptr */
61             /* Dict_char            sub char */
62             /* unsigned char        length of information */
63             /* char *               information */
64             char *info = (char*)p - indxp[-i];
65             memcpy (&subptr, info, sizeof(Dict_ptr));
66             
67             if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
68             {
69                 if (f)
70                     (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char), client);
71             }
72             if (subptr)
73             {
74                 dict_del_subtree (dict, subptr, client, f);
75         
76                 /* page may be gone. reread it .. */
77                 dict_bf_readp (dict->dbf, ptr, &p);
78                 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
79             }
80         }
81     }
82     DICT_backptr(p) = dict->head.freelist;
83     dict->head.freelist = ptr;
84     dict_bf_touch (dict->dbf, ptr);
85 }
86
87 static int dict_del_string (Dict dict, const Dict_char *str, Dict_ptr ptr,
88                             int sub_flag, void *client, 
89                             int (*f)(const char *, void *))
90 {
91     int mid, lo, hi;
92     int cmp;
93     void *p;
94     short *indxp;
95     char *info;
96
97     if (!ptr)
98         return 0;
99     dict_bf_readp (dict->dbf, ptr, &p);
100     mid = lo = 0;
101     hi = DICT_nodir(p)-1;
102     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));    
103     while (lo <= hi)
104     {
105         mid = (lo+hi)/2;
106         if (indxp[-mid] > 0)
107         {
108             /* string (Dict_char *) DICT_EOS terminated */
109             /* unsigned char        length of information */
110             /* char *               information */
111             info = (char*)p + indxp[-mid];
112
113             cmp = dict_strcmp((Dict_char*) info, str);
114             if (sub_flag)
115             {
116                 /* determine if prefix match */
117                 if (!dict_strncmp (str, (Dict_char*) info, dict_strlen(str)))
118                 {
119                     if (f)
120                         (*f)(info + (dict_strlen((Dict_char*) info)+1)
121                              *sizeof(Dict_char), client);
122
123                     hi = DICT_nodir(p)-1;
124                     while (mid < hi)
125                     {
126                         indxp[-mid] = indxp[-mid-1];
127                         mid++;
128                     }
129                     DICT_type(p) = 1;
130                     (DICT_nodir(p))--;
131                     dict_bf_touch (dict->dbf, ptr);
132                     --hi;
133                     mid = lo = 0;
134                     /* start again (may not be the most efficient way to go)*/
135                     continue; 
136                 }
137             }
138             else
139             {
140                 /* normal delete: delete if equal */
141                 if (!cmp)
142                 {
143                     hi = DICT_nodir(p)-1;
144                     while (mid < hi)
145                     {
146                         indxp[-mid] = indxp[-mid-1];
147                         mid++;
148                     }
149                     DICT_type(p) = 1;
150                     (DICT_nodir(p))--;
151                     dict_bf_touch (dict->dbf, ptr);
152                     return 1;
153                 }
154             }
155         }
156         else
157         {
158             Dict_char dc;
159             Dict_ptr subptr;
160
161             /* Dict_ptr             subptr */
162             /* Dict_char            sub char */
163             /* unsigned char        length of information */
164             /* char *               information */
165             info = (char*)p - indxp[-mid];
166             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
167             cmp = dc- *str;
168             if (!cmp)
169             {
170                 memcpy (&subptr, info, sizeof(Dict_ptr));
171                 if (*++str == DICT_EOS)
172                 {
173                     if (sub_flag && subptr)
174                     {
175                         Dict null_ptr = 0;
176                         memcpy (info, &null_ptr, sizeof(Dict_ptr));
177                     }
178                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
179                     {
180                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = 0;
181                         DICT_type(p) = 1;
182                         dict_bf_touch (dict->dbf, ptr);
183
184                         if (f)
185                             (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char),
186                                  client);
187                         if (sub_flag && subptr)
188                             dict_del_subtree (dict, subptr, client, f);
189                         return 1;
190                     }
191                     if (sub_flag && subptr)
192                     {
193                         DICT_type(p) = 1;
194                         dict_bf_touch (dict->dbf, ptr);
195                         dict_del_subtree (dict, subptr, client, f);
196                     }
197                     return 0;
198                 }
199                 else
200                 {
201                     if (subptr == 0)
202                         return 0;
203                     ptr = subptr;
204                     dict_bf_readp (dict->dbf, ptr, &p);
205                     mid = lo = 0;
206                     hi = DICT_nodir(p)-1;
207                     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
208                     continue;
209                 }
210             }
211         }
212         if (cmp < 0)
213             lo = mid+1;
214         else
215             hi = mid-1;
216     }
217     return 0;
218 }
219
220 int dict_delete (Dict dict, const char *p)
221 {
222     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 0,
223                             0, 0);
224 }
225
226 int dict_delete_subtree (Dict dict, const char *p, void *client,
227                          int (*f)(const char *info, void *client))
228 {
229     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 1,
230                             client, f);
231 }
232 /*
233  * Local variables:
234  * c-basic-offset: 4
235  * indent-tabs-mode: nil
236  * End:
237  * vim: shiftwidth=4 tabstop=8 expandtab
238  */
239