2 #include <yaz/xmalloc.h>
13 #define ISAMB_DATA_OFFSET 3
21 struct ISAMB_head head;
31 void *decodeClientData;
37 struct ISAMB_block **block;
40 void encode_ptr (char **dst, int pos)
42 memcpy (*dst, &pos, sizeof(pos));
43 (*dst) += sizeof(pos);
46 void decode_ptr (char **src, int *pos)
48 memcpy (pos, *src, sizeof(*pos));
49 (*src) += sizeof(*pos);
52 ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method)
54 ISAMB isamb = xmalloc (sizeof(*isamb));
57 isamb->method = (ISAMC_M) xmalloc (sizeof(*method));
58 memcpy (isamb->method, method, sizeof(*method));
60 isamb->head.first_block = 1;
61 isamb->head.last_block = 1;
62 isamb->head.block_size = 1024;
63 isamb->head_dirty = 0;
65 isamb->bf = bf_open (bfs, name, isamb->head.block_size, writeflag);
67 bf_read (isamb->bf, 0, 0, sizeof(struct ISAMB_head),
72 void isamb_close (ISAMB isamb)
74 if (isamb->head_dirty)
75 bf_write (isamb->bf, 0, 0, sizeof(struct ISAMB_head), &isamb->head);
76 xfree (isamb->method);
80 struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos)
82 struct ISAMB_block *p;
85 p = xmalloc (sizeof(*p));
87 p->bytes = xmalloc (b->head.block_size);
88 bf_read (b->bf, pos, 0, 0, p->bytes);
89 p->leaf = p->bytes[0];
90 p->size = p->bytes[1] + 256 * p->bytes[2];
91 p->offset = ISAMB_DATA_OFFSET;
93 p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
97 struct ISAMB_block *new_block (ISAMB b, int leaf)
99 struct ISAMB_block *p;
101 p = xmalloc (sizeof(*p));
102 p->pos = b->head.last_block++;
104 p->bytes = xmalloc (b->head.block_size);
105 memset (p->bytes, 0, b->head.block_size);
107 p->size = ISAMB_DATA_OFFSET;
109 p->offset = ISAMB_DATA_OFFSET;
110 p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
114 void close_block (ISAMB b, struct ISAMB_block *p)
120 p->bytes[0] = p->leaf;
121 p->bytes[1] = p->size & 255;
122 p->bytes[2] = p->size >> 8;
123 bf_write (b->bf, p->pos, 0, 0, p->bytes);
125 (*b->method->code_stop)(ISAMC_DECODE, p->decodeClientData);
130 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
131 struct ISAMB_block **sp,
132 void *sub_item, int *sub_size);
134 void insert_leaf (ISAMB b, struct ISAMB_block *p, const void *new_item,
135 struct ISAMB_block **sp,
136 void *sub_item, int *sub_size)
140 char *src = p->bytes + ISAMB_DATA_OFFSET;
141 char *endp = p->bytes + p->size;
142 void *c1 = (*b->method->code_start)(ISAMC_DECODE);
143 void *c2 = (*b->method->code_start)(ISAMC_ENCODE);
146 char *cut = dst_buf + p->size / 2;
147 char cut_item_buf[256];
148 int cut_item_size = 0;
152 char file_item_buf[256];
153 char *file_item = file_item_buf;
155 (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
158 int d = (*b->method->compare_item)(file_item_buf, new_item);
161 char *item_ptr = (char*) new_item;
162 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
172 if (!half1 && dst > cut)
174 half1 = dst; /* candidate for splitting */
176 file_item = file_item_buf;
177 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
179 cut_item_size = file_item - file_item_buf;
180 memcpy (cut_item_buf, file_item_buf, cut_item_size);
186 file_item = file_item_buf;
187 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
192 char *item_ptr = (char*) new_item;
193 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
197 p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
198 if (p->size > b->head.block_size)
201 char *cut_item = cut_item_buf;
204 p->size = half1 - dst_buf + ISAMB_DATA_OFFSET;
205 memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, half1 - dst_buf);
208 *sp = new_block (b, 1);
210 (*b->method->code_reset)(c2);
212 first_dst = (*sp)->bytes + ISAMB_DATA_OFFSET;
214 (*b->method->code_item)(ISAMC_ENCODE, c2, &first_dst, &cut_item);
216 memcpy (first_dst, half2, dst - half2);
218 (*sp)->size = (first_dst - (char*) (*sp)->bytes) + (dst - half2);
221 memcpy (sub_item, cut_item_buf, cut_item_size);
222 *sub_size = cut_item_size;
224 yaz_log (LOG_LOG, "l split %d / %d", p->size, (*sp)->size);
229 assert (p->size > ISAMB_DATA_OFFSET);
230 assert (p->size <= b->head.block_size);
231 memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, dst - dst_buf);
234 (*b->method->code_stop)(ISAMC_DECODE, c1);
235 (*b->method->code_stop)(ISAMC_ENCODE, c2);
238 void insert_int (ISAMB b, struct ISAMB_block *p, const void *new_item,
239 struct ISAMB_block **sp,
240 void *split_item, int *split_size)
242 char *startp = p->bytes + ISAMB_DATA_OFFSET;
244 char *endp = p->bytes + p->size;
246 struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
252 decode_ptr (&src, &pos);
257 decode_ptr (&src, &item_len);
258 d = (*b->method->compare_item)(src, new_item);
261 sub_p1 = open_block (b, pos);
263 insert_sub (b, sub_p1, new_item, &sub_p2,
264 sub_item, &sub_size);
268 decode_ptr (&src, &pos);
272 sub_p1 = open_block (b, pos);
274 insert_sub (b, sub_p1, new_item, &sub_p2,
275 sub_item, &sub_size);
282 assert (sub_size < 20);
284 memcpy (dst, startp, src - startp);
288 encode_ptr (&dst, sub_size); /* sub length and item */
289 memcpy (dst, sub_item, sub_size);
292 encode_ptr (&dst, sub_p2->pos); /* pos */
294 if (endp - src) /* remaining data */
296 memcpy (dst, src, endp - src);
299 p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
300 if (p->size <= b->head.block_size)
302 memcpy (startp, dst_buf, dst - dst_buf);
311 half = src + b->head.block_size/2;
312 decode_ptr (&src, &pos);
315 decode_ptr (&src, split_size);
317 decode_ptr (&src, &pos);
319 p_new_size = src - dst_buf;
320 memcpy (p->bytes + ISAMB_DATA_OFFSET, dst_buf, p_new_size);
321 p_new_size += ISAMB_DATA_OFFSET;
323 decode_ptr (&src, split_size);
324 memcpy (split_item, src, *split_size);
327 *sp = new_block (b, 0);
328 (*sp)->size = endp - src;
329 memcpy ((*sp)->bytes+ISAMB_DATA_OFFSET, src, (*sp)->size);
330 (*sp)->size += ISAMB_DATA_OFFSET;
332 yaz_log (LOG_LOG, "i split %d -> %d %d",
333 p->size, p_new_size, (*sp)->size);
334 p->size = p_new_size;
337 close_block (b, sub_p2);
339 close_block (b, sub_p1);
342 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
343 struct ISAMB_block **sp,
344 void *sub_item, int *sub_size)
347 insert_leaf (b, p, new_item, sp, sub_item, sub_size);
349 insert_int (b, p, new_item, sp, sub_item, sub_size);
352 int isamb_insert_one (ISAMB b, const void *item, ISAMC_P pos)
354 struct ISAMB_block *p, *sp = 0;
359 p = new_block (b, 1);
361 p = open_block (b, pos);
365 insert_sub (b, p, item, &sp, sub_item, &sub_size);
367 { /* increase level of tree by one */
368 struct ISAMB_block *p2 = new_block (b, 0);
369 char *dst = p2->bytes + p2->size;
371 encode_ptr (&dst, p->pos);
372 assert (sub_size < 20);
373 encode_ptr (&dst, sub_size);
374 memcpy (dst, sub_item, sub_size);
376 encode_ptr (&dst, sp->pos);
378 p2->size = dst - (char*) p2->bytes;
379 pos = p2->pos; /* return new super page */
384 pos = p->pos; /* return current one (again) */
389 ISAMB_P isamb_merge (ISAMB b, ISAMB_P pos, ISAMC_I data)
393 char *item_ptr = item_buf;
394 while ((*data->read_item)(data->clientData, &item_ptr, &i_mode))
397 pos = isamb_insert_one (b, item_buf, pos);
402 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAMB_P pos)
404 ISAMB_PP pp = xmalloc (sizeof(*pp));
407 pp->block = xmalloc (10 * sizeof(*pp->block));
412 struct ISAMB_block *p = open_block (isamb, pos);
413 char *src = p->bytes + p->offset;
414 pp->block[pp->level] = p;
416 if (p->bytes[0]) /* leaf */
419 decode_ptr (&src, &pos);
420 p->offset = src - (char*) p->bytes;
423 pp->block[pp->level+1] = 0;
427 void isamb_pp_close (ISAMB_PP pp)
432 for (i = 0; i <= pp->level; i++)
433 close_block (pp->isamb, pp->block[i]);
438 int isamb_pp_read (ISAMB_PP pp, void *buf)
442 struct ISAMB_block *p = pp->block[pp->level];
446 while (p->offset == p->size)
449 while (p->offset == p->size)
453 close_block (pp->isamb, pp->block[pp->level]);
454 pp->block[pp->level] = 0;
456 p = pp->block[pp->level];
457 assert (p->bytes[0] == 0); /* must be int */
459 src = p->bytes + p->offset;
461 decode_ptr (&src, &item_len);
463 decode_ptr (&src, &pos);
465 p->offset = src - (char*) p->bytes;
471 pp->block[pp->level] = p = open_block (pp->isamb, pos);
473 if (p->bytes[0]) /* leaf */
477 src = p->bytes + p->offset;
478 decode_ptr (&src, &pos);
479 p->offset = src - (char*) p->bytes;
483 assert (p->offset < p->size);
484 assert (p->bytes[0]);
485 src = p->bytes + p->offset;
486 (*pp->isamb->method->code_item)(ISAMC_DECODE, p->decodeClientData,
488 p->offset = src - (char*) p->bytes;
492 int isamb_pp_num (ISAMB_PP pp)