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