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.24 2002-04-16 22:31:42 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 {
 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             ispt[i] = isamd_pp_open (zi->reg->isamd, isam_p[from+i]);
 323             if (isamd_pp_read (ispt[i], ti->tmpbuf))
 324                 heap_insert (ti, ti->tmpbuf, i);
 325             else
 326                 isamd_pp_close (ispt[i]);
 327         }
 328         while (ti->heapnum)
 329         {
 330             int n = ti->indx[ti->ptr[1]];
 331
 332             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 333 #if 0
 334 /* section that preserve all keys */
 335             heap_delete (ti);
 336             if (isamd_pp_read (ispt[n], ti->tmpbuf))
 337                 heap_insert (ti, ti->tmpbuf, n);
 338             else
 339                 isamd_pp_close (ispt[n]);
 340 #else
 341 /* section that preserve all keys with unique sysnos */
 342             while (1)
 343             {
 344                 if (!isamd_pp_read (ispt[n], ti->tmpbuf))
 345                 {
 346                     heap_delete (ti);
 347                     isamd_pp_close (ispt[n]);
 348                     break;
 349                 }
 350                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 351                 {
 352                     heap_delete (ti);
 353                     heap_insert (ti, ti->tmpbuf, n);
 354                     break;
 355                 }
 356             }
 357 #endif
 358         }
 359         heap_close (ti);
 360         xfree (ispt);
 361     }
 362     else if (zi->reg->isams)
 363     {
 364         ISAMS_PP *ispt;
 365         int i;
 366         struct trunc_info *ti;
 367
 368         ispt = (ISAMS_PP *) xmalloc (sizeof(*ispt) * (to-from));
 369
 370         ti = heap_init (to-from, sizeof(struct it_key),
 371                         key_compare_it);
 372         for (i = to-from; --i >= 0; )
 373         {
 374             ispt[i] = isams_pp_open (zi->reg->isams, isam_p[from+i]);
 375             if (isams_pp_read (ispt[i], ti->tmpbuf))
 376                 heap_insert (ti, ti->tmpbuf, i);
 377             else
 378                 isams_pp_close (ispt[i]);
 379         }
 380         while (ti->heapnum)
 381         {
 382             int n = ti->indx[ti->ptr[1]];
 383
 384             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 385             while (1)
 386             {
 387                 if (!isams_pp_read (ispt[n], ti->tmpbuf))
 388                 {
 389                     heap_delete (ti);
 390                     isams_pp_close (ispt[n]);
 391                     break;
 392                 }
 393                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 394                 {
 395                     heap_delete (ti);
 396                     heap_insert (ti, ti->tmpbuf, n);
 397                     break;
 398                 }
 399             }
 400         }
 401         heap_close (ti);
 402         xfree (ispt);
 403     }
 404     else if (zi->reg->isamb)
 405     {
 406         ISAMB_PP *ispt;
 407         int i;
 408         struct trunc_info *ti;
 409
 410         ispt = (ISAMB_PP *) xmalloc (sizeof(*ispt) * (to-from));
 411
 412         ti = heap_init (to-from, sizeof(struct it_key),
 413                         key_compare_it);
 414         for (i = to-from; --i >= 0; )
 415         {
 416             ispt[i] = isamb_pp_open (zi->reg->isamb, isam_p[from+i]);
 417             if (isamb_pp_read (ispt[i], ti->tmpbuf))
 418                 heap_insert (ti, ti->tmpbuf, i);
 419             else
 420                 isamb_pp_close (ispt[i]);
 421         }
 422         while (ti->heapnum)
 423         {
 424             int n = ti->indx[ti->ptr[1]];
 425
 426             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 427
 428             if (preserve_position)
 429             {
 430                 heap_delete (ti);
 431                 if (isamb_pp_read (ispt[n], ti->tmpbuf))
 432                     heap_insert (ti, ti->tmpbuf, n);
 433                 else
 434                     isamb_pp_close (ispt[n]);
 435             }
 436             else
 437             {
 438                 while (1)
 439                 {
 440                     if (!isamb_pp_read (ispt[n], ti->tmpbuf))
 441                     {
 442                         heap_delete (ti);
 443                         isamb_pp_close (ispt[n]);
 444                         break;
 445                     }
 446                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 447                     {
 448                         heap_delete (ti);
 449                         heap_insert (ti, ti->tmpbuf, n);
 450                         break;
 451                     }
 452                 }
 453             }
 454         }
 455         heap_close (ti);
 456         xfree (ispt);
 457     }
 458     else
 459         logf (LOG_WARN, "Unknown isam set in rset_trunc_r");
 460
 461     rset_close (result, result_rsfd);
 462     return result;
 463 }
 464
 465 static int isams_trunc_cmp (const void *p1, const void *p2)
 466 {
 467     ISAMS_P i1 = *(ISAMS_P*) p1;
 468     ISAMS_P i2 = *(ISAMS_P*) p2;
 469
 470     return i1 - i2;
 471 }
 472
 473 static int isam_trunc_cmp (const void *p1, const void *p2)
 474 {
 475     ISAM_P i1 = *(ISAM_P*) p1;
 476     ISAM_P i2 = *(ISAM_P*) p2;
 477     int d;
 478
 479     d = is_type (i1) - is_type (i2);
 480     if (d)
 481         return d;
 482     return is_block (i1) - is_block (i2);
 483 }
 484
 485 static int isamc_trunc_cmp (const void *p1, const void *p2)
 486 {
 487     ISAMC_P i1 = *(ISAMC_P*) p1;
 488     ISAMC_P i2 = *(ISAMC_P*) p2;
 489     int d;
 490
 491     d = isc_type (i1) - isc_type (i2);
 492     if (d)
 493         return d;
 494     return isc_block (i1) - isc_block (i2);
 495 }
 496 static int isamd_trunc_cmp (const void *p1, const void *p2)
 497 {
 498     ISAMD_P i1 = *(ISAMD_P*) p1;
 499     ISAMD_P i2 = *(ISAMD_P*) p2;
 500     int d;
 501
 502     d = isamd_type (i1) - isamd_type (i2);
 503     if (d)
 504         return d;
 505     return isamd_block (i1) - isamd_block (i2);
 506 }
 507
 508 RSET rset_trunc (ZebraHandle zi, ISAMS_P *isam_p, int no,
 509                  const char *term, int length, const char *flags,
 510                  int preserve_position)
 511 {
 512     logf (LOG_DEBUG, "rset_trunc no=%d", no);
 513     if (no < 1)
 514     {
 515         rset_null_parms parms;
 516         parms.rset_term = rset_term_create (term, length, flags);
 517         return rset_create (rset_kind_null, &parms);
 518     }
 519     if (zi->reg->isams)
 520     {
 521         if (no == 1)
 522         {
 523             rset_isams_parms parms;
 524
 525             parms.pos = *isam_p;
 526             parms.is = zi->reg->isams;
 527             parms.rset_term = rset_term_create (term, length, flags);
 528             return rset_create (rset_kind_isams, &parms);
 529         }
 530         qsort (isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
 531     }
 532     else if (zi->reg->isam)
 533     {
 534         if (no == 1)
 535         {
 536             rset_isam_parms parms;
 537
 538             parms.pos = *isam_p;
 539             parms.is = zi->reg->isam;
 540             parms.rset_term = rset_term_create (term, length, flags);
 541             return rset_create (rset_kind_isam, &parms);
 542         }
 543         qsort (isam_p, no, sizeof(*isam_p), isam_trunc_cmp);
 544     }
 545     else if (zi->reg->isamc)
 546     {
 547         if (no == 1)
 548         {
 549             rset_isamc_parms parms;
 550
 551             parms.key_size = sizeof(struct it_key);
 552             parms.cmp = key_compare_it;
 553             parms.pos = *isam_p;
 554             parms.is = zi->reg->isamc;
 555             parms.rset_term = rset_term_create (term, length, flags);
 556             return rset_create (rset_kind_isamc, &parms);
 557         }
 558 #if NEW_TRUNC
 559         else if (no < 10000)
 560         {
 561             rset_m_or_parms parms;
 562
 563             parms.key_size = sizeof(struct it_key);
 564             parms.cmp = key_compare_it;
 565             parms.isc = zi->reg->isamc;
 566             parms.isam_positions = isam_p;
 567             parms.no_isam_positions = no;
 568             parms.no_save_positions = 100000;
 569             parms.rset_term = rset_term_create (term, length, flags);
 570             return rset_create (rset_kind_m_or, &parms);
 571         }
 572 #endif
 573         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 574     }
 575     else if (zi->reg->isamd)
 576     {
 577         if (no == 1)
 578         {
 579             rset_isamd_parms parms;
 580
 581             parms.pos = *isam_p;
 582             parms.is = zi->reg->isamd;
 583             parms.rset_term = rset_term_create (term, length, flags);
 584             return rset_create (rset_kind_isamd, &parms);
 585         }
 586 #if NEW_TRUNC_NOT_DONE_FOR_ISAM_D
 587         else if (no < 10000)
 588         {
 589             rset_m_or_parms parms;
 590
 591             parms.key_size = sizeof(struct it_key);
 592             parms.cmp = key_compare_it;
 593             parms.isc = 0;
 594             parms.isamd=zi->reg->isamd;
 595             parms.isam_positions = isam_p;
 596             parms.no_isam_positions = no;
 597             parms.no_save_positions = 100000;
 598             parms.rset_term = rset_term_create (term, length, flags);
 599             return rset_create (rset_kind_m_or, &parms);
 600         }
 601 #endif
 602         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
 603     }
 604     else if (zi->reg->isamb)
 605     {
 606         if (no == 1)
 607         {
 608             rset_isamb_parms parms;
 609
 610             parms.key_size = sizeof(struct it_key);
 611             parms.cmp = key_compare_it;
 612             parms.pos = *isam_p;
 613             parms.is = zi->reg->isamb;
 614             parms.rset_term = rset_term_create (term, length, flags);
 615             return rset_create (rset_kind_isamb, &parms);
 616         }
 617         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
 618     }
 619     else
 620     {
 621         logf (LOG_WARN, "Unknown isam set in rset_trunc");
 622         return rset_create (rset_kind_null, NULL);
 623     }
 624     return rset_trunc_r (zi, term, length, flags, isam_p, 0, no, 100,
 625                          preserve_position);
 626 }
 627