1 /* $Id: rsmultior.c,v 1.10 2004-09-09 10:08:06 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
35 static RSFD r_open (RSET ct, int flag);
36 static void r_close (RSFD rfd);
37 static void r_delete (RSET ct);
38 static void r_rewind (RSFD rfd);
39 static int r_read (RSFD rfd, void *buf);
40 static int r_write (RSFD rfd, const void *buf);
41 static int r_forward(RSFD rfd, void *buf,
42 const void *untilbuf);
43 static void r_pos (RSFD rfd, double *current, double *total);
45 static const struct rset_control control =
58 const struct rset_control *rset_kind_multior = &control;
60 /* The heap structure:
61 * The rset contains a list or rsets we are ORing together
62 * The rfd contains a heap of heap-items, which contain
63 * a rfd opened to those rsets, and a buffer for one key.
64 * They also contain a ptr to the rset list in the rset
65 * itself, for practical reasons.
77 const struct key_control *kctrl;
78 struct heap_item **heap; /* ptrs to the rfd */
80 typedef struct heap *HEAP;
83 struct rset_multior_info {
89 struct rset_multior_rfd {
91 struct heap_item *items; /* we alloc and free them here */
93 zint hits; /* returned so far */
97 static void heap_dump_item( HEAP h, int i, int level) {
101 (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
102 logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
103 &(h->heap[i]), h->heap[i]->buf, cur,tot );
104 heap_dump_item(h, 2*i, level+1);
105 heap_dump_item(h, 2*i+1, level+1);
107 static void heap_dump( HEAP h,char *msg) {
108 logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
109 heap_dump_item(h,1,1);
113 static void heap_swap (HEAP h, int x, int y)
115 struct heap_item *swap;
117 h->heap[x]=h->heap[y];
121 static int heap_cmp(HEAP h, int x, int y)
123 return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
126 static int heap_empty(HEAP h)
128 return ( 0==h->heapnum );
131 static void heap_delete (HEAP h)
132 { /* deletes the first item in the heap, and balances the rest */
133 int cur = 1, child = 2;
134 h->heap[1]=0; /* been deleted */
135 heap_swap (h, 1, h->heapnum--);
136 while (child <= h->heapnum) {
137 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
139 if (heap_cmp(h,cur,child) > 0)
141 heap_swap (h, cur, child);
150 static void heap_balance (HEAP h)
151 { /* The heap root element has changed value (to bigger) */
152 /* swap downwards until the heap is ordered again */
153 int cur = 1, child = 2;
154 while (child <= h->heapnum) {
155 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
157 if (heap_cmp(h,cur,child) > 0)
159 heap_swap (h, cur, child);
169 static void heap_insert (HEAP h, struct heap_item *hi)
173 cur = ++(h->heapnum);
174 assert(cur <= h->heapmax);
177 while (parent && (heap_cmp(h,parent,cur) > 0))
180 heap_swap (h, cur, parent);
188 HEAP heap_create (NMEM nmem, int size, const struct key_control *kctrl)
190 HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
192 ++size; /* heap array starts at 1 */
196 h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
197 h->heap[0]=0; /* not used */
201 static void heap_clear( HEAP h)
207 static void heap_destroy (HEAP h)
209 /* nothing to delete, all is nmem'd, and will go away in due time */
213 RSET rsmultior_create( NMEM nmem, const struct key_control *kcontrol, int scope,
214 int no_rsets, RSET* rsets)
216 RSET rnew=rset_create_base(&control, nmem,kcontrol, scope);
217 struct rset_multior_info *info;
218 info = (struct rset_multior_info *) nmem_malloc(rnew->nmem,sizeof(*info));
219 info->no_rsets=no_rsets;
220 info->rsets=(RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
221 memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
226 static void r_delete (RSET ct)
228 struct rset_multior_info *info = (struct rset_multior_info *) ct->priv;
230 for(i=0;i<info->no_rsets;i++)
231 rset_delete(info->rsets[i]);
234 static RSFD r_open (RSET ct, int flag)
237 struct rset_multior_rfd *p;
238 struct rset_multior_info *info = (struct rset_multior_info *) ct->priv;
239 const struct key_control *kctrl = ct->keycontrol;
242 if (flag & RSETF_WRITE)
244 logf (LOG_FATAL, "multior set type is read-only");
247 rfd=rfd_create_base(ct);
249 p=(struct rset_multior_rfd *)rfd->priv;
252 /* all other pointers shouls already be allocated, in right sizes! */
255 p = (struct rset_multior_rfd *) nmem_malloc (ct->nmem,sizeof(*p));
257 p->h = heap_create( ct->nmem, info->no_rsets, kctrl);
258 p->items=(struct heap_item *) nmem_malloc(ct->nmem,
259 info->no_rsets*sizeof(*p->items));
260 for (i=0; i<info->no_rsets; i++){
261 p->items[i].rset=info->rsets[i];
262 p->items[i].buf=nmem_malloc(ct->nmem,kctrl->key_size);
267 for (i=0; i<info->no_rsets; i++){
268 p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
269 if ( rset_read(p->items[i].fd, p->items[i].buf) )
270 heap_insert(p->h, &(p->items[i]));
275 static void r_close (RSFD rfd)
277 struct rset_multior_info *info=(struct rset_multior_info *)(rfd->rset->priv);
278 struct rset_multior_rfd *p=(struct rset_multior_rfd *)(rfd->priv);
282 for (i = 0; i<info->no_rsets; i++)
284 rset_close(p->items[i].fd);
285 rfd_delete_base(rfd);
289 static void r_rewind (RSFD rfd)
291 assert(!"rewind not implemented yet");
295 static int r_forward(RSFD rfd, void *buf, const void *untilbuf)
297 struct rset_multior_rfd *mrfd=rfd->priv;
298 const struct key_control *kctrl=rfd->rset->keycontrol;
301 if (heap_empty(mrfd->h))
303 it = *(mrfd->h->heap[1]);
304 memcpy(buf,it.buf, kctrl->key_size);
307 rdres=rset_forward(it.fd, it.buf, untilbuf);
309 rdres=rset_read(it.fd, it.buf);
311 heap_balance(mrfd->h);
313 heap_delete(mrfd->h);
318 static int r_read (RSFD rfd, void *buf)
320 return r_forward(rfd, buf,0);
323 static void r_pos (RSFD rfd, double *current, double *total)
325 struct rset_multior_info *info=(struct rset_multior_info *)(rfd->rset->priv);
326 struct rset_multior_rfd *mrfd=(struct rset_multior_rfd *)(rfd->priv);
328 double scur=0.0, stot=0.0;
330 for (i=0; i<info->no_rsets; i++){
331 rset_pos(mrfd->items[i].fd, &cur, &tot);
332 logf(LOG_LOG, "r_pos: %d %0.1f %0.1f", i, cur,tot);
336 if (stot <1.0) { /* nothing there */
342 *total=*current*stot/scur;
345 static int r_write (RSFD rfd, const void *buf)
347 logf (LOG_FATAL, "multior set type is read-only");