dictionary internal cache modules.

diff --git a/dict/dclose.c b/dict/dclose.c
new file mode 100644 (file)
index 0000000..701b0cb
--- /dev/null
+++ b/dict/dclose.c
@@ -0,0 +1,20 @@
+#include <sys/types.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <dict.h>
+
+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 (file)
index 0000000..3100088
--- /dev/null
+++ b/dict/dopen.c
@@ -0,0 +1,53 @@
+#include <sys/types.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <dict.h>
+
+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; i<cache-1; i++)
+        bf->all_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; i<cache; i++)
+        bf->all_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 (file)
index 0000000..a77e7a1
--- /dev/null
+++ b/dict/drdwr.c
@@ -0,0 +1,175 @@
+#include <sys/types.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <dict.h>
+
+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;
+}
+