index/trunc.c

   1 /* $Id: trunc.c,v 1.33 2004-08-11 13:35:04 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
   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 <rsisamc.h>
  34 #include <rsisamb.h>
  35 #if NEW_TRUNC
  36 #include <rsm_or.h>
  37 #endif
  38
  39 struct trunc_info {
  40     int  *ptr;
  41     int  *indx;
  42     char **heap;
  43     int  heapnum;
  44     int  (*cmp)(const void *p1, const void *p2);
  45     int  keysize;
  46     char *swapbuf;
  47     char *tmpbuf;
  48     char *buf;
  49 };
  50
  51 static void heap_swap (struct trunc_info *ti, int i1, int i2)
  52 {
  53     int swap;
  54
  55     swap = ti->ptr[i1];
  56     ti->ptr[i1] = ti->ptr[i2];
  57     ti->ptr[i2] = swap;
  58 }
  59
  60 static void heap_delete (struct trunc_info *ti)
  61 {
  62     int cur = 1, child = 2;
  63
  64     heap_swap (ti, 1, ti->heapnum--);
  65     while (child <= ti->heapnum) {
  66         if (child < ti->heapnum &&
  67             (*ti->cmp)(ti->heap[ti->ptr[child]],
  68                        ti->heap[ti->ptr[1+child]]) > 0)
  69             child++;
  70         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
  71                        ti->heap[ti->ptr[child]]) > 0)
  72         {
  73             heap_swap (ti, cur, child);
  74             cur = child;
  75             child = 2*cur;
  76         }
  77         else
  78             break;
  79     }
  80 }
  81
  82 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
  83 {
  84     int cur, parent;
  85
  86     cur = ++(ti->heapnum);
  87     memcpy (ti->heap[ti->ptr[cur]], buf, ti->keysize);
  88     ti->indx[ti->ptr[cur]] = indx;
  89     parent = cur/2;
  90     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
  91                                 ti->heap[ti->ptr[cur]]) > 0)
  92     {
  93         heap_swap (ti, cur, parent);
  94         cur = parent;
  95         parent = cur/2;
  96     }
  97 }
  98
  99 static struct trunc_info *heap_init (int size, int key_size,
 100                                      int (*cmp)(const void *p1,
 101                                                 const void *p2))
 102 {
 103     struct trunc_info *ti = (struct trunc_info *) xmalloc (sizeof(*ti));
 104     int i;
 105
 106     ++size;
 107     ti->heapnum = 0;
 108     ti->keysize = key_size;
 109     ti->cmp = cmp;
 110     ti->indx = (int *) xmalloc (size * sizeof(*ti->indx));
 111     ti->heap = (char **) xmalloc (size * sizeof(*ti->heap));
 112     ti->ptr = (int *) xmalloc (size * sizeof(*ti->ptr));
 113     ti->swapbuf = (char *) xmalloc (ti->keysize);
 114     ti->tmpbuf = (char *) xmalloc (ti->keysize);
 115     ti->buf = (char *) xmalloc (size * ti->keysize);
 116     for (i = size; --i >= 0; )
 117     {
 118         ti->ptr[i] = i;
 119         ti->heap[i] = ti->buf + ti->keysize * i;
 120     }
 121     return ti;
 122 }
 123
 124 static void heap_close (struct trunc_info *ti)
 125 {
 126     xfree (ti->ptr);
 127     xfree (ti->indx);
 128     xfree (ti->heap);
 129     xfree (ti->swapbuf);
 130     xfree (ti->tmpbuf);
 131     xfree (ti->buf);
 132     xfree (ti);
 133 }
 134
 135 static RSET rset_trunc_r (ZebraHandle zi, const char *term, int length,
 136                           const char *flags, ISAMS_P *isam_p, int from, int to,
 137                           int merge_chunk, int preserve_position,
 138                           int term_type)
 139 {
 140     RSET result;
 141     RSFD result_rsfd;
 142     rset_temp_parms parms;
 143     int nn = 0;
 144
 145     parms.cmp = key_compare_it;
 146     parms.key_size = sizeof(struct it_key);
 147     parms.temp_path = res_get (zi->res, "setTmpDir");
 148     parms.rset_term = rset_term_create (term, length, flags, term_type);
 149     result = rset_create (rset_kind_temp, &parms);
 150     result_rsfd = rset_open (result, RSETF_WRITE);
 151
 152     if (to - from > merge_chunk)
 153     {
 154         RSFD *rsfd;
 155         RSET *rset;
 156         int term_index;
 157         int i, i_add = (to-from)/merge_chunk + 1;
 158         struct trunc_info *ti;
 159         int rscur = 0;
 160         int rsmax = (to-from)/i_add + 1;
 161
 162         rset = (RSET *) xmalloc (sizeof(*rset) * rsmax);
 163         rsfd = (RSFD *) xmalloc (sizeof(*rsfd) * rsmax);
 164
 165         for (i = from; i < to; i += i_add)
 166         {
 167             if (i_add <= to - i)
 168                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
 169                                             isam_p, i, i+i_add,
 170                                             merge_chunk, preserve_position,
 171                                             term_type);
 172             else
 173                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
 174                                             isam_p, i, to,
 175                                             merge_chunk, preserve_position,
 176                                             term_type);
 177             rscur++;
 178         }
 179         ti = heap_init (rscur, sizeof(struct it_key), key_compare_it);
 180         for (i = rscur; --i >= 0; )
 181         {
 182             rsfd[i] = rset_open (rset[i], RSETF_READ);
 183             if (rset_read (rset[i], rsfd[i], ti->tmpbuf, &term_index))
 184                 heap_insert (ti, ti->tmpbuf, i);
 185             else
 186             {
 187                 rset_close (rset[i], rsfd[i]);
 188                 rset_delete (rset[i]);
 189             }
 190         }
 191         while (ti->heapnum)
 192         {
 193             int n = ti->indx[ti->ptr[1]];
 194
 195             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 196             nn++;
 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->isamc)
 220     {
 221         ISAMC_PP *ispt;
 222         int i;
 223         struct trunc_info *ti;
 224
 225         ispt = (ISAMC_PP *) 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] = isc_pp_open (zi->reg->isamc, isam_p[from+i]);
 232             if (isc_pp_read (ispt[i], ti->tmpbuf))
 233                 heap_insert (ti, ti->tmpbuf, i);
 234             else
 235                 isc_pp_close (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             nn++;
 243             if (preserve_position)
 244             {
 245                 heap_delete (ti);
 246                 if (isc_pp_read (ispt[n], ti->tmpbuf))
 247                     heap_insert (ti, ti->tmpbuf, n);
 248                 else
 249                     isc_pp_close (ispt[n]);
 250             }
 251             else
 252             {
 253                 while (1)
 254                 {
 255                     if (!isc_pp_read (ispt[n], ti->tmpbuf))
 256                     {
 257                         heap_delete (ti);
 258                         isc_pp_close (ispt[n]);
 259                         break;
 260                     }
 261                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 262                     {
 263                         heap_delete (ti);
 264                         heap_insert (ti, ti->tmpbuf, n);
 265                         break;
 266                     }
 267                 }
 268             }
 269         }
 270         heap_close (ti);
 271         xfree (ispt);
 272     }
 273     else if (zi->reg->isams)
 274     {
 275         ISAMS_PP *ispt;
 276         int i;
 277         struct trunc_info *ti;
 278         int nn = 0;
 279
 280         ispt = (ISAMS_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] = isams_pp_open (zi->reg->isams, isam_p[from+i]);
 287             if (isams_pp_read (ispt[i], ti->tmpbuf))
 288                 heap_insert (ti, ti->tmpbuf, i);
 289             else
 290                 isams_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             nn++;
 298             while (1)
 299             {
 300                 if (!isams_pp_read (ispt[n], ti->tmpbuf))
 301                 {
 302                     heap_delete (ti);
 303                     isams_pp_close (ispt[n]);
 304                     break;
 305                 }
 306                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 307                 {
 308                     heap_delete (ti);
 309                     heap_insert (ti, ti->tmpbuf, n);
 310                     break;
 311                 }
 312             }
 313         }
 314         heap_close (ti);
 315         xfree (ispt);
 316     }
 317     else if (zi->reg->isamb)
 318     {
 319         ISAMB_PP *ispt;
 320         int i;
 321         struct trunc_info *ti;
 322
 323         ispt = (ISAMB_PP *) xmalloc (sizeof(*ispt) * (to-from));
 324
 325         ti = heap_init (to-from, sizeof(struct it_key),
 326                         key_compare_it);
 327         for (i = to-from; --i >= 0; )
 328         {
 329             if (isam_p[from+i]) {
 330                 ispt[i] = isamb_pp_open (zi->reg->isamb, isam_p[from+i]);
 331                 if (isamb_pp_read (ispt[i], ti->tmpbuf))
 332                     heap_insert (ti, ti->tmpbuf, i);
 333                 else
 334                     isamb_pp_close (ispt[i]);
 335             }
 336         }
 337         while (ti->heapnum)
 338         {
 339             int n = ti->indx[ti->ptr[1]];
 340
 341             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 342             nn++;
 343
 344             if (preserve_position)
 345             {
 346                 heap_delete (ti);
 347                 if (isamb_pp_read (ispt[n], ti->tmpbuf))
 348                     heap_insert (ti, ti->tmpbuf, n);
 349                 else
 350                     isamb_pp_close (ispt[n]);
 351             }
 352             else
 353             {
 354                 while (1)
 355                 {
 356                     if (!isamb_pp_read (ispt[n], ti->tmpbuf))
 357                     {
 358                         heap_delete (ti);
 359                         isamb_pp_close (ispt[n]);
 360                         break;
 361                     }
 362                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 363                     {
 364                         heap_delete (ti);
 365                         heap_insert (ti, ti->tmpbuf, n);
 366                         break;
 367                     }
 368                 }
 369             }
 370         }
 371         heap_close (ti);
 372         xfree (ispt);
 373     }
 374     else
 375         logf (LOG_WARN, "Unknown isam set in rset_trunc_r");
 376
 377     parms.rset_term->nn = nn;
 378     rset_close (result, result_rsfd);
 379     return result;
 380 }
 381
 382 static int isams_trunc_cmp (const void *p1, const void *p2)
 383 {
 384     ISAMS_P i1 = *(ISAMS_P*) p1;
 385     ISAMS_P i2 = *(ISAMS_P*) p2;
 386
 387     if (i1 > i2)
 388         return 1;
 389     else if (i1 < i2)
 390         return -1;
 391     return 0;
 392 }
 393
 394 static int isamc_trunc_cmp (const void *p1, const void *p2)
 395 {
 396     ISAMC_P i1 = *(ISAMC_P*) p1;
 397     ISAMC_P i2 = *(ISAMC_P*) p2;
 398     zint d;
 399
 400     d = (isc_type (i1) - isc_type (i2));
 401     if (d == 0)
 402         d = isc_block (i1) - isc_block (i2);
 403     if (d > 0)
 404         return 1;
 405     else if (d < 0)
 406         return -1;
 407     return 0;
 408 }
 409
 410 RSET rset_trunc (ZebraHandle zi, ISAMS_P *isam_p, int no,
 411                  const char *term, int length, const char *flags,
 412                  int preserve_position, int term_type)
 413 {
 414     logf (LOG_DEBUG, "rset_trunc no=%d", no);
 415     if (no < 1)
 416     {
 417         rset_null_parms parms;
 418         parms.rset_term = rset_term_create (term, length, flags, term_type);
 419         return rset_create (rset_kind_null, &parms);
 420     }
 421     if (zi->reg->isams)
 422     {
 423         if (no == 1)
 424         {
 425             rset_isams_parms parms;
 426
 427             parms.pos = *isam_p;
 428             parms.is = zi->reg->isams;
 429             parms.rset_term = rset_term_create (term, length, flags,
 430                                                 term_type);
 431             return rset_create (rset_kind_isams, &parms);
 432         }
 433         qsort (isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
 434     }
 435     else if (zi->reg->isamc)
 436     {
 437         if (no == 1)
 438         {
 439             rset_isamc_parms parms;
 440
 441             parms.key_size = sizeof(struct it_key);
 442             parms.cmp = key_compare_it;
 443             parms.pos = *isam_p;
 444             parms.is = zi->reg->isamc;
 445             parms.rset_term = rset_term_create (term, length, flags,
 446                                                 term_type);
 447             return rset_create (rset_kind_isamc, &parms);
 448         }
 449 #if NEW_TRUNC
 450         else if (no < 10000)
 451         {
 452             rset_m_or_parms parms;
 453
 454             parms.key_size = sizeof(struct it_key);
 455             parms.cmp = key_compare_it;
 456             parms.isc = zi->reg->isamc;
 457             parms.isam_positions = isam_p;
 458             parms.no_isam_positions = no;
 459             parms.no_save_positions = 100000;
 460             parms.rset_term = rset_term_create (term, length, flags,
 461                                                 term_type);
 462             return rset_create (rset_kind_m_or, &parms);
 463         }
 464 #endif
 465         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 466     }
 467     else if (zi->reg->isamb)
 468     {
 469         if (no == 1)
 470         {
 471             rset_isamb_parms parms;
 472
 473             parms.key_size = sizeof(struct it_key);
 474             parms.cmp = key_compare_it;
 475             parms.pos = *isam_p;
 476             parms.is = zi->reg->isamb;
 477             parms.rset_term = rset_term_create (term, length, flags,
 478                                                 term_type);
 479             return rset_create (rset_kind_isamb, &parms);
 480         }
 481         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 482     }
 483     else
 484     {
 485         logf (LOG_WARN, "Unknown isam set in rset_trunc");
 486         return rset_create (rset_kind_null, NULL);
 487     }
 488     return rset_trunc_r (zi, term, length, flags, isam_p, 0, no, 100,
 489                          preserve_position, term_type);
 490 }
 491