Put local variables footer in all c, h files.
[idzebra-moved-to-github.git] / rset / rsmultiandor.c
1 /* $Id: rsmultiandor.c,v 1.20 2006-05-10 08:13:33 adam Exp $
2    Copyright (C) 1995-2005
3    Index Data ApS
4
5 This file is part of the Zebra server.
6
7 Zebra is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.
21 */
22
23
24 /*
25  * This module implements the rsmulti_or and rsmulti_and result sets
26  *
27  * rsmultior is based on a heap, from which we find the next hit.
28  *
29  * rsmultiand is based on a simple array of rsets, and a linear
30  * search to find the record that exists in all of those rsets.
31  * To speed things up, the array is sorted so that the smallest
32  * rsets come first, they are most likely to have the hits furthest
33  * away, and thus forwarding to them makes the most sense.
34  */
35
36
37 #include <assert.h>
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41
42 #include <idzebra/util.h>
43 #include <idzebra/isamc.h>
44 #include <rset.h>
45
46 static RSFD r_open_and (RSET ct, int flag);
47 static RSFD r_open_or (RSET ct, int flag);
48 static void r_close (RSFD rfd);
49 static void r_delete (RSET ct);
50 static int r_read_and (RSFD rfd, void *buf, TERMID *term);
51 static int r_read_or (RSFD rfd, void *buf, TERMID *term);
52 static int r_write (RSFD rfd, const void *buf);
53 static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
54                      const void *untilbuf);
55 static int r_forward_or(RSFD rfd, void *buf, TERMID *term,
56                      const void *untilbuf);
57 static void r_pos (RSFD rfd, double *current, double *total);
58 static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm);
59
60 static const struct rset_control control_or = 
61 {
62     "multi-or",
63     r_delete,
64     r_get_terms,
65     r_open_or,
66     r_close,
67     r_forward_or,
68     r_pos,
69     r_read_or,
70     r_write,
71 };
72
73 static const struct rset_control control_and = 
74 {
75     "multi-and",
76     r_delete,
77     r_get_terms,
78     r_open_and,
79     r_close,
80     r_forward_and,
81     r_pos,
82     r_read_and,
83     r_write,
84 };
85
86 /* The heap structure: 
87  * The rset contains a list or rsets we are ORing together 
88  * The rfd contains a heap of heap-items, which contain
89  * a rfd opened to those rsets, and a buffer for one key.
90  * They also contain a ptr to the rset list in the rset 
91  * itself, for practical reasons. 
92  */
93
94 struct heap_item {
95     RSFD fd;
96     void *buf;
97     RSET rset;
98     TERMID term;
99 };
100
101 struct heap {
102     int heapnum;
103     int heapmax;
104     const struct rset_key_control *kctrl;
105     struct heap_item **heap; /* ptrs to the rfd */
106 };
107 typedef struct heap *HEAP;
108
109
110 struct rset_private {
111     int dummy;
112 };
113
114
115 struct rfd_private {
116     int flag;
117     struct heap_item *items; /* we alloc and free them here */
118     HEAP h; /* and move around here */
119     zint hits; /* returned so far */
120     int eof; /* seen the end of it */
121     int tailcount; /* how many items are tailing */
122     char *tailbits;
123 };
124
125 static int log_level = 0;
126 static int log_level_initialized = 0;
127
128
129 /* Heap functions ***********************/
130
131 #if 0
132 static void heap_dump_item( HEAP h, int i, int level)
133 {
134     double cur,tot;
135     if (i>h->heapnum)
136         return;
137     (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
138     yaz_log(log_level," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",  
139                     &(h->heap[i]), h->heap[i]->buf, cur,tot );
140     heap_dump_item(h, 2*i, level+1);
141     heap_dump_item(h, 2*i+1, level+1);
142 }
143 static void heap_dump( HEAP h,char *msg) {
144     yaz_log(log_level, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
145     heap_dump_item(h,1,1);
146 }
147 #endif
148
149 static void heap_swap (HEAP h, int x, int y)
150 {
151     struct heap_item *swap;
152     swap = h->heap[x];
153     h->heap[x] = h->heap[y];
154     h->heap[y] = swap;
155 }
156
157 static int heap_cmp(HEAP h, int x, int y)
158 {
159     return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
160 }
161
162 static int heap_empty(HEAP h)
163 {
164     return ( 0==h->heapnum );
165 }
166
167 static void heap_delete (HEAP h)
168 { /* deletes the first item in the heap, and balances the rest */
169     int cur = 1, child = 2;
170     h->heap[1] = 0; /* been deleted */
171     heap_swap (h, 1, h->heapnum--);
172     while (child <= h->heapnum) {
173         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
174             child++;
175         if (heap_cmp(h,cur,child) > 0)
176         {
177             heap_swap (h, cur, child);
178             cur = child;
179             child = 2*cur;
180         }
181         else
182             break;
183     }
184 }
185
186 static void heap_balance (HEAP h)
187 { /* The heap root element has changed value (to bigger) */
188   /* swap downwards until the heap is ordered again */
189     int cur = 1, child = 2;
190     while (child <= h->heapnum) {
191         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
192             child++;
193         if (heap_cmp(h,cur,child) > 0)
194         {
195             heap_swap (h, cur, child);
196             cur = child;
197             child = 2*cur;
198         }
199         else
200             break;
201     }
202 }
203
204
205 static void heap_insert (HEAP h, struct heap_item *hi)
206 {
207     int cur, parent;
208
209     cur = ++(h->heapnum);
210     assert(cur <= h->heapmax);
211     h->heap[cur] = hi;
212     parent = cur/2;
213     while (parent && (heap_cmp(h,parent,cur) > 0))
214     {
215         assert(parent>0);
216         heap_swap (h, cur, parent);
217         cur = parent;
218         parent = cur/2;
219     }
220 }
221
222
223 static
224 HEAP heap_create (NMEM nmem, int size, const struct rset_key_control *kctrl)
225 {
226     HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
227
228     ++size; /* heap array starts at 1 */
229     h->heapnum = 0;
230     h->heapmax = size;
231     h->kctrl = kctrl;
232     h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
233     h->heap[0]=0; /* not used */
234     return h;
235 }
236
237 static void heap_clear( HEAP h)
238 {
239     assert(h);
240     h->heapnum = 0;
241 }
242
243 static void heap_destroy (HEAP h)
244 {
245     /* nothing to delete, all is nmem'd, and will go away in due time */
246 }
247
248 int compare_ands(const void *x, const void *y)
249 { /* used in qsort to get the multi-and args in optimal order */
250   /* that is, those with fewest occurrences first */
251     const struct heap_item *hx = x;
252     const struct heap_item *hy = y;
253     double cur, totx, toty;
254     rset_pos(hx->fd, &cur, &totx);
255     rset_pos(hy->fd, &cur, &toty);
256     if ( totx > toty +0.5 )
257         return 1;
258     if ( totx < toty -0.5 )
259         return -1;
260     return 0;  /* return totx - toty, except for overflows and rounding */
261 }
262
263 /* Creating and deleting rsets ***********************/
264
265 static RSET rsmulti_andor_create(NMEM nmem,
266                                  struct rset_key_control *kcontrol, 
267                                  int scope, TERMID termid,
268                                  int no_rsets, RSET* rsets, 
269                                  const struct rset_control *ctrl)
270 {
271     RSET rnew = rset_create_base(ctrl, nmem, kcontrol, scope, termid,
272                                  no_rsets, rsets);
273     struct rset_private *info;
274     if (!log_level_initialized)
275     {
276         log_level = yaz_log_module_level("rsmultiandor");
277         log_level_initialized = 1;
278     }
279     yaz_log(log_level, "rsmultiand_andor_create scope=%d", scope);
280     info = (struct rset_private *) nmem_malloc(rnew->nmem, sizeof(*info));
281     rnew->priv = info;
282     return rnew;
283 }
284
285 RSET rsmulti_or_create(NMEM nmem, struct rset_key_control *kcontrol,
286                        int scope, TERMID termid, int no_rsets, RSET* rsets)
287 {
288     return rsmulti_andor_create(nmem, kcontrol, scope, termid,
289                                 no_rsets, rsets, &control_or);
290 }
291
292 RSET rsmulti_and_create(NMEM nmem, struct rset_key_control *kcontrol,
293                         int scope, int no_rsets, RSET* rsets)
294 {
295     return rsmulti_andor_create(nmem, kcontrol, scope, 0,
296                                 no_rsets, rsets, &control_and);
297 }
298
299 static void r_delete (RSET ct)
300 {
301 }
302
303 /* Opening and closing fd's on them *********************/
304
305 static RSFD r_open_andor (RSET ct, int flag, int is_and)
306 {
307     RSFD rfd;
308     struct rfd_private *p;
309     const struct rset_key_control *kctrl = ct->keycontrol;
310     int i;
311
312     if (flag & RSETF_WRITE)
313     {
314         yaz_log (YLOG_FATAL, "multiandor set type is read-only");
315         return NULL;
316     }
317     rfd = rfd_create_base(ct);
318     if (rfd->priv) {
319         p = (struct rfd_private *)rfd->priv;
320         if (!is_and)
321             heap_clear(p->h);
322         assert(p->items);
323         /* all other pointers shouls already be allocated, in right sizes! */
324     }
325     else {
326         p = (struct rfd_private *) nmem_malloc (ct->nmem,sizeof(*p));
327         rfd->priv = p;
328         p->h = 0;
329         p->tailbits = 0;
330         if (is_and)
331             p->tailbits = nmem_malloc(ct->nmem, ct->no_children*sizeof(char) );
332         else 
333             p->h = heap_create( ct->nmem, ct->no_children, kctrl);
334         p->items = (struct heap_item *) 
335             nmem_malloc(ct->nmem, ct->no_children*sizeof(*p->items));
336         for (i = 0; i<ct->no_children; i++)
337         {
338             p->items[i].rset = ct->children[i];
339             p->items[i].buf = nmem_malloc(ct->nmem, kctrl->key_size);
340         }
341     }
342     p->flag = flag;
343     p->hits = 0;
344     p->eof = 0;
345     p->tailcount = 0;
346     if (is_and)
347     { /* read the array and sort it */
348         for (i = 0; i<ct->no_children; i++){
349             p->items[i].fd = rset_open(ct->children[i], RSETF_READ);
350             if (!rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
351                 p->eof = 1;
352             p->tailbits[i] = 0;
353         }
354         qsort(p->items, ct->no_children, sizeof(p->items[0]), compare_ands);
355     } else
356     { /* fill the heap for ORing */
357         for (i = 0; i<ct->no_children; i++){
358             p->items[i].fd = rset_open(ct->children[i],RSETF_READ);
359             if ( rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
360                 heap_insert(p->h, &(p->items[i]));
361         }
362     }
363     return rfd;
364 }
365
366 static RSFD r_open_or (RSET ct, int flag)
367 {
368     return r_open_andor(ct, flag, 0);
369 }
370
371 static RSFD r_open_and (RSET ct, int flag)
372 {
373     return r_open_andor(ct, flag, 1);
374 }
375
376
377 static void r_close (RSFD rfd)
378 {
379     struct rfd_private *p=(struct rfd_private *)(rfd->priv);
380     int i;
381
382     if (p->h)
383         heap_destroy (p->h);
384     for (i = 0; i<rfd->rset->no_children; i++) 
385         if (p->items[i].fd)
386             rset_close(p->items[i].fd);
387 }
388
389
390
391 static int r_forward_or(RSFD rfd, void *buf, 
392                         TERMID *term, const void *untilbuf)
393 { /* while heap head behind untilbuf, forward it and rebalance heap */
394     struct rfd_private *p = rfd->priv;
395     const struct rset_key_control *kctrl = rfd->rset->keycontrol;
396     if (heap_empty(p->h))
397         return 0;
398     while ( (*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
399     {
400         if (rset_forward(p->h->heap[1]->fd,p->h->heap[1]->buf,
401                          &p->h->heap[1]->term, untilbuf))
402             heap_balance(p->h);
403         else 
404         {
405             heap_delete(p->h);
406             if (heap_empty(p->h))
407                 return 0;
408         }
409
410     }
411     return r_read_or(rfd, buf, term);
412 }
413
414
415 static int r_read_or (RSFD rfd, void *buf, TERMID *term)
416 {
417     RSET rset = rfd->rset;
418     struct rfd_private *mrfd = rfd->priv;
419     const struct rset_key_control *kctrl = rset->keycontrol;
420     struct heap_item *it;
421     int rdres;
422     if (heap_empty(mrfd->h))
423         return 0;
424     it = mrfd->h->heap[1];
425     memcpy(buf, it->buf, kctrl->key_size);
426     if (term)
427     {
428         if (rset->term)
429             *term = rset->term;
430         else
431             *term = it->term;
432         assert(*term);
433     }
434     (mrfd->hits)++;
435     rdres = rset_read(it->fd, it->buf, &it->term);
436     if ( rdres )
437         heap_balance(mrfd->h);
438     else
439         heap_delete(mrfd->h);
440     return 1;
441
442 }
443
444 static int r_read_and (RSFD rfd, void *buf, TERMID *term)
445 { /* Has to return all hits where each item points to the */
446   /* same sysno (scope), in order. Keep an extra key (hitkey) */
447   /* as long as all records do not point to hitkey, forward */
448   /* them, and update hitkey to be the highest seen so far. */
449   /* (if any item eof's, mark eof, and return 0 thereafter) */
450   /* Once a hit has been found, scan all items for the smallest */
451   /* value. Mark all as being in the tail. Read next from that */
452   /* item, and if not in the same record, clear its tail bit */
453     struct rfd_private *p = rfd->priv;
454     RSET ct = rfd->rset;
455     const struct rset_key_control *kctrl = ct->keycontrol;
456     int i, mintail;
457     int cmp;
458
459     while (1) {
460         if (p->tailcount) 
461         { /* we are tailing, find lowest tail and return it */
462             mintail = 0;
463             while ((mintail<ct->no_children) && !p->tailbits[mintail])
464                 mintail++; /* first tail */
465             for (i = mintail+1; i<ct->no_children; i++)
466             {
467                 if (p->tailbits[i])
468                 {
469                     cmp=(*kctrl->cmp)(p->items[i].buf,p->items[mintail].buf);
470                     if (cmp<0) 
471                         mintail = i;
472                 }
473             }
474             /* return the lowest tail */
475             memcpy(buf, p->items[mintail].buf, kctrl->key_size); 
476             if (term)
477                 *term = p->items[mintail].term;
478             if (!rset_read(p->items[mintail].fd, p->items[mintail].buf,
479                            &p->items[mintail].term))
480             {
481                 p->eof = 1; /* game over, once tails have been returned */
482                 p->tailbits[mintail] = 0; 
483                 (p->tailcount)--;
484                 (p->hits)++;
485                 return 1;
486             }
487             /* still a tail? */
488             cmp = (*kctrl->cmp)(p->items[mintail].buf,buf);
489             if (cmp >= rfd->rset->scope){
490                 p->tailbits[mintail] = 0;
491                 (p->tailcount)--;
492             }
493             (p->hits)++;
494             return 1;
495         } 
496         /* not tailing, forward until all reocrds match, and set up */
497         /* as tails. the earlier 'if' will then return the hits */
498         if (p->eof)
499             return 0; /* nothing more to see */
500         i = 1; /* assume items[0] is highest up */
501         while (i<ct->no_children) {
502             cmp = (*kctrl->cmp)(p->items[0].buf, p->items[i].buf);
503             if (cmp <= -rfd->rset->scope) { /* [0] was behind, forward it */
504                 if (!rset_forward(p->items[0].fd, p->items[0].buf, 
505                                   &p->items[0].term, p->items[i].buf))
506                 {
507                     p->eof = 1; /* game over */
508                     return 0;
509                 }
510                 i = 0; /* start frowarding from scratch */
511             } else if (cmp>=rfd->rset->scope)
512             { /* [0] was ahead, forward i */
513                 if (!rset_forward(p->items[i].fd, p->items[i].buf, 
514                                   &p->items[i].term, p->items[0].buf))
515                 {
516                     p->eof = 1; /* game over */
517                     return 0;
518                 }
519             } else
520                 i++;
521         } /* while i */
522         /* if we get this far, all rsets are now within +- scope of [0] */
523         /* ergo, we have a hit. Mark them all as tailing, and let the */
524         /* upper 'if' return the hits in right order */
525         for (i = 0; i<ct->no_children; i++)
526             p->tailbits[i] = 1;
527         p->tailcount = ct->no_children;
528     } /* while 1 */
529 }
530
531
532 static int r_forward_and(RSFD rfd, void *buf, TERMID *term, 
533                          const void *untilbuf)
534
535     struct rfd_private *p = rfd->priv;
536     RSET ct = rfd->rset;
537     const struct rset_key_control *kctrl = ct->keycontrol;
538     int i;
539     int cmp;
540     int killtail = 0;
541
542     for (i = 0; i<ct->no_children; i++)
543     {
544         cmp = (*kctrl->cmp)(p->items[i].buf,untilbuf);
545         if (cmp <= -rfd->rset->scope)
546         {
547             killtail = 1; /* we are moving to a different hit */
548             if (!rset_forward(p->items[i].fd, p->items[i].buf, 
549                               &p->items[i].term, untilbuf))
550             {
551                 p->eof = 1; /* game over */
552                 p->tailcount = 0;
553                 return 0;
554             }
555         }
556     }
557     if (killtail) 
558     {
559         for (i = 0; i<ct->no_children; i++)
560             p->tailbits[i] = 0;
561         p->tailcount = 0;
562     }
563     return r_read_and(rfd,buf,term);
564 }
565
566 static void r_pos (RSFD rfd, double *current, double *total)
567 {
568     RSET ct = rfd->rset;
569     struct rfd_private *mrfd = 
570         (struct rfd_private *)(rfd->priv);
571     double cur, tot;
572     double scur = 0.0, stot = 0.0;
573     int i;
574     for (i = 0; i<ct->no_children; i++){
575         rset_pos(mrfd->items[i].fd, &cur, &tot);
576         yaz_log(log_level, "r_pos: %d %0.1f %0.1f", i, cur,tot); 
577         scur += cur;
578         stot += tot;
579     }
580     if (stot < 1.0) { /* nothing there */
581         *current = 0;
582         *total = 0;
583         yaz_log(log_level, "r_pos: NULL  %0.1f %0.1f",  *current, *total);
584     }
585     else
586     {
587         *current = (double) (mrfd->hits);
588         *total = *current*stot/scur;
589         yaz_log(log_level, "r_pos: =  %0.1f %0.1f",  *current, *total);
590     }
591 }
592
593 static int r_write (RSFD rfd, const void *buf)
594 {
595     yaz_log (YLOG_FATAL, "multior set type is read-only");
596     return -1;
597 }
598
599 static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm)
600 {
601     if (ct->term)
602         rset_get_one_term(ct, terms, maxterms, curterm);
603     else
604     {
605         /* Special case: Some multi-ors have all terms pointing to the same 
606            term. We do not want to duplicate those. Other multiors (and ands)
607            have different terms under them. Those we want. 
608         */
609         int firstterm= *curterm;
610         int i;
611
612         for (i = 0; i<ct->no_children; i++)
613         {
614             rset_getterms(ct->children[i], terms, maxterms, curterm);
615             if ( ( *curterm > firstterm+1 ) &&
616                  ( *curterm <= maxterms ) &&
617                  ( terms[(*curterm)-1] == terms[firstterm] ) 
618                 )
619                 (*curterm)--; /* forget the term, seen that before */
620         }
621     }
622 }
623
624
625 /*
626  * Local variables:
627  * c-basic-offset: 4
628  * indent-tabs-mode: nil
629  * End:
630  * vim: shiftwidth=4 tabstop=8 expandtab
631  */
632