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