Mercurial > libjeffpc
view tree.c @ 806:12a3139a2baf
sock: use atomic_cas_ptr correctly
This bug was caused by incorrect documentation (already fixed). It resulted
in us freeing the name on successful CAS and caching the freed pointer.
Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
author | Josef 'Jeff' Sipek <jeffpc@josefsipek.net> |
---|---|
date | Fri, 10 Apr 2020 12:27:10 -0400 |
parents | 0737d17f4959 |
children |
line wrap: on
line source
/* * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal * in the Software without restriction, including without limitation the rights * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell * copies of the Software, and to permit persons to whom the Software is * furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included in * all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ #include <string.h> #include <jeffpc/error.h> #include "tree_impl.h" void *tree_find(struct tree_tree *tree, const void *key, struct tree_cookie *cookie) { struct tree_node *cur; struct tree_cookie where; memset(&where, 0, sizeof(where)); cur = tree->root; while (cur) { int cmp; cmp = tree->cmp(key, node2obj(tree, cur)); if (cmp == 0) return node2obj(tree, cur); where.node = cur; where.dir = (cmp < 0) ? TREE_LEFT : TREE_RIGHT; cur = where.node->children[where.dir]; } if (cookie) *cookie = where; return NULL; } /* * This function is written from the perspective of finding the nearest * greater-than node. The less-than operation simply swaps the definition * of left and right. * * Essentially, we are trying to do one step of an in-order traversal where * the cookie indicates the last position. * * node | dir | meaning * ------+-------+----------------------------- * NULL | * | empty tree / invalid cookie * * | LEFT | return node * * | RIGHT | go up a level, "recursing" */ void *tree_nearest(struct tree_tree *tree, struct tree_cookie *cookie, bool gt) { const enum tree_dir left = gt ? TREE_LEFT : TREE_RIGHT; const enum tree_dir right = gt ? TREE_RIGHT : TREE_LEFT; struct tree_node *node; enum tree_dir dir; node = cookie->node; dir = cookie->dir; if (!node) return NULL; for (;;) { if (dir == left) return node2obj(tree, node); ASSERT3U(dir, ==, right); if (!get_parent(node)) return NULL; /* We finished the right subtree, time to go up the tree */ dir = which_dir(get_parent(node), node); node = get_parent(node); } } void *tree_insert_here(struct tree_tree *tree, void *newitem, struct tree_cookie *cookie) { struct tree_cookie local_cookie; struct tree_node *node; if (!cookie) { void *tmp; tmp = tree_find(tree, newitem, &local_cookie); if (tmp) return tmp; cookie = &local_cookie; } ASSERT(cookie->dir == TREE_LEFT || cookie->dir == TREE_RIGHT); tree->num_nodes++; node = obj2node(tree, newitem); node->children[TREE_LEFT] = NULL; node->children[TREE_RIGHT] = NULL; set_parent(node, cookie->node); if (cookie->node) cookie->node->children[cookie->dir] = node; else tree->root = node; return NULL; } static inline void __swap_nodes(struct tree_tree *tree, struct tree_node *x, struct tree_node *y, const enum tree_dir left) { const enum tree_dir right = 1 - left; const bool root = tree->root == x; enum tree_dir dir_to_orig_x; unsigned int tmp; ASSERT3P(x, !=, y); ASSERT3P(y->children[left], ==, NULL); if (!root) dir_to_orig_x = which_dir(get_parent(x), x); if (x->children[right] == y) { /* * A A * \ \ * \ \ * x y * / \ / \ * / \ => / \ * B y B x * \ \ * \ \ * E E */ struct tree_node *A, *B, *E; A = get_parent(x); B = x->children[left]; E = y->children[right]; set_parent(x, y); set_parent(y, A); set_parent(B, y); if (E) set_parent(E, x); x->children[left] = NULL; x->children[right] = E; y->children[left] = B; y->children[right] = x; if (!root) A->children[dir_to_orig_x] = y; else tree->root = y; } else { /* * A A * \ \ * \ \ * x y * / \ / \ * / \ => / \ * B C B C * / / * . . * . . * / / * D D * / / * / / * y x * \ \ * \ \ * E E */ struct tree_node *A, *B, *C, *D, *E; A = get_parent(x); B = x->children[left]; C = x->children[right]; D = get_parent(y); E = y->children[right]; set_parent(x, D); set_parent(y, A); set_parent(B, y); set_parent(C, y); if (E) set_parent(E, x); x->children[left] = NULL; x->children[right] = E; y->children[left] = B; y->children[right] = C; if (!root) A->children[dir_to_orig_x] = y; else tree->root = y; D->children[left] = x; } /* swap the extra data */ tmp = get_extra(x); set_extra(x, get_extra(y)); set_extra(y, tmp); } static inline void __promote_node_child(struct tree_tree *tree, struct tree_node *parent, struct tree_node *node, struct tree_node *child) { if (parent) parent->children[which_dir(parent, node)] = child; else tree->root = child; if (child) set_parent(child, parent); } /* * Remove @item from @tree. * * @parent_r: the parent node of @child_r (may be NULL) * @child_r: the node that ultimately took @item's new place in the tree * (may be NULL) */ void tree_remove(struct tree_tree *tree, void *item, struct tree_node **parent_r, struct tree_node **child_r) { struct tree_node *parent; struct tree_node *child; struct tree_node *node; ASSERT3P(tree, !=, NULL); ASSERT3P(item, !=, NULL); node = obj2node(tree, item); /* * Two children: exchange it with a leaf-ish node greater than this * node. */ if (node->children[TREE_LEFT] && node->children[TREE_RIGHT]) __swap_nodes(tree, node, firstlast(node->children[TREE_RIGHT], TREE_LEFT), TREE_LEFT); /* now, we have zero or one child */ ASSERT(!node->children[TREE_LEFT] || !node->children[TREE_RIGHT]); parent = get_parent(node); if (node->children[TREE_LEFT]) child = node->children[TREE_LEFT]; else child = node->children[TREE_RIGHT]; __promote_node_child(tree, parent, node, child); /* clear out the removed node */ set_parent(node, NULL); node->children[TREE_LEFT] = NULL; node->children[TREE_RIGHT] = NULL; tree->num_nodes--; /* return various info */ *parent_r = parent; *child_r = child; } void *tree_first(struct tree_tree *tree) { return firstlast_obj(tree, TREE_LEFT); } void *tree_last(struct tree_tree *tree) { return firstlast_obj(tree, TREE_RIGHT); } void *tree_next(struct tree_tree *tree, void *item) { return tree_next_dir(tree, item, true); } void *tree_prev(struct tree_tree *tree, void *item) { return tree_next_dir(tree, item, false); } #define DESTROY_NODES_DONE ((struct tree_node *)(uintptr_t)~0ul) static inline void destroy_nodes_save_parent(struct tree_tree *tree, struct tree_node *node, struct tree_cookie *cookie) { if (node != tree->root) { cookie->node = get_parent(node); cookie->dir = 1 - which_dir(get_parent(node), node); } else { /* indicate end of iteration */ cookie->node = DESTROY_NODES_DONE; } } static struct tree_node *destroy_nodes_step(struct tree_tree *tree, struct tree_node *node, struct tree_cookie *cookie) { ASSERT3P(node, !=, NULL); for (;;) { struct tree_node *tmp; tmp = firstlast(node, TREE_LEFT); if (!tmp->children[TREE_RIGHT]) { destroy_nodes_save_parent(tree, tmp, cookie); return node2obj(tree, tmp); } node = tmp->children[TREE_RIGHT]; } } /* * This function does a post-order traversal of the tree, returning each * node and using the cookie as a cursor. Once a node is returned, it's * memory is assumed to be free. * * The cookie's ->node is used as pointer to the next item to process (not * necessarily return!) and the ->dir member is used to indicate which child * of the next node to look at. * * node | dir | meaning * ------+-------+------------------------------------------ * NULL | * | first invocation, return first node * DONE | * | all nodes destroyed already, return NULL * * | RIGHT | process node's right subtree next * * | LEFT | process node itself next * * Note that since we traverse the tree left to right, we go as far left * every time we descend to the right. That is why there is no explicit * go-left state. */ void *tree_destroy_nodes(struct tree_tree *tree, struct tree_cookie *cookie) { struct tree_node *node; if (!tree->root) return NULL; if (cookie->node == DESTROY_NODES_DONE) { tree->root = NULL; tree->num_nodes = 0; return NULL; } if (!cookie->node) return destroy_nodes_step(tree, tree->root, cookie); /* descend down right subtree */ if (cookie->dir == TREE_RIGHT) { node = cookie->node->children[TREE_RIGHT]; if (node) return destroy_nodes_step(tree, node, cookie); } /* process current node */ node = cookie->node; destroy_nodes_save_parent(tree, cookie->node, cookie); return node2obj(tree, node); } void tree_swap(struct tree_tree *tree1, struct tree_tree *tree2) { struct tree_node *tmp_root; size_t tmp_num_nodes; VERIFY3P(tree1->cmp, ==, tree2->cmp); VERIFY3U(tree1->node_size, ==, tree2->node_size); VERIFY3U(tree1->node_off, ==, tree2->node_off); VERIFY3U(tree1->flavor, ==, tree2->flavor); tmp_root = tree1->root; tmp_num_nodes = tree1->num_nodes; tree1->root = tree2->root; tree1->num_nodes = tree2->num_nodes; tree2->root = tmp_root; tree2->num_nodes = tmp_num_nodes; }