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