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