return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
}
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+/* Sibling slots point directly to another slot in the same node */
+static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
+{
+ void **ptr = node;
+ return (parent->slots <= ptr) &&
+ (ptr < parent->slots + RADIX_TREE_MAP_SIZE);
+}
+#else
+static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
+{
+ return false;
+}
+#endif
+
+static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
+ void **slot)
+{
+ return slot - parent->slots;
+}
+
+static unsigned radix_tree_descend(struct radix_tree_node *parent,
+ struct radix_tree_node **nodep, unsigned offset)
+{
+ void **entry = rcu_dereference_raw(parent->slots[offset]);
+
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+ if (radix_tree_is_indirect_ptr(entry)) {
+ unsigned long siboff = get_slot_offset(parent, entry);
+ if (siboff < RADIX_TREE_MAP_SIZE) {
+ offset = siboff;
+ entry = rcu_dereference_raw(parent->slots[offset]);
+ }
+ }
+#endif
+
+ *nodep = (void *)entry;
+ return offset;
+}
+
static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
{
return root->gfp_mask & __GFP_BITS_MASK;
return height_to_maxindex[height];
}
+static inline unsigned long node_maxindex(struct radix_tree_node *node)
+{
+ return radix_tree_maxindex(node->path & RADIX_TREE_HEIGHT_MASK);
+}
+
+static unsigned radix_tree_load_root(struct radix_tree_root *root,
+ struct radix_tree_node **nodep, unsigned long *maxindex)
+{
+ struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
+
+ *nodep = node;
+
+ if (likely(radix_tree_is_indirect_ptr(node))) {
+ node = indirect_to_ptr(node);
+ *maxindex = node_maxindex(node);
+ return (node->path & RADIX_TREE_HEIGHT_MASK) *
+ RADIX_TREE_MAP_SHIFT;
+ }
+
+ *maxindex = 0;
+ return 0;
+}
+
/*
* Extend a radix tree so it can store key @index.
*/
static int radix_tree_extend(struct radix_tree_root *root,
- unsigned long index, unsigned order)
+ unsigned long index)
{
struct radix_tree_node *node;
struct radix_tree_node *slot;
while (index > radix_tree_maxindex(height))
height++;
- if ((root->rnode == NULL) && (order == 0)) {
+ if (root->rnode == NULL) {
root->height = height;
goto out;
}
node->count = 1;
node->parent = NULL;
slot = root->rnode;
- if (radix_tree_is_indirect_ptr(slot) && newheight > 1) {
+ if (radix_tree_is_indirect_ptr(slot)) {
slot = indirect_to_ptr(slot);
slot->parent = node;
slot = ptr_to_indirect(slot);
root->height = newheight;
} while (height > root->height);
out:
- return 0;
+ return height * RADIX_TREE_MAP_SHIFT;
}
/**
void ***slotp)
{
struct radix_tree_node *node = NULL, *slot;
+ unsigned long maxindex;
unsigned int height, shift, offset;
- int error;
+ unsigned long max = index | ((1UL << order) - 1);
- BUG_ON((0 < order) && (order < RADIX_TREE_MAP_SHIFT));
+ shift = radix_tree_load_root(root, &slot, &maxindex);
/* Make sure the tree is high enough. */
- if (index > radix_tree_maxindex(root->height)) {
- error = radix_tree_extend(root, index, order);
- if (error)
+ if (max > maxindex) {
+ int error = radix_tree_extend(root, max);
+ if (error < 0)
return error;
+ shift = error;
+ slot = root->rnode;
+ if (order == shift) {
+ shift += RADIX_TREE_MAP_SHIFT;
+ root->height++;
+ }
}
- slot = root->rnode;
-
height = root->height;
- shift = height * RADIX_TREE_MAP_SHIFT;
offset = 0; /* uninitialised var warning */
while (shift > order) {
slot = node->slots[offset];
}
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
/* Insert pointers to the canonical entry */
- if ((shift - order) > 0) {
- int i, n = 1 << (shift - order);
+ if (order > shift) {
+ int i, n = 1 << (order - shift);
offset = offset & ~(n - 1);
slot = ptr_to_indirect(&node->slots[offset]);
for (i = 0; i < n; i++) {
node->count++;
}
}
+#endif
if (nodep)
*nodep = node;
return deleted;
}
+static inline void delete_sibling_entries(struct radix_tree_node *node,
+ void *ptr, unsigned offset)
+{
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+ int i;
+ for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
+ if (node->slots[offset + i] != ptr)
+ break;
+ node->slots[offset + i] = NULL;
+ node->count--;
+ }
+#endif
+}
+
/**
* radix_tree_delete_item - delete an item from a radix tree
* @root: radix tree root
unsigned long index, void *item)
{
struct radix_tree_node *node;
- unsigned int offset, i;
+ unsigned int offset;
void **slot;
void *entry;
int tag;
return entry;
}
- offset = index & RADIX_TREE_MAP_MASK;
+ offset = get_slot_offset(node, slot);
/*
* Clear all tags associated with the item to be deleted.
radix_tree_tag_clear(root, index, tag);
}
- /* Delete any sibling slots pointing to this slot */
- for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
- if (node->slots[offset + i] != ptr_to_indirect(slot))
- break;
- node->slots[offset + i] = NULL;
- node->count--;
- }
+ delete_sibling_entries(node, ptr_to_indirect(slot), offset);
node->slots[offset] = NULL;
node->count--;