Updated footer comment
[idzebra-moved-to-github.git] / index / trunc.c
1 /* This file is part of the Zebra server.
2    Copyright (C) 1994-2009 Index Data
3
4 Zebra is free software; you can redistribute it and/or modify it under
5 the terms of the GNU General Public License as published by the Free
6 Software Foundation; either version 2, or (at your option) any later
7 version.
8
9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17
18 */
19
20
21 #include <stdio.h>
22 #include <assert.h>
23
24 #include "index.h"
25 #include <rset.h>
26
27 struct trunc_info {
28     int  *ptr;
29     int  *indx;
30     char **heap;
31     int  heapnum;
32     int  (*cmp)(const void *p1, const void *p2);
33     int  keysize;
34     char *swapbuf;
35     char *tmpbuf;
36     char *buf;
37 };
38
39 static void heap_swap(struct trunc_info *ti, int i1, int i2)
40 {
41     int swap;
42
43     swap = ti->ptr[i1];
44     ti->ptr[i1] = ti->ptr[i2];
45     ti->ptr[i2] = swap;
46 }
47
48 static void heap_delete(struct trunc_info *ti)
49 {
50     int cur = 1, child = 2;
51
52     heap_swap(ti, 1, ti->heapnum--);
53     while (child <= ti->heapnum) {
54         if (child < ti->heapnum &&
55             (*ti->cmp)(ti->heap[ti->ptr[child]],
56                        ti->heap[ti->ptr[1+child]]) > 0)
57             child++;
58         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
59                        ti->heap[ti->ptr[child]]) > 0)
60         {
61             heap_swap(ti, cur, child);
62             cur = child;
63             child = 2*cur;
64         }
65         else
66             break;
67     }
68 }
69
70 static void heap_insert(struct trunc_info *ti, const char *buf, int indx)
71 {
72     int cur, parent;
73
74     cur = ++(ti->heapnum);
75     memcpy(ti->heap[ti->ptr[cur]], buf, ti->keysize);
76     ti->indx[ti->ptr[cur]] = indx;
77     parent = cur/2;
78     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
79                                 ti->heap[ti->ptr[cur]]) > 0)
80     {
81         heap_swap(ti, cur, parent);
82         cur = parent;
83         parent = cur/2;
84     }
85 }
86
87 static struct trunc_info *heap_init(int size, int key_size,
88                                     int (*cmp)(const void *p1,
89                                                const void *p2))
90 {
91     struct trunc_info *ti = (struct trunc_info *) xmalloc(sizeof(*ti));
92     int i;
93
94     ++size;
95     ti->heapnum = 0;
96     ti->keysize = key_size;
97     ti->cmp = cmp;
98     ti->indx = (int *) xmalloc(size * sizeof(*ti->indx));
99     ti->heap = (char **) xmalloc(size * sizeof(*ti->heap));
100     ti->ptr = (int *) xmalloc(size * sizeof(*ti->ptr));
101     ti->swapbuf = (char *) xmalloc(ti->keysize);
102     ti->tmpbuf = (char *) xmalloc(ti->keysize);
103     ti->buf = (char *) xmalloc(size * ti->keysize);
104     for (i = size; --i >= 0; )
105     {
106         ti->ptr[i] = i;
107         ti->heap[i] = ti->buf + ti->keysize * i;
108     }
109     return ti;
110 }
111
112 static void heap_close(struct trunc_info *ti)
113 {
114     xfree(ti->ptr);
115     xfree(ti->indx);
116     xfree(ti->heap);
117     xfree(ti->swapbuf);
118     xfree(ti->tmpbuf);
119     xfree(ti->buf);
120     xfree(ti);
121 }
122
123 static RSET rset_trunc_r(ZebraHandle zi, const char *term, int length,
124                          const char *flags, ISAM_P *isam_p, int from, int to,
125                          int merge_chunk, int preserve_position,
126                          int term_type, NMEM rset_nmem,
127                          struct rset_key_control *kctrl, int scope,
128                          TERMID termid)
129 {
130     RSET result;
131     RSFD result_rsfd;
132     int nn = 0;
133
134     result = rset_create_temp(rset_nmem, kctrl, scope,
135                               res_get(zi->res, "setTmpDir"), termid);
136     result_rsfd = rset_open(result, RSETF_WRITE);
137
138     if (to - from > merge_chunk)
139     {
140         RSFD *rsfd;
141         RSET *rset;
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         int cmp_border = preserve_position ? 0 : 1;
147         NMEM rset_nmem_sub = nmem_create(); /* all sub rsets not needed
148                                                after this */
149         
150         rset = (RSET *) xmalloc(sizeof(*rset) * rsmax);
151         rsfd = (RSFD *) xmalloc(sizeof(*rsfd) * rsmax);
152         
153         for (i = from; i < to; i += i_add)
154         {
155             if (i_add <= to - i)
156                 rset[rscur] = rset_trunc_r(zi, term, length, flags,
157                                            isam_p, i, i+i_add,
158                                            merge_chunk, preserve_position,
159                                            term_type, rset_nmem_sub, 
160                                            kctrl, scope, 0);
161             else
162                 rset[rscur] = rset_trunc_r(zi, term, length, flags,
163                                            isam_p, i, to,
164                                            merge_chunk, preserve_position,
165                                            term_type, rset_nmem_sub, 
166                                            kctrl, scope, 0);
167             rscur++;
168         }
169         ti = heap_init (rscur, sizeof(struct it_key), key_compare_it);
170         for (i = rscur; --i >= 0; )
171         {
172             rsfd[i] = rset_open(rset[i], RSETF_READ);
173             if (rset_read(rsfd[i], ti->tmpbuf, 0))
174                 heap_insert(ti, ti->tmpbuf, i);
175             else
176             {
177                 rset_close(rsfd[i]);
178                 rset_delete(rset[i]);
179             }
180         }
181         while (ti->heapnum)
182         {
183             int n = ti->indx[ti->ptr[1]];
184
185             rset_write(result_rsfd, ti->heap[ti->ptr[1]]);
186             nn++;
187
188             while (1)
189             {
190                 if(!rset_read (rsfd[n], ti->tmpbuf,0))
191                 {
192                     heap_delete(ti);
193                     rset_close(rsfd[n]);
194                     rset_delete(rset[n]);
195                     break;
196                 }
197                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > cmp_border)
198                 {
199                     heap_delete(ti);
200                     heap_insert(ti, ti->tmpbuf, n);
201                     break;
202                 }
203             }
204         }
205         xfree(rset);
206         xfree(rsfd);
207         heap_close(ti);
208         nmem_destroy(rset_nmem_sub);
209     }
210     else if (zi->reg->isamc)
211     {
212         ISAMC_PP *ispt;
213         int i;
214         struct trunc_info *ti;
215
216         ispt = (ISAMC_PP *) xmalloc(sizeof(*ispt) * (to-from));
217
218         ti = heap_init(to-from, sizeof(struct it_key),
219                        key_compare_it);
220         for (i = to-from; --i >= 0; )
221         {
222             ispt[i] = isamc_pp_open(zi->reg->isamc, isam_p[from+i]);
223             if (isamc_pp_read(ispt[i], ti->tmpbuf))
224                 heap_insert(ti, ti->tmpbuf, i);
225             else
226                 isamc_pp_close(ispt[i]);
227         }
228         while (ti->heapnum)
229         {
230             int n = ti->indx[ti->ptr[1]];
231
232             rset_write(result_rsfd, ti->heap[ti->ptr[1]]);
233             nn++;
234             if (preserve_position)
235             {
236                 heap_delete(ti);
237                 if (isamc_pp_read(ispt[n], ti->tmpbuf))
238                     heap_insert(ti, ti->tmpbuf, n);
239                 else
240                     isamc_pp_close(ispt[n]);
241             }
242             else
243             {
244                 while (1)
245                 {
246                     if (!isamc_pp_read(ispt[n], ti->tmpbuf))
247                     {
248                         heap_delete(ti);
249                         isamc_pp_close(ispt[n]);
250                         break;
251                     }
252                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
253                     {
254                         heap_delete(ti);
255                         heap_insert(ti, ti->tmpbuf, n);
256                         break;
257                     }
258                 }
259             }
260         }
261         heap_close(ti);
262         xfree(ispt);
263     }
264     else if (zi->reg->isams)
265     {
266         ISAMS_PP *ispt;
267         int i;
268         struct trunc_info *ti;
269         int nn = 0;
270
271         ispt = (ISAMS_PP *) xmalloc(sizeof(*ispt) * (to-from));
272
273         ti = heap_init(to-from, sizeof(struct it_key),
274                        key_compare_it);
275         for (i = to-from; --i >= 0; )
276         {
277             ispt[i] = isams_pp_open(zi->reg->isams, isam_p[from+i]);
278             if (isams_pp_read(ispt[i], ti->tmpbuf))
279                 heap_insert(ti, ti->tmpbuf, i);
280             else
281                 isams_pp_close(ispt[i]);
282         }
283         while (ti->heapnum)
284         {
285             int n = ti->indx[ti->ptr[1]];
286
287             rset_write(result_rsfd, ti->heap[ti->ptr[1]]);
288             nn++;
289             while (1)
290             {
291                 if (!isams_pp_read(ispt[n], ti->tmpbuf))
292                 {
293                     heap_delete(ti);
294                     isams_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         heap_close(ti);
306         xfree(ispt);
307     }
308     else if (zi->reg->isamb)
309     {
310         ISAMB_PP *ispt;
311         int i;
312         struct trunc_info *ti;
313
314         ispt = (ISAMB_PP *) xmalloc(sizeof(*ispt) * (to-from));
315
316         ti = heap_init(to-from, sizeof(struct it_key),
317                        key_compare_it);
318         for (i = to-from; --i >= 0; )
319         {
320             if (isam_p[from+i]) {
321                 ispt[i] = isamb_pp_open(zi->reg->isamb, isam_p[from+i], scope);
322                 if (isamb_pp_read(ispt[i], ti->tmpbuf))
323                     heap_insert(ti, ti->tmpbuf, i);
324                 else
325                     isamb_pp_close(ispt[i]);
326             }
327         }
328         while (ti->heapnum)
329         {
330             int n = ti->indx[ti->ptr[1]];
331
332             rset_write(result_rsfd, ti->heap[ti->ptr[1]]);
333             nn++;
334
335             if (preserve_position)
336             {
337                 heap_delete(ti);
338                 if (isamb_pp_read(ispt[n], ti->tmpbuf))
339                     heap_insert(ti, ti->tmpbuf, n);
340                 else
341                     isamb_pp_close(ispt[n]);
342             }
343             else
344             {
345                 while (1)
346                 {
347                     if (!isamb_pp_read(ispt[n], ti->tmpbuf))
348                     {
349                         heap_delete(ti);
350                         isamb_pp_close(ispt[n]);
351                         break;
352                     }
353                     if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
354                     {
355                         heap_delete(ti);
356                         heap_insert(ti, ti->tmpbuf, n);
357                         break;
358                     }
359                 }
360             }
361         }
362         heap_close(ti);
363         xfree(ispt);
364     }
365     else
366         yaz_log(YLOG_WARN, "Unknown isam set in rset_trunc_r");
367
368     rset_close(result_rsfd);
369     return result;
370 }
371
372 static int isams_trunc_cmp(const void *p1, const void *p2)
373 {
374     ISAM_P i1 = *(ISAM_P*) p1;
375     ISAM_P i2 = *(ISAM_P*) p2;
376
377     if (i1 > i2)
378         return 1;
379     else if (i1 < i2)
380         return -1;
381     return 0;
382 }
383
384 static int isamc_trunc_cmp(const void *p1, const void *p2)
385 {
386     ISAM_P i1 = *(ISAM_P*) p1;
387     ISAM_P i2 = *(ISAM_P*) p2;
388     zint d;
389
390     d = (isamc_type(i1) - isamc_type(i2));
391     if (d == 0)
392         d = isamc_block(i1) - isamc_block(i2);
393     if (d > 0)
394         return 1;
395     else if (d < 0)
396         return -1;
397     return 0;
398 }
399
400 RSET rset_trunc(ZebraHandle zh, ISAM_P *isam_p, int no,
401                 const char *term, int length, const char *flags,
402                 int preserve_position, int term_type, NMEM rset_nmem,
403                 struct rset_key_control *kctrl, int scope,
404                 struct ord_list *ol, const char *index_type,
405                 zint hits_limit, const char *term_ref_id)
406 {
407     TERMID termid;
408     RSET result;
409     int trunc_chunk;
410     int trunc_limit = atoi(res_get_def(zh->res, "trunclimit", "10000"));
411
412     termid = rset_term_create(term, length, flags, term_type, rset_nmem, ol,
413                               *index_type, hits_limit, term_ref_id);
414     
415     if (no < 1)
416         return rset_create_null(rset_nmem, kctrl, termid);
417     else if (no == 1)
418         return zebra_create_rset_isam(zh, rset_nmem, kctrl,
419                                       scope, *isam_p, termid);
420     else if (zh->reg->isamb && no > 1 && no < trunc_limit)
421     {
422         RSET r;
423         RSET *rsets = xmalloc(no*sizeof(RSET)); /* use nmem! */
424         int i;
425         for (i = 0; i<no; i++)
426             rsets[i] = rsisamb_create(rset_nmem, kctrl, scope,
427                                       zh->reg->isamb, isam_p[i],
428                                       0 /* termid */);
429         r = rset_create_or(rset_nmem, kctrl, scope,
430                            termid, no, rsets);
431         xfree(rsets);
432         return r;
433     }
434     if (zh->reg->isamc)
435         qsort(isam_p, no, sizeof(*isam_p), isamc_trunc_cmp);
436     else
437         qsort(isam_p, no, sizeof(*isam_p), isams_trunc_cmp);
438     trunc_chunk = atoi(res_get_def(zh->res, "truncchunk", "20"));
439     result = rset_trunc_r(zh, term, length, flags, isam_p, 0, no, trunc_chunk,
440                           preserve_position, term_type, rset_nmem, kctrl,
441                           scope, termid);
442     return result;
443 }
444
445 /*
446  * Local variables:
447  * c-basic-offset: 4
448  * c-file-style: "Stroustrup"
449  * indent-tabs-mode: nil
450  * End:
451  * vim: shiftwidth=4 tabstop=8 expandtab
452  */
453