From c6c40893444f2288cdea91d30dd92df0f285e67d Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Mon, 26 Sep 1994 16:07:52 +0000 Subject: [PATCH] Most of the functionality in place. --- include/isam.h | 22 +++- isam/Makefile | 6 +- isam/isam.c | 215 +++++++++++++++++++++++++++++++++++-- isam/issh.c | 164 ++++++++++++++++++++++++++++ isam/keyops.h | 18 ++++ isam/memory.c | 315 +++++++++++++++++++++++++++++++++++++++++++++++++++++ isam/physical.c | 321 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ isam/physical.h | 22 ++++ isam/rootblk.c | 49 +++++++++ isam/rootblk.h | 30 ++++++ 10 files changed, 1148 insertions(+), 14 deletions(-) create mode 100644 isam/issh.c create mode 100644 isam/keyops.h create mode 100644 isam/memory.c create mode 100644 isam/physical.c create mode 100644 isam/physical.h create mode 100644 isam/rootblk.c create mode 100644 isam/rootblk.h diff --git a/include/isam.h b/include/isam.h index d9a4d15..dd70f69 100644 --- a/include/isam.h +++ b/include/isam.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.h,v $ - * Revision 1.2 1994-09-14 13:10:35 quinn + * Revision 1.3 1994-09-26 16:08:42 quinn + * Most of the functionality in place. + * + * Revision 1.2 1994/09/14 13:10:35 quinn * Small changes * * Revision 1.1 1994/09/12 08:02:07 quinn @@ -19,6 +22,8 @@ #include #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; @@ -32,9 +37,13 @@ typedef struct isam_blocktype int blocksize; int first_block; /* position of first data block */ int max_keys_block; /* max num of keys per block */ + 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 top; /* first unused block */ + int index; /* placeholder. Always 0. */ + char *dbuf; /* buffer for use in I/O operations */ } isam_blocktype; /* @@ -46,6 +55,7 @@ typedef struct isam_struct int num_types; /* number of block types used */ int writeflag; 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; @@ -57,8 +67,10 @@ typedef struct ispt_struct struct ispt_struct *next; /* freelist */ } ispt_struct, *ISPT; -#define IS_TYPE(x) ((x) & 3)) /* type part of position */ -#define IS_BLOCK(x) ((x >> 2)) /* block # part of position */ +#define is_type(x) ((x) & 3) /* type part of position */ +#define is_block(x) ((x) >> 2) /* block # part of position */ + +#define is_keysize(is) ((is)->keysize) /* * Public Prototypes. @@ -91,4 +103,8 @@ void is_pt_free(ISPT ip); */ int is_readkey(ISPT ip, void *buf); +int is_writekey(ISPT ip, const void *buf); + +ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data); + #endif diff --git a/isam/Makefile b/isam/Makefile index 3be9079..1081028 100644 --- a/isam/Makefile +++ b/isam/Makefile @@ -3,7 +3,7 @@ INCLUDE=-I../include CFLAGS=-g -Wall -pedantic DEFS=$(INCLUDE) LIB=../lib/isam.a -PO = isam.o isutil.o rootblk.o memory.o +PO = isam.o isutil.o rootblk.o memory.o physical.o CPP=cc -E all: $(LIB) @@ -12,6 +12,10 @@ isam-test: isam-test.c $(LIB) $(CC) -g -o isam-test -I../include isam-test.c \ ../lib/isam.a ../lib/bfile.a ../lib/util.a +issh: issh.c $(LIB) + $(CC) -g -o issh -I../include issh.c \ + ../lib/isam.a ../lib/bfile.a ../lib/util.a + #$(TPROG): $(TPROG).o $(LIB) # $(CC) -o $(TPROG) $(TPROG).o $(LIB) diff --git a/isam/isam.c b/isam/isam.c index 7794ede..ad2f90c 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.1 1994-09-12 08:02:13 quinn + * Revision 1.2 1994-09-26 16:07:53 quinn + * Most of the functionality in place. + * + * Revision 1.1 1994/09/12 08:02:13 quinn * Not functional yet * */ @@ -15,9 +18,13 @@ #include #include "isutil.h" +#include "rootblk.h" #include #include #include +#include "memory.h" +#include "physical.h" +#include "keyops.h" static int splitargs(const char *s, char *bf[], int max) { @@ -50,10 +57,13 @@ ISAM is_open(const char *name, int writeflag) ISAM new; char *nm, *r, *pp[IS_MAX_BLOCKTYPES+1], m[2]; int num, size, rs, tmp, i; + is_type_header th; log(LOG_DEBUG, "is_open(%s, %s)", name, writeflag ? "RW" : "RDONLY"); new = xmalloc(sizeof(*new)); new->writeflag = writeflag; + for (i = 0; i < IS_MAX_BLOCKTYPES; i++) + new->types[i].index = 0; /* dummy */ /* determine number and size of blocktypes */ if (!(r = res_get(common_resource, nm = strconcat(name, ".", @@ -84,6 +94,7 @@ ISAM is_open(const char *name, int writeflag) log(LOG_FATAL, "Illegal size suffix: %c", *m); return 0; } + new->types[i].dbuf = xmalloc(new->types[i].blocksize); m[0] = 'A' + i; m[1] = '\0'; if (!(new->types[i].bf = bf_open(strconcat(name, m, 0), @@ -92,16 +103,57 @@ ISAM is_open(const char *name, int writeflag) log(LOG_FATAL, "bf_open failed"); return 0; } + if ((rs = is_rb_read(&new->types[i], &th)) > 0) + { + if (th.blocksize != new->types[i].blocksize) + { + log(LOG_FATAL, "File blocksize mismatch in %s", name); + exit(1); + } + new->types[i].freelist = th.freelist; + new->types[i].top = th.top; + } + else if (writeflag) /* write dummy superblock to determine top */ + { + if ((rs = is_rb_write(&new->types[i], &th)) <=0) /* dummy */ + { + log(LOG_FATAL, "Failed to write initial superblock."); + exit(1); + } + new->types[i].freelist = -1; + new->types[i].top = rs; + } + /* ELSE: this is an empty file opened in read-only mode. */ + } + if (!(r = res_get_def(common_resource, nm = strconcat(name, ".", "keysize", + 0), "4"))) + { + log(LOG_FATAL, "Failed to locate resource %s", nm); + return 0; + } + if ((new->keysize = atoi(r)) <= 0) + { + log(LOG_FATAL, "Must specify positive keysize."); + return 0; } - /* determine nice fill rates */ + /* determine repack percent */ + if (!(r = res_get_def(common_resource, nm = strconcat(name, ".", "repack", + 0), IS_DEF_REPACK_PERCENT))) + { + log(LOG_FATAL, "Failed to locate resource %s", nm); + return 0; + } + new->repack = atoi(r); + + /* determine max keys/blocksize */ if (!(r = res_get(common_resource, nm = strconcat(name, ".", - "nicefill", 0))) || !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES))) + "maxkeys", 0))) || !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES))) { log(LOG_FATAL, "Failed to locate resource %s", nm); return 0; } - if (num < new->num_types) + if (num < new->num_types -1) { log(LOG_FATAL, "Not enough elements in %s", nm); return 0; @@ -113,17 +165,37 @@ ISAM is_open(const char *name, int writeflag) log(LOG_FATAL, "Error in resource %s: %s", r, pp[i]); return 0; } - new->types[i].nice_keys_block = tmp; + new->types[i].max_keys = tmp; } - /* determine max keys/blocksize */ + /* determine max keys/block */ + for (i = 0; i < new->num_types; i++) + { + if (!new->types[i].index) + { + new->types[i].max_keys_block = (new->types[i].blocksize - 2 * + sizeof(int)) / new->keysize; + new->types[i].max_keys_block0 = (new->types[i].blocksize - 3 * + sizeof(int)) / new->keysize; + } + else + new->types[i].max_keys_block = new->types[i].max_keys_block0 / + new->keysize; + if (new->types[i].max_keys_block0 < 1) + { + log(LOG_FATAL, "Blocksize too small in %s", name); + exit(1); + } + } + + /* determine nice fill rates */ if (!(r = res_get(common_resource, nm = strconcat(name, ".", - "maxkeys", 0))) || !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES))) + "nicefill", 0))) || !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES))) { log(LOG_FATAL, "Failed to locate resource %s", nm); return 0; } - if (num < new->num_types -1) + if (num < new->num_types) { log(LOG_FATAL, "Not enough elements in %s", nm); return 0; @@ -135,8 +207,13 @@ ISAM is_open(const char *name, int writeflag) log(LOG_FATAL, "Error in resource %s: %s", r, pp[i]); return 0; } - new->types[i].max_keys = tmp; + new->types[i].nice_keys_block = (new->types[i].max_keys_block0 * tmp) / + 100; + if (new->types[i].nice_keys_block < 1) + new->types[i].nice_keys_block = 1; } + + new->cmp = is_default_cmp; return new; } @@ -145,8 +222,126 @@ ISAM is_open(const char *name, int writeflag) */ int is_close(ISAM is) { + int i; + is_type_header th; + log(LOG_DEBUG, "is_close()"); - log(LOG_LOG, "is_close needs to close individual files."); + for (i = 0; i < is->num_types; i++) + { + if (is->types[i].bf) + { + if (is->writeflag) + { + th.blocksize = is->types[i].blocksize; + th.keysize = is->keysize; + th.freelist = is->types[i].freelist; + th.top = is->types[i].top; + if (is_rb_write(&is->types[i], &th) < 0) + { + log(LOG_FATAL, "Failed to write headerblock"); + exit(1); + } + } + bf_close(is->types[i].bf); + } + } xfree(is); return 0; } + +static ISAM_P is_address(int type, int pos) +{ + ISAM_P r; + + r = pos << 2; + r |= type; + return r; +} + +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; + char operation, *record; + + is_m_establish_tab(is, &tab, pos); + /* TODO: do something to aquire oldnum at this point */ + if (pos) + if (is_m_read_full(&tab, tab.data) < 0) + { + log(LOG_FATAL, "read_full failed"); + exit(1); + } + oldnum = tab.num_records; + oldtype = tab.pos_type; + while (num) + { + operation = *(data)++; + record = (char*)data; + data += is_keysize(is); + num--; + while (num && !memcmp(record, data, is_keysize(tab.is) + 1)) + { + data += 1 + is_keysize(is); + num--; + } + if ((res = is_m_seek_record(&tab, record)) > 0) /* no match */ + { + if (operation == KEYOP_INSERT) + { + log(LOG_DEBUG, "XXInserting new record."); + is_m_write_record(&tab, record); + } + else + log(LOG_DEBUG, "XXDeletion failed to find match."); + } + else /* match found */ + { + if (operation == KEYOP_INSERT) + { + log(LOG_DEBUG, "XXSkipping insertion - match found."); + continue; + } + else if (operation == KEYOP_DELETE) + { + /* try to avoid needlessly moving data */ + if (num && *(data) == KEYOP_INSERT) + { + /* next key is identical insert? - NOOP - skip it */ + if (!memcmp(record, data + 1, is_keysize(is))) + { + log(LOG_DEBUG, "XXNoop delete. skipping."); + data += 1 + is_keysize(is); + num--; + continue; + } + /* else check if next key can fit in this position */ + is_m_peek_record(&tab, keybuf); + res = (*is->cmp)(data + 1, keybuf); + if (res < 0) + { + log(LOG_DEBUG, "XXReplacing record."); + is_m_replace_record(&tab, data + 1); + data += 1 + is_keysize(is); + num--; + continue; + } + } + log(LOG_DEBUG, "Deleting record."); + is_m_delete_record(&tab); + } + } + } + while (tab.pos_type < tab.is->num_types - 1 && tab.num_records > + tab.is->types[tab.pos_type].max_keys) + tab.pos_type++; + 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); +} diff --git a/isam/issh.c b/isam/issh.c new file mode 100644 index 0000000..0b5fb8b --- /dev/null +++ b/isam/issh.c @@ -0,0 +1,164 @@ +#include +#include +#include +#include + +#include +#include + +static ISAM is = 0; + +int c_open(char *p); +int c_close(char *p); +int c_write(char *p); +int c_merge(char *p); +int c_rewind(char *p); +int c_read(char *p); +int c_exit(char *p); +int c_help(char *p); +int c_list(char *p); +int c_pos(char *p); + +struct +{ + char *word; + int (*fun)(char *p); +} cmdl[] = +{ + {"open", c_open}, + {"close", c_close}, + {"write", c_write}, + {"merge", c_merge}, + {"rewind", c_rewind}, + {"read", c_read}, + {"exit", c_exit}, + {"quit", c_exit}, + {"help", c_help}, + {"list", 0}, + {"pos", c_pos}, + + {0,0} +}; + + +int c_pos(char *p) +{ +} + +int c_open(char *p) +{ + if (!*p) + { + printf("Usage: open name\n"); + return -1; + } + if (!(is = is_open(p, 1))) + return -1; + return 0; +} + +int c_close(char *p) +{ + if (!is) + { + printf("Open first.\n"); + return -1; + } + is_close(is); + return 0; +} + +int c_write(char *p) {} + +int c_merge(char *p) +{ + char line[100], buf[1024], ch; + int pos = 0, num = 0; + int op, key; + int val; + + if (!is) + { + printf("Open first.\n"); + return -1; + } + if (!sscanf(p, "%d", &val)) + { + printf("Usage: merge
\n"); + return -1; + } + printf("Enter pairs of . Terminate with '.'\n"); + while (gets(line) && *line != '.') + { + if (sscanf(line, "%d %d", &op, &key) < 2) + { + printf("Error in input\n"); + return -1; + } + ch = op; + *(buf + pos++) = ch; + memcpy(buf + pos, &key, sizeof(key)); + pos += sizeof(key); + num++; + } + printf("is_merge(-->%d) returns: %d\n", val, is_merge(is, val, num , buf)); + return 0; +} + +int c_rewind(char *p) +{ + if (!is) + { + printf("Open first.\n"); + return -1; + } +} + +int c_read(char *p) {} + +int c_exit(char *p) +{ + exit(0); +} + +int c_help(char *p) +{ + int i; + + printf("ISSH: ISAM debugging shell.\n"); + printf("Commands:\n"); + for (i = 0; cmdl[i].word; i++) + printf(" %s %s\n", cmdl[i].word, cmdl[i].fun ? "": "UNDEFINED"); + return 0; +} + +int main() +{ + char line[1024]; + static char word[1024] = "help", arg[1024] = ""; + int i; + + log_init(LOG_ALL, "issh", 0); + + assert(common_resource = res_open("testres")); + + + for (;;) + { + printf("ISSH> "); + fflush(stdout); + if (!gets(line)) + return 0; + *arg = '\0'; + if (*line && sscanf(line, "%s %[^;]", word, arg) < 1) + abort(); + for (i = 0; cmdl[i].word; i++) + if (!strncmp(cmdl[i].word, word, strlen(word))) + { + printf("%s\n", (*cmdl[i].fun)(arg) == 0 ? "OK" : "FAILED"); + break; + } + if (!cmdl[i].word) + (*c_help)(""); + } +} diff --git a/isam/keyops.h b/isam/keyops.h new file mode 100644 index 0000000..3b8476f --- /dev/null +++ b/isam/keyops.h @@ -0,0 +1,18 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: keyops.h,v $ + * Revision 1.1 1994-09-26 16:07:55 quinn + * Most of the functionality in place. + * + */ + +#ifndef KEYOPS_H +#define KEYOPS_H + +#define KEYOP_DELETE 0 +#define KEYOP_INSERT 1 + +#endif diff --git a/isam/memory.c b/isam/memory.c new file mode 100644 index 0000000..13be94b --- /dev/null +++ b/isam/memory.c @@ -0,0 +1,315 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: memory.c,v $ + * Revision 1.1 1994-09-26 16:07:56 quinn + * Most of the functionality in place. + * + */ + +/* + * This module accesses and rearranges the records of the tables. + */ + +#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. + */ + +is_mblock *xmalloc_mblock() +{ + is_mblock *tmp; + + tmp = xmalloc(sizeof(is_mblock)); + tmp->next = 0; + return tmp; +} + +is_mbuf *xmalloc_mbuf(int type) +{ + is_mbuf *tmp; + + 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); + tmp->next = 0; + return tmp; +} + +#if 0 +void xfree_mblock(is_mblock *p) +{ + xfree(p); +} +#endif + +#if 0 +void xfree_mbuf(is_mblock *p) +{ + xfree(p); +} +#endif + +void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos) +{ + tab->data = xmalloc_mblock(); + if (pos > 0) + { + tab->pos_type = is_type(pos); + tab->num_records = -1; + tab->data->num_records = -1; + tab->data->diskpos = is_block(pos); + tab->data->state = IS_MBSTATE_UNREAD; + tab->data->data = 0; + tab->cur_mblock = tab->data; + tab->cur_mblock->cur_mbuf = 0; + } + else /* new block */ + { + tab->pos_type = 0; + tab->num_records = 0; + tab->data->num_records = 0; + tab->data->diskpos = -1; + tab->data->state = IS_MBSTATE_CLEAN; + tab->data->data = xmalloc_mbuf(IS_MBUF_TYPE_LARGE); + tab->cur_mblock = tab->data; + tab->cur_mblock->cur_mbuf = tab->data->data; + tab->cur_mblock->cur_mbuf->cur_record = 0; + } + tab->is = is; +} + +void is_m_rewind(is_mtable *tab) +{ + tab->cur_mblock = tab->data; + if (tab->data) + { + tab->data->cur_mbuf = tab->data->data; + if (tab->data->data) + tab->data->data->cur_record = 0; + } +} + +static int read_current_full(is_mtable *tab, is_mblock *mblock) +{ + if (is_p_read_full(tab, mblock) < 0) + return -1; + if (mblock->nextpos && !mblock->next) + { + mblock->next = xmalloc_mblock(); + mblock->next->diskpos = mblock->nextpos; + mblock->next->state = IS_MBSTATE_UNREAD; + mblock->next->data = 0; + } + mblock->cur_mbuf = mblock->data; + mblock->data->cur_record = 0; + return 0; +} + +int is_m_read_full(is_mtable *tab, is_mblock *mblock) +{ + return read_current_full(tab, mblock); +} + +/* + * replace the record right behind the pointer. + */ +void is_m_replace_record(is_mtable *tab, const void *rec) +{ + is_mbuf *mbuf = tab->cur_mblock->cur_mbuf; + + /* we assume that block is already in memory and that we are in the + * right mbuf, and that it has space for us. */ + memcpy(mbuf->data + mbuf->offset + (mbuf->cur_record - 1) * + is_keysize(tab->is), rec, is_keysize(tab->is)); + tab->cur_mblock->state = IS_MBSTATE_DIRTY; +} + +/* + * Delete the record right behind the pointer. + */ +void is_m_delete_record(is_mtable *tab) +{ + is_mbuf *mbuf, *new; + + mbuf = tab->cur_mblock->cur_mbuf; + if (mbuf->cur_record >= mbuf->num) /* top of mbuf */ + { + mbuf->num--; + mbuf->cur_record--; + } + else /* middle of a block */ + { + new = xmalloc_mbuf(IS_MBUF_TYPE_SMALL); + new->next = mbuf->next; + mbuf->next = new; + new->data = mbuf->data; + mbuf->refcount++; + new->offset = mbuf->offset + mbuf->cur_record * is_keysize(tab->is); + new->num = mbuf->num - mbuf->cur_record; + mbuf->num = mbuf->cur_record -1; + mbuf = mbuf->next; + mbuf->cur_record = 0; + } + tab->num_records--; + tab->cur_mblock->num_records--; + tab->cur_mblock->state = tab->data->state = IS_MBSTATE_DIRTY; +} + +int is_m_write_record(is_mtable *tab, const void *rec) +{ + is_mbuf *mbuf, *oldnext, *dmbuf; + + /* 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; + if (mbuf->cur_record >= mbuf->num) /* top of mbuf */ + { + /* mbuf is reference or full */ + if (mbuf->refcount != 1 || mbuf->offset + (mbuf->num + 1) * + is_keysize(tab->is) > is_mbuf_size[mbuf->type]) + { + oldnext = mbuf->next; + mbuf->next = xmalloc_mbuf(IS_MBUF_TYPE_LARGE); + mbuf->next->next = oldnext; + mbuf = mbuf->next; + tab->cur_mblock->cur_mbuf = mbuf; + mbuf->cur_record = 0; + } + } + else + { + oldnext = mbuf->next; + mbuf->next = xmalloc_mbuf(IS_MBUF_TYPE_MEDIUM); + mbuf->next->next = dmbuf = xmalloc_mbuf(IS_MBUF_TYPE_SMALL); + dmbuf->data = mbuf->data; + dmbuf->next = oldnext; + dmbuf->offset = mbuf->offset + mbuf->cur_record * is_keysize(tab->is); + dmbuf->num = mbuf->num - mbuf->cur_record; + mbuf->num -= dmbuf->num; + mbuf->refcount++; + mbuf = tab->cur_mblock->cur_mbuf = mbuf->next; + mbuf->cur_record = 0; + } + log(LOG_DEBUG, "is_m_write_rec(rec == %d)", mbuf->cur_record); + memcpy(mbuf->data + mbuf->offset + mbuf->cur_record * is_keysize(tab->is), + rec, is_keysize(tab->is)); + mbuf->num++; + mbuf->cur_record++; + tab->num_records++; + tab->cur_mblock->num_records++; + tab->cur_mblock->state = tab->data->state = IS_MBSTATE_DIRTY; + return 0; +} + +void is_m_unread_record(is_mtable *tab) +{ + assert(tab->cur_mblock->cur_mbuf->cur_record); + tab->cur_mblock->cur_mbuf->cur_record--; +} + +/* + * non-destructive read. + */ +int is_m_peek_record(is_mtable *tab, void *rec) +{ + is_mbuf *mbuf; + + /* 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; + if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */ + { + if (!mbuf->next) /* end of mblock */ + { + if (tab->cur_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) + return -1; + mbuf = tab->cur_mblock->next->data; + } + else + return 0; /* EOTable */ + } + else + mbuf = mbuf->next; + mbuf->cur_record = 0; + } + memcpy(rec, mbuf->data + mbuf->offset + mbuf->cur_record * + is_keysize(tab->is), is_keysize(tab->is)); + return 1; +} + +int is_m_read_record(is_mtable *tab, void *buf) +{ + is_mbuf *mbuf; + + /* 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; + if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */ + { + if (!mbuf->next) /* end of mblock */ + { + if (tab->cur_mblock->next) + { + tab->cur_mblock = tab->cur_mblock->next; + if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL) + if (read_current_full(tab, tab->cur_mblock) < 0) + return -1; + tab->cur_mblock->cur_mbuf = mbuf = tab->cur_mblock->data; + } + else + return 0; /* EOTable */ + } + else + tab->cur_mblock->cur_mbuf = mbuf = mbuf->next; + mbuf->cur_record = 0; + } + memcpy(buf, mbuf->data + mbuf->offset + mbuf->cur_record * + is_keysize(tab->is), is_keysize(tab->is)); + mbuf->cur_record++; + return 1; +} + +/* + * TODO: optimize this function by introducing a higher-level search. + */ +int is_m_seek_record(is_mtable *tab, const void *rec) +{ + char peek[IS_MAX_RECORD]; + int rs; + + for (;;) + { + if (is_m_read_record(tab, &peek) <= 0) + return 1; + if ((rs = (*tab->is->cmp)(peek, rec)) > 0) + { + is_m_unread_record(tab); + return 1; + } + else if (rs == 0) + return 0; + } +} diff --git a/isam/physical.c b/isam/physical.c new file mode 100644 index 0000000..d188a2b --- /dev/null +++ b/isam/physical.c @@ -0,0 +1,321 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: physical.c,v $ + * Revision 1.1 1994-09-26 16:07:57 quinn + * Most of the functionality in place. + * + */ + +/* + * This module handles the representation of tables in the bfiles. + */ + +#include + +#include +#include "memory.h" + +static int is_freestore_alloc(ISAM is, int type) +{ + int tmp; + + if (is->types[type].freelist >= 0) + { + tmp = is->types[type].freelist; + if (bf_read(is->types[type].bf, tmp, 0, sizeof(tmp), + &is->types[type].freelist) <=0) + { + log(LOG_FATAL, "Failed to allocate block"); + exit(1); + } + } + else + tmp = is->types[type].top++; + + return tmp; +} + +static void is_freestore_free(ISAM is, int type, int block) +{ + int tmp; + + tmp = is->types[type].freelist; + is->types[type].freelist = block; + if (bf_write(is->types[type].bf, block, 0, sizeof(tmp), &tmp) < 0) + { + log(LOG_FATAL, "Failed to deallocate block."); + exit(1); + } +} + +/* this code must be modified to handle an index */ +int is_p_read_partial(is_mtable *tab, is_mblock *block) +{ + int toread; + is_mbuf *buf; + + assert(block->state == IS_MBSTATE_UNREAD); + block->data = buf = xmalloc_mbuf(IS_MBUF_TYPE_LARGE); + toread = tab->is->types[tab->pos_type].blocksize; + if (toread > is_mbuf_size[buf->type]) + { + toread = is_mbuf_size[buf->type]; + block->state = IS_MBSTATE_PARTIAL; + } + else + block->state = IS_MBSTATE_CLEAN; + if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, 0, toread, + buf->data) < 0) + { + log(LOG_FATAL, "bfread failed."); + return -1; + } + /* extract header info */ + buf->offset = 0; + memcpy(&block->num_records, buf->data, sizeof(block->num_records)); + buf->offset += sizeof(block->num_records); + memcpy(&block->nextpos, buf->data + buf->offset, + sizeof(block->nextpos)); + buf->offset += sizeof(block->nextpos); + if (block == tab->data) /* first block */ + { + memcpy(&tab->num_records, buf->data + buf->offset, + sizeof(tab->num_records)); + buf->offset +=sizeof(tab->num_records); + } + buf->num = (toread - buf->offset) / is_keysize(tab->is); + if (buf->num >= block->num_records) + { + buf->num = block->num_records; + block->state = IS_MBSTATE_CLEAN; + } + else + block->bread = buf->num * is_keysize(tab->is); + return 0; +} + +int is_p_read_full(is_mtable *tab, is_mblock *block) +{ + is_mbuf *buf; + int dread, toread; + + if (block->state == IS_MBSTATE_UNREAD && is_p_read_partial(tab, block) < 0) + { + log(LOG_FATAL, "partial read failed."); + return -1; + } + if (block->state == IS_MBSTATE_PARTIAL) + { + buf = block->data; + dread = block->data->num; + while (dread < block->num_records) + { + buf->next = xmalloc_mbuf(IS_MBUF_TYPE_LARGE); + buf = buf->next; + + toread = is_mbuf_size[buf->type] / is_keysize(tab->is); + if (toread > block->num_records - dread) + toread = block->num_records - dread; + + if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, block->bread, toread * + is_keysize(tab->is), buf->data) < 0) + { + log(LOG_FATAL, "bfread failed."); + return -1; + } + buf->offset = 0; + buf->num = toread; + dread += toread; + block->bread += toread * is_keysize(tab->is); + } + } + return 0; +} + +/* + * write dirty blocks to bfile. + * Allocate blocks as necessary. + */ +void is_p_sync(is_mtable *tab) +{ + is_mblock *p; + is_mbuf *b; + int sum, v; + isam_blocktype *type; + + type = &tab->is->types[tab->pos_type]; + for (p = tab->data; p; p = p->next) + { + /* make sure that blocks are allocated. */ + if (p->diskpos < 0) + p->diskpos = is_freestore_alloc(tab->is, tab->pos_type); + if (p->next) + { + if (p->next->diskpos < 0) + p->nextpos = p->next->diskpos = is_freestore_alloc(tab->is, + tab->pos_type); + else + p->nextpos = p->next->diskpos; + } + sum = 0; + memcpy(type->dbuf, &p->num_records, sizeof(p->num_records)); + sum += sizeof(p->num_records); + memcpy(type->dbuf + sum, &p->nextpos, sizeof(p->nextpos)); + sum += sizeof(p->nextpos); + if (p == tab->data) /* first block */ + { + memcpy(type->dbuf + sum, &tab->num_records, + sizeof(tab->num_records)); + sum += sizeof(tab->num_records); + } + for (b = p->data; b; b = b->next) + { + memcpy(type->dbuf + sum, b->data + b->offset, v = b->num * + is_keysize(tab->is)); + sum += v; + assert(sum <= type->blocksize); + } + if (bf_write(type->bf, p->diskpos, 0, sum, type->dbuf) < 0) + { + log(LOG_FATAL, "Failed to write block."); + exit(1); + } + } +} + +/* + * Free all disk blocks associated with table. + */ +void is_p_unmap(is_mtable *tab) +{ + is_mblock *p; + + for (p = tab->data; p; p = p->next) + if (p->diskpos >= 0) + { + is_freestore_free(tab->is, tab->pos_type, p->diskpos); + p->diskpos = -1; + } +} + +static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize) +{ + is_mbuf *p = 0, **pp = &p, *new; + int toget = *num; + + while (*mb && toget >= (*mb)->num) + { + toget -= (*mb)->num; + *pp = *mb; + *mb = (*mb)->next; + (*pp)->next = 0; + pp = &(*pp)->next; + } + if (toget > 0 && *mb) + { + new = xmalloc_mbuf(IS_MBUF_TYPE_SMALL); + new->next = (*mb)->next; + (*mb)->next = new; + new->data = (*mb)->data; + (*mb)->refcount++; + new->offset = (*mb)->offset + toget * keysize; + new->num = (*mb)->num - toget; + (*mb)->num = toget; + *pp = *mb; + *mb = (*mb)->next; + (*pp)->next = 0; + toget = 0; + } + *num -= toget; + return p; +} + +/* + * Split up individual blocks which have grown too large. + * is_p_align and is_p_remap are alternative functions which trade off + * speed in updating versus optimum usage of disk blocks. + */ +void is_p_align(is_mtable *tab) +{ + is_mblock *mblock, *new; + is_mbuf *mbufs, *mbp; + int blocks, recsblock; + + log(LOG_DEBUG, "Realigning table."); + for (mblock = tab->data; mblock; mblock = mblock->next) + { + 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)) + { + 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; + mbufs = mblock->data; + while ((mbp = mbuf_takehead(&mbufs, &recsblock, + is_keysize(tab->is)))) + { + 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; + mblock = mblock->next; + } + } + } +} + +/* + * Reorganize data in blocks for minimum block usage and quick access. + * Free surplus blocks. + * is_p_align and is_p_remap are alternative functions which trade off + * speed in updating versus optimum usage of disk blocks. + */ +void is_p_remap(is_mtable *tab) +{ + is_mbuf *mbufs, **bufpp, *mbp; + is_mblock *blockp, **blockpp; + int recsblock, blocks; + + log(LOG_DEBUG, "Remapping table."); + /* collect all data */ + bufpp = &mbufs; + for (blockp = tab->data; blockp; blockp = blockp->next) + { + *bufpp = blockp->data; + while (*bufpp) + bufpp = &(*bufpp)->next; + blockp->data = 0; + } + 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; + blockpp = &tab->data; + while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is)))) + { + if (!*blockpp) + { + *blockpp = xmalloc_mblock(); + (*blockpp)->diskpos = -1; + } + (*blockpp)->data = mbp; + (*blockpp)->num_records = recsblock; + (*blockpp)->state = IS_MBSTATE_DIRTY; + blockpp = &(*blockpp)->next; + } +} diff --git a/isam/physical.h b/isam/physical.h new file mode 100644 index 0000000..5e9cd54 --- /dev/null +++ b/isam/physical.h @@ -0,0 +1,22 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: physical.h,v $ + * Revision 1.1 1994-09-26 16:07:59 quinn + * Most of the functionality in place. + * + */ + +#ifndef PHYSICAL_H +#define PHYSICAL_H + +void is_p_sync(is_mtable *tab); +void is_p_unmap(is_mtable *tab); +void is_p_align(is_mtable *tab); +void is_p_remap(is_mtable *tab); +int is_p_read_partial(is_mtable *tab, is_mblock *block); +int is_p_read_full(is_mtable *tab, is_mblock *block); + +#endif diff --git a/isam/rootblk.c b/isam/rootblk.c new file mode 100644 index 0000000..25c1a82 --- /dev/null +++ b/isam/rootblk.c @@ -0,0 +1,49 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: rootblk.c,v $ + * Revision 1.1 1994-09-26 16:08:00 quinn + * Most of the functionality in place. + * + */ + +/* + * Read and write the blocktype header. + */ + +#include +#include "rootblk.h" + +int is_rb_write(isam_blocktype *ib, is_type_header *hd) +{ + int pt = 0, ct = 0, towrite; + + while ((towrite = sizeof(*hd) - pt) > 0) + { + if (towrite > bf_blocksize(ib->bf)) + towrite = bf_blocksize(ib->bf); + if (bf_write(ib->bf, ct, 0, towrite, (char *)hd + pt) < 0) + return -1; + pt += bf_blocksize(ib->bf); + ct++; + } + return ct; +} + +int is_rb_read(isam_blocktype *ib, is_type_header *hd) +{ + int pt = 0, ct = 0, rs, toread; + + while ((toread = sizeof(*hd) - pt) > 0) + { + if (toread > bf_blocksize(ib->bf)) + toread = bf_blocksize(ib->bf); + if ((rs = bf_read(ib->bf, ct, 0, toread, (char*)hd + pt)) <= 0) + return rs; + pt += bf_blocksize(ib->bf); + ct++; + } + return ct; +} diff --git a/isam/rootblk.h b/isam/rootblk.h new file mode 100644 index 0000000..a7499cb --- /dev/null +++ b/isam/rootblk.h @@ -0,0 +1,30 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: rootblk.h,v $ + * Revision 1.1 1994-09-26 16:08:00 quinn + * Most of the functionality in place. + * + */ + +#ifndef ROOTBLK_H +#define ROOTBLK_H + +#include + +typedef struct is_type_header +{ + int blocksize; /* for sanity-checking */ + int keysize; /* -do- */ + int freelist; /* first free block */ + int top; /* first unused block */ +} is_type_header; + + + +int is_rb_write(isam_blocktype *ib, is_type_header *hd); +int is_rb_read(isam_blocktype *ib, is_type_header *hd); + +#endif -- 1.7.10.4