Major restructuring in rsets.
[idzebra-moved-to-github.git] / index / trunc.c
1 /* $Id: trunc.c,v 1.40 2004-08-31 10:43:35 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
24 #include <stdio.h>
25 #include <assert.h>
26
27 #include "index.h"
28 #include <rstemp.h>
29 #include <rsnull.h>
30 #include <rsisams.h>
31 #include <rsisamc.h>
32 #include <rsisamb.h>
33 #include <rsmultior.h>
34
35 struct trunc_info {
36     int  *ptr;
37     int  *indx;
38     char **heap;
39     int  heapnum;
40     int  (*cmp)(const void *p1, const void *p2);
41     int  keysize;
42     char *swapbuf;
43     char *tmpbuf;
44     char *buf;
45 };
46
47 static void heap_swap (struct trunc_info *ti, int i1, int i2)
48 {
49     int swap;
50
51     swap = ti->ptr[i1];
52     ti->ptr[i1] = ti->ptr[i2];
53     ti->ptr[i2] = swap;
54 }
55
56 static void heap_delete (struct trunc_info *ti)
57 {
58     int cur = 1, child = 2;
59
60     heap_swap (ti, 1, ti->heapnum--);
61     while (child <= ti->heapnum) {
62         if (child < ti->heapnum &&
63             (*ti->cmp)(ti->heap[ti->ptr[child]],
64                        ti->heap[ti->ptr[1+child]]) > 0)
65             child++;
66         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
67                        ti->heap[ti->ptr[child]]) > 0)
68         {
69             heap_swap (ti, cur, child);
70             cur = child;
71             child = 2*cur;
72         }
73         else
74             break;
75     }
76 }
77
78 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
79 {
80     int cur, parent;
81
82     cur = ++(ti->heapnum);
83     memcpy (ti->heap[ti->ptr[cur]], buf, ti->keysize);
84     ti->indx[ti->ptr[cur]] = indx;
85     parent = cur/2;
86     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
87                                 ti->heap[ti->ptr[cur]]) > 0)
88     {
89         heap_swap (ti, cur, parent);
90         cur = parent;
91         parent = cur/2;
92     }
93 }
94
95 static struct trunc_info *heap_init (int size, int key_size,
96                                      int (*cmp)(const void *p1,
97                                                 const void *p2))
98 {
99     struct trunc_info *ti = (struct trunc_info *) xmalloc (sizeof(*ti));
100     int i;
101
102     ++size;
103     ti->heapnum = 0;
104     ti->keysize = key_size;
105     ti->cmp = cmp;
106     ti->indx = (int *) xmalloc (size * sizeof(*ti->indx));
107     ti->heap = (char **) xmalloc (size * sizeof(*ti->heap));
108     ti->ptr = (int *) xmalloc (size * sizeof(*ti->ptr));
109     ti->swapbuf = (char *) xmalloc (ti->keysize);
110     ti->tmpbuf = (char *) xmalloc (ti->keysize);
111     ti->buf = (char *) xmalloc (size * ti->keysize);
112     for (i = size; --i >= 0; )
113     {
114         ti->ptr[i] = i;
115         ti->heap[i] = ti->buf + ti->keysize * i;
116     }
117     return ti;
118 }
119
120 static void heap_close (struct trunc_info *ti)
121 {
122     xfree (ti->ptr);
123     xfree (ti->indx);
124     xfree (ti->heap);
125     xfree (ti->swapbuf);
126     xfree (ti->tmpbuf);
127     xfree (ti->buf);
128     xfree (ti);
129 }
130
131 static RSET rset_trunc_r (ZebraHandle zi, const char *term, int length,
132                           const char *flags, ISAMS_P *isam_p, int from, int to,
133                           int merge_chunk, int preserve_position,
134                           int term_type)
135 {
136     RSET result; 
137     RSFD result_rsfd;
138     int nn = 0;
139
140     /*
141     rset_temp_parms parms;
142     parms.cmp = key_compare_it;
143     parms.key_size = sizeof(struct it_key);
144     parms.temp_path = res_get (zi->res, "setTmpDir");
145     result = rset_create (rset_kind_temp, &parms);
146     */
147     result=rstemp_create(NULL, /* FIXME - use a proper nmem */
148             sizeof(struct it_key), key_compare_it, 
149             res_get (zi->res, "setTmpDir"));
150     result_rsfd = rset_open (result, RSETF_WRITE);
151
152     if (to - from > merge_chunk)
153     {
154         RSFD *rsfd;
155         RSET *rset;
156         int i, i_add = (to-from)/merge_chunk + 1;
157         struct trunc_info *ti;
158         int rscur = 0;
159         int rsmax = (to-from)/i_add + 1;
160         
161         rset = (RSET *) xmalloc (sizeof(*rset) * rsmax);
162         rsfd = (RSFD *) xmalloc (sizeof(*rsfd) * rsmax);
163         
164         for (i = from; i < to; i += i_add)
165         {
166             if (i_add <= to - i)
167                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
168                                             isam_p, i, i+i_add,
169                                             merge_chunk, preserve_position,
170                                             term_type);
171             else
172                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
173                                             isam_p, i, to,
174                                             merge_chunk, preserve_position,
175                                             term_type);
176             rscur++;
177         }
178         ti = heap_init (rscur, sizeof(struct it_key), key_compare_it);
179         for (i = rscur; --i >= 0; )
180         {
181             rsfd[i] = rset_open (rset[i], RSETF_READ);
182             if (rset_read(rsfd[i], ti->tmpbuf))
183                 heap_insert (ti, ti->tmpbuf, i);
184             else
185             {
186                 rset_close (rsfd[i]);
187                 rset_delete (rset[i]);
188             }
189         }
190         while (ti->heapnum)
191         {
192             int n = ti->indx[ti->ptr[1]];
193
194             rset_write (result_rsfd, ti->heap[ti->ptr[1]]);
195             nn++;
196
197             while (1)
198             {
199                 if (!rset_read (rsfd[n], ti->tmpbuf))
200                 {
201                     heap_delete (ti);
202                     rset_close (rsfd[n]);
203                     rset_delete (rset[n]);
204                     break;
205                 }
206                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
207                 {
208                     heap_delete (ti);
209                     heap_insert (ti, ti->tmpbuf, n);
210                     break;
211                 }
212             }
213         }
214         xfree (rset);
215         xfree (rsfd);
216         heap_close (ti);
217     }
218     else if (zi->reg->isamc)
219     {
220         ISAMC_PP *ispt;
221         int i;
222         struct trunc_info *ti;
223
224         ispt = (ISAMC_PP *) xmalloc (sizeof(*ispt) * (to-from));
225
226         ti = heap_init (to-from, sizeof(struct it_key),
227                         key_compare_it);
228         for (i = to-from; --i >= 0; )
229         {
230             ispt[i] = isc_pp_open (zi->reg->isamc, isam_p[from+i]);
231             if (isc_pp_read (ispt[i], ti->tmpbuf))
232                 heap_insert (ti, ti->tmpbuf, i);
233             else
234                 isc_pp_close (ispt[i]);
235         }
236         while (ti->heapnum)
237         {
238             int n = ti->indx[ti->ptr[1]];
239
240             rset_write (result_rsfd, ti->heap[ti->ptr[1]]);
241             nn++;
242             if (preserve_position)
243             {
244                 heap_delete (ti);
245                 if (isc_pp_read (ispt[n], ti->tmpbuf))
246                     heap_insert (ti, ti->tmpbuf, n);
247                 else
248                     isc_pp_close (ispt[n]);
249             }
250             else
251             {
252                 while (1)
253                 {
254                     if (!isc_pp_read (ispt[n], ti->tmpbuf))
255                     {
256                         heap_delete (ti);
257                         isc_pp_close (ispt[n]);
258                         break;
259                     }
260                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
261                     {
262                         heap_delete (ti);
263                         heap_insert (ti, ti->tmpbuf, n);
264                         break;
265                     }
266                 }
267             }
268         }
269         heap_close (ti);
270         xfree (ispt);
271     }
272     else if (zi->reg->isams)
273     {
274         ISAMS_PP *ispt;
275         int i;
276         struct trunc_info *ti;
277         int nn = 0;
278
279         ispt = (ISAMS_PP *) xmalloc (sizeof(*ispt) * (to-from));
280
281         ti = heap_init (to-from, sizeof(struct it_key),
282                         key_compare_it);
283         for (i = to-from; --i >= 0; )
284         {
285             ispt[i] = isams_pp_open (zi->reg->isams, isam_p[from+i]);
286             if (isams_pp_read (ispt[i], ti->tmpbuf))
287                 heap_insert (ti, ti->tmpbuf, i);
288             else
289                 isams_pp_close (ispt[i]);
290         }
291         while (ti->heapnum)
292         {
293             int n = ti->indx[ti->ptr[1]];
294
295             rset_write (result_rsfd, ti->heap[ti->ptr[1]]);
296             nn++;
297             while (1)
298             {
299                 if (!isams_pp_read (ispt[n], ti->tmpbuf))
300                 {
301                     heap_delete (ti);
302                     isams_pp_close (ispt[n]);
303                     break;
304                 }
305                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
306                 {
307                     heap_delete (ti);
308                     heap_insert (ti, ti->tmpbuf, n);
309                     break;
310                 }
311             }
312         }
313         heap_close (ti);
314         xfree (ispt);
315     }
316     else if (zi->reg->isamb)
317     {
318         ISAMB_PP *ispt;
319         int i;
320         struct trunc_info *ti;
321
322         ispt = (ISAMB_PP *) xmalloc (sizeof(*ispt) * (to-from));
323
324         ti = heap_init (to-from, sizeof(struct it_key),
325                         key_compare_it);
326         for (i = to-from; --i >= 0; )
327         {
328             if (isam_p[from+i]) {
329                 ispt[i] = isamb_pp_open (zi->reg->isamb, isam_p[from+i]);
330                 if (isamb_pp_read (ispt[i], ti->tmpbuf))
331                     heap_insert (ti, ti->tmpbuf, i);
332                 else
333                     isamb_pp_close (ispt[i]);
334             }
335         }
336         while (ti->heapnum)
337         {
338             int n = ti->indx[ti->ptr[1]];
339
340             rset_write (result_rsfd, ti->heap[ti->ptr[1]]);
341             nn++;
342
343             if (preserve_position)
344             {
345                 heap_delete (ti);
346                 if (isamb_pp_read (ispt[n], ti->tmpbuf))
347                     heap_insert (ti, ti->tmpbuf, n);
348                 else
349                     isamb_pp_close (ispt[n]);
350             }
351             else
352             {
353                 while (1)
354                 {
355                     if (!isamb_pp_read (ispt[n], ti->tmpbuf))
356                     {
357                         heap_delete (ti);
358                         isamb_pp_close (ispt[n]);
359                         break;
360                     }
361                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
362                     {
363                         heap_delete (ti);
364                         heap_insert (ti, ti->tmpbuf, n);
365                         break;
366                     }
367                 }
368             }
369         }
370         heap_close (ti);
371         xfree (ispt);
372     }
373     else
374         logf (LOG_WARN, "Unknown isam set in rset_trunc_r");
375
376     rset_close (result_rsfd);
377     return result;
378 }
379
380 static int isams_trunc_cmp (const void *p1, const void *p2)
381 {
382     ISAMS_P i1 = *(ISAMS_P*) p1;
383     ISAMS_P i2 = *(ISAMS_P*) p2;
384
385     if (i1 > i2)
386         return 1;
387     else if (i1 < i2)
388         return -1;
389     return 0;
390 }
391
392 static int isamc_trunc_cmp (const void *p1, const void *p2)
393 {
394     ISAMC_P i1 = *(ISAMC_P*) p1;
395     ISAMC_P i2 = *(ISAMC_P*) p2;
396     zint d;
397
398     d = (isc_type (i1) - isc_type (i2));
399     if (d == 0)
400         d = isc_block (i1) - isc_block (i2);
401     if (d > 0)
402         return 1;
403     else if (d < 0)
404         return -1;
405     return 0;
406 }
407
408 RSET rset_trunc (ZebraHandle zi, ISAMS_P *isam_p, int no,
409                  const char *term, int length, const char *flags,
410                  int preserve_position, int term_type)
411 {
412     logf (LOG_DEBUG, "rset_trunc no=%d", no);
413     if (no < 1)
414         return rsnull_create (NULL); /* FIXME - use a proper nmem */
415     if (zi->reg->isams)
416     {
417         if (no == 1)
418             return rsisams_create(NULL, /* FIXME - use some nmem */
419                     sizeof(struct it_key), key_compare_it,
420                     zi->reg->isams, *isam_p);
421         /*
422         {
423             rset_isams_parms parms;
424
425             parms.pos = *isam_p;
426             parms.is = zi->reg->isams;
427             return rset_create (rset_kind_isams, &parms);
428         }
429         */
430         qsort (isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
431     }
432     else if (zi->reg->isamc)
433     {
434         if (no == 1)
435             return rsisamc_create(NULL, /* FIXME - use some nmem */
436                     sizeof(struct it_key), key_compare_it,
437                     zi->reg->isamc, *isam_p);
438         /*
439         {
440             rset_isamc_parms parms;
441
442             parms.key_size = sizeof(struct it_key);
443             parms.cmp = key_compare_it;
444             parms.pos = *isam_p;
445             parms.is = zi->reg->isamc;
446             return rset_create (rset_kind_isamc, &parms);
447         }
448         */
449
450 #if 0 /* NEW_TRUNC */ /* FIXME - Use the new multi_or instead !! */
451         else if (no < 10000)
452         {
453             rset_m_or_parms parms;
454
455             parms.key_size = sizeof(struct it_key);
456             parms.cmp = key_compare_it;
457             parms.isc = zi->reg->isamc;
458             parms.isam_positions = isam_p;
459             parms.no_isam_positions = no;
460             parms.no_save_positions = 100000;
461             return rset_create (rset_kind_m_or, &parms);
462         }
463 #endif
464         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
465     }
466     else if (zi->reg->isamb)
467     {
468         if (no == 1)
469             return rsisamb_create(NULL, /* FIXME - use some nmem */
470                     sizeof(struct it_key), key_compare_it,
471                     zi->reg->isamb, *isam_p);
472         /*
473         {
474             rset_isamb_parms parms;
475             parms.key_size = sizeof(struct it_key);
476             parms.cmp = key_compare_it;
477             parms.pos = *isam_p;
478             parms.is = zi->reg->isamb;
479             return rset_create (rset_kind_isamb, &parms);
480         }
481         */
482 #if 1
483         else if (no <10000 ) /* FIXME - hardcoded number */
484         {
485             RSET r;
486             RSET *rsets=xmalloc(no*sizeof(RSET)); /* use nmem! */
487             int i;
488             for (i=0;i<no;i++)
489                 rsets[i]=rsisamb_create(NULL, /* */
490                     sizeof(struct it_key), key_compare_it,
491                     zi->reg->isamb, isam_p[i] );
492             r=rsmultior_create( NULL, /* FIXME - use some nmem */
493                       sizeof(struct it_key), key_compare_it, 
494                       no, rsets);
495             xfree(rsets);
496             return r;
497             /*
498             rset_multior_parms m_parms;
499             rset_isamb_parms b_parms;
500             int i;
501             m_parms.key_size = sizeof(struct it_key);
502             m_parms.cmp = key_compare_it;
503             m_parms.no_rsets=no;
504             m_parms.rsets=xmalloc(sizeof(*m_parms.rsets)*no);
505             b_parms.key_size = sizeof(struct it_key);
506             b_parms.cmp = key_compare_it;
507             b_parms.is = zi->reg->isamb;
508             for (i=0;i<no;i++)
509             {
510                 b_parms.pos = isam_p[i];
511                 m_parms.rsets[i]=rset_create (rset_kind_isamb, &b_parms);
512             }
513             return rset_create (rset_kind_multior, &m_parms);
514             */
515         } /* <10000 - rs_multior */
516 #endif        
517         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
518     }
519     else
520     {
521         logf (LOG_WARN, "Unknown isam set in rset_trunc");
522         return rsnull_create (NULL); /* FIXME - nmem */
523     }
524     return rset_trunc_r (zi, term, length, flags, isam_p, 0, no, 100,
525                          preserve_position, term_type);
526 }
527