1 /* $Id: rsmultiandor.c,v 1.5 2004-09-30 09:53:05 heikki Exp $
2 Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
5 This file is part of the Zebra server.
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
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
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
25 * This module implements the rsmultior and rsmultiand result sets
27 * rsmultior is based on a heap, from which we find the next hit.
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.
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);
51 static int r_read_or (RSFD rfd, void *buf);
52 static int r_write (RSFD rfd, const void *buf);
53 static int r_forward_and(RSFD rfd, void *buf,
54 const void *untilbuf);
55 static int r_forward_or(RSFD rfd, void *buf,
56 const void *untilbuf);
57 static void r_pos (RSFD rfd, double *current, double *total);
59 static const struct rset_control control_or =
70 static const struct rset_control control_and =
82 const struct rset_control *rset_kind_multior = &control_or;
83 const struct rset_control *rset_kind_multiand = &control_and;
85 /* The heap structure:
86 * The rset contains a list or rsets we are ORing together
87 * The rfd contains a heap of heap-items, which contain
88 * a rfd opened to those rsets, and a buffer for one key.
89 * They also contain a ptr to the rset list in the rset
90 * itself, for practical reasons.
102 const struct key_control *kctrl;
103 struct heap_item **heap; /* ptrs to the rfd */
105 typedef struct heap *HEAP;
108 struct rset_multiandor_info {
114 struct rset_multiandor_rfd {
116 struct heap_item *items; /* we alloc and free them here */
117 HEAP h; /* and move around here */
118 zint hits; /* returned so far */
119 int eof; /* seen the end of it */
120 int tailcount; /* how many items are tailing */
124 /* Heap functions ***********************/
127 static void heap_dump_item( HEAP h, int i, int level) {
131 (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
132 logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
133 &(h->heap[i]), h->heap[i]->buf, cur,tot );
134 heap_dump_item(h, 2*i, level+1);
135 heap_dump_item(h, 2*i+1, level+1);
137 static void heap_dump( HEAP h,char *msg) {
138 logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
139 heap_dump_item(h,1,1);
143 static void heap_swap (HEAP h, int x, int y)
145 struct heap_item *swap;
147 h->heap[x]=h->heap[y];
151 static int heap_cmp(HEAP h, int x, int y)
153 return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
156 static int heap_empty(HEAP h)
158 return ( 0==h->heapnum );
161 static void heap_delete (HEAP h)
162 { /* deletes the first item in the heap, and balances the rest */
163 int cur = 1, child = 2;
164 h->heap[1]=0; /* been deleted */
165 heap_swap (h, 1, h->heapnum--);
166 while (child <= h->heapnum) {
167 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
169 if (heap_cmp(h,cur,child) > 0)
171 heap_swap (h, cur, child);
180 static void heap_balance (HEAP h)
181 { /* The heap root element has changed value (to bigger) */
182 /* swap downwards until the heap is ordered again */
183 int cur = 1, child = 2;
184 while (child <= h->heapnum) {
185 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
187 if (heap_cmp(h,cur,child) > 0)
189 heap_swap (h, cur, child);
199 static void heap_insert (HEAP h, struct heap_item *hi)
203 cur = ++(h->heapnum);
204 assert(cur <= h->heapmax);
207 while (parent && (heap_cmp(h,parent,cur) > 0))
210 heap_swap (h, cur, parent);
218 HEAP heap_create (NMEM nmem, int size, const struct key_control *kctrl)
220 HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
222 ++size; /* heap array starts at 1 */
226 h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
227 h->heap[0]=0; /* not used */
231 static void heap_clear( HEAP h)
237 static void heap_destroy (HEAP h)
239 /* nothing to delete, all is nmem'd, and will go away in due time */
242 int compare_ands(const void *x, const void *y)
243 { /* used in qsort to get the multi-and args in optimal order */
244 /* that is, those with fewest occurrences first */
245 const struct heap_item *hx=x;
246 const struct heap_item *hy=y;
247 double cur, totx, toty;
248 rset_pos(hx->fd, &cur, &totx);
249 rset_pos(hy->fd, &cur, &toty);
250 if ( totx > toty +0.5 ) return 1;
251 if ( totx < toty -0.5 ) return -1;
252 return 0; /* return totx - toty, except for overflows and rounding */
255 /* Creating and deleting rsets ***********************/
257 static RSET rsmulti_andor_create( NMEM nmem, const struct key_control *kcontrol,
258 int scope, int no_rsets, RSET* rsets,
259 const struct rset_control *ctrl)
261 RSET rnew=rset_create_base(ctrl, nmem,kcontrol, scope);
262 struct rset_multiandor_info *info;
263 info = (struct rset_multiandor_info *) nmem_malloc(rnew->nmem,sizeof(*info));
264 info->no_rsets=no_rsets;
265 info->rsets=(RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
266 memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
271 RSET rsmultior_create( NMEM nmem, const struct key_control *kcontrol, int scope,
272 int no_rsets, RSET* rsets)
274 return rsmulti_andor_create(nmem, kcontrol, scope,
275 no_rsets, rsets, &control_or);
278 RSET rsmultiand_create( NMEM nmem, const struct key_control *kcontrol, int scope,
279 int no_rsets, RSET* rsets)
281 return rsmulti_andor_create(nmem, kcontrol, scope,
282 no_rsets, rsets, &control_and);
285 static void r_delete (RSET ct)
287 struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
289 for(i=0;i<info->no_rsets;i++)
290 rset_delete(info->rsets[i]);
294 /* Opening and closing fd's on them *********************/
296 static RSFD r_open_andor (RSET ct, int flag, int is_and)
299 struct rset_multiandor_rfd *p;
300 struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
301 const struct key_control *kctrl = ct->keycontrol;
304 if (flag & RSETF_WRITE)
306 logf (LOG_FATAL, "multiandor set type is read-only");
309 rfd=rfd_create_base(ct);
311 p=(struct rset_multiandor_rfd *)rfd->priv;
315 /* all other pointers shouls already be allocated, in right sizes! */
318 p = (struct rset_multiandor_rfd *) nmem_malloc (ct->nmem,sizeof(*p));
323 p->tailbits=nmem_malloc(ct->nmem, info->no_rsets*sizeof(char) );
325 p->h = heap_create( ct->nmem, info->no_rsets, kctrl);
326 p->items=(struct heap_item *) nmem_malloc(ct->nmem,
327 info->no_rsets*sizeof(*p->items));
328 for (i=0; i<info->no_rsets; i++){
329 p->items[i].rset=info->rsets[i];
330 p->items[i].buf=nmem_malloc(ct->nmem,kctrl->key_size);
338 { /* read the array and sort it */
339 for (i=0; i<info->no_rsets; i++){
340 p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
341 if ( !rset_read(p->items[i].fd, p->items[i].buf) )
345 qsort(p->items, info->no_rsets, sizeof(p->items[0]), compare_ands);
347 { /* fill the heap for ORing */
348 for (i=0; i<info->no_rsets; i++){
349 p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
350 if ( rset_read(p->items[i].fd, p->items[i].buf) )
351 heap_insert(p->h, &(p->items[i]));
357 static RSFD r_open_or (RSET ct, int flag)
359 return r_open_andor(ct, flag, 0);
362 static RSFD r_open_and (RSET ct, int flag)
364 return r_open_andor(ct, flag, 1);
368 static void r_close (RSFD rfd)
370 struct rset_multiandor_info *info=
371 (struct rset_multiandor_info *)(rfd->rset->priv);
372 struct rset_multiandor_rfd *p=(struct rset_multiandor_rfd *)(rfd->priv);
377 for (i = 0; i<info->no_rsets; i++)
379 rset_close(p->items[i].fd);
380 rfd_delete_base(rfd);
385 static int r_forward_or(RSFD rfd, void *buf, const void *untilbuf)
386 { /* while heap head behind untilbuf, forward it and rebalance heap */
387 struct rset_multiandor_rfd *p=rfd->priv;
388 const struct key_control *kctrl=rfd->rset->keycontrol;
389 if (heap_empty(p->h))
391 while ( (*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
393 if ( rset_forward(p->h->heap[1]->fd, p->h->heap[1]->buf, untilbuf) )
398 if (heap_empty(p->h))
403 return r_read_or(rfd,buf);
407 static int r_read_or (RSFD rfd, void *buf)
409 struct rset_multiandor_rfd *mrfd=rfd->priv;
410 const struct key_control *kctrl=rfd->rset->keycontrol;
411 struct heap_item *it;
413 if (heap_empty(mrfd->h))
415 it = mrfd->h->heap[1];
416 memcpy(buf,it->buf, kctrl->key_size);
418 rdres=rset_read(it->fd, it->buf);
420 heap_balance(mrfd->h);
422 heap_delete(mrfd->h);
427 static int r_read_and (RSFD rfd, void *buf)
428 { /* Has to return all hits where each item points to the */
429 /* same sysno (scope), in order. Keep an extra key (hitkey) */
430 /* as long as all records do not point to hitkey, forward */
431 /* them, and update hitkey to be the highest seen so far. */
432 /* (if any item eof's, mark eof, and return 0 thereafter) */
433 /* Once a hit has been found, scan all items for the smallest */
434 /* value. Mark all as being in the tail. Read next from that */
435 /* item, and if not in the same record, clear its tail bit */
436 struct rset_multiandor_rfd *p=rfd->priv;
437 const struct key_control *kctrl=rfd->rset->keycontrol;
438 struct rset_multiandor_info *info=rfd->rset->priv;
444 { /* we are tailing, find lowest tail and return it */
446 while ((mintail<info->no_rsets) && !p->tailbits[mintail])
447 mintail++; /* first tail */
448 for (i=mintail+1;i<info->no_rsets;i++)
452 cmp=(*kctrl->cmp)(p->items[i].buf,p->items[mintail].buf);
457 /* return the lowest tail */
458 memcpy(buf, p->items[mintail].buf, kctrl->key_size);
459 if (!rset_read(p->items[mintail].fd, p->items[mintail].buf))
461 p->eof=1; /* game over, once tails have been returned */
462 p->tailbits[mintail]=0;
467 cmp=(*kctrl->cmp)(p->items[mintail].buf,buf);
468 if (cmp >= rfd->rset->scope){
469 p->tailbits[mintail]=0;
474 /* not tailing, forward until all reocrds match, and set up */
475 /* as tails. the earlier 'if' will then return the hits */
477 return 0; /* nothing more to see */
478 i=1; /* assume items[0] is highest up */
479 while (i<info->no_rsets) {
480 cmp=(*kctrl->cmp)(p->items[0].buf,p->items[i].buf);
481 if (cmp<=-rfd->rset->scope) { /* [0] was behind, forward it */
482 if (!rset_forward(p->items[0].fd, p->items[0].buf,
485 p->eof=1; /* game over */
488 i=0; /* start frowarding from scratch */
489 } else if (cmp>=rfd->rset->scope)
490 { /* [0] was ahead, forward i */
491 if (!rset_forward(p->items[i].fd, p->items[i].buf,
494 p->eof=1; /* game over */
500 /* if we get this far, all rsets are now within +- scope of [0] */
501 /* ergo, we have a hit. Mark them all as tailing, and let the */
502 /* upper 'if' return the hits in right order */
503 for (i=0; i<info->no_rsets;i++)
505 p->tailcount=info->no_rsets;
510 static int r_forward_and(RSFD rfd, void *buf, const void *untilbuf)
512 struct rset_multiandor_rfd *p=rfd->priv;
513 const struct key_control *kctrl=rfd->rset->keycontrol;
514 struct rset_multiandor_info *info=rfd->rset->priv;
519 for (i=0; i<info->no_rsets;i++)
521 cmp=(*kctrl->cmp)(p->items[i].buf,untilbuf);
522 if ( cmp <= -rfd->rset->scope )
524 killtail=1; /* we are moving to a different hit */
525 if (!rset_forward(p->items[i].fd, p->items[i].buf,
528 p->eof=1; /* game over */
536 for (i=0; i<info->no_rsets;i++)
540 return r_read_and(rfd,buf);
543 static void r_pos (RSFD rfd, double *current, double *total)
545 struct rset_multiandor_info *info=
546 (struct rset_multiandor_info *)(rfd->rset->priv);
547 struct rset_multiandor_rfd *mrfd=(struct rset_multiandor_rfd *)(rfd->priv);
549 double scur=0.0, stot=0.0;
551 for (i=0; i<info->no_rsets; i++){
552 rset_pos(mrfd->items[i].fd, &cur, &tot);
553 logf(LOG_DEBUG, "r_pos: %d %0.1f %0.1f", i, cur,tot);
557 if (stot <1.0) { /* nothing there */
563 *total=*current*stot/scur;
568 static int r_write (RSFD rfd, const void *buf)
570 logf (LOG_FATAL, "multior set type is read-only");