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