dict/insert.c

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