rset/rsm_or.c

   1 /*
   2  * Copyright (C) 1994-1999, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: rsm_or.c,v $
   7  * Revision 1.9  1999-07-13 14:45:42  adam
   8  * Fixed memory leak.
   9  *
  10  * Revision 1.8  1999/05/26 07:49:14  adam
  11  * C++ compilation.
  12  *
  13  * Revision 1.7  1998/09/22 10:03:46  adam
  14  * Changed result sets to be persistent in the sense that they can
  15  * be re-searched if needed.
  16  * Fixed memory leak in rsm_or.
  17  *
  18  * Revision 1.6  1998/03/05 08:36:28  adam
  19  * New result set model.
  20  *
  21  * Revision 1.5  1997/12/18 10:54:25  adam
  22  * New method result set method rs_hits that returns the number of
  23  * hits in result-set (if known). The ranked result set returns real
  24  * number of hits but only when not combined with other operands.
  25  *
  26  * Revision 1.4  1997/10/31 12:37:55  adam
  27  * Code calls xfree() instead of free().
  28  *
  29  * Revision 1.3  1997/09/09 13:38:16  adam
  30  * Partial port to WIN95/NT.
  31  *
  32  * Revision 1.2  1996/12/23 15:30:49  adam
  33  * Work on truncation.
  34  *
  35  * Revision 1.1  1996/12/20 11:07:21  adam
  36  * Implemented Multi-or result set.
  37  *
  38  */
  39
  40 #include <assert.h>
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <string.h>
  44
  45 #include <isam.h>
  46 #include <isamc.h>
  47 #include <rsm_or.h>
  48 #include <zebrautl.h>
  49
  50 static void *r_create(RSET ct, const struct rset_control *sel, void *parms);
  51 static RSFD r_open (RSET ct, int flag);
  52 static void r_close (RSFD rfd);
  53 static void r_delete (RSET ct);
  54 static void r_rewind (RSFD rfd);
  55 static int r_count (RSET ct);
  56 static int r_read (RSFD rfd, void *buf, int *term_index);
  57 static int r_write (RSFD rfd, const void *buf);
  58
  59 static const struct rset_control control =
  60 {
  61     "multi-or",
  62     r_create,
  63     r_open,
  64     r_close,
  65     r_delete,
  66     r_rewind,
  67     r_count,
  68     r_read,
  69     r_write,
  70 };
  71
  72 const struct rset_control *rset_kind_m_or = &control;
  73
  74 struct rset_mor_info {
  75     int     key_size;
  76     int     no_rec;
  77     int     (*cmp)(const void *p1, const void *p2);
  78     ISAMC   isc;
  79     ISAM_P  *isam_positions;
  80
  81     int     no_isam_positions;
  82     int     no_save_positions;
  83     struct rset_mor_rfd *rfd_list;
  84 };
  85
  86 struct trunc_info {
  87     int  *ptr;
  88     int  *indx;
  89     char **heap;
  90     int  heapnum;
  91     int  (*cmp)(const void *p1, const void *p2);
  92     int  keysize;
  93     char *swapbuf;
  94     char *tmpbuf;
  95     char *buf;
  96 };
  97
  98 struct rset_mor_rfd {
  99     int flag;
 100     int position;
 101     int position_max;
 102     ISAMC_PP *ispt;
 103     struct rset_mor_rfd *next;
 104     struct rset_mor_info *info;
 105     struct trunc_info *ti;
 106 };
 107
 108 static void heap_swap (struct trunc_info *ti, int i1, int i2)
 109 {
 110     int swap;
 111
 112     swap = ti->ptr[i1];
 113     ti->ptr[i1] = ti->ptr[i2];
 114     ti->ptr[i2] = swap;
 115 }
 116
 117 static void heap_delete (struct trunc_info *ti)
 118 {
 119     int cur = 1, child = 2;
 120
 121     heap_swap (ti, 1, ti->heapnum--);
 122     while (child <= ti->heapnum) {
 123         if (child < ti->heapnum &&
 124             (*ti->cmp)(ti->heap[ti->ptr[child]],
 125                        ti->heap[ti->ptr[1+child]]) > 0)
 126             child++;
 127         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
 128                        ti->heap[ti->ptr[child]]) > 0)
 129         {
 130             heap_swap (ti, cur, child);
 131             cur = child;
 132             child = 2*cur;
 133         }
 134         else
 135             break;
 136     }
 137 }
 138
 139 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
 140 {
 141     int cur, parent;
 142
 143     cur = ++(ti->heapnum);
 144     memcpy (ti->heap[ti->ptr[cur]], buf, ti->keysize);
 145     ti->indx[ti->ptr[cur]] = indx;
 146     parent = cur/2;
 147     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
 148                                 ti->heap[ti->ptr[cur]]) > 0)
 149     {
 150         heap_swap (ti, cur, parent);
 151         cur = parent;
 152         parent = cur/2;
 153     }
 154 }
 155
 156 static
 157 struct trunc_info *heap_init (int size, int key_size,
 158                               int (*cmp)(const void *p1, const void *p2))
 159 {
 160     struct trunc_info *ti = (struct trunc_info *) xmalloc (sizeof(*ti));
 161     int i;
 162
 163     ++size;
 164     ti->heapnum = 0;
 165     ti->keysize = key_size;
 166     ti->cmp = cmp;
 167     ti->indx = (int *) xmalloc (size * sizeof(*ti->indx));
 168     ti->heap = (char **) xmalloc (size * sizeof(*ti->heap));
 169     ti->ptr = (int *) xmalloc (size * sizeof(*ti->ptr));
 170     ti->swapbuf = (char *) xmalloc (ti->keysize);
 171     ti->tmpbuf = (char *) xmalloc (ti->keysize);
 172     ti->buf = (char *) xmalloc (size * ti->keysize);
 173     for (i = size; --i >= 0; )
 174     {
 175         ti->ptr[i] = i;
 176         ti->heap[i] = ti->buf + ti->keysize * i;
 177     }
 178     return ti;
 179 }
 180
 181 static void heap_close (struct trunc_info *ti)
 182 {
 183     xfree (ti->buf);
 184     xfree (ti->ptr);
 185     xfree (ti->indx);
 186     xfree (ti->heap);
 187     xfree (ti->swapbuf);
 188     xfree (ti->tmpbuf);
 189     xfree (ti);
 190 }
 191
 192 static void *r_create (RSET ct, const struct rset_control *sel, void *parms)
 193 {
 194     rset_m_or_parms *r_parms = (rset_m_or_parms *) parms;
 195     struct rset_mor_info *info;
 196
 197     ct->flags |= RSET_FLAG_VOLATILE;
 198     info = (struct rset_mor_info *) xmalloc (sizeof(*info));
 199     info->key_size = r_parms->key_size;
 200     assert (info->key_size > 1);
 201     info->cmp = r_parms->cmp;
 202
 203     info->no_save_positions = r_parms->no_save_positions;
 204
 205     info->isc = r_parms->isc;
 206     info->no_isam_positions = r_parms->no_isam_positions;
 207     info->isam_positions = (ISAM_P *)
 208         xmalloc (sizeof(*info->isam_positions) * info->no_isam_positions);
 209     memcpy (info->isam_positions, r_parms->isam_positions,
 210             sizeof(*info->isam_positions) * info->no_isam_positions);
 211     info->rfd_list = NULL;
 212
 213     ct->no_rset_terms = 1;
 214     ct->rset_terms = (RSET_TERM *) xmalloc (sizeof(*ct->rset_terms));
 215     ct->rset_terms[0] = r_parms->rset_term;
 216     return info;
 217 }
 218
 219 static RSFD r_open (RSET ct, int flag)
 220 {
 221     struct rset_mor_rfd *rfd;
 222     struct rset_mor_info *info = (struct rset_mor_info *) ct->buf;
 223     int i;
 224
 225     if (flag & RSETF_WRITE)
 226     {
 227         logf (LOG_FATAL, "m_or set type is read-only");
 228         return NULL;
 229     }
 230     rfd = (struct rset_mor_rfd *) xmalloc (sizeof(*rfd));
 231     rfd->flag = flag;
 232     rfd->next = info->rfd_list;
 233     rfd->info = info;
 234     info->rfd_list = rfd;
 235
 236     rfd->ispt = (ISAMC_PP *)
 237         xmalloc (sizeof(*rfd->ispt) * info->no_isam_positions);
 238
 239     rfd->ti = heap_init (info->no_isam_positions, info->key_size, info->cmp);
 240
 241     ct->rset_terms[0]->nn = 0;
 242     for (i = 0; i<info->no_isam_positions; i++)
 243     {
 244         rfd->ispt[i] = isc_pp_open (info->isc, info->isam_positions[i]);
 245
 246         ct->rset_terms[0]->nn += isc_pp_num (rfd->ispt[i]);
 247
 248         if (isc_pp_read (rfd->ispt[i], rfd->ti->tmpbuf))
 249             heap_insert (rfd->ti, rfd->ti->tmpbuf, i);
 250         else
 251         {
 252             isc_pp_close (rfd->ispt[i]);
 253             rfd->ispt[i] = NULL;
 254         }
 255     }
 256     rfd->position = info->no_save_positions;
 257     r_rewind (rfd);
 258     return rfd;
 259 }
 260
 261 static void r_close (RSFD rfd)
 262 {
 263     struct rset_mor_info *info = ((struct rset_mor_rfd*)rfd)->info;
 264     struct rset_mor_rfd **rfdp;
 265     int i;
 266
 267     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 268         if (*rfdp == rfd)
 269         {
 270             *rfdp = (*rfdp)->next;
 271
 272             heap_close (((struct rset_mor_rfd *) rfd)->ti);
 273             for (i = 0; i<info->no_isam_positions; i++)
 274                 if (((struct rset_mor_rfd *) rfd)->ispt[i])
 275                     isc_pp_close (((struct rset_mor_rfd *) rfd)->ispt[i]);
 276             xfree (((struct rset_mor_rfd *)rfd)->ispt);
 277             xfree (rfd);
 278             return;
 279         }
 280     logf (LOG_FATAL, "r_close but no rfd match!");
 281     assert (0);
 282 }
 283
 284 static void r_delete (RSET ct)
 285 {
 286     struct rset_mor_info *info = (struct rset_mor_info *) ct->buf;
 287     int i;
 288
 289     assert (info->rfd_list == NULL);
 290     xfree (info->isam_positions);
 291
 292     for (i = 0; i<ct->no_rset_terms; i++)
 293         rset_term_destroy (ct->rset_terms[i]);
 294     xfree (ct->rset_terms);
 295
 296     xfree (info);
 297 }
 298
 299 static void r_rewind (RSFD rfd)
 300 {
 301 }
 302
 303 static int r_count (RSET ct)
 304 {
 305     return 0;
 306 }
 307
 308 static int r_read (RSFD rfd, void *buf, int *term_index)
 309 {
 310     struct trunc_info *ti = ((struct rset_mor_rfd *) rfd)->ti;
 311     int n = ti->indx[ti->ptr[1]];
 312
 313     if (!ti->heapnum)
 314         return 0;
 315     *term_index = 0;
 316     memcpy (buf, ti->heap[ti->ptr[1]], ti->keysize);
 317     if (((struct rset_mor_rfd *) rfd)->position)
 318     {
 319         if (isc_pp_read (((struct rset_mor_rfd *) rfd)->ispt[n], ti->tmpbuf))
 320         {
 321             heap_delete (ti);
 322             if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 323                  ((struct rset_mor_rfd *) rfd)->position--;
 324             heap_insert (ti, ti->tmpbuf, n);
 325         }
 326         else
 327             heap_delete (ti);
 328         return 1;
 329     }
 330     while (1)
 331     {
 332         if (!isc_pp_read (((struct rset_mor_rfd *) rfd)->ispt[n], ti->tmpbuf))
 333         {
 334             heap_delete (ti);
 335             break;
 336         }
 337         if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 338         {
 339             heap_delete (ti);
 340             heap_insert (ti, ti->tmpbuf, n);
 341             break;
 342         }
 343     }
 344     return 1;
 345 }
 346
 347 static int r_write (RSFD rfd, const void *buf)
 348 {
 349     logf (LOG_FATAL, "mor set type is read-only");
 350     return -1;
 351 }