X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Favl_tree.h;h=2e07e03c5b7e3dff40663ce0eff81fbd774609ab;hp=da5bbd069d83813bad07a67c2b4d3f7106a9a7a4;hb=a60aa6bebc8cc1d72e89be6b9cfb7338f092158d;hpb=b770e5f2727e6447de45248df81c73604ced0917 diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h index da5bbd06..2e07e03c 100644 --- a/include/wimlib/avl_tree.h +++ b/include/wimlib/avl_tree.h @@ -1,28 +1,28 @@ /* - * avl_tree.h + * avl_tree.h - intrusive, nonrecursive AVL tree data structure (self-balancing + * binary search tree), header file * - * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search - * tree), header file. + * The following copying information applies to this specific source code file: * - * Author: Eric Biggers - * Year: 2014 + * Written in 2014 by Eric Biggers * - * This file is placed into the public domain. You can do whatever you want - * with it. + * To the extent possible under law, the author(s) have dedicated all copyright + * and related and neighboring rights to this software to the public domain + * worldwide via the Creative Commons Zero 1.0 Universal Public Domain + * Dedication (the "CC0"). + * + * This software 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 CC0 for more details. + * + * You should have received a copy of the CC0 along with this software; if not + * see . */ #ifndef _AVL_TREE_H_ #define _AVL_TREE_H_ -#include -#include -#include /* for uintptr_t */ - -#ifdef __GNUC__ -# define AVL_INLINE inline __attribute__((always_inline)) -#else -# define AVL_INLINE inline -#endif +#include "wimlib/types.h" /* Node in an AVL tree. Embed this in some other data structure. */ struct avl_tree_node { @@ -45,7 +45,7 @@ struct avl_tree_node { * 11 => undefined * * The rest of the bits are the pointer to the parent node. It must be - * 4-byte aligned, and it will be NULL if this is the root note and + * 4-byte aligned, and it will be NULL if this is the root node and * therefore has no parent. */ uintptr_t parent_balance; }; @@ -54,57 +54,84 @@ struct avl_tree_node { #define avl_tree_entry(entry, type, member) \ ((type*) ((char *)(entry) - offsetof(type, member))) -/* Extracts the parent pointer from the specified AVL tree node. - * Returns the parent pointer, or NULL if @node is the root node. */ -static AVL_INLINE struct avl_tree_node * +/* Returns a pointer to the parent of the specified AVL tree node, or NULL if it + * is already the root of the tree. */ +static forceinline struct avl_tree_node * avl_get_parent(const struct avl_tree_node *node) { return (struct avl_tree_node *)(node->parent_balance & ~3); } -/* Mark the node as unlinked from any tree. */ -static AVL_INLINE void +/* Marks the specified AVL tree node as unlinked from any tree. */ +static forceinline void avl_tree_node_set_unlinked(struct avl_tree_node *node) { node->parent_balance = (uintptr_t)node; } -/* Returns true iff the specified node has been marked with +/* Returns true iff the specified AVL tree node has been marked with * avl_tree_node_set_unlinked() and has not subsequently been inserted into a * tree. */ -static AVL_INLINE bool +static forceinline bool avl_tree_node_is_unlinked(const struct avl_tree_node *node) { return node->parent_balance == (uintptr_t)node; } -/* Internal use only */ +/* (Internal use only) */ extern void avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr, struct avl_tree_node *inserted); /* - * Look up an item in an AVL tree. + * Looks up an item in the specified AVL tree. * * @root * Pointer to the root of the AVL tree. (This can be NULL --- that just * means the tree is empty.) * * @cmp_ctx - * First argument to pass to the comparison callback --- generally a - * pointer to an object equal to the one being searched for. + * First argument to pass to the comparison callback. This generally + * should be a pointer to an object equal to the one being searched for. * * @cmp * Comparison callback. Must return < 0, 0, or > 0 if the first argument * is less than, equal to, or greater than the second argument, * respectively. The first argument will be @cmp_ctx and the second - * argument will be a pointer to the AVL tree node contained in the item - * inserted into the AVL tree. + * argument will be a pointer to the AVL tree node of an item in the tree. + * + * Returns a pointer to the AVL tree node of the resulting item, or NULL if the + * item was not found. + * + * Example: + * + * struct int_wrapper { + * int data; + * struct avl_tree_node index_node; + * }; + * + * static int _avl_cmp_int_to_node(const void *intptr, + * const struct avl_tree_node *nodeptr) + * { + * int n1 = *(const int *)intptr; + * int n2 = avl_tree_entry(nodeptr, struct int_wrapper, index_node)->data; + * if (n1 < n2) + * return -1; + * else if (n1 > n2) + * return 1; + * else + * return 0; + * } * - * Returns a pointer to the AVL tree node embedded in the resulting item, or - * NULL if the item was not found. + * bool contains_int(struct avl_tree_node *root, int n) + * { + * struct avl_tree_node *result; + * + * result = avl_tree_lookup(root, &n, _avl_cmp_int_to_node); + * return result ? true : false; + * } */ -static AVL_INLINE struct avl_tree_node * +static forceinline struct avl_tree_node * avl_tree_lookup(const struct avl_tree_node *root, const void *cmp_ctx, int (*cmp)(const void *, const struct avl_tree_node *)) @@ -123,11 +150,11 @@ avl_tree_lookup(const struct avl_tree_node *root, return (struct avl_tree_node*)cur; } -/* Same as avl_tree_lookup(), just uses a more specific type for the comparison - * function. Specifically, the item being searched for is expected to be in the - * same format as those already in the tree, with an embedded 'struct - * avl_tree_node'. */ -static AVL_INLINE struct avl_tree_node * +/* Same as avl_tree_lookup(), but uses a more specific type for the comparison + * function. Specifically, with this function the item being searched for is + * expected to be in the same format as those already in the tree, with an + * embedded 'struct avl_tree_node'. */ +static forceinline struct avl_tree_node * avl_tree_lookup_node(const struct avl_tree_node *root, const struct avl_tree_node *node, int (*cmp)(const struct avl_tree_node *, @@ -140,12 +167,12 @@ avl_tree_lookup_node(const struct avl_tree_node *root, } /* - * Insert an item into an AVL tree. + * Inserts an item into the specified AVL tree. * * @root_ptr - * Pointer to the pointer to the root of the AVL tree. (Indirection is - * needed because the root node may change.) Initialize *root_ptr to NULL - * for an empty tree. + * Location of the AVL tree's root pointer. Indirection is needed because + * the root node may change as a result of rotations caused by the + * insertion. Initialize *root_ptr to NULL for an empty tree. * * @item * Pointer to the `struct avl_tree_node' embedded in the item to insert. @@ -158,13 +185,48 @@ avl_tree_lookup_node(const struct avl_tree_node *root, * is less than, equal to, or greater than the second argument, * respectively. The first argument will be @item and the second * argument will be a pointer to an AVL tree node embedded in some - * previously-inserted item that @item is being compared with. + * previously-inserted item to which @item is being compared. + * + * If no item in the tree is comparatively equal (via @cmp) to @item, inserts + * @item and returns NULL. Otherwise does nothing and returns a pointer to the + * AVL tree node embedded in the previously-inserted item which compared equal + * to @item. + * + * Example: + * + * struct int_wrapper { + * int data; + * struct avl_tree_node index_node; + * }; * - * Returns NULL if the item was successfully inserted, otherwise the node of a - * previously-inserted item which compared equal to @item and prevented the new - * insertion of @item. + * #define GET_DATA(i) avl_tree_entry((i), struct int_wrapper, index_node)->data + * + * static int _avl_cmp_ints(const struct avl_tree_node *node1, + * const struct avl_tree_node *node2) + * { + * int n1 = GET_DATA(node1); + * int n2 = GET_DATA(node2); + * if (n1 < n2) + * return -1; + * else if (n1 > n2) + * return 1; + * else + * return 0; + * } + * + * bool insert_int(struct avl_tree_node **root_ptr, int data) + * { + * struct int_wrapper *i = malloc(sizeof(struct int_wrapper)); + * i->data = data; + * if (avl_tree_insert(root_ptr, &i->index_node, _avl_cmp_ints)) { + * // Duplicate. + * free(i); + * return false; + * } + * return true; + * } */ -static AVL_INLINE struct avl_tree_node * +static forceinline struct avl_tree_node * avl_tree_insert(struct avl_tree_node **root_ptr, struct avl_tree_node *item, int (*cmp)(const struct avl_tree_node *, @@ -189,6 +251,8 @@ avl_tree_insert(struct avl_tree_node **root_ptr, return NULL; } +/* Removes an item from the specified AVL tree. + * See implementation for details. */ extern void avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node); @@ -198,7 +262,10 @@ extern struct avl_tree_node * avl_tree_first_in_order(const struct avl_tree_node *root); extern struct avl_tree_node * -avl_tree_next_in_order(const struct avl_tree_node *prev); +avl_tree_next_in_order(const struct avl_tree_node *node); + +extern struct avl_tree_node * +avl_tree_prev_in_order(const struct avl_tree_node *node); extern struct avl_tree_node * avl_tree_first_in_postorder(const struct avl_tree_node *root); @@ -207,4 +274,56 @@ extern struct avl_tree_node * avl_tree_next_in_postorder(const struct avl_tree_node *prev, const struct avl_tree_node *prev_parent); +/* + * Iterate through the nodes in an AVL tree in sorted order. + * You may not modify the tree during the iteration. + * + * @child_struct + * Variable that will receive a pointer to each struct inserted into the + * tree. + * @root + * Root of the AVL tree. + * @struct_name + * Type of *child_struct. + * @struct_member + * Member of @struct_name type that is the AVL tree node. + * + * Example: + * + * struct int_wrapper { + * int data; + * struct avl_tree_node index_node; + * }; + * + * void print_ints(struct avl_tree_node *root) + * { + * struct int_wrapper *i; + * + * avl_tree_for_each_in_order(i, root, struct int_wrapper, index_node) + * printf("%d\n", i->data); + * } + */ +#define avl_tree_for_each_in_order(child_struct, root, \ + struct_name, struct_member) \ + for (struct avl_tree_node *_cur = \ + avl_tree_first_in_order(root); \ + _cur && ((child_struct) = \ + avl_tree_entry(_cur, struct_name, \ + struct_member), 1); \ + _cur = avl_tree_next_in_order(_cur)) + +/* + * Like avl_tree_for_each_in_order(), but iterates through the nodes in + * postorder, so the current node may be deleted or freed. + */ +#define avl_tree_for_each_in_postorder(child_struct, root, \ + struct_name, struct_member) \ + for (struct avl_tree_node *_cur = \ + avl_tree_first_in_postorder(root), *_parent; \ + _cur && ((child_struct) = \ + avl_tree_entry(_cur, struct_name, \ + struct_member), 1) \ + && (_parent = avl_get_parent(_cur), 1); \ + _cur = avl_tree_next_in_postorder(_cur, _parent)) + #endif /* _AVL_TREE_H_ */