1 /* $Id: rsmultior.c,v 1.7 2004-08-26 11:11:59 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
33 #include <rsmultior.h>
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(RSET ct, RSFD rfd, void *buf,
42 int (*cmpfunc)(const void *p1, const void *p2),
43 const void *untilbuf);
44 static void r_pos (RSFD rfd, double *current, double *total);
46 static const struct rset_control control =
59 const struct rset_control *rset_kind_multior = &control;
61 /* The heap structure:
62 * The rset contains a list or rsets we are ORing together
63 * The rfd contains a heap of heap-items, which contain
64 * a rfd opened to those rsets, and a buffer for one key.
65 * They also contain a ptr to the rset list in the rset
66 * itself, for practical reasons.
79 int (*cmp)(const void *p1, const void *p2);
80 struct heap_item **heap; /* ptrs to the rfd */
82 typedef struct heap *HEAP;
85 struct rset_multior_info {
88 int (*cmp)(const void *p1, const void *p2);
91 struct rset_multior_rfd *rfd_list; /* rfds in use */
92 struct rset_multior_rfd *free_list; /* rfds free */
93 /* rfds are allocated when first opened, if nothing in freelist */
94 /* when allocated, all their pointers are allocated as well, and */
95 /* those are kept intact when in the freelist, ready to be reused */
99 struct rset_multior_rfd {
101 struct heap_item *items; /* we alloc and free them here */
103 struct rset_multior_rfd *next;
104 struct rset_multior_info *info;
105 zint hits; /* returned so far */
106 char *prevvalue; /* to see if we are in another record */
107 /* FIXME - is this really needed? */
111 static void heap_dump_item( HEAP h, int i, int level) {
115 (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
116 logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
117 &(h->heap[i]), h->heap[i]->buf, cur,tot );
118 heap_dump_item(h, 2*i, level+1);
119 heap_dump_item(h, 2*i+1, level+1);
121 static void heap_dump( HEAP h,char *msg) {
122 logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
123 heap_dump_item(h,1,1);
127 static void heap_swap (HEAP h, int x, int y)
129 struct heap_item *swap;
131 h->heap[x]=h->heap[y];
135 static int heap_cmp(HEAP h, int x, int y)
137 return (*h->cmp)(h->heap[x]->buf,h->heap[y]->buf);
140 static int heap_empty(HEAP h)
142 return ( 0==h->heapnum );
145 static void heap_delete (HEAP h)
146 { /* deletes the first item in the heap, and balances the rest */
147 int cur = 1, child = 2;
148 h->heap[1]=0; /* been deleted */
149 heap_swap (h, 1, h->heapnum--);
150 while (child <= h->heapnum) {
151 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
153 if (heap_cmp(h,cur,child) > 0)
155 heap_swap (h, cur, child);
164 static void heap_balance (HEAP h)
165 { /* The heap root element has changed value (to bigger) */
166 /* swap downwards until the heap is ordered again */
167 int cur = 1, child = 2;
168 while (child <= h->heapnum) {
169 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
171 if (heap_cmp(h,cur,child) > 0)
173 heap_swap (h, cur, child);
183 static void heap_insert (HEAP h, struct heap_item *hi)
187 cur = ++(h->heapnum);
188 assert(cur <= h->heapmax);
191 while (parent && (heap_cmp(h,parent,cur) > 0))
194 heap_swap (h, cur, parent);
202 HEAP heap_create (NMEM nmem, int size, int key_size,
203 int (*cmp)(const void *p1, const void *p2))
205 HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
207 ++size; /* heap array starts at 1 */
210 h->keysize = key_size;
212 h->heap = (struct heap_item**) nmem_malloc(nmem,(size)*sizeof(*h->heap));
213 h->heap[0]=0; /* not used */
217 static void heap_clear( HEAP h)
223 static void heap_destroy (HEAP h)
225 /* nothing to delete, all is nmem'd, and will go away in due time */
229 RSET rsmultior_create( NMEM nmem, int key_size,
230 int (*cmp)(const void *p1, const void *p2),
231 int no_rsets, RSET* rsets)
233 RSET rnew=rset_create_base(&control, nmem);
234 struct rset_multior_info *info;
235 info = (struct rset_multior_info *) nmem_malloc(rnew->nmem,sizeof(*info));
236 info->key_size = key_size;
238 info->no_rsets=no_rsets;
239 info->rsets=(RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
240 memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
241 info->rfd_list = NULL;
242 info->free_list = NULL;
247 static void r_delete (RSET ct)
249 struct rset_multior_info *info = (struct rset_multior_info *) ct->priv;
252 assert (info->rfd_list == NULL);
253 for(i=0;i<info->no_rsets;i++)
254 rset_delete(info->rsets[i]);
257 static void *r_create (RSET ct, const struct rset_control *sel, void *parms)
259 rset_multior_parms *r_parms = (rset_multior_parms *) parms;
260 struct rset_multior_info *info;
261 info = (struct rset_multior_info *) xmalloc (sizeof(*info));
262 info->key_size = r_parms->key_size;
263 assert (info->key_size > 1);
264 info->cmp = r_parms->cmp;
265 info->no_rsets= r_parms->no_rsets;
266 info->rsets=r_parms->rsets; /* now we own it! */
272 static RSFD r_open (RSET ct, int flag)
274 struct rset_multior_rfd *rfd;
275 struct rset_multior_info *info = (struct rset_multior_info *) ct->priv;
278 if (flag & RSETF_WRITE)
280 logf (LOG_FATAL, "multior set type is read-only");
285 info->free_list=rfd->next;
288 /* all other pointers shouls already be allocated, in right sizes! */
291 rfd = (struct rset_multior_rfd *) nmem_malloc (ct->nmem,sizeof(*rfd));
292 rfd->h = heap_create( ct->nmem, info->no_rsets,
293 info->key_size, info->cmp);
294 rfd->items=(struct heap_item *) nmem_malloc(ct->nmem,
295 info->no_rsets*sizeof(*rfd->items));
296 for (i=0; i<info->no_rsets; i++){
297 rfd->items[i].rset=info->rsets[i];
298 rfd->items[i].buf=nmem_malloc(ct->nmem,info->key_size);
302 rfd->next = info->rfd_list;
304 info->rfd_list = rfd;
307 for (i=0; i<info->no_rsets; i++){
308 rfd->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
309 if ( rset_read(rfd->items[i].rset, rfd->items[i].fd,
311 heap_insert(rfd->h, &(rfd->items[i]));
316 static void r_close (RSFD rfd)
318 struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
319 struct rset_multior_info *info = mrfd->info;
320 struct rset_multior_rfd **rfdp;
323 for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
326 *rfdp = (*rfdp)->next;
328 heap_destroy (mrfd->h);
329 for (i = 0; i<info->no_rsets; i++) {
330 if (mrfd->items[i].fd)
331 rset_close(info->rsets[i],mrfd->items[i].fd);
333 mrfd->next=info->free_list;
334 info->free_list=mrfd;
337 logf (LOG_FATAL, "r_close but no rfd match!");
342 static void r_rewind (RSFD rfd)
344 assert(!"rewind not implemented yet");
348 static int r_forward(RSET ct, RSFD rfd, void *buf,
349 int (*cmpfunc)(const void *p1, const void *p2),
350 const void *untilbuf)
352 struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
353 struct rset_multior_info *info = mrfd->info;
356 if (heap_empty(mrfd->h))
359 assert(cmpfunc==mrfd->info->cmp);
360 it = *(mrfd->h->heap[1]);
361 memcpy(buf,it.buf, info->key_size);
364 rdres=rset_forward(it.rset, it.fd, it.buf, cmpfunc,untilbuf);
366 rdres=rset_read(it.rset, it.fd, it.buf);
368 heap_balance(mrfd->h);
370 heap_delete(mrfd->h);
375 static int r_read (RSFD rfd, void *buf)
377 return r_forward(0,rfd, buf,0,0);
380 static void r_pos (RSFD rfd, double *current, double *total)
382 struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
383 struct rset_multior_info *info = mrfd->info;
385 double scur=0.0, stot=0.0;
387 for (i=0; i<info->no_rsets; i++){
388 rset_pos(mrfd->items[i].rset, mrfd->items[i].fd, &cur, &tot);
389 logf(LOG_LOG, "r_pos: %d %0.1f %0.1f", i, cur,tot);
393 if (stot <1.0) { /* nothing there */
399 *total=*current*stot/scur;
402 static int r_write (RSFD rfd, const void *buf)
404 logf (LOG_FATAL, "multior set type is read-only");