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