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