2 * Copyright (c) 1995-1998, Index Data.
3 * See the file LICENSE for details.
6 * Isamh - append-only isam
9 * (get invstat to work)
11 * implement direct address bit
27 static void flush_block (ISAMH is, int cat);
28 static void release_fc (ISAMH is, int cat);
29 static void init_fc (ISAMH is, int cat);
31 #define ISAMH_FREELIST_CHUNK 1
35 ISAMH_M isamh_getmethod (void)
37 static struct ISAMH_filecat_s def_cat[] = {
39 /* blocksz, max keys before switching size */
50 /* assume about 2 bytes per pointer, when compressed. The head uses */
51 /* 16 bytes, and other blocks use 8 for header info... If you want 3 */
52 /* blocks of 32 bytes, say max 16+24+24 = 64 keys */
55 ISAMH_M m = (ISAMH_M) xmalloc (sizeof(*m));
63 m->compare_item = NULL;
67 m->max_blocks_mem = 10;
74 ISAMH isamh_open (BFiles bfs, const char *name, int writeflag, ISAMH_M method)
77 ISAMH_filecat filecat;
81 is = (ISAMH) xmalloc (sizeof(*is));
83 is->method = (ISAMH_M) xmalloc (sizeof(*is->method));
84 memcpy (is->method, method, sizeof(*method));
85 filecat = is->method->filecat;
88 /* determine number of block categories */
89 if (is->method->debug)
90 logf (LOG_LOG, "isc: bsize maxkeys");
93 if (is->method->debug)
94 logf (LOG_LOG, "isc:%6d %6d",
95 filecat[i].bsize, filecat[i].mblocks);
96 if (max_buf_size < filecat[i].bsize)
97 max_buf_size = filecat[i].bsize;
98 } while (filecat[i++].mblocks);
102 /* max_buf_size is the larget buffer to be used during merge */
103 max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
104 if (max_buf_size < (1+is->method->max_blocks_mem) * filecat[i].bsize)
105 max_buf_size = (1+is->method->max_blocks_mem) * filecat[i].bsize;
108 if (is->method->debug)
109 logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
111 assert (is->no_files > 0);
112 is->files = (ISAMH_file) xmalloc (sizeof(*is->files)*is->no_files);
116 is->merge_buf = (char *) xmalloc (max_buf_size+256);
117 memset (is->merge_buf, 0, max_buf_size+256);
119 is->startblock = (char *) xmalloc (max_buf_size+256);
120 memset (is->startblock, 0, max_buf_size+256);
121 is->lastblock = (char *) xmalloc (max_buf_size+256);
122 memset (is->lastblock, 0, max_buf_size+256);
123 /* The spare 256 bytes should not be needed! */
127 is->startblock = is->lastblock = NULL;
129 for (i = 0; i<is->no_files; i++)
133 sprintf (fname, "%s%c", name, i+'A');
134 is->files[i].bf = bf_open (bfs, fname, is->method->filecat[i].bsize,
136 is->files[i].head_is_dirty = 0;
137 if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
140 is->files[i].head.lastblock = 1;
141 is->files[i].head.freelist = 0;
143 is->files[i].alloc_entries_num = 0;
144 is->files[i].alloc_entries_max =
145 is->method->filecat[i].bsize / sizeof(int) - 1;
146 is->files[i].alloc_buf = (char *)
147 xmalloc (is->method->filecat[i].bsize);
148 is->files[i].no_writes = 0;
149 is->files[i].no_reads = 0;
150 is->files[i].no_skip_writes = 0;
151 is->files[i].no_allocated = 0;
152 is->files[i].no_released = 0;
153 is->files[i].no_remap = 0;
154 is->files[i].no_forward = 0;
155 is->files[i].no_backward = 0;
156 is->files[i].sum_forward = 0;
157 is->files[i].sum_backward = 0;
158 is->files[i].no_next = 0;
159 is->files[i].no_prev = 0;
166 int isamh_block_used (ISAMH is, int type)
168 if (type < 0 || type >= is->no_files)
170 return is->files[type].head.lastblock-1;
173 int isamh_block_size (ISAMH is, int type)
175 ISAMH_filecat filecat = is->method->filecat;
176 if (type < 0 || type >= is->no_files)
178 return filecat[type].bsize;
181 int isamh_close (ISAMH is)
185 if (is->method->debug)
187 logf (LOG_LOG, "isc: next forw mid-f prev backw mid-b");
188 for (i = 0; i<is->no_files; i++)
189 logf (LOG_LOG, "isc:%8d%8d%8.1f%8d%8d%8.1f",
190 is->files[i].no_next,
191 is->files[i].no_forward,
192 is->files[i].no_forward ?
193 (double) is->files[i].sum_forward/is->files[i].no_forward
195 is->files[i].no_prev,
196 is->files[i].no_backward,
197 is->files[i].no_backward ?
198 (double) is->files[i].sum_backward/is->files[i].no_backward
201 if (is->method->debug)
202 logf (LOG_LOG, "isc: writes reads skipped alloc released remap");
203 for (i = 0; i<is->no_files; i++)
206 assert (is->files[i].bf);
207 if (is->files[i].head_is_dirty)
208 bf_write (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
210 if (is->method->debug)
211 logf (LOG_LOG, "isc:%8d%8d%8d%8d%8d%8d",
212 is->files[i].no_writes,
213 is->files[i].no_reads,
214 is->files[i].no_skip_writes,
215 is->files[i].no_allocated,
216 is->files[i].no_released,
217 is->files[i].no_remap);
218 xfree (is->files[i].fc_list);
220 bf_close (is->files[i].bf);
223 xfree (is->startblock);
224 xfree (is->lastblock);
230 int isamh_read_block (ISAMH is, int cat, int pos, char *dst)
232 ++(is->files[cat].no_reads);
233 return bf_read (is->files[cat].bf, pos, 0, 0, dst);
236 int isamh_write_block (ISAMH is, int cat, int pos, char *src)
238 ++(is->files[cat].no_writes);
239 if (is->method->debug > 2)
240 logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
241 return bf_write (is->files[cat].bf, pos, 0, 0, src);
244 int isamh_write_dblock (ISAMH is, int cat, int pos, char *src,
245 int nextpos, int offset)
247 ISAMH_BLOCK_SIZE size = offset + ISAMH_BLOCK_OFFSET_N;
248 if (is->method->debug > 2)
249 logf (LOG_LOG, "isc: write_dblock. size=%d nextpos=%d",
250 (int) size, nextpos);
251 src -= ISAMH_BLOCK_OFFSET_N;
252 memcpy (src, &nextpos, sizeof(int));
253 memcpy (src + sizeof(int), &size, sizeof(size));
254 return isamh_write_block (is, cat, pos, src);
257 #if ISAMH_FREELIST_CHUNK
258 static void flush_block (ISAMH is, int cat)
260 char *abuf = is->files[cat].alloc_buf;
261 int block = is->files[cat].head.freelist;
262 if (block && is->files[cat].alloc_entries_num)
264 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
265 bf_write (is->files[cat].bf, block, 0, 0, abuf);
266 is->files[cat].alloc_entries_num = 0;
271 static int alloc_block (ISAMH is, int cat)
273 int block = is->files[cat].head.freelist;
274 char *abuf = is->files[cat].alloc_buf;
276 (is->files[cat].no_allocated)++;
280 block = (is->files[cat].head.lastblock)++; /* no free list */
281 is->files[cat].head_is_dirty = 1;
285 if (!is->files[cat].alloc_entries_num) /* read first time */
287 bf_read (is->files[cat].bf, block, 0, 0, abuf);
288 memcpy (&is->files[cat].alloc_entries_num, abuf,
289 sizeof(is->files[cat].alloc_entries_num));
290 assert (is->files[cat].alloc_entries_num > 0);
292 /* have some free blocks now */
293 assert (is->files[cat].alloc_entries_num > 0);
294 is->files[cat].alloc_entries_num--;
295 if (!is->files[cat].alloc_entries_num) /* last one in block? */
297 memcpy (&is->files[cat].head.freelist, abuf + sizeof(int),
299 is->files[cat].head_is_dirty = 1;
301 if (is->files[cat].head.freelist)
303 bf_read (is->files[cat].bf, is->files[cat].head.freelist,
305 memcpy (&is->files[cat].alloc_entries_num, abuf,
306 sizeof(is->files[cat].alloc_entries_num));
307 assert (is->files[cat].alloc_entries_num);
311 memcpy (&block, abuf + sizeof(int) + sizeof(int) *
312 is->files[cat].alloc_entries_num, sizeof(int));
317 static void release_block (ISAMH is, int cat, int pos)
319 char *abuf = is->files[cat].alloc_buf;
320 int block = is->files[cat].head.freelist;
322 (is->files[cat].no_released)++;
324 if (block && !is->files[cat].alloc_entries_num) /* must read block */
326 bf_read (is->files[cat].bf, block, 0, 0, abuf);
327 memcpy (&is->files[cat].alloc_entries_num, abuf,
328 sizeof(is->files[cat].alloc_entries_num));
329 assert (is->files[cat].alloc_entries_num > 0);
331 assert (is->files[cat].alloc_entries_num <= is->files[cat].alloc_entries_max);
332 if (is->files[cat].alloc_entries_num == is->files[cat].alloc_entries_max)
335 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
336 bf_write (is->files[cat].bf, block, 0, 0, abuf);
337 is->files[cat].alloc_entries_num = 0;
339 if (!is->files[cat].alloc_entries_num) /* make new buffer? */
341 memcpy (abuf + sizeof(int), &block, sizeof(int));
342 is->files[cat].head.freelist = pos;
343 is->files[cat].head_is_dirty = 1;
347 memcpy (abuf + sizeof(int) +
348 is->files[cat].alloc_entries_num*sizeof(int),
351 is->files[cat].alloc_entries_num++;
354 static void flush_block (ISAMH is, int cat)
356 char *abuf = is->files[cat].alloc_buf;
360 static int alloc_block (ISAMH is, int cat)
363 char buf[sizeof(int)];
365 is->files[cat].head_is_dirty = 1;
366 (is->files[cat].no_allocated)++;
367 if ((block = is->files[cat].head.freelist))
369 bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
370 memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
373 block = (is->files[cat].head.lastblock)++;
377 static void release_block (ISAMH is, int cat, int pos)
379 char buf[sizeof(int)];
381 (is->files[cat].no_released)++;
382 is->files[cat].head_is_dirty = 1;
383 memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
384 is->files[cat].head.freelist = pos;
385 bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
389 int isamh_alloc_block (ISAMH is, int cat)
393 if (is->files[cat].fc_list)
396 for (j = 0; j < is->files[cat].fc_max; j++)
397 if ((nb = is->files[cat].fc_list[j]) && (!block || nb < block))
399 is->files[cat].fc_list[j] = 0;
405 block = alloc_block (is, cat);
406 if (is->method->debug > 3)
407 logf (LOG_LOG, "isc: alloc_block in cat %d: %d", cat, block);
411 void isamh_release_block (ISAMH is, int cat, int pos)
413 if (is->method->debug > 3)
414 logf (LOG_LOG, "isc: release_block in cat %d: %d", cat, pos);
415 if (is->files[cat].fc_list)
418 for (j = 0; j<is->files[cat].fc_max; j++)
419 if (!is->files[cat].fc_list[j])
421 is->files[cat].fc_list[j] = pos;
425 release_block (is, cat, pos);
428 static void init_fc (ISAMH is, int cat)
432 is->files[cat].fc_max = j;
433 is->files[cat].fc_list = (int *)
434 xmalloc (sizeof(*is->files[0].fc_list) * j);
436 is->files[cat].fc_list[j] = 0;
439 static void release_fc (ISAMH is, int cat)
441 int b, j = is->files[cat].fc_max;
444 if ((b = is->files[cat].fc_list[j]))
446 release_block (is, cat, b);
447 is->files[cat].fc_list[j] = 0;
451 void isamh_pp_close (ISAMH_PP pp)
455 (*is->method->code_stop)(ISAMH_DECODE, pp->decodeClientData);
460 ISAMH_PP isamh_pp_open (ISAMH is, ISAMH_P ipos)
462 ISAMH_PP pp = (ISAMH_PP) xmalloc (sizeof(*pp));
465 pp->cat = isamh_type(ipos);
466 pp->pos = isamh_block(ipos);
468 src = pp->buf = (char *) xmalloc (is->method->filecat[pp->cat].bsize);
474 pp->decodeClientData = (*is->method->code_start)(ISAMH_DECODE);
482 isamh_read_block (is, pp->cat, pp->pos, src);
483 memcpy (&pp->next, src, sizeof(pp->next));
484 src += sizeof(pp->next);
485 memcpy (&pp->size, src, sizeof(pp->size));
486 src += sizeof(pp->size);
487 memcpy (&pp->numKeys, src, sizeof(pp->numKeys));
488 src += sizeof(pp->numKeys);
489 memcpy (&pp->lastblock, src, sizeof(pp->lastblock));
490 src += sizeof(pp->lastblock);
491 assert (pp->next != pp->pos);
492 pp->offset = src - pp->buf;
493 assert (pp->offset == ISAMH_BLOCK_OFFSET_1);
494 if (is->method->debug > 2)
495 logf (LOG_LOG, "isamh_pp_open sz=%d c=%d p=%d n=%d",
496 pp->size, pp->cat, pp->pos, isamh_block(pp->next));
503 void isamh_buildfirstblock(ISAMH_PP pp){
506 assert(pp->next != pp->pos);
507 memcpy(dst, &pp->next, sizeof(pp->next) );
508 dst += sizeof(pp->next);
509 memcpy(dst, &pp->size,sizeof(pp->size));
510 dst += sizeof(pp->size);
511 memcpy(dst, &pp->numKeys, sizeof(pp->numKeys));
512 dst += sizeof(pp->numKeys);
513 memcpy(dst, &pp->lastblock, sizeof(pp->lastblock));
514 dst += sizeof(pp->lastblock);
515 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_1);
516 if (pp->is->method->debug > 2)
517 logf (LOG_LOG, "isamh: first: sz=%d p=%d/%d>%d/%d>%d/%d nk=%d",
520 isamh_block(pp->next), isamh_type(pp->next),
521 isamh_block(pp->lastblock), isamh_type(pp->lastblock),
525 void isamh_buildlaterblock(ISAMH_PP pp){
528 assert(pp->next != isamh_addr(pp->pos,pp->cat));
529 memcpy(dst, &pp->next, sizeof(pp->next) );
530 dst += sizeof(pp->next);
531 memcpy(dst, &pp->size,sizeof(pp->size));
532 dst += sizeof(pp->size);
533 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_N);
534 if (pp->is->method->debug > 2)
535 logf (LOG_LOG, "isamh: l8r: sz=%d p=%d/%d>%d/%d",
538 isamh_block(pp->next), isamh_type(pp->next) );
543 /* returns non-zero if item could be read; 0 otherwise */
544 int isamh_pp_read (ISAMH_PP pp, void *buf)
546 return isamh_read_item (pp, (char **) &buf);
549 /* read one item from file - decode and store it in *dst.
552 1 if item could be read ok and NO boundary
553 2 if item could be read ok and boundary */
554 int isamh_read_item (ISAMH_PP pp, char **dst)
557 char *src = pp->buf + pp->offset;
560 if (pp->offset >= pp->size)
565 return 0; /* end of file */
567 if (pp->next > pp->pos)
569 if (pp->next == pp->pos + 1)
570 is->files[pp->cat].no_next++;
573 is->files[pp->cat].no_forward++;
574 is->files[pp->cat].sum_forward += pp->next - pp->pos;
579 if (pp->next + 1 == pp->pos)
580 is->files[pp->cat].no_prev++;
583 is->files[pp->cat].no_backward++;
584 is->files[pp->cat].sum_backward += pp->pos - pp->next;
587 /* out new block position */
588 newcat = isamh_type(pp->next);
589 if (pp->cat != newcat ) {
590 pp->buf = xrealloc(pp->buf, is->method->filecat[newcat].bsize);
592 pp->pos = isamh_block(pp->next);
593 pp->cat = isamh_type(pp->next);
596 /* read block and save 'next' and 'size' entry */
597 isamh_read_block (is, pp->cat, pp->pos, src);
598 memcpy (&pp->next, src, sizeof(pp->next));
599 src += sizeof(pp->next);
600 memcpy (&pp->size, src, sizeof(pp->size));
601 src += sizeof(pp->size);
602 /* assume block is non-empty */
603 assert (src - pp->buf == ISAMH_BLOCK_OFFSET_N);
604 assert (pp->next != isamh_addr(pp->pos,pp->cat));
606 isamh_release_block (is, pp->cat, pp->pos);
607 (*is->method->code_reset)(pp->decodeClientData);
608 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
609 pp->offset = src - pp->buf;
610 if (is->method->debug > 2)
611 logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
612 pp->size, pp->cat, pp->pos, pp->next);
615 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
616 pp->offset = src - pp->buf;
620 int isamh_pp_num (ISAMH_PP pp)
629 * Revision 1.5 1999-07-08 14:23:27 heikki
630 * Fixed a bug in isamh_pp_read and cleaned up a bit
632 * Revision 1.4 1999/07/07 09:36:04 heikki
633 * Fixed an assertion in isamh
635 * Revision 1.2 1999/07/06 09:37:05 heikki
636 * Working on isamh - not ready yet.
638 * Revision 1.1 1999/06/30 15:04:54 heikki
639 * Copied from isamc.c, slowly starting to simplify...