isamb/isamb.c

   1
   2 #include <yaz/xmalloc.h>
   3 #include <yaz/log.h>
   4 #include <isamb.h>
   5 #include <assert.h>
   6
   7 struct ISAMB_head {
   8     int first_block;
   9     int last_block;
  10     int block_size;
  11 };
  12
  13 #define ISAMB_DATA_OFFSET 3
  14
  15 struct ISAMB_s {
  16     BFiles bfs;
  17     BFile bf;
  18     ISAMC_M method;
  19     int head_dirty;
  20
  21     struct ISAMB_head head;
  22 };
  23
  24 struct ISAMB_block {
  25     int pos;
  26     int size;
  27     int leaf;
  28     int dirty;
  29     int offset;
  30     unsigned char *bytes;
  31     void *decodeClientData;
  32 };
  33
  34 struct ISAMB_PP_s {
  35     ISAMB isamb;
  36     int level;
  37     struct ISAMB_block **block;
  38 };
  39
  40 void encode_ptr (char **dst, int pos)
  41 {
  42     memcpy (*dst, &pos, sizeof(pos));
  43     (*dst) += sizeof(pos);
  44 }
  45
  46 void decode_ptr (char **src, int *pos)
  47 {
  48     memcpy (pos, *src, sizeof(*pos));
  49     (*src) += sizeof(*pos);
  50 }
  51
  52 ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method)
  53 {
  54     ISAMB isamb = xmalloc (sizeof(*isamb));
  55
  56     isamb->bfs = bfs;
  57     isamb->method = (ISAMC_M) xmalloc (sizeof(*method));
  58     memcpy (isamb->method, method, sizeof(*method));
  59
  60     isamb->head.first_block = 1;
  61     isamb->head.last_block = 1;
  62     isamb->head.block_size = 1024;
  63     isamb->head_dirty = 0;
  64
  65     isamb->bf = bf_open (bfs, name, isamb->head.block_size, writeflag);
  66
  67     bf_read (isamb->bf, 0, 0, sizeof(struct ISAMB_head),
  68              &isamb->head);
  69     return isamb;
  70 }
  71
  72 void isamb_close (ISAMB isamb)
  73 {
  74     if (isamb->head_dirty)
  75         bf_write (isamb->bf, 0, 0, sizeof(struct ISAMB_head), &isamb->head);
  76     xfree (isamb->method);
  77     xfree (isamb);
  78 }
  79
  80 struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos)
  81 {
  82     struct ISAMB_block *p;
  83     if (!pos)
  84         return 0;
  85     p = xmalloc (sizeof(*p));
  86     p->pos = pos;
  87     p->bytes = xmalloc (b->head.block_size);
  88     bf_read (b->bf, pos, 0, 0, p->bytes);
  89     p->leaf = p->bytes[0];
  90     p->size = p->bytes[1] + 256 * p->bytes[2];
  91     p->offset = ISAMB_DATA_OFFSET;
  92     p->dirty = 0;
  93     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
  94     return p;
  95 }
  96
  97 struct ISAMB_block *new_block (ISAMB b, int leaf)
  98 {
  99     struct ISAMB_block *p;
 100
 101     p = xmalloc (sizeof(*p));
 102     p->pos = b->head.last_block++;
 103     b->head_dirty = 1;
 104     p->bytes = xmalloc (b->head.block_size);
 105     memset (p->bytes, 0, b->head.block_size);
 106     p->leaf = leaf;
 107     p->size = ISAMB_DATA_OFFSET;
 108     p->dirty = 1;
 109     p->offset = ISAMB_DATA_OFFSET;
 110     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
 111     return p;
 112 }
 113
 114 void close_block (ISAMB b, struct ISAMB_block *p)
 115 {
 116     if (!p)
 117         return;
 118     if (p->dirty)
 119     {
 120         p->bytes[0] = p->leaf;
 121         p->bytes[1] = p->size & 255;
 122         p->bytes[2] = p->size >> 8;
 123         bf_write (b->bf, p->pos, 0, 0, p->bytes);
 124     }
 125     (*b->method->code_stop)(ISAMC_DECODE, p->decodeClientData);
 126     xfree (p->bytes);
 127     xfree (p);
 128 }
 129
 130 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
 131                  struct ISAMB_block **sp,
 132                  void *sub_item, int *sub_size);
 133
 134 void insert_leaf (ISAMB b, struct ISAMB_block *p, const void *new_item,
 135                   struct ISAMB_block **sp,
 136                   void *sub_item, int *sub_size)
 137 {
 138     char dst_buf[2048];
 139     char *dst = dst_buf;
 140     char *src = p->bytes + ISAMB_DATA_OFFSET;
 141     char *endp = p->bytes + p->size;
 142     void *c1 = (*b->method->code_start)(ISAMC_DECODE);
 143     void *c2 = (*b->method->code_start)(ISAMC_ENCODE);
 144     char *half1 = 0;
 145     char *half2 = 0;
 146     char *cut = dst_buf + p->size / 2;
 147     char cut_item_buf[256];
 148     int cut_item_size = 0;
 149
 150     while (src != endp)
 151     {
 152         char file_item_buf[256];
 153         char *file_item = file_item_buf;
 154
 155         (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
 156         if (new_item)
 157         {
 158             int d = (*b->method->compare_item)(file_item_buf, new_item);
 159             if (d > 0)
 160             {
 161                 char *item_ptr = (char*) new_item;
 162                 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
 163                 new_item = 0;
 164                 p->dirty = 1;
 165             }
 166             else if (d == 0)
 167             {
 168                 new_item = 0;
 169             }
 170         }
 171
 172         if (!half1 && dst > cut)
 173         {
 174             half1 = dst; /* candidate for splitting */
 175
 176             file_item = file_item_buf;
 177             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
 178
 179             cut_item_size = file_item - file_item_buf;
 180             memcpy (cut_item_buf, file_item_buf, cut_item_size);
 181
 182             half2 = dst;
 183         }
 184         else
 185         {
 186             file_item = file_item_buf;
 187             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
 188         }
 189     }
 190     if (new_item)
 191     {
 192         char *item_ptr = (char*) new_item;
 193         (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
 194         new_item = 0;
 195         p->dirty = 1;
 196     }
 197     p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
 198     if (p->size > b->head.block_size)
 199     {
 200         char *first_dst;
 201         char *cut_item = cut_item_buf;
 202
 203        /* first half */
 204         p->size = half1 - dst_buf + ISAMB_DATA_OFFSET;
 205         memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, half1 - dst_buf);
 206
 207         /* second half */
 208         *sp = new_block (b, 1);
 209
 210         (*b->method->code_reset)(c2);
 211
 212         first_dst = (*sp)->bytes + ISAMB_DATA_OFFSET;
 213
 214         (*b->method->code_item)(ISAMC_ENCODE, c2, &first_dst, &cut_item);
 215
 216         memcpy (first_dst, half2, dst - half2);
 217
 218         (*sp)->size = (first_dst - (char*) (*sp)->bytes) + (dst - half2);
 219         (*sp)->dirty = 1;
 220         p->dirty = 1;
 221         memcpy (sub_item, cut_item_buf, cut_item_size);
 222         *sub_size = cut_item_size;
 223
 224         yaz_log (LOG_LOG, "l split %d / %d", p->size, (*sp)->size);
 225
 226     }
 227     else
 228     {
 229         assert (p->size > ISAMB_DATA_OFFSET);
 230         assert (p->size <= b->head.block_size);
 231         memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, dst - dst_buf);
 232         *sp = 0;
 233     }
 234     (*b->method->code_stop)(ISAMC_DECODE, c1);
 235     (*b->method->code_stop)(ISAMC_ENCODE, c2);
 236 }
 237
 238 void insert_int (ISAMB b, struct ISAMB_block *p, const void *new_item,
 239                  struct ISAMB_block **sp,
 240                  void *split_item, int *split_size)
 241 {
 242     char *startp = p->bytes + ISAMB_DATA_OFFSET;
 243     char *src = startp;
 244     char *endp = p->bytes + p->size;
 245     int pos;
 246     struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
 247     char sub_item[256];
 248     int sub_size;
 249
 250     *sp = 0;
 251
 252     decode_ptr (&src, &pos);
 253     while (src != endp)
 254     {
 255         int item_len;
 256         int d;
 257         decode_ptr (&src, &item_len);
 258         d = (*b->method->compare_item)(src, new_item);
 259         if (d > 0)
 260         {
 261             sub_p1 = open_block (b, pos);
 262             assert (sub_p1);
 263             insert_sub (b, sub_p1, new_item, &sub_p2,
 264                         sub_item, &sub_size);
 265             break;
 266         }
 267         src += item_len;
 268         decode_ptr (&src, &pos);
 269     }
 270     if (!sub_p1)
 271     {
 272         sub_p1 = open_block (b, pos);
 273         assert (sub_p1);
 274         insert_sub (b, sub_p1, new_item, &sub_p2,
 275                     sub_item, &sub_size);
 276     }
 277     if (sub_p2)
 278     {
 279         char dst_buf[2048];
 280         char *dst = dst_buf;
 281
 282         assert (sub_size < 20);
 283
 284         memcpy (dst, startp, src - startp);
 285
 286         dst += src - startp;
 287
 288         encode_ptr (&dst, sub_size);      /* sub length and item */
 289         memcpy (dst, sub_item, sub_size);
 290         dst += sub_size;
 291
 292         encode_ptr (&dst, sub_p2->pos);   /* pos */
 293
 294         if (endp - src)                   /* remaining data */
 295         {
 296             memcpy (dst, src, endp - src);
 297             dst += endp - src;
 298         }
 299         p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
 300         if (p->size <= b->head.block_size)
 301         {
 302             memcpy (startp, dst_buf, dst - dst_buf);
 303         }
 304         else
 305         {
 306             int p_new_size;
 307             char *half;
 308             src = dst_buf;
 309             endp = dst;
 310
 311             half = src + b->head.block_size/2;
 312             decode_ptr (&src, &pos);
 313             while (src <= half)
 314             {
 315                 decode_ptr (&src, split_size);
 316                 src += *split_size;
 317                 decode_ptr (&src, &pos);
 318             }
 319             p_new_size = src - dst_buf;
 320             memcpy (p->bytes + ISAMB_DATA_OFFSET, dst_buf, p_new_size);
 321             p_new_size += ISAMB_DATA_OFFSET;
 322
 323             decode_ptr (&src, split_size);
 324             memcpy (split_item, src, *split_size);
 325             src += *split_size;
 326
 327             *sp = new_block (b, 0);
 328             (*sp)->size = endp - src;
 329             memcpy ((*sp)->bytes+ISAMB_DATA_OFFSET, src, (*sp)->size);
 330             (*sp)->size += ISAMB_DATA_OFFSET;
 331
 332             yaz_log (LOG_LOG, "i split %d -> %d %d",
 333                      p->size, p_new_size, (*sp)->size);
 334             p->size = p_new_size;
 335         }
 336         p->dirty = 1;
 337         close_block (b, sub_p2);
 338     }
 339     close_block (b, sub_p1);
 340 }
 341
 342 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
 343                 struct ISAMB_block **sp,
 344                 void *sub_item, int *sub_size)
 345 {
 346     if (p->leaf)
 347         insert_leaf (b, p, new_item, sp, sub_item, sub_size);
 348     else
 349         insert_int (b, p, new_item, sp, sub_item, sub_size);
 350 }
 351
 352 int isamb_insert_one (ISAMB b, const void *item, ISAMC_P pos)
 353 {
 354     struct ISAMB_block *p, *sp = 0;
 355     char sub_item[256];
 356     int sub_size;
 357
 358     if (!pos)
 359         p = new_block (b, 1);
 360     else
 361         p = open_block (b, pos);
 362     if (!p)
 363         return -1;
 364
 365     insert_sub (b, p, item, &sp, sub_item, &sub_size);
 366     if (sp)
 367     {    /* increase level of tree by one */
 368         struct ISAMB_block *p2 = new_block (b, 0);
 369         char *dst = p2->bytes + p2->size;
 370
 371         encode_ptr (&dst, p->pos);
 372         assert (sub_size < 20);
 373         encode_ptr (&dst, sub_size);
 374         memcpy (dst, sub_item, sub_size);
 375         dst += sub_size;
 376         encode_ptr (&dst, sp->pos);
 377
 378         p2->size = dst - (char*) p2->bytes;
 379         pos = p2->pos;  /* return new super page */
 380         close_block (b, sp);
 381         close_block (b, p2);
 382     }
 383     else
 384         pos = p->pos;   /* return current one (again) */
 385     close_block (b, p);
 386     return pos;
 387 }
 388
 389 ISAMB_P isamb_merge (ISAMB b, ISAMB_P pos, ISAMC_I data)
 390 {
 391     int i_mode;
 392     char item_buf[256];
 393     char *item_ptr = item_buf;
 394     while ((*data->read_item)(data->clientData, &item_ptr, &i_mode))
 395     {
 396         item_ptr = item_buf;
 397         pos = isamb_insert_one (b, item_buf, pos);
 398     }
 399     return pos;
 400 }
 401
 402 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAMB_P pos)
 403 {
 404     ISAMB_PP pp = xmalloc (sizeof(*pp));
 405
 406     pp->isamb = isamb;
 407     pp->block = xmalloc (10 * sizeof(*pp->block));
 408
 409     pp->level = 0;
 410     while (1)
 411     {
 412         struct ISAMB_block *p = open_block (isamb, pos);
 413         char *src = p->bytes + p->offset;
 414         pp->block[pp->level] = p;
 415
 416         if (p->bytes[0]) /* leaf */
 417             break;
 418
 419         decode_ptr (&src, &pos);
 420         p->offset = src - (char*) p->bytes;
 421         pp->level++;
 422     }
 423     pp->block[pp->level+1] = 0;
 424     return pp;
 425 }
 426
 427 void isamb_pp_close (ISAMB_PP pp)
 428 {
 429     int i;
 430     if (!pp)
 431         return;
 432     for (i = 0; i <= pp->level; i++)
 433         close_block (pp->isamb, pp->block[i]);
 434     xfree (pp->block);
 435     xfree (pp);
 436 }
 437
 438 int isamb_pp_read (ISAMB_PP pp, void *buf)
 439 {
 440     char *dst = buf;
 441     char *src;
 442     struct ISAMB_block *p = pp->block[pp->level];
 443     if (!p)
 444         return 0;
 445
 446     while (p->offset == p->size)
 447     {
 448         int pos, item_len;
 449         while (p->offset == p->size)
 450         {
 451             if (pp->level == 0)
 452                 return 0;
 453             close_block (pp->isamb, pp->block[pp->level]);
 454             pp->block[pp->level] = 0;
 455             (pp->level)--;
 456             p = pp->block[pp->level];
 457             assert (p->bytes[0] == 0);  /* must be int */
 458         }
 459         src = p->bytes + p->offset;
 460
 461         decode_ptr (&src, &item_len);
 462         src += item_len;
 463         decode_ptr (&src, &pos);
 464
 465         p->offset = src - (char*) p->bytes;
 466
 467         ++(pp->level);
 468
 469         while (1)
 470         {
 471             pp->block[pp->level] = p = open_block (pp->isamb, pos);
 472
 473             if (p->bytes[0]) /* leaf */
 474             {
 475                 break;
 476             }
 477             src = p->bytes + p->offset;
 478             decode_ptr (&src, &pos);
 479             p->offset = src - (char*) p->bytes;
 480             pp->level++;
 481         }
 482     }
 483     assert (p->offset < p->size);
 484     assert (p->bytes[0]);
 485     src = p->bytes + p->offset;
 486     (*pp->isamb->method->code_item)(ISAMC_DECODE, p->decodeClientData,
 487                                     &dst, &src);
 488     p->offset = src - (char*) p->bytes;
 489     return 1;
 490 }
 491
 492 int isamb_pp_num (ISAMB_PP pp)
 493 {
 494     return 1;
 495 }