avl_tree: Cleanup and improve comments
[wimlib] / include / wimlib / avl_tree.h
index 875c9f02a83da8f51acf594f47d02b14a4da3b15..7d13966f33e3d5eeb140e4784903aab963ec937e 100644 (file)
@@ -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);