Using nmem for all rsets, and keeping a freelist for freed rfds, so
[idzebra-moved-to-github.git] / rset / rsprox.c
1 /* $Id: rsprox.c,v 1.12 2004-08-26 11:11:59 heikki Exp $
2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
3    Index Data Aps
4
5 This file is part of the Zebra server.
6
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
10 version.
11
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
15 for more details.
16
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
20 02111-1307, USA.
21 */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <assert.h>
27
28 #include <zebrautl.h>
29 #include <rsprox.h>
30
31 #ifndef RSET_DEBUG
32 #define RSET_DEBUG 0
33 #endif
34
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_forward(RSET ct, RSFD rfd, void *buf, 
40                      int (*cmpfunc)(const void *p1, const void *p2),
41                      const void *untilbuf);
42 static int r_read (RSFD rfd, void *buf);
43 static int r_write (RSFD rfd, const void *buf);
44 static void r_pos (RSFD rfd, double *current, double *total);
45
46 static const struct rset_control control = 
47 {
48     "prox",
49     r_open,
50     r_close,
51     r_delete,
52     r_rewind,
53     r_forward,
54     r_pos,
55     r_read,
56     r_write,
57 };
58
59 const struct rset_control *rset_kind_prox = &control;
60
61 struct rset_prox_info {
62 /*    struct rset_prox_parms p; */
63     RSET *rset;  
64     int rset_no;
65     int ordered;
66     int exclusion;
67     int relation;
68     int distance;
69     int key_size;
70     int (*cmp)(const void *p1, const void *p2);
71     int (*getseq)(const void *p);
72     struct rset_prox_rfd *rfd_list;
73     struct rset_prox_rfd *free_list;
74 };
75
76 struct rset_prox_rfd {
77     RSFD *rfd;
78     char **buf;  /* lookahead key buffers */
79     char *more;  /* more in each lookahead? */
80     struct rset_prox_rfd *next;
81     struct rset_prox_info *info;
82     zint hits;
83 };    
84
85
86 RSET rsprox_create( NMEM nmem, int key_size, 
87             int (*cmp)(const void *p1, const void *p2),
88             int (*getseq)(const void *p),
89             int rset_no, RSET *rset,
90             int ordered, int exclusion,
91             int relation, int distance)
92 {
93     RSET rnew=rset_create_base(&control, nmem);
94     struct rset_prox_info *info;
95     info = (struct rset_prox_info *) nmem_malloc(rnew->nmem,sizeof(*info));
96     info->key_size = key_size;
97     info->cmp = cmp;
98     info->getseq=getseq; /* FIXME - what about multi-level stuff ?? */
99     info->rset = nmem_malloc(rnew->nmem,rset_no * sizeof(*info->rset));
100     memcpy(info->rset, rset,
101            rset_no * sizeof(*info->rset));
102     info->rset_no=rset_no;
103     info->ordered=ordered;
104     info->exclusion=exclusion;
105     info->relation=relation;
106     info->distance=distance;
107     info->rfd_list = NULL;
108     info->free_list = NULL;
109     rnew->priv=info;
110     return rnew;
111 }
112
113
114 static void r_delete (RSET ct)
115 {
116     struct rset_prox_info *info = (struct rset_prox_info *) ct->priv;
117     int i;
118
119     assert (info->rfd_list == NULL);
120     for (i = 0; i<info->rset_no; i++)
121         rset_delete (info->rset[i]);
122 }
123
124
125 static RSFD r_open (RSET ct, int flag)
126 {
127     struct rset_prox_info *info = (struct rset_prox_info *) ct->priv;
128     struct rset_prox_rfd *rfd;
129     int i;
130
131     if (flag & RSETF_WRITE)
132     {
133         logf (LOG_FATAL, "prox set type is read-only");
134         return NULL;
135     }
136     rfd = info->free_list;
137     if (rfd)
138         info->free_list=rfd->next;
139     else {
140         rfd = (struct rset_prox_rfd *) xmalloc (sizeof(*rfd));
141         rfd->more = nmem_malloc (ct->nmem,sizeof(*rfd->more) * info->rset_no);
142         rfd->buf = nmem_malloc(ct->nmem,sizeof(*rfd->buf) * info->rset_no);
143         for (i = 0; i < info->rset_no; i++)
144             rfd->buf[i] = nmem_malloc(ct->nmem,info->key_size);
145         rfd->rfd = nmem_malloc(ct->nmem,sizeof(*rfd->rfd) * info->rset_no);
146     }
147     logf(LOG_DEBUG,"rsprox (%s) open [%p]", ct->control->desc, rfd);
148     rfd->next = info->rfd_list;
149     info->rfd_list = rfd;
150     rfd->info = info;
151
152
153     for (i = 0; i < info->rset_no; i++) {
154         rfd->rfd[i] = rset_open (info->rset[i], RSETF_READ);
155         rfd->more[i] = rset_read (info->rset[i], rfd->rfd[i],
156                                   rfd->buf[i]);
157     }
158     rfd->hits=0;
159     return rfd;
160 }
161
162 static void r_close (RSFD rfd)
163 {
164     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
165     struct rset_prox_rfd **rfdp;
166     
167     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
168         if (*rfdp == rfd)
169         {
170             int i;
171             struct rset_prox_rfd *rfd_tmp=*rfdp;
172             for (i = 0; i<info->rset_no; i++)
173                 rset_close (info->rset[i], (*rfdp)->rfd[i]);
174             *rfdp = (*rfdp)->next;
175             rfd_tmp->next=info->free_list;
176             info->free_list=rfd_tmp;
177             return;
178         }
179     logf (LOG_FATAL, "r_close but no rfd match!");
180     assert (0);
181 }
182
183 static void r_rewind (RSFD rfd)
184 {
185     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
186     struct rset_prox_rfd *p = (struct rset_prox_rfd *) rfd;
187     int i;
188
189     logf (LOG_DEBUG, "rsprox_rewind");
190
191     for (i = 0; i < info->rset_no; i++)
192     {
193         rset_rewind (info->rset[i], p->rfd[i]);
194         p->more[i] = rset_read (info->rset[i], p->rfd[i], p->buf[i]);
195     }
196     p->hits=0;
197 }
198
199 static int r_forward (RSET ct, RSFD rfd, void *buf, 
200                       int (*cmpfunc)(const void *p1, const void *p2),
201                       const void *untilbuf)
202 {
203     /* Note: CT is not used. We _can_ pass NULL for it */
204     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
205     struct rset_prox_rfd *p = (struct rset_prox_rfd *) rfd;
206     int cmp=0;
207     int i;
208
209     if (untilbuf)
210     {
211         /* it's enough to forward first one. Other will follow
212            automatically */
213         if ( p->more[0] && ((cmpfunc)(untilbuf, p->buf[0]) >= 2) )
214             p->more[0] = rset_forward(info->rset[0], p->rfd[0],
215                                       p->buf[0], info->cmp,
216                                       untilbuf);
217     }
218     if (info->ordered && info->relation == 3 && info->exclusion == 0
219         && info->distance == 1)
220     {
221         while (p->more[0]) 
222         {
223             for (i = 1; i < info->rset_no; i++)
224             {
225                 if (!p->more[i]) 
226                 {
227                     p->more[0] = 0;    /* saves us a goto out of while loop. */
228                     break;
229                 }
230                 cmp = (*info->cmp) (p->buf[i], p->buf[i-1]);
231                 if (cmp > 1)
232                 {
233                     p->more[i-1] = rset_forward (info->rset[i-1],
234                                                  p->rfd[i-1],
235                                                  p->buf[i-1],
236                                                  info->cmp,
237                                                  p->buf[i]);
238                     break;
239                 }
240                 else if (cmp == 1)
241                 {
242                     if ((*info->getseq)(p->buf[i-1]) +1 != 
243                         (*info->getseq)(p->buf[i]))
244                     {
245                         p->more[i-1] = rset_read ( info->rset[i-1], 
246                                              p->rfd[i-1], p->buf[i-1]);
247                         break;
248                     }
249                 }
250                 else
251                 {
252                     p->more[i] = rset_forward (info->rset[i], p->rfd[i],
253                                                p->buf[i], info->cmp,
254                                                p->buf[i-1]);
255                     break;
256                 }
257             }
258             if (i == p->info->rset_no)
259             {
260                 memcpy (buf, p->buf[0], info->key_size);
261                 p->more[0] = rset_read (info->rset[0], p->rfd[0], p->buf[0]);
262                 p->hits++;
263                 return 1;
264             }
265         }
266     }
267     else if (info->rset_no == 2)
268     {
269         while (p->more[0] && p->more[1]) 
270         {
271             int cmp = (*info->cmp)(p->buf[0], p->buf[1]);
272             if (cmp < -1)
273                 p->more[0] = rset_forward (info->rset[0], p->rfd[0],
274                                            p->buf[0], info->cmp, p->buf[0]);
275             else if (cmp > 1)
276                 p->more[1] = rset_forward (info->rset[1], p->rfd[1],
277                                            p->buf[1], info->cmp, p->buf[1]);
278             else
279             {
280                 int seqno[500];
281                 int n = 0;
282                 
283                 seqno[n++] = (*info->getseq)(p->buf[0]);
284                 while ((p->more[0] = rset_read (info->rset[0], p->rfd[0],
285                                                 p->buf[0])) >= -1 &&
286                        p->more[0] <= -1)
287                     if (n < 500)
288                         seqno[n++] = (*info->getseq)(p->buf[0]);
289                 
290                 for (i = 0; i<n; i++)
291                 {
292                     int diff = (*info->getseq)(p->buf[1]) - seqno[i];
293                     int excl = info->exclusion;
294                     if (!info->ordered && diff < 0)
295                         diff = -diff;
296                     switch (info->relation)
297                     {
298                     case 1:      /* < */
299                         if (diff < info->distance && diff >= 0)
300                             excl = !excl;
301                         break;
302                     case 2:      /* <= */
303                         if (diff <= info->distance && diff >= 0)
304                             excl = !excl;
305                         break;
306                     case 3:      /* == */
307                         if (diff == info->distance && diff >= 0)
308                             excl = !excl;
309                         break;
310                     case 4:      /* >= */
311                         if (diff >= info->distance && diff >= 0)
312                             excl = !excl;
313                         break;
314                     case 5:      /* > */
315                         if (diff > info->distance && diff >= 0)
316                             excl = !excl;
317                         break;
318                     case 6:      /* != */
319                         if (diff != info->distance && diff >= 0)
320                             excl = !excl;
321                         break;
322                     }
323                     if (excl)
324                     {
325                         memcpy (buf, p->buf[1], info->key_size);
326                         
327                         p->more[1] = rset_read (info->rset[1],
328                                                 p->rfd[1], p->buf[1]);
329                         p->hits++;
330                         return 1;
331                     }
332                 }
333                 p->more[1] = rset_read (info->rset[1], p->rfd[1],
334                                         p->buf[1]);
335             }
336         }
337     }
338     return 0;
339 }
340
341
342 static int r_read (RSFD rfd, void *buf)
343 {
344     { double cur,tot; r_pos(rfd,&cur,&tot); } /*!*/
345     return r_forward(0, rfd, buf, 0, 0);
346 }
347
348 static int r_write (RSFD rfd, const void *buf)
349 {
350     logf (LOG_FATAL, "prox set type is read-only");
351     return -1;
352 }
353
354 static void r_pos (RSFD rfd, double *current, double *total)
355 {
356     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
357     struct rset_prox_rfd *p = (struct rset_prox_rfd *) rfd;
358     int i;
359     double cur,tot=-1;
360     double scur=0,stot=0;
361     double r;
362
363     logf (LOG_DEBUG, "rsprox_pos");
364
365     for (i = 0; i < info->rset_no; i++)
366     {
367         rset_pos(info->rset[i], p->rfd[i],  &cur, &tot);
368         if (tot>0) {
369             scur += cur;
370             stot += tot;
371         }
372     }
373     if (tot <0) {  /* nothing found */
374         *current=-1;
375         *total=-1;
376     } else if (tot <1) { /* most likely tot==0 */
377         *current=0;
378         *total=0;
379     } else {
380         r=scur/stot; 
381         *current=p->hits;
382         *total=*current/r ; 
383     }
384     logf(LOG_DEBUG,"prox_pos: [%d] %0.1f/%0.1f= %0.4f ",
385                     i,*current, *total, r);
386 }