dict/insert.c

   1 /* $Id: insert.c,v 1.22 2002-08-02 19:26:55 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   3    Index Data Aps
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24
  25 #include <string.h>
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28 #include <assert.h>
  29
  30 #include <dict.h>
  31
  32 #define CHECK 0
  33
  34 static int dict_ins (Dict dict, const Dict_char *str,
  35                      Dict_ptr back_ptr, int userlen, void *userinfo);
  36 static void clean_page (Dict dict, Dict_ptr ptr, void *p, Dict_char *out,
  37                 Dict_ptr subptr, char *userinfo);
  38
  39
  40 static Dict_ptr new_page (Dict dict, Dict_ptr back_ptr, void **pp)
  41 {
  42     void *p;
  43     Dict_ptr ptr = dict->head.last;
  44     if (!dict->head.freelist)
  45     {
  46         dict_bf_newp (dict->dbf, dict->head.last, &p, dict->head.page_size);
  47         (dict->head.last)++;
  48     }
  49     else
  50     {
  51         ptr = dict->head.freelist;
  52         dict_bf_readp (dict->dbf, ptr, &p);
  53         dict->head.freelist = DICT_backptr(p);
  54     }
  55     assert (p);
  56     DICT_type(p) = 0;
  57     DICT_backptr(p) = back_ptr;
  58     DICT_nodir(p) = 0;
  59     DICT_size(p) = DICT_infoffset;
  60     DICT_bsize(p) = dict->head.page_size;
  61     if (pp)
  62         *pp = p;
  63     return ptr;
  64 }
  65
  66 static int split_page (Dict dict, Dict_ptr ptr, void *p)
  67 {
  68     void *subp;
  69     char *info_here;
  70     Dict_ptr subptr;
  71     int i, j;
  72     short *indxp, *best_indxp = NULL;
  73     Dict_char best_char = 0;
  74     Dict_char prev_char = 0;
  75     int best_no = -1, no_current = 1;
  76
  77     /* determine splitting char... */
  78     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
  79     for (i = DICT_nodir (p); --i >= 0; --indxp)
  80     {
  81         if (*indxp > 0) /* tail string here! */
  82         {
  83             Dict_char dc;
  84
  85             memcpy (&dc, (char*) p + *indxp, sizeof(dc));
  86             if (best_no < 0)
  87             {   /* first entry met */
  88                 best_char = prev_char = dc;
  89                 best_no = 1;
  90                 best_indxp = indxp;
  91             }
  92             else if (prev_char == dc)
  93             {   /* same char prefix. update */
  94                 if (++no_current > best_no)
  95                 {   /* best entry so far */
  96                     best_no = no_current;
  97                     best_char = dc;
  98                     best_indxp = indxp;
  99                 }
 100             }
 101             else
 102             {   /* new char prefix. restore */
 103                 prev_char = dc;
 104                 no_current = 1;
 105             }
 106         }
 107     }
 108     if (best_no < 0) /* we didn't find any tail string entry at all! */
 109         return -1;
 110
 111     j = best_indxp - (short*) p;
 112     subptr = new_page (dict, ptr, &subp);
 113     /* scan entries to see if there is a string with */
 114     /* length 1. info_here indicates if such entry exist */
 115     info_here = NULL;
 116     for (i=0; i<best_no; i++, j++)
 117     {
 118         char *info, *info1;
 119         int slen;
 120         Dict_char dc;
 121
 122         info = (char*) p + ((short*) p)[j];
 123         /* entry start */
 124         memcpy (&dc, info, sizeof(dc));
 125         assert (dc == best_char);
 126         slen = 1+dict_strlen((Dict_char*) info);
 127
 128         assert (slen > 1);
 129         if (slen == 2)
 130         {
 131             assert (!info_here);
 132             info_here = info+slen*sizeof(Dict_char);
 133         }
 134         else
 135         {
 136             info1 = info+slen*sizeof(Dict_char);  /* info start */
 137             dict_ins (dict, (Dict_char*) (info+sizeof(Dict_char)),
 138                       subptr, *info1, info1+1);
 139             dict_bf_readp (dict->dbf, ptr, &p);
 140         }
 141     }
 142     /* now clean the page ... */
 143     clean_page (dict, ptr, p, &best_char, subptr, info_here);
 144     return 0;
 145 }
 146
 147 static void clean_page (Dict dict, Dict_ptr ptr, void *p, Dict_char *out,
 148                         Dict_ptr subptr, char *userinfo)
 149 {
 150     char *np = (char *) xmalloc (dict->head.page_size);
 151     int i, slen, no = 0;
 152     short *indxp1, *indxp2;
 153     char *info1, *info2;
 154
 155     DICT_bsize(np) = dict->head.page_size;
 156     indxp1 = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 157     indxp2 = (short*) ((char*) np+DICT_bsize(np));
 158     info2 = (char*) np + DICT_infoffset;
 159     for (i = DICT_nodir (p); --i >= 0; --indxp1)
 160     {
 161         if (*indxp1 > 0) /* tail string here! */
 162         {
 163             /* string (Dict_char *) DICT_EOS terminated */
 164             /* unsigned char        length of information */
 165             /* char *               information */
 166
 167             info1 = (char*) p + *indxp1;
 168             if (out && memcmp (out, info1, sizeof(Dict_char)) == 0)
 169             {
 170                 if (subptr == 0)
 171                     continue;
 172                 *--indxp2 = -(info2 - np);
 173                 memcpy (info2, &subptr, sizeof(Dict_ptr));
 174                 info2 += sizeof(Dict_ptr);
 175                 memcpy (info2, out, sizeof(Dict_char));
 176                 info2 += sizeof(Dict_char);
 177                 if (userinfo)
 178                 {
 179                     memcpy (info2, userinfo, *userinfo+1);
 180                     info2 += *userinfo + 1;
 181                 }
 182                 else
 183                     *info2++ = 0;
 184                 subptr = 0;
 185                 ++no;
 186                 continue;
 187             }
 188             *--indxp2 = info2 - np;
 189             slen = (dict_strlen((Dict_char*) info1)+1)*sizeof(Dict_char);
 190             memcpy (info2, info1, slen);
 191             info1 += slen;
 192             info2 += slen;
 193         }
 194         else
 195         {
 196             /* Dict_ptr             subptr */
 197             /* Dict_char            sub char */
 198             /* unsigned char        length of information */
 199             /* char *               information */
 200
 201             assert (*indxp1 < 0);
 202             *--indxp2 = -(info2 - np);
 203             info1 = (char*) p - *indxp1;
 204             memcpy (info2, info1, sizeof(Dict_ptr)+sizeof(Dict_char));
 205             info1 += sizeof(Dict_ptr)+sizeof(Dict_char);
 206             info2 += sizeof(Dict_ptr)+sizeof(Dict_char);
 207         }
 208         slen = *info1+1;
 209         memcpy (info2, info1, slen);
 210         info2 += slen;
 211         ++no;
 212     }
 213 #if 1
 214     memcpy ((char*)p+DICT_infoffset,
 215             (char*)np+DICT_infoffset,
 216             info2 - ((char*)np+DICT_infoffset));
 217     memcpy ((char*)p + ((char*)indxp2 - (char*)np),
 218             indxp2,
 219             ((char*) np+DICT_bsize(p)) - (char*)indxp2);
 220 #else
 221     memcpy ((char*)p+DICT_infoffset, (char*)np+DICT_infoffset,
 222             DICT_pagesize(dict)-DICT_infoffset);
 223 #endif
 224     DICT_size(p) = info2 - np;
 225     DICT_type(p) = 0;
 226     DICT_nodir(p) = no;
 227     xfree (np);
 228     dict_bf_touch (dict->dbf, ptr);
 229 }
 230
 231
 232
 233 /* return 0 if new */
 234 /* return 1 if before but change of info */
 235 /* return 2 if same as before */
 236
 237 static int dict_ins (Dict dict, const Dict_char *str,
 238                      Dict_ptr ptr, int userlen, void *userinfo)
 239 {
 240     int hi, lo, mid, slen, cmp = 1;
 241     short *indxp;
 242     char *info;
 243     void *p;
 244
 245     dict_bf_readp (dict->dbf, ptr, &p);
 246
 247     assert (p);
 248     assert (ptr);
 249
 250     mid = lo = 0;
 251     hi = DICT_nodir(p)-1;
 252     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 253     while (lo <= hi)
 254     {
 255         mid = (lo+hi)/2;
 256         if (indxp[-mid] > 0)
 257         {
 258             /* string (Dict_char *) DICT_EOS terminated */
 259             /* unsigned char        length of information */
 260             /* char *               information */
 261             info = (char*)p + indxp[-mid];
 262             cmp = dict_strcmp((Dict_char*) info, str);
 263             if (!cmp)
 264             {
 265                 info += (dict_strlen((Dict_char*) info)+1)*sizeof(Dict_char);
 266                 /* consider change of userinfo length... */
 267                 if (*info == userlen)
 268                 {
 269                     /* change of userinfo ? */
 270                     if (memcmp (info+1, userinfo, userlen))
 271                     {
 272                         dict_bf_touch (dict->dbf, ptr);
 273                         memcpy (info+1, userinfo, userlen);
 274                         return 1;
 275                     }
 276                     /* same userinfo */
 277                     return 2;
 278                 }
 279                 else if (*info > userlen)
 280                 {
 281                     /* room for new userinfo */
 282                     DICT_type(p) = 1;
 283                     *info = userlen;
 284                     dict_bf_touch (dict->dbf, ptr);
 285                     memcpy (info+1, userinfo, userlen);
 286                     return 1;
 287                 }
 288                 break;
 289             }
 290         }
 291         else
 292         {
 293             Dict_char dc;
 294             Dict_ptr subptr;
 295
 296             /* Dict_ptr             subptr */
 297             /* Dict_char            sub char */
 298             /* unsigned char        length of information */
 299             /* char *               information */
 300             info = (char*)p - indxp[-mid];
 301             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 302             cmp = dc- *str;
 303             if (!cmp)
 304             {
 305                 memcpy (&subptr, info, sizeof(Dict_ptr));
 306                 if (*++str == DICT_EOS)
 307                 {
 308                     /* finish of string. Store userinfo here... */
 309
 310                     int xlen = info[sizeof(Dict_ptr)+sizeof(Dict_char)];
 311                     if (xlen == userlen)
 312                     {
 313                         if (memcmp (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 314                                     userinfo, userlen))
 315                         {
 316                             dict_bf_touch (dict->dbf, ptr);
 317                             memcpy (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 318                                     userinfo, userlen);
 319                             return 1;
 320                         }
 321                         return 2;
 322                     }
 323                     else if (xlen > userlen)
 324                     {
 325                         DICT_type(p) = 1;
 326                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = userlen;
 327                         memcpy (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 328                                 userinfo, userlen);
 329                         dict_bf_touch (dict->dbf, ptr);
 330                         return 1;
 331                     }
 332                     /* xlen < userlen, expanding needed ... */
 333                     if (DICT_size(p)+sizeof(Dict_char)+sizeof(Dict_ptr)+
 334                         userlen >=
 335                         DICT_bsize(p) - (1+DICT_nodir(p))*sizeof(short))
 336                     {
 337                         /* not enough room - split needed ... */
 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                             logf (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                     {   /* enough room - no split needed ... */
 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         (int)(DICT_bsize(p) - (1+DICT_nodir(p))*sizeof(short)))/* overflow? */
 392     {
 393         if (DICT_type(p))
 394         {
 395             clean_page (dict, ptr, p, NULL, 0, NULL);
 396             return dict_ins (dict, str, ptr, userlen, userinfo);
 397         }
 398         split_page (dict, ptr, p);
 399         return dict_ins (dict, str, ptr, userlen, userinfo);
 400     }
 401     if (cmp)
 402     {
 403         short *indxp1;
 404         (DICT_nodir(p))++;
 405         indxp1 = (short*)((char*) p + DICT_bsize(p)
 406                           - DICT_nodir(p)*sizeof(short));
 407         for (; indxp1 != indxp; indxp1++)
 408             indxp1[0] = indxp1[1];
 409 #if CHECK
 410         indxp1 = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
 411         for (i = DICT_nodir (p); --i >= 0; --indxp1)
 412         {
 413             if (*indxp1 < 0)
 414             {
 415                 info = (char*)p - *indxp1;
 416                 assert (info[sizeof(Dict_ptr)] > ' ');
 417             }
 418         }
 419 #endif
 420     }
 421     else
 422         DICT_type(p) = 1;
 423     info = (char*)p + DICT_size(p);
 424     memcpy (info, str, slen);
 425     info += slen;
 426     *info++ = userlen;
 427     memcpy (info, userinfo, userlen);
 428     info += userlen;
 429
 430     *indxp = DICT_size(p);
 431     DICT_size(p) = info- (char*) p;
 432     dict_bf_touch (dict->dbf, ptr);
 433     if (cmp)
 434         return 0;
 435     return 1;
 436 }
 437
 438 int dict_insert (Dict dict, const char *str, int userlen, void *userinfo)
 439 {
 440     if (!dict->head.root)
 441     {
 442         void *p;
 443         if (dict->rw)
 444             dict->head.root = new_page (dict, 0, &p);
 445         if (!dict->head.root)
 446             return 0;
 447     }
 448     return dict_ins (dict, (const Dict_char *) str, dict->head.root,
 449                      userlen, userinfo);
 450 }
 451