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