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