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