dict/insert.c

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