1 /* $Id: rsmultiandor.c,v 1.1 2004-09-28 13:06:35 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 void r_rewind (RSFD rfd);
51 static int r_read_and (RSFD rfd, void *buf);
52 static int r_read_or (RSFD rfd, void *buf);
53 static int r_write (RSFD rfd, const void *buf);
54 static int r_forward_and(RSFD rfd, void *buf,
55 const void *untilbuf);
56 static int r_forward_or(RSFD rfd, void *buf,
57 const void *untilbuf);
58 static void r_pos (RSFD rfd, double *current, double *total);
60 static const struct rset_control control_or =
72 static const struct rset_control control_and =
85 const struct rset_control *rset_kind_multior = &control_or;
86 const struct rset_control *rset_kind_multiand = &control_and;
88 /* The heap structure:
89 * The rset contains a list or rsets we are ORing together
90 * The rfd contains a heap of heap-items, which contain
91 * a rfd opened to those rsets, and a buffer for one key.
92 * They also contain a ptr to the rset list in the rset
93 * itself, for practical reasons.
105 const struct key_control *kctrl;
106 struct heap_item **heap; /* ptrs to the rfd */
108 typedef struct heap *HEAP;
111 struct rset_multiandor_info {
117 struct rset_multiandor_rfd {
119 struct heap_item *items; /* we alloc and free them here */
121 zint hits; /* returned so far */
122 int eof; /* seen the end of it */
125 /* Heap functions ***********************/
128 static void heap_dump_item( HEAP h, int i, int level) {
132 (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
133 logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
134 &(h->heap[i]), h->heap[i]->buf, cur,tot );
135 heap_dump_item(h, 2*i, level+1);
136 heap_dump_item(h, 2*i+1, level+1);
138 static void heap_dump( HEAP h,char *msg) {
139 logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
140 heap_dump_item(h,1,1);
144 static void heap_swap (HEAP h, int x, int y)
146 struct heap_item *swap;
148 h->heap[x]=h->heap[y];
152 static int heap_cmp(HEAP h, int x, int y)
154 return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
157 static int heap_empty(HEAP h)
159 return ( 0==h->heapnum );
162 static void heap_delete (HEAP h)
163 { /* deletes the first item in the heap, and balances the rest */
164 int cur = 1, child = 2;
165 h->heap[1]=0; /* been deleted */
166 heap_swap (h, 1, h->heapnum--);
167 while (child <= h->heapnum) {
168 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
170 if (heap_cmp(h,cur,child) > 0)
172 heap_swap (h, cur, child);
181 static void heap_balance (HEAP h)
182 { /* The heap root element has changed value (to bigger) */
183 /* swap downwards until the heap is ordered again */
184 int cur = 1, child = 2;
185 while (child <= h->heapnum) {
186 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
188 if (heap_cmp(h,cur,child) > 0)
190 heap_swap (h, cur, child);
200 static void heap_insert (HEAP h, struct heap_item *hi)
204 cur = ++(h->heapnum);
205 assert(cur <= h->heapmax);
208 while (parent && (heap_cmp(h,parent,cur) > 0))
211 heap_swap (h, cur, parent);
219 HEAP heap_create (NMEM nmem, int size, const struct key_control *kctrl)
221 HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
223 ++size; /* heap array starts at 1 */
227 h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
228 h->heap[0]=0; /* not used */
232 static void heap_clear( HEAP h)
238 static void heap_destroy (HEAP h)
240 /* nothing to delete, all is nmem'd, and will go away in due time */
244 /* Creating and deleting rsets ***********************/
246 static RSET rsmulti_andor_create( NMEM nmem, const struct key_control *kcontrol,
247 int scope, int no_rsets, RSET* rsets,
248 const struct rset_control *ctrl)
250 RSET rnew=rset_create_base(ctrl, nmem,kcontrol, scope);
251 struct rset_multiandor_info *info;
252 info = (struct rset_multiandor_info *) nmem_malloc(rnew->nmem,sizeof(*info));
253 info->no_rsets=no_rsets;
254 info->rsets=(RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
255 memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
260 RSET rsmultior_create( NMEM nmem, const struct key_control *kcontrol, int scope,
261 int no_rsets, RSET* rsets)
263 return rsmulti_andor_create(nmem, kcontrol, scope,
264 no_rsets, rsets, &control_or);
267 RSET rsmultiand_create( NMEM nmem, const struct key_control *kcontrol, int scope,
268 int no_rsets, RSET* rsets)
270 return rsmulti_andor_create(nmem, kcontrol, scope,
271 no_rsets, rsets, &control_and);
274 static void r_delete (RSET ct)
276 struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
278 for(i=0;i<info->no_rsets;i++)
279 rset_delete(info->rsets[i]);
282 /* Opening and closing fd's on them *********************/
284 static RSFD r_open_andor (RSET ct, int flag, int is_and)
287 struct rset_multiandor_rfd *p;
288 struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
289 const struct key_control *kctrl = ct->keycontrol;
292 if (flag & RSETF_WRITE)
294 logf (LOG_FATAL, "multior set type is read-only");
297 rfd=rfd_create_base(ct);
299 p=(struct rset_multiandor_rfd *)rfd->priv;
302 /* all other pointers shouls already be allocated, in right sizes! */
305 p = (struct rset_multiandor_rfd *) nmem_malloc (ct->nmem,sizeof(*p));
307 p->h = heap_create( ct->nmem, info->no_rsets, kctrl);
308 p->items=(struct heap_item *) nmem_malloc(ct->nmem,
309 info->no_rsets*sizeof(*p->items));
310 for (i=0; i<info->no_rsets; i++){
311 p->items[i].rset=info->rsets[i];
312 p->items[i].buf=nmem_malloc(ct->nmem,kctrl->key_size);
319 { /* read the array and sort it */
320 for (i=0; i<info->no_rsets; i++){
321 p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
322 if ( !rset_read(p->items[i].fd, p->items[i].buf) )
326 { /* fill the heap for ORing */
327 for (i=0; i<info->no_rsets; i++){
328 p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
329 if ( rset_read(p->items[i].fd, p->items[i].buf) )
330 heap_insert(p->h, &(p->items[i]));
336 static RSFD r_open_or (RSET ct, int flag)
338 return r_open_andor(ct, flag, 0);
341 static RSFD r_open_and (RSET ct, int flag)
343 return r_open_andor(ct, flag, 1);
347 static void r_close (RSFD rfd)
349 struct rset_multiandor_info *info=(struct rset_multiandor_info *)(rfd->rset->priv);
350 struct rset_multiandor_rfd *p=(struct rset_multiandor_rfd *)(rfd->priv);
354 for (i = 0; i<info->no_rsets; i++)
356 rset_close(p->items[i].fd);
357 rfd_delete_base(rfd);
362 static int r_forward_or(RSFD rfd, void *buf, const void *untilbuf)
364 struct rset_multiandor_rfd *mrfd=rfd->priv;
365 const struct key_control *kctrl=rfd->rset->keycontrol;
368 if (heap_empty(mrfd->h))
370 it = *(mrfd->h->heap[1]);
371 memcpy(buf,it.buf, kctrl->key_size);
372 /* FIXME - This is not right ! */
373 /* If called with an untilbuf, we need to compare to that, and */
374 /* forward until we are somewhere! */
377 rdres=rset_forward(it.fd, it.buf, untilbuf);
379 rdres=rset_read(it.fd, it.buf);
381 heap_balance(mrfd->h);
383 heap_delete(mrfd->h);
388 static int r_read_or (RSFD rfd, void *buf)
390 return r_forward_or(rfd, buf,0);
393 static int r_read_and (RSFD rfd, void *buf)
397 static int r_forward_and(RSFD rfd, void *buf, const void *untilbuf)
402 static void r_pos (RSFD rfd, double *current, double *total)
404 struct rset_multiandor_info *info=
405 (struct rset_multiandor_info *)(rfd->rset->priv);
406 struct rset_multiandor_rfd *mrfd=(struct rset_multiandor_rfd *)(rfd->priv);
408 double scur=0.0, stot=0.0;
410 for (i=0; i<info->no_rsets; i++){
411 rset_pos(mrfd->items[i].fd, &cur, &tot);
412 logf(LOG_LOG, "r_pos: %d %0.1f %0.1f", i, cur,tot);
416 if (stot <1.0) { /* nothing there */
422 *total=*current*stot/scur;
426 static void r_rewind (RSFD rfd)
428 assert(!"rewind not implemented yet");
429 /* FIXME - rewind all parts, rebalance heap, clear hits */
432 static int r_write (RSFD rfd, const void *buf)
434 logf (LOG_FATAL, "multior set type is read-only");