diff options
| -rw-r--r-- | contrib/rbtree/rb.c | 929 | ||||
| -rw-r--r-- | contrib/rbtree/rb.h | 122 | ||||
| -rw-r--r-- | libglusterfs/src/Makefile.am | 6 | ||||
| -rw-r--r-- | libglusterfs/src/rbthash.c | 388 | ||||
| -rw-r--r-- | libglusterfs/src/rbthash.h | 75 |
5 files changed, 1517 insertions, 3 deletions
diff --git a/contrib/rbtree/rb.c b/contrib/rbtree/rb.c new file mode 100644 index 00000000000..d1339b97d0a --- /dev/null +++ b/contrib/rbtree/rb.c @@ -0,0 +1,929 @@ +/* Produced by texiweb from libavl.w. */ + +/* libavl - library for manipulation of binary trees. + Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc. + + This program 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 2 of the + License, or (at your option) any later version. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. + + The author may be contacted at <blp@gnu.org> on the Internet, or + write to Ben Pfaff, Stanford University, Computer Science Dept., 353 + Serra Mall, Stanford CA 94305, USA. +*/ + +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include "rb.h" + +/* Creates and returns a new table + with comparison function |compare| using parameter |param| + and memory allocator |allocator|. + Returns |NULL| if memory allocation failed. */ +struct rb_table * +rb_create (rb_comparison_func *compare, void *param, + struct libavl_allocator *allocator) +{ + struct rb_table *tree; + + assert (compare != NULL); + + if (allocator == NULL) + allocator = &rb_allocator_default; + + tree = allocator->libavl_malloc (allocator, sizeof *tree); + if (tree == NULL) + return NULL; + + tree->rb_root = NULL; + tree->rb_compare = compare; + tree->rb_param = param; + tree->rb_alloc = allocator; + tree->rb_count = 0; + tree->rb_generation = 0; + + return tree; +} + +/* Search |tree| for an item matching |item|, and return it if found. + Otherwise return |NULL|. */ +void * +rb_find (const struct rb_table *tree, const void *item) +{ + const struct rb_node *p; + + assert (tree != NULL && item != NULL); + for (p = tree->rb_root; p != NULL; ) + { + int cmp = tree->rb_compare (item, p->rb_data, tree->rb_param); + + if (cmp < 0) + p = p->rb_link[0]; + else if (cmp > 0) + p = p->rb_link[1]; + else /* |cmp == 0| */ + return p->rb_data; + } + + return NULL; +} + +/* Inserts |item| into |tree| and returns a pointer to |item|'s address. + If a duplicate item is found in the tree, + returns a pointer to the duplicate without inserting |item|. + Returns |NULL| in case of memory allocation failure. */ +void ** +rb_probe (struct rb_table *tree, void *item) +{ + struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */ + unsigned char da[RB_MAX_HEIGHT]; /* Directions moved from stack nodes. */ + int k; /* Stack height. */ + + struct rb_node *p; /* Traverses tree looking for insertion point. */ + struct rb_node *n; /* Newly inserted node. */ + + assert (tree != NULL && item != NULL); + + pa[0] = (struct rb_node *) &tree->rb_root; + da[0] = 0; + k = 1; + for (p = tree->rb_root; p != NULL; p = p->rb_link[da[k - 1]]) + { + int cmp = tree->rb_compare (item, p->rb_data, tree->rb_param); + if (cmp == 0) + return &p->rb_data; + + pa[k] = p; + da[k++] = cmp > 0; + } + + n = pa[k - 1]->rb_link[da[k - 1]] = + tree->rb_alloc->libavl_malloc (tree->rb_alloc, sizeof *n); + if (n == NULL) + return NULL; + + n->rb_data = item; + n->rb_link[0] = n->rb_link[1] = NULL; + n->rb_color = RB_RED; + tree->rb_count++; + tree->rb_generation++; + + while (k >= 3 && pa[k - 1]->rb_color == RB_RED) + { + if (da[k - 2] == 0) + { + struct rb_node *y = pa[k - 2]->rb_link[1]; + if (y != NULL && y->rb_color == RB_RED) + { + pa[k - 1]->rb_color = y->rb_color = RB_BLACK; + pa[k - 2]->rb_color = RB_RED; + k -= 2; + } + else + { + struct rb_node *x; + + if (da[k - 1] == 0) + y = pa[k - 1]; + else + { + x = pa[k - 1]; + y = x->rb_link[1]; + x->rb_link[1] = y->rb_link[0]; + y->rb_link[0] = x; + pa[k - 2]->rb_link[0] = y; + } + + x = pa[k - 2]; + x->rb_color = RB_RED; + y->rb_color = RB_BLACK; + + x->rb_link[0] = y->rb_link[1]; + y->rb_link[1] = x; + pa[k - 3]->rb_link[da[k - 3]] = y; + break; + } + } + else + { + struct rb_node *y = pa[k - 2]->rb_link[0]; + if (y != NULL && y->rb_color == RB_RED) + { + pa[k - 1]->rb_color = y->rb_color = RB_BLACK; + pa[k - 2]->rb_color = RB_RED; + k -= 2; + } + else + { + struct rb_node *x; + + if (da[k - 1] == 1) + y = pa[k - 1]; + else + { + x = pa[k - 1]; + y = x->rb_link[0]; + x->rb_link[0] = y->rb_link[1]; + y->rb_link[1] = x; + pa[k - 2]->rb_link[1] = y; + } + + x = pa[k - 2]; + x->rb_color = RB_RED; + y->rb_color = RB_BLACK; + + x->rb_link[1] = y->rb_link[0]; + y->rb_link[0] = x; + pa[k - 3]->rb_link[da[k - 3]] = y; + break; + } + } + } + tree->rb_root->rb_color = RB_BLACK; + + + return &n->rb_data; +} + +/* Inserts |item| into |table|. + Returns |NULL| if |item| was successfully inserted + or if a memory allocation error occurred. + Otherwise, returns the duplicate item. */ +void * +rb_insert (struct rb_table *table, void *item) +{ + void **p = rb_probe (table, item); + return p == NULL || *p == item ? NULL : *p; +} + +/* Inserts |item| into |table|, replacing any duplicate item. + Returns |NULL| if |item| was inserted without replacing a duplicate, + or if a memory allocation error occurred. + Otherwise, returns the item that was replaced. */ +void * +rb_replace (struct rb_table *table, void *item) +{ + void **p = rb_probe (table, item); + if (p == NULL || *p == item) + return NULL; + else + { + void *r = *p; + *p = item; + return r; + } +} + +/* Deletes from |tree| and returns an item matching |item|. + Returns a null pointer if no matching item found. */ +void * +rb_delete (struct rb_table *tree, const void *item) +{ + struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */ + unsigned char da[RB_MAX_HEIGHT]; /* Directions moved from stack nodes. */ + int k; /* Stack height. */ + + struct rb_node *p; /* The node to delete, or a node part way to it. */ + int cmp; /* Result of comparison between |item| and |p|. */ + + assert (tree != NULL && item != NULL); + + k = 0; + p = (struct rb_node *) &tree->rb_root; + for (cmp = -1; cmp != 0; + cmp = tree->rb_compare (item, p->rb_data, tree->rb_param)) + { + int dir = cmp > 0; + + pa[k] = p; + da[k++] = dir; + + p = p->rb_link[dir]; + if (p == NULL) + return NULL; + } + item = p->rb_data; + + if (p->rb_link[1] == NULL) + pa[k - 1]->rb_link[da[k - 1]] = p->rb_link[0]; + else + { + enum rb_color t; + struct rb_node *r = p->rb_link[1]; + + if (r->rb_link[0] == NULL) + { + r->rb_link[0] = p->rb_link[0]; + t = r->rb_color; + r->rb_color = p->rb_color; + p->rb_color = t; + pa[k - 1]->rb_link[da[k - 1]] = r; + da[k] = 1; + pa[k++] = r; + } + else + { + struct rb_node *s; + int j = k++; + + for (;;) + { + da[k] = 0; + pa[k++] = r; + s = r->rb_link[0]; + if (s->rb_link[0] == NULL) + break; + + r = s; + } + + da[j] = 1; + pa[j] = s; + pa[j - 1]->rb_link[da[j - 1]] = s; + + s->rb_link[0] = p->rb_link[0]; + r->rb_link[0] = s->rb_link[1]; + s->rb_link[1] = p->rb_link[1]; + + t = s->rb_color; + s->rb_color = p->rb_color; + p->rb_color = t; + } + } + + if (p->rb_color == RB_BLACK) + { + for (;;) + { + struct rb_node *x = pa[k - 1]->rb_link[da[k - 1]]; + if (x != NULL && x->rb_color == RB_RED) + { + x->rb_color = RB_BLACK; + break; + } + if (k < 2) + break; + + if (da[k - 1] == 0) + { + struct rb_node *w = pa[k - 1]->rb_link[1]; + + if (w->rb_color == RB_RED) + { + w->rb_color = RB_BLACK; + pa[k - 1]->rb_color = RB_RED; + + pa[k - 1]->rb_link[1] = w->rb_link[0]; + w->rb_link[0] = pa[k - 1]; + pa[k - 2]->rb_link[da[k - 2]] = w; + + pa[k] = pa[k - 1]; + da[k] = 0; + pa[k - 1] = w; + k++; + + w = pa[k - 1]->rb_link[1]; + } + + if ((w->rb_link[0] == NULL + || w->rb_link[0]->rb_color == RB_BLACK) + && (w->rb_link[1] == NULL + || w->rb_link[1]->rb_color == RB_BLACK)) + w->rb_color = RB_RED; + else + { + if (w->rb_link[1] == NULL + || w->rb_link[1]->rb_color == RB_BLACK) + { + struct rb_node *y = w->rb_link[0]; + y->rb_color = RB_BLACK; + w->rb_color = RB_RED; + w->rb_link[0] = y->rb_link[1]; + y->rb_link[1] = w; + w = pa[k - 1]->rb_link[1] = y; + } + + w->rb_color = pa[k - 1]->rb_color; + pa[k - 1]->rb_color = RB_BLACK; + w->rb_link[1]->rb_color = RB_BLACK; + + pa[k - 1]->rb_link[1] = w->rb_link[0]; + w->rb_link[0] = pa[k - 1]; + pa[k - 2]->rb_link[da[k - 2]] = w; + break; + } + } + else + { + struct rb_node *w = pa[k - 1]->rb_link[0]; + + if (w->rb_color == RB_RED) + { + w->rb_color = RB_BLACK; + pa[k - 1]->rb_color = RB_RED; + + pa[k - 1]->rb_link[0] = w->rb_link[1]; + w->rb_link[1] = pa[k - 1]; + pa[k - 2]->rb_link[da[k - 2]] = w; + + pa[k] = pa[k - 1]; + da[k] = 1; + pa[k - 1] = w; + k++; + + w = pa[k - 1]->rb_link[0]; + } + + if ((w->rb_link[0] == NULL + || w->rb_link[0]->rb_color == RB_BLACK) + && (w->rb_link[1] == NULL + || w->rb_link[1]->rb_color == RB_BLACK)) + w->rb_color = RB_RED; + else + { + if (w->rb_link[0] == NULL + || w->rb_link[0]->rb_color == RB_BLACK) + { + struct rb_node *y = w->rb_link[1]; + y->rb_color = RB_BLACK; + w->rb_color = RB_RED; + w->rb_link[1] = y->rb_link[0]; + y->rb_link[0] = w; + w = pa[k - 1]->rb_link[0] = y; + } + + w->rb_color = pa[k - 1]->rb_color; + pa[k - 1]->rb_color = RB_BLACK; + w->rb_link[0]->rb_color = RB_BLACK; + + pa[k - 1]->rb_link[0] = w->rb_link[1]; + w->rb_link[1] = pa[k - 1]; + pa[k - 2]->rb_link[da[k - 2]] = w; + break; + } + } + + k--; + } + + } + + tree->rb_alloc->libavl_free (tree->rb_alloc, p); + tree->rb_count--; + tree->rb_generation++; + return (void *) item; +} + +/* Refreshes the stack of parent pointers in |trav| + and updates its generation number. */ +static void +trav_refresh (struct rb_traverser *trav) +{ + assert (trav != NULL); + + trav->rb_generation = trav->rb_table->rb_generation; + + if (trav->rb_node != NULL) + { + rb_comparison_func *cmp = trav->rb_table->rb_compare; + void *param = trav->rb_table->rb_param; + struct rb_node *node = trav->rb_node; + struct rb_node *i; + + trav->rb_height = 0; + for (i = trav->rb_table->rb_root; i != node; ) + { + assert (trav->rb_height < RB_MAX_HEIGHT); + assert (i != NULL); + + trav->rb_stack[trav->rb_height++] = i; + i = i->rb_link[cmp (node->rb_data, i->rb_data, param) > 0]; + } + } +} + +/* Initializes |trav| for use with |tree| + and selects the null node. */ +void +rb_t_init (struct rb_traverser *trav, struct rb_table *tree) +{ + trav->rb_table = tree; + trav->rb_node = NULL; + trav->rb_height = 0; + trav->rb_generation = tree->rb_generation; +} + +/* Initializes |trav| for |tree| + and selects and returns a pointer to its least-valued item. + Returns |NULL| if |tree| contains no nodes. */ +void * +rb_t_first (struct rb_traverser *trav, struct rb_table *tree) +{ + struct rb_node *x; + + assert (tree != NULL && trav != NULL); + + trav->rb_table = tree; + trav->rb_height = 0; + trav->rb_generation = tree->rb_generation; + + x = tree->rb_root; + if (x != NULL) + while (x->rb_link[0] != NULL) + { + assert (trav->rb_height < RB_MAX_HEIGHT); + trav->rb_stack[trav->rb_height++] = x; + x = x->rb_link[0]; + } + trav->rb_node = x; + + return x != NULL ? x->rb_data : NULL; +} + +/* Initializes |trav| for |tree| + and selects and returns a pointer to its greatest-valued item. + Returns |NULL| if |tree| contains no nodes. */ +void * +rb_t_last (struct rb_traverser *trav, struct rb_table *tree) +{ + struct rb_node *x; + + assert (tree != NULL && trav != NULL); + + trav->rb_table = tree; + trav->rb_height = 0; + trav->rb_generation = tree->rb_generation; + + x = tree->rb_root; + if (x != NULL) + while (x->rb_link[1] != NULL) + { + assert (trav->rb_height < RB_MAX_HEIGHT); + trav->rb_stack[trav->rb_height++] = x; + x = x->rb_link[1]; + } + trav->rb_node = x; + + return x != NULL ? x->rb_data : NULL; +} + +/* Searches for |item| in |tree|. + If found, initializes |trav| to the item found and returns the item + as well. + If there is no matching item, initializes |trav| to the null item + and returns |NULL|. */ +void * +rb_t_find (struct rb_traverser *trav, struct rb_table *tree, void *item) +{ + struct rb_node *p, *q; + + assert (trav != NULL && tree != NULL && item != NULL); + trav->rb_table = tree; + trav->rb_height = 0; + trav->rb_generation = tree->rb_generation; + for (p = tree->rb_root; p != NULL; p = q) + { + int cmp = tree->rb_compare (item, p->rb_data, tree->rb_param); + + if (cmp < 0) + q = p->rb_link[0]; + else if (cmp > 0) + q = p->rb_link[1]; + else /* |cmp == 0| */ + { + trav->rb_node = p; + return p->rb_data; + } + + assert (trav->rb_height < RB_MAX_HEIGHT); + trav->rb_stack[trav->rb_height++] = p; + } + + trav->rb_height = 0; + trav->rb_node = NULL; + return NULL; +} + +/* Attempts to insert |item| into |tree|. + If |item| is inserted successfully, it is returned and |trav| is + initialized to its location. + If a duplicate is found, it is returned and |trav| is initialized to + its location. No replacement of the item occurs. + If a memory allocation failure occurs, |NULL| is returned and |trav| + is initialized to the null item. */ +void * +rb_t_insert (struct rb_traverser *trav, struct rb_table *tree, void *item) +{ + void **p; + + assert (trav != NULL && tree != NULL && item != NULL); + + p = rb_probe (tree, item); + if (p != NULL) + { + trav->rb_table = tree; + trav->rb_node = + ((struct rb_node *) + ((char *) p - offsetof (struct rb_node, rb_data))); + trav->rb_generation = tree->rb_generation - 1; + return *p; + } + else + { + rb_t_init (trav, tree); + return NULL; + } +} + +/* Initializes |trav| to have the same current node as |src|. */ +void * +rb_t_copy (struct rb_traverser *trav, const struct rb_traverser *src) +{ + assert (trav != NULL && src != NULL); + + if (trav != src) + { + trav->rb_table = src->rb_table; + trav->rb_node = src->rb_node; + trav->rb_generation = src->rb_generation; + if (trav->rb_generation == trav->rb_table->rb_generation) + { + trav->rb_height = src->rb_height; + memcpy (trav->rb_stack, (const void *) src->rb_stack, + sizeof *trav->rb_stack * trav->rb_height); + } + } + + return trav->rb_node != NULL ? trav->rb_node->rb_data : NULL; +} + +/* Returns the next data item in inorder + within the tree being traversed with |trav|, + or if there are no more data items returns |NULL|. */ +void * +rb_t_next (struct rb_traverser *trav) +{ + struct rb_node *x; + + assert (trav != NULL); + + if (trav->rb_generation != trav->rb_table->rb_generation) + trav_refresh (trav); + + x = trav->rb_node; + if (x == NULL) + { + return rb_t_first (trav, trav->rb_table); + } + else if (x->rb_link[1] != NULL) + { + assert (trav->rb_height < RB_MAX_HEIGHT); + trav->rb_stack[trav->rb_height++] = x; + x = x->rb_link[1]; + + while (x->rb_link[0] != NULL) + { + assert (trav->rb_height < RB_MAX_HEIGHT); + trav->rb_stack[trav->rb_height++] = x; + x = x->rb_link[0]; + } + } + else + { + struct rb_node *y; + + do + { + if (trav->rb_height == 0) + { + trav->rb_node = NULL; + return NULL; + } + + y = x; + x = trav->rb_stack[--trav->rb_height]; + } + while (y == x->rb_link[1]); + } + trav->rb_node = x; + + return x->rb_data; +} + +/* Returns the previous data item in inorder + within the tree being traversed with |trav|, + or if there are no more data items returns |NULL|. */ +void * +rb_t_prev (struct rb_traverser *trav) +{ + struct rb_node *x; + + assert (trav != NULL); + + if (trav->rb_generation != trav->rb_table->rb_generation) + trav_refresh (trav); + + x = trav->rb_node; + if (x == NULL) + { + return rb_t_last (trav, trav->rb_table); + } + else if (x->rb_link[0] != NULL) + { + assert (trav->rb_height < RB_MAX_HEIGHT); + trav->rb_stack[trav->rb_height++] = x; + x = x->rb_link[0]; + + while (x->rb_link[1] != NULL) + { + assert (trav->rb_height < RB_MAX_HEIGHT); + trav->rb_stack[trav->rb_height++] = x; + x = x->rb_link[1]; + } + } + else + { + struct rb_node *y; + + do + { + if (trav->rb_height == 0) + { + trav->rb_node = NULL; + return NULL; + } + + y = x; + x = trav->rb_stack[--trav->rb_height]; + } + while (y == x->rb_link[0]); + } + trav->rb_node = x; + + return x->rb_data; +} + +/* Returns |trav|'s current item. */ +void * +rb_t_cur (struct rb_traverser *trav) +{ + assert (trav != NULL); + + return trav->rb_node != NULL ? trav->rb_node->rb_data : NULL; +} + +/* Replaces the current item in |trav| by |new| and returns the item replaced. + |trav| must not have the null item selected. + The new item must not upset the ordering of the tree. */ +void * +rb_t_replace (struct rb_traverser *trav, void *new) +{ + void *old; + + assert (trav != NULL && trav->rb_node != NULL && new != NULL); + old = trav->rb_node->rb_data; + trav->rb_node->rb_data = new; + return old; +} + +/* Destroys |new| with |rb_destroy (new, destroy)|, + first setting right links of nodes in |stack| within |new| + to null pointers to avoid touching uninitialized data. */ +static void +copy_error_recovery (struct rb_node **stack, int height, + struct rb_table *new, rb_item_func *destroy) +{ + assert (stack != NULL && height >= 0 && new != NULL); + + for (; height > 2; height -= 2) + stack[height - 1]->rb_link[1] = NULL; + rb_destroy (new, destroy); +} + +/* Copies |org| to a newly created tree, which is returned. + If |copy != NULL|, each data item in |org| is first passed to |copy|, + and the return values are inserted into the tree, + with |NULL| return values taken as indications of failure. + On failure, destroys the partially created new tree, + applying |destroy|, if non-null, to each item in the new tree so far, + and returns |NULL|. + If |allocator != NULL|, it is used for allocation in the new tree. + Otherwise, the same allocator used for |org| is used. */ +struct rb_table * +rb_copy (const struct rb_table *org, rb_copy_func *copy, + rb_item_func *destroy, struct libavl_allocator *allocator) +{ + struct rb_node *stack[2 * (RB_MAX_HEIGHT + 1)]; + int height = 0; + + struct rb_table *new; + const struct rb_node *x; + struct rb_node *y; + + assert (org != NULL); + new = rb_create (org->rb_compare, org->rb_param, + allocator != NULL ? allocator : org->rb_alloc); + if (new == NULL) + return NULL; + new->rb_count = org->rb_count; + if (new->rb_count == 0) + return new; + + x = (const struct rb_node *) &org->rb_root; + y = (struct rb_node *) &new->rb_root; + for (;;) + { + while (x->rb_link[0] != NULL) + { + assert (height < 2 * (RB_MAX_HEIGHT + 1)); + + y->rb_link[0] = + new->rb_alloc->libavl_malloc (new->rb_alloc, + sizeof *y->rb_link[0]); + if (y->rb_link[0] == NULL) + { + if (y != (struct rb_node *) &new->rb_root) + { + y->rb_data = NULL; + y->rb_link[1] = NULL; + } + + copy_error_recovery (stack, height, new, destroy); + return NULL; + } + + stack[height++] = (struct rb_node *) x; + stack[height++] = y; + x = x->rb_link[0]; + y = y->rb_link[0]; + } + y->rb_link[0] = NULL; + + for (;;) + { + y->rb_color = x->rb_color; + if (copy == NULL) + y->rb_data = x->rb_data; + else + { + y->rb_data = copy (x->rb_data, org->rb_param); + if (y->rb_data == NULL) + { + y->rb_link[1] = NULL; + copy_error_recovery (stack, height, new, destroy); + return NULL; + } + } + + if (x->rb_link[1] != NULL) + { + y->rb_link[1] = + new->rb_alloc->libavl_malloc (new->rb_alloc, + sizeof *y->rb_link[1]); + if (y->rb_link[1] == NULL) + { + copy_error_recovery (stack, height, new, destroy); + return NULL; + } + + x = x->rb_link[1]; + y = y->rb_link[1]; + break; + } + else + y->rb_link[1] = NULL; + + if (height <= 2) + return new; + + y = stack[--height]; + x = stack[--height]; + } + } +} + +/* Frees storage allocated for |tree|. + If |destroy != NULL|, applies it to each data item in inorder. */ +void +rb_destroy (struct rb_table *tree, rb_item_func *destroy) +{ + struct rb_node *p, *q; + + assert (tree != NULL); + + for (p = tree->rb_root; p != NULL; p = q) + if (p->rb_link[0] == NULL) + { + q = p->rb_link[1]; + if (destroy != NULL && p->rb_data != NULL) + destroy (p->rb_data, tree->rb_param); + tree->rb_alloc->libavl_free (tree->rb_alloc, p); + } + else + { + q = p->rb_link[0]; + p->rb_link[0] = q->rb_link[1]; + q->rb_link[1] = p; + } + + tree->rb_alloc->libavl_free (tree->rb_alloc, tree); +} + +/* Allocates |size| bytes of space using |malloc()|. + Returns a null pointer if allocation fails. */ +void * +rb_malloc (struct libavl_allocator *allocator, size_t size) +{ + assert (allocator != NULL && size > 0); + return malloc (size); +} + +/* Frees |block|. */ +void +rb_free (struct libavl_allocator *allocator, void *block) +{ + assert (allocator != NULL && block != NULL); + free (block); +} + +/* Default memory allocator that uses |malloc()| and |free()|. */ +struct libavl_allocator rb_allocator_default = + { + rb_malloc, + rb_free + }; + +#undef NDEBUG +#include <assert.h> + +/* Asserts that |rb_insert()| succeeds at inserting |item| into |table|. */ +void +(rb_assert_insert) (struct rb_table *table, void *item) +{ + void **p = rb_probe (table, item); + assert (p != NULL && *p == item); +} + +/* Asserts that |rb_delete()| really removes |item| from |table|, + and returns the removed item. */ +void * +(rb_assert_delete) (struct rb_table *table, void *item) +{ + void *p = rb_delete (table, item); + assert (p != NULL); + return p; +} + diff --git a/contrib/rbtree/rb.h b/contrib/rbtree/rb.h new file mode 100644 index 00000000000..c8858b55682 --- /dev/null +++ b/contrib/rbtree/rb.h @@ -0,0 +1,122 @@ +/* Produced by texiweb from libavl.w. */ + +/* libavl - library for manipulation of binary trees. + Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc. + + This program 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 2 of the + License, or (at your option) any later version. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. + + The author may be contacted at <blp@gnu.org> on the Internet, or + write to Ben Pfaff, Stanford University, Computer Science Dept., 353 + Serra Mall, Stanford CA 94305, USA. +*/ + +#ifndef RB_H +#define RB_H 1 + +#include <stddef.h> + +/* Function types. */ +typedef int rb_comparison_func (const void *rb_a, const void *rb_b, + void *rb_param); +typedef void rb_item_func (void *rb_item, void *rb_param); +typedef void *rb_copy_func (void *rb_item, void *rb_param); + +#ifndef LIBAVL_ALLOCATOR +#define LIBAVL_ALLOCATOR +/* Memory allocator. */ +struct libavl_allocator + { + void *(*libavl_malloc) (struct libavl_allocator *, size_t libavl_size); + void (*libavl_free) (struct libavl_allocator *, void *libavl_block); + }; +#endif + +/* Default memory allocator. */ +extern struct libavl_allocator rb_allocator_default; +void *rb_malloc (struct libavl_allocator *, size_t); +void rb_free (struct libavl_allocator *, void *); + +/* Maximum RB height. */ +#ifndef RB_MAX_HEIGHT +#define RB_MAX_HEIGHT 48 +#endif + +/* Tree data structure. */ +struct rb_table + { + struct rb_node *rb_root; /* Tree's root. */ + rb_comparison_func *rb_compare; /* Comparison function. */ + void *rb_param; /* Extra argument to |rb_compare|. */ + struct libavl_allocator *rb_alloc; /* Memory allocator. */ + size_t rb_count; /* Number of items in tree. */ + unsigned long rb_generation; /* Generation number. */ + }; + +/* Color of a red-black node. */ +enum rb_color + { + RB_BLACK, /* Black. */ + RB_RED /* Red. */ + }; + +/* A red-black tree node. */ +struct rb_node + { + struct rb_node *rb_link[2]; /* Subtrees. */ + void *rb_data; /* Pointer to data. */ + unsigned char rb_color; /* Color. */ + }; + +/* RB traverser structure. */ +struct rb_traverser + { + struct rb_table *rb_table; /* Tree being traversed. */ + struct rb_node *rb_node; /* Current node in tree. */ + struct rb_node *rb_stack[RB_MAX_HEIGHT]; + /* All the nodes above |rb_node|. */ + size_t rb_height; /* Number of nodes in |rb_parent|. */ + unsigned long rb_generation; /* Generation number. */ + }; + +/* Table functions. */ +struct rb_table *rb_create (rb_comparison_func *, void *, + struct libavl_allocator *); +struct rb_table *rb_copy (const struct rb_table *, rb_copy_func *, + rb_item_func *, struct libavl_allocator *); +void rb_destroy (struct rb_table *, rb_item_func *); +void **rb_probe (struct rb_table *, void *); +void *rb_insert (struct rb_table *, void *); +void *rb_replace (struct rb_table *, void *); +void *rb_delete (struct rb_table *, const void *); +void *rb_find (const struct rb_table *, const void *); +void rb_assert_insert (struct rb_table *, void *); +void *rb_assert_delete (struct rb_table *, void *); + +#define rb_count(table) ((size_t) (table)->rb_count) + +/* Table traverser functions. */ +void rb_t_init (struct rb_traverser *, struct rb_table *); +void *rb_t_first (struct rb_traverser *, struct rb_table *); +void *rb_t_last (struct rb_traverser *, struct rb_table *); +void *rb_t_find (struct rb_traverser *, struct rb_table *, void *); +void *rb_t_insert (struct rb_traverser *, struct rb_table *, void *); +void *rb_t_copy (struct rb_traverser *, const struct rb_traverser *); +void *rb_t_next (struct rb_traverser *); +void *rb_t_prev (struct rb_traverser *); +void *rb_t_cur (struct rb_traverser *); +void *rb_t_replace (struct rb_traverser *, void *); + +#endif /* rb.h */ diff --git a/libglusterfs/src/Makefile.am b/libglusterfs/src/Makefile.am index 05d124aeea1..90f8b65d532 100644 --- a/libglusterfs/src/Makefile.am +++ b/libglusterfs/src/Makefile.am @@ -1,14 +1,14 @@ libglusterfs_la_CFLAGS = -fPIC -Wall -g -shared -nostartfiles $(GF_CFLAGS) $(GF_DARWIN_LIBGLUSTERFS_CFLAGS) -libglusterfs_la_CPPFLAGS = -D_FILE_OFFSET_BITS=64 -D__USE_FILE_OFFSET64 -D_GNU_SOURCE -DXLATORDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/xlator\" -DSCHEDULERDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/scheduler\" -DTRANSPORTDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/transport\" -D$(GF_HOST_OS) -DLIBDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/auth\" +libglusterfs_la_CPPFLAGS = -D_FILE_OFFSET_BITS=64 -D__USE_FILE_OFFSET64 -D_GNU_SOURCE -DXLATORDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/xlator\" -DSCHEDULERDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/scheduler\" -DTRANSPORTDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/transport\" -D$(GF_HOST_OS) -DLIBDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/auth\" -I$(CONTRIBDIR)/rbtree libglusterfs_la_LIBADD = @LEXLIB@ lib_LTLIBRARIES = libglusterfs.la -libglusterfs_la_SOURCES = dict.c spec.lex.c y.tab.c xlator.c logging.c hashfn.c defaults.c scheduler.c common-utils.c transport.c timer.c inode.c call-stub.c compat.c authenticate.c fd.c compat-errno.c event.c mem-pool.c gf-dirent.c syscall.c iobuf.c globals.c statedump.c stack.c checksum.c md5.c +libglusterfs_la_SOURCES = dict.c spec.lex.c y.tab.c xlator.c logging.c hashfn.c defaults.c scheduler.c common-utils.c transport.c timer.c inode.c call-stub.c compat.c authenticate.c fd.c compat-errno.c event.c mem-pool.c gf-dirent.c syscall.c iobuf.c globals.c statedump.c stack.c checksum.c md5.c $(CONTRIBDIR)/rbtree/rb.c rbthash.c -noinst_HEADERS = common-utils.h defaults.h dict.h glusterfs.h hashfn.h logging.h protocol.h scheduler.h xlator.h transport.h stack.h timer.h list.h inode.h call-stub.h compat.h authenticate.h fd.h revision.h compat-errno.h event.h mem-pool.h byte-order.h gf-dirent.h locking.h syscall.h iobuf.h globals.h statedump.h checksum.h md5.h +noinst_HEADERS = common-utils.h defaults.h dict.h glusterfs.h hashfn.h logging.h protocol.h scheduler.h xlator.h transport.h stack.h timer.h list.h inode.h call-stub.h compat.h authenticate.h fd.h revision.h compat-errno.h event.h mem-pool.h byte-order.h gf-dirent.h locking.h syscall.h iobuf.h globals.h statedump.h checksum.h md5.h $(CONTRIBDIR)/rbtree/rb.h rbthash.h EXTRA_DIST = spec.l spec.y diff --git a/libglusterfs/src/rbthash.c b/libglusterfs/src/rbthash.c new file mode 100644 index 00000000000..829257448ea --- /dev/null +++ b/libglusterfs/src/rbthash.c @@ -0,0 +1,388 @@ +/* + Copyright (c) 2008-2009 Z RESEARCH, Inc. <http://www.zresearch.com> + This file is part of GlusterFS. + + GlusterFS 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 of the License, + or (at your option) any later version. + + GlusterFS 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 this program. If not, see + <http://www.gnu.org/licenses/>. +*/ + + +#include "rbthash.h" +#include "rb.h" +#include "locking.h" +#include "mem-pool.h" +#include "logging.h" + +#include <pthread.h> +#include <string.h> + + +int +rbthash_comparator (void *entry1, void *entry2, void *param) +{ + int ret = 0; + rbthash_entry_t *e1 = NULL; + rbthash_entry_t *e2 = NULL; + + if ((!entry1) || (!entry2) || (!param)) + return -1; + + e1 = (rbthash_entry_t *)entry1; + e2 = (rbthash_entry_t *)entry2; + + if (e1->keylen != e2->keylen) { + if (e1->keylen < e2->keylen) + ret = -1; + else if (e1->keylen > e2->keylen) + ret = 1; + } else + ret = memcmp (e1->key, e2->key, e1->keylen); + + return ret; +} + + +int +__rbthash_init_buckets (rbthash_table_t *tbl, int buckets) +{ + int i = 0; + int ret = -1; + + if (!tbl) + return -1; + + for (; i < buckets; i++) { + LOCK_INIT (&tbl->buckets[i].bucketlock); + tbl->buckets[i].bucket = rb_create ((rb_comparison_func *)rbthash_comparator, tbl, NULL); + if (!tbl->buckets[i].bucket) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to create rb" + " table bucket"); + ret = -1; + goto err; + } + } + + ret = 0; +err: + return ret; +} + + +rbthash_table_t * +rbthash_table_init (int buckets, rbt_hasher_t hfunc, rbt_data_destroyer_t dfunc) +{ + rbthash_table_t *newtab = NULL; + int ret = -1; + + if (!hfunc) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Hash function not given"); + return NULL; + } + + newtab = CALLOC (1, sizeof (*newtab)); + if (!newtab) + return NULL; + + newtab->buckets = CALLOC (buckets, sizeof (struct rbthash_bucket)); + if (!newtab->buckets) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to allocate memory"); + goto free_newtab; + } + + newtab->entrypool = mem_pool_new (rbthash_entry_t, GF_RBTHASH_MEMPOOL); + if (!newtab->entrypool) { + gf_log (GF_RBTHASH, GF_LOG_ERROR,"Failed to allocate mem-pool"); + goto free_buckets; + } + + LOCK_INIT (&newtab->tablelock); + newtab->numbuckets = buckets; + ret = __rbthash_init_buckets (newtab, buckets); + + if (ret == -1) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to init buckets"); + mem_pool_destroy (newtab->entrypool); + } else + gf_log (GF_RBTHASH, GF_LOG_TRACE, "Inited hash table: buckets:" + " %d", buckets); + + newtab->hashfunc = hfunc; + newtab->dfunc = dfunc; +free_buckets: + if (ret == -1) + FREE (newtab->buckets); + +free_newtab: + if (ret == -1) { + FREE (newtab); + newtab = NULL; + } + + return newtab; +} + + +rbthash_entry_t * +rbthash_init_entry (rbthash_table_t *tbl, void *data, void *key, int keylen) +{ + int ret = -1; + rbthash_entry_t *entry = NULL; + + if ((!tbl) || (!data) || (!key)) + return NULL; + + entry = mem_get (tbl->entrypool); + if (!entry) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to get entry from" + " mem-pool"); + goto ret; + } + + entry->data = data; + entry->key = CALLOC (keylen, sizeof (char)); + if (!entry->key) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Memory allocation failed"); + goto free_entry; + } + + memcpy (entry->key, key, keylen); + entry->keylen = keylen; + entry->keyhash = tbl->hashfunc (entry->key, entry->keylen); + gf_log (GF_RBTHASH, GF_LOG_TRACE, "HASH: %u", entry->keyhash); + + ret = 0; +free_entry: + if (ret == -1) { + mem_put (tbl->entrypool, entry); + entry = NULL; + } + +ret: + return entry; +} + + +void +rbthash_deinit_entry (rbthash_table_t *tbl, rbthash_entry_t *entry) +{ + + if (!entry) + return; + + if (entry->key) + FREE (entry->key); + + if (tbl) { + if ((entry->data) && (tbl->dfunc)) + tbl->dfunc (entry->data); + mem_put (tbl->entrypool, entry); + } + + return; +} + + +inline struct rbthash_bucket * +rbthash_entry_bucket (rbthash_table_t *tbl, rbthash_entry_t * entry) +{ + int nbucket = 0; + + nbucket = (entry->keyhash % tbl->numbuckets); + gf_log (GF_RBTHASH, GF_LOG_TRACE, "BUCKET: %d", nbucket); + return &tbl->buckets[nbucket]; +} + + +int +rbthash_insert_entry (rbthash_table_t *tbl, rbthash_entry_t *entry) +{ + struct rbthash_bucket *bucket = NULL; + int ret = -1; + + if ((!tbl) || (!entry)) + return -1; + + bucket = rbthash_entry_bucket (tbl, entry); + if (!bucket) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to get bucket"); + goto err; + } + + ret = 0; + LOCK (&bucket->bucketlock); + { + if (!rb_probe (bucket->bucket, (void *)entry)) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to insert" + " entry"); + ret = -1; + } + } + UNLOCK (&bucket->bucketlock); + +err: + return ret; +} + + +int +rbthash_insert (rbthash_table_t *tbl, void *data, void *key, int keylen) +{ + rbthash_entry_t *entry = NULL; + int ret = -1; + + if ((!tbl) || (!data) || (!key)) + return -1; + + entry = rbthash_init_entry (tbl, data, key, keylen); + if (!entry) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to init entry"); + goto err; + } + + ret = rbthash_insert_entry (tbl, entry); + + if (ret == -1) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to insert entry"); + rbthash_deinit_entry (tbl, entry); + } + +err: + return ret; +} + +inline struct rbthash_bucket * +rbthash_key_bucket (rbthash_table_t *tbl, void *key, int keylen) +{ + uint32_t keyhash = 0; + int nbucket = 0; + + if ((!tbl) || (!key)) + return NULL; + + keyhash = tbl->hashfunc (key, keylen); + gf_log (GF_RBTHASH, GF_LOG_TRACE, "HASH: %u", keyhash); + nbucket = (keyhash % tbl->numbuckets); + gf_log (GF_RBTHASH, GF_LOG_TRACE, "BUCKET: %u", nbucket); + + return &tbl->buckets[nbucket]; +} + + +void * +rbthash_get (rbthash_table_t *tbl, void *key, int keylen) +{ + struct rbthash_bucket *bucket = NULL; + rbthash_entry_t *entry = NULL; + rbthash_entry_t searchentry = {0, }; + + if ((!tbl) || (!key)) + return NULL; + + bucket = rbthash_key_bucket (tbl, key, keylen); + if (!bucket) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to get bucket"); + return NULL; + } + + searchentry.key = key; + searchentry.keylen = keylen; + LOCK (&bucket->bucketlock); + { + entry = rb_find (bucket->bucket, &searchentry); + } + UNLOCK (&bucket->bucketlock); + + if (!entry) + return NULL; + + return entry->data; +} + + +void * +rbthash_remove (rbthash_table_t *tbl, void *key, int keylen) +{ + struct rbthash_bucket *bucket = NULL; + rbthash_entry_t *entry = NULL; + rbthash_entry_t searchentry = {0, }; + void *dataref = NULL; + + if ((!tbl) || (!key)) + return NULL; + + bucket = rbthash_key_bucket (tbl, key, keylen); + if (!bucket) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to get bucket"); + return NULL; + } + + searchentry.key = key; + searchentry.keylen = keylen; + + LOCK (&bucket->bucketlock); + { + entry = rb_delete (bucket->bucket, &searchentry); + } + UNLOCK (&bucket->bucketlock); + + if (!entry) + return NULL; + + FREE (entry->key); + dataref = entry->data; + mem_put (tbl->entrypool, entry); + + return dataref; +} + + +void +rbthash_entry_deiniter (void *entry, void *rbparam) +{ + if (!entry) + return; + + rbthash_deinit_entry (rbparam, entry); +} + + +void +rbthash_table_destroy_buckets (rbthash_table_t *tbl) +{ + int x = 0; + if (!tbl) + return; + + for (;x < tbl->numbuckets; x++) { + LOCK_DESTROY (&tbl->buckets[x].bucketlock); + rb_destroy (tbl->buckets[x].bucket, rbthash_entry_deiniter); + } + + return; +} + + +void +rbthash_table_destroy (rbthash_table_t *tbl) +{ + if (!tbl) + return; + + rbthash_table_destroy_buckets (tbl); + mem_pool_destroy (tbl->entrypool); + + FREE (tbl->buckets); + FREE (tbl); +} + diff --git a/libglusterfs/src/rbthash.h b/libglusterfs/src/rbthash.h new file mode 100644 index 00000000000..5bfa6afd0ef --- /dev/null +++ b/libglusterfs/src/rbthash.h @@ -0,0 +1,75 @@ +/* + Copyright (c) 2008-2009 Z RESEARCH, Inc. <http://www.zresearch.com> + This file is part of GlusterFS. + + GlusterFS 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 of the License, + or (at your option) any later version. + + GlusterFS 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 this program. If not, see + <http://www.gnu.org/licenses/>. +*/ + +#ifndef __RBTHASH_TABLE_H_ +#define __RBTHASH_TABLE_H_ +#include "rb.h" +#include "locking.h" +#include "mem-pool.h" +#include "logging.h" + +#include <pthread.h> + +#define GF_RBTHASH_MEMPOOL 1048576 +#define GF_RBTHASH "rbthash" + +struct rbthash_bucket { + struct rb_table *bucket; + gf_lock_t bucketlock; +}; + +typedef struct rbthash_entry { + void *data; + void *key; + int keylen; + uint32_t keyhash; +} rbthash_entry_t; + +typedef uint32_t (*rbt_hasher_t) (void *data, int len); +typedef void (*rbt_data_destroyer_t) (void *data); + +typedef struct rbthash_table { + int size; + int numbuckets; + struct mem_pool *entrypool; + gf_lock_t tablelock; + struct rbthash_bucket *buckets; + rbt_hasher_t hashfunc; + rbt_data_destroyer_t dfunc; +} rbthash_table_t; + +extern rbthash_table_t * +rbthash_table_init (int buckets, rbt_hasher_t hfunc, + rbt_data_destroyer_t dfunc); + +extern int +rbthash_insert (rbthash_table_t *tbl, void *data, void *key, int keylen); + +extern void * +rbthash_get (rbthash_table_t *tbl, void *key, int keylen); + +extern void * +rbthash_remove (rbthash_table_t *tbl, void *key, int keylen); + +extern void * +rbthash_replace (rbthash_table_t *tbl, void *key, int keylen, void *newdata); + +extern void +rbthash_table_destroy (rbthash_table_t *tbl); +#endif |