index/trunc.c

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