index/trunc.c

   1 /*
   2  * Copyright (C) 1994-1996, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: trunc.c,v $
   7  * Revision 1.3  1996-12-20 11:07:14  adam
   8  * Multi-or result set.
   9  *
  10  * Revision 1.2  1996/11/08 11:10:28  adam
  11  * Buffers used during file match got bigger.
  12  * Compressed ISAM support everywhere.
  13  * Bug fixes regarding masking characters in queries.
  14  * Redesigned Regexp-2 queries.
  15  *
  16  * Revision 1.1  1996/11/04 14:07:40  adam
  17  * Moved truncation code to trunc.c.
  18  *
  19  */
  20 #include <stdio.h>
  21 #include <assert.h>
  22
  23 #include "zserver.h"
  24 #include <rstemp.h>
  25 #include <rsisam.h>
  26 #include <rsisamc.h>
  27 #include <rsnull.h>
  28
  29 #define NEW_TRUNC 0
  30
  31 #if NEW_TRUNC
  32 #include <rsm_or.h>
  33 #endif
  34
  35 struct trunc_info {
  36     int  *ptr;
  37     int  *indx;
  38     char **heap;
  39     int  heapnum;
  40     int  (*cmp)(const void *p1, const void *p2);
  41     int  keysize;
  42     char *swapbuf;
  43     char *tmpbuf;
  44     char *buf;
  45 };
  46
  47 static void heap_swap (struct trunc_info *ti, int i1, int i2)
  48 {
  49     int swap;
  50
  51     swap = ti->ptr[i1];
  52     ti->ptr[i1] = ti->ptr[i2];
  53     ti->ptr[i2] = swap;
  54 }
  55
  56 static void heap_delete (struct trunc_info *ti)
  57 {
  58     int cur = 1, child = 2;
  59
  60     heap_swap (ti, 1, ti->heapnum--);
  61     while (child <= ti->heapnum) {
  62         if (child < ti->heapnum &&
  63             (*ti->cmp)(ti->heap[ti->ptr[child]],
  64                        ti->heap[ti->ptr[1+child]]) > 0)
  65             child++;
  66         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
  67                        ti->heap[ti->ptr[child]]) > 0)
  68         {
  69             heap_swap (ti, cur, child);
  70             cur = child;
  71             child = 2*cur;
  72         }
  73         else
  74             break;
  75     }
  76 }
  77
  78 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
  79 {
  80     int cur, parent;
  81
  82     cur = ++(ti->heapnum);
  83     memcpy (ti->heap[ti->ptr[cur]], buf, ti->keysize);
  84     ti->indx[ti->ptr[cur]] = indx;
  85     parent = cur/2;
  86     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
  87                                 ti->heap[ti->ptr[cur]]) > 0)
  88     {
  89         heap_swap (ti, cur, parent);
  90         cur = parent;
  91         parent = cur/2;
  92     }
  93 }
  94
  95 static
  96 struct trunc_info *heap_init (int size, int key_size,
  97                               int (*cmp)(const void *p1, const void *p2))
  98 {
  99     struct trunc_info *ti = xmalloc (sizeof(*ti));
 100     int i;
 101
 102     ++size;
 103     ti->heapnum = 0;
 104     ti->keysize = key_size;
 105     ti->cmp = cmp;
 106     ti->indx = xmalloc (size * sizeof(*ti->indx));
 107     ti->heap = xmalloc (size * sizeof(*ti->heap));
 108     ti->ptr = xmalloc (size * sizeof(*ti->ptr));
 109     ti->swapbuf = xmalloc (ti->keysize);
 110     ti->tmpbuf = xmalloc (ti->keysize);
 111     ti->buf = xmalloc (size * ti->keysize);
 112     for (i = size; --i >= 0; )
 113     {
 114         ti->ptr[i] = i;
 115         ti->heap[i] = ti->buf + ti->keysize * i;
 116     }
 117     return ti;
 118 }
 119
 120 static void heap_close (struct trunc_info *ti)
 121 {
 122     xfree (ti->ptr);
 123     xfree (ti->indx);
 124     xfree (ti->heap);
 125     xfree (ti->swapbuf);
 126     xfree (ti->tmpbuf);
 127     xfree (ti);
 128 }
 129
 130 static RSET rset_trunc_r (ZServerInfo *zi, ISAM_P *isam_p, int from, int to,
 131                          int merge_chunk)
 132 {
 133     RSET result;
 134     RSFD result_rsfd;
 135     rset_temp_parms parms;
 136
 137     parms.key_size = sizeof(struct it_key);
 138     result = rset_create (rset_kind_temp, &parms);
 139     result_rsfd = rset_open (result, RSETF_WRITE|RSETF_SORT_SYSNO);
 140
 141     if (to - from > merge_chunk)
 142     {
 143         RSFD *rsfd;
 144         RSET *rset;
 145         int i, i_add = (to-from)/merge_chunk + 1;
 146         struct trunc_info *ti;
 147         int rscur = 0;
 148         int rsmax = (to-from)/i_add + 1;
 149
 150         rset = xmalloc (sizeof(*rset) * rsmax);
 151         rsfd = xmalloc (sizeof(*rsfd) * rsmax);
 152
 153         for (i = from; i < to; i += i_add)
 154         {
 155             if (i_add <= to - i)
 156                 rset[rscur] = rset_trunc_r (zi, isam_p, i, i+i_add,
 157                                             merge_chunk);
 158             else
 159                 rset[rscur] = rset_trunc_r (zi, isam_p, i, to,
 160                                             merge_chunk);
 161             rscur++;
 162         }
 163         ti = heap_init (rscur, sizeof(struct it_key), key_compare);
 164         for (i = rscur; --i >= 0; )
 165         {
 166             rsfd[i] = rset_open (rset[i], RSETF_READ|RSETF_SORT_SYSNO);
 167             if (rset_read (rset[i], rsfd[i], ti->tmpbuf))
 168                 heap_insert (ti, ti->tmpbuf, i);
 169             else
 170             {
 171                 rset_close (rset[i], rsfd[i]);
 172                 rset_delete (rset[i]);
 173             }
 174         }
 175         while (ti->heapnum)
 176         {
 177             int n = ti->indx[ti->ptr[1]];
 178
 179             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 180
 181             while (1)
 182             {
 183                 if (!rset_read (rset[n], rsfd[n], ti->tmpbuf))
 184                 {
 185                     heap_delete (ti);
 186                     rset_close (rset[n], rsfd[n]);
 187                     rset_delete (rset[n]);
 188                     break;
 189                 }
 190                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 191                 {
 192                     heap_delete (ti);
 193                     heap_insert (ti, ti->tmpbuf, n);
 194                     break;
 195                 }
 196             }
 197         }
 198         xfree (rset);
 199         xfree (rsfd);
 200         heap_close (ti);
 201     }
 202     else if (zi->isam)
 203     {
 204         ISPT *ispt;
 205         int i;
 206         struct trunc_info *ti;
 207
 208         ispt = xmalloc (sizeof(*ispt) * (to-from));
 209
 210         ti = heap_init (to-from, sizeof(struct it_key),
 211                         key_compare);
 212         for (i = to-from; --i >= 0; )
 213         {
 214             ispt[i] = is_position (zi->isam, isam_p[from+i]);
 215             if (is_readkey (ispt[i], ti->tmpbuf))
 216                 heap_insert (ti, ti->tmpbuf, i);
 217             else
 218                 is_pt_free (ispt[i]);
 219         }
 220         while (ti->heapnum)
 221         {
 222             int n = ti->indx[ti->ptr[1]];
 223
 224             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 225 #if 1
 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 #else
 233 /* section that preserve all keys with unique sysnos */
 234             while (1)
 235             {
 236                 if (!is_readkey (ispt[n], ti->tmpbuf))
 237                 {
 238                     heap_delete (ti);
 239                     is_pt_free (ispt[n]);
 240                     break;
 241                 }
 242                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 243                 {
 244                     heap_delete (ti);
 245                     heap_insert (ti, ti->tmpbuf, n);
 246                     break;
 247                 }
 248             }
 249 #endif
 250         }
 251         heap_close (ti);
 252         xfree (ispt);
 253     }
 254     else
 255     {
 256         ISAMC_PP *ispt;
 257         int i;
 258         struct trunc_info *ti;
 259
 260         ispt = xmalloc (sizeof(*ispt) * (to-from));
 261
 262         ti = heap_init (to-from, sizeof(struct it_key),
 263                         key_compare);
 264         for (i = to-from; --i >= 0; )
 265         {
 266             ispt[i] = isc_pp_open (zi->isamc, isam_p[from+i]);
 267             if (isc_pp_read (ispt[i], ti->tmpbuf))
 268                 heap_insert (ti, ti->tmpbuf, i);
 269             else
 270                 isc_pp_close (ispt[i]);
 271         }
 272         while (ti->heapnum)
 273         {
 274             int n = ti->indx[ti->ptr[1]];
 275
 276             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 277 #if 0
 278 /* section that preserve all keys */
 279             heap_delete (ti);
 280             if (is_readkey (ispt[n], ti->tmpbuf))
 281                 heap_insert (ti, ti->tmpbuf, n);
 282             else
 283                 isc_pp_close (ispt[n]);
 284 #else
 285 /* section that preserve all keys with unique sysnos */
 286             while (1)
 287             {
 288                 if (!isc_pp_read (ispt[n], ti->tmpbuf))
 289                 {
 290                     heap_delete (ti);
 291                     isc_pp_close (ispt[n]);
 292                     break;
 293                 }
 294                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 295                 {
 296                     heap_delete (ti);
 297                     heap_insert (ti, ti->tmpbuf, n);
 298                     break;
 299                 }
 300             }
 301 #endif
 302         }
 303         heap_close (ti);
 304         xfree (ispt);
 305     }
 306     rset_close (result, result_rsfd);
 307     return result;
 308 }
 309
 310 static int isam_trunc_cmp (const void *p1, const void *p2)
 311 {
 312     ISAM_P i1 = *(ISAM_P*) p1;
 313     ISAM_P i2 = *(ISAM_P*) p2;
 314     int d;
 315
 316     d = is_type (i1) - is_type (i2);
 317     if (d)
 318         return d;
 319     return is_block (i1) - is_block (i2);
 320 }
 321
 322 static int isamc_trunc_cmp (const void *p1, const void *p2)
 323 {
 324     ISAMC_P i1 = *(ISAMC_P*) p1;
 325     ISAMC_P i2 = *(ISAMC_P*) p2;
 326     int d;
 327
 328     d = isc_type (i1) - isc_type (i2);
 329     if (d)
 330         return d;
 331     return isc_block (i1) - isc_block (i2);
 332 }
 333
 334 RSET rset_trunc (ZServerInfo *zi, ISAM_P *isam_p, int no)
 335 {
 336     logf (LOG_LOG, "rset_trunc no=%d", no);
 337     if (zi->isam)
 338     {
 339         if (no < 1)
 340             return rset_create (rset_kind_null, NULL);
 341         else if (no == 1)
 342         {
 343             rset_isam_parms parms;
 344
 345             parms.pos = *isam_p;
 346             parms.is = zi->isam;
 347             return rset_create (rset_kind_isam, &parms);
 348         }
 349         qsort (isam_p, no, sizeof(*isam_p), isam_trunc_cmp);
 350     }
 351     else if (zi->isamc)
 352     {
 353         if (no < 1)
 354             return rset_create (rset_kind_null, NULL);
 355         else if (no == 1)
 356         {
 357             rset_isamc_parms parms;
 358
 359             parms.pos = *isam_p;
 360             parms.is = zi->isamc;
 361             return rset_create (rset_kind_isamc, &parms);
 362         }
 363 #if NEW_TRUNC
 364         else if (no < 2000)
 365         {
 366             rset_m_or_parms parms;
 367
 368             logf (LOG_LOG, "new_trunc");
 369             parms.key_size = sizeof(struct it_key);
 370             parms.cmp = key_compare;
 371             parms.isc = zi->isamc;
 372             parms.isam_positions = isam_p;
 373             parms.no_isam_positions = no;
 374             return rset_create (rset_kind_m_or, &parms);
 375         }
 376 #endif
 377         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
 378     }
 379     else
 380         logf (LOG_FATAL, "Neither isam nor isamc set in rset_trunc");
 381     return rset_trunc_r (zi, isam_p, 0, no, 100);
 382 }
 383