index/trunc.c

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