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