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