dict/delete.c

   1 /* $Id: delete.c,v 1.8 2002-08-02 19:26:55 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   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
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <stdio.h>
  28 #include <assert.h>
  29
  30 #include <dict.h>
  31
  32 static void dict_del_subtree (Dict dict, Dict_ptr ptr,
  33                               void *client,
  34                               int (*f)(const char *, void *))
  35 {
  36     int more = 1;
  37     void *p = 0;
  38
  39     if (!ptr)
  40         return;
  41
  42     while (more)
  43     {
  44         short *indxp;
  45         int i, hi;
  46
  47         dict_bf_readp (dict->dbf, ptr, &p);
  48         hi = DICT_nodir(p)-1;
  49         indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  50         more = 0;
  51         for (i = 0; i <= hi; i++)
  52         {
  53             if (indxp[-i] > 0)
  54             {
  55                 /* string (Dict_char *) DICT_EOS terminated */
  56                 /* unsigned char        length of information */
  57                 /* char *               information */
  58                 char *info = (char*)p + indxp[-i];
  59                 if (f)
  60                     (*f)(info + (dict_strlen((Dict_char*) info)+1)
  61                          *sizeof(Dict_char), client);
  62             }
  63             else
  64             {
  65
  66                 Dict_ptr subptr;
  67
  68                 /* Dict_ptr             subptr */
  69                 /* Dict_char            sub char */
  70                 /* unsigned char        length of information */
  71                 /* char *               information */
  72                 char *info = (char*)p - indxp[-i];
  73                 memcpy (&subptr, info, sizeof(Dict_ptr));
  74
  75                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  76                 {
  77                     if (f)
  78                         (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char), client);
  79                 }
  80                 if (subptr)
  81                 {
  82                     dict_del_subtree (dict, subptr, client, f);
  83                     more = 1;
  84                     break;
  85                 }
  86             }
  87         }
  88     }
  89     DICT_backptr(p) = dict->head.freelist;
  90     dict->head.freelist = ptr;
  91     dict_bf_touch (dict->dbf, ptr);
  92 }
  93
  94 static int dict_del_string (Dict dict, const Dict_char *str, Dict_ptr ptr,
  95                             int sub_flag, void *client,
  96                             int (*f)(const char *, void *))
  97 {
  98     int mid, lo, hi;
  99     int cmp;
 100     void *p;
 101     short *indxp;
 102     char *info;
 103
 104     if (!ptr)
 105         return 0;
 106     dict_bf_readp (dict->dbf, ptr, &p);
 107     mid = lo = 0;
 108     hi = DICT_nodir(p)-1;
 109     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 110     while (lo <= hi)
 111     {
 112         mid = (lo+hi)/2;
 113         if (indxp[-mid] > 0)
 114         {
 115             /* string (Dict_char *) DICT_EOS terminated */
 116             /* unsigned char        length of information */
 117             /* char *               information */
 118             info = (char*)p + indxp[-mid];
 119
 120             cmp = dict_strcmp((Dict_char*) info, str);
 121             if (sub_flag)
 122             {
 123                 /* determine if prefix match */
 124                 if (!dict_strncmp (str, (Dict_char*) info, dict_strlen(str)))
 125                 {
 126                     if (f)
 127                         (*f)(info + (dict_strlen((Dict_char*) info)+1)
 128                              *sizeof(Dict_char), client);
 129
 130                     hi = DICT_nodir(p)-1;
 131                     while (mid < hi)
 132                     {
 133                         indxp[-mid] = indxp[-mid-1];
 134                         mid++;
 135                     }
 136                     DICT_type(p) = 1;
 137                     (DICT_nodir(p))--;
 138                     dict_bf_touch (dict->dbf, ptr);
 139                     --hi;
 140                     mid = lo = 0;
 141                     /* start again (may not be the most efficient way to go)*/
 142                     continue;
 143                 }
 144             }
 145             else
 146             {
 147                 /* normal delete: delete if equal */
 148                 if (!cmp)
 149                 {
 150                     hi = DICT_nodir(p)-1;
 151                     while (mid < hi)
 152                     {
 153                         indxp[-mid] = indxp[-mid-1];
 154                         mid++;
 155                     }
 156                     DICT_type(p) = 1;
 157                     (DICT_nodir(p))--;
 158                     dict_bf_touch (dict->dbf, ptr);
 159                     return 1;
 160                 }
 161             }
 162         }
 163         else
 164         {
 165             Dict_char dc;
 166             Dict_ptr subptr;
 167
 168             /* Dict_ptr             subptr */
 169             /* Dict_char            sub char */
 170             /* unsigned char        length of information */
 171             /* char *               information */
 172             info = (char*)p - indxp[-mid];
 173             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 174             cmp = dc- *str;
 175             if (!cmp)
 176             {
 177                 memcpy (&subptr, info, sizeof(Dict_ptr));
 178                 if (*++str == DICT_EOS)
 179                 {
 180                     if (sub_flag && subptr)
 181                     {
 182                         Dict null_ptr = 0;
 183                         memcpy (info, &null_ptr, sizeof(Dict_ptr));
 184                     }
 185                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 186                     {
 187                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = 0;
 188                         DICT_type(p) = 1;
 189                         dict_bf_touch (dict->dbf, ptr);
 190
 191                         if (f)
 192                             (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char),
 193                                  client);
 194                         if (sub_flag && subptr)
 195                             dict_del_subtree (dict, subptr, client, f);
 196                         return 1;
 197                     }
 198                     if (sub_flag && subptr)
 199                     {
 200                         DICT_type(p) = 1;
 201                         dict_bf_touch (dict->dbf, ptr);
 202                         dict_del_subtree (dict, subptr, client, f);
 203                     }
 204                     return 0;
 205                 }
 206                 else
 207                 {
 208                     if (subptr == 0)
 209                         return 0;
 210                     ptr = subptr;
 211                     dict_bf_readp (dict->dbf, ptr, &p);
 212                     mid = lo = 0;
 213                     hi = DICT_nodir(p)-1;
 214                     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 215                     continue;
 216                 }
 217             }
 218         }
 219         if (cmp < 0)
 220             lo = mid+1;
 221         else
 222             hi = mid-1;
 223     }
 224     return 0;
 225 }
 226
 227 int dict_delete (Dict dict, const char *p)
 228 {
 229     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 0,
 230                             0, 0);
 231 }
 232
 233 int dict_delete_subtree (Dict dict, const char *p, void *client,
 234                          int (*f)(const char *info, void *client))
 235 {
 236     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 1,
 237                             client, f);
 238 }