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.8  1994-09-16 12:35:01  adam
   8  * New version of split_page which use clean_page for splitting.
   9  *
  10  * Revision 1.7  1994/09/12  08:06:42  adam
  11  * Futher development of insert.c
  12  *
  13  * Revision 1.6  1994/09/06  13:05:15  adam
  14  * Further development of insertion. Some special cases are
  15  * not properly handled yet! assert(0) are put here. The
  16  * binary search in each page definitely reduce usr CPU.
  17  *
  18  * Revision 1.5  1994/09/01  17:49:39  adam
  19  * Removed stupid line. Work on insertion in dictionary. Not finished yet.
  20  *
  21  * Revision 1.4  1994/09/01  17:44:09  adam
  22  * depend include change.
  23  *
  24  * Revision 1.3  1994/08/18  12:40:56  adam
  25  * Some development of dictionary. Not finished at all!
  26  *
  27  * Revision 1.2  1994/08/17  13:32:19  adam
  28  * Use cache in dict - not in bfile.
  29  *
  30  * Revision 1.1  1994/08/16  16:26:48  adam
  31  * Added dict.
  32  *
  33  */
  34
  35 #include <string.h>
  36 #include <stdlib.h>
  37 #include <stdio.h>
  38 #include <assert.h>
  39
  40 #include <dict.h>
  41
  42 #define CHECK 0
  43
  44 static int dict_ins (Dict dict, const Dict_char *str,
  45                      Dict_ptr back_ptr, int userlen, void *userinfo);
  46 static void clean_page (Dict dict, Dict_ptr ptr, void *p, Dict_char *out,
  47                 Dict_ptr subptr, char *userinfo);
  48
  49
  50 static Dict_ptr new_page (Dict dict, Dict_ptr back_ptr, void **pp)
  51 {
  52     void *p;
  53     Dict_ptr ptr = dict->head.free_list;
  54     if (dict->head.free_list == dict->head.last)
  55     {
  56         dict->head.free_list++;
  57         dict->head.last = dict->head.free_list;
  58         dict_bf_newp (dict->dbf, ptr, &p);
  59     }
  60     else
  61     {
  62         dict_bf_readp (dict->dbf, dict->head.free_list, &p);
  63         dict->head.free_list = DICT_nextptr(p);
  64         if (dict->head.free_list == 0)
  65             dict->head.free_list = dict->head.last;
  66     }
  67     assert (p);
  68     DICT_type(p) = 0;
  69     DICT_backptr(p) = back_ptr;
  70     DICT_nextptr(p) = 0;
  71     DICT_nodir(p) = 0;
  72     DICT_size(p) = DICT_infoffset;
  73     if (pp)
  74         *pp = p;
  75     return ptr;
  76 }
  77
  78 static int split_page (Dict dict, Dict_ptr ptr, void *p)
  79 {
  80     void *subp;
  81     char *info_here;
  82     Dict_ptr subptr;
  83     int i, need;
  84     short *indxp, *best_indxp;
  85     Dict_char best_char = 0;
  86     Dict_char prev_char = 0;
  87     int best_no = -1, no_current = 1;
  88
  89     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
  90     for (i = DICT_nodir (p); --i >= 0; --indxp)
  91     {
  92         if (*indxp > 0) /* tail string here! */
  93         {
  94             Dict_char dc;
  95
  96             memcpy (&dc, (char*) p + *indxp, sizeof(dc));
  97             if (best_no < 0)
  98             {   /* first entry met */
  99                 best_char = prev_char = dc;
 100                 best_no = 1;
 101             }
 102             else if (prev_char == dc)
 103             {   /* same char prefix. update */
 104                 if (++no_current > best_no)
 105                 {   /* best entry so far */
 106                     best_no = no_current;
 107                     best_char = dc;
 108                     best_indxp = indxp;
 109                 }
 110             }
 111             else
 112             {   /* new char prefix. restore */
 113                 prev_char = dc;
 114                 no_current = 1;
 115             }
 116         }
 117     }
 118     if (best_no < 0) /* we didn't find any tail string entry at all! */
 119         return -1;
 120
 121     subptr = new_page (dict, ptr, &subp);
 122     /* scan entries to see if there is a string with */
 123     /* length 1. info_here indicates if such entry exist */
 124     info_here = NULL;
 125     for (indxp=best_indxp, i=0; i<best_no; i++, indxp++)
 126     {
 127         char *info;
 128         int slen;
 129
 130         assert (*indxp > 0);
 131
 132         info = (char*) p + *indxp;                    /* entry start */
 133         assert (*info == best_char);
 134         slen = dict_strlen(info);
 135
 136         assert (slen > 0);
 137         if (slen == 1)
 138         {
 139             assert (!info_here);
 140             info_here = info+(slen+1)*sizeof(Dict_char);
 141         }
 142     }
 143     /* calculate the amount of bytes needed for this entry when */
 144     /* transformed to a sub entry */
 145     need = sizeof(Dict_char)+sizeof(Dict_ptr)+1;
 146     if (info_here)
 147         need += *info_here;
 148
 149     indxp = best_indxp;
 150     /* now loop on all entries with string length > 1 i.e. all */
 151     /* those entries which contribute to a sub page */
 152     best_indxp = NULL;
 153     for (i=0; i<best_no; i++, indxp++)
 154     {
 155         char *info, *info1;
 156         int slen;
 157
 158         assert (*indxp > 0);
 159
 160         info = (char*) p + *indxp;                    /* entry start */
 161         assert (*info == best_char);
 162         slen = dict_strlen(info);
 163
 164         if (slen > 1)
 165         {
 166             info1 = info+(1+slen)*sizeof(Dict_char);  /* info start */
 167
 168             if (need <= (1+slen)*sizeof(Dict_char) + 1 + *info1)
 169                 best_indxp = indxp;                   /* space for entry */
 170             dict_ins (dict, info+sizeof(Dict_char), subptr, *info1, info1+1);
 171             dict_bf_readp (dict->dbf, ptr, &p);
 172         }
 173     }
 174 #if 1
 175     /* now clean the page ... */
 176     clean_page (dict, ptr, p, &best_char, subptr, info_here);
 177     return 0;
 178 #endif
 179     if (best_indxp)
 180     {   /* there was a hole big enough for a sub entry */
 181         char *info = (char*) p + *best_indxp;
 182         short *indxp1;
 183
 184         *--indxp = - *best_indxp;
 185         DICT_type(p) = 1;
 186         DICT_nodir (p) -= (best_no-1);
 187         indxp1 = (short*)((char*)p+DICT_PAGESIZE-DICT_nodir(p)*sizeof(short));
 188         while (indxp != indxp1)
 189         {
 190             --indxp;
 191             *indxp = indxp[1-best_no];
 192         }
 193         memcpy (info, &subptr, sizeof(Dict_ptr));     /* store subptr */
 194         info += sizeof(Dict_ptr);
 195         memcpy (info, &best_char, sizeof(Dict_char)); /* store sub char */
 196         info += sizeof(Dict_char);
 197         if (info_here)
 198             memcpy (info, info_here, *info_here+1);   /* with information */
 199         else
 200             *info = 0;                                /* without info */
 201 #if CHECK
 202         best_indxp = NULL;
 203         prev_char = 0;
 204         indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 205         for (i = DICT_nodir (p); --i >= 0; --indxp)
 206         {
 207             if (*indxp > 0) /* tail string here! */
 208             {
 209                 Dict_char dc;
 210
 211                 memcpy (&dc, (char*) p + *indxp, sizeof(dc));
 212                 assert (dc != best_char);
 213                 assert (dc >= prev_char);
 214                 prev_char = dc;
 215             }
 216             else
 217             {
 218                 Dict_char dc;
 219                 memcpy (&dc, (char*)p - *indxp+sizeof(Dict_ptr),
 220                         sizeof(dc));
 221                 assert (dc > prev_char);
 222                 if (dc == best_char)
 223                 {
 224                     assert (best_indxp == NULL);
 225                     best_indxp = indxp;
 226                 }
 227                 prev_char = dc;
 228             }
 229         }
 230         assert (best_indxp);
 231 #endif
 232     }
 233     else
 234     {
 235         short *indxp1, *indxp2;
 236         assert (0);
 237         DICT_type(p) = 1;
 238         DICT_nodir(p) -= best_no;
 239         indxp2 = indxp;
 240         indxp1 = (short*)((char*) p+DICT_PAGESIZE-DICT_nodir(p)*sizeof(short));
 241         do
 242         {
 243             --indxp2;
 244             indxp2[0] = indxp2[-best_no];
 245         } while (indxp2 != indxp1);
 246     }
 247     return 0;
 248 }
 249
 250 static void clean_page (Dict dict, Dict_ptr ptr, void *p, Dict_char *out,
 251                 Dict_ptr subptr, char *userinfo)
 252 {
 253     char *np = xmalloc (dict->head.page_size);
 254     int i, slen, no = 0;
 255     short *indxp1, *indxp2;
 256     char *info1, *info2;
 257
 258     indxp1 = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 259     indxp2 = (short*) ((char*) np+DICT_PAGESIZE);
 260     info2 = (char*) np + DICT_infoffset;
 261     for (i = DICT_nodir (p); --i >= 0; --indxp1)
 262     {
 263         if (*indxp1 > 0) /* tail string here! */
 264         {
 265             /* string (Dict_char *) DICT_EOS terminated */
 266             /* unsigned char        length of information */
 267             /* char *               information */
 268
 269             info1 = (char*) p + *indxp1;
 270             if (out && memcmp (out, info1, sizeof(Dict_char)) == 0)
 271             {
 272                 if (subptr == 0)
 273                     continue;
 274                 *--indxp2 = -(info2 - np);
 275                 memcpy (info2, &subptr, sizeof(Dict_ptr));
 276                 info2 += sizeof(Dict_ptr);
 277                 memcpy (info2, out, sizeof(Dict_char));
 278                 info2 += sizeof(Dict_char);
 279                 if (userinfo)
 280                 {
 281                     memcpy (info2, userinfo, *userinfo+1);
 282                     info2 += *userinfo + 1;
 283                 }
 284                 else
 285                     *info2++ = 0;
 286                 subptr = 0;
 287                 ++no;
 288                 continue;
 289             }
 290             *--indxp2 = info2 - np;
 291             slen = (dict_strlen(info1)+1)*sizeof(Dict_char);
 292             memcpy (info2, info1, slen);
 293             info1 += slen;
 294             info2 += slen;
 295         }
 296         else
 297         {
 298             /* Dict_ptr             subptr */
 299             /* Dict_char            sub char */
 300             /* unsigned char        length of information */
 301             /* char *               information */
 302
 303             assert (*indxp1 < 0);
 304             *--indxp2 = -(info2 - np);
 305             info1 = (char*) p - *indxp1;
 306             memcpy (info2, info1, sizeof(Dict_ptr)+sizeof(Dict_char));
 307             info1 += sizeof(Dict_ptr)+sizeof(Dict_char);
 308             info2 += sizeof(Dict_ptr)+sizeof(Dict_char);
 309         }
 310         slen = *info1+1;
 311         memcpy (info2, info1, slen);
 312         info2 += slen;
 313         ++no;
 314     }
 315     memcpy ((char*)p+DICT_infoffset, (char*)np+DICT_infoffset,
 316             DICT_PAGESIZE-DICT_infoffset);
 317     DICT_size(p) = info2 - np;
 318     DICT_type(p) = 0;
 319     DICT_nodir(p) = no;
 320     xfree (np);
 321 }
 322
 323
 324
 325 /* return 0 if new */
 326 /* return 1 if before but change of info */
 327 /* return 2 if same as before */
 328
 329 static int dict_ins (Dict dict, const Dict_char *str,
 330                      Dict_ptr back_ptr, int userlen, void *userinfo)
 331 {
 332     int hi, lo, mid, i, slen, cmp = 1;
 333     Dict_ptr ptr = back_ptr;
 334     short *indxp;
 335     char *info;
 336     void *p;
 337
 338     if (ptr == 0)
 339         ptr = new_page (dict, back_ptr, &p);
 340     else
 341         dict_bf_readp (dict->dbf, ptr, &p);
 342
 343     assert (p);
 344     assert (ptr);
 345
 346     mid = lo = 0;
 347     hi = DICT_nodir(p)-1;
 348     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 349     while (lo <= hi)
 350     {
 351         mid = (lo+hi)/2;
 352         if (indxp[-mid] > 0)
 353         {
 354             /* string (Dict_char *) DICT_EOS terminated */
 355             /* unsigned char        length of information */
 356             /* char *               information */
 357             info = (char*)p + indxp[-mid];
 358             cmp = dict_strcmp((Dict_char*) info, str);
 359             if (!cmp)
 360             {
 361                 info += (dict_strlen(info)+1)*sizeof(Dict_char);
 362                 /* consider change of userinfo length... */
 363                 if (*info == userlen)
 364                 {
 365                     if (memcmp (info+1, userinfo, userlen))
 366                     {
 367                         dict_bf_touch (dict->dbf, ptr);
 368                         memcpy (info+1, userinfo, userlen);
 369                         return 1;
 370                     }
 371                     return 2;
 372                 }
 373                 else if (*info > userlen)
 374                 {
 375                     DICT_type(p) = 1;
 376                     *info = userlen;
 377                     dict_bf_touch (dict->dbf, ptr);
 378                     memcpy (info+1, userinfo, userlen);
 379                     return 1;
 380                 }
 381                 break;
 382             }
 383         }
 384         else
 385         {
 386             Dict_char dc;
 387             Dict_ptr subptr;
 388
 389             /* Dict_ptr             subptr */
 390             /* Dict_char            sub char */
 391             /* unsigned char        length of information */
 392             /* char *               information */
 393             info = (char*)p - indxp[-mid];
 394             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 395             cmp = dc- *str;
 396             if (!cmp)
 397             {
 398                 memcpy (&subptr, info, sizeof(Dict_ptr));
 399                 if (*++str == DICT_EOS)
 400                 {
 401                     int xlen;
 402
 403                     xlen = info[sizeof(Dict_ptr)+sizeof(Dict_char)];
 404                     if (xlen == userlen)
 405                     {
 406                         if (memcmp (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 407                                     userinfo, userlen))
 408                         {
 409                             dict_bf_touch (dict->dbf, ptr);
 410                             memcpy (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 411                                     userinfo, userlen);
 412                             return 1;
 413                         }
 414                         return 2;
 415                     }
 416                     else if (xlen > userlen)
 417                     {
 418                         DICT_type(p) = 1;
 419                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = userlen;
 420                         memcpy (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 421                                 userinfo, userlen);
 422                         dict_bf_touch (dict->dbf, ptr);
 423                         return 1;
 424                     }
 425                     if (DICT_size(p)+sizeof(Dict_char)+sizeof(Dict_ptr)+
 426                         userlen >=
 427                         DICT_PAGESIZE - (1+DICT_nodir(p))*sizeof(short))
 428                     {
 429                         if (DICT_type(p) == 1)
 430                         {
 431                             clean_page (dict, ptr, p, NULL, 0, NULL);
 432                             dict_bf_touch (dict->dbf, ptr);
 433                             return dict_ins (dict, str-1, ptr,
 434                                              userlen, userinfo);
 435                         }
 436                         if (split_page (dict, ptr, p))
 437                         {
 438                             log (LOG_FATAL, "Unable to split page %d\n", ptr);
 439                             abort ();
 440                         }
 441                         return dict_ins (dict, str-1, ptr, userlen, userinfo);
 442                     }
 443                     else
 444                     {
 445                         info = (char*)p + DICT_size(p);
 446                         memcpy (info, &subptr, sizeof(subptr));
 447                         memcpy (info+sizeof(Dict_ptr), &dc, sizeof(Dict_char));
 448                         info[sizeof(Dict_char)+sizeof(Dict_ptr)] = userlen;
 449                         memcpy (info+sizeof(Dict_char)+sizeof(Dict_ptr)+1,
 450                                 userinfo, userlen);
 451                         indxp[-mid] = -DICT_size(p);
 452                         DICT_size(p) += sizeof(Dict_char)+sizeof(Dict_ptr)
 453                             +1+userlen;
 454                         DICT_type(p) = 1;
 455                         dict_bf_touch (dict->dbf, ptr);
 456                     }
 457                     if (xlen)
 458                         return 1;
 459                     return 0;
 460                 }
 461                 else
 462                 {
 463                     if (subptr == 0)
 464                     {
 465                         subptr = new_page (dict, ptr, NULL);
 466                         memcpy (info, &subptr, sizeof(subptr));
 467                         dict_bf_touch (dict->dbf, ptr);
 468                     }
 469                     return dict_ins (dict, str, subptr, userlen, userinfo);
 470                 }
 471             }
 472         }
 473         if (cmp < 0)
 474             lo = mid+1;
 475         else
 476             hi = mid-1;
 477     }
 478     indxp = indxp-mid;
 479     if (lo>hi && cmp < 0)
 480         --indxp;
 481     slen = (dict_strlen(str)+1)*sizeof(Dict_char);
 482     if (DICT_size(p)+slen+userlen >=
 483         DICT_PAGESIZE - (1+DICT_nodir(p))*sizeof(short)) /* overflow? */
 484     {
 485         if (DICT_type(p) == 1)
 486         {
 487             clean_page (dict, ptr, p, NULL, 0, NULL);
 488             dict_bf_touch (dict->dbf, ptr);
 489             return dict_ins (dict, str, ptr, userlen, userinfo);
 490         }
 491         i = 0;
 492         do
 493         {
 494             assert (i <= 1);
 495             if (split_page (dict, ptr, p))
 496             {
 497                 log (LOG_FATAL, "Unable to split page %d\n", ptr);
 498                 abort ();
 499             }
 500             if (DICT_size(p)+slen+userlen <
 501                 DICT_PAGESIZE - (1+DICT_nodir(p))*sizeof(short))
 502                 break;
 503             i++;
 504             clean_page (dict, ptr, p, NULL, 0, NULL);
 505         } while (DICT_size(p)+slen+userlen > DICT_PAGESIZE -
 506                  (1+DICT_nodir(p))*sizeof(short));
 507         return dict_ins (dict, str, ptr, userlen, userinfo);
 508     }
 509     if (cmp)
 510     {
 511         short *indxp1;
 512         (DICT_nodir(p))++;
 513         indxp1 = (short*)((char*) p + DICT_PAGESIZE
 514                           - DICT_nodir(p)*sizeof(short));
 515         for (; indxp1 != indxp; indxp1++)
 516             indxp1[0] = indxp1[1];
 517 #if CHECK
 518         indxp1 = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 519         for (i = DICT_nodir (p); --i >= 0; --indxp1)
 520         {
 521             if (*indxp1 < 0)
 522             {
 523                 info = (char*)p - *indxp1;
 524                 assert (info[sizeof(Dict_ptr)] > ' ');
 525             }
 526         }
 527 #endif
 528     }
 529     else
 530         DICT_type(p) = 1;
 531     info = (char*)p + DICT_size(p);
 532     memcpy (info, str, slen);
 533     info += slen;
 534     *info++ = userlen;
 535     memcpy (info, userinfo, userlen);
 536     info += userlen;
 537
 538     *indxp = DICT_size(p);
 539     DICT_size(p) = info- (char*) p;
 540     dict_bf_touch (dict->dbf, ptr);
 541     if (cmp)
 542         return 0;
 543     return 1;
 544 }
 545
 546 int dict_insert (Dict dict, const Dict_char *str, int userlen, void *userinfo)
 547 {
 548     assert (dict->head.last > 0);
 549     if (dict->head.last == 1)
 550         return dict_ins (dict, str, 0, userlen, userinfo);
 551     else
 552         return dict_ins (dict, str, 1, userlen, userinfo);
 553 }
 554