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