X-Git-Url: http://git.indexdata.com/?a=blobdiff_plain;f=isamb%2Fisamb.c;h=bc38a557bfb0343dd921d7725da5c24c6a292558;hb=842cbb4cd47fd56905c92429a6ede3a550b618cf;hp=343e5e3794e18de0d20a4e6edac4a01625db3c30;hpb=1dec188ccbdafb0ec7b7c98857d701a7b77d46a1;p=idzebra-moved-to-github.git diff --git a/isamb/isamb.c b/isamb/isamb.c index 343e5e3..bc38a55 100644 --- a/isamb/isamb.c +++ b/isamb/isamb.c @@ -1,9 +1,26 @@ -/* - * Copyright (c) 2000-2002, Index Data. - * See the file LICENSE for details. - * - * $Id: isamb.c,v 1.17 2002-06-19 10:29:17 adam Exp $ - */ +/* $Id: isamb.c,v 1.28 2004-05-30 18:04:49 adam Exp $ + Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004 + Index Data Aps + +This file is part of the Zebra server. + +Zebra is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +Zebra is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with Zebra; see the file LICENSE.zebra. If not, write to the +Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. +*/ + +#include #include #include #include @@ -14,28 +31,52 @@ struct ISAMB_head { int last_block; int block_size; int block_max; + int free_list; }; #define ISAMB_DATA_OFFSET 3 +/* maximum size of encoded buffer */ #define DST_ITEM_MAX 256 -/* approx 2*4 K + max size of item */ -#define DST_BUF_SIZE 8448 +/* approx 2*max page + max size of item */ +#define DST_BUF_SIZE 16840 + +#define ISAMB_CACHE_ENTRY_SIZE 4096 +/* CAT_MAX: _must_ be power of 2 */ +#define CAT_MAX 4 +#define CAT_MASK (CAT_MAX-1) +/* CAT_NO: <= CAT_MAX */ +#define CAT_NO 4 + +/* ISAMB_PTR_CODEC=1 var, =0 fixed */ +#define ISAMB_PTR_CODEC 1 + +struct ISAMB_cache_entry { + ISAMB_P pos; + unsigned char *buf; + int dirty; + int hits; + struct ISAMB_cache_entry *next; +}; struct ISAMB_file { BFile bf; int head_dirty; struct ISAMB_head head; + struct ISAMB_cache_entry *cache_entries; }; struct ISAMB_s { BFiles bfs; - ISAMC_M method; + ISAMC_M *method; struct ISAMB_file *file; int no_cat; + int cache; /* 0=no cache, 1=use cache, -1=dummy isam (for testing only) */ + int log_io; /* log level for bf_read/bf_write calls */ + int log_freelist; /* log level for freelist handling */ }; struct ISAMB_block { @@ -44,10 +85,12 @@ struct ISAMB_block { int size; int leaf; int dirty; + int deleted; int offset; char *bytes; unsigned char *buf; void *decodeClientData; + int log_rw; }; struct ISAMB_PP_s { @@ -59,86 +102,237 @@ struct ISAMB_PP_s { struct ISAMB_block **block; }; -void encode_ptr (char **dst, int pos) +#if ISAMB_PTR_CODEC +static void encode_ptr (char **dst, unsigned pos) { - memcpy (*dst, &pos, sizeof(pos)); + unsigned char *bp = (unsigned char*) *dst; + + while (pos > 127) + { + *bp++ = 128 | (pos & 127); + pos = pos >> 7; + } + *bp++ = pos; + *dst = (char *) bp; +} +#else +static void encode_ptr (char **dst, unsigned pos) +{ + memcpy(*dst, &pos, sizeof(pos)); (*dst) += sizeof(pos); } +#endif + +#if ISAMB_PTR_CODEC +static void decode_ptr (char **src1, int *pos) +{ + unsigned char **src = (unsigned char **) src1; + unsigned d = 0; + unsigned char c; + unsigned r = 0; -void decode_ptr (char **src, int *pos) + while (((c = *(*src)++) & 128)) + { + d += ((c & 127) << r); + r += 7; + } + d += (c << r); + *pos = d; +} +#else +static void decode_ptr (char **src, int *pos) { - memcpy (pos, *src, sizeof(*pos)); - (*src) += sizeof(*pos); + memcpy (pos, *src, sizeof(*pos)); + (*src) += sizeof(*pos); } +#endif -ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method) +ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M *method, + int cache) { ISAMB isamb = xmalloc (sizeof(*isamb)); int i, b_size = 32; isamb->bfs = bfs; - isamb->method = (ISAMC_M) xmalloc (sizeof(*method)); + isamb->method = (ISAMC_M *) xmalloc (sizeof(*method)); memcpy (isamb->method, method, sizeof(*method)); - isamb->no_cat = 4; + isamb->no_cat = CAT_NO; + isamb->log_io = 0; + isamb->log_freelist = 0; + isamb->cache = cache; + assert (cache == 0); isamb->file = xmalloc (sizeof(*isamb->file) * isamb->no_cat); for (i = 0; ino_cat; i++) { char fname[DST_BUF_SIZE]; + isamb->file[i].cache_entries = 0; isamb->file[i].head_dirty = 0; sprintf (fname, "%s%c", name, i+'A'); - isamb->file[i].bf = bf_open (bfs, fname, b_size, writeflag); - + if (cache) + isamb->file[i].bf = bf_open (bfs, fname, ISAMB_CACHE_ENTRY_SIZE, + writeflag); + else + isamb->file[i].bf = bf_open (bfs, fname, b_size, writeflag); + + if (!bf_read (isamb->file[i].bf, 0, 0, sizeof(struct ISAMB_head), - &isamb->file[i].head)) + &isamb->file[i].head)) { - isamb->file[i].head.first_block = 1; - isamb->file[i].head.last_block = 1; + isamb->file[i].head.first_block = ISAMB_CACHE_ENTRY_SIZE/b_size+1; + isamb->file[i].head.last_block = isamb->file[i].head.first_block; isamb->file[i].head.block_size = b_size; isamb->file[i].head.block_max = b_size - ISAMB_DATA_OFFSET; + isamb->file[i].head.free_list = 0; } assert (isamb->file[i].head.block_size >= ISAMB_DATA_OFFSET); isamb->file[i].head_dirty = 0; + assert(isamb->file[i].head.block_size == b_size); b_size = b_size * 4; } return isamb; } +static void flush_blocks (ISAMB b, int cat) +{ + while (b->file[cat].cache_entries) + { + struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries; + b->file[cat].cache_entries = ce_this->next; + + if (ce_this->dirty) + { + yaz_log (b->log_io, "bf_write: flush_blocks"); + bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf); + } + xfree (ce_this->buf); + xfree (ce_this); + } +} + +static int get_block (ISAMB b, ISAMC_P pos, char *userbuf, int wr) +{ + int cat = pos&CAT_MASK; + int off = ((pos/CAT_MAX) & + (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1)) + * b->file[cat].head.block_size; + int norm = pos / (CAT_MASK*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size); + int no = 0; + struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0; + + if (!b->cache) + return 0; + + assert (ISAMB_CACHE_ENTRY_SIZE >= b->file[cat].head.block_size); + for (ce = &b->file[cat].cache_entries; *ce; ce = &(*ce)->next, no++) + { + ce_last = ce; + if ((*ce)->pos == norm) + { + ce_this = *ce; + *ce = (*ce)->next; /* remove from list */ + + ce_this->next = b->file[cat].cache_entries; /* move to front */ + b->file[cat].cache_entries = ce_this; + + if (wr) + { + memcpy (ce_this->buf + off, userbuf, + b->file[cat].head.block_size); + ce_this->dirty = 1; + } + else + memcpy (userbuf, ce_this->buf + off, + b->file[cat].head.block_size); + return 1; + } + } + if (no >= 40) + { + assert (no == 40); + assert (ce_last && *ce_last); + ce_this = *ce_last; + *ce_last = 0; /* remove the last entry from list */ + if (ce_this->dirty) + { + yaz_log (b->log_io, "bf_write: get_block"); + bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf); + } + xfree (ce_this->buf); + xfree (ce_this); + } + ce_this = xmalloc (sizeof(*ce_this)); + ce_this->next = b->file[cat].cache_entries; + b->file[cat].cache_entries = ce_this; + ce_this->buf = xmalloc (ISAMB_CACHE_ENTRY_SIZE); + ce_this->pos = norm; + yaz_log (b->log_io, "bf_read: get_block"); + if (!bf_read (b->file[cat].bf, norm, 0, 0, ce_this->buf)) + memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE); + if (wr) + { + memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size); + ce_this->dirty = 1; + } + else + { + ce_this->dirty = 0; + memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size); + } + return 1; +} + + void isamb_close (ISAMB isamb) { int i; for (i = 0; ino_cat; i++) { + flush_blocks (isamb, i); if (isamb->file[i].head_dirty) bf_write (isamb->file[i].bf, 0, 0, sizeof(struct ISAMB_head), &isamb->file[i].head); + + bf_close (isamb->file[i].bf); } xfree (isamb->file); xfree (isamb->method); xfree (isamb); } + struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos) { - int cat = pos&3; + int cat = pos&CAT_MASK; struct ISAMB_block *p; if (!pos) return 0; p = xmalloc (sizeof(*p)); p->pos = pos; - p->cat = pos & 3; + p->cat = pos & CAT_MASK; p->buf = xmalloc (b->file[cat].head.block_size); - if (!bf_read (b->file[cat].bf, pos/4, 0, 0, p->buf)) + + if (!get_block (b, pos, p->buf, 0)) { - yaz_log (LOG_FATAL, "read failure for pos=%ld block=%ld", - (long) pos, (long) pos/4); - abort(); + yaz_log (b->log_io, "bf_read: open_block"); + if (!bf_read (b->file[cat].bf, pos/CAT_MAX, 0, 0, p->buf)) + { + yaz_log (LOG_FATAL, "isamb: read fail for pos=%ld block=%ld", + (long) pos, (long) pos/CAT_MAX); + abort(); + } } p->bytes = p->buf + ISAMB_DATA_OFFSET; p->leaf = p->buf[0]; - p->size = p->buf[1] + 256 * p->buf[2] - ISAMB_DATA_OFFSET; + p->size = (p->buf[1] + 256 * p->buf[2]) - ISAMB_DATA_OFFSET; + if (p->size < 0) + { + fprintf (stderr, "pos=%d\n", pos); + } + assert (p->size >= 0); p->offset = 0; p->dirty = 0; + p->deleted = 0; p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE); return p; } @@ -146,20 +340,42 @@ struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos) struct ISAMB_block *new_block (ISAMB b, int leaf, int cat) { struct ISAMB_block *p; - int block_no; - + p = xmalloc (sizeof(*p)); - block_no = b->file[cat].head.last_block++; - p->cat = cat; - p->pos = block_no * 4 + cat; + p->buf = xmalloc (b->file[cat].head.block_size); + + if (!b->file[cat].head.free_list) + { + int block_no; + block_no = b->file[cat].head.last_block++; + p->pos = block_no * CAT_MAX + cat; + } + else + { + p->pos = b->file[cat].head.free_list; + assert((p->pos & CAT_MASK) == cat); + if (!get_block (b, p->pos, p->buf, 0)) + { + yaz_log (b->log_io, "bf_read: new_block"); + if (!bf_read (b->file[cat].bf, p->pos/CAT_MAX, 0, 0, p->buf)) + { + yaz_log (LOG_FATAL, "isamb: read fail for pos=%ld block=%ld", + (long) p->pos/CAT_MAX, (long) p->pos/CAT_MAX); + abort (); + } + } + yaz_log (b->log_freelist, "got block %d from freelist %d:%d", p->pos, + cat, p->pos/CAT_MAX); + memcpy (&b->file[cat].head.free_list, p->buf, sizeof(int)); + } p->cat = cat; b->file[cat].head_dirty = 1; - p->buf = xmalloc (b->file[cat].head.block_size); memset (p->buf, 0, b->file[cat].head.block_size); p->bytes = p->buf + ISAMB_DATA_OFFSET; p->leaf = leaf; p->size = 0; p->dirty = 1; + p->deleted = 0; p->offset = 0; p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE); return p; @@ -176,17 +392,63 @@ struct ISAMB_block *new_int (ISAMB b, int cat) return new_block (b, 0, cat); } +static void check_block (ISAMB b, struct ISAMB_block *p) +{ + if (p->leaf) + { + ; + } + else + { + /* sanity check */ + char *startp = p->bytes; + char *src = startp; + char *endp = p->bytes + p->size; + int pos; + + decode_ptr (&src, &pos); + assert ((pos&CAT_MASK) == p->cat); + while (src != endp) + { + int item_len; + decode_ptr (&src, &item_len); + assert (item_len > 0 && item_len < 30); + src += item_len; + decode_ptr (&src, &pos); + assert ((pos&CAT_MASK) == p->cat); + } + } +} + void close_block (ISAMB b, struct ISAMB_block *p) { if (!p) return; - if (p->dirty) + if (p->deleted) + { + yaz_log (b->log_freelist, "release block %d from freelist %d:%d", + p->pos, p->cat, p->pos/CAT_MAX); + memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(int)); + b->file[p->cat].head.free_list = p->pos; + if (!get_block (b, p->pos, p->buf, 1)) + { + yaz_log (b->log_io, "bf_write: close_block (deleted)"); + bf_write (b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf); + } + } + else if (p->dirty) { int size = p->size + ISAMB_DATA_OFFSET; + assert (p->size >= 0); p->buf[0] = p->leaf; p->buf[1] = size & 255; p->buf[2] = size >> 8; - bf_write (b->file[p->cat].bf, p->pos/4, 0, 0, p->buf); + check_block(b, p); + if (!get_block (b, p->pos, p->buf, 1)) + { + yaz_log (b->log_io, "bf_write: close_block"); + bf_write (b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf); + } } (*b->method->code_stop)(ISAMC_DECODE, p->decodeClientData); xfree (p->buf); @@ -195,14 +457,14 @@ void close_block (ISAMB b, struct ISAMB_block *p) int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item, int *mode, - ISAMC_I stream, + ISAMC_I *stream, struct ISAMB_block **sp, void *sub_item, int *sub_size, void *max_item); int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, int *mode, - ISAMC_I stream, struct ISAMB_block **sp, + ISAMC_I *stream, struct ISAMB_block **sp, void *split_item, int *split_size, void *last_max_item) { char *startp = p->bytes; @@ -216,11 +478,13 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, *sp = 0; + assert(p->size >= 0); decode_ptr (&src, &pos); while (src != endp) { int item_len; int d; + char *src0 = src; decode_ptr (&src, &item_len); d = (*b->method->compare_item)(src, lookahead_item); if (d > 0) @@ -230,6 +494,7 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2, sub_item, &sub_size, src); + src = src0; break; } src += item_len; @@ -266,6 +531,7 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, dst += endp - src; } p->size = dst - dst_buf; + assert (p->size >= 0); if (p->size <= b->file[p->cat].head.block_max) { memcpy (startp, dst_buf, dst - dst_buf); @@ -307,7 +573,8 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, - int *lookahead_mode, ISAMC_I stream, struct ISAMB_block **sp2, + int *lookahead_mode, ISAMC_I *stream, + struct ISAMB_block **sp2, void *sub_item, int *sub_size, void *max_item) { @@ -318,7 +585,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, void *c1 = (*b->method->code_start)(ISAMC_DECODE); void *c2 = (*b->method->code_start)(ISAMC_ENCODE); int more = 1; - int quater = b->file[b->no_cat-1].head.block_max / 4; + int quater = b->file[b->no_cat-1].head.block_max / CAT_MAX; char *cut = dst_buf + quater * 2; char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max; char *half1 = 0; @@ -347,7 +614,11 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, if (d > 0) { dst_item = lookahead_item; - assert (*lookahead_mode); + if (!*lookahead_mode) + { + yaz_log (LOG_WARN, "isamb: Inconsistent register (1)"); + assert (*lookahead_mode); + } } else dst_item = file_item_buf; @@ -433,7 +704,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, } if (!*lookahead_mode) { - yaz_log (LOG_WARN, "Inconsistent register (2)"); + yaz_log (LOG_WARN, "isamb: Inconsistent register (2)"); abort(); } else if (!half1 && dst > cut) @@ -471,6 +742,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, new_size > b->file[p->cat].head.block_max) { /* non-btree block will be removed */ + p->deleted = 1; close_block (b, p); /* delete it too!! */ p = 0; /* make a new one anyway */ @@ -527,7 +799,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item, int *mode, - ISAMC_I stream, + ISAMC_I *stream, struct ISAMB_block **sp, void *sub_item, int *sub_size, void *max_item) @@ -540,13 +812,53 @@ int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item, sub_size, max_item); } -int isamb_merge (ISAMB b, ISAMC_P pos, ISAMC_I stream) +int isamb_unlink (ISAMB b, ISAMC_P pos) +{ + struct ISAMB_block *p1; + + if (!pos) + return 0; + p1 = open_block(b, pos); + p1->deleted = 1; + if (!p1->leaf) + { + int sub_p; + int item_len; + char *src = p1->bytes + p1->offset; + + decode_ptr(&src, &sub_p); + isamb_unlink(b, sub_p); + + while (src != p1->bytes + p1->size) + { + decode_ptr(&src, &item_len); + src += item_len; + decode_ptr(&src, &sub_p); + isamb_unlink(b, sub_p); + } + } + close_block(b, p1); + return 0; +} + +int isamb_merge (ISAMB b, ISAMC_P pos, ISAMC_I *stream) { char item_buf[DST_ITEM_MAX]; char *item_ptr; int i_mode; int more; + if (b->cache < 0) + { + int more = 1; + while (more) + { + item_ptr = item_buf; + more = + (*stream->read_item)(stream->clientData, &item_ptr, &i_mode); + } + return 1; + } item_ptr = item_buf; more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode); while (more) @@ -645,7 +957,7 @@ int isamb_block_info (ISAMB isamb, int cat) void isamb_pp_close (ISAMB_PP pp) { - return isamb_pp_close_x (pp, 0, 0); + isamb_pp_close_x (pp, 0, 0); } int isamb_pp_read (ISAMB_PP pp, void *buf)