XML reader for data1 (EXPAT)
[idzebra-moved-to-github.git] / index / trunc.c
1 /*
2  * Copyright (C) 1994-2002, Index Data
3  * All rights reserved.
4  * Sebastian Hammer, Adam Dickmeiss, Heikki Levanto
5  *
6  * $Id: trunc.c,v 1.24 2002-04-16 22:31:42 adam Exp $
7  *
8  */
9 #include <stdio.h>
10 #include <assert.h>
11
12 #define NEW_TRUNC 1
13
14 #include "index.h"
15 #include <rstemp.h>
16 #include <rsnull.h>
17 #include <rsisams.h>
18 #include <rsisam.h>
19 #include <rsisamc.h>
20 #include <rsisamd.h>
21 #include <rsisamb.h>
22 #if NEW_TRUNC
23 #include <rsm_or.h>
24 #endif
25
26 struct trunc_info {
27     int  *ptr;
28     int  *indx;
29     char **heap;
30     int  heapnum;
31     int  (*cmp)(const void *p1, const void *p2);
32     int  keysize;
33     char *swapbuf;
34     char *tmpbuf;
35     char *buf;
36 };
37
38 static void heap_swap (struct trunc_info *ti, int i1, int i2)
39 {
40     int swap;
41
42     swap = ti->ptr[i1];
43     ti->ptr[i1] = ti->ptr[i2];
44     ti->ptr[i2] = swap;
45 }
46
47 static void heap_delete (struct trunc_info *ti)
48 {
49     int cur = 1, child = 2;
50
51     heap_swap (ti, 1, ti->heapnum--);
52     while (child <= ti->heapnum) {
53         if (child < ti->heapnum &&
54             (*ti->cmp)(ti->heap[ti->ptr[child]],
55                        ti->heap[ti->ptr[1+child]]) > 0)
56             child++;
57         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
58                        ti->heap[ti->ptr[child]]) > 0)
59         {
60             heap_swap (ti, cur, child);
61             cur = child;
62             child = 2*cur;
63         }
64         else
65             break;
66     }
67 }
68
69 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
70 {
71     int cur, parent;
72
73     cur = ++(ti->heapnum);
74     memcpy (ti->heap[ti->ptr[cur]], buf, ti->keysize);
75     ti->indx[ti->ptr[cur]] = indx;
76     parent = cur/2;
77     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
78                                 ti->heap[ti->ptr[cur]]) > 0)
79     {
80         heap_swap (ti, cur, parent);
81         cur = parent;
82         parent = cur/2;
83     }
84 }
85
86 static struct trunc_info *heap_init (int size, int key_size,
87                                      int (*cmp)(const void *p1,
88                                                 const void *p2))
89 {
90     struct trunc_info *ti = (struct trunc_info *) xmalloc (sizeof(*ti));
91     int i;
92
93     ++size;
94     ti->heapnum = 0;
95     ti->keysize = key_size;
96     ti->cmp = cmp;
97     ti->indx = (int *) xmalloc (size * sizeof(*ti->indx));
98     ti->heap = (char **) xmalloc (size * sizeof(*ti->heap));
99     ti->ptr = (int *) xmalloc (size * sizeof(*ti->ptr));
100     ti->swapbuf = (char *) xmalloc (ti->keysize);
101     ti->tmpbuf = (char *) xmalloc (ti->keysize);
102     ti->buf = (char *) xmalloc (size * ti->keysize);
103     for (i = size; --i >= 0; )
104     {
105         ti->ptr[i] = i;
106         ti->heap[i] = ti->buf + ti->keysize * i;
107     }
108     return ti;
109 }
110
111 static void heap_close (struct trunc_info *ti)
112 {
113     xfree (ti->ptr);
114     xfree (ti->indx);
115     xfree (ti->heap);
116     xfree (ti->swapbuf);
117     xfree (ti->tmpbuf);
118     xfree (ti->buf);
119     xfree (ti);
120 }
121
122 static RSET rset_trunc_r (ZebraHandle zi, const char *term, int length,
123                           const char *flags, ISAMS_P *isam_p, int from, int to,
124                           int merge_chunk, int preserve_position)
125 {
126     RSET result; 
127     RSFD result_rsfd;
128     rset_temp_parms parms;
129
130     parms.cmp = key_compare_it;
131     parms.key_size = sizeof(struct it_key);
132     parms.temp_path = res_get (zi->res, "setTmpDir");
133     parms.rset_term = rset_term_create (term, length, flags);
134     result = rset_create (rset_kind_temp, &parms);
135     result_rsfd = rset_open (result, RSETF_WRITE);
136
137     if (to - from > merge_chunk)
138     {
139         RSFD *rsfd;
140         RSET *rset;
141         int term_index;
142         int i, i_add = (to-from)/merge_chunk + 1;
143         struct trunc_info *ti;
144         int rscur = 0;
145         int rsmax = (to-from)/i_add + 1;
146         
147         rset = (RSET *) xmalloc (sizeof(*rset) * rsmax);
148         rsfd = (RSFD *) xmalloc (sizeof(*rsfd) * rsmax);
149         
150         for (i = from; i < to; i += i_add)
151         {
152             if (i_add <= to - i)
153                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
154                                             isam_p, i, i+i_add,
155                                             merge_chunk, preserve_position);
156             else
157                 rset[rscur] = rset_trunc_r (zi, term, length, flags,
158                                             isam_p, i, to,
159                                             merge_chunk, preserve_position);
160             rscur++;
161         }
162         ti = heap_init (rscur, sizeof(struct it_key), key_compare_it);
163         for (i = rscur; --i >= 0; )
164         {
165             rsfd[i] = rset_open (rset[i], RSETF_READ);
166             if (rset_read (rset[i], rsfd[i], ti->tmpbuf, &term_index))
167                 heap_insert (ti, ti->tmpbuf, i);
168             else
169             {
170                 rset_close (rset[i], rsfd[i]);
171                 rset_delete (rset[i]);
172             }
173         }
174         while (ti->heapnum)
175         {
176             int n = ti->indx[ti->ptr[1]];
177
178             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
179
180             while (1)
181             {
182                 if (!rset_read (rset[n], rsfd[n], ti->tmpbuf, &term_index))
183                 {
184                     heap_delete (ti);
185                     rset_close (rset[n], rsfd[n]);
186                     rset_delete (rset[n]);
187                     break;
188                 }
189                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
190                 {
191                     heap_delete (ti);
192                     heap_insert (ti, ti->tmpbuf, n);
193                     break;
194                 }
195             }
196         }
197         xfree (rset);
198         xfree (rsfd);
199         heap_close (ti);
200     }
201     else if (zi->reg->isam)
202     {
203         ISPT *ispt;
204         int i;
205         struct trunc_info *ti;
206
207         ispt = (ISPT *) xmalloc (sizeof(*ispt) * (to-from));
208
209         ti = heap_init (to-from, sizeof(struct it_key),
210                         key_compare_it);
211         for (i = to-from; --i >= 0; )
212         {
213             ispt[i] = is_position (zi->reg->isam, isam_p[from+i]);
214             if (is_readkey (ispt[i], ti->tmpbuf))
215                 heap_insert (ti, ti->tmpbuf, i);
216             else
217                 is_pt_free (ispt[i]);
218         }
219         while (ti->heapnum)
220         {
221             int n = ti->indx[ti->ptr[1]];
222
223             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
224             if (preserve_position)
225             {
226 /* section that preserve all keys */
227                 heap_delete (ti);
228                 if (is_readkey (ispt[n], ti->tmpbuf))
229                     heap_insert (ti, ti->tmpbuf, n);
230                 else
231                     is_pt_free (ispt[n]);
232             }
233             else
234             {
235 /* section that preserve all keys with unique sysnos */
236                 while (1)
237                 {
238                     if (!is_readkey (ispt[n], ti->tmpbuf))
239                     {
240                         heap_delete (ti);
241                         is_pt_free (ispt[n]);
242                         break;
243                     }
244                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
245                     {
246                         heap_delete (ti);
247                         heap_insert (ti, ti->tmpbuf, n);
248                         break;
249                     }
250                 }
251             }
252         }
253         heap_close (ti);
254         xfree (ispt);
255     }
256     else if (zi->reg->isamc)
257     {
258         ISAMC_PP *ispt;
259         int i;
260         struct trunc_info *ti;
261
262         ispt = (ISAMC_PP *) xmalloc (sizeof(*ispt) * (to-from));
263
264         ti = heap_init (to-from, sizeof(struct it_key),
265                         key_compare_it);
266         for (i = to-from; --i >= 0; )
267         {
268             ispt[i] = isc_pp_open (zi->reg->isamc, isam_p[from+i]);
269             if (isc_pp_read (ispt[i], ti->tmpbuf))
270                 heap_insert (ti, ti->tmpbuf, i);
271             else
272                 isc_pp_close (ispt[i]);
273         }
274         while (ti->heapnum)
275         {
276             int n = ti->indx[ti->ptr[1]];
277
278             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
279             if (preserve_position)
280             {
281                 heap_delete (ti);
282                 if (isc_pp_read (ispt[n], ti->tmpbuf))
283                     heap_insert (ti, ti->tmpbuf, n);
284                 else
285                     isc_pp_close (ispt[n]);
286             }
287             else
288             {
289                 while (1)
290                 {
291                     if (!isc_pp_read (ispt[n], ti->tmpbuf))
292                     {
293                         heap_delete (ti);
294                         isc_pp_close (ispt[n]);
295                         break;
296                     }
297                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
298                     {
299                         heap_delete (ti);
300                         heap_insert (ti, ti->tmpbuf, n);
301                         break;
302                     }
303                 }
304             }
305         }
306         heap_close (ti);
307         xfree (ispt);
308     }
309
310     else if (zi->reg->isamd)
311     {
312         ISAMD_PP *ispt;
313         int i;
314         struct trunc_info *ti;
315
316         ispt = (ISAMD_PP *) xmalloc (sizeof(*ispt) * (to-from));
317
318         ti = heap_init (to-from, sizeof(struct it_key),
319                         key_compare_it);
320         for (i = to-from; --i >= 0; )
321         {
322             ispt[i] = isamd_pp_open (zi->reg->isamd, isam_p[from+i]);
323             if (isamd_pp_read (ispt[i], ti->tmpbuf))
324                 heap_insert (ti, ti->tmpbuf, i);
325             else
326                 isamd_pp_close (ispt[i]);
327         }
328         while (ti->heapnum)
329         {
330             int n = ti->indx[ti->ptr[1]];
331
332             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
333 #if 0
334 /* section that preserve all keys */
335             heap_delete (ti);
336             if (isamd_pp_read (ispt[n], ti->tmpbuf))
337                 heap_insert (ti, ti->tmpbuf, n);
338             else
339                 isamd_pp_close (ispt[n]);
340 #else
341 /* section that preserve all keys with unique sysnos */
342             while (1)
343             {
344                 if (!isamd_pp_read (ispt[n], ti->tmpbuf))
345                 {
346                     heap_delete (ti);
347                     isamd_pp_close (ispt[n]);
348                     break;
349                 }
350                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
351                 {
352                     heap_delete (ti);
353                     heap_insert (ti, ti->tmpbuf, n);
354                     break;
355                 }
356             }
357 #endif
358         }
359         heap_close (ti);
360         xfree (ispt);
361     }
362     else if (zi->reg->isams)
363     {
364         ISAMS_PP *ispt;
365         int i;
366         struct trunc_info *ti;
367
368         ispt = (ISAMS_PP *) xmalloc (sizeof(*ispt) * (to-from));
369
370         ti = heap_init (to-from, sizeof(struct it_key),
371                         key_compare_it);
372         for (i = to-from; --i >= 0; )
373         {
374             ispt[i] = isams_pp_open (zi->reg->isams, isam_p[from+i]);
375             if (isams_pp_read (ispt[i], ti->tmpbuf))
376                 heap_insert (ti, ti->tmpbuf, i);
377             else
378                 isams_pp_close (ispt[i]);
379         }
380         while (ti->heapnum)
381         {
382             int n = ti->indx[ti->ptr[1]];
383
384             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
385             while (1)
386             {
387                 if (!isams_pp_read (ispt[n], ti->tmpbuf))
388                 {
389                     heap_delete (ti);
390                     isams_pp_close (ispt[n]);
391                     break;
392                 }
393                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
394                 {
395                     heap_delete (ti);
396                     heap_insert (ti, ti->tmpbuf, n);
397                     break;
398                 }
399             }
400         }
401         heap_close (ti);
402         xfree (ispt);
403     }
404     else if (zi->reg->isamb)
405     {
406         ISAMB_PP *ispt;
407         int i;
408         struct trunc_info *ti;
409
410         ispt = (ISAMB_PP *) xmalloc (sizeof(*ispt) * (to-from));
411
412         ti = heap_init (to-from, sizeof(struct it_key),
413                         key_compare_it);
414         for (i = to-from; --i >= 0; )
415         {
416             ispt[i] = isamb_pp_open (zi->reg->isamb, isam_p[from+i]);
417             if (isamb_pp_read (ispt[i], ti->tmpbuf))
418                 heap_insert (ti, ti->tmpbuf, i);
419             else
420                 isamb_pp_close (ispt[i]);
421         }
422         while (ti->heapnum)
423         {
424             int n = ti->indx[ti->ptr[1]];
425
426             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
427
428             if (preserve_position)
429             {
430                 heap_delete (ti);
431                 if (isamb_pp_read (ispt[n], ti->tmpbuf))
432                     heap_insert (ti, ti->tmpbuf, n);
433                 else
434                     isamb_pp_close (ispt[n]);
435             }
436             else
437             {
438                 while (1)
439                 {
440                     if (!isamb_pp_read (ispt[n], ti->tmpbuf))
441                     {
442                         heap_delete (ti);
443                         isamb_pp_close (ispt[n]);
444                         break;
445                     }
446                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
447                     {
448                         heap_delete (ti);
449                         heap_insert (ti, ti->tmpbuf, n);
450                         break;
451                     }
452                 }
453             }
454         }
455         heap_close (ti);
456         xfree (ispt);
457     }
458     else
459         logf (LOG_WARN, "Unknown isam set in rset_trunc_r");
460
461     rset_close (result, result_rsfd);
462     return result;
463 }
464
465 static int isams_trunc_cmp (const void *p1, const void *p2)
466 {
467     ISAMS_P i1 = *(ISAMS_P*) p1;
468     ISAMS_P i2 = *(ISAMS_P*) p2;
469
470     return i1 - i2;
471 }
472
473 static int isam_trunc_cmp (const void *p1, const void *p2)
474 {
475     ISAM_P i1 = *(ISAM_P*) p1;
476     ISAM_P i2 = *(ISAM_P*) p2;
477     int d;
478
479     d = is_type (i1) - is_type (i2);
480     if (d)
481         return d;
482     return is_block (i1) - is_block (i2);
483 }
484
485 static int isamc_trunc_cmp (const void *p1, const void *p2)
486 {
487     ISAMC_P i1 = *(ISAMC_P*) p1;
488     ISAMC_P i2 = *(ISAMC_P*) p2;
489     int d;
490
491     d = isc_type (i1) - isc_type (i2);
492     if (d)
493         return d;
494     return isc_block (i1) - isc_block (i2);
495 }
496 static int isamd_trunc_cmp (const void *p1, const void *p2)
497 {
498     ISAMD_P i1 = *(ISAMD_P*) p1;
499     ISAMD_P i2 = *(ISAMD_P*) p2;
500     int d;
501
502     d = isamd_type (i1) - isamd_type (i2);
503     if (d)
504         return d;
505     return isamd_block (i1) - isamd_block (i2);
506 }
507
508 RSET rset_trunc (ZebraHandle zi, ISAMS_P *isam_p, int no,
509                  const char *term, int length, const char *flags,
510                  int preserve_position)
511 {
512     logf (LOG_DEBUG, "rset_trunc no=%d", no);
513     if (no < 1)
514     {
515         rset_null_parms parms;
516         parms.rset_term = rset_term_create (term, length, flags);
517         return rset_create (rset_kind_null, &parms);
518     }
519     if (zi->reg->isams)
520     {
521         if (no == 1)
522         {
523             rset_isams_parms parms;
524
525             parms.pos = *isam_p;
526             parms.is = zi->reg->isams;
527             parms.rset_term = rset_term_create (term, length, flags);
528             return rset_create (rset_kind_isams, &parms);
529         }
530         qsort (isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
531     }
532     else if (zi->reg->isam)
533     {
534         if (no == 1)
535         {
536             rset_isam_parms parms;
537
538             parms.pos = *isam_p;
539             parms.is = zi->reg->isam;
540             parms.rset_term = rset_term_create (term, length, flags);
541             return rset_create (rset_kind_isam, &parms);
542         }
543         qsort (isam_p, no, sizeof(*isam_p), isam_trunc_cmp);
544     }
545     else if (zi->reg->isamc)
546     {
547         if (no == 1)
548         {
549             rset_isamc_parms parms;
550
551             parms.key_size = sizeof(struct it_key);
552             parms.cmp = key_compare_it;
553             parms.pos = *isam_p;
554             parms.is = zi->reg->isamc;
555             parms.rset_term = rset_term_create (term, length, flags);
556             return rset_create (rset_kind_isamc, &parms);
557         }
558 #if NEW_TRUNC
559         else if (no < 10000)
560         {
561             rset_m_or_parms parms;
562
563             parms.key_size = sizeof(struct it_key);
564             parms.cmp = key_compare_it;
565             parms.isc = zi->reg->isamc;
566             parms.isam_positions = isam_p;
567             parms.no_isam_positions = no;
568             parms.no_save_positions = 100000;
569             parms.rset_term = rset_term_create (term, length, flags);
570             return rset_create (rset_kind_m_or, &parms);
571         }
572 #endif
573         qsort (isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
574     }
575     else if (zi->reg->isamd)
576     {
577         if (no == 1)
578         {
579             rset_isamd_parms parms;
580
581             parms.pos = *isam_p;
582             parms.is = zi->reg->isamd;
583             parms.rset_term = rset_term_create (term, length, flags);
584             return rset_create (rset_kind_isamd, &parms);
585         }
586 #if NEW_TRUNC_NOT_DONE_FOR_ISAM_D
587         else if (no < 10000)
588         {
589             rset_m_or_parms parms;
590
591             parms.key_size = sizeof(struct it_key);
592             parms.cmp = key_compare_it;
593             parms.isc = 0;
594             parms.isamd=zi->reg->isamd;
595             parms.isam_positions = isam_p;
596             parms.no_isam_positions = no;
597             parms.no_save_positions = 100000;
598             parms.rset_term = rset_term_create (term, length, flags);
599             return rset_create (rset_kind_m_or, &parms);
600         }
601 #endif
602         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
603     }
604     else if (zi->reg->isamb)
605     {
606         if (no == 1)
607         {
608             rset_isamb_parms parms;
609
610             parms.key_size = sizeof(struct it_key);
611             parms.cmp = key_compare_it;
612             parms.pos = *isam_p;
613             parms.is = zi->reg->isamb;
614             parms.rset_term = rset_term_create (term, length, flags);
615             return rset_create (rset_kind_isamb, &parms);
616         }
617         qsort (isam_p, no, sizeof(*isam_p), isamd_trunc_cmp);
618     }
619     else
620     {
621         logf (LOG_WARN, "Unknown isam set in rset_trunc");
622         return rset_create (rset_kind_null, NULL);
623     }
624     return rset_trunc_r (zi, term, length, flags, isam_p, 0, no, 100,
625                          preserve_position);
626 }
627