dict/insert.c

   1 /* $Id: insert.c,v 1.29 2006-11-14 12:04:38 adam Exp $
   2    Copyright (C) 1995-2006
   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 this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 */
  22
  23
  24
  25 #include <string.h>
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28 #include <assert.h>
  29
  30 #include "dict-p.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     assert(best_no >= 0); /* we didn't find any tail string entry at all! */
 109
 110     j = best_indxp - (short*) p;
 111     subptr = new_page (dict, ptr, &subp);
 112     /* scan entries to see if there is a string with */
 113     /* length 1. info_here indicates if such entry exist */
 114     info_here = NULL;
 115     for (i=0; i<best_no; i++, j++)
 116     {
 117         char *info, *info1;
 118         int slen;
 119         Dict_char dc;
 120
 121         info = (char*) p + ((short*) p)[j];
 122         /* entry start */
 123         memcpy (&dc, info, sizeof(dc));
 124         assert (dc == best_char);
 125         slen = 1+dict_strlen((Dict_char*) info);
 126
 127         assert (slen > 1);
 128         if (slen == 2)
 129         {
 130             assert (!info_here);
 131             info_here = info+slen*sizeof(Dict_char);
 132         }
 133         else
 134         {
 135             info1 = info+slen*sizeof(Dict_char);  /* info start */
 136             dict_ins (dict, (Dict_char*) (info+sizeof(Dict_char)),
 137                       subptr, *info1, info1+1);
 138             dict_bf_readp (dict->dbf, ptr, &p);
 139         }
 140     }
 141     /* now clean the page ... */
 142     clean_page (dict, ptr, p, &best_char, subptr, info_here);
 143     return 0;
 144 }
 145
 146 static void clean_page (Dict dict, Dict_ptr ptr, void *p, Dict_char *out,
 147                         Dict_ptr subptr, char *userinfo)
 148 {
 149     char *np = (char *) xmalloc (dict->head.page_size);
 150     int i, slen, no = 0;
 151     short *indxp1, *indxp2;
 152     char *info1, *info2;
 153
 154     DICT_bsize(np) = dict->head.page_size;
 155     indxp1 = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 156     indxp2 = (short*) ((char*) np+DICT_bsize(np));
 157     info2 = (char*) np + DICT_infoffset;
 158     for (i = DICT_nodir (p); --i >= 0; --indxp1)
 159     {
 160         if (*indxp1 > 0) /* tail string here! */
 161         {
 162             /* string (Dict_char *) DICT_EOS terminated */
 163             /* unsigned char        length of information */
 164             /* char *               information */
 165
 166             info1 = (char*) p + *indxp1;
 167             if (out && memcmp (out, info1, sizeof(Dict_char)) == 0)
 168             {
 169                 if (subptr == 0)
 170                     continue;
 171                 *--indxp2 = -(info2 - np);
 172                 memcpy (info2, &subptr, sizeof(Dict_ptr));
 173                 info2 += sizeof(Dict_ptr);
 174                 memcpy (info2, out, sizeof(Dict_char));
 175                 info2 += sizeof(Dict_char);
 176                 if (userinfo)
 177                 {
 178                     memcpy (info2, userinfo, *userinfo+1);
 179                     info2 += *userinfo + 1;
 180                 }
 181                 else
 182                     *info2++ = 0;
 183                 subptr = 0;
 184                 ++no;
 185                 continue;
 186             }
 187             *--indxp2 = info2 - np;
 188             slen = (dict_strlen((Dict_char*) info1)+1)*sizeof(Dict_char);
 189             memcpy (info2, info1, slen);
 190             info1 += slen;
 191             info2 += slen;
 192         }
 193         else
 194         {
 195             /* Dict_ptr             subptr */
 196             /* Dict_char            sub char */
 197             /* unsigned char        length of information */
 198             /* char *               information */
 199
 200             assert (*indxp1 < 0);
 201             *--indxp2 = -(info2 - np);
 202             info1 = (char*) p - *indxp1;
 203             memcpy (info2, info1, sizeof(Dict_ptr)+sizeof(Dict_char));
 204             info1 += sizeof(Dict_ptr)+sizeof(Dict_char);
 205             info2 += sizeof(Dict_ptr)+sizeof(Dict_char);
 206         }
 207         slen = *info1+1;
 208         memcpy (info2, info1, slen);
 209         info2 += slen;
 210         ++no;
 211     }
 212 #if 1
 213     memcpy ((char*)p+DICT_infoffset,
 214             (char*)np+DICT_infoffset,
 215             info2 - ((char*)np+DICT_infoffset));
 216     memcpy ((char*)p + ((char*)indxp2 - (char*)np),
 217             indxp2,
 218             ((char*) np+DICT_bsize(p)) - (char*)indxp2);
 219 #else
 220     memcpy ((char*)p+DICT_infoffset, (char*)np+DICT_infoffset,
 221             DICT_pagesize(dict)-DICT_infoffset);
 222 #endif
 223     DICT_size(p) = info2 - np;
 224     DICT_type(p) = 0;
 225     DICT_nodir(p) = no;
 226     xfree (np);
 227     dict_bf_touch (dict->dbf, ptr);
 228 }
 229
 230
 231
 232 /* return 0 if new */
 233 /* return 1 if before but change of info */
 234 /* return 2 if same as before */
 235
 236 static int dict_ins (Dict dict, const Dict_char *str,
 237                      Dict_ptr ptr, int userlen, void *userinfo)
 238 {
 239     int hi, lo, mid, slen, cmp = 1;
 240     short *indxp;
 241     char *info;
 242     void *p;
 243
 244     dict_bf_readp (dict->dbf, ptr, &p);
 245
 246     assert (p);
 247     assert (ptr);
 248
 249     mid = lo = 0;
 250     hi = DICT_nodir(p)-1;
 251     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 252     while (lo <= hi)
 253     {
 254         mid = (lo+hi)/2;
 255         if (indxp[-mid] > 0)
 256         {
 257             /* string (Dict_char *) DICT_EOS terminated */
 258             /* unsigned char        length of information */
 259             /* char *               information */
 260             info = (char*)p + indxp[-mid];
 261             cmp = dict_strcmp((Dict_char*) info, str);
 262             if (!cmp)
 263             {
 264                 info += (dict_strlen((Dict_char*) info)+1)*sizeof(Dict_char);
 265                 /* consider change of userinfo length... */
 266                 if (*info == userlen)
 267                 {
 268                     /* change of userinfo ? */
 269                     if (memcmp (info+1, userinfo, userlen))
 270                     {
 271                         dict_bf_touch (dict->dbf, ptr);
 272                         memcpy (info+1, userinfo, userlen);
 273                         return 1;
 274                     }
 275                     /* same userinfo */
 276                     return 2;
 277                 }
 278                 else if (*info > userlen)
 279                 {
 280                     /* room for new userinfo */
 281                     DICT_type(p) = 1;
 282                     *info = userlen;
 283                     dict_bf_touch (dict->dbf, ptr);
 284                     memcpy (info+1, userinfo, userlen);
 285                     return 1;
 286                 }
 287                 break;
 288             }
 289         }
 290         else
 291         {
 292             Dict_char dc;
 293             Dict_ptr subptr;
 294
 295             /* Dict_ptr             subptr */
 296             /* Dict_char            sub char */
 297             /* unsigned char        length of information */
 298             /* char *               information */
 299             info = (char*)p - indxp[-mid];
 300             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 301             cmp = dc- *str;
 302             if (!cmp)
 303             {
 304                 memcpy (&subptr, info, sizeof(Dict_ptr));
 305                 if (*++str == DICT_EOS)
 306                 {
 307                     /* finish of string. Store userinfo here... */
 308
 309                     int xlen = info[sizeof(Dict_ptr)+sizeof(Dict_char)];
 310                     if (xlen == userlen)
 311                     {
 312                         if (memcmp (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 313                                     userinfo, userlen))
 314                         {
 315                             dict_bf_touch (dict->dbf, ptr);
 316                             memcpy (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 317                                     userinfo, userlen);
 318                             return 1;
 319                         }
 320                         return 2;
 321                     }
 322                     else if (xlen > userlen)
 323                     {
 324                         DICT_type(p) = 1;
 325                         info[sizeof(Dict_ptr)+sizeof(Dict_char)] = userlen;
 326                         memcpy (info+sizeof(Dict_ptr)+sizeof(Dict_char)+1,
 327                                 userinfo, userlen);
 328                         dict_bf_touch (dict->dbf, ptr);
 329                         return 1;
 330                     }
 331                     /* xlen < userlen, expanding needed ... */
 332                     if (DICT_size(p)+sizeof(Dict_char)+sizeof(Dict_ptr)+
 333                         userlen >=
 334                         DICT_bsize(p) - (1+DICT_nodir(p))*sizeof(short))
 335                     {
 336                         /* not enough room - split needed ... */
 337                         if (DICT_type(p) == 1)
 338                         {
 339                             clean_page (dict, ptr, p, NULL, 0, NULL);
 340                             return dict_ins (dict, str-1, ptr,
 341                                              userlen, userinfo);
 342                         }
 343                         if (split_page (dict, ptr, p))
 344                         {
 345                             yaz_log (YLOG_FATAL, "Unable to split page %d\n", ptr);
 346                             assert(0);
 347                         }
 348                         return dict_ins (dict, str-1, ptr, userlen, userinfo);
 349                     }
 350                     else
 351                     {   /* enough room - no split needed ... */
 352                         info = (char*)p + DICT_size(p);
 353                         memcpy (info, &subptr, sizeof(subptr));
 354                         memcpy (info+sizeof(Dict_ptr), &dc, sizeof(Dict_char));
 355                         info[sizeof(Dict_char)+sizeof(Dict_ptr)] = userlen;
 356                         memcpy (info+sizeof(Dict_char)+sizeof(Dict_ptr)+1,
 357                                 userinfo, userlen);
 358                         indxp[-mid] = -DICT_size(p);
 359                         DICT_size(p) += sizeof(Dict_char)+sizeof(Dict_ptr)
 360                             +1+userlen;
 361                         DICT_type(p) = 1;
 362                         dict_bf_touch (dict->dbf, ptr);
 363                     }
 364                     if (xlen)
 365                         return 1;
 366                     return 0;
 367                 }
 368                 else
 369                 {
 370                     if (subptr == 0)
 371                     {
 372                         subptr = new_page (dict, ptr, NULL);
 373                         memcpy (info, &subptr, sizeof(subptr));
 374                         dict_bf_touch (dict->dbf, ptr);
 375                     }
 376                     return dict_ins (dict, str, subptr, userlen, userinfo);
 377                 }
 378             }
 379         }
 380         if (cmp < 0)
 381             lo = mid+1;
 382         else
 383             hi = mid-1;
 384     }
 385     indxp = indxp-mid;
 386     if (lo>hi && cmp < 0)
 387         --indxp;
 388     slen = (dict_strlen(str)+1)*sizeof(Dict_char);
 389     if (DICT_size(p)+slen+userlen >=
 390         (int)(DICT_bsize(p) - (1+DICT_nodir(p))*sizeof(short)))/* overflow? */
 391     {
 392         if (DICT_type(p))
 393         {
 394             clean_page (dict, ptr, p, NULL, 0, NULL);
 395             return dict_ins (dict, str, ptr, userlen, userinfo);
 396         }
 397         split_page (dict, ptr, p);
 398         return dict_ins (dict, str, ptr, userlen, userinfo);
 399     }
 400     if (cmp)
 401     {
 402         short *indxp1;
 403         (DICT_nodir(p))++;
 404         indxp1 = (short*)((char*) p + DICT_bsize(p)
 405                           - DICT_nodir(p)*sizeof(short));
 406         for (; indxp1 != indxp; indxp1++)
 407             indxp1[0] = indxp1[1];
 408 #if CHECK
 409         indxp1 = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
 410         for (i = DICT_nodir (p); --i >= 0; --indxp1)
 411         {
 412             if (*indxp1 < 0)
 413             {
 414                 info = (char*)p - *indxp1;
 415                 assert (info[sizeof(Dict_ptr)] > ' ');
 416             }
 417         }
 418 #endif
 419     }
 420     else
 421         DICT_type(p) = 1;
 422     info = (char*)p + DICT_size(p);
 423     memcpy (info, str, slen);
 424     info += slen;
 425     *info++ = userlen;
 426     memcpy (info, userinfo, userlen);
 427     info += userlen;
 428
 429     *indxp = DICT_size(p);
 430     DICT_size(p) = info- (char*) p;
 431     dict_bf_touch (dict->dbf, ptr);
 432     if (cmp)
 433         return 0;
 434     return 1;
 435 }
 436
 437 int dict_insert (Dict dict, const char *str, int userlen, void *userinfo)
 438 {
 439     if (!dict->rw)
 440         return -1;
 441     if (!dict->head.root)
 442     {
 443         void *p;
 444         dict->head.root = new_page (dict, 0, &p);
 445         if (!dict->head.root)
 446             return -1;
 447     }
 448     return dict_ins (dict, (const Dict_char *) str, dict->head.root,
 449                      userlen, userinfo);
 450 }
 451
 452 /*
 453  * Local variables:
 454  * c-basic-offset: 4
 455  * indent-tabs-mode: nil
 456  * End:
 457  * vim: shiftwidth=4 tabstop=8 expandtab
 458  */
 459