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 /* Behold, a tree! */
  25 struct hed_tree {
  26         struct hed_tree_node *root;
  27 };
  28
  29 /**
  30  * tree_entry - get the struct for this entry
  31  * @ptr:        the &struct hed_tree_node pointer.
  32  * @type:       the type of the struct this is embedded in.
  33  * @member:     the name of the struct hed_tree_node within the struct.
  34  */
  35 #define tree_entry(ptr, type, member) ({                        \
  36         const struct hed_tree_node *__mptr = (ptr);                     \
  37         (type *)( (char *)__mptr - offsetof(type,member) );})
  38
  39 #define tree_list_entry(ptr)    list_entry(ptr,struct hed_tree_node,link)
  40
  41 /* THIS IS NOT AN IMPLEMENTATION OF A GENERIC SPLAY TREE
  42  *
  43  * The tree structure implemented here has some limitations which
  44  * do not matter to the only use case (struct hed_file), but allow
  45  * simplifying the code.
  46  *
  47  * 1. The tree always contains at least one node
  48  *    Code that relies on this feature is tagged with the NONEMPTY keyword.
  49  *
  50  * 2. The last node in the tree does not change
  51  *    A pointer to this node is given during initialization already,
  52  *    and it must stay valid for the whole lifetime of the tree.
  53  *    Code that relies on this feature is tagged with the CONSTLAST keyword.
  54  */
  55
  56 /* These prototypes may be in fact defined as macros below! */
  57
  58 /* Initialize a new tree with one element (the tree @root), which is
  59  * the immutable last element of the tree.
  60  */
  61 void init_tree(struct hed_tree *tree, struct hed_tree_node *root);
  62
  63 #define init_node(node) INIT_LIST_HEAD(&(node)->link)
  64
  65 /* Update node information */
  66 void recalc_node_recursive(struct hed_tree_node *item);
  67
  68 /* Delete from the tree, but do NOT recalculate parent nodes. Use this when
  69  * replacing one node with another (equally sized). However, you SHOULD
  70  * recalculate when merging two nodes together etc. - the cover sizes
  71  * might not be right if you merged a child in. */
  72 void del_from_tree(struct hed_tree *tree, struct hed_tree_node *item);
  73
  74 /* Delete from the tree and recalculate parent nodes. */
  75 void recalc_del_from_tree(struct hed_tree *tree, struct hed_tree_node *item);
  76
  77 /* Insert a new item before @pos.
  78  * Inserting at the end (appending to the tree) is not possible.
  79  */
  80 void insert_into_tree(struct hed_tree *tree, struct hed_tree_node *item,
  81                       struct hed_tree_node *pos);
  82
  83 /* Finds the item at or right before the given offset (except when there is
  84  * no item at or before the offset; then it gives the nearest item after
  85  * the offset; you can distinguish the case by item->left being the
  86  * null node. */
  87 struct hed_tree_node *find_in_tree(struct hed_tree *tree, hed_uoff_t offset);
  88
  89 #define prev_in_tree(item)      tree_list_entry((item)->link.prev)
  90 #define next_in_tree(item)      tree_list_entry((item)->link.next)
  91
  92 hed_uoff_t tree_block_offset(struct hed_tree_node *block);
  93
  94 #endif