dict/delete.c

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