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.4  1994-09-01 17:44:09  adam
   8  * depend include change.
   9  * CVS ----------------------------------------------------------------------
  10  *
  11  * Revision 1.3  1994/08/18  12:40:56  adam
  12  * Some development of dictionary. Not finished at all!
  13  *
  14  * Revision 1.2  1994/08/17  13:32:19  adam
  15  * Use cache in dict - not in bfile.
  16  *
  17  * Revision 1.1  1994/08/16  16:26:48  adam
  18  * Added dict.
  19  *
  20  */
  21
  22 #include <string.h>
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <assert.h>
  26
  27 #include <dict.h>
  28
  29 static int dict_ins (Dict dict, const Dict_char *str,
  30                      Dict_ptr back_ptr, int userlen, void *userinfo);
  31
  32
  33 static Dict_ptr new_page (Dict dict, Dict_ptr back_ptr, void **pp)
  34 {
  35     void *p;
  36     Dict_ptr ptr = dict->head.free_list;
  37     if (dict->head.free_list == dict->head.last)
  38     {
  39         dict->head.free_list++;
  40         dict->head.last = dict->head.free_list;
  41         dict_bf_newp (dict->dbf, ptr, &p);
  42     }
  43     else
  44     {
  45         dict_bf_readp (dict->dbf, dict->head.free_list, &p);
  46         dict->head.free_list = DICT_nextptr(p);
  47         if (dict->head.free_list == 0)
  48             dict->head.free_list = dict->head.last;
  49     }
  50     assert (p);
  51     DICT_type(p) = 0;
  52     DICT_backptr(p) = back_ptr;
  53     DICT_nextptr(p) = 0;
  54     DICT_nodir(p) = 0;
  55     DICT_size(p) = DICT_infoffset;
  56     *pp = p;
  57     return ptr;
  58 }
  59
  60 static int split_page (Dict dict, Dict_ptr ptr, void *p)
  61 {
  62     void *subp;
  63     char *info_here;
  64     Dict_ptr subptr;
  65     int i, need;
  66     short *indxp, *best_indxp;
  67     Dict_char best_char;
  68     Dict_char prev_char;
  69     int best_no = -1, no_current;
  70
  71     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
  72     for (i = DICT_nodir (p); --i >= 0; --indxp)
  73     {
  74         if (*indxp > 0) /* tail string here! */
  75         {
  76             Dict_char dc;
  77
  78             memcpy (&dc, (char*) p + *indxp, sizeof(dc));
  79             if (best_no < 0)
  80             {   /* first entry met */
  81                 best_char = prev_char = dc;
  82                 no_current = best_no = 1;
  83             }
  84             else if (prev_char == dc)
  85             {   /* same char prefix. update */
  86                 if (++no_current > best_no)
  87                 {   /* best entry so far */
  88                     best_no = no_current;
  89                     best_char = dc;
  90                     best_indxp = indxp;
  91                 }
  92             }
  93             else
  94             {   /* new char prefix. restore */
  95                 prev_char = dc;
  96                 no_current = 1;
  97             }
  98         }
  99     }
 100     if (best_no < 0) /* we didn't find any tail string entry at all! */
 101         return -1;
 102
 103     subptr = new_page (dict, ptr, &subp);
 104     /* scan entries to see if there is a string with */
 105     /* length 1. info_here indicates if such entry exist */
 106     info_here = NULL;
 107     for (indxp=best_indxp, i=0; i<best_no; i++, indxp++)
 108     {
 109         char *info;
 110         int slen;
 111
 112         assert (*indxp > 0);
 113
 114         info = (char*) p + *indxp;                    /* entry start */
 115         slen = dict_strlen(info);
 116
 117         assert (slen > 0);
 118         if (slen == 1)
 119         {
 120             assert (!info_here);
 121             info_here = info+(slen+1)*sizeof(Dict_char);
 122         }
 123     }
 124     /* calculate the amount of bytes needed for this entry when */
 125     /* transformed to a sub entry */
 126     need = sizeof(Dict_char)+sizeof(Dict_ptr)+1;
 127     if (info_here)
 128         need += *info_here;
 129
 130     indxp = best_indxp;
 131     /* now loop on all entries with string length > 1 i.e. all */
 132     /* those entries which contribute to a sub page */
 133     best_indxp = NULL;
 134     for (i=0; i<best_no; i++, indxp++)
 135     {
 136         char *info, *info1;
 137         int slen;
 138
 139         assert (*indxp > 0);
 140
 141         info = (char*) p + *indxp;                    /* entry start */
 142         slen = dict_strlen(info);
 143
 144         if (slen > 1)
 145         {
 146             info1 = info+(1+slen)*sizeof(Dict_char);  /* info start */
 147
 148             if (need <= (1+slen)*sizeof(Dict_char) + 1 + *info1)
 149                 best_indxp = indxp;                   /* space for entry */
 150             dict_ins (dict, info+sizeof(Dict_char), subptr, *info1, info1+1);
 151         }
 152     }
 153     if (best_indxp)
 154     {   /* there was a hole big enough for a sub entry */
 155         char *info = (char*) p + *best_indxp;
 156         short *indxp1;
 157
 158         *--indxp = - *best_indxp;
 159         DICT_type(p) = 1;
 160         DICT_nodir (p) -= (best_no-1);
 161         indxp1 = (short*)((char*)p+DICT_PAGESIZE-DICT_nodir(p)*sizeof(short));
 162         while (indxp != indxp1)
 163         {
 164             --indxp;
 165             *indxp = indxp[1-best_no];
 166         }
 167         memcpy (info, &subptr, sizeof(Dict_ptr));     /* store subptr */
 168         info += sizeof(Dict_ptr);
 169         memcpy (info, &best_char, sizeof(Dict_char)); /* store sub char */
 170         info += sizeof(Dict_char);
 171         if (info_here)
 172             memcpy (info, info_here, *info_here+1);   /* with information */
 173         else
 174             *info = 0;                                /* without info */
 175     }
 176     else
 177     {
 178         short *indxp1, *indxp2;
 179         assert (0);
 180         DICT_type(p) = 1;
 181         DICT_nodir(p) -= best_no;
 182         indxp2 = indxp;
 183         indxp1 = (short*)((char*) p+DICT_PAGESIZE-DICT_nodir(p)*sizeof(short));
 184         do
 185         {
 186             --indxp2;
 187             indxp2[0] = indxp2[-best_no];
 188         } while (indxp2 != indxp1);
 189     }
 190     return 0;
 191 }
 192
 193 static void clean_page (Dict dict, void *p)
 194 {
 195     char *np = xmalloc (dict->head.page_size);
 196     int i, slen;
 197     short *indxp1, *indxp2;
 198     char *info1, *info2;
 199
 200     indxp1 = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 201     indxp2 = (short*) ((char*) np+DICT_PAGESIZE);
 202     info2 = (char*) np + DICT_infoffset;
 203     for (i = DICT_nodir (p); --i >= 0; --indxp1)
 204     {
 205         if (*indxp1 > 0) /* tail string here! */
 206         {
 207             /* string (Dict_char *) DICT_EOS terminated */
 208             /* unsigned char        length of information */
 209             /* char *               information */
 210
 211             *--indxp2 = info2 - np;
 212             info1 = (char*) p + *indxp1;
 213             slen = (dict_strlen(info1)+1)*sizeof(Dict_char);
 214             memcpy (info2, info1, slen);
 215             info2 += slen;
 216             info1 += slen;
 217             slen = *info1+1;
 218             memcpy (info2, info1, slen);
 219             info2 += slen;
 220             info1 += slen;
 221         }
 222         else
 223         {
 224             /* Dict_ptr             subptr */
 225             /* Dict_char            sub char */
 226             /* unsigned char        length of information */
 227             /* char *               information */
 228
 229             *--indxp2 = -(info2 - np);
 230             info1 = (char*) p - *indxp1;
 231             memcpy (info2, info1, sizeof(Dict_ptr)+sizeof(Dict_char));
 232             info2 += sizeof(Dict_ptr)+sizeof(Dict_char);
 233             info1 += sizeof(Dict_ptr)+sizeof(Dict_char);
 234             slen = *info1+1;
 235             memcpy (info2, info1, slen);
 236             info2 += slen;
 237             info1 += slen;
 238         }
 239     }
 240     memcpy ((char*) p + DICT_infoffset, (char*) np + DICT_infoffset,
 241             DICT_PAGESIZE-DICT_infoffset);
 242     DICT_size(p) = info2 - np;
 243     DICT_type(p) = 0;
 244     xfree (np);
 245 }
 246
 247 static int dict_ins (Dict dict, const Dict_char *str,
 248                      Dict_ptr back_ptr, int userlen, void *userinfo)
 249 {
 250     int i, slen, cmp = 1;
 251     Dict_ptr ptr = back_ptr;
 252     short *indxp;
 253     char *info;
 254     void *p;
 255
 256     if (ptr == 0)
 257         ptr = new_page (dict, back_ptr, &p);
 258     else
 259         dict_bf_readp (dict->dbf, ptr, &p);
 260
 261     assert (p);
 262     assert (ptr);
 263
 264     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 265     for (i = DICT_nodir (p); --i >= 0; --indxp)
 266     {
 267         if (*indxp > 0) /* tail string here! */
 268         {
 269             info = (char*) p + *indxp;
 270             /* string (Dict_char *) DICT_EOS terminated */
 271             /* unsigned char        length of information */
 272             /* char *               information */
 273             cmp = dict_strcmp ((Dict_char*) info, str);
 274             if (!cmp)
 275             {
 276                 info += (dict_strlen(info)+1)*sizeof(Dict_char);
 277                 /* consider change of userinfo length... */
 278                 if (*info == userlen)
 279                 {
 280                     if (memcmp (info+1, userinfo, userlen))
 281                     {
 282                         dict_bf_touch (dict->dbf, ptr);
 283                         memcpy (info+1, userinfo, userlen);
 284                     }
 285                 }
 286                 else if (*info > userlen)
 287                 {
 288                     DICT_type(p) = 1;
 289                     *info = userlen;
 290                     dict_bf_touch (dict->dbf, ptr);
 291                     memcpy (info+1, userinfo, userlen);
 292                 }
 293                 else
 294                 {
 295                     DICT_type(p) = 1;
 296                     break;
 297                 }
 298                 return 0;
 299             }
 300             else if(cmp > 0)
 301                 break;
 302         }
 303         else  /* tail of string in sub page */
 304         {
 305             Dict_char dc;
 306             assert (*indxp < 0);
 307             info = (char*) p - *indxp;
 308             /* Dict_ptr             subptr */
 309             /* Dict_char            sub char */
 310             /* unsigned char        length of information */
 311             /* char *               information */
 312             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 313             cmp = dc- *str;
 314             if (!cmp)
 315             {
 316                 Dict_ptr subptr;
 317                 void *pp;
 318                 if (*++str == DICT_EOS)
 319                 {   /* missing: consider change of userinfo length ... */
 320                     if (memcmp (info+sizeof(Dict_char)+sizeof(Dict_ptr)+1,
 321                                 userinfo, userlen))
 322                     {
 323                         memcpy (dict+sizeof(Dict_char)+sizeof(Dict_ptr)+1,
 324                                 userinfo, userlen);
 325                         dict_bf_touch (dict->dbf, ptr);
 326                     }
 327                     return 0;
 328                 }
 329                 else
 330                 {
 331                     memcpy (&subptr, info, sizeof(subptr));
 332                     if (subptr == 0)
 333                     {
 334                         subptr = new_page (dict, ptr, &pp);
 335                         memcpy (info, &subptr, sizeof(subptr));
 336                         dict_bf_touch (dict->dbf, ptr);
 337                     }
 338                     return dict_ins (dict, str, ptr, userlen, userinfo);
 339                 }
 340             }
 341             else if(cmp > 0)
 342                 break;
 343         }
 344     }
 345     slen = (dict_strlen(str)+1)*sizeof(Dict_char);
 346     if (DICT_size(p)+slen+userlen >=
 347         DICT_PAGESIZE - (1+DICT_nodir(p))*sizeof(short)) /* overflow? */
 348     {
 349         if (DICT_type(p) == 1)
 350         {
 351             clean_page (dict, p);
 352             dict_ins (dict, str, ptr, userlen, userinfo);
 353             return 0;
 354         }
 355         i = 0;
 356         do
 357         {
 358             if (i > 0)
 359                 assert (0);
 360             if (split_page (dict, ptr, p))
 361             {
 362                 log (LOG_FATAL, "Unable to split page %d\n", ptr);
 363                 abort ();
 364             }
 365             if (DICT_size(p)+slen+userlen <
 366                 DICT_PAGESIZE - (1+DICT_nodir(p))*sizeof(short))
 367                 break;
 368             i++;
 369             clean_page (dict, p);
 370         } while (DICT_size(p)+slen+userlen > DICT_PAGESIZE -
 371                  (1+DICT_nodir(p))*sizeof(short));
 372         dict_ins (dict, str, ptr, userlen, userinfo);
 373         return 0;
 374     }
 375     if (cmp)
 376     {
 377         short *indxp1;
 378         (DICT_nodir(p))++;
 379         indxp1 = (short*)((char*) p + DICT_PAGESIZE
 380                           - DICT_nodir(p)*sizeof(short));
 381         for (; indxp1 != indxp; indxp1++)
 382             indxp1[0] = indxp1[1];
 383     }
 384     info = (char*)p + DICT_size(p);
 385     memcpy (info, str, slen);
 386     info += slen;
 387     *info++ = userlen;
 388     memcpy (info, userinfo, userlen);
 389     info += userlen;
 390
 391     *indxp = DICT_size(p);
 392 #if 0
 393     printf ("indxp[%d]\n", (char*) indxp - (char*) p);
 394 #endif
 395
 396     DICT_size(p) = info- (char*) p;
 397     dict_bf_touch (dict->dbf, ptr);
 398     return 0;
 399 }
 400
 401 int dict_insert (Dict dict, const Dict_char *str, int userlen, void *userinfo)
 402 {
 403     assert (dict->head.last > 0);
 404     if (dict->head.last == 1)
 405         dict_ins (dict, str, 0, userlen, userinfo);
 406     else
 407         dict_ins (dict, str, 1, userlen, userinfo);
 408     return 0;
 409 }