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