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.25 2002-07-12 18:12:22 heikki 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 {
 126     RSET result;
 127     RSFD result_rsfd;
 128     rset_temp_parms parms;
 129
 130     parms.cmp = key_compare_it;
 131     parms.key_size = sizeof(struct it_key);
 132     parms.temp_path = res_get (zi->res, "setTmpDir");
 133     parms.rset_term = rset_term_create (term, length, flags);
 134     result = rset_create (rset_kind_temp, &parms);
 135     result_rsfd = rset_open (result, RSETF_WRITE);
 136
 137     if (to - from > merge_chunk)
 138     {
 139         RSFD *rsfd;
 140         RSET *rset;
 141         int term_index;
 142         int i, i_add = (to-from)/merge_chunk + 1;
 143         struct trunc_info *ti;
 144         int rscur = 0;
 145         int rsmax = (to-from)/i_add + 1;
 146
 147         rset = (RSET *) xmalloc (sizeof(*rset) * rsmax);
 148         rsfd = (RSFD *) xmalloc (sizeof(*rsfd) * rsmax);
 149
 150         for (i = from; i < to; i += i_add)
 151         {
 152             if (i_add <= to - i)
 153                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
 154                                             isam_p, i, i+i_add,
 155                                             merge_chunk, preserve_position);
 156             else
 157                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
 158                                             isam_p, i, to,
 159                                             merge_chunk, preserve_position);
 160             rscur++;
 161         }
 162         ti = heap_init (rscur, sizeof(struct it_key), key_compare_it);
 163         for (i = rscur; --i >= 0; )
 164         {
 165             rsfd[i] = rset_open (rset[i], RSETF_READ);
 166             if (rset_read (rset[i], rsfd[i], ti->tmpbuf, &term_index))
 167                 heap_insert (ti, ti->tmpbuf, i);
 168             else
 169             {
 170                 rset_close (rset[i], rsfd[i]);
 171                 rset_delete (rset[i]);
 172             }
 173         }
 174         while (ti->heapnum)
 175         {
 176             int n = ti->indx[ti->ptr[1]];
 177
 178             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 179
 180             while (1)
 181             {
 182                 if (!rset_read (rset[n], rsfd[n], ti->tmpbuf, &term_index))
 183                 {
 184                     heap_delete (ti);
 185                     rset_close (rset[n], rsfd[n]);
 186                     rset_delete (rset[n]);
 187                     break;
 188                 }
 189                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 190                 {
 191                     heap_delete (ti);
 192                     heap_insert (ti, ti->tmpbuf, n);
 193                     break;
 194                 }
 195             }
 196         }
 197         xfree (rset);
 198         xfree (rsfd);
 199         heap_close (ti);
 200     }
 201     else if (zi->reg->isam)
 202     {
 203         ISPT *ispt;
 204         int i;
 205         struct trunc_info *ti;
 206
 207         ispt = (ISPT *) xmalloc (sizeof(*ispt) * (to-from));
 208
 209         ti = heap_init (to-from, sizeof(struct it_key),
 210                         key_compare_it);
 211         for (i = to-from; --i >= 0; )
 212         {
 213             ispt[i] = is_position (zi->reg->isam, isam_p[from+i]);
 214             if (is_readkey (ispt[i], ti->tmpbuf))
 215                 heap_insert (ti, ti->tmpbuf, i);
 216             else
 217                 is_pt_free (ispt[i]);
 218         }
 219         while (ti->heapnum)
 220         {
 221             int n = ti->indx[ti->ptr[1]];
 222
 223             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 224             if (preserve_position)
 225             {
 226 /* section that preserve all keys */
 227                 heap_delete (ti);
 228                 if (is_readkey (ispt[n], ti->tmpbuf))
 229                     heap_insert (ti, ti->tmpbuf, n);
 230                 else
 231                     is_pt_free (ispt[n]);
 232             }
 233             else
 234             {
 235 /* section that preserve all keys with unique sysnos */
 236                 while (1)
 237                 {
 238                     if (!is_readkey (ispt[n], ti->tmpbuf))
 239                     {
 240                         heap_delete (ti);
 241                         is_pt_free (ispt[n]);
 242                         break;
 243                     }
 244                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 245                     {
 246                         heap_delete (ti);
 247                         heap_insert (ti, ti->tmpbuf, n);
 248                         break;
 249                     }
 250                 }
 251             }
 252         }
 253         heap_close (ti);
 254         xfree (ispt);
 255     }
 256     else if (zi->reg->isamc)
 257     {
 258         ISAMC_PP *ispt;
 259         int i;
 260         struct trunc_info *ti;
 261
 262         ispt = (ISAMC_PP *) xmalloc (sizeof(*ispt) * (to-from));
 263
 264         ti = heap_init (to-from, sizeof(struct it_key),
 265                         key_compare_it);
 266         for (i = to-from; --i >= 0; )
 267         {
 268             ispt[i] = isc_pp_open (zi->reg->isamc, isam_p[from+i]);
 269             if (isc_pp_read (ispt[i], ti->tmpbuf))
 270                 heap_insert (ti, ti->tmpbuf, i);
 271             else
 272                 isc_pp_close (ispt[i]);
 273         }
 274         while (ti->heapnum)
 275         {
 276             int n = ti->indx[ti->ptr[1]];
 277
 278             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 279             if (preserve_position)
 280             {
 281                 heap_delete (ti);
 282                 if (isc_pp_read (ispt[n], ti->tmpbuf))
 283                     heap_insert (ti, ti->tmpbuf, n);
 284                 else
 285                     isc_pp_close (ispt[n]);
 286             }
 287             else
 288             {
 289                 while (1)
 290                 {
 291                     if (!isc_pp_read (ispt[n], ti->tmpbuf))
 292                     {
 293                         heap_delete (ti);
 294                         isc_pp_close (ispt[n]);
 295                         break;
 296                     }
 297                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 298                     {
 299                         heap_delete (ti);
 300                         heap_insert (ti, ti->tmpbuf, n);
 301                         break;
 302                     }
 303                 }
 304             }
 305         }
 306         heap_close (ti);
 307         xfree (ispt);
 308     }
 309
 310     else if (zi->reg->isamd)
 311     {
 312         ISAMD_PP *ispt;
 313         int i;
 314         struct trunc_info *ti;
 315
 316         ispt = (ISAMD_PP *) xmalloc (sizeof(*ispt) * (to-from));
 317
 318         ti = heap_init (to-from, sizeof(struct it_key),
 319                         key_compare_it);
 320         for (i = to-from; --i >= 0; )
 321         {
 322             logf(LOG_FATAL, "isam_d does not (currently) support truncs");
 323             abort();
 324             /*ispt[i] = isamd_pp_open (zi->reg->isamd, isam_p[from+i]); */
 325             if (isamd_pp_read (ispt[i], ti->tmpbuf))
 326                 heap_insert (ti, ti->tmpbuf, i);
 327             else
 328                 isamd_pp_close (ispt[i]);
 329         }
 330         while (ti->heapnum)
 331         {
 332             int n = ti->indx[ti->ptr[1]];
 333
 334             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 335 #if 0
 336 /* section that preserve all keys */
 337             heap_delete (ti);
 338             if (isamd_pp_read (ispt[n], ti->tmpbuf))
 339                 heap_insert (ti, ti->tmpbuf, n);
 340             else
 341                 isamd_pp_close (ispt[n]);
 342 #else
 343 /* section that preserve all keys with unique sysnos */
 344             while (1)
 345             {
 346                 if (!isamd_pp_read (ispt[n], ti->tmpbuf))
 347                 {
 348                     heap_delete (ti);
 349                     isamd_pp_close (ispt[n]);
 350                     break;
 351                 }
 352                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 353                 {
 354                     heap_delete (ti);
 355                     heap_insert (ti, ti->tmpbuf, n);
 356                     break;
 357                 }
 358             }
 359 #endif
 360         }
 361         heap_close (ti);
 362         xfree (ispt);
 363     }
 364     else if (zi->reg->isams)
 365     {
 366         ISAMS_PP *ispt;
 367         int i;
 368         struct trunc_info *ti;
 369
 370         ispt = (ISAMS_PP *) xmalloc (sizeof(*ispt) * (to-from));
 371
 372         ti = heap_init (to-from, sizeof(struct it_key),
 373                         key_compare_it);
 374         for (i = to-from; --i >= 0; )
 375         {
 376             ispt[i] = isams_pp_open (zi->reg->isams, isam_p[from+i]);
 377             if (isams_pp_read (ispt[i], ti->tmpbuf))
 378                 heap_insert (ti, ti->tmpbuf, i);
 379             else
 380                 isams_pp_close (ispt[i]);
 381         }
 382         while (ti->heapnum)
 383         {
 384             int n = ti->indx[ti->ptr[1]];
 385
 386             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 387             while (1)
 388             {
 389                 if (!isams_pp_read (ispt[n], ti->tmpbuf))
 390                 {
 391                     heap_delete (ti);
 392                     isams_pp_close (ispt[n]);
 393                     break;
 394                 }
 395                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 396                 {
 397                     heap_delete (ti);
 398                     heap_insert (ti, ti->tmpbuf, n);
 399                     break;
 400                 }
 401             }
 402         }
 403         heap_close (ti);
 404         xfree (ispt);
 405     }
 406     else if (zi->reg->isamb)
 407     {
 408         ISAMB_PP *ispt;
 409         int i;
 410         struct trunc_info *ti;
 411
 412         ispt = (ISAMB_PP *) xmalloc (sizeof(*ispt) * (to-from));
 413
 414         ti = heap_init (to-from, sizeof(struct it_key),
 415                         key_compare_it);
 416         for (i = to-from; --i >= 0; )
 417         {
 418             ispt[i] = isamb_pp_open (zi->reg->isamb, isam_p[from+i]);
 419             if (isamb_pp_read (ispt[i], ti->tmpbuf))
 420                 heap_insert (ti, ti->tmpbuf, i);
 421             else
 422                 isamb_pp_close (ispt[i]);
 423         }
 424         while (ti->heapnum)
 425         {
 426             int n = ti->indx[ti->ptr[1]];
 427
 428             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 429
 430             if (preserve_position)
 431             {
 432                 heap_delete (ti);
 433                 if (isamb_pp_read (ispt[n], ti->tmpbuf))
 434                     heap_insert (ti, ti->tmpbuf, n);
 435                 else
 436                     isamb_pp_close (ispt[n]);
 437             }
 438             else
 439             {
 440                 while (1)
 441                 {
 442                     if (!isamb_pp_read (ispt[n], ti->tmpbuf))
 443                     {
 444                         heap_delete (ti);
 445                         isamb_pp_close (ispt[n]);
 446                         break;
 447                     }
 448                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 449                     {
 450                         heap_delete (ti);
 451                         heap_insert (ti, ti->tmpbuf, n);
 452                         break;
 453                     }
 454                 }
 455             }
 456         }
 457         heap_close (ti);
 458         xfree (ispt);
 459     }
 460     else
 461         logf (LOG_WARN, "Unknown isam set in rset_trunc_r");
 462
 463     rset_close (result, result_rsfd);
 464     return result;
 465 }
 466
 467 static int isams_trunc_cmp (const void *p1, const void *p2)
 468 {
 469     ISAMS_P i1 = *(ISAMS_P*) p1;
 470     ISAMS_P i2 = *(ISAMS_P*) p2;
 471
 472     return i1 - i2;
 473 }
 474
 475 static int isam_trunc_cmp (const void *p1, const void *p2)
 476 {
 477     ISAM_P i1 = *(ISAM_P*) p1;
 478     ISAM_P i2 = *(ISAM_P*) p2;
 479     int d;
 480
 481     d = is_type (i1) - is_type (i2);
 482     if (d)
 483         return d;
 484     return is_block (i1) - is_block (i2);
 485 }
 486
 487 static int isamc_trunc_cmp (const void *p1, const void *p2)
 488 {
 489     ISAMC_P i1 = *(ISAMC_P*) p1;
 490     ISAMC_P i2 = *(ISAMC_P*) p2;
 491     int d;
 492
 493     d = isc_type (i1) - isc_type (i2);
 494     if (d)
 495         return d;
 496     return isc_block (i1) - isc_block (i2);
 497 }
 498 static int isamd_trunc_cmp (const void *p1, const void *p2)
 499 {
 500     ISAMD_P i1 = *(ISAMD_P*) p1;
 501     ISAMD_P i2 = *(ISAMD_P*) p2;
 502     int d;
 503
 504     d = isamd_type (i1) - isamd_type (i2);
 505     if (d)
 506         return d;
 507     return isamd_block (i1) - isamd_block (i2);
 508 }
 509
 510 RSET rset_trunc (ZebraHandle zi, ISAMS_P *isam_p, int no,
 511                  const char *term, int length, const char *flags,
 512                  int preserve_position)
 513 {
 514     logf (LOG_DEBUG, "rset_trunc no=%d", no);
 515     if (no < 1)
 516     {
 517         rset_null_parms parms;
 518         parms.rset_term = rset_term_create (term, length, flags);
 519         return rset_create (rset_kind_null, &parms);
 520     }
 521     if (zi->reg->isams)
 522     {
 523         if (no == 1)
 524         {
 525             rset_isams_parms parms;
 526
 527             parms.pos = *isam_p;
 528             parms.is = zi->reg->isams;
 529             parms.rset_term = rset_term_create (term, length, flags);
 530             return rset_create (rset_kind_isams, &parms);
 531         }
 532         qsort (isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
 533     }
 534     else if (zi->reg->isam)
 535     {
 536         if (no == 1)
 537         {
 538             rset_isam_parms parms;
 539
 540             parms.pos = *isam_p;
 541             parms.is = zi->reg->isam;
 542             parms.rset_term = rset_term_create (term, length, flags);
 543             return rset_create (rset_kind_isam, &parms);
 544         }
 545         qsort (isam_p, no, sizeof(*isam_p), isam_trunc_cmp);
 546     }
 547     else if (zi->reg->isamc)
 548     {
 549         if (no == 1)
 550         {
 551             rset_isamc_parms parms;
 552
 553             parms.key_size = sizeof(struct it_key);
 554             parms.cmp = key_compare_it;
 555             parms.pos = *isam_p;
 556             parms.is = zi->reg->isamc;
 557             parms.rset_term = rset_term_create (term, length, flags);
 558             return rset_create (rset_kind_isamc, &parms);
 559         }
 560 #if NEW_TRUNC
 561         else if (no < 10000)
 562         {
 563             rset_m_or_parms parms;
 564
 565             parms.key_size = sizeof(struct it_key);
 566             parms.cmp = key_compare_it;
 567             parms.isc = zi->reg->isamc;
 568             parms.isam_positions = isam_p;
 569             parms.no_isam_positions = no;
 570             parms.no_save_positions = 100000;
 571             parms.rset_term = rset_term_create (term, length, flags);
 572             return rset_create (rset_kind_m_or, &parms);
 573         }
 574 #endif
 575         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 576     }
 577     else if (zi->reg->isamd)
 578     {
 579         if (no == 1)
 580         {
 581             rset_isamd_parms parms;
 582
 583             logf(LOG_FATAL, "isam_d does not (currently) support truncs");
 584             abort();
 585             /* parms.pos = *isam_p; */
 586             parms.is = zi->reg->isamd;
 587             parms.rset_term = rset_term_create (term, length, flags);
 588             return rset_create (rset_kind_isamd, &parms);
 589         }
 590 #if NEW_TRUNC_NOT_DONE_FOR_ISAM_D
 591         else if (no < 10000)
 592         {
 593             rset_m_or_parms parms;
 594
 595             parms.key_size = sizeof(struct it_key);
 596             parms.cmp = key_compare_it;
 597             parms.isc = 0;
 598             parms.isamd=zi->reg->isamd;
 599             parms.isam_positions = isam_p;
 600             parms.no_isam_positions = no;
 601             parms.no_save_positions = 100000;
 602             parms.rset_term = rset_term_create (term, length, flags);
 603             return rset_create (rset_kind_m_or, &parms);
 604         }
 605 #endif
 606         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
 607     }
 608     else if (zi->reg->isamb)
 609     {
 610         if (no == 1)
 611         {
 612             rset_isamb_parms parms;
 613
 614             parms.key_size = sizeof(struct it_key);
 615             parms.cmp = key_compare_it;
 616             parms.pos = *isam_p;
 617             parms.is = zi->reg->isamb;
 618             parms.rset_term = rset_term_create (term, length, flags);
 619             return rset_create (rset_kind_isamb, &parms);
 620         }
 621         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
 622     }
 623     else
 624     {
 625         logf (LOG_WARN, "Unknown isam set in rset_trunc");
 626         return rset_create (rset_kind_null, NULL);
 627     }
 628     return rset_trunc_r (zi, term, length, flags, isam_p, 0, no, 100,
 629                          preserve_position);
 630 }
 631