dict/delete.c

   1 /*
   2  * Copyright (C) 1994-2000, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: delete.c,v $
   7  * Revision 1.7  2000-12-05 09:59:10  adam
   8  * Work on dict_delete_subtree.
   9  *
  10  * Revision 1.6  1999/05/15 14:36:37  adam
  11  * Updated dictionary. Implemented "compression" of dictionary.
  12  *
  13  * Revision 1.5  1999/02/02 14:50:17  adam
  14  * Updated WIN32 code specific sections. Changed header.
  15  *
  16  * Revision 1.4  1996/02/02 13:43:50  adam
  17  * The public functions simply use char instead of Dict_char to represent
  18  * search strings. Dict_char is used internally only.
  19  *
  20  * Revision 1.3  1995/12/07  11:48:55  adam
  21  * Insert operation obeys DICT_type = 1 (slack in page).
  22  * Function dict_open exists if page size or magic aren't right.
  23  *
  24  * Revision 1.2  1995/12/06  17:48:30  adam
  25  * Bug fix: delete didn't work.
  26  *
  27  * Revision 1.1  1995/12/06  14:52:21  adam
  28  * New function: dict_delete.
  29  *
  30  */
  31
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <stdio.h>
  35 #include <assert.h>
  36
  37 #include <dict.h>
  38
  39 static void dict_del_subtree (Dict dict, Dict_ptr ptr,
  40                               void *client,
  41                               int (*f)(const char *, void *))
  42 {
  43     int more = 1;
  44     void *p = 0;
  45
  46     if (!ptr)
  47         return;
  48
  49     while (more)
  50     {
  51         short *indxp;
  52         int i, hi;
  53
  54         dict_bf_readp (dict->dbf, ptr, &p);
  55         hi = DICT_nodir(p)-1;
  56         indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  57         more = 0;
  58         for (i = 0; i <= hi; i++)
  59         {
  60             if (indxp[-i] > 0)
  61             {
  62                 /* string (Dict_char *) DICT_EOS terminated */
  63                 /* unsigned char        length of information */
  64                 /* char *               information */
  65                 char *info = (char*)p + indxp[-i];
  66                 if (f)
  67                     (*f)(info + (dict_strlen((Dict_char*) info)+1)
  68                          *sizeof(Dict_char), client);
  69             }
  70             else
  71             {
  72
  73                 Dict_ptr subptr;
  74
  75                 /* Dict_ptr             subptr */
  76                 /* Dict_char            sub char */
  77                 /* unsigned char        length of information */
  78                 /* char *               information */
  79                 char *info = (char*)p - indxp[-i];
  80                 memcpy (&subptr, info, sizeof(Dict_ptr));
  81
  82                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  83                 {
  84                     if (f)
  85                         (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char), client);
  86                 }
  87                 if (subptr)
  88                 {
  89                     dict_del_subtree (dict, subptr, client, f);
  90                     more = 1;
  91                     break;
  92                 }
  93             }
  94         }
  95     }
  96     DICT_backptr(p) = dict->head.freelist;
  97     dict->head.freelist = ptr;
  98     dict_bf_touch (dict->dbf, ptr);
  99 }
 100
 101 static int dict_del_string (Dict dict, const Dict_char *str, Dict_ptr ptr,
 102                             int sub_flag, void *client,
 103                             int (*f)(const char *, void *))
 104 {
 105     int mid, lo, hi;
 106     int cmp;
 107     void *p;
 108     short *indxp;
 109     char *info;
 110
 111     if (!ptr)
 112         return 0;
 113     dict_bf_readp (dict->dbf, ptr, &p);
 114     mid = lo = 0;
 115     hi = DICT_nodir(p)-1;
 116     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 117     while (lo <= hi)
 118     {
 119         mid = (lo+hi)/2;
 120         if (indxp[-mid] > 0)
 121         {
 122             /* string (Dict_char *) DICT_EOS terminated */
 123             /* unsigned char        length of information */
 124             /* char *               information */
 125             info = (char*)p + indxp[-mid];
 126
 127             cmp = dict_strcmp((Dict_char*) info, str);
 128             if (sub_flag)
 129             {
 130                 /* determine if prefix match */
 131                 if (!dict_strncmp (str, (Dict_char*) info, dict_strlen(str)))
 132                 {
 133                     if (f)
 134                         (*f)(info + (dict_strlen((Dict_char*) info)+1)
 135                              *sizeof(Dict_char), client);
 136
 137                     hi = DICT_nodir(p)-1;
 138                     while (mid < hi)
 139                     {
 140                         indxp[-mid] = indxp[-mid-1];
 141                         mid++;
 142                     }
 143                     DICT_type(p) = 1;
 144                     (DICT_nodir(p))--;
 145                     dict_bf_touch (dict->dbf, ptr);
 146                     --hi;
 147                     mid = lo = 0;
 148                     /* start again (may not be the most efficient way to go)*/
 149                     continue;
 150                 }
 151             }
 152             else
 153             {
 154                 /* normal delete: delete if equal */
 155                 if (!cmp)
 156                 {
 157                     hi = DICT_nodir(p)-1;
 158                     while (mid < hi)
 159                     {
 160                         indxp[-mid] = indxp[-mid-1];
 161                         mid++;
 162                     }
 163                     DICT_type(p) = 1;
 164                     (DICT_nodir(p))--;
 165                     dict_bf_touch (dict->dbf, ptr);
 166                     return 1;
 167                 }
 168             }
 169         }
 170         else
 171         {
 172             Dict_char dc;
 173             Dict_ptr subptr;
 174
 175             /* Dict_ptr             subptr */
 176             /* Dict_char            sub char */
 177             /* unsigned char        length of information */
 178             /* char *               information */
 179             info = (char*)p - indxp[-mid];
 180             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 181             cmp = dc- *str;
 182             if (!cmp)
 183             {
 184                 memcpy (&subptr, info, sizeof(Dict_ptr));
 185                 if (*++str == DICT_EOS)
 186                 {
 187                     if (sub_flag && subptr)
 188                     {
 189                         Dict null_ptr = 0;
 190                         memcpy (info, &null_ptr, sizeof(Dict_ptr));
 191                     }
 192                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 193                     {
 194                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = 0;
 195                         DICT_type(p) = 1;
 196                         dict_bf_touch (dict->dbf, ptr);
 197
 198                         if (f)
 199                             (*f)(info+sizeof(Dict_ptr)+sizeof(Dict_char),
 200                                  client);
 201                         if (sub_flag && subptr)
 202                             dict_del_subtree (dict, subptr, client, f);
 203                         return 1;
 204                     }
 205                     if (sub_flag && subptr)
 206                     {
 207                         DICT_type(p) = 1;
 208                         dict_bf_touch (dict->dbf, ptr);
 209                         dict_del_subtree (dict, subptr, client, f);
 210                     }
 211                     return 0;
 212                 }
 213                 else
 214                 {
 215                     if (subptr == 0)
 216                         return 0;
 217                     ptr = subptr;
 218                     dict_bf_readp (dict->dbf, ptr, &p);
 219                     mid = lo = 0;
 220                     hi = DICT_nodir(p)-1;
 221                     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 222                     continue;
 223                 }
 224             }
 225         }
 226         if (cmp < 0)
 227             lo = mid+1;
 228         else
 229             hi = mid-1;
 230     }
 231     return 0;
 232 }
 233
 234 int dict_delete (Dict dict, const char *p)
 235 {
 236     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 0,
 237                             0, 0);
 238 }
 239
 240 int dict_delete_subtree (Dict dict, const char *p, void *client,
 241                          int (*f)(const char *info, void *client))
 242 {
 243     return dict_del_string (dict, (const Dict_char*) p, dict->head.root, 1,
 244                             client, f);
 245 }