libhed/tree.h

   1 /* A splay tree implemenatation for file blocks */
   2
   3 /* This is a libhed PRIVATE file.
   4  * Do not include outside of libhed. Do not install on the system.
   5  */
   6
   7 #ifndef LIBHED__TREE_H
   8 #define LIBHED__TREE_H
   9
  10 #include "types.h"
  11 #include <util/lists.h>
  12
  13 /* Prevent polluting linker namespace with internal symbols */
  14 #include "private.h"
  15 #define append_to_tree internal_name(append_to_tree)
  16 #define del_from_tree internal_name(del_from_tree)
  17 #define find_in_tree internal_name(find_in_tree)
  18 #define init_tree internal_name(init_tree)
  19 #define insert_into_tree internal_name(insert_into_tree)
  20 #define recalc_del_from_tree internal_name(recalc_del_from_tree)
  21 #define recalc_node_recursive internal_name(recalc_node_recursive)
  22 #define tree_block_offset internal_name(tree_block_offset)
  23
  24 /**
  25  * tree_entry - get the struct for this entry
  26  * @ptr:        the &struct hed_tree_node pointer.
  27  * @type:       the type of the struct this is embedded in.
  28  * @member:     the name of the struct hed_tree_node within the struct.
  29  */
  30 #define tree_entry(ptr, type, member) ({                        \
  31         const struct hed_tree_node *__mptr = (ptr);                     \
  32         (type *)( (char *)__mptr - offsetof(type,member) );})
  33
  34 #define tree_list_entry(ptr)    list_entry(ptr,struct hed_tree_node,link)
  35
  36 /* These prototypes may be in fact defined as macros below! */
  37
  38 void init_tree(struct hed_tree *tree, struct hed_tree_node *root);
  39
  40 #define init_node(node) INIT_LIST_HEAD(&(node)->link)
  41
  42 /* Update node information */
  43 void recalc_node_recursive(struct hed_tree_node *item);
  44
  45 /* Delete from the tree, but do NOT recalculate parent nodes. Use this when
  46  * replacing one node with another (equally sized). However, you SHOULD
  47  * recalculate when merging two nodes together etc. - the cover sizes
  48  * might not be right if you merged a child in. */
  49 void del_from_tree(struct hed_tree *tree, struct hed_tree_node *item);
  50
  51 /* Delete from the tree and recalculate parent nodes. */
  52 void recalc_del_from_tree(struct hed_tree *tree, struct hed_tree_node *item);
  53
  54 /* Insert a new item after @pos. If @pos is NULL, insert at the beginning. */
  55 void insert_into_tree(struct hed_tree *tree, struct hed_tree_node *item,
  56                       struct hed_tree_node *pos);
  57
  58 /* Finds the item at or right before the given offset (except when there is
  59  * no item at or before the offset; then it gives the nearest item after
  60  * the offset; you can distinguish the case by item->left being the
  61  * null node. */
  62 struct hed_tree_node *find_in_tree(struct hed_tree *tree, hed_uoff_t offset);
  63
  64 #define first_in_tree(tree)     next_in_tree(last_in_tree(tree))
  65 #define prev_in_tree(item)      tree_list_entry((item)->link.prev)
  66 #define next_in_tree(item)      tree_list_entry((item)->link.next)
  67 #define last_in_tree(tree)      ((tree)->last)
  68
  69 hed_uoff_t tree_block_offset(struct hed_tree_node *block);
  70
  71 #endif