diff options
| -rw-r--r-- | isisd/ChangeLog | 8 | ||||
| -rw-r--r-- | isisd/dict.c | 2090 | ||||
| -rw-r--r-- | isisd/dict.h | 128 |
3 files changed, 1022 insertions, 1204 deletions
diff --git a/isisd/ChangeLog b/isisd/ChangeLog index 78dc462b..a695800e 100644 --- a/isisd/ChangeLog +++ b/isisd/ChangeLog @@ -1,3 +1,11 @@ +2005-09-25 Hasso Tepper <hasso at quagga.net> + + * dict.[ch]: Revert all nonfunctional changes. It's external module + imported from kazlib and it's better not to screw it - there is + theoretical chance that we might want to merge changes from upstream + at some point. Also avoid the loss of info about upstream version + (rcsid). + 2005-09-21 Hasso Tepper <hasso at quagga.net> * isis_route.c: Fix output of nexthops in case of extreme debug. diff --git a/isisd/dict.c b/isisd/dict.c index 784ec842..a333d3ef 100644 --- a/isisd/dict.c +++ b/isisd/dict.c @@ -14,7 +14,7 @@ * into proprietary software; there is no requirement for such software to * contain a copyright notice related to this source. * - * $Id: dict.c,v 1.3 2004/11/24 17:14:49 ajs Exp $ + * $Id: dict.c,v 1.4 2005/09/25 12:04:25 hasso Exp $ * $Name: $ */ @@ -25,8 +25,7 @@ #include "dict.h" #ifdef KAZLIB_RCSID -static const char rcsid[] = - "$Id: dict.c,v 1.3 2004/11/24 17:14:49 ajs Exp $"; +static const char rcsid[] = "Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz"; #endif /* @@ -63,8 +62,8 @@ static const char rcsid[] = #define dict_nil(D) (&(D)->nilnode) #define DICT_DEPTH_MAX 64 -static dnode_t *dnode_alloc (void *context); -static void dnode_free (dnode_t * node, void *context); +static dnode_t *dnode_alloc(void *context); +static void dnode_free(dnode_t *node, void *context); /* * Perform a ``left rotation'' adjustment on the tree. The given node P and @@ -73,32 +72,28 @@ static void dnode_free (dnode_t * node, void *context); * for P. The ordering of the keys within the tree is thus preserved. */ -static void -rotate_left (dnode_t * upper) +static void rotate_left(dnode_t *upper) { - dnode_t *lower, *lowleft, *upparent; + dnode_t *lower, *lowleft, *upparent; - lower = upper->right; - upper->right = lowleft = lower->left; - lowleft->parent = upper; + lower = upper->right; + upper->right = lowleft = lower->left; + lowleft->parent = upper; - lower->parent = upparent = upper->parent; + lower->parent = upparent = upper->parent; - /* don't need to check for root node here because root->parent is - the sentinel nil node, and root->parent->left points back to root */ + /* don't need to check for root node here because root->parent is + the sentinel nil node, and root->parent->left points back to root */ - if (upper == upparent->left) - { - upparent->left = lower; - } - else - { - assert (upper == upparent->right); - upparent->right = lower; + if (upper == upparent->left) { + upparent->left = lower; + } else { + assert (upper == upparent->right); + upparent->right = lower; } - lower->left = upper; - upper->parent = lower; + lower->left = upper; + upper->parent = lower; } /* @@ -106,29 +101,25 @@ rotate_left (dnode_t * upper) * the same procedure, but with left and right interchanged. */ -static void -rotate_right (dnode_t * upper) +static void rotate_right(dnode_t *upper) { - dnode_t *lower, *lowright, *upparent; + dnode_t *lower, *lowright, *upparent; - lower = upper->left; - upper->left = lowright = lower->right; - lowright->parent = upper; + lower = upper->left; + upper->left = lowright = lower->right; + lowright->parent = upper; - lower->parent = upparent = upper->parent; + lower->parent = upparent = upper->parent; - if (upper == upparent->right) - { - upparent->right = lower; - } - else - { - assert (upper == upparent->left); - upparent->left = lower; + if (upper == upparent->right) { + upparent->right = lower; + } else { + assert (upper == upparent->left); + upparent->left = lower; } - lower->right = upper; - upper->parent = lower; + lower->right = upper; + upper->parent = lower; } /* @@ -136,14 +127,13 @@ rotate_right (dnode_t * upper) * node and free everything under it. Used by dict_free(). */ -static void -free_nodes (dict_t * dict, dnode_t * node, dnode_t * nil) +static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil) { - if (node == nil) - return; - free_nodes (dict, node->left, nil); - free_nodes (dict, node->right, nil); - dict->freenode (node, dict->context); + if (node == nil) + return; + free_nodes(dict, node->left, nil); + free_nodes(dict, node->right, nil); + dict->freenode(node, dict->context); } /* @@ -155,32 +145,26 @@ free_nodes (dict_t * dict, dnode_t * node, dnode_t * nil) * debugging purposes. */ -static int -verify_bintree (dict_t * dict) +static int verify_bintree(dict_t *dict) { - dnode_t *first, *next; + dnode_t *first, *next; - first = dict_first (dict); + first = dict_first(dict); - if (dict->dupes) - { - while (first && (next = dict_next (dict, first))) - { - if (dict->compare (first->key, next->key) > 0) - return 0; - first = next; + if (dict->dupes) { + while (first && (next = dict_next(dict, first))) { + if (dict->compare(first->key, next->key) > 0) + return 0; + first = next; } - } - else - { - while (first && (next = dict_next (dict, first))) - { - if (dict->compare (first->key, next->key) >= 0) - return 0; - first = next; + } else { + while (first && (next = dict_next(dict, first))) { + if (dict->compare(first->key, next->key) >= 0) + return 0; + first = next; } } - return 1; + return 1; } @@ -197,32 +181,29 @@ verify_bintree (dict_t * dict) * subtree is not red-black. */ -static unsigned int -verify_redblack (dnode_t * nil, dnode_t * root) +static unsigned int verify_redblack(dnode_t *nil, dnode_t *root) { - unsigned height_left, height_right; + unsigned height_left, height_right; - if (root != nil) - { - height_left = verify_redblack (nil, root->left); - height_right = verify_redblack (nil, root->right); - if (height_left == 0 || height_right == 0) - return 0; - if (height_left != height_right) - return 0; - if (root->color == dnode_red) - { - if (root->left->color != dnode_black) + if (root != nil) { + height_left = verify_redblack(nil, root->left); + height_right = verify_redblack(nil, root->right); + if (height_left == 0 || height_right == 0) return 0; - if (root->right->color != dnode_black) + if (height_left != height_right) return 0; - return height_left; + if (root->color == dnode_red) { + if (root->left->color != dnode_black) + return 0; + if (root->right->color != dnode_black) + return 0; + return height_left; } - if (root->color != dnode_black) - return 0; - return height_left + 1; - } - return 1; + if (root->color != dnode_black) + return 0; + return height_left + 1; + } + return 1; } /* @@ -231,14 +212,13 @@ verify_redblack (dnode_t * nil, dnode_t * root) * detect a mismatch. */ -static dictcount_t -verify_node_count (dnode_t * nil, dnode_t * root) +static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root) { - if (root == nil) - return 0; - else - return 1 + verify_node_count (nil, root->left) - + verify_node_count (nil, root->right); + if (root == nil) + return 0; + else + return 1 + verify_node_count(nil, root->left) + + verify_node_count(nil, root->right); } /* @@ -248,58 +228,54 @@ verify_node_count (dnode_t * nil, dnode_t * root) * returns zero. It is intended for debugging purposes. */ -static int -verify_dict_has_node (dnode_t * nil, dnode_t * root, dnode_t * node) +static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node) { - if (root != nil) - { - return root == node - || verify_dict_has_node (nil, root->left, node) - || verify_dict_has_node (nil, root->right, node); + if (root != nil) { + return root == node + || verify_dict_has_node(nil, root->left, node) + || verify_dict_has_node(nil, root->right, node); } - return 0; + return 0; } + /* * Dynamically allocate and initialize a dictionary object. */ -dict_t * -dict_create (dictcount_t maxcount, dict_comp_t comp) +dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp) { - dict_t *new = malloc (sizeof *new); - - if (new) - { - new->compare = comp; - new->allocnode = dnode_alloc; - new->freenode = dnode_free; - new->context = NULL; - new->nodecount = 0; - new->maxcount = maxcount; - new->nilnode.left = &new->nilnode; - new->nilnode.right = &new->nilnode; - new->nilnode.parent = &new->nilnode; - new->nilnode.color = dnode_black; - new->dupes = 0; + dict_t *new = malloc(sizeof *new); + + if (new) { + new->compare = comp; + new->allocnode = dnode_alloc; + new->freenode = dnode_free; + new->context = NULL; + new->nodecount = 0; + new->maxcount = maxcount; + new->nilnode.left = &new->nilnode; + new->nilnode.right = &new->nilnode; + new->nilnode.parent = &new->nilnode; + new->nilnode.color = dnode_black; + new->dupes = 0; } - return new; + return new; } /* * Select a different set of node allocator routines. */ -void -dict_set_allocator (dict_t * dict, dnode_alloc_t al, - dnode_free_t fr, void *context) +void dict_set_allocator(dict_t *dict, dnode_alloc_t al, + dnode_free_t fr, void *context) { - assert (dict_count (dict) == 0); - assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL)); + assert (dict_count(dict) == 0); + assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL)); - dict->allocnode = al ? al : dnode_alloc; - dict->freenode = fr ? fr : dnode_free; - dict->context = context; + dict->allocnode = al ? al : dnode_alloc; + dict->freenode = fr ? fr : dnode_free; + dict->context = context; } /* @@ -307,11 +283,10 @@ dict_set_allocator (dict_t * dict, dnode_alloc_t al, * from the tree before deleting it is required. */ -void -dict_destroy (dict_t * dict) +void dict_destroy(dict_t *dict) { - assert (dict_isempty (dict)); - free (dict); + assert (dict_isempty(dict)); + free(dict); } /* @@ -319,117 +294,112 @@ dict_destroy (dict_t * dict) * installed free routine. The dictionary is emptied. */ -void -dict_free_nodes (dict_t * dict) +void dict_free_nodes(dict_t *dict) { - dnode_t *nil = dict_nil (dict), *root = dict_root (dict); - free_nodes (dict, root, nil); - dict->nodecount = 0; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; + dnode_t *nil = dict_nil(dict), *root = dict_root(dict); + free_nodes(dict, root, nil); + dict->nodecount = 0; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; } /* * Obsolescent function, equivalent to dict_free_nodes */ -void -dict_free (dict_t * dict) +void dict_free(dict_t *dict) { #ifdef KAZLIB_OBSOLESCENT_DEBUG - assert ("call to obsolescent function dict_free()" && 0); + assert ("call to obsolescent function dict_free()" && 0); #endif - dict_free_nodes (dict); + dict_free_nodes(dict); } /* * Initialize a user-supplied dictionary object. */ -dict_t * -dict_init (dict_t * dict, dictcount_t maxcount, dict_comp_t comp) +dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp) { - dict->compare = comp; - dict->allocnode = dnode_alloc; - dict->freenode = dnode_free; - dict->context = NULL; - dict->nodecount = 0; - dict->maxcount = maxcount; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; - dict->nilnode.parent = &dict->nilnode; - dict->nilnode.color = dnode_black; - dict->dupes = 0; - return dict; + dict->compare = comp; + dict->allocnode = dnode_alloc; + dict->freenode = dnode_free; + dict->context = NULL; + dict->nodecount = 0; + dict->maxcount = maxcount; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; + dict->nilnode.parent = &dict->nilnode; + dict->nilnode.color = dnode_black; + dict->dupes = 0; + return dict; } /* * Initialize a dictionary in the likeness of another dictionary */ -void -dict_init_like (dict_t * dict, const dict_t * template) +void dict_init_like(dict_t *dict, const dict_t *template) { - dict->compare = template->compare; - dict->allocnode = template->allocnode; - dict->freenode = template->freenode; - dict->context = template->context; - dict->nodecount = 0; - dict->maxcount = template->maxcount; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; - dict->nilnode.parent = &dict->nilnode; - dict->nilnode.color = dnode_black; - dict->dupes = template->dupes; - - assert (dict_similar (dict, template)); + dict->compare = template->compare; + dict->allocnode = template->allocnode; + dict->freenode = template->freenode; + dict->context = template->context; + dict->nodecount = 0; + dict->maxcount = template->maxcount; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; + dict->nilnode.parent = &dict->nilnode; + dict->nilnode.color = dnode_black; + dict->dupes = template->dupes; + + assert (dict_similar(dict, template)); } /* * Remove all nodes from the dictionary (without freeing them in any way). */ -static void -dict_clear (dict_t * dict) +static void dict_clear(dict_t *dict) { - dict->nodecount = 0; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; - dict->nilnode.parent = &dict->nilnode; - assert (dict->nilnode.color == dnode_black); + dict->nodecount = 0; + dict->nilnode.left = &dict->nilnode; + dict->nilnode.right = &dict->nilnode; + dict->nilnode.parent = &dict->nilnode; + assert (dict->nilnode.color == dnode_black); } + /* * Verify the integrity of the dictionary structure. This is provided for * debugging purposes, and should be placed in assert statements. Just because * this function succeeds doesn't mean that the tree is not corrupt. Certain * corruptions in the tree may simply cause undefined behavior. - */ + */ -int -dict_verify (dict_t * dict) +int dict_verify(dict_t *dict) { - dnode_t *nil = dict_nil (dict), *root = dict_root (dict); + dnode_t *nil = dict_nil(dict), *root = dict_root(dict); - /* check that the sentinel node and root node are black */ - if (root->color != dnode_black) - return 0; - if (nil->color != dnode_black) - return 0; - if (nil->right != nil) - return 0; - /* nil->left is the root node; check that its parent pointer is nil */ - if (nil->left->parent != nil) - return 0; - /* perform a weak test that the tree is a binary search tree */ - if (!verify_bintree (dict)) - return 0; - /* verify that the tree is a red-black tree */ - if (!verify_redblack (nil, root)) - return 0; - if (verify_node_count (nil, root) != dict_count (dict)) - return 0; - return 1; + /* check that the sentinel node and root node are black */ + if (root->color != dnode_black) + return 0; + if (nil->color != dnode_black) + return 0; + if (nil->right != nil) + return 0; + /* nil->left is the root node; check that its parent pointer is nil */ + if (nil->left->parent != nil) + return 0; + /* perform a weak test that the tree is a binary search tree */ + if (!verify_bintree(dict)) + return 0; + /* verify that the tree is a red-black tree */ + if (!verify_redblack(nil, root)) + return 0; + if (verify_node_count(nil, root) != dict_count(dict)) + return 0; + return 1; } /* @@ -437,25 +407,24 @@ dict_verify (dict_t * dict) * allocator functions, and same status as to whether duplicates are allowed. */ -int -dict_similar (const dict_t * left, const dict_t * right) +int dict_similar(const dict_t *left, const dict_t *right) { - if (left->compare != right->compare) - return 0; + if (left->compare != right->compare) + return 0; - if (left->allocnode != right->allocnode) - return 0; + if (left->allocnode != right->allocnode) + return 0; - if (left->freenode != right->freenode) - return 0; + if (left->freenode != right->freenode) + return 0; - if (left->context != right->context) - return 0; + if (left->context != right->context) + return 0; - if (left->dupes != right->dupes) - return 0; + if (left->dupes != right->dupes) + return 0; - return 1; + return 1; } /* @@ -465,45 +434,37 @@ dict_similar (const dict_t * left, const dict_t * right) * located node is returned. */ -dnode_t * -dict_lookup (dict_t * dict, const void *key) +dnode_t *dict_lookup(dict_t *dict, const void *key) { - dnode_t *root = dict_root (dict); - dnode_t *nil = dict_nil (dict); - dnode_t *saved; - int result; - - /* simple binary search adapted for trees that contain duplicate keys */ - - while (root != nil) - { - result = dict->compare (key, root->key); - if (result < 0) - root = root->left; - else if (result > 0) - root = root->right; - else - { - if (!dict->dupes) - { /* no duplicates, return match */ - return root; - } - else - { /* could be dupes, find leftmost one */ - do - { - saved = root; - root = root->left; - while (root != nil && dict->compare (key, root->key)) - root = root->right; - } - while (root != nil); - return saved; + dnode_t *root = dict_root(dict); + dnode_t *nil = dict_nil(dict); + dnode_t *saved; + int result; + + /* simple binary search adapted for trees that contain duplicate keys */ + + while (root != nil) { + result = dict->compare(key, root->key); + if (result < 0) + root = root->left; + else if (result > 0) + root = root->right; + else { + if (!dict->dupes) { /* no duplicates, return match */ + return root; + } else { /* could be dupes, find leftmost one */ + do { + saved = root; + root = root->left; + while (root != nil && dict->compare(key, root->key)) + root = root->right; + } while (root != nil); + return saved; } } } - return NULL; + return NULL; } /* @@ -511,41 +472,31 @@ dict_lookup (dict_t * dict, const void *key) * greater than the given key. If there is no such node, return null. */ -dnode_t * -dict_lower_bound (dict_t * dict, const void *key) +dnode_t *dict_lower_bound(dict_t *dict, const void *key) { - dnode_t *root = dict_root (dict); - dnode_t *nil = dict_nil (dict); - dnode_t *tentative = 0; - - while (root != nil) - { - int result = dict->compare (key, root->key); - - if (result > 0) - { - root = root->right; - } - else if (result < 0) - { - tentative = root; - root = root->left; - } - else - { - if (!dict->dupes) - { - return root; + dnode_t *root = dict_root(dict); + dnode_t *nil = dict_nil(dict); + dnode_t *tentative = 0; + + while (root != nil) { + int result = dict->compare(key, root->key); + + if (result > 0) { + root = root->right; + } else if (result < 0) { + tentative = root; + root = root->left; + } else { + if (!dict->dupes) { + return root; + } else { + tentative = root; + root = root->left; } - else - { - tentative = root; - root = root->left; - } - } + } } - - return tentative; + + return tentative; } /* @@ -553,41 +504,31 @@ dict_lower_bound (dict_t * dict, const void *key) * lower than the given key. If there is no such node, return null. */ -dnode_t * -dict_upper_bound (dict_t * dict, const void *key) +dnode_t *dict_upper_bound(dict_t *dict, const void *key) { - dnode_t *root = dict_root (dict); - dnode_t *nil = dict_nil (dict); - dnode_t *tentative = 0; - - while (root != nil) - { - int result = dict->compare (key, root->key); - - if (result < 0) - { - root = root->left; - } - else if (result > 0) - { - tentative = root; - root = root->right; - } - else - { - if (!dict->dupes) - { - return root; - } - else - { - tentative = root; - root = root->right; + dnode_t *root = dict_root(dict); + dnode_t *nil = dict_nil(dict); + dnode_t *tentative = 0; + + while (root != nil) { + int result = dict->compare(key, root->key); + + if (result < 0) { + root = root->left; + } else if (result > 0) { + tentative = root; + root = root->right; + } else { + if (!dict->dupes) { + return root; + } else { + tentative = root; + root = root->right; } - } + } } - - return tentative; + + return tentative; } /* @@ -598,109 +539,95 @@ dict_upper_bound (dict_t * dict, const void *key) * function returns true). */ -void -dict_insert (dict_t * dict, dnode_t * node, const void *key) +void dict_insert(dict_t *dict, dnode_t *node, const void *key) { - dnode_t *where = dict_root (dict), *nil = dict_nil (dict); - dnode_t *parent = nil, *uncle, *grandpa; - int result = -1; - - node->key = key; - - assert (!dict_isfull (dict)); - assert (!dict_contains (dict, node)); - assert (!dnode_is_in_a_dict (node)); - - /* basic binary tree insert */ - - while (where != nil) - { - parent = where; - result = dict->compare (key, where->key); - /* trap attempts at duplicate key insertion unless it's explicitly allowed */ - assert (dict->dupes || result != 0); - if (result < 0) - where = where->left; - else - where = where->right; + dnode_t *where = dict_root(dict), *nil = dict_nil(dict); + dnode_t *parent = nil, *uncle, *grandpa; + int result = -1; + + node->key = key; + + assert (!dict_isfull(dict)); + assert (!dict_contains(dict, node)); + assert (!dnode_is_in_a_dict(node)); + + /* basic binary tree insert */ + + while (where != nil) { + parent = where; + result = dict->compare(key, where->key); + /* trap attempts at duplicate key insertion unless it's explicitly allowed */ + assert (dict->dupes || result != 0); + if (result < 0) + where = where->left; + else + where = where->right; } - assert (where == nil); - - if (result < 0) - parent->left = node; - else - parent->right = node; - - node->parent = parent; - node->left = nil; - node->right = nil; - - dict->nodecount++; - - /* red black adjustments */ - - node->color = dnode_red; - - while (parent->color == dnode_red) - { - grandpa = parent->parent; - if (parent == grandpa->left) - { - uncle = grandpa->right; - if (uncle->color == dnode_red) - { /* red parent, red uncle */ - parent->color = dnode_black; - uncle->color = dnode_black; - grandpa->color = dnode_red; - node = grandpa; - parent = grandpa->parent; - } - else - { /* red parent, black uncle */ - if (node == parent->right) - { - rotate_left (parent); - parent = node; - assert (grandpa == parent->parent); - /* rotation between parent and child preserves grandpa */ + assert (where == nil); + + if (result < 0) + parent->left = node; + else + parent->right = node; + + node->parent = parent; + node->left = nil; + node->right = nil; + + dict->nodecount++; + + /* red black adjustments */ + + node->color = dnode_red; + + while (parent->color == dnode_red) { + grandpa = parent->parent; + if (parent == grandpa->left) { + uncle = grandpa->right; + if (uncle->color == dnode_red) { /* red parent, red uncle */ + parent->color = dnode_black; + uncle->color = dnode_black; + grandpa->color = dnode_red; + node = grandpa; + parent = grandpa->parent; + } else { /* red parent, black uncle */ + if (node == parent->right) { + rotate_left(parent); + parent = node; + assert (grandpa == parent->parent); + /* rotation between parent and child preserves grandpa */ } - parent->color = dnode_black; - grandpa->color = dnode_red; - rotate_right (grandpa); - break; - } - } - else - { /* symmetric cases: parent == parent->parent->right */ - uncle = grandpa->left; - if (uncle->color == dnode_red) - { - parent->color = dnode_black; - uncle->color = dnode_black; - grandpa->color = dnode_red; - node = grandpa; - parent = grandpa->parent; + parent->color = dnode_black; + grandpa->color = dnode_red; + rotate_right(grandpa); + break; } - else - { - if (node == parent->left) - { - rotate_right (parent); - parent = node; - assert (grandpa == parent->parent); + } else { /* symmetric cases: parent == parent->parent->right */ + uncle = grandpa->left; + if (uncle->color == dnode_red) { + parent->color = dnode_black; + uncle->color = dnode_black; + grandpa->color = dnode_red; + node = grandpa; + parent = grandpa->parent; + } else { + if (node == parent->left) { + rotate_right(parent); + parent = node; + assert (grandpa == parent->parent); } - parent->color = dnode_black; - grandpa->color = dnode_red; - rotate_left (grandpa); - break; + parent->color = dnode_black; + grandpa->color = dnode_red; + rotate_left(grandpa); + break; } } } - dict_root (dict)->color = dnode_black; + dict_root(dict)->color = dnode_black; - assert (dict_verify (dict)); + assert (dict_verify(dict)); } /* @@ -709,201 +636,173 @@ dict_insert (dict_t * dict, dnode_t * node, const void *key) * deleted node is returned. */ -dnode_t * -dict_delete (dict_t * dict, dnode_t * delete) +dnode_t *dict_delete(dict_t *dict, dnode_t *delete) { - dnode_t *nil = dict_nil (dict), *child, *delparent = delete->parent; - - /* basic deletion */ - - assert (!dict_isempty (dict)); - assert (dict_contains (dict, delete)); - - /* - * If the node being deleted has two children, then we replace it with its - * successor (i.e. the leftmost node in the right subtree.) By doing this, - * we avoid the traditional algorithm under which the successor's key and - * value *only* move to the deleted node and the successor is spliced out - * from the tree. We cannot use this approach because the user may hold - * pointers to the successor, or nodes may be inextricably tied to some - * other structures by way of embedding, etc. So we must splice out the - * node we are given, not some other node, and must not move contents from - * one node to another behind the user's back. - */ - - if (delete->left != nil && delete->right != nil) - { - dnode_t *next = dict_next (dict, delete); - dnode_t *nextparent = next->parent; - dnode_color_t nextcolor = next->color; - - assert (next != nil); - assert (next->parent != nil); - assert (next->left == nil); - - /* - * First, splice out the successor from the tree completely, by - * moving up its right child into its place. - */ - - child = next->right; - child->parent = nextparent; - - if (nextparent->left == next) - { - nextparent->left = child; + dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; + + /* basic deletion */ + + assert (!dict_isempty(dict)); + assert (dict_contains(dict, delete)); + + /* + * If the node being deleted has two children, then we replace it with its + * successor (i.e. the leftmost node in the right subtree.) By doing this, + * we avoid the traditional algorithm under which the successor's key and + * value *only* move to the deleted node and the successor is spliced out + * from the tree. We cannot use this approach because the user may hold + * pointers to the successor, or nodes may be inextricably tied to some + * other structures by way of embedding, etc. So we must splice out the + * node we are given, not some other node, and must not move contents from + * one node to another behind the user's back. + */ + + if (delete->left != nil && delete->right != nil) { + dnode_t *next = dict_next(dict, delete); + dnode_t *nextparent = next->parent; + dnode_color_t nextcolor = next->color; + + assert (next != nil); + assert (next->parent != nil); + assert (next->left == nil); + + /* + * First, splice out the successor from the tree completely, by + * moving up its right child into its place. + */ + + child = next->right; + child->parent = nextparent; + + if (nextparent->left == next) { + nextparent->left = child; + } else { + assert (nextparent->right == next); + nextparent->right = child; } - else - { - assert (nextparent->right == next); - nextparent->right = child; - } - - /* - * Now that the successor has been extricated from the tree, install it - * in place of the node that we want deleted. - */ - next->parent = delparent; - next->left = delete->left; - next->right = delete->right; - next->left->parent = next; - next->right->parent = next; - next->color = delete->color; - delete->color = nextcolor; - - if (delparent->left == delete) - { - delparent->left = next; - } - else - { - assert (delparent->right == delete); - delparent->right = next; + /* + * Now that the successor has been extricated from the tree, install it + * in place of the node that we want deleted. + */ + + next->parent = delparent; + next->left = delete->left; + next->right = delete->right; + next->left->parent = next; + next->right->parent = next; + next->color = delete->color; + delete->color = nextcolor; + + if (delparent->left == delete) { + delparent->left = next; + } else { + assert (delparent->right == delete); + delparent->right = next; } - } - else - { - assert (delete != nil); - assert (delete->left == nil || delete->right == nil); + } else { + assert (delete != nil); + assert (delete->left == nil || delete->right == nil); - child = (delete->left != nil) ? delete->left : delete->right; + child = (delete->left != nil) ? delete->left : delete->right; - child->parent = delparent = delete->parent; + child->parent = delparent = delete->parent; - if (delete == delparent->left) - { - delparent->left = child; - } - else - { - assert (delete == delparent->right); - delparent->right = child; + if (delete == delparent->left) { + delparent->left = child; + } else { + assert (delete == delparent->right); + delparent->right = child; } } - delete->parent = NULL; - delete->right = NULL; - delete->left = NULL; + delete->parent = NULL; + delete->right = NULL; + delete->left = NULL; - dict->nodecount--; + dict->nodecount--; - assert (verify_bintree (dict)); + assert (verify_bintree(dict)); - /* red-black adjustments */ + /* red-black adjustments */ - if (delete->color == dnode_black) - { - dnode_t *parent, *sister; + if (delete->color == dnode_black) { + dnode_t *parent, *sister; - dict_root (dict)->color = dnode_red; + dict_root(dict)->color = dnode_red; - while (child->color == dnode_black) - { - parent = child->parent; - if (child == parent->left) - { - sister = parent->right; - assert (sister != nil); - if (sister->color == dnode_red) - { - sister->color = dnode_black; - parent->color = dnode_red; - rotate_left (parent); - sister = parent->right; - assert (sister != nil); - } - if (sister->left->color == dnode_black - && sister->right->color == dnode_black) - { - sister->color = dnode_red; - child = parent; + while (child->color == dnode_black) { + parent = child->parent; + if (child == parent->left) { + sister = parent->right; + assert (sister != nil); + if (sister->color == dnode_red) { + sister->color = dnode_black; + parent->color = dnode_red; + rotate_left(parent); + sister = parent->right; + assert (sister != nil); } - else - { - if (sister->right->color == dnode_black) - { - assert (sister->left->color == dnode_red); - sister->left->color = dnode_black; - sister->color = dnode_red; - rotate_right (sister); - sister = parent->right; - assert (sister != nil); + if (sister->left->color == dnode_black + && sister->right->color == dnode_black) { + sister->color = dnode_red; + child = parent; + } else { + if (sister->right->color == dnode_black) { + assert (sister->left->color == dnode_red); + sister->left->color = dnode_black; + sister->color = dnode_red; + rotate_right(sister); + sister = parent->right; + assert (sister != nil); } - sister->color = parent->color; - sister->right->color = dnode_black; - parent->color = dnode_black; - rotate_left (parent); - break; + sister->color = parent->color; + sister->right->color = dnode_black; + parent->color = dnode_black; + rotate_left(parent); + break; } - } - else - { /* symmetric case: child == child->parent->right */ - assert (child == parent->right); - sister = parent->left; - assert (sister != nil); - if (sister->color == dnode_red) - { - sister->color = dnode_black; - parent->color = dnode_red; - rotate_right (parent); - sister = parent->left; - assert (sister != nil); - } - if (sister->right->color == dnode_black - && sister->left->color == dnode_black) - { - sister->color = dnode_red; - child = parent; + } else { /* symmetric case: child == child->parent->right */ + assert (child == parent->right); + sister = parent->left; + assert (sister != nil); + if (sister->color == dnode_red) { + sister->color = dnode_black; + parent->color = dnode_red; + rotate_right(parent); + sister = parent->left; + assert (sister != nil); } - else - { - if (sister->left->color == dnode_black) - { - assert (sister->right->color == dnode_red); - sister->right->color = dnode_black; - sister->color = dnode_red; - rotate_left (sister); - sister = parent->left; - assert (sister != nil); + if (sister->right->color == dnode_black + && sister->left->color == dnode_black) { + sister->color = dnode_red; + child = parent; + } else { + if (sister->left->color == dnode_black) { + assert (sister->right->color == dnode_red); + sister->right->color = dnode_black; + sister->color = dnode_red; + rotate_left(sister); + sister = parent->left; + assert (sister != nil); } - sister->color = parent->color; - sister->left->color = dnode_black; - parent->color = dnode_black; - rotate_right (parent); - break; + sister->color = parent->color; + sister->left->color = dnode_black; + parent->color = dnode_black; + rotate_right(parent); + break; } } } - child->color = dnode_black; - dict_root (dict)->color = dnode_black; + child->color = dnode_black; + dict_root(dict)->color = dnode_black; } - assert (dict_verify (dict)); + assert (dict_verify(dict)); - return delete; + return delete; } /* @@ -911,25 +810,22 @@ dict_delete (dict_t * dict, dnode_t * delete) * the data item. */ -int -dict_alloc_insert (dict_t * dict, const void *key, void *data) +int dict_alloc_insert(dict_t *dict, const void *key, void *data) { - dnode_t *node = dict->allocnode (dict->context); + dnode_t *node = dict->allocnode(dict->context); - if (node) - { - dnode_init (node, data); - dict_insert (dict, node, key); - return 1; + if (node) { + dnode_init(node, data); + dict_insert(dict, node, key); + return 1; } - return 0; + return 0; } -void -dict_delete_free (dict_t * dict, dnode_t * node) +void dict_delete_free(dict_t *dict, dnode_t *node) { - dict_delete (dict, node); - dict->freenode (node, dict->context); + dict_delete(dict, node); + dict->freenode(node, dict->context); } /* @@ -937,16 +833,15 @@ dict_delete_free (dict_t * dict, dnode_t * node) * (that is, dict_isempty(dict) returns 1) a null pointer is returned. */ -dnode_t * -dict_first (dict_t * dict) +dnode_t *dict_first(dict_t *dict) { - dnode_t *nil = dict_nil (dict), *root = dict_root (dict), *left; + dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; - if (root != nil) - while ((left = root->left) != nil) - root = left; + if (root != nil) + while ((left = root->left) != nil) + root = left; - return (root == nil) ? NULL : root; + return (root == nil) ? NULL : root; } /* @@ -954,16 +849,15 @@ dict_first (dict_t * dict) * (that is, dict_isempty(dict) returns 1) a null pointer is returned. */ -dnode_t * -dict_last (dict_t * dict) +dnode_t *dict_last(dict_t *dict) { - dnode_t *nil = dict_nil (dict), *root = dict_root (dict), *right; + dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right; - if (root != nil) - while ((right = root->right) != nil) - root = right; + if (root != nil) + while ((right = root->right) != nil) + root = right; - return (root == nil) ? NULL : root; + return (root == nil) ? NULL : root; } /* @@ -973,28 +867,25 @@ dict_last (dict_t * dict) * the nil node. */ -dnode_t * -dict_next (dict_t * dict, dnode_t * curr) +dnode_t *dict_next(dict_t *dict, dnode_t *curr) { - dnode_t *nil = dict_nil (dict), *parent, *left; - - if (curr->right != nil) - { - curr = curr->right; - while ((left = curr->left) != nil) - curr = left; - return curr; + dnode_t *nil = dict_nil(dict), *parent, *left; + + if (curr->right != nil) { + curr = curr->right; + while ((left = curr->left) != nil) + curr = left; + return curr; } - parent = curr->parent; + parent = curr->parent; - while (parent != nil && curr == parent->right) - { - curr = parent; - parent = curr->parent; + while (parent != nil && curr == parent->right) { + curr = parent; + parent = curr->parent; } - return (parent == nil) ? NULL : parent; + return (parent == nil) ? NULL : parent; } /* @@ -1002,34 +893,30 @@ dict_next (dict_t * dict, dnode_t * curr) * The nil sentinel node is returned if there is no predecessor. */ -dnode_t * -dict_prev (dict_t * dict, dnode_t * curr) +dnode_t *dict_prev(dict_t *dict, dnode_t *curr) { - dnode_t *nil = dict_nil (dict), *parent, *right; - - if (curr->left != nil) - { - curr = curr->left; - while ((right = curr->right) != nil) - curr = right; - return curr; + dnode_t *nil = dict_nil(dict), *parent, *right; + + if (curr->left != nil) { + curr = curr->left; + while ((right = curr->right) != nil) + curr = right; + return curr; } - parent = curr->parent; + parent = curr->parent; - while (parent != nil && curr == parent->left) - { - curr = parent; - parent = curr->parent; + while (parent != nil && curr == parent->left) { + curr = parent; + parent = curr->parent; } - return (parent == nil) ? NULL : parent; + return (parent == nil) ? NULL : parent; } -void -dict_allow_dupes (dict_t * dict) +void dict_allow_dupes(dict_t *dict) { - dict->dupes = 1; + dict->dupes = 1; } #undef dict_count @@ -1039,308 +926,268 @@ dict_allow_dupes (dict_t * dict) #undef dnode_put #undef dnode_getkey -dictcount_t -dict_count (dict_t * dict) +dictcount_t dict_count(dict_t *dict) { - return dict->nodecount; + return dict->nodecount; } -int -dict_isempty (dict_t * dict) +int dict_isempty(dict_t *dict) { - return dict->nodecount == 0; + return dict->nodecount == 0; } -int -dict_isfull (dict_t * dict) +int dict_isfull(dict_t *dict) { - return dict->nodecount == dict->maxcount; + return dict->nodecount == dict->maxcount; } -int -dict_contains (dict_t * dict, dnode_t * node) +int dict_contains(dict_t *dict, dnode_t *node) { - return verify_dict_has_node (dict_nil (dict), dict_root (dict), node); + return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); } -static dnode_t * -dnode_alloc (void *context) +static dnode_t *dnode_alloc(void *context) { - return malloc (sizeof *dnode_alloc (NULL)); + return malloc(sizeof *dnode_alloc(NULL)); } -static void -dnode_free (dnode_t * node, void *context) +static void dnode_free(dnode_t *node, void *context) { - free (node); + free(node); } -dnode_t * -dnode_create (void *data) +dnode_t *dnode_create(void *data) { - dnode_t *new = malloc (sizeof *new); - if (new) - { - new->data = data; - new->parent = NULL; - new->left = NULL; - new->right = NULL; + dnode_t *new = malloc(sizeof *new); + if (new) { + new->data = data; + new->parent = NULL; + new->left = NULL; + new->right = NULL; } - return new; + return new; } -dnode_t * -dnode_init (dnode_t * dnode, void *data) +dnode_t *dnode_init(dnode_t *dnode, void *data) { - dnode->data = data; - dnode->parent = NULL; - dnode->left = NULL; - dnode->right = NULL; - return dnode; + dnode->data = data; + dnode->parent = NULL; + dnode->left = NULL; + dnode->right = NULL; + return dnode; } -void -dnode_destroy (dnode_t * dnode) +void dnode_destroy(dnode_t *dnode) { - assert (!dnode_is_in_a_dict (dnode)); - free (dnode); + assert (!dnode_is_in_a_dict(dnode)); + free(dnode); } -void * -dnode_get (dnode_t * dnode) +void *dnode_get(dnode_t *dnode) { - return dnode->data; + return dnode->data; } -const void * -dnode_getkey (dnode_t * dnode) +const void *dnode_getkey(dnode_t *dnode) { - return dnode->key; + return dnode->key; } -void -dnode_put (dnode_t * dnode, void *data) +void dnode_put(dnode_t *dnode, void *data) { - dnode->data = data; + dnode->data = data; } -int -dnode_is_in_a_dict (dnode_t * dnode) +int dnode_is_in_a_dict(dnode_t *dnode) { - return (dnode->parent && dnode->left && dnode->right); + return (dnode->parent && dnode->left && dnode->right); } -void -dict_process (dict_t * dict, void *context, dnode_process_t function) +void dict_process(dict_t *dict, void *context, dnode_process_t function) { - dnode_t *node = dict_first (dict), *next; - - while (node != NULL) - { - /* check for callback function deleting */ - /* the next node from under us */ - assert (dict_contains (dict, node)); - next = dict_next (dict, node); - function (dict, node, context); - node = next; + dnode_t *node = dict_first(dict), *next; + + while (node != NULL) { + /* check for callback function deleting */ + /* the next node from under us */ + assert (dict_contains(dict, node)); + next = dict_next(dict, node); + function(dict, node, context); + node = next; } } -static void -load_begin_internal (dict_load_t * load, dict_t * dict) +static void load_begin_internal(dict_load_t *load, dict_t *dict) { - load->dictptr = dict; - load->nilnode.left = &load->nilnode; - load->nilnode.right = &load->nilnode; + load->dictptr = dict; + load->nilnode.left = &load->nilnode; + load->nilnode.right = &load->nilnode; } -void -dict_load_begin (dict_load_t * load, dict_t * dict) +void dict_load_begin(dict_load_t *load, dict_t *dict) { - assert (dict_isempty (dict)); - load_begin_internal (load, dict); + assert (dict_isempty(dict)); + load_begin_internal(load, dict); } -void -dict_load_next (dict_load_t * load, dnode_t * newnode, const void *key) +void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key) { - dict_t *dict = load->dictptr; - dnode_t *nil = &load->nilnode; - - assert (!dnode_is_in_a_dict (newnode)); - assert (dict->nodecount < dict->maxcount); - -#ifndef NDEBUG - if (dict->nodecount > 0) - { - if (dict->dupes) - assert (dict->compare (nil->left->key, key) <= 0); - else - assert (dict->compare (nil->left->key, key) < 0); + dict_t *dict = load->dictptr; + dnode_t *nil = &load->nilnode; + + assert (!dnode_is_in_a_dict(newnode)); + assert (dict->nodecount < dict->maxcount); + + #ifndef NDEBUG + if (dict->nodecount > 0) { + if (dict->dupes) + assert (dict->compare(nil->left->key, key) <= 0); + else + assert (dict->compare(nil->left->key, key) < 0); } -#endif + #endif - newnode->key = key; - nil->right->left = newnode; - nil->right = newnode; - newnode->left = nil; - dict->nodecount++; + newnode->key = key; + nil->right->left = newnode; + nil->right = newnode; + newnode->left = nil; + dict->nodecount++; } -void -dict_load_end (dict_load_t * load) +void dict_load_end(dict_load_t *load) { - dict_t *dict = load->dictptr; - dnode_t *tree[DICT_DEPTH_MAX] = { 0 }; - dnode_t *curr, *dictnil = dict_nil (dict), *loadnil = &load->nilnode, *next; - dnode_t *complete = 0; - dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; - dictcount_t botrowcount; - unsigned baselevel = 0, level = 0, i; - - assert (dnode_red == 0 && dnode_black == 1); - - while (fullcount >= nodecount && fullcount) - fullcount >>= 1; - - botrowcount = nodecount - fullcount; - - for (curr = loadnil->left; curr != loadnil; curr = next) - { - next = curr->left; - - if (complete == NULL && botrowcount-- == 0) - { - assert (baselevel == 0); - assert (level == 0); - baselevel = level = 1; - complete = tree[0]; - - if (complete != 0) - { - tree[0] = 0; - complete->right = dictnil; - while (tree[level] != 0) - { - tree[level]->right = complete; - complete->parent = tree[level]; - complete = tree[level]; - tree[level++] = 0; + dict_t *dict = load->dictptr; + dnode_t *tree[DICT_DEPTH_MAX] = { 0 }; + dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next; + dnode_t *complete = 0; + dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; + dictcount_t botrowcount; + unsigned baselevel = 0, level = 0, i; + + assert (dnode_red == 0 && dnode_black == 1); + + while (fullcount >= nodecount && fullcount) + fullcount >>= 1; + + botrowcount = nodecount - fullcount; + + for (curr = loadnil->left; curr != loadnil; curr = next) { + next = curr->left; + + if (complete == NULL && botrowcount-- == 0) { + assert (baselevel == 0); + assert (level == 0); + baselevel = level = 1; + complete = tree[0]; + + if (complete != 0) { + tree[0] = 0; + complete->right = dictnil; + while (tree[level] != 0) { + tree[level]->right = complete; + complete->parent = tree[level]; + complete = tree[level]; + tree[level++] = 0; } } } - if (complete == NULL) - { - curr->left = dictnil; - curr->right = dictnil; - curr->color = level % 2; - complete = curr; - - assert (level == baselevel); - while (tree[level] != 0) - { - tree[level]->right = complete; - complete->parent = tree[level]; - complete = tree[level]; - tree[level++] = 0; + if (complete == NULL) { + curr->left = dictnil; + curr->right = dictnil; + curr->color = level % 2; + complete = curr; + + assert (level == baselevel); + while (tree[level] != 0) { + tree[level]->right = complete; + complete->parent = tree[level]; + complete = tree[level]; + tree[level++] = 0; } - } - else - { - curr->left = complete; - curr->color = (level + 1) % 2; - complete->parent = curr; - tree[level] = curr; - complete = 0; - level = baselevel; + } else { + curr->left = complete; + curr->color = (level + 1) % 2; + complete->parent = curr; + tree[level] = curr; + complete = 0; + level = baselevel; } } - if (complete == NULL) - complete = dictnil; + if (complete == NULL) + complete = dictnil; - for (i = 0; i < DICT_DEPTH_MAX; i++) - { - if (tree[i] != 0) - { - tree[i]->right = complete; - complete->parent = tree[i]; - complete = tree[i]; + for (i = 0; i < DICT_DEPTH_MAX; i++) { + if (tree[i] != 0) { + tree[i]->right = complete; + complete->parent = tree[i]; + complete = tree[i]; } } - dictnil->color = dnode_black; - dictnil->right = dictnil; - complete->parent = dictnil; - complete->color = dnode_black; - dict_root (dict) = complete; + dictnil->color = dnode_black; + dictnil->right = dictnil; + complete->parent = dictnil; + complete->color = dnode_black; + dict_root(dict) = complete; - assert (dict_verify (dict)); + assert (dict_verify(dict)); } -void -dict_merge (dict_t * dest, dict_t * source) +void dict_merge(dict_t *dest, dict_t *source) { - dict_load_t load; - dnode_t *leftnode = dict_first (dest), *rightnode = dict_first (source); + dict_load_t load; + dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source); - assert (dict_similar (dest, source)); + assert (dict_similar(dest, source)); - if (source == dest) - return; + if (source == dest) + return; - dest->nodecount = 0; - load_begin_internal (&load, dest); + dest->nodecount = 0; + load_begin_internal(&load, dest); - for (;;) - { - if (leftnode != NULL && rightnode != NULL) - { - if (dest->compare (leftnode->key, rightnode->key) < 0) + for (;;) { + if (leftnode != NULL && rightnode != NULL) { + if (dest->compare(leftnode->key, rightnode->key) < 0) + goto copyleft; + else + goto copyright; + } else if (leftnode != NULL) { goto copyleft; - else + } else if (rightnode != NULL) { goto copyright; + } else { + assert (leftnode == NULL && rightnode == NULL); + break; } - else if (leftnode != NULL) - { - goto copyleft; - } - else if (rightnode != NULL) + + copyleft: { - goto copyright; + dnode_t *next = dict_next(dest, leftnode); + #ifndef NDEBUG + leftnode->left = NULL; /* suppress assertion in dict_load_next */ + #endif + dict_load_next(&load, leftnode, leftnode->key); + leftnode = next; + continue; } - else + + copyright: { - assert (leftnode == NULL && rightnode == NULL); - break; + dnode_t *next = dict_next(source, rightnode); + #ifndef NDEBUG + rightnode->left = NULL; + #endif + dict_load_next(&load, rightnode, rightnode->key); + rightnode = next; + continue; } - - copyleft: - { - dnode_t *next = dict_next (dest, leftnode); -#ifndef NDEBUG - leftnode->left = NULL; /* suppress assertion in dict_load_next */ -#endif - dict_load_next (&load, leftnode, leftnode->key); - leftnode = next; - continue; - } - - copyright: - { - dnode_t *next = dict_next (source, rightnode); -#ifndef NDEBUG - rightnode->left = NULL; -#endif - dict_load_next (&load, rightnode, rightnode->key); - rightnode = next; - continue; - } } - dict_clear (source); - dict_load_end (&load); + dict_clear(source); + dict_load_end(&load); } #ifdef KAZLIB_TEST_MAIN @@ -1352,329 +1199,298 @@ dict_merge (dict_t * dest, dict_t * source) typedef char input_t[256]; -static int -tokenize (char *string, ...) +static int tokenize(char *string, ...) { - char **tokptr; - va_list arglist; - int tokcount = 0; - - va_start (arglist, string); - tokptr = va_arg (arglist, char **); - while (tokptr) - { - while (*string && isspace ((unsigned char) *string)) - string++; - if (!*string) - break; - *tokptr = string; - while (*string && !isspace ((unsigned char) *string)) - string++; - tokptr = va_arg (arglist, char **); - tokcount++; - if (!*string) - break; - *string++ = 0; + char **tokptr; + va_list arglist; + int tokcount = 0; + + va_start(arglist, string); + tokptr = va_arg(arglist, char **); + while (tokptr) { + while (*string && isspace((unsigned char) *string)) + string++; + if (!*string) + break; + *tokptr = string; + while (*string && !isspace((unsigned char) *string)) + string++; + tokptr = va_arg(arglist, char **); + tokcount++; + if (!*string) + break; + *string++ = 0; } - va_end (arglist); + va_end(arglist); - return tokcount; + return tokcount; } -static int -comparef (const void *key1, const void *key2) +static int comparef(const void *key1, const void *key2) { - return strcmp (key1, key2); + return strcmp(key1, key2); } -static char * -dupstring (char *str) +static char *dupstring(char *str) { - int sz = strlen (str) + 1; - char *new = malloc (sz); - if (new) - memcpy (new, str, sz); - return new; + int sz = strlen(str) + 1; + char *new = malloc(sz); + if (new) + memcpy(new, str, sz); + return new; } -static dnode_t * -new_node (void *c) +static dnode_t *new_node(void *c) { - static dnode_t few[5]; - static int count; + static dnode_t few[5]; + static int count; - if (count < 5) - return few + count++; + if (count < 5) + return few + count++; - return NULL; + return NULL; } -static void -del_node (dnode_t * n, void *c) +static void del_node(dnode_t *n, void *c) { } static int prompt = 0; -static void -construct (dict_t * d) +static void construct(dict_t *d) { - input_t in; - int done = 0; - dict_load_t dl; - dnode_t *dn; - char *tok1, *tok2, *val; - const char *key; - char *help = - "p turn prompt on\n" - "q finish construction\n" - "a <key> <val> add new entry\n"; - - if (!dict_isempty (d)) - puts ("warning: dictionary not empty!"); - - dict_load_begin (&dl, d); - - while (!done) - { - if (prompt) - putchar ('>'); - fflush (stdout); - - if (!fgets (in, sizeof (input_t), stdin)) - break; - - switch (in[0]) - { - case '?': - puts (help); - break; - case 'p': - prompt = 1; - break; - case 'q': - done = 1; - break; - case 'a': - if (tokenize (in + 1, &tok1, &tok2, (char **) 0) != 2) - { - puts ("what?"); - break; - } - key = dupstring (tok1); - val = dupstring (tok2); - dn = dnode_create (val); - - if (!key || !val || !dn) - { - puts ("out of memory"); - free ((void *) key); - free (val); - if (dn) - dnode_destroy (dn); - } + input_t in; + int done = 0; + dict_load_t dl; + dnode_t *dn; + char *tok1, *tok2, *val; + const char *key; + char *help = + "p turn prompt on\n" + "q finish construction\n" + "a <key> <val> add new entry\n"; + + if (!dict_isempty(d)) + puts("warning: dictionary not empty!"); + + dict_load_begin(&dl, d); + + while (!done) { + if (prompt) + putchar('>'); + fflush(stdout); + + if (!fgets(in, sizeof(input_t), stdin)) + break; + + switch (in[0]) { + case '?': + puts(help); + break; + case 'p': + prompt = 1; + break; + case 'q': + done = 1; + break; + case 'a': + if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { + puts("what?"); + break; + } + key = dupstring(tok1); + val = dupstring(tok2); + dn = dnode_create(val); + + if (!key || !val || !dn) { + puts("out of memory"); + free((void *) key); + free(val); + if (dn) + dnode_destroy(dn); + } - dict_load_next (&dl, dn, key); - break; - default: - putchar ('?'); - putchar ('\n'); - break; + dict_load_next(&dl, dn, key); + break; + default: + putchar('?'); + putchar('\n'); + break; } } - dict_load_end (&dl); + dict_load_end(&dl); } -int -main (void) +int main(void) { - input_t in; - dict_t darray[10]; - dict_t *d = &darray[0]; - dnode_t *dn; - int i; - char *tok1, *tok2, *val; - const char *key; - - char *help = - "a <key> <val> add value to dictionary\n" - "d <key> delete value from dictionary\n" - "l <key> lookup value in dictionary\n" - "( <key> lookup lower bound\n" - ") <key> lookup upper bound\n" - "# <num> switch to alternate dictionary (0-9)\n" - "j <num> <num> merge two dictionaries\n" - "f free the whole dictionary\n" - "k allow duplicate keys\n" - "c show number of entries\n" - "t dump whole dictionary in sort order\n" - "m make dictionary out of sorted items\n" - "p turn prompt on\n" - "s switch to non-functioning allocator\n" - "q quit"; - - for (i = 0; i < sizeof darray / sizeof *darray; i++) - dict_init (&darray[i], DICTCOUNT_T_MAX, comparef); - - for (;;) - { - if (prompt) - putchar ('>'); - fflush (stdout); - - if (!fgets (in, sizeof (input_t), stdin)) - break; - - switch (in[0]) - { - case '?': - puts (help); - break; - case 'a': - if (tokenize (in + 1, &tok1, &tok2, (char **) 0) != 2) - { - puts ("what?"); - break; - } - key = dupstring (tok1); - val = dupstring (tok2); - - if (!key || !val) - { - puts ("out of memory"); - free ((void *) key); - free (val); - } + input_t in; + dict_t darray[10]; + dict_t *d = &darray[0]; + dnode_t *dn; + int i; + char *tok1, *tok2, *val; + const char *key; + + char *help = + "a <key> <val> add value to dictionary\n" + "d <key> delete value from dictionary\n" + "l <key> lookup value in dictionary\n" + "( <key> lookup lower bound\n" + ") <key> lookup upper bound\n" + "# <num> switch to alternate dictionary (0-9)\n" + "j <num> <num> merge two dictionaries\n" + "f free the whole dictionary\n" + "k allow duplicate keys\n" + "c show number of entries\n" + "t dump whole dictionary in sort order\n" + "m make dictionary out of sorted items\n" + "p turn prompt on\n" + "s switch to non-functioning allocator\n" + "q quit"; + + for (i = 0; i < sizeof darray / sizeof *darray; i++) + dict_init(&darray[i], DICTCOUNT_T_MAX, comparef); + + for (;;) { + if (prompt) + putchar('>'); + fflush(stdout); + + if (!fgets(in, sizeof(input_t), stdin)) + break; + + switch(in[0]) { + case '?': + puts(help); + break; + case 'a': + if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { + puts("what?"); + break; + } + key = dupstring(tok1); + val = dupstring(tok2); - if (!dict_alloc_insert (d, key, val)) - { - puts ("dict_alloc_insert failed"); - free ((void *) key); - free (val); - break; - } - break; - case 'd': - if (tokenize (in + 1, &tok1, (char **) 0) != 1) - { - puts ("what?"); - break; - } - dn = dict_lookup (d, tok1); - if (!dn) - { - puts ("dict_lookup failed"); - break; - } - val = dnode_get (dn); - key = dnode_getkey (dn); - dict_delete_free (d, dn); - - free (val); - free ((void *) key); - break; - case 'f': - dict_free (d); - break; - case 'l': - case '(': - case ')': - if (tokenize (in + 1, &tok1, (char **) 0) != 1) - { - puts ("what?"); - break; - } - dn = 0; - switch (in[0]) - { + if (!key || !val) { + puts("out of memory"); + free((void *) key); + free(val); + } + + if (!dict_alloc_insert(d, key, val)) { + puts("dict_alloc_insert failed"); + free((void *) key); + free(val); + break; + } + break; + case 'd': + if (tokenize(in+1, &tok1, (char **) 0) != 1) { + puts("what?"); + break; + } + dn = dict_lookup(d, tok1); + if (!dn) { + puts("dict_lookup failed"); + break; + } + val = dnode_get(dn); + key = dnode_getkey(dn); + dict_delete_free(d, dn); + + free(val); + free((void *) key); + break; + case 'f': + dict_free(d); + break; case 'l': - dn = dict_lookup (d, tok1); - break; case '(': - dn = dict_lower_bound (d, tok1); - break; case ')': - dn = dict_upper_bound (d, tok1); - break; - } - if (!dn) - { - puts ("lookup failed"); - break; - } - val = dnode_get (dn); - puts (val); - break; - case 'm': - construct (d); - break; - case 'k': - dict_allow_dupes (d); - break; - case 'c': - printf ("%lu\n", (unsigned long) dict_count (d)); - break; - case 't': - for (dn = dict_first (d); dn; dn = dict_next (d, dn)) - { - printf ("%s\t%s\n", (char *) dnode_getkey (dn), - (char *) dnode_get (dn)); - } - break; - case 'q': - exit (0); - break; - case '\0': - break; - case 'p': - prompt = 1; - break; - case 's': - dict_set_allocator (d, new_node, del_node, NULL); - break; - case '#': - if (tokenize (in + 1, &tok1, (char **) 0) != 1) - { - puts ("what?"); - break; - } - else - { - int dictnum = atoi (tok1); - if (dictnum < 0 || dictnum > 9) - { - puts ("invalid number"); - break; + if (tokenize(in+1, &tok1, (char **) 0) != 1) { + puts("what?"); + break; } - d = &darray[dictnum]; - } - break; - case 'j': - if (tokenize (in + 1, &tok1, &tok2, (char **) 0) != 2) - { - puts ("what?"); - break; - } - else - { - int dict1 = atoi (tok1), dict2 = atoi (tok2); - if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) - { - puts ("invalid number"); - break; + dn = 0; + switch (in[0]) { + case 'l': + dn = dict_lookup(d, tok1); + break; + case '(': + dn = dict_lower_bound(d, tok1); + break; + case ')': + dn = dict_upper_bound(d, tok1); + break; } - dict_merge (&darray[dict1], &darray[dict2]); - } - break; - default: - putchar ('?'); - putchar ('\n'); - break; + if (!dn) { + puts("lookup failed"); + break; + } + val = dnode_get(dn); + puts(val); + break; + case 'm': + construct(d); + break; + case 'k': + dict_allow_dupes(d); + break; + case 'c': + printf("%lu\n", (unsigned long) dict_count(d)); + break; + case 't': + for (dn = dict_first(d); dn; dn = dict_next(d, dn)) { + printf("%s\t%s\n", (char *) dnode_getkey(dn), + (char *) dnode_get(dn)); + } + break; + case 'q': + exit(0); + break; + case '\0': + break; + case 'p': + prompt = 1; + break; + case 's': + dict_set_allocator(d, new_node, del_node, NULL); + break; + case '#': + if (tokenize(in+1, &tok1, (char **) 0) != 1) { + puts("what?"); + break; + } else { + int dictnum = atoi(tok1); + if (dictnum < 0 || dictnum > 9) { + puts("invalid number"); + break; + } + d = &darray[dictnum]; + } + break; + case 'j': + if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { + puts("what?"); + break; + } else { + int dict1 = atoi(tok1), dict2 = atoi(tok2); + if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) { + puts("invalid number"); + break; + } + dict_merge(&darray[dict1], &darray[dict2]); + } + break; + default: + putchar('?'); + putchar('\n'); + break; } } - return 0; + return 0; } #endif diff --git a/isisd/dict.h b/isisd/dict.h index 1a5e9d7c..9395d1c0 100644 --- a/isisd/dict.h +++ b/isisd/dict.h @@ -14,7 +14,7 @@ * into proprietary software; there is no requirement for such software to * contain a copyright notice related to this source. * - * $Id: dict.h,v 1.2 2004/09/10 20:48:21 hasso Exp $ + * $Id: dict.h,v 1.3 2005/09/25 12:04:25 hasso Exp $ * $Name: $ */ @@ -31,41 +31,37 @@ */ #ifdef __cplusplus -extern "C" -{ +extern "C" { #endif - typedef unsigned long dictcount_t; +typedef unsigned long dictcount_t; #define DICTCOUNT_T_MAX ULONG_MAX /* * The dictionary is implemented as a red-black tree */ - typedef enum - { dnode_red, dnode_black } dnode_color_t; +typedef enum { dnode_red, dnode_black } dnode_color_t; - typedef struct dnode_t - { -#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) +typedef struct dnode_t { + #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) struct dnode_t *dict_left; struct dnode_t *dict_right; struct dnode_t *dict_parent; dnode_color_t dict_color; const void *dict_key; void *dict_data; -#else + #else int dict_dummy; -#endif - } dnode_t; + #endif +} dnode_t; - typedef int (*dict_comp_t) (const void *, const void *); - typedef dnode_t *(*dnode_alloc_t) (void *); - typedef void (*dnode_free_t) (dnode_t *, void *); +typedef int (*dict_comp_t)(const void *, const void *); +typedef dnode_t *(*dnode_alloc_t)(void *); +typedef void (*dnode_free_t)(dnode_t *, void *); - typedef struct dict_t - { -#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) +typedef struct dict_t { + #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) dnode_t dict_nilnode; dictcount_t dict_nodecount; dictcount_t dict_maxcount; @@ -74,61 +70,59 @@ extern "C" dnode_free_t dict_freenode; void *dict_context; int dict_dupes; -#else + #else int dict_dummmy; -#endif - } dict_t; + #endif +} dict_t; - typedef void (*dnode_process_t) (dict_t *, dnode_t *, void *); +typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *); - typedef struct dict_load_t - { -#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) +typedef struct dict_load_t { + #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) dict_t *dict_dictptr; dnode_t dict_nilnode; -#else + #else int dict_dummmy; -#endif - } dict_load_t; - - extern dict_t *dict_create (dictcount_t, dict_comp_t); - extern void dict_set_allocator (dict_t *, dnode_alloc_t, dnode_free_t, - void *); - extern void dict_destroy (dict_t *); - extern void dict_free_nodes (dict_t *); - extern void dict_free (dict_t *); - extern dict_t *dict_init (dict_t *, dictcount_t, dict_comp_t); - extern void dict_init_like (dict_t *, const dict_t *); - extern int dict_verify (dict_t *); - extern int dict_similar (const dict_t *, const dict_t *); - extern dnode_t *dict_lookup (dict_t *, const void *); - extern dnode_t *dict_lower_bound (dict_t *, const void *); - extern dnode_t *dict_upper_bound (dict_t *, const void *); - extern void dict_insert (dict_t *, dnode_t *, const void *); - extern dnode_t *dict_delete (dict_t *, dnode_t *); - extern int dict_alloc_insert (dict_t *, const void *, void *); - extern void dict_delete_free (dict_t *, dnode_t *); - extern dnode_t *dict_first (dict_t *); - extern dnode_t *dict_last (dict_t *); - extern dnode_t *dict_next (dict_t *, dnode_t *); - extern dnode_t *dict_prev (dict_t *, dnode_t *); - extern dictcount_t dict_count (dict_t *); - extern int dict_isempty (dict_t *); - extern int dict_isfull (dict_t *); - extern int dict_contains (dict_t *, dnode_t *); - extern void dict_allow_dupes (dict_t *); - extern int dnode_is_in_a_dict (dnode_t *); - extern dnode_t *dnode_create (void *); - extern dnode_t *dnode_init (dnode_t *, void *); - extern void dnode_destroy (dnode_t *); - extern void *dnode_get (dnode_t *); - extern const void *dnode_getkey (dnode_t *); - extern void dnode_put (dnode_t *, void *); - extern void dict_process (dict_t *, void *, dnode_process_t); - extern void dict_load_begin (dict_load_t *, dict_t *); - extern void dict_load_next (dict_load_t *, dnode_t *, const void *); - extern void dict_load_end (dict_load_t *); - extern void dict_merge (dict_t *, dict_t *); + #endif +} dict_load_t; + +extern dict_t *dict_create(dictcount_t, dict_comp_t); +extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *); +extern void dict_destroy(dict_t *); +extern void dict_free_nodes(dict_t *); +extern void dict_free(dict_t *); +extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t); +extern void dict_init_like(dict_t *, const dict_t *); +extern int dict_verify(dict_t *); +extern int dict_similar(const dict_t *, const dict_t *); +extern dnode_t *dict_lookup(dict_t *, const void *); +extern dnode_t *dict_lower_bound(dict_t *, const void *); +extern dnode_t *dict_upper_bound(dict_t *, const void *); +extern void dict_insert(dict_t *, dnode_t *, const void *); +extern dnode_t *dict_delete(dict_t *, dnode_t *); +extern int dict_alloc_insert(dict_t *, const void *, void *); +extern void dict_delete_free(dict_t *, dnode_t *); +extern dnode_t *dict_first(dict_t *); +extern dnode_t *dict_last(dict_t *); +extern dnode_t *dict_next(dict_t *, dnode_t *); +extern dnode_t *dict_prev(dict_t *, dnode_t *); +extern dictcount_t dict_count(dict_t *); +extern int dict_isempty(dict_t *); +extern int dict_isfull(dict_t *); +extern int dict_contains(dict_t *, dnode_t *); +extern void dict_allow_dupes(dict_t *); +extern int dnode_is_in_a_dict(dnode_t *); +extern dnode_t *dnode_create(void *); +extern dnode_t *dnode_init(dnode_t *, void *); +extern void dnode_destroy(dnode_t *); +extern void *dnode_get(dnode_t *); +extern const void *dnode_getkey(dnode_t *); +extern void dnode_put(dnode_t *, void *); +extern void dict_process(dict_t *, void *, dnode_process_t); +extern void dict_load_begin(dict_load_t *, dict_t *); +extern void dict_load_next(dict_load_t *, dnode_t *, const void *); +extern void dict_load_end(dict_load_t *); +extern void dict_merge(dict_t *, dict_t *); #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) #ifdef KAZLIB_SIDEEFFECT_DEBUG |