lib: radix-tree: native accounting of exceptional entries

[mirror_ubuntu-artful-kernel.git] / include / linux / radix-tree.h

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index af3581b8a4518119d484b367869035537607070b..7ced8a70cc8b4712e1aab71393a5a22018a13da9 100644 (file)
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -85,9 +85,10 @@ static inline bool radix_tree_is_internal_node(void *ptr)
 #define RADIX_TREE_COUNT_MASK  ((1UL << RADIX_TREE_COUNT_SHIFT) - 1)
 
 struct radix_tree_node {
-       unsigned char   shift;  /* Bits remaining in each slot */
-       unsigned char   offset; /* Slot offset in parent */
-       unsigned int    count;
+       unsigned char   shift;          /* Bits remaining in each slot */
+       unsigned char   offset;         /* Slot offset in parent */
+       unsigned int    count;          /* Total entry count */
+       unsigned char   exceptional;    /* Exceptional entry count */
        union {
                struct {
                        /* Used when ascending tree */
@@ -276,6 +277,9 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
                          struct radix_tree_node **nodep, void ***slotp);
 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
+void __radix_tree_replace(struct radix_tree_root *root,
+                         struct radix_tree_node *node,
+                         void **slot, void *item);
 bool __radix_tree_delete_node(struct radix_tree_root *root,
                              struct radix_tree_node *node);
 void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);