| /* Sequential list data type implemented by a binary tree. |
| Copyright (C) 2006-2007, 2009-2020 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 <https://www.gnu.org/licenses/>. */ |
| |
| /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ |
| |
| /* -------------------------- gl_list_t Data Type -------------------------- */ |
| |
| /* Creates 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; |
| } |
| |
| /* Rotates left a subtree. |
| |
| B D |
| / \ / \ |
| A D --> B E |
| / \ / \ |
| C E A C |
| |
| Changes the tree structure, updates 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; |
| } |
| |
| /* Rotates right a subtree. |
| |
| D B |
| / \ / \ |
| B E --> A D |
| / \ / \ |
| A C C E |
| |
| Changes the tree structure, updates 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; |
| } |
| |
| /* Ensures 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; |
| } |
| } |
| } |
| |
| /* Ensures 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; |
| } |
