diff options
Diffstat (limited to 'mcastseed/lib/gl_anyrbtree_list2.h')
| -rw-r--r-- | mcastseed/lib/gl_anyrbtree_list2.h | 1028 |
1 files changed, 0 insertions, 1028 deletions
diff --git a/mcastseed/lib/gl_anyrbtree_list2.h b/mcastseed/lib/gl_anyrbtree_list2.h deleted file mode 100644 index a0e2e43..0000000 --- a/mcastseed/lib/gl_anyrbtree_list2.h +++ /dev/null @@ -1,1028 +0,0 @@ -/* Sequential list data type implemented by a binary tree. - Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - 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 3 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, see <http://www.gnu.org/licenses/>. */ - -/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ - -/* -------------------------- gl_list_t Data Type -------------------------- */ - -/* Create a subtree for count >= 1 elements. - Its black-height bh is passed as argument, with - 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1. - Its height is h where 2^(h-1) <= count <= 2^h - 1. - Return NULL upon out-of-memory. */ -static gl_list_node_t -create_subtree_with_contents (unsigned int bh, - size_t count, const void **contents) -{ - size_t half1 = (count - 1) / 2; - size_t half2 = count / 2; - /* Note: half1 + half2 = count - 1. */ - gl_list_node_t node = - (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); - if (node == NULL) - return NULL; - - if (half1 > 0) - { - /* half1 > 0 implies count > 1, implies bh >= 1, implies - 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */ - node->left = - create_subtree_with_contents (bh - 1, half1, contents); - if (node->left == NULL) - goto fail1; - node->left->parent = node; - } - else - node->left = NULL; - - node->value = contents[half1]; - - if (half2 > 0) - { - /* half2 > 0 implies count > 1, implies bh >= 1, implies - 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */ - node->right = - create_subtree_with_contents (bh - 1, half2, contents + half1 + 1); - if (node->right == NULL) - goto fail2; - node->right->parent = node; - } - else - node->right = NULL; - - node->color = (bh == 0 ? RED : BLACK); - - node->branch_size = count; - - return node; - - fail2: - if (node->left != NULL) - free_subtree (node->left); - fail1: - free (node); - return NULL; -} - -static gl_list_t -gl_tree_nx_create (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates, - size_t count, const void **contents) -{ - struct gl_list_impl *list = - (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); - - if (list == NULL) - return NULL; - - list->base.vtable = implementation; - list->base.equals_fn = equals_fn; - list->base.hashcode_fn = hashcode_fn; - list->base.dispose_fn = dispose_fn; - list->base.allow_duplicates = allow_duplicates; -#if WITH_HASHTABLE - { - size_t estimate = xsum (count, count / 2); /* 1.5 * count */ - if (estimate < 10) - estimate = 10; - list->table_size = next_prime (estimate); - if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t)))) - goto fail1; - list->table = - (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); - if (list->table == NULL) - goto fail1; - } -#endif - if (count > 0) - { - /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose - upper bh levels are black, and only the partially present lowest - level is red. */ - unsigned int bh; - { - size_t n; - for (n = count + 1, bh = 0; n > 1; n = n >> 1) - bh++; - } - - list->root = create_subtree_with_contents (bh, count, contents); - if (list->root == NULL) - goto fail2; - list->root->parent = NULL; - -#if WITH_HASHTABLE - /* Now that the tree is built, node_position() works. Now we can - add the nodes to the hash table. */ - if (add_nodes_to_buckets (list) < 0) - goto fail3; -#endif - } - else - list->root = NULL; - - return list; - -#if WITH_HASHTABLE - fail3: - free_subtree (list->root); -#endif - fail2: -#if WITH_HASHTABLE - free (list->table); - fail1: -#endif - free (list); - return NULL; -} - -/* Rotate left a subtree. - - B D - / \ / \ - A D --> B E - / \ / \ - C E A C - - Change the tree structure, update the branch sizes. - The caller must update the colors and register D as child of its parent. */ -static gl_list_node_t -rotate_left (gl_list_node_t b_node, gl_list_node_t d_node) -{ - gl_list_node_t a_node = b_node->left; - gl_list_node_t c_node = d_node->left; - gl_list_node_t e_node = d_node->right; - - b_node->right = c_node; - d_node->left = b_node; - - d_node->parent = b_node->parent; - b_node->parent = d_node; - if (c_node != NULL) - c_node->parent = b_node; - - b_node->branch_size = - (a_node != NULL ? a_node->branch_size : 0) - + 1 + (c_node != NULL ? c_node->branch_size : 0); - d_node->branch_size = - b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0); - - return d_node; -} - -/* Rotate right a subtree. - - D B - / \ / \ - B E --> A D - / \ / \ - A C C E - - Change the tree structure, update the branch sizes. - The caller must update the colors and register B as child of its parent. */ -static gl_list_node_t -rotate_right (gl_list_node_t b_node, gl_list_node_t d_node) -{ - gl_list_node_t a_node = b_node->left; - gl_list_node_t c_node = b_node->right; - gl_list_node_t e_node = d_node->right; - - d_node->left = c_node; - b_node->right = d_node; - - b_node->parent = d_node->parent; - d_node->parent = b_node; - if (c_node != NULL) - c_node->parent = d_node; - - d_node->branch_size = - (c_node != NULL ? c_node->branch_size : 0) - + 1 + (e_node != NULL ? e_node->branch_size : 0); - b_node->branch_size = - (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size; - - return b_node; -} - -/* Ensure the tree is balanced, after an insertion operation. - Also assigns node->color. - parent is the given node's parent, known to be non-NULL. */ -static void -rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent) -{ - for (;;) - { - /* At this point, parent = node->parent != NULL. - Think of node->color being RED (although node->color is not yet - assigned.) */ - gl_list_node_t grandparent; - gl_list_node_t uncle; - - if (parent->color == BLACK) - { - /* A RED color for node is acceptable. */ - node->color = RED; - return; - } - - grandparent = parent->parent; - /* Since parent is RED, we know that - grandparent is != NULL and colored BLACK. */ - - if (grandparent->left == parent) - uncle = grandparent->right; - else if (grandparent->right == parent) - uncle = grandparent->left; - else - abort (); - - if (uncle != NULL && uncle->color == RED) - { - /* Change grandparent from BLACK to RED, and - change parent and uncle from RED to BLACK. - This makes it acceptable for node to be RED. */ - node->color = RED; - parent->color = uncle->color = BLACK; - node = grandparent; - } - else - { - /* grandparent and uncle are BLACK. parent is RED. node wants - to be RED too. - In this case, recoloring is not sufficient. Need to perform - one or two rotations. */ - gl_list_node_t *grandparentp; - - if (grandparent->parent == NULL) - grandparentp = &list->root; - else if (grandparent->parent->left == grandparent) - grandparentp = &grandparent->parent->left; - else if (grandparent->parent->right == grandparent) - grandparentp = &grandparent->parent->right; - else - abort (); - - if (grandparent->left == parent) - { - if (parent->right == node) - { - /* Rotation between node and parent. */ - grandparent->left = rotate_left (parent, node); - node = parent; - parent = grandparent->left; - } - /* grandparent and uncle are BLACK. parent and node want to be - RED. parent = grandparent->left. node = parent->left. - - grandparent parent - bh+1 bh+1 - / \ / \ - parent uncle --> node grandparent - bh bh bh bh - / \ / \ - node C C uncle - bh bh bh bh - */ - *grandparentp = rotate_right (parent, grandparent); - parent->color = BLACK; - node->color = grandparent->color = RED; - } - else /* grandparent->right == parent */ - { - if (parent->left == node) - { - /* Rotation between node and parent. */ - grandparent->right = rotate_right (node, parent); - node = parent; - parent = grandparent->right; - } - /* grandparent and uncle are BLACK. parent and node want to be - RED. parent = grandparent->right. node = parent->right. - - grandparent parent - bh+1 bh+1 - / \ / \ - uncle parent --> grandparent node - bh bh bh bh - / \ / \ - C node uncle C - bh bh bh bh - */ - *grandparentp = rotate_left (grandparent, parent); - parent->color = BLACK; - node->color = grandparent->color = RED; - } - return; - } - - /* Start again with a new (node, parent) pair. */ - parent = node->parent; - - if (parent == NULL) - { - /* Change node's color from RED to BLACK. This increases the - tree's black-height. */ - node->color = BLACK; - return; - } - } -} - -/* Ensure the tree is balanced, after a deletion operation. - CHILD was a grandchild of PARENT and is now its child. Between them, - a black node was removed. CHILD is also black, or NULL. - (CHILD can also be NULL. But PARENT is non-NULL.) */ -static void -rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent) -{ - for (;;) - { - /* At this point, we reduced the black-height of the CHILD subtree by 1. - To make up, either look for a possibility to turn a RED to a BLACK - node, or try to reduce the black-height tree of CHILD's sibling - subtree as well. */ - gl_list_node_t *parentp; - - if (parent->parent == NULL) - parentp = &list->root; - else if (parent->parent->left == parent) - parentp = &parent->parent->left; - else if (parent->parent->right == parent) - parentp = &parent->parent->right; - else - abort (); - - if (parent->left == child) - { - gl_list_node_t sibling = parent->right; - /* sibling's black-height is >= 1. In particular, - sibling != NULL. - - parent - / \ - child sibling - bh bh+1 - */ - - if (sibling->color == RED) - { - /* sibling is RED, hence parent is BLACK and sibling's children - are non-NULL and BLACK. - - parent sibling - bh+2 bh+2 - / \ / \ - child sibling --> parent SR - bh bh+1 bh+1 bh+1 - / \ / \ - SL SR child SL - bh+1 bh+1 bh bh+1 - */ - *parentp = rotate_left (parent, sibling); - parent->color = RED; - sibling->color = BLACK; - - /* Concentrate on the subtree of parent. The new sibling is - one of the old sibling's children, and known to be BLACK. */ - parentp = &sibling->left; - sibling = parent->right; - } - /* Now we know that sibling is BLACK. - - parent - / \ - child sibling - bh bh+1 - */ - if (sibling->right != NULL && sibling->right->color == RED) - { - /* - parent sibling - bh+1|bh+2 bh+1|bh+2 - / \ / \ - child sibling --> parent SR - bh bh+1 bh+1 bh+1 - / \ / \ - SL SR child SL - bh bh bh bh - */ - *parentp = rotate_left (parent, sibling); - sibling->color = parent->color; - parent->color = BLACK; - sibling->right->color = BLACK; - return; - } - else if (sibling->left != NULL && sibling->left->color == RED) - { - /* - parent parent - bh+1|bh+2 bh+1|bh+2 - / \ / \ - child sibling --> child SL - bh bh+1 bh bh+1 - / \ / \ - SL SR SLL sibling - bh bh bh bh - / \ / \ - SLL SLR SLR SR - bh bh bh bh - - where SLL, SLR, SR are all black. - */ - parent->right = rotate_right (sibling->left, sibling); - /* Change sibling from BLACK to RED and SL from RED to BLACK. */ - sibling->color = RED; - sibling = parent->right; - sibling->color = BLACK; - - /* Now do as in the previous case. */ - *parentp = rotate_left (parent, sibling); - sibling->color = parent->color; - parent->color = BLACK; - sibling->right->color = BLACK; - return; - } - else - { - if (parent->color == BLACK) - { - /* Change sibling from BLACK to RED. Then the entire - subtree at parent has decreased its black-height. - parent parent - bh+2 bh+1 - / \ / \ - child sibling --> child sibling - bh bh+1 bh bh - */ - sibling->color = RED; - - child = parent; - } - else - { - /* Change parent from RED to BLACK, but compensate by - changing sibling from BLACK to RED. - parent parent - bh+1 bh+1 - / \ / \ - child sibling --> child sibling - bh bh+1 bh bh - */ - parent->color = BLACK; - sibling->color = RED; - return; - } - } - } - else if (parent->right == child) - { - gl_list_node_t sibling = parent->left; - /* sibling's black-height is >= 1. In particular, - sibling != NULL. - - parent - / \ - sibling child - bh+1 bh - */ - - if (sibling->color == RED) - { - /* sibling is RED, hence parent is BLACK and sibling's children - are non-NULL and BLACK. - - parent sibling - bh+2 bh+2 - / \ / \ - sibling child --> SR parent - bh+1 ch bh+1 bh+1 - / \ / \ - SL SR SL child - bh+1 bh+1 bh+1 bh - */ - *parentp = rotate_right (sibling, parent); - parent->color = RED; - sibling->color = BLACK; - - /* Concentrate on the subtree of parent. The new sibling is - one of the old sibling's children, and known to be BLACK. */ - parentp = &sibling->right; - sibling = parent->left; - } - /* Now we know that sibling is BLACK. - - parent - / \ - sibling child - bh+1 bh - */ - if (sibling->left != NULL && sibling->left->color == RED) - { - /* - parent sibling - bh+1|bh+2 bh+1|bh+2 - / \ / \ - sibling child --> SL parent - bh+1 bh bh+1 bh+1 - / \ / \ - SL SR SR child - bh bh bh bh - */ - *parentp = rotate_right (sibling, parent); - sibling->color = parent->color; - parent->color = BLACK; - sibling->left->color = BLACK; - return; - } - else if (sibling->right != NULL && sibling->right->color == RED) - { - /* - parent parent - bh+1|bh+2 bh+1|bh+2 - / \ / \ - sibling child --> SR child - bh+1 bh bh+1 bh - / \ / \ - SL SR sibling SRR - bh bh bh bh - / \ / \ - SRL SRR SL SRL - bh bh bh bh - - where SL, SRL, SRR are all black. - */ - parent->left = rotate_left (sibling, sibling->right); - /* Change sibling from BLACK to RED and SL from RED to BLACK. */ - sibling->color = RED; - sibling = parent->left; - sibling->color = BLACK; - - /* Now do as in the previous case. */ - *parentp = rotate_right (sibling, parent); - sibling->color = parent->color; - parent->color = BLACK; - sibling->left->color = BLACK; - return; - } - else - { - if (parent->color == BLACK) - { - /* Change sibling from BLACK to RED. Then the entire - subtree at parent has decreased its black-height. - parent parent - bh+2 bh+1 - / \ / \ - sibling child --> sibling child - bh+1 bh bh bh - */ - sibling->color = RED; - - child = parent; - } - else - { - /* Change parent from RED to BLACK, but compensate by - changing sibling from BLACK to RED. - parent parent - bh+1 bh+1 - / \ / \ - sibling child --> sibling child - bh+1 bh bh bh - */ - parent->color = BLACK; - sibling->color = RED; - return; - } - } - } - else - abort (); - - /* Start again with a new (child, parent) pair. */ - parent = child->parent; - -#if 0 /* Already handled. */ - if (child != NULL && child->color == RED) - { - child->color = BLACK; - return; - } -#endif - - if (parent == NULL) - return; - } -} - -static void -gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node) -{ - gl_list_node_t parent = node->parent; - - if (node->left == NULL) - { - /* Replace node with node->right. */ - gl_list_node_t child = node->right; - - if (child != NULL) - { - child->parent = parent; - /* Since node->left == NULL, child must be RED and of height 1, - hence node must have been BLACK. Recolor the child. */ - child->color = BLACK; - } - if (parent == NULL) - list->root = child; - else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = parent; p != NULL; p = p->parent) - p->branch_size--; - } - - if (child == NULL && node->color == BLACK) - rebalance_after_remove (list, child, parent); - } - } - else if (node->right == NULL) - { - /* It is not absolutely necessary to treat this case. But the more - general case below is more complicated, hence slower. */ - /* Replace node with node->left. */ - gl_list_node_t child = node->left; - - child->parent = parent; - /* Since node->right == NULL, child must be RED and of height 1, - hence node must have been BLACK. Recolor the child. */ - child->color = BLACK; - if (parent == NULL) - list->root = child; - else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = parent; p != NULL; p = p->parent) - p->branch_size--; - } - } - } - else - { - /* Replace node with the rightmost element of the node->left subtree. */ - gl_list_node_t subst; - gl_list_node_t subst_parent; - gl_list_node_t child; - color_t removed_color; - - for (subst = node->left; subst->right != NULL; ) - subst = subst->right; - - subst_parent = subst->parent; - - child = subst->left; - - removed_color = subst->color; - - /* The case subst_parent == node is special: If we do nothing special, - we get confusion about node->left, subst->left and child->parent. - subst_parent == node - <==> The 'for' loop above terminated immediately. - <==> subst == subst_parent->left - [otherwise subst == subst_parent->right] - In this case, we would need to first set - child->parent = node; node->left = child; - and later - when we copy subst into node's position - again - child->parent = subst; subst->left = child; - Altogether a no-op. */ - if (subst_parent != node) - { - if (child != NULL) - child->parent = subst_parent; - subst_parent->right = child; - } - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = subst_parent; p != NULL; p = p->parent) - p->branch_size--; - } - - /* Copy subst into node's position. - (This is safer than to copy subst's value into node, keep node in - place, and free subst.) */ - if (subst_parent != node) - { - subst->left = node->left; - subst->left->parent = subst; - } - subst->right = node->right; - subst->right->parent = subst; - subst->color = node->color; - subst->branch_size = node->branch_size; - subst->parent = parent; - if (parent == NULL) - list->root = subst; - else if (parent->left == node) - parent->left = subst; - else /* parent->right == node */ - parent->right = subst; - - if (removed_color == BLACK) - { - if (child != NULL && child->color == RED) - /* Recolor the child. */ - child->color = BLACK; - else - /* Rebalancing starts at child's parent, that is subst_parent - - except when subst_parent == node. In this case, we need to use - its replacement, subst. */ - rebalance_after_remove (list, child, - subst_parent != node ? subst_parent : subst); - } - } -} - -static gl_list_node_t -gl_tree_nx_add_first (gl_list_t list, const void *elt) -{ - /* Create new node. */ - gl_list_node_t new_node = - (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->branch_size = 1; - new_node->value = elt; -#if WITH_HASHTABLE - new_node->h.hashcode = - (list->base.hashcode_fn != NULL - ? list->base.hashcode_fn (new_node->value) - : (size_t)(uintptr_t) new_node->value); -#endif - - /* Add it to the tree. */ - if (list->root == NULL) - { - new_node->color = BLACK; - list->root = new_node; - new_node->parent = NULL; - } - else - { - gl_list_node_t node; - - for (node = list->root; node->left != NULL; ) - node = node->left; - - node->left = new_node; - new_node->parent = node; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = node; p != NULL; p = p->parent) - p->branch_size++; - } - - /* Color and rebalance. */ - rebalance_after_add (list, new_node, node); - } - -#if WITH_HASHTABLE - /* Add node to the hash table. - Note that this is only possible _after_ the node has been added to the - tree structure, because add_to_bucket() uses node_position(). */ - if (add_to_bucket (list, new_node) < 0) - { - gl_tree_remove_node_from_tree (list, new_node); - free (new_node); - return NULL; - } - hash_resize_after_add (list); -#endif - - return new_node; -} - -static gl_list_node_t -gl_tree_nx_add_last (gl_list_t list, const void *elt) -{ - /* Create new node. */ - gl_list_node_t new_node = - (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->branch_size = 1; - new_node->value = elt; -#if WITH_HASHTABLE - new_node->h.hashcode = - (list->base.hashcode_fn != NULL - ? list->base.hashcode_fn (new_node->value) - : (size_t)(uintptr_t) new_node->value); -#endif - - /* Add it to the tree. */ - if (list->root == NULL) - { - new_node->color = BLACK; - list->root = new_node; - new_node->parent = NULL; - } - else - { - gl_list_node_t node; - - for (node = list->root; node->right != NULL; ) - node = node->right; - - node->right = new_node; - new_node->parent = node; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = node; p != NULL; p = p->parent) - p->branch_size++; - } - - /* Color and rebalance. */ - rebalance_after_add (list, new_node, node); - } - -#if WITH_HASHTABLE - /* Add node to the hash table. - Note that this is only possible _after_ the node has been added to the - tree structure, because add_to_bucket() uses node_position(). */ - if (add_to_bucket (list, new_node) < 0) - { - gl_tree_remove_node_from_tree (list, new_node); - free (new_node); - return NULL; - } - hash_resize_after_add (list); -#endif - - return new_node; -} - -static gl_list_node_t -gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) -{ - /* Create new node. */ - gl_list_node_t new_node = - (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->branch_size = 1; - new_node->value = elt; -#if WITH_HASHTABLE - new_node->h.hashcode = - (list->base.hashcode_fn != NULL - ? list->base.hashcode_fn (new_node->value) - : (size_t)(uintptr_t) new_node->value); -#endif - - /* Add it to the tree. */ - if (node->left == NULL) - node->left = new_node; - else - { - for (node = node->left; node->right != NULL; ) - node = node->right; - node->right = new_node; - } - new_node->parent = node; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = node; p != NULL; p = p->parent) - p->branch_size++; - } - - /* Color and rebalance. */ - rebalance_after_add (list, new_node, node); - -#if WITH_HASHTABLE - /* Add node to the hash table. - Note that this is only possible _after_ the node has been added to the - tree structure, because add_to_bucket() uses node_position(). */ - if (add_to_bucket (list, new_node) < 0) - { - gl_tree_remove_node_from_tree (list, new_node); - free (new_node); - return NULL; - } - hash_resize_after_add (list); -#endif - - return new_node; -} - -static gl_list_node_t -gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) -{ - /* Create new node. */ - gl_list_node_t new_node = - (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->branch_size = 1; - new_node->value = elt; -#if WITH_HASHTABLE - new_node->h.hashcode = - (list->base.hashcode_fn != NULL - ? list->base.hashcode_fn (new_node->value) - : (size_t)(uintptr_t) new_node->value); -#endif - - /* Add it to the tree. */ - if (node->right == NULL) - node->right = new_node; - else - { - for (node = node->right; node->left != NULL; ) - node = node->left; - node->left = new_node; - } - new_node->parent = node; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = node; p != NULL; p = p->parent) - p->branch_size++; - } - - /* Color and rebalance. */ - rebalance_after_add (list, new_node, node); - -#if WITH_HASHTABLE - /* Add node to the hash table. - Note that this is only possible _after_ the node has been added to the - tree structure, because add_to_bucket() uses node_position(). */ - if (add_to_bucket (list, new_node) < 0) - { - gl_tree_remove_node_from_tree (list, new_node); - free (new_node); - return NULL; - } - hash_resize_after_add (list); -#endif - - return new_node; -} |