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