index/trunc.c

   1 /*
   2  * Copyright (C) 1994-2002, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss, Heikki Levanto
   5  *
   6  * $Id: trunc.c,v 1.26 2002-07-25 13:06:43 adam Exp $
   7  *
   8  */
   9 #include <stdio.h>
  10 #include <assert.h>
  11
  12 #define NEW_TRUNC 1
  13
  14 #include "index.h"
  15 #include <rstemp.h>
  16 #include <rsnull.h>
  17 #include <rsisams.h>
  18 #include <rsisam.h>
  19 #include <rsisamc.h>
  20 #include <rsisamd.h>
  21 #include <rsisamb.h>
  22 #if NEW_TRUNC
  23 #include <rsm_or.h>
  24 #endif
  25
  26 struct trunc_info {
  27     int  *ptr;
  28     int  *indx;
  29     char **heap;
  30     int  heapnum;
  31     int  (*cmp)(const void *p1, const void *p2);
  32     int  keysize;
  33     char *swapbuf;
  34     char *tmpbuf;
  35     char *buf;
  36 };
  37
  38 static void heap_swap (struct trunc_info *ti, int i1, int i2)
  39 {
  40     int swap;
  41
  42     swap = ti->ptr[i1];
  43     ti->ptr[i1] = ti->ptr[i2];
  44     ti->ptr[i2] = swap;
  45 }
  46
  47 static void heap_delete (struct trunc_info *ti)
  48 {
  49     int cur = 1, child = 2;
  50
  51     heap_swap (ti, 1, ti->heapnum--);
  52     while (child <= ti->heapnum) {
  53         if (child < ti->heapnum &&
  54             (*ti->cmp)(ti->heap[ti->ptr[child]],
  55                        ti->heap[ti->ptr[1+child]]) > 0)
  56             child++;
  57         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
  58                        ti->heap[ti->ptr[child]]) > 0)
  59         {
  60             heap_swap (ti, cur, child);
  61             cur = child;
  62             child = 2*cur;
  63         }
  64         else
  65             break;
  66     }
  67 }
  68
  69 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
  70 {
  71     int cur, parent;
  72
  73     cur = ++(ti->heapnum);
  74     memcpy (ti->heap[ti->ptr[cur]], buf, ti->keysize);
  75     ti->indx[ti->ptr[cur]] = indx;
  76     parent = cur/2;
  77     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
  78                                 ti->heap[ti->ptr[cur]]) > 0)
  79     {
  80         heap_swap (ti, cur, parent);
  81         cur = parent;
  82         parent = cur/2;
  83     }
  84 }
  85
  86 static struct trunc_info *heap_init (int size, int key_size,
  87                                      int (*cmp)(const void *p1,
  88                                                 const void *p2))
  89 {
  90     struct trunc_info *ti = (struct trunc_info *) xmalloc (sizeof(*ti));
  91     int i;
  92
  93     ++size;
  94     ti->heapnum = 0;
  95     ti->keysize = key_size;
  96     ti->cmp = cmp;
  97     ti->indx = (int *) xmalloc (size * sizeof(*ti->indx));
  98     ti->heap = (char **) xmalloc (size * sizeof(*ti->heap));
  99     ti->ptr = (int *) xmalloc (size * sizeof(*ti->ptr));
 100     ti->swapbuf = (char *) xmalloc (ti->keysize);
 101     ti->tmpbuf = (char *) xmalloc (ti->keysize);
 102     ti->buf = (char *) xmalloc (size * ti->keysize);
 103     for (i = size; --i >= 0; )
 104     {
 105         ti->ptr[i] = i;
 106         ti->heap[i] = ti->buf + ti->keysize * i;
 107     }
 108     return ti;
 109 }
 110
 111 static void heap_close (struct trunc_info *ti)
 112 {
 113     xfree (ti->ptr);
 114     xfree (ti->indx);
 115     xfree (ti->heap);
 116     xfree (ti->swapbuf);
 117     xfree (ti->tmpbuf);
 118     xfree (ti->buf);
 119     xfree (ti);
 120 }
 121
 122 static RSET rset_trunc_r (ZebraHandle zi, const char *term, int length,
 123                           const char *flags, ISAMS_P *isam_p, int from, int to,
 124                           int merge_chunk, int preserve_position,
 125                           int term_type)
 126 {
 127     RSET result;
 128     RSFD result_rsfd;
 129     rset_temp_parms parms;
 130
 131     parms.cmp = key_compare_it;
 132     parms.key_size = sizeof(struct it_key);
 133     parms.temp_path = res_get (zi->res, "setTmpDir");
 134     parms.rset_term = rset_term_create (term, length, flags, term_type);
 135     result = rset_create (rset_kind_temp, &parms);
 136     result_rsfd = rset_open (result, RSETF_WRITE);
 137
 138     if (to - from > merge_chunk)
 139     {
 140         RSFD *rsfd;
 141         RSET *rset;
 142         int term_index;
 143         int i, i_add = (to-from)/merge_chunk + 1;
 144         struct trunc_info *ti;
 145         int rscur = 0;
 146         int rsmax = (to-from)/i_add + 1;
 147
 148         rset = (RSET *) xmalloc (sizeof(*rset) * rsmax);
 149         rsfd = (RSFD *) xmalloc (sizeof(*rsfd) * rsmax);
 150
 151         for (i = from; i < to; i += i_add)
 152         {
 153             if (i_add <= to - i)
 154                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
 155                                             isam_p, i, i+i_add,
 156                                             merge_chunk, preserve_position,
 157                                             term_type);
 158             else
 159                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
 160                                             isam_p, i, to,
 161                                             merge_chunk, preserve_position,
 162                                             term_type);
 163             rscur++;
 164         }
 165         ti = heap_init (rscur, sizeof(struct it_key), key_compare_it);
 166         for (i = rscur; --i >= 0; )
 167         {
 168             rsfd[i] = rset_open (rset[i], RSETF_READ);
 169             if (rset_read (rset[i], rsfd[i], ti->tmpbuf, &term_index))
 170                 heap_insert (ti, ti->tmpbuf, i);
 171             else
 172             {
 173                 rset_close (rset[i], rsfd[i]);
 174                 rset_delete (rset[i]);
 175             }
 176         }
 177         while (ti->heapnum)
 178         {
 179             int n = ti->indx[ti->ptr[1]];
 180
 181             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 182
 183             while (1)
 184             {
 185                 if (!rset_read (rset[n], rsfd[n], ti->tmpbuf, &term_index))
 186                 {
 187                     heap_delete (ti);
 188                     rset_close (rset[n], rsfd[n]);
 189                     rset_delete (rset[n]);
 190                     break;
 191                 }
 192                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 193                 {
 194                     heap_delete (ti);
 195                     heap_insert (ti, ti->tmpbuf, n);
 196                     break;
 197                 }
 198             }
 199         }
 200         xfree (rset);
 201         xfree (rsfd);
 202         heap_close (ti);
 203     }
 204     else if (zi->reg->isam)
 205     {
 206         ISPT *ispt;
 207         int i;
 208         struct trunc_info *ti;
 209
 210         ispt = (ISPT *) xmalloc (sizeof(*ispt) * (to-from));
 211
 212         ti = heap_init (to-from, sizeof(struct it_key),
 213                         key_compare_it);
 214         for (i = to-from; --i >= 0; )
 215         {
 216             ispt[i] = is_position (zi->reg->isam, isam_p[from+i]);
 217             if (is_readkey (ispt[i], ti->tmpbuf))
 218                 heap_insert (ti, ti->tmpbuf, i);
 219             else
 220                 is_pt_free (ispt[i]);
 221         }
 222         while (ti->heapnum)
 223         {
 224             int n = ti->indx[ti->ptr[1]];
 225
 226             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 227             if (preserve_position)
 228             {
 229 /* section that preserve all keys */
 230                 heap_delete (ti);
 231                 if (is_readkey (ispt[n], ti->tmpbuf))
 232                     heap_insert (ti, ti->tmpbuf, n);
 233                 else
 234                     is_pt_free (ispt[n]);
 235             }
 236             else
 237             {
 238 /* section that preserve all keys with unique sysnos */
 239                 while (1)
 240                 {
 241                     if (!is_readkey (ispt[n], ti->tmpbuf))
 242                     {
 243                         heap_delete (ti);
 244                         is_pt_free (ispt[n]);
 245                         break;
 246                     }
 247                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 248                     {
 249                         heap_delete (ti);
 250                         heap_insert (ti, ti->tmpbuf, n);
 251                         break;
 252                     }
 253                 }
 254             }
 255         }
 256         heap_close (ti);
 257         xfree (ispt);
 258     }
 259     else if (zi->reg->isamc)
 260     {
 261         ISAMC_PP *ispt;
 262         int i;
 263         struct trunc_info *ti;
 264
 265         ispt = (ISAMC_PP *) xmalloc (sizeof(*ispt) * (to-from));
 266
 267         ti = heap_init (to-from, sizeof(struct it_key),
 268                         key_compare_it);
 269         for (i = to-from; --i >= 0; )
 270         {
 271             ispt[i] = isc_pp_open (zi->reg->isamc, isam_p[from+i]);
 272             if (isc_pp_read (ispt[i], ti->tmpbuf))
 273                 heap_insert (ti, ti->tmpbuf, i);
 274             else
 275                 isc_pp_close (ispt[i]);
 276         }
 277         while (ti->heapnum)
 278         {
 279             int n = ti->indx[ti->ptr[1]];
 280
 281             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 282             if (preserve_position)
 283             {
 284                 heap_delete (ti);
 285                 if (isc_pp_read (ispt[n], ti->tmpbuf))
 286                     heap_insert (ti, ti->tmpbuf, n);
 287                 else
 288                     isc_pp_close (ispt[n]);
 289             }
 290             else
 291             {
 292                 while (1)
 293                 {
 294                     if (!isc_pp_read (ispt[n], ti->tmpbuf))
 295                     {
 296                         heap_delete (ti);
 297                         isc_pp_close (ispt[n]);
 298                         break;
 299                     }
 300                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 301                     {
 302                         heap_delete (ti);
 303                         heap_insert (ti, ti->tmpbuf, n);
 304                         break;
 305                     }
 306                 }
 307             }
 308         }
 309         heap_close (ti);
 310         xfree (ispt);
 311     }
 312
 313     else if (zi->reg->isamd)
 314     {
 315         ISAMD_PP *ispt;
 316         int i;
 317         struct trunc_info *ti;
 318
 319         ispt = (ISAMD_PP *) xmalloc (sizeof(*ispt) * (to-from));
 320
 321         ti = heap_init (to-from, sizeof(struct it_key),
 322                         key_compare_it);
 323         for (i = to-from; --i >= 0; )
 324         {
 325             logf(LOG_FATAL, "isam_d does not (currently) support truncs");
 326             abort();
 327             /*ispt[i] = isamd_pp_open (zi->reg->isamd, isam_p[from+i]); */
 328             if (isamd_pp_read (ispt[i], ti->tmpbuf))
 329                 heap_insert (ti, ti->tmpbuf, i);
 330             else
 331                 isamd_pp_close (ispt[i]);
 332         }
 333         while (ti->heapnum)
 334         {
 335             int n = ti->indx[ti->ptr[1]];
 336
 337             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 338 #if 0
 339 /* section that preserve all keys */
 340             heap_delete (ti);
 341             if (isamd_pp_read (ispt[n], ti->tmpbuf))
 342                 heap_insert (ti, ti->tmpbuf, n);
 343             else
 344                 isamd_pp_close (ispt[n]);
 345 #else
 346 /* section that preserve all keys with unique sysnos */
 347             while (1)
 348             {
 349                 if (!isamd_pp_read (ispt[n], ti->tmpbuf))
 350                 {
 351                     heap_delete (ti);
 352                     isamd_pp_close (ispt[n]);
 353                     break;
 354                 }
 355                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 356                 {
 357                     heap_delete (ti);
 358                     heap_insert (ti, ti->tmpbuf, n);
 359                     break;
 360                 }
 361             }
 362 #endif
 363         }
 364         heap_close (ti);
 365         xfree (ispt);
 366     }
 367     else if (zi->reg->isams)
 368     {
 369         ISAMS_PP *ispt;
 370         int i;
 371         struct trunc_info *ti;
 372
 373         ispt = (ISAMS_PP *) xmalloc (sizeof(*ispt) * (to-from));
 374
 375         ti = heap_init (to-from, sizeof(struct it_key),
 376                         key_compare_it);
 377         for (i = to-from; --i >= 0; )
 378         {
 379             ispt[i] = isams_pp_open (zi->reg->isams, isam_p[from+i]);
 380             if (isams_pp_read (ispt[i], ti->tmpbuf))
 381                 heap_insert (ti, ti->tmpbuf, i);
 382             else
 383                 isams_pp_close (ispt[i]);
 384         }
 385         while (ti->heapnum)
 386         {
 387             int n = ti->indx[ti->ptr[1]];
 388
 389             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 390             while (1)
 391             {
 392                 if (!isams_pp_read (ispt[n], ti->tmpbuf))
 393                 {
 394                     heap_delete (ti);
 395                     isams_pp_close (ispt[n]);
 396                     break;
 397                 }
 398                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 399                 {
 400                     heap_delete (ti);
 401                     heap_insert (ti, ti->tmpbuf, n);
 402                     break;
 403                 }
 404             }
 405         }
 406         heap_close (ti);
 407         xfree (ispt);
 408     }
 409     else if (zi->reg->isamb)
 410     {
 411         ISAMB_PP *ispt;
 412         int i;
 413         struct trunc_info *ti;
 414
 415         ispt = (ISAMB_PP *) xmalloc (sizeof(*ispt) * (to-from));
 416
 417         ti = heap_init (to-from, sizeof(struct it_key),
 418                         key_compare_it);
 419         for (i = to-from; --i >= 0; )
 420         {
 421             ispt[i] = isamb_pp_open (zi->reg->isamb, isam_p[from+i]);
 422             if (isamb_pp_read (ispt[i], ti->tmpbuf))
 423                 heap_insert (ti, ti->tmpbuf, i);
 424             else
 425                 isamb_pp_close (ispt[i]);
 426         }
 427         while (ti->heapnum)
 428         {
 429             int n = ti->indx[ti->ptr[1]];
 430
 431             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 432
 433             if (preserve_position)
 434             {
 435                 heap_delete (ti);
 436                 if (isamb_pp_read (ispt[n], ti->tmpbuf))
 437                     heap_insert (ti, ti->tmpbuf, n);
 438                 else
 439                     isamb_pp_close (ispt[n]);
 440             }
 441             else
 442             {
 443                 while (1)
 444                 {
 445                     if (!isamb_pp_read (ispt[n], ti->tmpbuf))
 446                     {
 447                         heap_delete (ti);
 448                         isamb_pp_close (ispt[n]);
 449                         break;
 450                     }
 451                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 452                     {
 453                         heap_delete (ti);
 454                         heap_insert (ti, ti->tmpbuf, n);
 455                         break;
 456                     }
 457                 }
 458             }
 459         }
 460         heap_close (ti);
 461         xfree (ispt);
 462     }
 463     else
 464         logf (LOG_WARN, "Unknown isam set in rset_trunc_r");
 465
 466     rset_close (result, result_rsfd);
 467     return result;
 468 }
 469
 470 static int isams_trunc_cmp (const void *p1, const void *p2)
 471 {
 472     ISAMS_P i1 = *(ISAMS_P*) p1;
 473     ISAMS_P i2 = *(ISAMS_P*) p2;
 474
 475     return i1 - i2;
 476 }
 477
 478 static int isam_trunc_cmp (const void *p1, const void *p2)
 479 {
 480     ISAM_P i1 = *(ISAM_P*) p1;
 481     ISAM_P i2 = *(ISAM_P*) p2;
 482     int d;
 483
 484     d = is_type (i1) - is_type (i2);
 485     if (d)
 486         return d;
 487     return is_block (i1) - is_block (i2);
 488 }
 489
 490 static int isamc_trunc_cmp (const void *p1, const void *p2)
 491 {
 492     ISAMC_P i1 = *(ISAMC_P*) p1;
 493     ISAMC_P i2 = *(ISAMC_P*) p2;
 494     int d;
 495
 496     d = isc_type (i1) - isc_type (i2);
 497     if (d)
 498         return d;
 499     return isc_block (i1) - isc_block (i2);
 500 }
 501 static int isamd_trunc_cmp (const void *p1, const void *p2)
 502 {
 503     ISAMD_P i1 = *(ISAMD_P*) p1;
 504     ISAMD_P i2 = *(ISAMD_P*) p2;
 505     int d;
 506
 507     d = isamd_type (i1) - isamd_type (i2);
 508     if (d)
 509         return d;
 510     return isamd_block (i1) - isamd_block (i2);
 511 }
 512
 513 RSET rset_trunc (ZebraHandle zi, ISAMS_P *isam_p, int no,
 514                  const char *term, int length, const char *flags,
 515                  int preserve_position, int term_type)
 516 {
 517     logf (LOG_DEBUG, "rset_trunc no=%d", no);
 518     if (no < 1)
 519     {
 520         rset_null_parms parms;
 521         parms.rset_term = rset_term_create (term, length, flags, term_type);
 522         return rset_create (rset_kind_null, &parms);
 523     }
 524     if (zi->reg->isams)
 525     {
 526         if (no == 1)
 527         {
 528             rset_isams_parms parms;
 529
 530             parms.pos = *isam_p;
 531             parms.is = zi->reg->isams;
 532             parms.rset_term = rset_term_create (term, length, flags,
 533                                                 term_type);
 534             return rset_create (rset_kind_isams, &parms);
 535         }
 536         qsort (isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
 537     }
 538     else if (zi->reg->isam)
 539     {
 540         if (no == 1)
 541         {
 542             rset_isam_parms parms;
 543
 544             parms.pos = *isam_p;
 545             parms.is = zi->reg->isam;
 546             parms.rset_term = rset_term_create (term, length, flags,
 547                                                 term_type);
 548             return rset_create (rset_kind_isam, &parms);
 549         }
 550         qsort (isam_p, no, sizeof(*isam_p), isam_trunc_cmp);
 551     }
 552     else if (zi->reg->isamc)
 553     {
 554         if (no == 1)
 555         {
 556             rset_isamc_parms parms;
 557
 558             parms.key_size = sizeof(struct it_key);
 559             parms.cmp = key_compare_it;
 560             parms.pos = *isam_p;
 561             parms.is = zi->reg->isamc;
 562             parms.rset_term = rset_term_create (term, length, flags,
 563                                                 term_type);
 564             return rset_create (rset_kind_isamc, &parms);
 565         }
 566 #if NEW_TRUNC
 567         else if (no < 10000)
 568         {
 569             rset_m_or_parms parms;
 570
 571             parms.key_size = sizeof(struct it_key);
 572             parms.cmp = key_compare_it;
 573             parms.isc = zi->reg->isamc;
 574             parms.isam_positions = isam_p;
 575             parms.no_isam_positions = no;
 576             parms.no_save_positions = 100000;
 577             parms.rset_term = rset_term_create (term, length, flags,
 578                                                 term_type);
 579             return rset_create (rset_kind_m_or, &parms);
 580         }
 581 #endif
 582         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 583     }
 584     else if (zi->reg->isamd)
 585     {
 586         if (no == 1)
 587         {
 588             rset_isamd_parms parms;
 589
 590             logf(LOG_FATAL, "isam_d does not (currently) support truncs");
 591             abort();
 592             /* parms.pos = *isam_p; */
 593             parms.is = zi->reg->isamd;
 594             parms.rset_term = rset_term_create (term, length, flags,
 595                                                 term_type);
 596             return rset_create (rset_kind_isamd, &parms);
 597         }
 598 #if NEW_TRUNC_NOT_DONE_FOR_ISAM_D
 599         else if (no < 10000)
 600         {
 601             rset_m_or_parms parms;
 602
 603             parms.key_size = sizeof(struct it_key);
 604             parms.cmp = key_compare_it;
 605             parms.isc = 0;
 606             parms.isamd=zi->reg->isamd;
 607             parms.isam_positions = isam_p;
 608             parms.no_isam_positions = no;
 609             parms.no_save_positions = 100000;
 610             parms.rset_term = rset_term_create (term, length, flags);
 611             return rset_create (rset_kind_m_or, &parms);
 612         }
 613 #endif
 614         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
 615     }
 616     else if (zi->reg->isamb)
 617     {
 618         if (no == 1)
 619         {
 620             rset_isamb_parms parms;
 621
 622             parms.key_size = sizeof(struct it_key);
 623             parms.cmp = key_compare_it;
 624             parms.pos = *isam_p;
 625             parms.is = zi->reg->isamb;
 626             parms.rset_term = rset_term_create (term, length, flags,
 627                                                 term_type);
 628             return rset_create (rset_kind_isamb, &parms);
 629         }
 630         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
 631     }
 632     else
 633     {
 634         logf (LOG_WARN, "Unknown isam set in rset_trunc");
 635         return rset_create (rset_kind_null, NULL);
 636     }
 637     return rset_trunc_r (zi, term, length, flags, isam_p, 0, no, 100,
 638                          preserve_position, term_type);
 639 }
 640