1 /* $Id: rsmultior.c,v 1.2 2004-08-19 12:49:15 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 void *r_create(RSET ct, const struct rset_control *sel, void *parms);
36 static RSFD r_open (RSET ct, int flag);
37 static void r_close (RSFD rfd);
38 static void r_delete (RSET ct);
39 static void r_rewind (RSFD rfd);
40 static int r_read (RSFD rfd, void *buf, int *term_index);
41 static int r_write (RSFD rfd, const void *buf);
42 static int r_forward(RSET ct, RSFD rfd, void *buf, int *term_index,
43 int (*cmpfunc)(const void *p1, const void *p2),
44 const void *untilbuf);
46 static const struct rset_control control =
55 rset_default_pos, /* FIXME */
60 const struct rset_control *rset_kind_multior = &control;
62 /* The heap structure:
63 * The rset contains a list or rsets we are ORing together
64 * The rfd contains a heap of heap-items, which contain
65 * a rfd opened to those rsets, and a buffer for one key.
66 * They also contain a ptr to the rset list in the rset
67 * itself, for practical reasons.
80 int (*cmp)(const void *p1, const void *p2);
81 struct heap_item **heap; /* ptrs to the rfd */
83 typedef struct heap *HEAP;
86 struct rset_multior_info {
89 int (*cmp)(const void *p1, const void *p2);
93 struct rset_multior_rfd *rfd_list;
97 struct rset_multior_rfd {
99 struct heap_item *items; /* we alloc and free them here */
101 struct rset_multior_rfd *next;
102 struct rset_multior_info *info;
104 char *prevvalue; /* to see if we are in another record */
108 static void heap_dump_item( HEAP h, int i, int level) {
112 (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
113 logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
114 &(h->heap[i]), h->heap[i]->buf, cur,tot );
115 heap_dump_item(h, 2*i, level+1);
116 heap_dump_item(h, 2*i+1, level+1);
118 static void heap_dump( HEAP h,char *msg) {
119 logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
120 heap_dump_item(h,1,1);
124 static void heap_swap (HEAP h, int x, int y)
126 struct heap_item *swap;
128 h->heap[x]=h->heap[y];
132 static int heap_cmp(HEAP h, int x, int y)
134 return (*h->cmp)(h->heap[x]->buf,h->heap[y]->buf);
137 static int heap_empty(HEAP h)
139 return ( 0==h->heapnum );
142 static void heap_delete (HEAP h)
143 { /* deletes the first item in the heap, and balances the rest */
144 int cur = 1, child = 2;
145 h->heap[1]=0; /* been deleted */
146 heap_swap (h, 1, h->heapnum--);
147 while (child <= h->heapnum) {
148 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
150 if (heap_cmp(h,cur,child) > 0)
152 heap_swap (h, cur, child);
161 static void heap_balance (HEAP h)
162 { /* The heap root element has changed value (to bigger) */
163 /* swap downwards until the heap is ordered again */
164 int cur = 1, child = 2;
165 while (child <= h->heapnum) {
166 if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
168 if (heap_cmp(h,cur,child) > 0)
170 heap_swap (h, cur, child);
180 static void heap_insert (HEAP h, struct heap_item *hi)
184 cur = ++(h->heapnum);
185 assert(cur <= h->heapmax);
188 while (parent && (heap_cmp(h,parent,cur) > 0))
191 heap_swap (h, cur, parent);
199 HEAP heap_create (int size, int key_size,
200 int (*cmp)(const void *p1, const void *p2))
202 HEAP h = (HEAP) xmalloc (sizeof(*h));
204 ++size; /* heap array starts at 1 */
207 h->keysize = key_size;
209 h->heap = (struct heap_item**) xmalloc((size)*sizeof(*h->heap));
210 h->heap[0]=0; /* not used */
214 static void heap_destroy (HEAP h)
216 xfree (h->heap); /* safe, they all point to the rfd */
221 static void *r_create (RSET ct, const struct rset_control *sel, void *parms)
223 rset_multior_parms *r_parms = (rset_multior_parms *) parms;
224 struct rset_multior_info *info;
226 ct->flags |= RSET_FLAG_VOLATILE;
227 /* FIXME - Remove the whole flags thing, from all rsets */
228 info = (struct rset_multior_info *) xmalloc (sizeof(*info));
229 info->key_size = r_parms->key_size;
230 assert (info->key_size > 1);
231 info->cmp = r_parms->cmp;
232 info->no_rsets= r_parms->no_rsets;
233 info->rsets=r_parms->rsets; /* now we own it! */
235 info->term_index=0 ; /* r_parms->rset_term; */ /*??*/ /*FIXME */
236 ct->no_rset_terms = 1;
237 ct->rset_terms = (RSET_TERM *) xmalloc (sizeof(*ct->rset_terms));
238 ct->rset_terms[0] = r_parms->rset_term;
242 static RSFD r_open (RSET ct, int flag)
244 struct rset_multior_rfd *rfd;
245 struct rset_multior_info *info = (struct rset_multior_info *) ct->buf;
249 if (flag & RSETF_WRITE)
251 logf (LOG_FATAL, "multior set type is read-only");
254 rfd = (struct rset_multior_rfd *) xmalloc (sizeof(*rfd));
256 rfd->next = info->rfd_list;
258 info->rfd_list = rfd;
259 if (ct->no_rset_terms==1)
260 rfd->countp=&ct->rset_terms[0]->count;
263 rfd->h = heap_create( info->no_rsets, info->key_size, info->cmp);
265 rfd->items=(struct heap_item *) xmalloc(info->no_rsets*sizeof(*rfd->items));
266 for (i=0; i<info->no_rsets; i++){
267 rfd->items[i].rset=info->rsets[i];
268 rfd->items[i].buf=xmalloc(info->key_size);
269 rfd->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
270 /* if (item_readbuf(&(rfd->items[i]))) */
271 if ( rset_read(rfd->items[i].rset, rfd->items[i].fd,
272 rfd->items[i].buf, &dummy_termindex) )
273 heap_insert(rfd->h, &(rfd->items[i]));
278 static void r_close (RSFD rfd)
280 struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
281 struct rset_multior_info *info = mrfd->info;
282 struct rset_multior_rfd **rfdp;
285 for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
288 *rfdp = (*rfdp)->next;
290 heap_destroy (mrfd->h);
291 for (i = 0; i<info->no_rsets; i++) {
292 if (mrfd->items[i].fd)
293 rset_close(info->rsets[i],mrfd->items[i].fd);
294 xfree(mrfd->items[i].buf);
298 xfree(mrfd->prevvalue);
302 logf (LOG_FATAL, "r_close but no rfd match!");
306 static void r_delete (RSET ct)
308 struct rset_multior_info *info = (struct rset_multior_info *) ct->buf;
311 assert (info->rfd_list == NULL);
312 for(i=0;i<info->no_rsets;i++)
313 rset_delete(info->rsets[i]);
317 for (i = 0; i<ct->no_rset_terms; i++) /* usually only 1 */
318 rset_term_destroy (ct->rset_terms[i]);
319 xfree (ct->rset_terms);
322 static void r_rewind (RSFD rfd)
324 assert(!"rewind not implemented yet");
328 static int r_forward(RSET ct, RSFD rfd, void *buf, int *term_index,
329 int (*cmpfunc)(const void *p1, const void *p2),
330 const void *untilbuf)
332 struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
333 struct rset_multior_info *info = mrfd->info;
337 if (heap_empty(mrfd->h))
340 assert(cmpfunc==mrfd->info->cmp);
342 it = *(mrfd->h->heap[1]);
343 memcpy(buf,it.buf, info->key_size);
345 if (mrfd->prevvalue) { /* in another record */
346 if ( (*mrfd->info->cmp)(mrfd->prevvalue,it.buf) < -1)
349 mrfd->prevvalue=xmalloc(info->key_size);
352 memcpy(mrfd->prevvalue,it.buf, info->key_size);
355 rdres=rset_forward(it.rset, it.fd, it.buf, &dummycount,
358 rdres=rset_read(it.rset, it.fd, it.buf, &dummycount);
360 heap_balance(mrfd->h);
362 heap_delete(mrfd->h);
367 static int r_read (RSFD rfd, void *buf, int *term_index)
369 return r_forward(0,rfd, buf, term_index,0,0);
375 struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
376 struct trunc_info *ti = mrfd->ti;
377 int n = ti->indx[ti->ptr[1]];
382 memcpy (buf, ti->heap[ti->ptr[1]], ti->keysize);
383 if (((struct rset_multior_rfd *) rfd)->position)
385 if (isc_pp_read (((struct rset_multior_rfd *) rfd)->ispt[n], ti->tmpbuf))
388 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
389 ((struct rset_multior_rfd *) rfd)->position--;
390 heap_insert (ti, ti->tmpbuf, n);
394 if (mrfd->countp && (
395 *mrfd->countp == 0 || (*ti->cmp)(buf, mrfd->pbuf) > 1))
397 memcpy (mrfd->pbuf, buf, ti->keysize);
404 if (!isc_pp_read (((struct rset_multior_rfd *) rfd)->ispt[n], ti->tmpbuf))
409 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
412 heap_insert (ti, ti->tmpbuf, n);
416 if (mrfd->countp && (
417 *mrfd->countp == 0 || (*ti->cmp)(buf, mrfd->pbuf) > 1))
419 memcpy (mrfd->pbuf, buf, ti->keysize);
426 /*!*/ /* FIXME Forward */
427 /*!*/ /* FIXME pos */
429 static int r_write (RSFD rfd, const void *buf)
431 logf (LOG_FATAL, "multior set type is read-only");