rset/rsm_or.c

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