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[] = {
48 ISAMH_M m = (ISAMH_M) xmalloc (sizeof(*m));
56 m->compare_item = NULL;
60 m->max_blocks_mem = 10;
66 ISAMH isamh_open (BFiles bfs, const char *name, int writeflag, ISAMH_M method)
69 ISAMH_filecat filecat;
73 is = (ISAMH) xmalloc (sizeof(*is));
75 is->method = (ISAMH_M) xmalloc (sizeof(*is->method));
76 memcpy (is->method, method, sizeof(*method));
77 filecat = is->method->filecat;
80 /* determine number of block categories */
81 if (is->method->debug)
82 logf (LOG_LOG, "isc: bsize ifill mfill mblocks");
85 if (is->method->debug)
86 logf (LOG_LOG, "isc:%6d %6d",
87 filecat[i].bsize, filecat[i].mblocks);
88 if (max_buf_size < filecat[i].mblocks * filecat[i].bsize)
89 max_buf_size = filecat[i].mblocks * filecat[i].bsize;
90 } while (filecat[i++].mblocks);
93 /* max_buf_size is the larget buffer to be used during merge */
94 max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
95 if (max_buf_size < (1+is->method->max_blocks_mem) * filecat[i].bsize)
96 max_buf_size = (1+is->method->max_blocks_mem) * filecat[i].bsize;
97 if (is->method->debug)
98 logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
100 assert (is->no_files > 0);
101 is->files = (ISAMH_file) xmalloc (sizeof(*is->files)*is->no_files);
104 is->merge_buf = (char *) xmalloc (max_buf_size+256);
105 memset (is->merge_buf, 0, max_buf_size+256);
108 is->merge_buf = NULL;
109 for (i = 0; i<is->no_files; i++)
113 sprintf (fname, "%s%c", name, i+'A');
114 is->files[i].bf = bf_open (bfs, fname, is->method->filecat[i].bsize,
116 is->files[i].head_is_dirty = 0;
117 if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
120 is->files[i].head.lastblock = 1;
121 is->files[i].head.freelist = 0;
123 is->files[i].alloc_entries_num = 0;
124 is->files[i].alloc_entries_max =
125 is->method->filecat[i].bsize / sizeof(int) - 1;
126 is->files[i].alloc_buf = (char *)
127 xmalloc (is->method->filecat[i].bsize);
128 is->files[i].no_writes = 0;
129 is->files[i].no_reads = 0;
130 is->files[i].no_skip_writes = 0;
131 is->files[i].no_allocated = 0;
132 is->files[i].no_released = 0;
133 is->files[i].no_remap = 0;
134 is->files[i].no_forward = 0;
135 is->files[i].no_backward = 0;
136 is->files[i].sum_forward = 0;
137 is->files[i].sum_backward = 0;
138 is->files[i].no_next = 0;
139 is->files[i].no_prev = 0;
146 int isamh_block_used (ISAMH is, int type)
148 if (type < 0 || type >= is->no_files)
150 return is->files[type].head.lastblock-1;
153 int isamh_block_size (ISAMH is, int type)
155 ISAMH_filecat filecat = is->method->filecat;
156 if (type < 0 || type >= is->no_files)
158 return filecat[type].bsize;
161 int isamh_close (ISAMH is)
165 if (is->method->debug)
167 logf (LOG_LOG, "isc: next forw mid-f prev backw mid-b");
168 for (i = 0; i<is->no_files; i++)
169 logf (LOG_LOG, "isc:%8d%8d%8.1f%8d%8d%8.1f",
170 is->files[i].no_next,
171 is->files[i].no_forward,
172 is->files[i].no_forward ?
173 (double) is->files[i].sum_forward/is->files[i].no_forward
175 is->files[i].no_prev,
176 is->files[i].no_backward,
177 is->files[i].no_backward ?
178 (double) is->files[i].sum_backward/is->files[i].no_backward
181 if (is->method->debug)
182 logf (LOG_LOG, "isc: writes reads skipped alloc released remap");
183 for (i = 0; i<is->no_files; i++)
186 assert (is->files[i].bf);
187 if (is->files[i].head_is_dirty)
188 bf_write (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
190 if (is->method->debug)
191 logf (LOG_LOG, "isc:%8d%8d%8d%8d%8d%8d",
192 is->files[i].no_writes,
193 is->files[i].no_reads,
194 is->files[i].no_skip_writes,
195 is->files[i].no_allocated,
196 is->files[i].no_released,
197 is->files[i].no_remap);
198 xfree (is->files[i].fc_list);
200 bf_close (is->files[i].bf);
203 xfree (is->merge_buf);
209 int isamh_read_block (ISAMH is, int cat, int pos, char *dst)
211 ++(is->files[cat].no_reads);
212 return bf_read (is->files[cat].bf, pos, 0, 0, dst);
215 int isamh_write_block (ISAMH is, int cat, int pos, char *src)
217 ++(is->files[cat].no_writes);
218 if (is->method->debug > 2)
219 logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
220 return bf_write (is->files[cat].bf, pos, 0, 0, src);
223 int isamh_write_dblock (ISAMH is, int cat, int pos, char *src,
224 int nextpos, int offset)
226 ISAMH_BLOCK_SIZE size = offset + ISAMH_BLOCK_OFFSET_N;
227 if (is->method->debug > 2)
228 logf (LOG_LOG, "isc: write_dblock. size=%d nextpos=%d",
229 (int) size, nextpos);
230 src -= ISAMH_BLOCK_OFFSET_N;
231 memcpy (src, &nextpos, sizeof(int));
232 memcpy (src + sizeof(int), &size, sizeof(size));
233 return isamh_write_block (is, cat, pos, src);
236 #if ISAMH_FREELIST_CHUNK
237 static void flush_block (ISAMH is, int cat)
239 char *abuf = is->files[cat].alloc_buf;
240 int block = is->files[cat].head.freelist;
241 if (block && is->files[cat].alloc_entries_num)
243 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
244 bf_write (is->files[cat].bf, block, 0, 0, abuf);
245 is->files[cat].alloc_entries_num = 0;
250 static int alloc_block (ISAMH is, int cat)
252 int block = is->files[cat].head.freelist;
253 char *abuf = is->files[cat].alloc_buf;
255 (is->files[cat].no_allocated)++;
259 block = (is->files[cat].head.lastblock)++; /* no free list */
260 is->files[cat].head_is_dirty = 1;
264 if (!is->files[cat].alloc_entries_num) /* read first time */
266 bf_read (is->files[cat].bf, block, 0, 0, abuf);
267 memcpy (&is->files[cat].alloc_entries_num, abuf,
268 sizeof(is->files[cat].alloc_entries_num));
269 assert (is->files[cat].alloc_entries_num > 0);
271 /* have some free blocks now */
272 assert (is->files[cat].alloc_entries_num > 0);
273 is->files[cat].alloc_entries_num--;
274 if (!is->files[cat].alloc_entries_num) /* last one in block? */
276 memcpy (&is->files[cat].head.freelist, abuf + sizeof(int),
278 is->files[cat].head_is_dirty = 1;
280 if (is->files[cat].head.freelist)
282 bf_read (is->files[cat].bf, is->files[cat].head.freelist,
284 memcpy (&is->files[cat].alloc_entries_num, abuf,
285 sizeof(is->files[cat].alloc_entries_num));
286 assert (is->files[cat].alloc_entries_num);
290 memcpy (&block, abuf + sizeof(int) + sizeof(int) *
291 is->files[cat].alloc_entries_num, sizeof(int));
296 static void release_block (ISAMH is, int cat, int pos)
298 char *abuf = is->files[cat].alloc_buf;
299 int block = is->files[cat].head.freelist;
301 (is->files[cat].no_released)++;
303 if (block && !is->files[cat].alloc_entries_num) /* must read block */
305 bf_read (is->files[cat].bf, block, 0, 0, abuf);
306 memcpy (&is->files[cat].alloc_entries_num, abuf,
307 sizeof(is->files[cat].alloc_entries_num));
308 assert (is->files[cat].alloc_entries_num > 0);
310 assert (is->files[cat].alloc_entries_num <= is->files[cat].alloc_entries_max);
311 if (is->files[cat].alloc_entries_num == is->files[cat].alloc_entries_max)
314 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
315 bf_write (is->files[cat].bf, block, 0, 0, abuf);
316 is->files[cat].alloc_entries_num = 0;
318 if (!is->files[cat].alloc_entries_num) /* make new buffer? */
320 memcpy (abuf + sizeof(int), &block, sizeof(int));
321 is->files[cat].head.freelist = pos;
322 is->files[cat].head_is_dirty = 1;
326 memcpy (abuf + sizeof(int) +
327 is->files[cat].alloc_entries_num*sizeof(int),
330 is->files[cat].alloc_entries_num++;
333 static void flush_block (ISAMH is, int cat)
335 char *abuf = is->files[cat].alloc_buf;
339 static int alloc_block (ISAMH is, int cat)
342 char buf[sizeof(int)];
344 is->files[cat].head_is_dirty = 1;
345 (is->files[cat].no_allocated)++;
346 if ((block = is->files[cat].head.freelist))
348 bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
349 memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
352 block = (is->files[cat].head.lastblock)++;
356 static void release_block (ISAMH is, int cat, int pos)
358 char buf[sizeof(int)];
360 (is->files[cat].no_released)++;
361 is->files[cat].head_is_dirty = 1;
362 memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
363 is->files[cat].head.freelist = pos;
364 bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
368 int isamh_alloc_block (ISAMH is, int cat)
372 if (is->files[cat].fc_list)
375 for (j = 0; j < is->files[cat].fc_max; j++)
376 if ((nb = is->files[cat].fc_list[j]) && (!block || nb < block))
378 is->files[cat].fc_list[j] = 0;
384 block = alloc_block (is, cat);
385 if (is->method->debug > 3)
386 logf (LOG_LOG, "isc: alloc_block in cat %d: %d", cat, block);
390 void isamh_release_block (ISAMH is, int cat, int pos)
392 if (is->method->debug > 3)
393 logf (LOG_LOG, "isc: release_block in cat %d: %d", cat, pos);
394 if (is->files[cat].fc_list)
397 for (j = 0; j<is->files[cat].fc_max; j++)
398 if (!is->files[cat].fc_list[j])
400 is->files[cat].fc_list[j] = pos;
404 release_block (is, cat, pos);
407 static void init_fc (ISAMH is, int cat)
411 is->files[cat].fc_max = j;
412 is->files[cat].fc_list = (int *)
413 xmalloc (sizeof(*is->files[0].fc_list) * j);
415 is->files[cat].fc_list[j] = 0;
418 static void release_fc (ISAMH is, int cat)
420 int b, j = is->files[cat].fc_max;
423 if ((b = is->files[cat].fc_list[j]))
425 release_block (is, cat, b);
426 is->files[cat].fc_list[j] = 0;
430 void isamh_pp_close (ISAMH_PP pp)
434 (*is->method->code_stop)(ISAMH_DECODE, pp->decodeClientData);
439 ISAMH_PP isamh_pp_open (ISAMH is, ISAMH_P ipos)
441 ISAMH_PP pp = (ISAMH_PP) xmalloc (sizeof(*pp));
444 pp->cat = isamh_type(ipos);
445 pp->pos = isamh_block(ipos);
447 src = pp->buf = (char *) xmalloc (is->method->filecat[pp->cat].bsize);
453 pp->decodeClientData = (*is->method->code_start)(ISAMH_DECODE);
460 isamh_read_block (is, pp->cat, pp->pos, src);
461 memcpy (&pp->next, src, sizeof(pp->next));
462 src += sizeof(pp->next);
463 memcpy (&pp->size, src, sizeof(pp->size));
464 src += sizeof(pp->size);
465 memcpy (&pp->numKeys, src, sizeof(pp->numKeys));
466 src += sizeof(pp->numKeys);
467 assert (pp->next != pp->pos);
468 pp->offset = src - pp->buf;
469 assert (pp->offset == ISAMH_BLOCK_OFFSET_1);
470 if (is->method->debug > 2)
471 logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
472 pp->size, pp->cat, pp->pos, pp->next);
477 /* returns non-zero if item could be read; 0 otherwise */
478 int isamh_pp_read (ISAMH_PP pp, void *buf)
480 return isamh_read_item (pp, (char **) &buf);
483 /* read one item from file - decode and store it in *dst.
486 1 if item could be read ok and NO boundary
487 2 if item could be read ok and boundary */
488 int isamh_read_item (ISAMH_PP pp, char **dst)
491 char *src = pp->buf + pp->offset;
493 if (pp->offset >= pp->size)
498 return 0; /* end of file */
500 if (pp->next > pp->pos)
502 if (pp->next == pp->pos + 1)
503 is->files[pp->cat].no_next++;
506 is->files[pp->cat].no_forward++;
507 is->files[pp->cat].sum_forward += pp->next - pp->pos;
512 if (pp->next + 1 == pp->pos)
513 is->files[pp->cat].no_prev++;
516 is->files[pp->cat].no_backward++;
517 is->files[pp->cat].sum_backward += pp->pos - pp->next;
520 /* out new block position */
523 /* read block and save 'next' and 'size' entry */
524 isamh_read_block (is, pp->cat, pp->pos, src);
525 memcpy (&pp->next, src, sizeof(pp->next));
526 src += sizeof(pp->next);
527 memcpy (&pp->size, src, sizeof(pp->size));
528 src += sizeof(pp->size);
529 /* assume block is non-empty */
530 assert (src - pp->buf == ISAMH_BLOCK_OFFSET_N);
531 assert (pp->next != pp->pos);
533 isamh_release_block (is, pp->cat, pp->pos);
534 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
535 pp->offset = src - pp->buf;
536 if (is->method->debug > 2)
537 logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
538 pp->size, pp->cat, pp->pos, pp->next);
541 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
542 pp->offset = src - pp->buf;
546 int isamh_pp_num (ISAMH_PP pp)
553 * Revision 1.1 1999-06-30 15:04:54 heikki
554 * Copied from isamc.c, slowly starting to simplify...