From a5545de18b5d3762a1f29569a4b10ca5017506db Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Tue, 27 Sep 1994 20:03:36 +0000 Subject: [PATCH] Seems relatively bug-free. --- include/isam.h | 14 +++++--- isam/Makefile | 6 ++-- isam/isam.c | 36 +++++++++++++------ isam/issh.c | 1 - isam/memory.c | 103 +++++++++++++++++++++++++++++++++++++++++++------------ isam/memory.h | 16 ++++++--- isam/physical.c | 91 ++++++++++++++++++++++++++++++++++++++++-------- 7 files changed, 207 insertions(+), 60 deletions(-) diff --git a/include/isam.h b/include/isam.h index bf96583..3b694bd 100644 --- a/include/isam.h +++ b/include/isam.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.h,v $ - * Revision 1.4 1994-09-26 17:05:54 quinn + * Revision 1.5 1994-09-27 20:03:36 quinn + * Seems relatively bug-free. + * + * Revision 1.4 1994/09/26 17:05:54 quinn * Trivial. * * Revision 1.3 1994/09/26 16:08:42 quinn @@ -23,12 +26,14 @@ #include +#include "../isam/memory.h" +#include "../isam/physical.h" + #define IS_MAX_BLOCKTYPES 4 #define IS_MAX_RECORD 512 #define IS_DEF_REPACK_PERCENT "30" /* how much relative change before repack */ typedef unsigned int SYSNO; /* should be somewhere else */ -typedef unsigned int ISAM_P; /* * Description of a blocktype (part of an isam file) @@ -42,7 +47,7 @@ typedef struct isam_blocktype int max_keys_block0; /* max num of keys in first block */ int nice_keys_block; /* nice number of keys per block */ int max_keys; /* max number of keys per table */ - int freelist; /* fist free block */ + int freelist; /* first free block */ int top; /* first unused block */ int index; /* placeholder. Always 0. */ char *dbuf; /* buffer for use in I/O operations */ @@ -59,9 +64,8 @@ typedef struct isam_struct int keysize; /* size of the keys (records) used */ int repack; /* how many percent to grow before repack */ int (*cmp)(const void *k1, const void *k2); /* compare function */ -} isam_struct, *ISAM; +} isam_struct; -struct is_mtable; typedef struct ispt_struct { struct is_mtable *tab; diff --git a/isam/Makefile b/isam/Makefile index 345135a..341ee3e 100644 --- a/isam/Makefile +++ b/isam/Makefile @@ -1,7 +1,7 @@ # Copyright (C) 1994, Index Data I/S # All rights reserved. # Sebastian Hammer, Adam Dickmeiss -# $Id: Makefile,v 1.10 1994-09-27 16:31:40 adam Exp $ +# $Id: Makefile,v 1.11 1994-09-27 20:03:50 quinn Exp $ SHELL=/bin/sh INCLUDE=-I../include @@ -13,6 +13,8 @@ CPP=cc -E all: $(LIB) +alll: $(LIB) isam-test issh + test: test.c $(LIB) $(CC) -g -o test -I../include test.c \ ../lib/isam.a ../lib/bfile.a ../lib/util.a @@ -37,7 +39,7 @@ $(LIB): $(PO) $(CC) -c $(DEFS) $(CFLAGS) $< clean: - rm -f *.[oa] $(TPROG) core mon.out gmon.out errlist isam-test issh + rm -f *.[oa] $(TPROG) core mon.out gmon.out errlist test isam-test issh depend: depend2 diff --git a/isam/isam.c b/isam/isam.c index 2f58aa1..3ae755c 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.4 1994-09-26 17:11:29 quinn + * Revision 1.5 1994-09-27 20:03:50 quinn + * Seems relatively bug-free. + * + * Revision 1.4 1994/09/26 17:11:29 quinn * Trivial * * Revision 1.3 1994/09/26 17:06:35 quinn @@ -25,8 +28,6 @@ #include #include "isutil.h" #include "rootblk.h" -#include "memory.h" -#include "physical.h" #include "keyops.h" static int splitargs(const char *s, char *bf[], int max) @@ -266,7 +267,7 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) is_mtable tab; int res; char keybuf[IS_MAX_RECORD]; - int oldnum, oldtype; + int oldnum, oldtype, i; char operation, *record; is_m_establish_tab(is, &tab, pos); @@ -282,10 +283,10 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) while (num) { operation = *(data)++; - record = (char*)data; + record = (char*) data; data += is_keysize(is); num--; - while (num && !memcmp(record, data, is_keysize(tab.is) + 1)) + while (num && !memcmp(record - 1, data, is_keysize(tab.is) + 1)) { data += 1 + is_keysize(is); num--; @@ -337,16 +338,29 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) } } } - while (tab.pos_type < tab.is->num_types - 1 && tab.num_records > - tab.is->types[tab.pos_type].max_keys) - tab.pos_type++; + i = tab.pos_type; + while (i < tab.is->num_types - 1 && tab.num_records > + tab.is->types[i].max_keys) + i++; + if (i != tab.pos_type) + { + is_p_unmap(&tab); + tab.pos_type = i; + } if (!oldnum || tab.pos_type != oldtype || (abs(oldnum - tab.num_records) * 100) / oldnum > tab.is->repack) is_p_remap(&tab); else is_p_align(&tab); - is_p_sync(&tab); - return is_address(tab.pos_type, tab.data->diskpos); + if (tab.data) + { + is_p_sync(&tab); + pos = is_address(tab.pos_type, tab.data->diskpos); + } + else + pos = 0; + is_m_release_tab(&tab); + return pos; } /* diff --git a/isam/issh.c b/isam/issh.c index 0b5fb8b..15232bb 100644 --- a/isam/issh.c +++ b/isam/issh.c @@ -3,7 +3,6 @@ #include #include -#include #include static ISAM is = 0; diff --git a/isam/memory.c b/isam/memory.c index 38091b2..7962a0e 100644 --- a/isam/memory.c +++ b/isam/memory.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: memory.c,v $ - * Revision 1.3 1994-09-26 17:11:30 quinn + * Revision 1.4 1994-09-27 20:03:52 quinn + * Seems relatively bug-free. + * + * Revision 1.3 1994/09/26 17:11:30 quinn * Trivial * * Revision 1.2 1994/09/26 17:06:35 quinn @@ -22,22 +25,32 @@ #include #include -#include "memory.h" -#include "physical.h" #include int is_mbuf_size[3] = { 0, 1024, 4096 }; -/* - * TODO: make internal memory-management scheme for these units. - */ +static is_mblock *mblock_tmplist = 0, *mblock_freelist = 0; +static is_mbuf *mbuf_freelist[3] = {0, 0, 0}; + +#define MALLOC_CHUNK 20 is_mblock *xmalloc_mblock() { is_mblock *tmp; + int i; - tmp = xmalloc(sizeof(is_mblock)); + if (!mblock_freelist) + { + mblock_freelist = xmalloc(sizeof(is_mblock) * MALLOC_CHUNK); + for (i = 0; i < MALLOC_CHUNK - 1; i++) + mblock_freelist[i].next = &mblock_freelist[i+1]; + mblock_freelist[i].next = 0; + } + tmp = mblock_freelist; + mblock_freelist = mblock_freelist->next; tmp->next = 0; + tmp->state = IS_MBSTATE_UNREAD; + tmp->data = 0; return tmp; } @@ -45,8 +58,16 @@ is_mbuf *xmalloc_mbuf(int type) { is_mbuf *tmp; - tmp = xmalloc(sizeof(is_mbuf) + is_mbuf_size[type]); - tmp->type = type; + if (mbuf_freelist[type]) + { + tmp = mbuf_freelist[type]; + mbuf_freelist[type] = tmp->next; + } + else + { + tmp = xmalloc(sizeof(is_mbuf) + is_mbuf_size[type]); + tmp->type = type; + } tmp->refcount = type ? 1 : 0; tmp->offset = tmp->num = tmp->cur_record = 0; tmp->data = (char*) tmp + sizeof(is_mbuf); @@ -54,19 +75,48 @@ is_mbuf *xmalloc_mbuf(int type) return tmp; } -#if 0 +void xfree_mbuf(is_mbuf *p) +{ + p->next = mbuf_freelist[p->type]; + mbuf_freelist[p->type] = p; +} + +void xfree_mbufs(is_mbuf *l) +{ + is_mbuf *p; + + while (l) + { + p = l->next; + xfree_mbuf(l); + l = p; + } +} + void xfree_mblock(is_mblock *p) { - xfree(p); + xfree_mbufs(p->data); + p->next = mblock_freelist; + mblock_freelist = p; } -#endif -#if 0 -void xfree_mbuf(is_mblock *p) +void xrelease_mblock(is_mblock *p) { - xfree(p); + p->next = mblock_tmplist; + mblock_tmplist = p; +} + +void xfree_mblocks(is_mblock *l) +{ + is_mblock *p; + + while (l) + { + p = l->next; + xfree_mblock(l); + l = p; + } } -#endif void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos) { @@ -97,6 +147,13 @@ void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos) tab->is = is; } +void is_m_release_tab(is_mtable *tab) +{ + xfree_mblocks(tab->data); + xfree_mblocks(mblock_tmplist); + mblock_tmplist = 0; +} + void is_m_rewind(is_mtable *tab) { tab->cur_mblock = tab->data; @@ -234,23 +291,25 @@ void is_m_unread_record(is_mtable *tab) int is_m_peek_record(is_mtable *tab, void *rec) { is_mbuf *mbuf; + is_mblock *mblock; /* make sure block is all in memory */ if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL) if (read_current_full(tab, tab->cur_mblock) < 0) return -1; - mbuf = tab->cur_mblock->cur_mbuf; + mblock = tab->cur_mblock; + mbuf = mblock->cur_mbuf; if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */ { if (!mbuf->next) /* end of mblock */ { - if (tab->cur_mblock->next) + if (mblock->next) { - tab->cur_mblock = tab->cur_mblock->next; - if (tab->cur_mblock->next->state <= IS_MBSTATE_PARTIAL) - if (read_current_full(tab, tab->cur_mblock->next) < 0) + mblock = mblock->next; + if (mblock->state <= IS_MBSTATE_PARTIAL) + if (read_current_full(tab, mblock) < 0) return -1; - mbuf = tab->cur_mblock->next->data; + mbuf = mblock->data; } else return 0; /* EOTable */ diff --git a/isam/memory.h b/isam/memory.h index 2948448..59e726d 100644 --- a/isam/memory.h +++ b/isam/memory.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: memory.h,v $ - * Revision 1.1 1994-09-26 17:12:32 quinn + * Revision 1.2 1994-09-27 20:03:52 quinn + * Seems relatively bug-free. + * + * Revision 1.1 1994/09/26 17:12:32 quinn * Back again * * Revision 1.1 1994/09/26 16:07:57 quinn @@ -15,10 +18,10 @@ #ifndef MEMORY_H #define MEMORY_H -#include - extern int is_mbuf_size[3]; +typedef unsigned int ISAM_P; + /* * Memory buffer. Used to manage records (keys) in memory for * reading and insertion/deletion. @@ -58,6 +61,7 @@ typedef struct is_mblock struct is_mblock *next; /* next diskblock */ } is_mblock; +typedef struct isam_struct *ISAM; /* * Descriptor for a specific table. */ @@ -73,8 +77,12 @@ typedef struct is_mtable is_mblock *xmalloc_mblock(); is_mbuf *xmalloc_mbuf(int type); void xfree_mblock(is_mblock *p); -void xfree_mbuf(is_mblock *p); +void xfree_mblocks(is_mblock *l); +void xfree_mbuf(is_mbuf *p); +void xfree_mbufs(is_mbuf *l); +void xrelease_mblock(is_mblock *p); void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos); +void is_m_release_tab(is_mtable *tab); void is_m_rewind(is_mtable *tab); void is_m_replace_record(is_mtable *tab, const void *rec); int is_m_write_record(is_mtable *tab, const void *rec); diff --git a/isam/physical.c b/isam/physical.c index afb5343..ae1f584 100644 --- a/isam/physical.c +++ b/isam/physical.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: physical.c,v $ - * Revision 1.3 1994-09-26 17:11:31 quinn + * Revision 1.4 1994-09-27 20:03:53 quinn + * Seems relatively bug-free. + * + * Revision 1.3 1994/09/26 17:11:31 quinn * Trivial * * Revision 1.2 1994/09/26 17:06:36 quinn @@ -22,7 +25,6 @@ #include #include -#include "memory.h" static int is_freestore_alloc(ISAM is, int type) { @@ -41,6 +43,7 @@ static int is_freestore_alloc(ISAM is, int type) else tmp = is->types[type].top++; + log(LOG_DEBUG, "Allocating block #%d", tmp); return tmp; } @@ -48,6 +51,7 @@ static void is_freestore_free(ISAM is, int type, int block) { int tmp; + log(LOG_DEBUG, "Releasing block #%d", block); tmp = is->types[type].freelist; is->types[type].freelist = block; if (bf_write(is->types[type].bf, block, 0, sizeof(tmp), &tmp) < 0) @@ -138,6 +142,7 @@ int is_p_read_full(is_mtable *tab, is_mblock *block) block->bread += toread * is_keysize(tab->is); } } + log(LOG_DEBUG, "R: Block #%d contains %d records.", block->diskpos, block->num_records); return 0; } @@ -155,6 +160,13 @@ void is_p_sync(is_mtable *tab) type = &tab->is->types[tab->pos_type]; for (p = tab->data; p; p = p->next) { + int fummy; +/* +if (p->num_records == 0) + fummy = 1/0; +*/ + if (p->state < IS_MBSTATE_DIRTY) + continue; /* make sure that blocks are allocated. */ if (p->diskpos < 0) p->diskpos = is_freestore_alloc(tab->is, tab->pos_type); @@ -166,6 +178,8 @@ void is_p_sync(is_mtable *tab) else p->nextpos = p->next->diskpos; } + else + p->nextpos = 0; sum = 0; memcpy(type->dbuf, &p->num_records, sizeof(p->num_records)); sum += sizeof(p->num_records); @@ -189,6 +203,7 @@ void is_p_sync(is_mtable *tab) log(LOG_FATAL, "Failed to write block."); exit(1); } + log(LOG_DEBUG, "W: Block #%d contains %d records.", p->diskpos, p->num_records); } } @@ -212,6 +227,8 @@ static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize) is_mbuf *p = 0, **pp = &p, *new; int toget = *num; + if (!toget) + return 0; while (*mb && toget >= (*mb)->num) { toget -= (*mb)->num; @@ -246,14 +263,33 @@ static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize) */ void is_p_align(is_mtable *tab) { - is_mblock *mblock, *new; + is_mblock *mblock, *new, *last = 0, *next; is_mbuf *mbufs, *mbp; int blocks, recsblock; log(LOG_DEBUG, "Realigning table."); - for (mblock = tab->data; mblock; mblock = mblock->next) + for (mblock = tab->data; mblock; mblock = next) { - if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records > + next = mblock->next; + if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records == 0) + { + if (last) + { + last->next = mblock->next; + last->state = IS_MBSTATE_DIRTY; + next = mblock->next; + } + else + { + tab->data = tab->data->next; + tab->data->state = IS_MBSTATE_DIRTY; + next = tab->data; + } + if (mblock->diskpos >= 0) + is_freestore_free(tab->is, tab->pos_type, mblock->diskpos); + xrelease_mblock(mblock); + } + else if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records > (mblock == tab->data ? tab->is->types[tab->pos_type].max_keys_block0 : tab->is->types[tab->pos_type].max_keys_block)) @@ -268,18 +304,25 @@ void is_p_align(is_mtable *tab) recsblock = 1; mbufs = mblock->data; while ((mbp = mbuf_takehead(&mbufs, &recsblock, - is_keysize(tab->is)))) + is_keysize(tab->is))) && recsblock) { - new = xmalloc_mblock(); - new->diskpos = -1; - new->state = IS_MBSTATE_DIRTY; - new->next = mblock->next; - mblock->next = new; + if (mbufs) + { + new = xmalloc_mblock(); + new->diskpos = -1; + new->state = IS_MBSTATE_DIRTY; + new->next = mblock->next; + mblock->next = new; + } mblock->data = mbp; mblock->num_records = recsblock; + last = mblock; mblock = mblock->next; } + next = mblock; } + else + last = mblock; } } @@ -300,6 +343,11 @@ void is_p_remap(is_mtable *tab) bufpp = &mbufs; for (blockp = tab->data; blockp; blockp = blockp->next) { + if (blockp->state < IS_MBSTATE_CLEAN && is_m_read_full(tab, blockp) < 0) + { + log(LOG_FATAL, "Read-full failed in remap."); + exit(1); + } *bufpp = blockp->data; while (*bufpp) bufpp = &(*bufpp)->next; @@ -308,11 +356,14 @@ void is_p_remap(is_mtable *tab) blocks = tab->num_records / tab->is->types[tab->pos_type].nice_keys_block; if (tab->num_records % tab->is->types[tab->pos_type].nice_keys_block) blocks++; - recsblock = tab->num_records / blocks; - if (recsblock < 1) - recsblock = 1; + if (blocks == 0) + blocks = 1; + recsblock = tab->num_records / blocks + 1; + if (recsblock > tab->is->types[tab->pos_type].nice_keys_block) + recsblock--; blockpp = &tab->data; - while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is)))) + while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is))) && + recsblock) { if (!*blockpp) { @@ -324,4 +375,14 @@ void is_p_remap(is_mtable *tab) (*blockpp)->state = IS_MBSTATE_DIRTY; blockpp = &(*blockpp)->next; } + if (mbp) + xfree_mbufs(mbp); + if (*blockpp) + { + for (blockp = *blockpp; blockp; blockp = blockp->next) + if (blockp->diskpos >= 0) + is_freestore_free(tab->is, tab->pos_type, blockp->diskpos); + xfree_mblocks(*blockpp); + *blockpp = 0; + } } -- 1.7.10.4