#include <linux/rcupdate.h>
/*
- * A direct pointer (root->rnode pointing directly to a data item,
- * rather than another radix_tree_node) is signalled by the low bit
- * set in the root->rnode pointer.
+ * An indirect pointer (root->rnode pointing to a radix_tree_node, rather
+ * than a data item) is signalled by the low bit set in the root->rnode
+ * pointer.
*
- * In this case root->height is also NULL, but the direct pointer tests are
- * needed for RCU lookups when root->height is unreliable.
+ * In this case root->height is > 0, but the indirect pointer tests are
+ * needed for RCU lookups (because root->height is unreliable). The only
+ * time callers need worry about this is when doing a lookup_slot under
+ * RCU.
*/
-#define RADIX_TREE_DIRECT_PTR 1
+#define RADIX_TREE_INDIRECT_PTR 1
+#define RADIX_TREE_RETRY ((void *)-1UL)
-static inline void *radix_tree_ptr_to_direct(void *ptr)
+static inline void *radix_tree_ptr_to_indirect(void *ptr)
{
- return (void *)((unsigned long)ptr | RADIX_TREE_DIRECT_PTR);
+ return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
}
-static inline void *radix_tree_direct_to_ptr(void *ptr)
+static inline void *radix_tree_indirect_to_ptr(void *ptr)
{
- return (void *)((unsigned long)ptr & ~RADIX_TREE_DIRECT_PTR);
+ return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
}
-static inline int radix_tree_is_direct_ptr(void *ptr)
+static inline int radix_tree_is_indirect_ptr(void *ptr)
{
- return (int)((unsigned long)ptr & RADIX_TREE_DIRECT_PTR);
+ return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
}
/*** radix-tree API starts here ***/
* management of their lifetimes must be completely managed by API users.
*
* For API usage, in general,
- * - any function _modifying_ the the tree or tags (inserting or deleting
+ * - any function _modifying_ the tree or tags (inserting or deleting
* items, setting or clearing tags must exclude other modifications, and
* exclude any functions reading the tree.
- * - any function _reading_ the the tree or tags (looking up items or tags,
+ * - any function _reading_ the tree or tags (looking up items or tags,
* gang lookups) must exclude modifications to the tree, but may occur
* concurrently with other readers.
*
*/
static inline void *radix_tree_deref_slot(void **pslot)
{
- return radix_tree_direct_to_ptr(*pslot);
+ void *ret = *pslot;
+ if (unlikely(radix_tree_is_indirect_ptr(ret)))
+ ret = RADIX_TREE_RETRY;
+ return ret;
}
/**
* radix_tree_replace_slot - replace item in a slot
*/
static inline void radix_tree_replace_slot(void **pslot, void *item)
{
- BUG_ON(radix_tree_is_direct_ptr(item));
- rcu_assign_pointer(*pslot,
- (void *)((unsigned long)item |
- ((unsigned long)*pslot & RADIX_TREE_DIRECT_PTR)));
+ BUG_ON(radix_tree_is_indirect_ptr(item));
+ rcu_assign_pointer(*pslot, item);
}
int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
unsigned long first_index, unsigned int max_items);
+unsigned long radix_tree_next_hole(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan);
int radix_tree_preload(gfp_t gfp_mask);
void radix_tree_init(void);
void *radix_tree_tag_set(struct radix_tree_root *root,