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