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