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 #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
  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     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