dict/delete.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: delete.c,v $
   7  * Revision 1.4  1996-02-02 13:43:50  adam
   8  * The public functions simply use char instead of Dict_char to represent
   9  * search strings. Dict_char is used internally only.
  10  *
  11  * Revision 1.3  1995/12/07  11:48:55  adam
  12  * Insert operation obeys DICT_type = 1 (slack in page).
  13  * Function dict_open exists if page size or magic aren't right.
  14  *
  15  * Revision 1.2  1995/12/06  17:48:30  adam
  16  * Bug fix: delete didn't work.
  17  *
  18  * Revision 1.1  1995/12/06  14:52:21  adam
  19  * New function: dict_delete.
  20  *
  21  */
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <stdio.h>
  26 #include <assert.h>
  27
  28 #include <dict.h>
  29
  30 static int dict_del (Dict dict, const Dict_char *str)
  31 {
  32     Dict_ptr ptr = 1;
  33     int mid, lo, hi;
  34     int cmp;
  35     void *p;
  36     short *indxp;
  37     char *info;
  38
  39     dict_bf_readp (dict->dbf, ptr, &p);
  40     mid = lo = 0;
  41     hi = DICT_nodir(p)-1;
  42     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
  43     while (lo <= hi)
  44     {
  45         mid = (lo+hi)/2;
  46         if (indxp[-mid] > 0)
  47         {
  48             /* string (Dict_char *) DICT_EOS terminated */
  49             /* unsigned char        length of information */
  50             /* char *               information */
  51             info = (char*)p + indxp[-mid];
  52             cmp = dict_strcmp((Dict_char*) info, str);
  53             if (!cmp)
  54             {
  55                 hi = DICT_nodir(p)-1;
  56                 while (mid < hi)
  57                 {
  58                     indxp[-mid] = indxp[-mid-1];
  59                     mid++;
  60                 }
  61                 DICT_type(p) = 1;
  62                 (DICT_nodir(p))--;
  63                 dict_bf_touch (dict->dbf, ptr);
  64                 return 1;
  65             }
  66         }
  67         else
  68         {
  69             Dict_char dc;
  70             Dict_ptr subptr;
  71
  72             /* Dict_ptr             subptr */
  73             /* Dict_char            sub char */
  74             /* unsigned char        length of information */
  75             /* char *               information */
  76             info = (char*)p - indxp[-mid];
  77             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  78             cmp = dc- *str;
  79             if (!cmp)
  80             {
  81                 memcpy (&subptr, info, sizeof(Dict_ptr));
  82                 if (*++str == DICT_EOS)
  83                 {
  84                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  85                     {
  86                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = 0;
  87                         DICT_type(p) = 1;
  88                         dict_bf_touch (dict->dbf, ptr);
  89                         return 1;
  90                     }
  91                     return 0;
  92                 }
  93                 else
  94                 {
  95                     if (subptr == 0)
  96                         return 0;
  97                     ptr = subptr;
  98                     dict_bf_readp (dict->dbf, ptr, &p);
  99                     mid = lo = 0;
 100                     hi = DICT_nodir(p)-1;
 101                     indxp = (short*) ((char*) p+DICT_pagesize(dict)
 102                                       -sizeof(short));
 103                     continue;
 104                 }
 105             }
 106         }
 107         if (cmp < 0)
 108             lo = mid+1;
 109         else
 110             hi = mid-1;
 111     }
 112     return 0;
 113 }
 114
 115 int dict_delete (Dict dict, const char *p)
 116 {
 117     if (dict->head.last == 1)
 118         return 0;
 119     return dict_del (dict, (const Dict_char*) p);
 120 }