2 * Copyright (c) 1995-1998, Index Data.
3 * See the file LICENSE for details.
6 * Isamd - isam with diffs
9 * most of it, this is just a copy of isamh
24 #include "../index/index.h" /* for dump */
26 static void flush_block (ISAMH is, int cat);
27 static void release_fc (ISAMH is, int cat);
28 static void init_fc (ISAMH is, int cat);
30 #define ISAMH_FREELIST_CHUNK 1
34 ISAMH_M isamd_getmethod (void)
36 static struct ISAMH_filecat_s def_cat[] = {
38 /* blocksz, max keys before switching size */
56 /* assume about 2 bytes per pointer, when compressed. The head uses */
57 /* 16 bytes, and other blocks use 8 for header info... If you want 3 */
58 /* blocks of 32 bytes, say max 16+24+24 = 64 keys */
61 ISAMH_M m = (ISAMH_M) xmalloc (sizeof(*m));
69 m->compare_item = NULL;
73 m->max_blocks_mem = 10;
80 ISAMH isamd_open (BFiles bfs, const char *name, int writeflag, ISAMH_M method)
83 ISAMH_filecat filecat;
87 is = (ISAMH) xmalloc (sizeof(*is));
89 is->method = (ISAMH_M) xmalloc (sizeof(*is->method));
90 memcpy (is->method, method, sizeof(*method));
91 filecat = is->method->filecat;
94 /* determine number of block categories */
95 if (is->method->debug)
96 logf (LOG_LOG, "isc: bsize maxkeys");
99 if (is->method->debug)
100 logf (LOG_LOG, "isc:%6d %6d",
101 filecat[i].bsize, filecat[i].mblocks);
102 if (max_buf_size < filecat[i].bsize)
103 max_buf_size = filecat[i].bsize;
104 } while (filecat[i++].mblocks);
108 /* max_buf_size is the larget buffer to be used during merge */
109 max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
110 if (max_buf_size < (1+is->method->max_blocks_mem) * filecat[i].bsize)
111 max_buf_size = (1+is->method->max_blocks_mem) * filecat[i].bsize;
114 if (is->method->debug)
115 logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
117 assert (is->no_files > 0);
118 is->files = (ISAMH_file) xmalloc (sizeof(*is->files)*is->no_files);
122 is->merge_buf = (char *) xmalloc (max_buf_size+256);
123 memset (is->merge_buf, 0, max_buf_size+256);
125 is->startblock = (char *) xmalloc (max_buf_size+256);
126 memset (is->startblock, 0, max_buf_size+256);
127 is->lastblock = (char *) xmalloc (max_buf_size+256);
128 memset (is->lastblock, 0, max_buf_size+256);
129 /* The spare 256 bytes should not be needed! */
133 is->startblock = is->lastblock = NULL;
135 for (i = 0; i<is->no_files; i++)
139 sprintf (fname, "%s%c", name, i+'A');
140 is->files[i].bf = bf_open (bfs, fname, is->method->filecat[i].bsize,
142 is->files[i].head_is_dirty = 0;
143 if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
146 is->files[i].head.lastblock = 1;
147 is->files[i].head.freelist = 0;
149 is->files[i].alloc_entries_num = 0;
150 is->files[i].alloc_entries_max =
151 is->method->filecat[i].bsize / sizeof(int) - 1;
152 is->files[i].alloc_buf = (char *)
153 xmalloc (is->method->filecat[i].bsize);
154 is->files[i].no_writes = 0;
155 is->files[i].no_reads = 0;
156 is->files[i].no_skip_writes = 0;
157 is->files[i].no_allocated = 0;
158 is->files[i].no_released = 0;
159 is->files[i].no_remap = 0;
160 is->files[i].no_forward = 0;
161 is->files[i].no_backward = 0;
162 is->files[i].sum_forward = 0;
163 is->files[i].sum_backward = 0;
164 is->files[i].no_next = 0;
165 is->files[i].no_prev = 0;
172 int isamd_block_used (ISAMH is, int type)
174 if (type < 0 || type >= is->no_files)
176 return is->files[type].head.lastblock-1;
179 int isamd_block_size (ISAMH is, int type)
181 ISAMH_filecat filecat = is->method->filecat;
182 if (type < 0 || type >= is->no_files)
184 return filecat[type].bsize;
187 int isamd_close (ISAMH is)
191 if (is->method->debug)
193 logf (LOG_LOG, "isc: next forw mid-f prev backw mid-b");
194 for (i = 0; i<is->no_files; i++)
195 logf (LOG_LOG, "isc:%8d%8d%8.1f%8d%8d%8.1f",
196 is->files[i].no_next,
197 is->files[i].no_forward,
198 is->files[i].no_forward ?
199 (double) is->files[i].sum_forward/is->files[i].no_forward
201 is->files[i].no_prev,
202 is->files[i].no_backward,
203 is->files[i].no_backward ?
204 (double) is->files[i].sum_backward/is->files[i].no_backward
207 if (is->method->debug)
208 logf (LOG_LOG, "isc: writes reads skipped alloc released remap");
209 for (i = 0; i<is->no_files; i++)
212 assert (is->files[i].bf);
213 if (is->files[i].head_is_dirty)
214 bf_write (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
216 if (is->method->debug)
217 logf (LOG_LOG, "isc:%8d%8d%8d%8d%8d%8d",
218 is->files[i].no_writes,
219 is->files[i].no_reads,
220 is->files[i].no_skip_writes,
221 is->files[i].no_allocated,
222 is->files[i].no_released,
223 is->files[i].no_remap);
224 xfree (is->files[i].fc_list);
226 bf_close (is->files[i].bf);
229 xfree (is->startblock);
230 xfree (is->lastblock);
236 int isamd_read_block (ISAMH is, int cat, int pos, char *dst)
238 ++(is->files[cat].no_reads);
239 return bf_read (is->files[cat].bf, pos, 0, 0, dst);
242 int isamd_write_block (ISAMH is, int cat, int pos, char *src)
244 ++(is->files[cat].no_writes);
245 if (is->method->debug > 2)
246 logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
247 return bf_write (is->files[cat].bf, pos, 0, 0, src);
250 int isamd_write_dblock (ISAMH is, int cat, int pos, char *src,
251 int nextpos, int offset)
253 ISAMH_BLOCK_SIZE size = offset + ISAMH_BLOCK_OFFSET_N;
254 if (is->method->debug > 2)
255 logf (LOG_LOG, "isc: write_dblock. size=%d nextpos=%d",
256 (int) size, nextpos);
257 src -= ISAMH_BLOCK_OFFSET_N;
258 memcpy (src, &nextpos, sizeof(int));
259 memcpy (src + sizeof(int), &size, sizeof(size));
260 return isamd_write_block (is, cat, pos, src);
263 #if ISAMH_FREELIST_CHUNK
264 static void flush_block (ISAMH is, int cat)
266 char *abuf = is->files[cat].alloc_buf;
267 int block = is->files[cat].head.freelist;
268 if (block && is->files[cat].alloc_entries_num)
270 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
271 bf_write (is->files[cat].bf, block, 0, 0, abuf);
272 is->files[cat].alloc_entries_num = 0;
277 static int alloc_block (ISAMH is, int cat)
279 int block = is->files[cat].head.freelist;
280 char *abuf = is->files[cat].alloc_buf;
282 (is->files[cat].no_allocated)++;
286 block = (is->files[cat].head.lastblock)++; /* no free list */
287 is->files[cat].head_is_dirty = 1;
291 if (!is->files[cat].alloc_entries_num) /* read first time */
293 bf_read (is->files[cat].bf, block, 0, 0, abuf);
294 memcpy (&is->files[cat].alloc_entries_num, abuf,
295 sizeof(is->files[cat].alloc_entries_num));
296 assert (is->files[cat].alloc_entries_num > 0);
298 /* have some free blocks now */
299 assert (is->files[cat].alloc_entries_num > 0);
300 is->files[cat].alloc_entries_num--;
301 if (!is->files[cat].alloc_entries_num) /* last one in block? */
303 memcpy (&is->files[cat].head.freelist, abuf + sizeof(int),
305 is->files[cat].head_is_dirty = 1;
307 if (is->files[cat].head.freelist)
309 bf_read (is->files[cat].bf, is->files[cat].head.freelist,
311 memcpy (&is->files[cat].alloc_entries_num, abuf,
312 sizeof(is->files[cat].alloc_entries_num));
313 assert (is->files[cat].alloc_entries_num);
317 memcpy (&block, abuf + sizeof(int) + sizeof(int) *
318 is->files[cat].alloc_entries_num, sizeof(int));
323 static void release_block (ISAMH is, int cat, int pos)
325 char *abuf = is->files[cat].alloc_buf;
326 int block = is->files[cat].head.freelist;
328 (is->files[cat].no_released)++;
330 if (block && !is->files[cat].alloc_entries_num) /* must read block */
332 bf_read (is->files[cat].bf, block, 0, 0, abuf);
333 memcpy (&is->files[cat].alloc_entries_num, abuf,
334 sizeof(is->files[cat].alloc_entries_num));
335 assert (is->files[cat].alloc_entries_num > 0);
337 assert (is->files[cat].alloc_entries_num <= is->files[cat].alloc_entries_max);
338 if (is->files[cat].alloc_entries_num == is->files[cat].alloc_entries_max)
341 memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
342 bf_write (is->files[cat].bf, block, 0, 0, abuf);
343 is->files[cat].alloc_entries_num = 0;
345 if (!is->files[cat].alloc_entries_num) /* make new buffer? */
347 memcpy (abuf + sizeof(int), &block, sizeof(int));
348 is->files[cat].head.freelist = pos;
349 is->files[cat].head_is_dirty = 1;
353 memcpy (abuf + sizeof(int) +
354 is->files[cat].alloc_entries_num*sizeof(int),
357 is->files[cat].alloc_entries_num++;
360 static void flush_block (ISAMH is, int cat)
362 char *abuf = is->files[cat].alloc_buf;
366 static int alloc_block (ISAMH is, int cat)
369 char buf[sizeof(int)];
371 is->files[cat].head_is_dirty = 1;
372 (is->files[cat].no_allocated)++;
373 if ((block = is->files[cat].head.freelist))
375 bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
376 memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
379 block = (is->files[cat].head.lastblock)++;
383 static void release_block (ISAMH is, int cat, int pos)
385 char buf[sizeof(int)];
387 (is->files[cat].no_released)++;
388 is->files[cat].head_is_dirty = 1;
389 memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
390 is->files[cat].head.freelist = pos;
391 bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
395 int isamd_alloc_block (ISAMH is, int cat)
399 if (is->files[cat].fc_list)
402 for (j = 0; j < is->files[cat].fc_max; j++)
403 if ((nb = is->files[cat].fc_list[j]) && (!block || nb < block))
405 is->files[cat].fc_list[j] = 0;
411 block = alloc_block (is, cat);
412 if (is->method->debug > 3)
413 logf (LOG_LOG, "isc: alloc_block in cat %d: %d", cat, block);
417 void isamd_release_block (ISAMH is, int cat, int pos)
419 if (is->method->debug > 3)
420 logf (LOG_LOG, "isc: release_block in cat %d: %d", cat, pos);
421 if (is->files[cat].fc_list)
424 for (j = 0; j<is->files[cat].fc_max; j++)
425 if (!is->files[cat].fc_list[j])
427 is->files[cat].fc_list[j] = pos;
431 release_block (is, cat, pos);
434 static void init_fc (ISAMH is, int cat)
438 is->files[cat].fc_max = j;
439 is->files[cat].fc_list = (int *)
440 xmalloc (sizeof(*is->files[0].fc_list) * j);
442 is->files[cat].fc_list[j] = 0;
445 static void release_fc (ISAMH is, int cat)
447 int b, j = is->files[cat].fc_max;
450 if ((b = is->files[cat].fc_list[j]))
452 release_block (is, cat, b);
453 is->files[cat].fc_list[j] = 0;
457 void isamd_pp_close (ISAMH_PP pp)
461 (*is->method->code_stop)(ISAMH_DECODE, pp->decodeClientData);
466 ISAMH_PP isamd_pp_open (ISAMH is, ISAMH_P ipos)
468 ISAMH_PP pp = (ISAMH_PP) xmalloc (sizeof(*pp));
471 pp->cat = isamd_type(ipos);
472 pp->pos = isamd_block(ipos);
474 src = pp->buf = (char *) xmalloc (is->method->filecat[pp->cat].bsize);
480 pp->decodeClientData = (*is->method->code_start)(ISAMH_DECODE);
488 isamd_read_block (is, pp->cat, pp->pos, src);
489 memcpy (&pp->next, src, sizeof(pp->next));
490 src += sizeof(pp->next);
491 memcpy (&pp->size, src, sizeof(pp->size));
492 src += sizeof(pp->size);
493 memcpy (&pp->numKeys, src, sizeof(pp->numKeys));
494 src += sizeof(pp->numKeys);
495 memcpy (&pp->lastblock, src, sizeof(pp->lastblock));
496 src += sizeof(pp->lastblock);
497 assert (pp->next != pp->pos);
498 pp->offset = src - pp->buf;
499 assert (pp->offset == ISAMH_BLOCK_OFFSET_1);
500 if (is->method->debug > 2)
501 logf (LOG_LOG, "isamd_pp_open sz=%d c=%d p=%d n=%d",
502 pp->size, pp->cat, pp->pos, isamd_block(pp->next));
509 void isamd_buildfirstblock(ISAMH_PP pp){
512 assert(pp->next != pp->pos);
513 memcpy(dst, &pp->next, sizeof(pp->next) );
514 dst += sizeof(pp->next);
515 memcpy(dst, &pp->size,sizeof(pp->size));
516 dst += sizeof(pp->size);
517 memcpy(dst, &pp->numKeys, sizeof(pp->numKeys));
518 dst += sizeof(pp->numKeys);
519 memcpy(dst, &pp->lastblock, sizeof(pp->lastblock));
520 dst += sizeof(pp->lastblock);
521 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_1);
522 if (pp->is->method->debug > 2)
523 logf (LOG_LOG, "isamd: first: sz=%d p=%d/%d>%d/%d>%d/%d nk=%d",
526 isamd_block(pp->next), isamd_type(pp->next),
527 isamd_block(pp->lastblock), isamd_type(pp->lastblock),
531 void isamd_buildlaterblock(ISAMH_PP pp){
534 assert(pp->next != isamd_addr(pp->pos,pp->cat));
535 memcpy(dst, &pp->next, sizeof(pp->next) );
536 dst += sizeof(pp->next);
537 memcpy(dst, &pp->size,sizeof(pp->size));
538 dst += sizeof(pp->size);
539 assert (dst - pp->buf == ISAMH_BLOCK_OFFSET_N);
540 if (pp->is->method->debug > 2)
541 logf (LOG_LOG, "isamd: l8r: sz=%d p=%d/%d>%d/%d",
544 isamd_block(pp->next), isamd_type(pp->next) );
549 /* returns non-zero if item could be read; 0 otherwise */
550 int isamd_pp_read (ISAMH_PP pp, void *buf)
552 return isamd_read_item (pp, (char **) &buf);
555 /* read one item from file - decode and store it in *dst.
558 1 if item could be read ok and NO boundary
559 2 if item could be read ok and boundary */
560 int isamd_read_item (ISAMH_PP pp, char **dst)
563 char *src = pp->buf + pp->offset;
566 if (pp->offset >= pp->size)
571 return 0; /* end of file */
573 if (pp->next > pp->pos)
575 if (pp->next == pp->pos + 1)
576 is->files[pp->cat].no_next++;
579 is->files[pp->cat].no_forward++;
580 is->files[pp->cat].sum_forward += pp->next - pp->pos;
585 if (pp->next + 1 == pp->pos)
586 is->files[pp->cat].no_prev++;
589 is->files[pp->cat].no_backward++;
590 is->files[pp->cat].sum_backward += pp->pos - pp->next;
593 /* out new block position */
594 newcat = isamd_type(pp->next);
595 if (pp->cat != newcat ) {
596 pp->buf = xrealloc(pp->buf, is->method->filecat[newcat].bsize);
598 pp->pos = isamd_block(pp->next);
599 pp->cat = isamd_type(pp->next);
602 /* read block and save 'next' and 'size' entry */
603 isamd_read_block (is, pp->cat, pp->pos, src);
604 memcpy (&pp->next, src, sizeof(pp->next));
605 src += sizeof(pp->next);
606 memcpy (&pp->size, src, sizeof(pp->size));
607 src += sizeof(pp->size);
608 /* assume block is non-empty */
609 assert (src - pp->buf == ISAMH_BLOCK_OFFSET_N);
610 assert (pp->next != isamd_addr(pp->pos,pp->cat));
612 isamd_release_block (is, pp->cat, pp->pos);
613 (*is->method->code_reset)(pp->decodeClientData);
614 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
615 pp->offset = src - pp->buf;
616 if (is->method->debug > 2)
617 logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
618 pp->size, pp->cat, pp->pos, pp->next);
621 (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
622 pp->offset = src - pp->buf;
626 int isamd_pp_num (ISAMH_PP pp)
631 static char *hexdump(unsigned char *p, int len, char *buff) {
632 static char localbuff[128];
634 if (!buff) buff=localbuff;
637 sprintf(bytebuff,"%02x",*p);
639 strcat(buff,bytebuff);
640 if (len) strcat(buff," ");
646 void isamd_pp_dump (ISAMH is, ISAMH_P ipos)
656 logf(LOG_LOG,"dumping isamd block %d (%d:%d)",
657 (int)ipos, isamd_type(ipos), isamd_block(ipos) );
658 pp=isamd_pp_open(is,ipos);
659 logf(LOG_LOG,"numKeys=%d, last=%d (%d:%d) ofs=%d ",
662 isamd_type(pp->lastblock), isamd_block(pp->lastblock),
665 while(isamd_pp_read(pp, &key))
667 if (oldaddr != isamd_addr(pp->pos,pp->cat) )
669 oldaddr = isamd_addr(pp->pos,pp->cat);
670 logf(LOG_LOG,"block %d (%d:%d) sz=%d nx=%d (%d:%d) ofs=%d",
671 isamd_addr(pp->pos,pp->cat),
672 pp->cat, pp->pos, pp->size,
673 pp->next, isamd_type(pp->next), isamd_block(pp->next),
679 logf(LOG_LOG," %05x: %s",i,hexdump(pp->buf+i,n,hexbuff));
682 if (oldoffs > ISAMH_BLOCK_OFFSET_N)
683 oldoffs=ISAMH_BLOCK_OFFSET_N;
686 logf (LOG_LOG," got %d:%d=%x:%x from %s at %d=%x",
687 key.sysno, key.seqno,
688 key.sysno, key.seqno,
689 hexdump(pp->buf+oldoffs, pp->offset-oldoffs, hexbuff),
691 oldoffs = pp->offset;
698 * Revision 1.1 1999-07-14 12:34:43 heikki
699 * Copied from isamh, starting to change things...