2 * Copyright (c) 1995-1998, Index Data.
3 * See the file LICENSE for details.
6 * Isamh - append-only isam
25 static void flush_block (ISAMH is, int cat);
26 static void release_fc (ISAMH is, int cat);
27 static void init_fc (ISAMH is, int cat);
29 #define ISAMH_FREELIST_CHUNK 1
33 ISAMH_M isamh_getmethod (void)
35 static struct ISAMH_filecat_s def_cat[] = {
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, "isc: read_block size=%d %d %d next=%d",
489 pp->size, pp->cat, pp->pos, pp->next);
494 void isamh_buildfirstblock(ISAMH_PP pp){
497 assert(pp->next != pp->pos);
498 memcpy(dst, &pp->next, sizeof(pp->next) );
499 dst += sizeof(pp->next);
500 memcpy(dst, &pp->size,sizeof(pp->size));
501 dst += sizeof(pp->size);
502 memcpy(dst, &pp->numKeys, sizeof(pp->numKeys));
503 dst += sizeof(pp->numKeys);
504 memcpy(dst, &pp->lastblock, sizeof(pp->lastblock));
505 dst += sizeof(pp->lastblock);
506 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_1);
507 if (pp->is->method->debug > 2)
508 logf (LOG_LOG, "isamh: firstblock: sz=%d c=%d p=%d>%d>%d nk=%d",
509 pp->size, pp->cat, pp->pos, pp->next, pp->lastblock,pp->numKeys);
512 void isamh_buildlaterblock(ISAMH_PP pp){
515 assert(pp->next != pp->pos);
516 memcpy(dst, &pp->next, sizeof(pp->next) );
517 dst += sizeof(pp->next);
518 memcpy(dst, &pp->size,sizeof(pp->size));
519 dst += sizeof(pp->size);
520 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_N);
521 if (pp->is->method->debug > 2)
522 logf (LOG_LOG, "isamh: laterblock: sz=%d c=%d p=%d>%d",
523 pp->size, pp->cat, pp->pos, pp->next);
528 /* returns non-zero if item could be read; 0 otherwise */
529 int isamh_pp_read (ISAMH_PP pp, void *buf)
531 return isamh_read_item (pp, (char **) &buf);
534 /* read one item from file - decode and store it in *dst.
537 1 if item could be read ok and NO boundary
538 2 if item could be read ok and boundary */
539 int isamh_read_item (ISAMH_PP pp, char **dst)
542 char *src = pp->buf + pp->offset;
544 if (pp->offset >= pp->size)
549 return 0; /* end of file */
551 if (pp->next > pp->pos)
553 if (pp->next == pp->pos + 1)
554 is->files[pp->cat].no_next++;
557 is->files[pp->cat].no_forward++;
558 is->files[pp->cat].sum_forward += pp->next - pp->pos;
563 if (pp->next + 1 == pp->pos)
564 is->files[pp->cat].no_prev++;
567 is->files[pp->cat].no_backward++;
568 is->files[pp->cat].sum_backward += pp->pos - pp->next;
571 /* out new block position */
574 /* read block and save 'next' and 'size' entry */
575 isamh_read_block (is, pp->cat, pp->pos, src);
576 memcpy (&pp->next, src, sizeof(pp->next));
577 src += sizeof(pp->next);
578 memcpy (&pp->size, src, sizeof(pp->size));
579 src += sizeof(pp->size);
580 /* assume block is non-empty */
581 assert (src - pp->buf == ISAMH_BLOCK_OFFSET_N);
582 assert (pp->next != pp->pos);
584 isamh_release_block (is, pp->cat, pp->pos);
585 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
586 pp->offset = src - pp->buf;
587 if (is->method->debug > 2)
588 logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
589 pp->size, pp->cat, pp->pos, pp->next);
592 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
593 pp->offset = src - pp->buf;
597 int isamh_pp_num (ISAMH_PP pp)
604 * Revision 1.2 1999-07-06 09:37:05 heikki
605 * Working on isamh - not ready yet.
607 * Revision 1.1 1999/06/30 15:04:54 heikki
608 * Copied from isamc.c, slowly starting to simplify...