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