dict/insert.c

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