dict/insert.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: insert.c,v $
   7  * Revision 1.1  1994-08-16 16:26:48  adam
   8  * Added dict.
   9  *
  10  */
  11
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <stdio.h>
  15 #include <assert.h>
  16
  17 #include <dict.h>
  18
  19 static Dict_ptr new_page (Dict dict, Dict_ptr back_ptr, void **pp)
  20 {
  21     void *p;
  22     Dict_ptr ptr = dict->head.free_list;
  23     if (dict->head.free_list == dict->head.last)
  24     {
  25         dict->head.free_list++;
  26         dict->head.last = dict->head.free_list;
  27         bf_newp (dict->bf, ptr, &p);
  28     }
  29     else
  30     {
  31         bf_readp (dict->bf, dict->head.free_list, &p);
  32         dict->head.free_list = DICT_nextptr(p);
  33         if (dict->head.free_list == 0)
  34             dict->head.free_list = dict->head.last;
  35     }
  36     assert (p);
  37     DICT_type(p) = 1;
  38     DICT_backptr(p) = back_ptr;
  39     DICT_nextptr(p) = 0;
  40     DICT_nodir(p) = 0;
  41     DICT_size(p) = 0;
  42     *pp = p;
  43     return ptr;
  44 }
  45
  46 static int dict_ins (Dict dict, const Dict_char *str, Dict_ptr back_ptr,
  47                      void *p, void *userinfo)
  48 {
  49     Dict_ptr ptr = back_ptr, subptr;
  50     short *indxp, *indxp1, *indxp2;
  51     short newsize;
  52     if (ptr == 0)
  53         ptr = new_page (dict, back_ptr, &p);
  54     assert (p);
  55     assert (ptr);
  56
  57     indxp = (short*) ((char*) p+DICT_PAGESIZE);
  58     while (*str != DICT_EOS)
  59     {
  60         char *info;
  61         if (*--indxp > 0) /* tail string here! */
  62         {
  63             int cmp;
  64             info = DICT_info(p) + *indxp;
  65             cmp = dict_strcmp ((Dict_char*)
  66                               (info+sizeof(Dict_info)+sizeof(Dict_ptr)),
  67                                str);
  68             if (!cmp)
  69             {
  70                 if (memcmp (info+sizeof(Dict_ptr), userinfo, sizeof(userinfo)))
  71                 {
  72                     memcpy (info+sizeof(Dict_ptr), userinfo, sizeof(userinfo));
  73                     bf_touch (dict->bf, ptr);
  74                 }
  75                 return 0;
  76             }
  77             else if(cmp < 0)
  78                 break;
  79
  80         }
  81         else if(*indxp < 0)  /* tail of string in sub page */
  82         {
  83             int cmp;
  84             info = DICT_info(p) - *indxp;
  85             cmp = memcmp (info+sizeof(Dict_info)+sizeof(Dict_ptr), str,
  86                          sizeof(Dict_char));
  87             if (!cmp)
  88             {
  89                 Dict_ptr subptr;
  90                 void *pp;
  91                 memcpy (&subptr, info, sizeof(subptr));
  92                 if (subptr == 0)
  93                 {
  94                     subptr = new_page (dict, ptr, &pp);
  95                     memcpy (info, &subptr, sizeof(subptr));
  96                     bf_touch (dict->bf, ptr);
  97                 }
  98                 return dict_ins (dict, str+1, ptr, pp, userinfo);
  99             }
 100             else if(cmp < 0)
 101                 break;
 102         }
 103         else
 104             break;
 105     }
 106     newsize = DICT_size(p);
 107     subptr = 0;
 108     memcpy (DICT_info(p) + newsize, &subptr, sizeof(subptr));
 109     memcpy (DICT_info(p) + newsize + sizeof(Dict_ptr), userinfo,
 110             sizeof(Dict_info));
 111     memcpy (DICT_info(p) + newsize + sizeof(Dict_ptr)+sizeof(Dict_info),
 112             str, dict_strlen (str));
 113     newsize = DICT_size(p) +
 114         sizeof(Dict_info) + sizeof(Dict_ptr) + dict_strlen (str);
 115     DICT_size (p) = newsize;
 116
 117     DICT_nodir(p) = DICT_nodir(p)+1;
 118     indxp2 = (short*)((char*) p + DICT_PAGESIZE - DICT_nodir(p)*sizeof(short));
 119     for (indxp1 = indxp2; indxp1 != indxp; indxp1++)
 120         indxp[0] = indxp[1];
 121     *indxp = -newsize;
 122     return 0;
 123 }
 124
 125 int dict_insert (Dict dict, const Dict_char *str, void *userinfo)
 126 {
 127     dict_ins (dict, str, 0, NULL, userinfo);
 128     return 0;
 129 }
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142