From df82693c96b0691db2508139dea6fc4a03766193 Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Wed, 17 Aug 1994 13:37:40 +0000 Subject: [PATCH] dictionary internal cache modules. --- dict/dclose.c | 20 +++++++ dict/dopen.c | 53 +++++++++++++++++ dict/drdwr.c | 175 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 248 insertions(+) create mode 100644 dict/dclose.c create mode 100644 dict/dopen.c create mode 100644 dict/drdwr.c diff --git a/dict/dclose.c b/dict/dclose.c new file mode 100644 index 0000000..701b0cb --- /dev/null +++ b/dict/dclose.c @@ -0,0 +1,20 @@ +#include +#include +#include +#include +#include + +#include + +int dict_bf_close (Dict_BFile dbf) +{ + int i; + dict_bf_flush_blocks (dbf, -1); + + free (dbf->all_blocks); + free (dbf->all_data); + free (dbf->hash_array); + i = bf_close (dbf->bf); + free (dbf); + return i; +} diff --git a/dict/dopen.c b/dict/dopen.c new file mode 100644 index 0000000..3100088 --- /dev/null +++ b/dict/dopen.c @@ -0,0 +1,53 @@ +#include +#include +#include +#include +#include + +#include + +static void common_init (Dict_BFile bf, int block_size, int cache) +{ + int i; + + bf->cache = cache; + bf->hash_size = 31; + + bf->hits = bf->misses = 0; + + /* Allocate all blocks in one chunk. */ + bf->all_data = xmalloc (block_size * cache); + + /* Allocate and initialize hash array (as empty) */ + bf->hash_array = xmalloc(sizeof(*bf->hash_array) * bf->hash_size); + for (i=bf->hash_size; --i >= 0; ) + bf->hash_array[i] = NULL; + + /* Allocate all block descriptors in one chunk */ + bf->all_blocks = xmalloc (sizeof(*bf->all_blocks) * cache); + + /* Initialize the free list */ + bf->free_list = bf->all_blocks; + for (i=0; iall_blocks[i].h_next = bf->all_blocks+(i+1); + bf->all_blocks[i].h_next = NULL; + + /* Initialize the data for each block. Will never be moved again */ + for (i=0; iall_blocks[i].data = (char*) bf->all_data + i*block_size; + + /* Initialize lru queue */ + bf->lru_back = NULL; + bf->lru_front = NULL; +} + + +Dict_BFile dict_bf_open (const char *name, int block_size, int cache, int rw) +{ + Dict_BFile dbf; + + dbf = xmalloc (sizeof(*dbf)); + dbf->bf = bf_open (name, block_size, rw); + common_init (dbf, block_size, cache); + return dbf; +} diff --git a/dict/drdwr.c b/dict/drdwr.c new file mode 100644 index 0000000..a77e7a1 --- /dev/null +++ b/dict/drdwr.c @@ -0,0 +1,175 @@ +#include +#include +#include +#include +#include +#include +#include + +#include + +static void pr_lru (Dict_BFile bf) +{ + struct Dict_file_block *p; + for (p=bf->lru_back; p; p = p->lru_next) + { + printf (" %d", p->no); + } + printf ("\n"); + fflush (stdout); +} + +static struct Dict_file_block *find_block (Dict_BFile bf, int no) +{ + struct Dict_file_block *p; + + for (p=bf->hash_array[no% bf->hash_size]; p; p=p->h_next) + if (p->no == no) + break; + return p; +} + +static void release_block (Dict_BFile bf, struct Dict_file_block *p) +{ + assert (p); + + /* remove from lru queue */ + if (p->lru_prev) + p->lru_prev->lru_next = p->lru_next; + else + bf->lru_back = p->lru_next; + if (p->lru_next) + p->lru_next->lru_prev = p->lru_prev; + else + bf->lru_back = p->lru_prev; + + /* remove from hash chain */ + *p->h_prev = p->h_next; + if (p->h_next) + p->h_next->h_prev = p->h_prev; + + /* move to list of free blocks */ + p->h_next = bf->free_list; + bf->free_list = p; +} + +void dict_bf_flush_blocks (Dict_BFile bf, int no_to_flush) +{ + struct Dict_file_block *p; + int i; + for (i=0; i != no_to_flush && bf->lru_back; i++) + { + p = bf->lru_back; + if (p->dirty) + bf_write (bf->bf, p->no, p->data); + release_block (bf, p); + } +} + +static struct Dict_file_block *alloc_block (Dict_BFile bf, int no) +{ + struct Dict_file_block *p, **pp; + + if (!bf->free_list) + dict_bf_flush_blocks (bf, 1); + assert (bf->free_list); + p = bf->free_list; + bf->free_list = p->h_next; + p->dirty = 0; + p->no = no; + + /* insert at front in lru chain */ + p->lru_next = NULL; + p->lru_prev = bf->lru_front; + if (bf->lru_front) + bf->lru_front->lru_next = p; + else + bf->lru_back = p; + bf->lru_front = p; + + /* insert in hash chain */ + pp = bf->hash_array + (no % bf->hash_size); + p->h_next = *pp; + p->h_prev = pp; + if (*pp) + (*pp)->h_prev = &p->h_next; + *pp = p; + + return p; +} + +static void move_to_front (Dict_BFile bf, struct Dict_file_block *p) +{ + /* Already at front? */ + if (!p->lru_next) + return ; + + /* Remove */ + if (p->lru_prev) + p->lru_prev->lru_next = p->lru_next; + else + bf->lru_back = p->lru_next; + p->lru_next->lru_prev = p->lru_prev; + + /* Insert at front */ + p->lru_next = NULL; + p->lru_prev = bf->lru_front; + if (bf->lru_front) + bf->lru_front->lru_next = p; + else + bf->lru_back = p; + bf->lru_front = p; +} + +int bf_readp (Dict_BFile bf, int no, void **bufp) +{ + struct Dict_file_block *p; + int i; + if ((p = find_block (bf, no))) + { + *bufp = p->data; + move_to_front (bf, p); + bf->hits++; + return 1; + } + bf->misses++; + p = alloc_block (bf, no); + i = bf_read (bf->bf, no, p->data); + if (i > 0) + { + *bufp = p->data; + return i; + } + release_block (bf, p); + *bufp = NULL; + return i; +} + +int bf_newp (Dict_BFile bf, int no, void **bufp) +{ + struct Dict_file_block *p; + if (!(p = find_block (bf, no))) + p = alloc_block (bf, no); + else + move_to_front (bf, p); + *bufp = p->data; + memset (p->data, 0, bf->bf->block_size); + p->dirty = 1; +#if 0 + printf ("bf_newp of %d:", no); + pr_lru (bf); +#endif + return 1; +} + +int bf_touch (Dict_BFile bf, int no) +{ + struct Dict_file_block *p; + if ((p = find_block (bf, no))) + { + p->dirty = 1; + return 0; + } + return -1; +} + -- 1.7.10.4