IDZEBRA  2.1.2
delete.c
Go to the documentation of this file.
1 /* This file is part of the Zebra server.
2  Copyright (C) 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 #if HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23 #include <stdlib.h>
24 #include <string.h>
25 #include <stdio.h>
26 #include <assert.h>
27 
28 #include "dict-p.h"
29 
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  int r = 0;
97  Dict_ptr subptr = 0;
98 
99  if (!ptr)
100  return 0;
101  dict_bf_readp(dict->dbf, ptr, &p);
102  mid = lo = 0;
103  hi = DICT_nodir(p)-1;
104  indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
105  while (lo <= hi)
106  {
107  mid = (lo+hi)/2;
108  if (indxp[-mid] > 0)
109  {
110  /* string (Dict_char *) DICT_EOS terminated */
111  /* unsigned char length of information */
112  /* char * information */
113  info = (char*)p + indxp[-mid];
114 
115  cmp = dict_strcmp((Dict_char*) info, str);
116  if (sub_flag)
117  {
118  /* determine if prefix match */
119  if (!dict_strncmp(str, (Dict_char*) info, dict_strlen(str)))
120  {
121  if (f)
122  (*f)(info + (dict_strlen((Dict_char*) info)+1)
123  *sizeof(Dict_char), client);
124 
125  hi = DICT_nodir(p)-1;
126  while (mid < hi)
127  {
128  indxp[-mid] = indxp[-mid-1];
129  mid++;
130  }
131  DICT_type(p) = 1;
132  (DICT_nodir(p))--;
133  dict_bf_touch(dict->dbf, ptr);
134  --hi;
135  mid = lo = 0;
136  r = 1; /* signal deleted */
137  /* start again (may not be the most efficient way to go)*/
138  continue;
139  }
140  }
141  else
142  {
143  /* normal delete: delete if equal */
144  if (!cmp)
145  {
146  hi = DICT_nodir(p)-1;
147  while (mid < hi)
148  {
149  indxp[-mid] = indxp[-mid-1];
150  mid++;
151  }
152  DICT_type(p) = 1;
153  (DICT_nodir(p))--;
154  dict_bf_touch(dict->dbf, ptr);
155  r = 1;
156  break;
157  }
158  }
159  }
160  else
161  {
162  Dict_char dc;
163 
164  /* Dict_ptr subptr */
165  /* Dict_char sub char */
166  /* unsigned char length of information */
167  /* char * information */
168  info = (char*)p - indxp[-mid];
169  memcpy(&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
170  cmp = dc- *str;
171  if (!cmp)
172  {
173  memcpy(&subptr, info, sizeof(Dict_ptr));
174  if (*++str == DICT_EOS)
175  {
176  if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
177  {
178  /* entry does exist. Wipe it out */
179  info[sizeof(Dict_ptr)+sizeof(Dict_char)] = 0;
180  DICT_type(p) = 1;
181  dict_bf_touch(dict->dbf, ptr);
182 
183  if (f)
184  (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char),
185  client);
186  r = 1;
187  }
188  if (sub_flag)
189  {
190  /* must delete all suffixes (subtrees) as well */
191  hi = DICT_nodir(p)-1;
192  while (mid < hi)
193  {
194  indxp[-mid] = indxp[-mid-1];
195  mid++;
196  }
197  (DICT_nodir(p))--;
198  DICT_type(p) = 1;
199  dict_bf_touch(dict->dbf, ptr);
200  }
201  }
202  else
203  {
204  /* subptr may be 0 */
205  r = dict_del_string(dict, str, subptr, sub_flag, client, f);
206 
207  /* recover */
208  dict_bf_readp(dict->dbf, ptr, &p);
209  indxp = (short*)
210  ((char*) p+DICT_bsize(p)-sizeof(short));
211  info = (char*)p - indxp[-mid];
212 
213  subptr = 0; /* avoid dict_del_subtree (end of function)*/
214  if (r == 2)
215  { /* subptr page became empty and is removed */
216 
217  /* see if this entry is a real one or if it just
218  serves as pointer to subptr */
219  if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
220  {
221  /* this entry do exist, set subptr to 0 */
222  memcpy(info, &subptr, sizeof(subptr));
223  }
224  else
225  {
226  /* this entry ONLY points to subptr. remove it */
227  hi = DICT_nodir(p)-1;
228  while (mid < hi)
229  {
230  indxp[-mid] = indxp[-mid-1];
231  mid++;
232  }
233  (DICT_nodir(p))--;
234  }
235  dict_bf_touch(dict->dbf, ptr);
236  r = 1;
237  }
238  }
239  break;
240  }
241  }
242  if (cmp < 0)
243  lo = mid+1;
244  else
245  hi = mid-1;
246  }
247  if (DICT_nodir(p) == 0 && ptr != dict->head.root)
248  {
249  DICT_backptr(p) = dict->head.freelist;
250  dict->head.freelist = ptr;
251  dict_bf_touch(dict->dbf, ptr);
252  r = 2;
253  }
254  if (subptr && sub_flag)
255  dict_del_subtree(dict, subptr, client, f);
256 
257  return r;
258 }
259 
260 int dict_delete(Dict dict, const char *p)
261 {
262  return dict_del_string(dict, (const Dict_char*) p, dict->head.root, 0,
263  0, 0);
264 }
265 
266 int dict_delete_subtree(Dict dict, const char *p, void *client,
267  int (*f)(const char *info, void *client))
268 {
269  return dict_del_string(dict, (const Dict_char*) p, dict->head.root, 1,
270  client, f);
271 }
272 /*
273  * Local variables:
274  * c-basic-offset: 4
275  * c-file-style: "Stroustrup"
276  * indent-tabs-mode: nil
277  * End:
278  * vim: shiftwidth=4 tabstop=8 expandtab
279  */
280 
#define DICT_backptr(x)
Definition: dict-p.h:104
int dict_strcmp(const Dict_char *s1, const Dict_char *s2)
Definition: open.c:108
struct Dict_head head
Definition: dict-p.h:83
int dict_strlen(const Dict_char *s)
Definition: open.c:118
#define DICT_bsize(x)
Definition: dict-p.h:105
int dict_delete_subtree(Dict dict, const char *p, void *client, int(*f)(const char *info, void *client))
delete items with a given prefix from dictionary
Definition: delete.c:266
#define DICT_EOS
Definition: dict-p.h:102
static int dict_del_string(Dict dict, const Dict_char *str, Dict_ptr ptr, int sub_flag, void *client, int(*f)(const char *, void *))
Definition: delete.c:87
static Dict dict
Definition: dicttest.c:34
unsigned Dict_ptr
Definition: dict-p.h:34
static void dict_del_subtree(Dict dict, Dict_ptr ptr, void *client, int(*f)(const char *, void *))
Definition: delete.c:30
Dict_BFile dbf
Definition: dict-p.h:74
#define DICT_type(x)
Definition: dict-p.h:103
int dict_bf_readp(Dict_BFile bf, int no, void **bufp)
Definition: drdwr.c:188
#define DICT_nodir(x)
Definition: dict-p.h:106
int dict_bf_touch(Dict_BFile bf, int no)
Definition: drdwr.c:244
int dict_delete(Dict dict, const char *p)
deletes item from dictionary
Definition: delete.c:260
int dict_strncmp(const Dict_char *s1, const Dict_char *s2, size_t n)
Definition: open.c:113
Dict_ptr root
Definition: dict-p.h:40
Dict_ptr freelist
Definition: dict-p.h:40
unsigned char Dict_char
Definition: dict-p.h:33