X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Favl_tree.h;h=7d13966f33e3d5eeb140e4784903aab963ec937e;hp=875c9f02a83da8f51acf594f47d02b14a4da3b15;hb=54d3007554444024077d89091d63e4a250fedd01;hpb=56f881eba91349abe40dd250ecbf08310cb88ce8 diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h index 875c9f02..7d13966f 100644 --- a/include/wimlib/avl_tree.h +++ b/include/wimlib/avl_tree.h @@ -22,6 +22,7 @@ # define AVL_INLINE inline __attribute__((always_inline)) #else # define AVL_INLINE inline +# warning "AVL tree functions may not be inlined as intended" #endif /* Node in an AVL tree. Embed this in some other data structure. */ @@ -45,7 +46,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,22 +55,22 @@ 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. */ +/* Returns a pointer to the parent of the specified AVL tree node, or NULL if it + * is already the root of the tree. */ static AVL_INLINE 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. */ +/* Marks the specified AVL tree node as unlinked from any tree. */ static AVL_INLINE 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 @@ -78,21 +79,21 @@ 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 @@ -100,8 +101,8 @@ avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr, * respectively. The first argument will be @cmp_ctx and the second * argument will be a pointer to the AVL tree node of an item in the tree. * - * Returns a pointer to the AVL tree node embedded in the resulting item, or - * NULL if the item was not found. + * Returns a pointer to the AVL tree node of the resulting item, or NULL if the + * item was not found. */ static AVL_INLINE struct avl_tree_node * avl_tree_lookup(const struct avl_tree_node *root, @@ -122,10 +123,10 @@ 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'. */ +/* 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 AVL_INLINE struct avl_tree_node * avl_tree_lookup_node(const struct avl_tree_node *root, const struct avl_tree_node *node, @@ -139,12 +140,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. @@ -157,11 +158,12 @@ 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. * - * 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. + * 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. */ static AVL_INLINE struct avl_tree_node * avl_tree_insert(struct avl_tree_node **root_ptr, @@ -188,6 +190,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);