aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org>2021-01-03 12:57:59 +0200
committerSergey Poznyakoff <gray@gnu.org>2021-01-03 12:57:59 +0200
commita6f1b4142dd4e811a2c0228d2e96efab81a204e0 (patch)
treedbaa3f49e5a6c5ad3f71082ba3dc5c695debe0ad
parentf6072091fe3049768fa0c3a8a19a7ba4e4901d49 (diff)
downloadgdbm-a6f1b4142dd4e811a2c0228d2e96efab81a204e0.tar.gz
gdbm-a6f1b4142dd4e811a2c0228d2e96efab81a204e0.tar.bz2
Switch cache from RBT to sorted index array.
* src/cachetree.c: Remove. * src/Makefile.am: Remove cachetree.c * src/bucket.c (cache_idx_lookup): New function. (cache_elem_free): Remove index entry. (cache_lookup): Rewrite. (_gdbm_cache_init): Set up cache_storage, cache_idx and cache_avail. (_gdbm_cache_free): Free allocated memory. * src/gdbmdefs.h (cache_elem): Change ca_bucket type to a pointer. (cache_tree): Remove typedef. (gdbm_file_info): Replace cache_tree with cache_storage and cache_idx, * src/gdbmopen.c (gdbm_fd_open): Rempve cache_tree. * src/proto.h: Remove cachetree prototypes. * src/recover.c (_gdbm_finish_transfer): Copy cache_storage and cache_idx.
-rw-r--r--configure.ac1
-rw-r--r--src/Makefile.am1
-rw-r--r--src/bucket.c206
-rw-r--r--src/cachetree.c486
-rw-r--r--src/gdbmdefs.h22
-rw-r--r--src/gdbmopen.c1
-rw-r--r--src/proto.h15
-rw-r--r--src/recover.c3
8 files changed, 122 insertions, 613 deletions
diff --git a/configure.ac b/configure.ac
index 4d956d9..1b84971 100644
--- a/configure.ac
+++ b/configure.ac
@@ -16,7 +16,6 @@
m4_define([_GDBM_VERSION_MAJOR], 1)
m4_define([_GDBM_VERSION_MINOR], 19)
-m4_dnl m4_define([_GDBM_VERSION_PATCH], 0)
AC_INIT([gdbm],
_GDBM_VERSION_MAJOR._GDBM_VERSION_MINOR[]m4_ifdef([_GDBM_VERSION_PATCH],._GDBM_VERSION_PATCH),
diff --git a/src/Makefile.am b/src/Makefile.am
index 25b0a1f..71e6ee0 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -41,7 +41,6 @@ lib_LTLIBRARIES = libgdbm.la
libgdbm_la_LIBADD = @LTLIBINTL@
libgdbm_la_SOURCES = \
- cachetree.c\
gdbmclose.c\
gdbmcount.c\
gdbmdelete.c\
diff --git a/src/bucket.c b/src/bucket.c
index 675bf32..bcd4be2 100644
--- a/src/bucket.c
+++ b/src/bucket.c
@@ -111,50 +111,54 @@ lru_unlink_elem (GDBM_FILE dbf, cache_elem *elem)
elem->ca_prev = elem->ca_next = NULL;
}
-/* Creates and returns new cache element for DBF. The element is initialized,
- but not linked to the LRU list.
- Return NULL on error.
-*/
-static cache_elem *
-cache_elem_new (GDBM_FILE dbf, off_t adr)
-{
- cache_elem *elem;
+enum
+ {
+ elem_failure = -1,
+ elem_new,
+ elem_found
+ };
- elem = dbf->cache_avail;
- if (elem)
+int
+cache_idx_lookup (GDBM_FILE dbf, off_t adr, size_t *idx)
+{
+ if (dbf->cache_num == 0)
{
- dbf->cache_avail = elem->ca_next;
+ *idx = 0;
}
else
{
- elem = calloc (1,
- sizeof (*elem) -
- sizeof (elem->ca_bucket[0]) +
- dbf->header->bucket_size);
-
- if (!elem)
- return NULL;
- }
-
- elem->ca_adr = adr;
- elem->ca_changed = FALSE;
- elem->ca_data.hash_val = -1;
- elem->ca_data.elem_loc = -1;
-
- elem->ca_prev = elem->ca_next = NULL;
- elem->ca_hits = 0;
- elem->ca_node = NULL;
+ size_t l, r, m;
- dbf->cache_num++;
+ l = 0;
+ r = dbf->cache_num;
- return elem;
+ while (l < r)
+ {
+ m = (l + r) / 2;
+ if (dbf->cache_idx[m].elem->ca_adr < adr)
+ l = m + 1;
+ else
+ r = m;
+ }
+
+ *idx = l;
+ if (l < dbf->cache_num && dbf->cache_idx[l].elem->ca_adr == adr)
+ return elem_found;
+ }
+ return elem_new;
}
/* Frees element ELEM. Unlinks it from the cache tree and LRU list. */
static void
cache_elem_free (GDBM_FILE dbf, cache_elem *elem)
{
- _gdbm_cache_tree_delete (dbf->cache_tree, elem->ca_node);
+ size_t n;
+
+ if (cache_idx_lookup (dbf, elem->ca_adr, &n) != elem_found)
+ abort (); //FIXME
+ memmove (&dbf->cache_idx[n], &dbf->cache_idx[n + 1],
+ (dbf->cache_num - n - 1) * sizeof (dbf->cache_idx[0]));
+
lru_unlink_elem (dbf, elem);
elem->ca_next = dbf->cache_avail;
dbf->cache_avail = elem;
@@ -166,6 +170,7 @@ static inline int
cache_lru_free (GDBM_FILE dbf)
{
cache_elem *last = dbf->cache_lru;
+
if (last->ca_changed)
{
if (_gdbm_write_bucket (dbf, last))
@@ -179,51 +184,54 @@ static int
cache_lookup (GDBM_FILE dbf, off_t adr, cache_elem *ref, cache_elem **ret_elem)
{
int rc;
- cache_node *node;
+ size_t n;
cache_elem *elem;
int retrying = 0;
dbf->cache_access_count++;
- retry:
- rc = _gdbm_cache_tree_lookup (dbf->cache_tree, adr, &node);
+ rc = cache_idx_lookup (dbf, adr, &n);
switch (rc)
{
- case node_found:
- elem = node->elem;
+ case elem_found:
+ elem = dbf->cache_idx[n].elem;
elem->ca_hits++;
lru_unlink_elem (dbf, elem);
break;
- case node_new:
- elem = cache_elem_new (dbf, adr);
- if (!elem)
+ case elem_new:
+ if (!dbf->cache_avail)
{
- _gdbm_cache_tree_delete (dbf->cache_tree, node);
- return node_failure;
+ if (cache_lru_free (dbf))
+ return elem_failure;
}
- elem->ca_node = node;
- node->elem = elem;
-
- if (dbf->cache_num > dbf->cache_size && cache_lru_free (dbf))
+ elem = dbf->cache_avail;
+
+ if (elem->ca_bucket == NULL)
{
- cache_elem_free (dbf, elem);
- return node_failure;
+ if ((elem->ca_bucket = calloc (1, dbf->header->bucket_size)) == NULL)
+ return elem_failure;
}
- break;
+ dbf->cache_avail = elem->ca_next;
- case node_failure:
- if (!retrying)
- {
- if (errno == ENOMEM)
- {
- /* Release the last recently used element and retry. */
- if (cache_lru_free (dbf))
- return node_failure;
- retrying = 1;
- goto retry;
- }
- }
- return node_failure;
+ if (n < dbf->cache_num)
+ memmove (&dbf->cache_idx[n + 1], &dbf->cache_idx[n],
+ (dbf->cache_num - n) * sizeof (dbf->cache_idx[0]));
+ dbf->cache_idx[n].elem = elem;
+
+ elem->ca_adr = adr;
+ elem->ca_changed = FALSE;
+ elem->ca_data.hash_val = -1;
+ elem->ca_data.elem_loc = -1;
+
+ elem->ca_prev = elem->ca_next = NULL;
+ elem->ca_hits = 0;
+
+ dbf->cache_num++;
+
+ break;
+
+ default:
+ abort ();
}
lru_link_elem (dbf, elem, ref);
@@ -260,10 +268,10 @@ _gdbm_get_bucket (GDBM_FILE dbf, int dir_index)
switch (cache_lookup (dbf, bucket_adr, NULL, &elem))
{
- case node_found:
+ case elem_found:
break;
- case node_new:
+ case elem_new:
/* Position the file pointer */
file_pos = gdbm_file_seek (dbf, bucket_adr, SEEK_SET);
if (file_pos != bucket_adr)
@@ -312,7 +320,7 @@ _gdbm_get_bucket (GDBM_FILE dbf, int dir_index)
break;
- case node_failure:
+ case elem_failure:
return -1;
}
set_cache_entry (dbf, elem);
@@ -353,10 +361,10 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
adr_0 = _gdbm_alloc (dbf, dbf->header->bucket_size);
switch (cache_lookup (dbf, adr_0, dbf->cache_mru, &newcache[0]))
{
- case node_new:
+ case elem_new:
break;
- case node_found:
+ case elem_found:
/* should not happen */
GDBM_DEBUG (GDBM_DEBUG_ERR,
"%s: bucket found where it should not",
@@ -364,7 +372,7 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
GDBM_SET_ERRNO (dbf, GDBM_BUCKET_CACHE_CORRUPTED, TRUE);
return -1;
- case node_failure:
+ case elem_failure:
return -1;
}
_gdbm_new_bucket (dbf, newcache[0]->ca_bucket, new_bits);
@@ -372,10 +380,10 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
adr_1 = _gdbm_alloc (dbf, dbf->header->bucket_size);
switch (cache_lookup (dbf, adr_1, newcache[0], &newcache[1]))
{
- case node_new:
+ case elem_new:
break;
- case node_found:
+ case elem_found:
/* should not happen */
GDBM_DEBUG (GDBM_DEBUG_ERR,
"%s: bucket found where it should not",
@@ -383,7 +391,7 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
GDBM_SET_ERRNO (dbf, GDBM_BUCKET_CACHE_CORRUPTED, TRUE);
return -1;
- case node_failure:
+ case elem_failure:
return -1;
}
_gdbm_new_bucket (dbf, newcache[1]->ca_bucket, new_bits);
@@ -566,24 +574,34 @@ _gdbm_write_bucket (GDBM_FILE dbf, cache_elem *ca_entry)
int
_gdbm_cache_init (GDBM_FILE dbf, size_t size)
{
+ size_t i;
+
if (size == 0)
size = 1;
-
- if (size == dbf->cache_size)
- return 0;
- while (size < dbf->cache_num)
+ if (dbf->cache_size)
{
- /* Flush the least recently used element */
- cache_elem *elem = dbf->cache_lru;
- if (elem->ca_changed)
- {
- if (_gdbm_write_bucket (dbf, elem))
- return -1;
- }
- cache_elem_free (dbf, elem);
+ _gdbm_cache_flush (dbf);
+ _gdbm_cache_free (dbf);
}
-
+
+ dbf->cache_storage = calloc (size, sizeof (dbf->cache_storage[0]));
+ if (!dbf->cache_storage)
+ return -1;
+ dbf->cache_avail = &dbf->cache_storage[0];
+ for (i = 0; i < size - 1; i++)
+ dbf->cache_storage[i].ca_next = &dbf->cache_storage[i+1];
+ dbf->cache_storage[i].ca_next = NULL;
+
+ dbf->cache_idx = calloc (size, sizeof (dbf->cache_idx[0]));
+ if (!dbf->cache_idx)
+ {
+ free (dbf->cache_storage);
+ dbf->cache_storage = NULL;
+ dbf->cache_avail = NULL;
+ return -1;
+ }
+
dbf->cache_size = size;
return 0;
@@ -593,17 +611,15 @@ _gdbm_cache_init (GDBM_FILE dbf, size_t size)
void
_gdbm_cache_free (GDBM_FILE dbf)
{
- cache_elem *elem;
-
- while (dbf->cache_lru)
- cache_elem_free (dbf, dbf->cache_lru);
- _gdbm_cache_tree_destroy (dbf->cache_tree);
- while ((elem = dbf->cache_avail) != NULL)
+ size_t i;
+
+ for (i = 0; i < dbf->cache_size; i++)
{
- dbf->cache_avail = elem->ca_next;
- free (elem->ca_data.dptr);
- free (elem);
+ free (dbf->cache_storage[i].ca_data.dptr);
+ free (dbf->cache_storage[i].ca_bucket);
}
+ free (dbf->cache_storage);
+ free (dbf->cache_idx);
}
/* Flush cache content to disk. */
@@ -640,10 +656,10 @@ _gdbm_fetch_data (GDBM_FILE dbf, off_t off, size_t size, void *buf)
switch (cache_lookup (dbf, bucket_adr, dbf->cache_mru, &elem))
{
- case node_found:
+ case elem_found:
break;
- case node_new:
+ case elem_new:
/* Position the file pointer */
file_pos = gdbm_file_seek (dbf, bucket_adr, SEEK_SET);
if (file_pos != bucket_adr)
@@ -669,7 +685,7 @@ _gdbm_fetch_data (GDBM_FILE dbf, off_t off, size_t size, void *buf)
}
break;
- case node_failure:
+ case elem_failure:
return -1;
}
diff --git a/src/cachetree.c b/src/cachetree.c
deleted file mode 100644
index d25739a..0000000
--- a/src/cachetree.c
+++ /dev/null
@@ -1,486 +0,0 @@
-/* cachetree.c - Implementation of the red-black tree for cache lookups. */
-
-/* This file is part of GDBM, the GNU data base manager.
- Copyright (C) 2019-2021 Free Software Foundation, Inc.
-
- GDBM 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 3, or (at your option)
- any later version.
-
- GDBM 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 GDBM. If not, see <http://www.gnu.org/licenses/>. */
-
-#include "autoconf.h"
-#include "gdbmdefs.h"
-#define NDEBUG
-#include "assert.h"
-
-enum cache_node_color { RED, BLACK };
-
-struct cache_tree
-{
- cache_node *root; /* Root of the tree */
- cache_node *avail; /* List of available nodes, linked by parent field */
-};
-
-/* Allocate and return a new node. Pick the head item from the avail
- list and update the avail pointer. If the list is empty, malloc
- a new node.
- All members in the returned node are filled with 0.
-*/
-static cache_node *
-rbt_node_alloc (cache_tree *tree)
-{
- cache_node *n;
-
- n = tree->avail;
- if (n)
- tree->avail = n->parent;
- else
- {
- n = malloc (sizeof (*n));
- if (!n)
- return NULL;
- }
- memset (n, 0, sizeof (*n));
- return n;
-}
-
-/* Return the node N to the avail list in TREE. */
-static void
-rbt_node_dealloc (cache_tree *tree, cache_node *n)
-{
- n->parent = tree->avail;
- tree->avail = n;
-}
-
-/* Red-black tree properties:
- 1. Each node is either red or black.
- 2. The root node is black.
- 3. All leaves are black and contain no data.
- 4. Every red node has two children, and both are black.
- IOW, the parent of every red node is black.
- 5. All paths from any given node to its leaf nodes contain the same
- number of black nodes.
- */
-
-/* Auxiliary functions for accessing nodes. */
-
-/* Return the grandparent node of N.
- Prerequisite: N may not be root.
-*/
-static inline cache_node *
-grandparent (cache_node *n)
-{
- return n->parent->parent;
-}
-
-/* Return the sibling node of N.
- Prerequisite: N may not be root.
-*/
-static inline cache_node *
-sibling (cache_node *n)
-{
- return (n == n->parent->left) ? n->parent->right : n->parent->left;
-}
-
-/* Return the uncle node of N.
- Prerequisite: N must be at least 2 nodes away from root.
-*/
-static inline cache_node *
-uncle (cache_node *n)
-{
- return sibling (n->parent);
-}
-
-/* Returns the color of the node N.
- Empty leaves are represented by NULL, therefore NULL is assumed to
- be black (see property 3).
-*/
-static inline enum cache_node_color
-node_color (cache_node *n)
-{
- return n == NULL ? BLACK : n->color;
-}
-
-/* Replace the OLDN with NEWN.
- Does not modify OLDN. */
-static void
-replace_node (cache_tree *tree, cache_node *oldn, cache_node *newn)
-{
- if (oldn->parent == NULL)
- tree->root = newn;
- else if (oldn == oldn->parent->left)
- oldn->parent->left = newn;
- else
- oldn->parent->right = newn;
-
- if (newn != NULL)
- newn->parent = oldn->parent;
-}
-
-/* Rotate the TREE left over the node N. */
-static void
-rotate_left (cache_tree *tree, cache_node *n)
-{
- cache_node *right = n->right;
- replace_node (tree, n, right);
- n->right = right->left;
- if (right->left != NULL)
- right->left->parent = n;
- right->left = n;
- n->parent = right;
-}
-
-/* Rotate the TREE right over the node N. */
-static void
-rotate_right (cache_tree *tree, cache_node *n)
-{
- cache_node *left = n->left;
- replace_node (tree, n, left);
- n->left = left->right;
- if (left->right != NULL)
- left->right->parent = n;
- left->right = n;
- n->parent = left;
-}
-
-/* Node deletion */
-static void rbt_delete_fixup (cache_tree *tree, cache_node *n);
-
-/* Remove N from the TREE. */
-void
-_gdbm_cache_tree_delete (cache_tree *tree, cache_node *n)
-{
- cache_node *child;
-
- /* If N has both left and right children, reduce the problem to
- the node with only one child. To do so, find the in-order
- predecessor of N, copy its value (elem) to N and then delete
- the predecessor. */
- if (n->left != NULL && n->right != NULL)
- {
- cache_node *p;
- for (p = n->left; p->right; p = p->right)
- ;
- n->adr = p->adr;
- n->elem = p->elem;
- n->elem->ca_node = n;
- n = p;
- }
-
- /* N has only one child. Select it. */
- child = n->left ? n->left : n->right;
- if (node_color (n) == BLACK)
- {
- n->color = node_color (child);
- rbt_delete_fixup (tree, n);
- }
- replace_node (tree, n, child);
- if (n->parent == NULL && child != NULL) /* root should be black */
- child->color = BLACK;
-
- /* Return N to the avail pool */
- rbt_node_dealloc (tree, n);
-}
-
-static void
-rbt_delete_fixup (cache_tree *tree, cache_node *n)
-{
- while (1)
- {
- if (n->parent == NULL)
- {
- /* If N has become the root node, deletion resulted in removing
- one black node (prior root) from every path, so all properties
- still hold.
- */
- return;
- }
- else
- {
- /* If N has a red sibling, change the colors of the parent and
- sibling and rotate about the parent. Thus, the sibling becomes
- grandparent and we can proceed to the next case.
- */
- if (node_color (sibling (n)) == RED)
- {
- n->parent->color = RED;
- sibling (n)->color = BLACK;
- if (n == n->parent->left)
- rotate_left (tree, n->parent);
- else
- rotate_right (tree, n->parent);
- }
-
- /* If the parent, sibling and nephews are all black, paint the
- sibling red. This means one black node was removed from all
- paths passing through the parent, so we recurse to the beginning
- of the loop with parent as the argument to restore the properties.
- This is the only branch that loops.
- */
- if (node_color (n->parent) == BLACK
- && node_color (sibling (n)) == BLACK
- && node_color (sibling (n)->left) == BLACK
- && node_color (sibling (n)->right) == BLACK)
- {
- sibling (n)->color = RED;
- n = n->parent;
- continue;
- }
- else
- {
- /* If the sibling and nephews are black but the parent is red,
- swap the colors of the sibling and parent. The properties
- are then restored.
- */
- if (node_color (n->parent) == RED
- && node_color (sibling (n)) == BLACK
- && node_color (sibling (n)->left) == BLACK
- && node_color (sibling (n)->right) == BLACK)
- {
- sibling (n)->color = RED;
- n->parent->color = BLACK;
- }
- else
- {
- /* N is the left child of its parent, its sibling is black,
- and the sibling's right child is black. Swap the colors
- of the sibling and its left sibling and rotate right
- over the sibling.
- */
- if (n == n->parent->left
- && node_color (sibling (n)) == BLACK
- && node_color (sibling (n)->left) == RED
- && node_color (sibling (n)->right) == BLACK)
- {
- sibling (n)->color = RED;
- sibling (n)->left->color = BLACK;
- rotate_right (tree, sibling (n));
- }
- else if (n == n->parent->right
- && node_color (sibling (n)) == BLACK
- && node_color (sibling (n)->right) == RED
- && node_color (sibling (n)->left) == BLACK)
- {
- /* The mirror case is handled similarly. */
- sibling (n)->color = RED;
- sibling (n)->right->color = BLACK;
- rotate_left (tree, sibling (n));
- }
- /* N is the left child of its parent, its sibling is black
- and the sibling's right child is red. Swap the colors
- of the parent and sibling, paint the sibling's right
- child black and rotate left at the parent. Similarly
- for the mirror case. This achieves the following:
-
- . A black node is added to all paths passing through N;
- . A black node is removed from all paths through the
- sibling's red child.
- . The latter is painted black which restores missing
- black node in all paths through the sibling's red child.
-
- Another sibling's child becomes a child of N's parent
- during the rotation and is therefore not affected.
- */
- sibling (n)->color = node_color (n->parent);
- n->parent->color = BLACK;
- if (n == n->parent->left)
- {
- sibling (n)->right->color = BLACK;
- rotate_left (tree, n->parent);
- }
- else
- {
- sibling (n)->left->color = BLACK;
- rotate_right (tree, n->parent);
- }
- }
- }
- }
- break;
- }
-}
-
-/* Insertion */
-static void rbt_insert_fixup (cache_tree *tree, cache_node *n);
-
-/* Look up the node with the given ADR.
- If found, put it in *RETVAL and return node_found.
-
- Otherwise, create a new node and insert it at the appropriate place in
- the tree. Store the address of the newly created node in *RETVAL and
- return node_new.
-
- If a new node cannot be created (memory exhausted), return node_failure.
-*/
-int
-_gdbm_cache_tree_lookup (cache_tree *tree, off_t adr, cache_node **retval)
-{
- int res;
- cache_node *node, *parent = NULL;
- cache_node **nodeptr;
-
- nodeptr = &tree->root;
- while ((node = *nodeptr) != NULL)
- {
- if (adr == node->adr)
- break;
- parent = node;
- if (adr < node->adr)
- nodeptr = &node->left;
- else
- nodeptr = &node->right;
- }
-
- if (node)
- {
- res = node_found;
- }
- else
- {
- node = rbt_node_alloc (tree);
- if (!node)
- return node_failure;
- *nodeptr = node;
- node->adr = adr;
- node->parent = parent;
- rbt_insert_fixup (tree, node);
- res = node_new;
- }
- *retval = node;
- return res;
-}
-
-static void
-rbt_insert_fixup (cache_tree *tree, cache_node *n)
-{
- while (1)
- {
- if (n->parent == NULL)
- {
- /* Node was inserted at the root of the tree.
- The root node must be black (property 2). Changing its color
- to black would add one black node to every path, which means
- the property 5 would remain satisfied. So we simply paint the
- node black.
- */
- n->color = BLACK;
- }
- else if (node_color (n->parent) == BLACK)
- {
- /* The node has black parent.
- All properties are satisfied. There's no need to change anything.
- */
- return;
- }
- else if (node_color (uncle (n)) == RED)
- {
- /* The uncle node is red.
- Repaint the parent and uncle black and the grandparent red. This
- would satisfy 4. However, if the grandparent is root, this would
- violate the property 2. So we repaint the grandparent by
- re-entering the fixup loop with grandparent as the node.
- This is the only branch that loops.
- */
- n->parent->color = BLACK;
- uncle (n)->color = BLACK;
- n = grandparent (n);
- n->color = RED;
- continue;
- }
- else
- {
- /* The new node is the right child of its parent and the parent is
- the left child of the grandparent. Rotate left about the parent.
- Mirror case: The new node is the left child of its parent and the
- parent is the right child of the grandparent. Rotate right about
- the parent. This fixes the properties for the rbt_insert_5.
- */
- if (n == n->parent->right && n->parent == grandparent (n)->left)
- {
- rotate_left (tree, n->parent);
- n = n->left;
- }
- else if (n == n->parent->left && n->parent == grandparent (n)->right)
- {
- rotate_right (tree, n->parent);
- n = n->right;
- }
-
- /* The new node is the left child of its parent and the parent is the
- left child of the grandparent. Rotate right about the grandparent.
- Mirror case: The new node is the right child of its parent and the
- parent
- is the right child of the grandparent. Rotate left.
- */
- n->parent->color = BLACK;
- grandparent (n)->color = RED;
- if (n == n->parent->left && n->parent == grandparent (n)->left)
- {
- rotate_right (tree, grandparent (n));
- }
- else
- {
- rotate_left (tree, grandparent (n));
- }
- }
- break;
- }
-}
-
-/* Interface functions */
-
-/* Create a cache tree structure for the database file DBF. */
-cache_tree *
-_gdbm_cache_tree_alloc (void)
-{
- cache_tree *t = malloc (sizeof (*t));
- if (t)
- {
- t->root = NULL;
- t->avail = NULL;
- }
- return t;
-}
-
-/* Free the memory used by the TREE. */
-void
-_gdbm_cache_tree_destroy (cache_tree *tree)
-{
- cache_node *n;
-
- /* Free the allocated tree nodes. Traverse the tree as if it were
- a simple binary tree: there's no use preserving RBT properties now.
- */
- while ((n = tree->root) != NULL)
- {
- if (!n->left)
- tree->root = n->right;
- else if (!n->right)
- tree->root = n->left;
- else
- {
- cache_node *p;
- for (p = n->left; p->right; p = p->right)
- ;
- p->right = n->right;
- tree->root = n->left;
- }
- free (n);
- }
-
- /* Free the avail list */
- while ((n = tree->avail) != NULL)
- {
- tree->avail = n->parent;
- free (n);
- }
- free (tree);
-}
diff --git a/src/gdbmdefs.h b/src/gdbmdefs.h
index ea9df3e..57ca1d9 100644
--- a/src/gdbmdefs.h
+++ b/src/gdbmdefs.h
@@ -157,15 +157,11 @@ typedef struct
} data_cache_elem;
typedef struct cache_elem cache_elem;
-typedef struct cache_node cache_node;
-struct cache_node
+typedef struct
{
- cache_node *left, *right, *parent;
- int color;
- off_t adr;
cache_elem *elem;
-};
+} cache_idx;
struct cache_elem
{
@@ -178,14 +174,10 @@ struct cache_elem
ca_next is used. It points to the next
available element. */
size_t ca_hits; /* Number of times this element was requested */
- cache_node *ca_node; /* Points back to the RBT node for this
- element. */
- hash_bucket ca_bucket[1];/* Associated bucket (dbf->header->bucket_size
+ hash_bucket *ca_bucket; /* Associated bucket (dbf->header->bucket_size
bytes). */
};
-typedef struct cache_tree cache_tree;
-
/* This final structure contains all main memory based information for
a gdbm file. This allows multiple gdbm files to be opened at the same
time by one program. */
@@ -248,8 +240,12 @@ struct gdbm_file_info
/* The bucket cache. */
size_t cache_size; /* Cache capacity */
size_t cache_num; /* Actual number of elements in cache */
- /* Cache elements form a binary search tree. */
- cache_tree *cache_tree;
+
+ /* Cache element storage */
+ cache_elem *cache_storage;
+ /* Cache index sorted by offset */
+ cache_idx *cache_idx;
+
/* Cache elements are linked in a list sorted by relative access time */
cache_elem *cache_mru; /* Most recently used element - head of the list */
cache_elem *cache_lru; /* Last recently used element - tail of the list */
diff --git a/src/gdbmopen.c b/src/gdbmopen.c
index 7806c7a..3aefe9f 100644
--- a/src/gdbmopen.c
+++ b/src/gdbmopen.c
@@ -270,7 +270,6 @@ gdbm_fd_open (int fd, const char *file_name, int block_size,
dbf->header = NULL;
/* Initialize cache */
- dbf->cache_tree = _gdbm_cache_tree_alloc ();
_gdbm_cache_init (dbf, DEFAULT_CACHESIZE);
dbf->memory_mapping = FALSE;
diff --git a/src/proto.h b/src/proto.h
index 4ba5cc0..80817ba 100644
--- a/src/proto.h
+++ b/src/proto.h
@@ -84,21 +84,6 @@ int _gdbm_dump (GDBM_FILE dbf, FILE *fp);
/* From recover.c */
int _gdbm_next_bucket_dir (GDBM_FILE dbf, int bucket_dir);
-/* cachetree.c */
-cache_tree *_gdbm_cache_tree_alloc (void);
-void _gdbm_cache_tree_destroy (cache_tree *tree);
-void _gdbm_cache_tree_delete (cache_tree *tree, struct cache_node *n);
-
-/* Return codes for _gdbm_cache_tree_lookup. */
-enum
- {
- node_found, /* Returned element was found in cache. */
- node_new, /* Returned element has been created and inserted to cache */
- node_failure /* An error occurred. */
- };
-
-int _gdbm_cache_tree_lookup (cache_tree *tree, off_t adr, cache_node **retval);
-
/* I/O functions */
static inline ssize_t
gdbm_file_read (GDBM_FILE dbf, void *buf, size_t size)
diff --git a/src/recover.c b/src/recover.c
index 78a5d1c..f6c4543 100644
--- a/src/recover.c
+++ b/src/recover.c
@@ -154,7 +154,8 @@ _gdbm_finish_transfer (GDBM_FILE dbf, GDBM_FILE new_dbf,
dbf->cache_size = new_dbf->cache_size;
dbf->cache_num = new_dbf->cache_num;
- dbf->cache_tree = new_dbf->cache_tree;
+ dbf->cache_storage = new_dbf->cache_storage;
+ dbf->cache_idx = new_dbf->cache_idx;
dbf->cache_entry = new_dbf->cache_entry;
dbf->cache_lru = new_dbf->cache_lru;
dbf->cache_avail = new_dbf->cache_avail;

Return to:

Send suggestions and report system problems to the System administrator.