index/trunc.c

   1 /* $Id: trunc.c,v 1.31 2004-08-06 13:14:46 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             ispt[i] = isamb_pp_open (zi->reg->isamb, isam_p[from+i]);
 330             if (isamb_pp_read (ispt[i], ti->tmpbuf))
 331                 heap_insert (ti, ti->tmpbuf, i);
 332             else
 333                 isamb_pp_close (ispt[i]);
 334         }
 335         while (ti->heapnum)
 336         {
 337             int n = ti->indx[ti->ptr[1]];
 338
 339             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 340             nn++;
 341
 342             if (preserve_position)
 343             {
 344                 heap_delete (ti);
 345                 if (isamb_pp_read (ispt[n], ti->tmpbuf))
 346                     heap_insert (ti, ti->tmpbuf, n);
 347                 else
 348                     isamb_pp_close (ispt[n]);
 349             }
 350             else
 351             {
 352                 while (1)
 353                 {
 354                     if (!isamb_pp_read (ispt[n], ti->tmpbuf))
 355                     {
 356                         heap_delete (ti);
 357                         isamb_pp_close (ispt[n]);
 358                         break;
 359                     }
 360                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 361                     {
 362                         heap_delete (ti);
 363                         heap_insert (ti, ti->tmpbuf, n);
 364                         break;
 365                     }
 366                 }
 367             }
 368         }
 369         heap_close (ti);
 370         xfree (ispt);
 371     }
 372     else
 373         logf (LOG_WARN, "Unknown isam set in rset_trunc_r");
 374
 375     parms.rset_term->nn = nn;
 376     rset_close (result, result_rsfd);
 377     return result;
 378 }
 379
 380 static int isams_trunc_cmp (const void *p1, const void *p2)
 381 {
 382     ISAMS_P i1 = *(ISAMS_P*) p1;
 383     ISAMS_P i2 = *(ISAMS_P*) p2;
 384
 385     if (i1 > i2)
 386         return 1;
 387     else if (i1 < i2)
 388         return -1;
 389     return 0;
 390 }
 391
 392 static int isamc_trunc_cmp (const void *p1, const void *p2)
 393 {
 394     ISAMC_P i1 = *(ISAMC_P*) p1;
 395     ISAMC_P i2 = *(ISAMC_P*) p2;
 396     int d;
 397
 398     d = (int) (isc_type (i1) - isc_type (i2));
 399     if (d)
 400         return d;
 401     d = isc_block (i1) - isc_block (i2);
 402     if (d > 0)
 403         return 1;
 404     else if (d < 0)
 405         return -1;
 406     return 0;
 407 }
 408
 409 RSET rset_trunc (ZebraHandle zi, ISAMS_P *isam_p, int no,
 410                  const char *term, int length, const char *flags,
 411                  int preserve_position, int term_type)
 412 {
 413     logf (LOG_DEBUG, "rset_trunc no=%d", no);
 414     if (no < 1)
 415     {
 416         rset_null_parms parms;
 417         parms.rset_term = rset_term_create (term, length, flags, term_type);
 418         return rset_create (rset_kind_null, &parms);
 419     }
 420     if (zi->reg->isams)
 421     {
 422         if (no == 1)
 423         {
 424             rset_isams_parms parms;
 425
 426             parms.pos = *isam_p;
 427             parms.is = zi->reg->isams;
 428             parms.rset_term = rset_term_create (term, length, flags,
 429                                                 term_type);
 430             return rset_create (rset_kind_isams, &parms);
 431         }
 432         qsort (isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
 433     }
 434     else if (zi->reg->isamc)
 435     {
 436         if (no == 1)
 437         {
 438             rset_isamc_parms parms;
 439
 440             parms.key_size = sizeof(struct it_key);
 441             parms.cmp = key_compare_it;
 442             parms.pos = *isam_p;
 443             parms.is = zi->reg->isamc;
 444             parms.rset_term = rset_term_create (term, length, flags,
 445                                                 term_type);
 446             return rset_create (rset_kind_isamc, &parms);
 447         }
 448 #if NEW_TRUNC
 449         else if (no < 10000)
 450         {
 451             rset_m_or_parms parms;
 452
 453             parms.key_size = sizeof(struct it_key);
 454             parms.cmp = key_compare_it;
 455             parms.isc = zi->reg->isamc;
 456             parms.isam_positions = isam_p;
 457             parms.no_isam_positions = no;
 458             parms.no_save_positions = 100000;
 459             parms.rset_term = rset_term_create (term, length, flags,
 460                                                 term_type);
 461             return rset_create (rset_kind_m_or, &parms);
 462         }
 463 #endif
 464         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 465     }
 466     else if (zi->reg->isamb)
 467     {
 468         if (no == 1)
 469         {
 470             rset_isamb_parms parms;
 471
 472             parms.key_size = sizeof(struct it_key);
 473             parms.cmp = key_compare_it;
 474             parms.pos = *isam_p;
 475             parms.is = zi->reg->isamb;
 476             parms.rset_term = rset_term_create (term, length, flags,
 477                                                 term_type);
 478             return rset_create (rset_kind_isamb, &parms);
 479         }
 480         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 481     }
 482     else
 483     {
 484         logf (LOG_WARN, "Unknown isam set in rset_trunc");
 485         return rset_create (rset_kind_null, NULL);
 486     }
 487     return rset_trunc_r (zi, term, length, flags, isam_p, 0, no, 100,
 488                          preserve_position, term_type);
 489 }
 490