dict/delete.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 #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     int r = 0;
  94     Dict_ptr subptr = 0;
  95
  96     if (!ptr)
  97         return 0;
  98     dict_bf_readp(dict->dbf, ptr, &p);
  99     mid = lo = 0;
 100     hi = DICT_nodir(p)-1;
 101     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 102     while (lo <= hi)
 103     {
 104         mid = (lo+hi)/2;
 105         if (indxp[-mid] > 0)
 106         {
 107             /* string (Dict_char *) DICT_EOS terminated */
 108             /* unsigned char        length of information */
 109             /* char *               information */
 110             info = (char*)p + indxp[-mid];
 111
 112             cmp = dict_strcmp((Dict_char*) info, str);
 113             if (sub_flag)
 114             {
 115                 /* determine if prefix match */
 116                 if (!dict_strncmp(str, (Dict_char*) info, dict_strlen(str)))
 117                 {
 118                     if (f)
 119                         (*f)(info + (dict_strlen((Dict_char*) info)+1)
 120                              *sizeof(Dict_char), client);
 121
 122                     hi = DICT_nodir(p)-1;
 123                     while (mid < hi)
 124                     {
 125                         indxp[-mid] = indxp[-mid-1];
 126                         mid++;
 127                     }
 128                     DICT_type(p) = 1;
 129                     (DICT_nodir(p))--;
 130                     dict_bf_touch(dict->dbf, ptr);
 131                     --hi;
 132                     mid = lo = 0;
 133                     r = 1; /* signal deleted */
 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                     r = 1;
 153                     break;
 154                 }
 155             }
 156         }
 157         else
 158         {
 159             Dict_char dc;
 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 (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 174                     {
 175                         /* entry does exist. Wipe it out */
 176                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = 0;
 177                         DICT_type(p) = 1;
 178                         dict_bf_touch(dict->dbf, ptr);
 179
 180                         if (f)
 181                             (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char),
 182                                  client);
 183                         r = 1;
 184                     }
 185                     if (sub_flag)
 186                     {
 187                         /* must delete all suffixes (subtrees) as well */
 188                         hi = DICT_nodir(p)-1;
 189                         while (mid < hi)
 190                         {
 191                             indxp[-mid] = indxp[-mid-1];
 192                             mid++;
 193                         }
 194                         (DICT_nodir(p))--;
 195                         DICT_type(p) = 1;
 196                         dict_bf_touch(dict->dbf, ptr);
 197                     }
 198                 }
 199                 else
 200                 {
 201                     /* subptr may be 0 */
 202                     r = dict_del_string(dict, str, subptr, sub_flag, client, f);
 203
 204                     /* recover */
 205                     dict_bf_readp(dict->dbf, ptr, &p);
 206                     indxp = (short*)
 207                         ((char*) p+DICT_bsize(p)-sizeof(short));
 208                     info = (char*)p - indxp[-mid];
 209
 210                     subptr = 0; /* avoid dict_del_subtree (end of function)*/
 211                     if (r == 2)
 212                     {   /* subptr page became empty and is removed */
 213
 214                         /* see if this entry is a real one or if it just
 215                            serves as pointer to subptr */
 216                         if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 217                         {
 218                             /* this entry do exist, set subptr to 0 */
 219                             memcpy(info, &subptr, sizeof(subptr));
 220                         }
 221                         else
 222                         {
 223                             /* this entry ONLY points to subptr. remove it */
 224                             hi = DICT_nodir(p)-1;
 225                             while (mid < hi)
 226                             {
 227                                 indxp[-mid] = indxp[-mid-1];
 228                                 mid++;
 229                             }
 230                             (DICT_nodir(p))--;
 231                         }
 232                         dict_bf_touch(dict->dbf, ptr);
 233                         r = 1;
 234                     }
 235                 }
 236                 break;
 237             }
 238         }
 239         if (cmp < 0)
 240             lo = mid+1;
 241         else
 242             hi = mid-1;
 243     }
 244     if (DICT_nodir(p) == 0 && ptr != dict->head.root)
 245     {
 246         DICT_backptr(p) = dict->head.freelist;
 247         dict->head.freelist = ptr;
 248         dict_bf_touch(dict->dbf, ptr);
 249         r = 2;
 250     }
 251     if (subptr && sub_flag)
 252         dict_del_subtree(dict, subptr, client, f);
 253
 254     return r;
 255 }
 256
 257 int dict_delete(Dict dict, const char *p)
 258 {
 259     return dict_del_string(dict, (const Dict_char*) p, dict->head.root, 0,
 260                            0, 0);
 261 }
 262
 263 int dict_delete_subtree(Dict dict, const char *p, void *client,
 264                         int (*f)(const char *info, void *client))
 265 {
 266     return dict_del_string(dict, (const Dict_char*) p, dict->head.root, 1,
 267                            client, f);
 268 }
 269 /*
 270  * Local variables:
 271  * c-basic-offset: 4
 272  * c-file-style: "Stroustrup"
 273  * indent-tabs-mode: nil
 274  * End:
 275  * vim: shiftwidth=4 tabstop=8 expandtab
 276  */
 277