65bed28900fdb9141360519955d1c520960423f8
[idzebra-moved-to-github.git] / isamb / isamb.c
1 /*
2  *  Copyright (c) 1995-1998, Index Data.
3  *  See the file LICENSE for details.
4  *
5  *  $Id: isamb.c,v 1.6 2002-04-17 09:03:38 adam Exp $
6  */
7 #include <yaz/xmalloc.h>
8 #include <yaz/log.h>
9 #include <isamb.h>
10 #include <assert.h>
11
12 struct ISAMB_head {
13     int first_block;
14     int last_block;
15     int block_size;
16 };
17
18 #define ISAMB_DATA_OFFSET 3
19
20 #define DST_BUF_SIZE 4500
21 #define DST_ITEM_MAX 256
22
23 struct ISAMB_file {
24     BFile bf;
25     int head_dirty;
26     struct ISAMB_head head;
27 };
28
29 struct ISAMB_s {
30     BFiles bfs;
31     ISAMC_M method;
32
33     struct ISAMB_file *file;
34     int no_cat;
35 };
36
37 struct ISAMB_block {
38     int pos;
39     int cat;
40     int size;
41     int leaf;
42     int dirty;
43     int offset;
44     unsigned char *bytes;
45     void *decodeClientData;
46 };
47
48 struct ISAMB_PP_s {
49     ISAMB isamb;
50     int level;
51     struct ISAMB_block **block;
52 };
53
54 void encode_ptr (char **dst, int pos)
55 {
56     memcpy (*dst, &pos, sizeof(pos));
57     (*dst) += sizeof(pos);
58 }
59
60 void decode_ptr (char **src, int *pos)
61 {
62     memcpy (pos, *src, sizeof(*pos));
63     (*src) += sizeof(*pos);
64 }
65
66 ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method)
67 {
68     ISAMB isamb = xmalloc (sizeof(*isamb));
69     int i, b_size = 64;
70
71     isamb->bfs = bfs;
72     isamb->method = (ISAMC_M) xmalloc (sizeof(*method));
73     memcpy (isamb->method, method, sizeof(*method));
74     isamb->no_cat = 2;
75
76     isamb->file = xmalloc (sizeof(*isamb->file) * isamb->no_cat);
77     for (i = 0; i<isamb->no_cat; i++)
78     {
79         char fname[DST_BUF_SIZE];
80         isamb->file[i].head.first_block = 1;
81         isamb->file[i].head.last_block = 1;
82         isamb->file[i].head.block_size = b_size;
83         b_size = b_size * 4;
84         isamb->file[i].head_dirty = 0;
85         sprintf (fname, "%s-%d", name, i);
86         isamb->file[i].bf =
87             bf_open (bfs, fname, isamb->file[i].head.block_size, writeflag);
88     
89         bf_read (isamb->file[i].bf, 0, 0, sizeof(struct ISAMB_head),
90                  &isamb->file[i].head);
91     }
92     return isamb;
93 }
94
95 void isamb_close (ISAMB isamb)
96 {
97     int i;
98     for (i = 0; i<isamb->no_cat; i++)
99     {
100         if (isamb->file[i].head_dirty)
101             bf_write (isamb->file[i].bf, 0, 0,
102                       sizeof(struct ISAMB_head), &isamb->file[i].head);
103     }
104     xfree (isamb->file);
105     xfree (isamb->method);
106     xfree (isamb);
107 }
108
109 struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos)
110 {
111     int cat = pos&3;
112     struct ISAMB_block *p;
113     if (!pos)
114         return 0;
115     p = xmalloc (sizeof(*p));
116     p->pos = pos;
117     p->cat = pos & 3;
118     p->bytes = xmalloc (b->file[cat].head.block_size);
119     bf_read (b->file[cat].bf, pos/4, 0, 0, p->bytes);
120     p->leaf = p->bytes[0];
121     p->size = p->bytes[1] + 256 * p->bytes[2];
122     p->offset = ISAMB_DATA_OFFSET;
123     p->dirty = 0;
124     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
125     return p;
126 }
127
128 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
129 {
130     struct ISAMB_block *p;
131     int block_no;
132     
133     p = xmalloc (sizeof(*p));
134     block_no = b->file[cat].head.last_block++;
135     p->cat = cat;
136     p->pos = block_no * 4 + cat;
137     p->cat = cat;
138     b->file[cat].head_dirty = 1;
139     p->bytes = xmalloc (b->file[cat].head.block_size);
140     memset (p->bytes, 0, b->file[cat].head.block_size);
141     p->leaf = leaf;
142     p->size = ISAMB_DATA_OFFSET;
143     p->dirty = 1;
144     p->offset = ISAMB_DATA_OFFSET;
145     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
146     return p;
147 }
148
149 void close_block (ISAMB b, struct ISAMB_block *p)
150 {
151     if (!p)
152         return;
153     if (p->dirty)
154     {
155         p->bytes[0] = p->leaf;
156         p->bytes[1] = p->size & 255;
157         p->bytes[2] = p->size >> 8;
158         bf_write (b->file[p->cat].bf, p->pos/4, 0, 0, p->bytes);
159     }
160     (*b->method->code_stop)(ISAMC_DECODE, p->decodeClientData);
161     xfree (p->bytes);
162     xfree (p);
163 }
164
165 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
166                  struct ISAMB_block **sp,
167                  void *sub_item, int *sub_size);
168
169 void insert_leaf (ISAMB b, struct ISAMB_block *p, const void *new_item,
170                   struct ISAMB_block **sp,
171                   void *sub_item, int *sub_size)
172 {
173     char dst_buf[DST_BUF_SIZE];
174     char *dst = dst_buf;
175     char *src = p->bytes + ISAMB_DATA_OFFSET;
176     char *endp = p->bytes + p->size;
177     void *c1 = (*b->method->code_start)(ISAMC_DECODE);
178     void *c2 = (*b->method->code_start)(ISAMC_ENCODE);
179     char *half1 = 0;
180     char *half2 = 0;
181     char *cut = dst_buf + p->size / 2;
182     char cut_item_buf[DST_ITEM_MAX];
183     int cut_item_size = 0;
184
185     while (src != endp)
186     {
187         char file_item_buf[DST_ITEM_MAX];
188         char *file_item = file_item_buf;
189
190         (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
191         if (new_item)
192         {
193             int d = (*b->method->compare_item)(file_item_buf, new_item);
194             if (d > 0)
195             {
196                 char *item_ptr = (char*) new_item;
197                 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
198                 new_item = 0;
199                 p->dirty = 1;
200             }
201             else if (d == 0)
202             {
203                 new_item = 0;
204             }
205         }
206         
207         if (!half1 && dst > cut)   
208         {
209             half1 = dst; /* candidate for splitting */
210
211             file_item = file_item_buf;
212             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
213
214             cut_item_size = file_item - file_item_buf;
215             memcpy (cut_item_buf, file_item_buf, cut_item_size);
216
217             half2 = dst;
218         }
219         else
220         {
221             file_item = file_item_buf;
222             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
223         }
224     }
225     if (new_item)
226     {
227         char *item_ptr = (char*) new_item;
228         (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
229         new_item = 0;
230         p->dirty = 1;
231     }
232     p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
233     if (p->size > b->file[p->cat].head.block_size)
234     {
235         char *first_dst;
236         char *cut_item = cut_item_buf;
237  
238        /* first half */
239         p->size = half1 - dst_buf + ISAMB_DATA_OFFSET;
240         memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, half1 - dst_buf);
241
242         /* second half */
243         *sp = new_block (b, 1, p->cat);
244
245         (*b->method->code_reset)(c2);
246
247         first_dst = (*sp)->bytes + ISAMB_DATA_OFFSET;
248
249         (*b->method->code_item)(ISAMC_ENCODE, c2, &first_dst, &cut_item);
250
251         memcpy (first_dst, half2, dst - half2);
252
253         (*sp)->size = (first_dst - (char*) (*sp)->bytes) + (dst - half2);
254         (*sp)->dirty = 1;
255         p->dirty = 1;
256         memcpy (sub_item, cut_item_buf, cut_item_size);
257         *sub_size = cut_item_size;
258
259         yaz_log (LOG_LOG, "l split %d / %d", p->size, (*sp)->size);
260
261     }
262     else
263     {
264         assert (p->size > ISAMB_DATA_OFFSET);
265         assert (p->size <= b->file[p->cat].head.block_size);
266         memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, dst - dst_buf);
267         *sp = 0;
268     }
269     (*b->method->code_stop)(ISAMC_DECODE, c1);
270     (*b->method->code_stop)(ISAMC_ENCODE, c2);
271 }
272
273 void insert_int (ISAMB b, struct ISAMB_block *p, const void *new_item,
274                  struct ISAMB_block **sp,
275                  void *split_item, int *split_size)
276 {
277     char *startp = p->bytes + ISAMB_DATA_OFFSET;
278     char *src = startp;
279     char *endp = p->bytes + p->size;
280     int pos;
281     struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
282     char sub_item[DST_ITEM_MAX];
283     int sub_size;
284
285     *sp = 0;
286
287     decode_ptr (&src, &pos);
288     while (src != endp)
289     {
290         int item_len;
291         int d;
292         decode_ptr (&src, &item_len);
293         d = (*b->method->compare_item)(src, new_item);
294         if (d > 0)
295         {
296             sub_p1 = open_block (b, pos);
297             assert (sub_p1);
298             insert_sub (b, sub_p1, new_item, &sub_p2, 
299                         sub_item, &sub_size);
300             break;
301         }
302         src += item_len;
303         decode_ptr (&src, &pos);
304     }
305     if (!sub_p1)
306     {
307         sub_p1 = open_block (b, pos);
308         assert (sub_p1);
309         insert_sub (b, sub_p1, new_item, &sub_p2, 
310                     sub_item, &sub_size);
311     }
312     if (sub_p2)
313     {
314         char dst_buf[DST_BUF_SIZE];
315         char *dst = dst_buf;
316
317         assert (sub_size < 20);
318
319         memcpy (dst, startp, src - startp);
320                 
321         dst += src - startp;
322
323         encode_ptr (&dst, sub_size);      /* sub length and item */
324         memcpy (dst, sub_item, sub_size);
325         dst += sub_size;
326
327         encode_ptr (&dst, sub_p2->pos);   /* pos */
328
329         if (endp - src)                   /* remaining data */
330         {
331             memcpy (dst, src, endp - src);
332             dst += endp - src;
333         }
334         p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
335         if (p->size <= b->file[p->cat].head.block_size)
336         {
337             memcpy (startp, dst_buf, dst - dst_buf);
338         }
339         else
340         {
341             int p_new_size;
342             char *half;
343             src = dst_buf;
344             endp = dst;
345
346             half = src + b->file[p->cat].head.block_size/2;
347             decode_ptr (&src, &pos);
348             while (src <= half)
349             {
350                 decode_ptr (&src, split_size);
351                 src += *split_size;
352                 decode_ptr (&src, &pos);
353             }
354             p_new_size = src - dst_buf;
355             memcpy (p->bytes + ISAMB_DATA_OFFSET, dst_buf, p_new_size);
356             p_new_size += ISAMB_DATA_OFFSET;
357
358             decode_ptr (&src, split_size);
359             memcpy (split_item, src, *split_size);
360             src += *split_size;
361
362             *sp = new_block (b, 0, p->cat);
363             (*sp)->size = endp - src;
364             memcpy ((*sp)->bytes+ISAMB_DATA_OFFSET, src, (*sp)->size);
365             (*sp)->size += ISAMB_DATA_OFFSET;
366
367             yaz_log (LOG_LOG, "i split %d -> %d %d",
368                      p->size, p_new_size, (*sp)->size);
369             p->size = p_new_size;
370         }
371         p->dirty = 1;
372         close_block (b, sub_p2);
373     }
374     close_block (b, sub_p1);
375 }
376
377 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
378                 struct ISAMB_block **sp,
379                 void *sub_item, int *sub_size)
380 {
381     if (p->leaf)
382         insert_leaf (b, p, new_item, sp, sub_item, sub_size);
383     else
384         insert_int (b, p, new_item, sp, sub_item, sub_size);
385 }
386
387 int insert_flat (ISAMB b, const void *new_item, ISAMC_P *posp)
388 {
389     struct ISAMB_block *p = 0;
390     char *src = 0, *endp = 0;
391     char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
392     int new_size;
393     ISAMB_P pos = *posp;
394     void *c1 = (*b->method->code_start)(ISAMC_DECODE);
395     void *c2 = (*b->method->code_start)(ISAMC_ENCODE);
396     
397     if (pos)
398     {
399         p = open_block (b, pos);
400         if (!p)
401             return -1;
402         src = p->bytes + ISAMB_DATA_OFFSET;
403         endp = p->bytes + p->size;
404
405     }
406     while (p && src != endp)
407     {
408         char file_item_buf[DST_ITEM_MAX];
409         char *file_item = file_item_buf;
410
411         (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
412         if (new_item)
413         {
414             int d = (*b->method->compare_item)(file_item_buf, new_item);
415             if (d > 0)
416             {
417                 char *item_ptr = (char*) new_item;
418                 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
419                 new_item = 0;
420                 p->dirty = 1;
421             }
422             else if (d == 0)
423             {
424                 new_item = 0;
425             }
426         }
427         file_item = file_item_buf;
428         (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
429     }
430     if (new_item)
431     {
432         char *item_ptr = (char*) new_item;
433         (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
434         new_item = 0;
435         if (p)
436             p->dirty = 1;
437     }
438     new_size = dst - dst_buf + ISAMB_DATA_OFFSET;
439     if (p && new_size > b->file[p->cat].head.block_size)
440     {
441         yaz_log (LOG_LOG, "resize %d -> %d", p->size, new_size);
442         close_block (b, p);
443         /* delete it too!! */
444         p = 0; /* make a new one anyway */
445     }
446     if (!p)
447     {   /* must create a new one */
448         int i;
449         for (i = 0; i < b->no_cat; i++)
450             if (new_size <= b->file[i].head.block_size)
451                 break;
452         p = new_block (b, 1, i);
453     }
454     memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, dst - dst_buf);
455     p->size = new_size;
456     *posp = p->pos;
457     (*b->method->code_stop)(ISAMC_DECODE, c1);
458     (*b->method->code_stop)(ISAMC_ENCODE, c2);
459     close_block (b, p);
460     return 0;
461 }
462
463 int isamb_insert_one (ISAMB b, const void *item, ISAMC_P pos)
464 {
465
466     if ((pos & 3) != b->no_cat-1)
467     {
468         /* note if pos == 0 we go here too! */
469         /* flat insert */
470         insert_flat (b, item, &pos);
471     }
472     else
473     {
474         /* b-tree insert */
475         struct ISAMB_block *p = open_block (b, pos), *sp = 0;
476         char sub_item[DST_ITEM_MAX];
477         int sub_size;
478
479
480         insert_sub (b, p, item, &sp, sub_item, &sub_size);
481         if (sp)
482         {    /* increase level of tree by one */
483             struct ISAMB_block *p2 = new_block (b, 0, p->cat);
484             char *dst = p2->bytes + p2->size;
485             
486             encode_ptr (&dst, p->pos);
487             assert (sub_size < 20);
488             encode_ptr (&dst, sub_size);
489             memcpy (dst, sub_item, sub_size);
490             dst += sub_size;
491             encode_ptr (&dst, sp->pos);
492             
493             p2->size = dst - (char*) p2->bytes;
494             pos = p2->pos;  /* return new super page */
495             close_block (b, sp);
496             close_block (b, p2);
497         }
498         else
499             pos = p->pos;   /* return current one (again) */
500         close_block (b, p);
501     }
502     return pos;
503 }
504
505 ISAMB_P isamb_merge (ISAMB b, ISAMB_P pos, ISAMC_I data)
506 {
507     int i_mode;
508     char item_buf[DST_ITEM_MAX];
509     char *item_ptr = item_buf;
510     while ((*data->read_item)(data->clientData, &item_ptr, &i_mode))
511     {
512         item_ptr = item_buf;
513         pos = isamb_insert_one (b, item_buf, pos);
514     }
515     return pos;
516 }
517
518 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAMB_P pos)
519 {
520     ISAMB_PP pp = xmalloc (sizeof(*pp));
521
522     pp->isamb = isamb;
523     pp->block = xmalloc (10 * sizeof(*pp->block));
524
525     pp->level = 0;
526     while (1)
527     {
528         struct ISAMB_block *p = open_block (isamb, pos);
529         char *src = p->bytes + p->offset;
530         pp->block[pp->level] = p;
531
532         if (p->bytes[0]) /* leaf */
533             break;
534
535         decode_ptr (&src, &pos);
536         p->offset = src - (char*) p->bytes;
537         pp->level++;
538     }
539     pp->block[pp->level+1] = 0;
540     return pp;
541 }
542
543 void isamb_pp_close (ISAMB_PP pp)
544 {
545     int i;
546     if (!pp)
547         return;
548     for (i = 0; i <= pp->level; i++)
549         close_block (pp->isamb, pp->block[i]);
550     xfree (pp->block);
551     xfree (pp);
552 }
553
554 int isamb_pp_read (ISAMB_PP pp, void *buf)
555 {
556     char *dst = buf;
557     char *src;
558     struct ISAMB_block *p = pp->block[pp->level];
559     if (!p)
560         return 0;
561
562     while (p->offset == p->size)
563     {
564         int pos, item_len;
565         while (p->offset == p->size)
566         {
567             if (pp->level == 0)
568                 return 0;
569             close_block (pp->isamb, pp->block[pp->level]);
570             pp->block[pp->level] = 0;
571             (pp->level)--;
572             p = pp->block[pp->level];
573             assert (p->bytes[0] == 0);  /* must be int */
574         }
575         src = p->bytes + p->offset;
576         
577         decode_ptr (&src, &item_len);
578         src += item_len;
579         decode_ptr (&src, &pos);
580         
581         p->offset = src - (char*) p->bytes;
582
583         ++(pp->level);
584         
585         while (1)
586         {
587             pp->block[pp->level] = p = open_block (pp->isamb, pos);
588             
589             if (p->bytes[0]) /* leaf */
590             {
591                 break;
592             }
593             src = p->bytes + p->offset;
594             decode_ptr (&src, &pos);
595             p->offset = src - (char*) p->bytes;
596             pp->level++;
597         }
598     }
599     assert (p->offset < p->size);
600     assert (p->bytes[0]);
601     src = p->bytes + p->offset;
602     (*pp->isamb->method->code_item)(ISAMC_DECODE, p->decodeClientData,
603                                     &dst, &src);
604     p->offset = src - (char*) p->bytes;
605     return 1;
606 }
607
608 int isamb_pp_num (ISAMB_PP pp)
609 {
610     return 1;
611 }