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