2 * Copyright (c) 1995-1998, Index Data.
3 * See the file LICENSE for details.
6 * Isamh - append-only isam
21 static void flush_block (ISAMH is, int cat);
22 static void release_fc (ISAMH is, int cat);
23 static void init_fc (ISAMH is, int cat);
25 #define ISAMH_FREELIST_CHUNK 1
29 ISAMH_M isamh_getmethod (void)
31 static struct ISAMH_filecat_s def_cat[] = {
33 /* blocksz, max keys before switching size */
44 /* assume about 2 bytes per pointer, when compressed. The head uses */
45 /* 16 bytes, and other blocks use 8 for header info... If you want 3 */
46 /* blocks of 32 bytes, say max 16+24+24 = 64 keys */
49 ISAMH_M m = (ISAMH_M) xmalloc (sizeof(*m));
57 m->compare_item = NULL;
61 m->max_blocks_mem = 10;
67 ISAMH isamh_open (BFiles bfs, const char *name, int writeflag, ISAMH_M method)
70 ISAMH_filecat filecat;
74 is = (ISAMH) xmalloc (sizeof(*is));
76 is->method = (ISAMH_M) xmalloc (sizeof(*is->method));
77 memcpy (is->method, method, sizeof(*method));
78 filecat = is->method->filecat;
81 /* determine number of block categories */
82 if (is->method->debug)
83 logf (LOG_LOG, "isc: bsize ifill mfill mblocks");
86 if (is->method->debug)
87 logf (LOG_LOG, "isc:%6d %6d",
88 filecat[i].bsize, filecat[i].mblocks);
89 if (max_buf_size < filecat[i].bsize)
90 max_buf_size = filecat[i].bsize;
91 } while (filecat[i++].mblocks);
95 /* max_buf_size is the larget buffer to be used during merge */
96 max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
97 if (max_buf_size < (1+is->method->max_blocks_mem) * filecat[i].bsize)
98 max_buf_size = (1+is->method->max_blocks_mem) * filecat[i].bsize;
101 if (is->method->debug)
102 logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
104 assert (is->no_files > 0);
105 is->files = (ISAMH_file) xmalloc (sizeof(*is->files)*is->no_files);
109 is->merge_buf = (char *) xmalloc (max_buf_size+256);
110 memset (is->merge_buf, 0, max_buf_size+256);
112 is->startblock = (char *) xmalloc (max_buf_size+256);
113 memset (is->startblock, 0, max_buf_size+256);
114 is->lastblock = (char *) xmalloc (max_buf_size+256);
115 memset (is->lastblock, 0, max_buf_size+256);
116 /* The spare 256 bytes should not be needed! */
120 is->startblock = is->lastblock = NULL;
122 for (i = 0; i<is->no_files; i++)
126 sprintf (fname, "%s%c", name, i+'A');
127 is->files[i].bf = bf_open (bfs, fname, is->method->filecat[i].bsize,
129 is->files[i].head_is_dirty = 0;
130 if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
133 is->files[i].head.lastblock = 1;
134 is->files[i].head.freelist = 0;
136 is->files[i].alloc_entries_num = 0;
137 is->files[i].alloc_entries_max =
138 is->method->filecat[i].bsize / sizeof(int) - 1;
139 is->files[i].alloc_buf = (char *)
140 xmalloc (is->method->filecat[i].bsize);
141 is->files[i].no_writes = 0;
142 is->files[i].no_reads = 0;
143 is->files[i].no_skip_writes = 0;
144 is->files[i].no_allocated = 0;
145 is->files[i].no_released = 0;
146 is->files[i].no_remap = 0;
147 is->files[i].no_forward = 0;
148 is->files[i].no_backward = 0;
149 is->files[i].sum_forward = 0;
150 is->files[i].sum_backward = 0;
151 is->files[i].no_next = 0;
152 is->files[i].no_prev = 0;
159 int isamh_block_used (ISAMH is, int type)
161 if (type < 0 || type >= is->no_files)
163 return is->files[type].head.lastblock-1;
166 int isamh_block_size (ISAMH is, int type)
168 ISAMH_filecat filecat = is->method->filecat;
169 if (type < 0 || type >= is->no_files)
171 return filecat[type].bsize;
174 int isamh_close (ISAMH is)
178 if (is->method->debug)
180 logf (LOG_LOG, "isc: next forw mid-f prev backw mid-b");
181 for (i = 0; i<is->no_files; i++)
182 logf (LOG_LOG, "isc:%8d%8d%8.1f%8d%8d%8.1f",
183 is->files[i].no_next,
184 is->files[i].no_forward,
185 is->files[i].no_forward ?
186 (double) is->files[i].sum_forward/is->files[i].no_forward
188 is->files[i].no_prev,
189 is->files[i].no_backward,
190 is->files[i].no_backward ?
191 (double) is->files[i].sum_backward/is->files[i].no_backward
194 if (is->method->debug)
195 logf (LOG_LOG, "isc: writes reads skipped alloc released remap");
196 for (i = 0; i<is->no_files; i++)
199 assert (is->files[i].bf);
200 if (is->files[i].head_is_dirty)
201 bf_write (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
203 if (is->method->debug)
204 logf (LOG_LOG, "isc:%8d%8d%8d%8d%8d%8d",
205 is->files[i].no_writes,
206 is->files[i].no_reads,
207 is->files[i].no_skip_writes,
208 is->files[i].no_allocated,
209 is->files[i].no_released,
210 is->files[i].no_remap);
211 xfree (is->files[i].fc_list);
213 bf_close (is->files[i].bf);
216 xfree (is->startblock);
217 xfree (is->lastblock);
223 int isamh_read_block (ISAMH is, int cat, int pos, char *dst)
225 ++(is->files[cat].no_reads);
226 return bf_read (is->files[cat].bf, pos, 0, 0, dst);
229 int isamh_write_block (ISAMH is, int cat, int pos, char *src)
231 ++(is->files[cat].no_writes);
232 if (is->method->debug > 2)
233 logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
234 return bf_write (is->files[cat].bf, pos, 0, 0, src);
237 int isamh_write_dblock (ISAMH is, int cat, int pos, char *src,
238 int nextpos, int offset)
240 ISAMH_BLOCK_SIZE size = offset + ISAMH_BLOCK_OFFSET_N;
241 if (is->method->debug > 2)
242 logf (LOG_LOG, "isc: write_dblock. size=%d nextpos=%d",
243 (int) size, nextpos);
244 src -= ISAMH_BLOCK_OFFSET_N;
245 memcpy (src, &nextpos, sizeof(int));
246 memcpy (src + sizeof(int), &size, sizeof(size));
247 return isamh_write_block (is, cat, pos, src);
250 #if ISAMH_FREELIST_CHUNK
251 static void flush_block (ISAMH is, int cat)
253 char *abuf = is->files[cat].alloc_buf;
254 int block = is->files[cat].head.freelist;
255 if (block && is->files[cat].alloc_entries_num)
257 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
258 bf_write (is->files[cat].bf, block, 0, 0, abuf);
259 is->files[cat].alloc_entries_num = 0;
264 static int alloc_block (ISAMH is, int cat)
266 int block = is->files[cat].head.freelist;
267 char *abuf = is->files[cat].alloc_buf;
269 (is->files[cat].no_allocated)++;
273 block = (is->files[cat].head.lastblock)++; /* no free list */
274 is->files[cat].head_is_dirty = 1;
278 if (!is->files[cat].alloc_entries_num) /* read first time */
280 bf_read (is->files[cat].bf, block, 0, 0, abuf);
281 memcpy (&is->files[cat].alloc_entries_num, abuf,
282 sizeof(is->files[cat].alloc_entries_num));
283 assert (is->files[cat].alloc_entries_num > 0);
285 /* have some free blocks now */
286 assert (is->files[cat].alloc_entries_num > 0);
287 is->files[cat].alloc_entries_num--;
288 if (!is->files[cat].alloc_entries_num) /* last one in block? */
290 memcpy (&is->files[cat].head.freelist, abuf + sizeof(int),
292 is->files[cat].head_is_dirty = 1;
294 if (is->files[cat].head.freelist)
296 bf_read (is->files[cat].bf, is->files[cat].head.freelist,
298 memcpy (&is->files[cat].alloc_entries_num, abuf,
299 sizeof(is->files[cat].alloc_entries_num));
300 assert (is->files[cat].alloc_entries_num);
304 memcpy (&block, abuf + sizeof(int) + sizeof(int) *
305 is->files[cat].alloc_entries_num, sizeof(int));
310 static void release_block (ISAMH is, int cat, int pos)
312 char *abuf = is->files[cat].alloc_buf;
313 int block = is->files[cat].head.freelist;
315 (is->files[cat].no_released)++;
317 if (block && !is->files[cat].alloc_entries_num) /* must read block */
319 bf_read (is->files[cat].bf, block, 0, 0, abuf);
320 memcpy (&is->files[cat].alloc_entries_num, abuf,
321 sizeof(is->files[cat].alloc_entries_num));
322 assert (is->files[cat].alloc_entries_num > 0);
324 assert (is->files[cat].alloc_entries_num <= is->files[cat].alloc_entries_max);
325 if (is->files[cat].alloc_entries_num == is->files[cat].alloc_entries_max)
328 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
329 bf_write (is->files[cat].bf, block, 0, 0, abuf);
330 is->files[cat].alloc_entries_num = 0;
332 if (!is->files[cat].alloc_entries_num) /* make new buffer? */
334 memcpy (abuf + sizeof(int), &block, sizeof(int));
335 is->files[cat].head.freelist = pos;
336 is->files[cat].head_is_dirty = 1;
340 memcpy (abuf + sizeof(int) +
341 is->files[cat].alloc_entries_num*sizeof(int),
344 is->files[cat].alloc_entries_num++;
347 static void flush_block (ISAMH is, int cat)
349 char *abuf = is->files[cat].alloc_buf;
353 static int alloc_block (ISAMH is, int cat)
356 char buf[sizeof(int)];
358 is->files[cat].head_is_dirty = 1;
359 (is->files[cat].no_allocated)++;
360 if ((block = is->files[cat].head.freelist))
362 bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
363 memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
366 block = (is->files[cat].head.lastblock)++;
370 static void release_block (ISAMH is, int cat, int pos)
372 char buf[sizeof(int)];
374 (is->files[cat].no_released)++;
375 is->files[cat].head_is_dirty = 1;
376 memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
377 is->files[cat].head.freelist = pos;
378 bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
382 int isamh_alloc_block (ISAMH is, int cat)
386 if (is->files[cat].fc_list)
389 for (j = 0; j < is->files[cat].fc_max; j++)
390 if ((nb = is->files[cat].fc_list[j]) && (!block || nb < block))
392 is->files[cat].fc_list[j] = 0;
398 block = alloc_block (is, cat);
399 if (is->method->debug > 3)
400 logf (LOG_LOG, "isc: alloc_block in cat %d: %d", cat, block);
404 void isamh_release_block (ISAMH is, int cat, int pos)
406 if (is->method->debug > 3)
407 logf (LOG_LOG, "isc: release_block in cat %d: %d", cat, pos);
408 if (is->files[cat].fc_list)
411 for (j = 0; j<is->files[cat].fc_max; j++)
412 if (!is->files[cat].fc_list[j])
414 is->files[cat].fc_list[j] = pos;
418 release_block (is, cat, pos);
421 static void init_fc (ISAMH is, int cat)
425 is->files[cat].fc_max = j;
426 is->files[cat].fc_list = (int *)
427 xmalloc (sizeof(*is->files[0].fc_list) * j);
429 is->files[cat].fc_list[j] = 0;
432 static void release_fc (ISAMH is, int cat)
434 int b, j = is->files[cat].fc_max;
437 if ((b = is->files[cat].fc_list[j]))
439 release_block (is, cat, b);
440 is->files[cat].fc_list[j] = 0;
444 void isamh_pp_close (ISAMH_PP pp)
448 (*is->method->code_stop)(ISAMH_DECODE, pp->decodeClientData);
453 ISAMH_PP isamh_pp_open (ISAMH is, ISAMH_P ipos)
455 ISAMH_PP pp = (ISAMH_PP) xmalloc (sizeof(*pp));
458 pp->cat = isamh_type(ipos);
459 pp->pos = isamh_block(ipos);
461 src = pp->buf = (char *) xmalloc (is->method->filecat[pp->cat].bsize);
467 pp->decodeClientData = (*is->method->code_start)(ISAMH_DECODE);
475 isamh_read_block (is, pp->cat, pp->pos, src);
476 memcpy (&pp->next, src, sizeof(pp->next));
477 src += sizeof(pp->next);
478 memcpy (&pp->size, src, sizeof(pp->size));
479 src += sizeof(pp->size);
480 memcpy (&pp->numKeys, src, sizeof(pp->numKeys));
481 src += sizeof(pp->numKeys);
482 memcpy (&pp->lastblock, src, sizeof(pp->lastblock));
483 src += sizeof(pp->lastblock);
484 assert (pp->next != pp->pos);
485 pp->offset = src - pp->buf;
486 assert (pp->offset == ISAMH_BLOCK_OFFSET_1);
487 if (is->method->debug > 2)
488 logf (LOG_LOG, "isamh_pp_open sz=%d c=%d p=%d n=%d",
489 pp->size, pp->cat, pp->pos, isamh_block(pp->next));
496 void isamh_buildfirstblock(ISAMH_PP pp){
499 assert(pp->next != pp->pos);
500 memcpy(dst, &pp->next, sizeof(pp->next) );
501 dst += sizeof(pp->next);
502 memcpy(dst, &pp->size,sizeof(pp->size));
503 dst += sizeof(pp->size);
504 memcpy(dst, &pp->numKeys, sizeof(pp->numKeys));
505 dst += sizeof(pp->numKeys);
506 memcpy(dst, &pp->lastblock, sizeof(pp->lastblock));
507 dst += sizeof(pp->lastblock);
508 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_1);
509 if (pp->is->method->debug > 2)
510 logf (LOG_LOG, "isamh: first: sz=%d p=%d/%d>%d/%d>%d/%d nk=%d",
513 isamh_block(pp->next), isamh_type(pp->next),
514 isamh_block(pp->lastblock), isamh_type(pp->lastblock),
518 void isamh_buildlaterblock(ISAMH_PP pp){
521 assert(pp->next != isamh_addr(pp->pos,pp->cat));
522 memcpy(dst, &pp->next, sizeof(pp->next) );
523 dst += sizeof(pp->next);
524 memcpy(dst, &pp->size,sizeof(pp->size));
525 dst += sizeof(pp->size);
526 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_N);
527 if (pp->is->method->debug > 2)
528 logf (LOG_LOG, "isamh: l8r: sz=%d p=%d/%d>%d/%d",
531 isamh_block(pp->next), isamh_type(pp->next) );
536 /* returns non-zero if item could be read; 0 otherwise */
537 int isamh_pp_read (ISAMH_PP pp, void *buf)
539 return isamh_read_item (pp, (char **) &buf);
542 /* read one item from file - decode and store it in *dst.
545 1 if item could be read ok and NO boundary
546 2 if item could be read ok and boundary */
547 int isamh_read_item (ISAMH_PP pp, char **dst)
550 char *src = pp->buf + pp->offset;
552 if (pp->offset >= pp->size)
557 return 0; /* end of file */
559 if (pp->next > pp->pos)
561 if (pp->next == pp->pos + 1)
562 is->files[pp->cat].no_next++;
565 is->files[pp->cat].no_forward++;
566 is->files[pp->cat].sum_forward += pp->next - pp->pos;
571 if (pp->next + 1 == pp->pos)
572 is->files[pp->cat].no_prev++;
575 is->files[pp->cat].no_backward++;
576 is->files[pp->cat].sum_backward += pp->pos - pp->next;
579 /* out new block position */
582 /* read block and save 'next' and 'size' entry */
583 isamh_read_block (is, pp->cat, pp->pos, src);
584 memcpy (&pp->next, src, sizeof(pp->next));
585 src += sizeof(pp->next);
586 memcpy (&pp->size, src, sizeof(pp->size));
587 src += sizeof(pp->size);
588 /* assume block is non-empty */
589 assert (src - pp->buf == ISAMH_BLOCK_OFFSET_N);
590 assert (pp->next != pp->pos);
592 isamh_release_block (is, pp->cat, pp->pos);
593 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
594 pp->offset = src - pp->buf;
595 if (is->method->debug > 2)
596 logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
597 pp->size, pp->cat, pp->pos, pp->next);
600 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
601 pp->offset = src - pp->buf;
605 int isamh_pp_num (ISAMH_PP pp)
612 * Revision 1.4 1999-07-07 09:36:04 heikki
613 * Fixed an assertion in isamh
615 * Revision 1.2 1999/07/06 09:37:05 heikki
616 * Working on isamh - not ready yet.
618 * Revision 1.1 1999/06/30 15:04:54 heikki
619 * Copied from isamc.c, slowly starting to simplify...