dict/delete.c

   1 /* $Id: delete.c,v 1.11 2005-01-15 19:38:21 adam Exp $
   2    Copyright (C) 1995-2005
   3    Index Data ApS
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  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
  97     if (!ptr)
  98         return 0;
  99     dict_bf_readp (dict->dbf, ptr, &p);
 100     mid = lo = 0;
 101     hi = DICT_nodir(p)-1;
 102     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 103     while (lo <= hi)
 104     {
 105         mid = (lo+hi)/2;
 106         if (indxp[-mid] > 0)
 107         {
 108             /* string (Dict_char *) DICT_EOS terminated */
 109             /* unsigned char        length of information */
 110             /* char *               information */
 111             info = (char*)p + indxp[-mid];
 112
 113             cmp = dict_strcmp((Dict_char*) info, str);
 114             if (sub_flag)
 115             {
 116                 /* determine if prefix match */
 117                 if (!dict_strncmp (str, (Dict_char*) info, dict_strlen(str)))
 118                 {
 119                     if (f)
 120                         (*f)(info + (dict_strlen((Dict_char*) info)+1)
 121                              *sizeof(Dict_char), client);
 122
 123                     hi = DICT_nodir(p)-1;
 124                     while (mid < hi)
 125                     {
 126                         indxp[-mid] = indxp[-mid-1];
 127                         mid++;
 128                     }
 129                     DICT_type(p) = 1;
 130                     (DICT_nodir(p))--;
 131                     dict_bf_touch (dict->dbf, ptr);
 132                     --hi;
 133                     mid = lo = 0;
 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                     return 1;
 153                 }
 154             }
 155         }
 156         else
 157         {
 158             Dict_char dc;
 159             Dict_ptr subptr;
 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 (sub_flag && subptr)
 174                     {
 175                         Dict null_ptr = 0;
 176                         memcpy (info, &null_ptr, sizeof(Dict_ptr));
 177                     }
 178                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 179                     {
 180                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = 0;
 181                         DICT_type(p) = 1;
 182                         dict_bf_touch (dict->dbf, ptr);
 183
 184                         if (f)
 185                             (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char),
 186                                  client);
 187                         if (sub_flag && subptr)
 188                             dict_del_subtree (dict, subptr, client, f);
 189                         return 1;
 190                     }
 191                     if (sub_flag && subptr)
 192                     {
 193                         DICT_type(p) = 1;
 194                         dict_bf_touch (dict->dbf, ptr);
 195                         dict_del_subtree (dict, subptr, client, f);
 196                     }
 197                     return 0;
 198                 }
 199                 else
 200                 {
 201                     if (subptr == 0)
 202                         return 0;
 203                     ptr = subptr;
 204                     dict_bf_readp (dict->dbf, ptr, &p);
 205                     mid = lo = 0;
 206                     hi = DICT_nodir(p)-1;
 207                     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 208                     continue;
 209                 }
 210             }
 211         }
 212         if (cmp < 0)
 213             lo = mid+1;
 214         else
 215             hi = mid-1;
 216     }
 217     return 0;
 218 }
 219
 220 int dict_delete (Dict dict, const char *p)
 221 {
 222     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 0,
 223                             0, 0);
 224 }
 225
 226 int dict_delete_subtree (Dict dict, const char *p, void *client,
 227                          int (*f)(const char *info, void *client))
 228 {
 229     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 1,
 230                             client, f);
 231 }