include/linux/radix-tree.h | 48 +---
lib/Kconfig | 3 -
lib/radix-tree.c | 100 +-------
mm/Kconfig | 1 -
mm/filemap.c | 2 +-
tools/testing/radix-tree/Makefile | 2 +-
tools/testing/radix-tree/generated/autoconf.h | 1 -
tools/testing/radix-tree/main.c | 34 +--
tools/testing/radix-tree/multiorder.c | 337 --------------------------
tools/testing/radix-tree/test.c | 14 +-
tools/testing/radix-tree/test.h | 5 -
11 files changed, 29 insertions(+), 518 deletions(-)
@@ -263,15 +263,9 @@ static inline void radix_tree_replace_slot(void **pslot, void *item)
}
int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
- unsigned order, struct radix_tree_node **nodep,
+ struct radix_tree_node **nodep,
void ***slotp);
-int __radix_tree_insert(struct radix_tree_root *, unsigned long index,
- unsigned order, void *);
-static inline int radix_tree_insert(struct radix_tree_root *root,
- unsigned long index, void *entry)
-{
- return __radix_tree_insert(root, index, 0, entry);
-}
+int radix_tree_insert(struct radix_tree_root *, unsigned long index, void *);
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);
@@ -338,20 +332,8 @@ struct radix_tree_iter {
unsigned long index;
unsigned long next_index;
unsigned long tags;
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- unsigned int shift;
-#endif
};
-static inline unsigned int iter_shift(struct radix_tree_iter *iter)
-{
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- return iter->shift;
-#else
- return 0;
-#endif
-}
-
#define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */
#define RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */
#define RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */
@@ -415,7 +397,7 @@ void **radix_tree_iter_retry(struct radix_tree_iter *iter)
static inline unsigned long
__radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
{
- return iter->index + (slots << iter_shift(iter));
+ return iter->index + slots;
}
/**
@@ -443,7 +425,7 @@ void **radix_tree_iter_next(struct radix_tree_iter *iter)
static __always_inline long
radix_tree_chunk_size(struct radix_tree_iter *iter)
{
- return (iter->next_index - iter->index) >> iter_shift(iter);
+ return iter->next_index - iter->index;
}
static inline struct radix_tree_node *entry_to_node(void *ptr)
@@ -466,22 +448,9 @@ static __always_inline void **
radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
{
if (flags & RADIX_TREE_ITER_TAGGED) {
- void *canon = slot;
-
iter->tags >>= 1;
if (unlikely(!iter->tags))
return NULL;
- while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_internal_node(slot[1])) {
- if (entry_to_node(slot[1]) == canon) {
- iter->tags >>= 1;
- iter->index = __radix_tree_iter_add(iter, 1);
- slot++;
- continue;
- }
- iter->next_index = __radix_tree_iter_add(iter, 1);
- return NULL;
- }
if (likely(iter->tags & 1ul)) {
iter->index = __radix_tree_iter_add(iter, 1);
return slot + 1;
@@ -495,20 +464,11 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
}
} else {
long count = radix_tree_chunk_size(iter);
- void *canon = slot;
while (--count > 0) {
slot++;
iter->index = __radix_tree_iter_add(iter, 1);
- if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_internal_node(*slot)) {
- if (entry_to_node(*slot) == canon)
- continue;
- iter->next_index = iter->index;
- break;
- }
-
if (likely(*slot))
return slot;
if (flags & RADIX_TREE_ITER_CONTIG) {
@@ -362,9 +362,6 @@ config INTERVAL_TREE
for more information.
-config RADIX_TREE_MULTIORDER
- bool
-
config ASSOCIATIVE_ARRAY
bool
help
@@ -76,21 +76,6 @@ static inline void *node_to_entry(void *ptr)
#define RADIX_TREE_RETRY node_to_entry(NULL)
-#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)
{
@@ -103,16 +88,6 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
void **entry = rcu_dereference_raw(parent->slots[offset]);
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- if (radix_tree_is_internal_node(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;
}
@@ -231,12 +206,7 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
void *entry = node->slots[i];
if (!entry)
continue;
- if (is_sibling_entry(node, entry)) {
- pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
- entry, i,
- *(void **)entry_to_node(entry),
- first, last);
- } else if (!radix_tree_is_internal_node(entry)) {
+ if (!radix_tree_is_internal_node(entry)) {
pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
entry, i, first, last);
} else {
@@ -551,29 +521,28 @@ out:
* Returns -ENOMEM, or 0 for success.
*/
int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
- unsigned order, struct radix_tree_node **nodep,
+ struct radix_tree_node **nodep,
void ***slotp)
{
struct radix_tree_node *node = NULL, *child;
void **slot = (void **)&root->rnode;
unsigned long maxindex;
unsigned int shift, offset = 0;
- unsigned long max = index | ((1UL << order) - 1);
shift = radix_tree_load_root(root, &child, &maxindex);
/* Make sure the tree is high enough. */
- if (max > maxindex) {
- int error = radix_tree_extend(root, max, shift);
+ if (index > maxindex) {
+ int error = radix_tree_extend(root, index, shift);
if (error < 0)
return error;
shift = error;
child = root->rnode;
- if (order == shift)
+ if (!shift)
shift += RADIX_TREE_MAP_SHIFT;
}
- while (shift > order) {
+ while (shift > 0) {
shift -= RADIX_TREE_MAP_SHIFT;
if (child == NULL) {
/* Have to add a child node. */
@@ -595,25 +564,6 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
slot = &node->slots[offset];
}
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- /* Insert pointers to the canonical entry */
- if (order > shift) {
- unsigned i, n = 1 << (order - shift);
- offset = offset & ~(n - 1);
- slot = &node->slots[offset];
- child = node_to_entry(slot);
- for (i = 0; i < n; i++) {
- if (slot[i])
- return -EEXIST;
- }
-
- for (i = 1; i < n; i++) {
- rcu_assign_pointer(slot[i], child);
- node->count++;
- }
- }
-#endif
-
if (nodep)
*nodep = node;
if (slotp)
@@ -630,8 +580,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
*
* Insert an item into the radix tree at position @index.
*/
-int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
- unsigned order, void *item)
+int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
{
struct radix_tree_node *node;
void **slot;
@@ -639,7 +588,7 @@ int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
BUG_ON(radix_tree_is_internal_node(item));
- error = __radix_tree_create(root, index, order, &node, &slot);
+ error = __radix_tree_create(root, index, &node, &slot);
if (error)
return error;
if (*slot != NULL)
@@ -658,7 +607,7 @@ int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
return 0;
}
-EXPORT_SYMBOL(__radix_tree_insert);
+EXPORT_SYMBOL(radix_tree_insert);
/**
* __radix_tree_lookup - lookup an item in a radix tree
@@ -894,14 +843,6 @@ int radix_tree_tag_get(struct radix_tree_root *root,
}
EXPORT_SYMBOL(radix_tree_tag_get);
-static inline void __set_iter_shift(struct radix_tree_iter *iter,
- unsigned int shift)
-{
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- iter->shift = shift;
-#endif
-}
-
/**
* radix_tree_next_chunk - find next chunk of slots for iteration
*
@@ -945,7 +886,6 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
iter->index = index;
iter->next_index = maxindex + 1;
iter->tags = 1;
- __set_iter_shift(iter, 0);
return (void **)&root->rnode;
}
@@ -967,8 +907,6 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
else
while (++offset < RADIX_TREE_MAP_SIZE) {
void *slot = node->slots[offset];
- if (is_sibling_entry(node, slot))
- continue;
if (slot)
break;
}
@@ -989,7 +927,6 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
/* Update the iterator state */
iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
iter->next_index = (index | node_maxindex(node)) + 1;
- __set_iter_shift(iter, node->shift);
/* Construct iter->tags bit-mask from node->tags[tag] array */
if (flags & RADIX_TREE_ITER_TAGGED) {
@@ -1112,8 +1049,6 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
node = node->parent;
offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
}
- if (is_sibling_entry(node, node->slots[offset]))
- goto next;
if (tagged >= nr_to_tag)
break;
}
@@ -1329,8 +1264,6 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item,
continue;
}
node = entry_to_node(node);
- if (is_sibling_entry(slot, node))
- continue;
slot = node;
break;
}
@@ -1505,20 +1438,6 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
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
@@ -1558,7 +1477,6 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
node_tag_clear(root, node, tag, offset);
- delete_sibling_entries(node, node_to_entry(slot), offset);
node->slots[offset] = NULL;
node->count--;
@@ -412,7 +412,6 @@ config TRANSPARENT_HUGEPAGE
bool "Transparent Hugepage Support"
depends on HAVE_ARCH_TRANSPARENT_HUGEPAGE
select COMPACTION
- select RADIX_TREE_MULTIORDER
help
Transparent Hugepages allows the kernel to use huge pages and
huge tlb transparently to the applications whenever possible.
@@ -591,7 +591,7 @@ static int page_cache_tree_insert(struct address_space *mapping,
void **slot;
int error;
- error = __radix_tree_create(&mapping->page_tree, page->index, 0,
+ error = __radix_tree_create(&mapping->page_tree, page->index,
&node, &slot);
if (error)
return error;
@@ -3,7 +3,7 @@ CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
LDFLAGS += -lpthread -lurcu
TARGETS = main
OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \
- regression1.o regression2.o regression3.o multiorder.o
+ regression1.o regression2.o regression3.o
targets: $(TARGETS)
@@ -1,3 +1,2 @@
-#define CONFIG_RADIX_TREE_MULTIORDER 1
#define CONFIG_SHMEM 1
#define CONFIG_SWAP 1
@@ -232,18 +232,17 @@ void copy_tag_check(void)
item_kill_tree(&tree);
}
-static void __locate_check(struct radix_tree_root *tree, unsigned long index,
- unsigned order)
+static void __locate_check(struct radix_tree_root *tree, unsigned long index)
{
struct item *item;
unsigned long index2;
- item_insert_order(tree, index, order);
+ item_insert(tree, index);
item = item_lookup(tree, index);
index2 = radix_tree_locate_item(tree, item);
if (index != index2) {
- printf("index %ld order %d inserted; found %ld\n",
- index, order, index2);
+ printf("index %ld inserted; found %ld\n",
+ index, index2);
abort();
}
}
@@ -254,7 +253,7 @@ static void __order_0_locate_check(void)
int i;
for (i = 0; i < 50; i++)
- __locate_check(&tree, rand() % INT_MAX, 0);
+ __locate_check(&tree, rand() % INT_MAX);
item_kill_tree(&tree);
}
@@ -262,28 +261,23 @@ static void __order_0_locate_check(void)
static void locate_check(void)
{
RADIX_TREE(tree, GFP_KERNEL);
- unsigned order;
unsigned long offset, index;
__order_0_locate_check();
- for (order = 0; order < 20; order++) {
- for (offset = 0; offset < (1 << (order + 3));
- offset += (1UL << order)) {
- for (index = 0; index < (1UL << (order + 5));
- index += (1UL << order)) {
- __locate_check(&tree, index + offset, order);
- }
- if (radix_tree_locate_item(&tree, &tree) != -1)
- abort();
-
- item_kill_tree(&tree);
+ for (offset = 0; offset < (1 << 3); offset++) {
+ for (index = 0; index < (1UL << 5); index++) {
+ __locate_check(&tree, index + offset);
}
+ if (radix_tree_locate_item(&tree, &tree) != -1)
+ abort();
+
+ item_kill_tree(&tree);
}
if (radix_tree_locate_item(&tree, &tree) != -1)
abort();
- __locate_check(&tree, -1, 0);
+ __locate_check(&tree, -1);
if (radix_tree_locate_item(&tree, &tree) != -1)
abort();
item_kill_tree(&tree);
@@ -294,8 +288,6 @@ static void single_thread_tests(bool long_run)
int i;
printf("starting single_thread_tests: %d allocated\n", nr_allocated);
- multiorder_checks();
- printf("after multiorder_check: %d allocated\n", nr_allocated);
locate_check();
printf("after locate_check: %d allocated\n", nr_allocated);
tag_check();
deleted file mode 100644
@@ -1,337 +0,0 @@
-/*
- * multiorder.c: Multi-order radix tree entry testing
- * Copyright (c) 2016 Intel Corporation
- * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
- * Author: Matthew Wilcox <matthew.r.wilcox@intel.com>
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms and conditions of the GNU General Public License,
- * version 2, as published by the Free Software Foundation.
- *
- * This program is distributed in the hope it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
- * more details.
- */
-#include <linux/radix-tree.h>
-#include <linux/slab.h>
-#include <linux/errno.h>
-
-#include "test.h"
-
-#define for_each_index(i, base, order) \
- for (i = base; i < base + (1 << order); i++)
-
-static void __multiorder_tag_test(int index, int order)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- int base, err, i;
- unsigned long first = 0;
-
- /* our canonical entry */
- base = index & ~((1 << order) - 1);
-
- printf("Multiorder tag test with index %d, canonical entry %d\n",
- index, base);
-
- err = item_insert_order(&tree, index, order);
- assert(!err);
-
- /*
- * Verify we get collisions for covered indices. We try and fail to
- * insert an exceptional entry so we don't leak memory via
- * item_insert_order().
- */
- for_each_index(i, base, order) {
- err = __radix_tree_insert(&tree, i, order,
- (void *)(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY));
- assert(err == -EEXIST);
- }
-
- for_each_index(i, base, order) {
- assert(!radix_tree_tag_get(&tree, i, 0));
- assert(!radix_tree_tag_get(&tree, i, 1));
- }
-
- assert(radix_tree_tag_set(&tree, index, 0));
-
- for_each_index(i, base, order) {
- assert(radix_tree_tag_get(&tree, i, 0));
- assert(!radix_tree_tag_get(&tree, i, 1));
- }
-
- assert(radix_tree_range_tag_if_tagged(&tree, &first, ~0UL, 10, 0, 1) == 1);
- assert(radix_tree_tag_clear(&tree, index, 0));
-
- for_each_index(i, base, order) {
- assert(!radix_tree_tag_get(&tree, i, 0));
- assert(radix_tree_tag_get(&tree, i, 1));
- }
-
- assert(radix_tree_tag_clear(&tree, index, 1));
-
- assert(!radix_tree_tagged(&tree, 0));
- assert(!radix_tree_tagged(&tree, 1));
-
- item_kill_tree(&tree);
-}
-
-static void multiorder_tag_tests(void)
-{
- /* test multi-order entry for indices 0-7 with no sibling pointers */
- __multiorder_tag_test(0, 3);
- __multiorder_tag_test(5, 3);
-
- /* test multi-order entry for indices 8-15 with no sibling pointers */
- __multiorder_tag_test(8, 3);
- __multiorder_tag_test(15, 3);
-
- /*
- * Our order 5 entry covers indices 0-31 in a tree with height=2.
- * This is broken up as follows:
- * 0-7: canonical entry
- * 8-15: sibling 1
- * 16-23: sibling 2
- * 24-31: sibling 3
- */
- __multiorder_tag_test(0, 5);
- __multiorder_tag_test(29, 5);
-
- /* same test, but with indices 32-63 */
- __multiorder_tag_test(32, 5);
- __multiorder_tag_test(44, 5);
-
- /*
- * Our order 8 entry covers indices 0-255 in a tree with height=3.
- * This is broken up as follows:
- * 0-63: canonical entry
- * 64-127: sibling 1
- * 128-191: sibling 2
- * 192-255: sibling 3
- */
- __multiorder_tag_test(0, 8);
- __multiorder_tag_test(190, 8);
-
- /* same test, but with indices 256-511 */
- __multiorder_tag_test(256, 8);
- __multiorder_tag_test(300, 8);
-
- __multiorder_tag_test(0x12345678UL, 8);
-}
-
-static void multiorder_check(unsigned long index, int order)
-{
- unsigned long i;
- unsigned long min = index & ~((1UL << order) - 1);
- unsigned long max = min + (1UL << order);
- RADIX_TREE(tree, GFP_KERNEL);
-
- printf("Multiorder index %ld, order %d\n", index, order);
-
- assert(item_insert_order(&tree, index, order) == 0);
-
- for (i = min; i < max; i++) {
- struct item *item = item_lookup(&tree, i);
- assert(item != 0);
- assert(item->index == index);
- }
- for (i = 0; i < min; i++)
- item_check_absent(&tree, i);
- for (i = max; i < 2*max; i++)
- item_check_absent(&tree, i);
- for (i = min; i < max; i++) {
- static void *entry = (void *)
- (0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY);
- assert(radix_tree_insert(&tree, i, entry) == -EEXIST);
- }
-
- assert(item_delete(&tree, index) != 0);
-
- for (i = 0; i < 2*max; i++)
- item_check_absent(&tree, i);
-}
-
-static void multiorder_shrink(unsigned long index, int order)
-{
- unsigned long i;
- unsigned long max = 1 << order;
- RADIX_TREE(tree, GFP_KERNEL);
- struct radix_tree_node *node;
-
- printf("Multiorder shrink index %ld, order %d\n", index, order);
-
- assert(item_insert_order(&tree, 0, order) == 0);
-
- node = tree.rnode;
-
- assert(item_insert(&tree, index) == 0);
- assert(node != tree.rnode);
-
- assert(item_delete(&tree, index) != 0);
- assert(node == tree.rnode);
-
- for (i = 0; i < max; i++) {
- struct item *item = item_lookup(&tree, i);
- assert(item != 0);
- assert(item->index == 0);
- }
- for (i = max; i < 2*max; i++)
- item_check_absent(&tree, i);
-
- if (!item_delete(&tree, 0)) {
- printf("failed to delete index %ld (order %d)\n", index, order); abort();
- }
-
- for (i = 0; i < 2*max; i++)
- item_check_absent(&tree, i);
-}
-
-static void multiorder_insert_bug(void)
-{
- RADIX_TREE(tree, GFP_KERNEL);
-
- item_insert(&tree, 0);
- radix_tree_tag_set(&tree, 0, 0);
- item_insert_order(&tree, 3 << 6, 6);
-
- item_kill_tree(&tree);
-}
-
-void multiorder_iteration(void)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- struct radix_tree_iter iter;
- void **slot;
- int i, j, err;
-
- printf("Multiorder iteration test\n");
-
-#define NUM_ENTRIES 11
- int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
- int order[NUM_ENTRIES] = {1, 1, 2, 3, 4, 1, 0, 1, 3, 0, 7};
-
- for (i = 0; i < NUM_ENTRIES; i++) {
- err = item_insert_order(&tree, index[i], order[i]);
- assert(!err);
- }
-
- for (j = 0; j < 256; j++) {
- for (i = 0; i < NUM_ENTRIES; i++)
- if (j <= (index[i] | ((1 << order[i]) - 1)))
- break;
-
- radix_tree_for_each_slot(slot, &tree, &iter, j) {
- int height = order[i] / RADIX_TREE_MAP_SHIFT;
- int shift = height * RADIX_TREE_MAP_SHIFT;
- int mask = (1 << order[i]) - 1;
-
- assert(iter.index >= (index[i] &~ mask));
- assert(iter.index <= (index[i] | mask));
- assert(iter.shift == shift);
- i++;
- }
- }
-
- item_kill_tree(&tree);
-}
-
-void multiorder_tagged_iteration(void)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- struct radix_tree_iter iter;
- void **slot;
- unsigned long first = 0;
- int i, j;
-
- printf("Multiorder tagged iteration test\n");
-
-#define MT_NUM_ENTRIES 9
- int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
- int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7};
-
-#define TAG_ENTRIES 7
- int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
-
- for (i = 0; i < MT_NUM_ENTRIES; i++)
- assert(!item_insert_order(&tree, index[i], order[i]));
-
- assert(!radix_tree_tagged(&tree, 1));
-
- for (i = 0; i < TAG_ENTRIES; i++)
- assert(radix_tree_tag_set(&tree, tag_index[i], 1));
-
- for (j = 0; j < 256; j++) {
- int mask, k;
-
- for (i = 0; i < TAG_ENTRIES; i++) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- if (j <= (index[k] | ((1 << order[k]) - 1)))
- break;
- }
-
- radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- mask = (1 << order[k]) - 1;
-
- assert(iter.index >= (tag_index[i] &~ mask));
- assert(iter.index <= (tag_index[i] | mask));
- i++;
- }
- }
-
- radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
- MT_NUM_ENTRIES, 1, 2);
-
- for (j = 0; j < 256; j++) {
- int mask, k;
-
- for (i = 0; i < TAG_ENTRIES; i++) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- if (j <= (index[k] | ((1 << order[k]) - 1)))
- break;
- }
-
- radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- mask = (1 << order[k]) - 1;
-
- assert(iter.index >= (tag_index[i] &~ mask));
- assert(iter.index <= (tag_index[i] | mask));
- i++;
- }
- }
-
- first = 1;
- radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
- MT_NUM_ENTRIES, 1, 0);
- i = 0;
- radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
- assert(iter.index == tag_index[i]);
- i++;
- }
-
- item_kill_tree(&tree);
-}
-
-void multiorder_checks(void)
-{
- int i;
-
- for (i = 0; i < 20; i++) {
- multiorder_check(200, i);
- multiorder_check(0, i);
- multiorder_check((1UL << i) + 1, i);
- }
-
- for (i = 0; i < 15; i++)
- multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
-
- multiorder_insert_bug();
- multiorder_tag_tests();
- multiorder_iteration();
- multiorder_tagged_iteration();
-}
@@ -24,21 +24,9 @@ int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
return radix_tree_tag_get(root, index, tag);
}
-int __item_insert(struct radix_tree_root *root, struct item *item,
- unsigned order)
-{
- return __radix_tree_insert(root, item->index, order, item);
-}
-
int item_insert(struct radix_tree_root *root, unsigned long index)
{
- return __item_insert(root, item_create(index), 0);
-}
-
-int item_insert_order(struct radix_tree_root *root, unsigned long index,
- unsigned order)
-{
- return __item_insert(root, item_create(index), order);
+ return radix_tree_insert(root, index, item_create(index));
}
int item_delete(struct radix_tree_root *root, unsigned long index)
@@ -8,11 +8,7 @@ struct item {
};
struct item *item_create(unsigned long index);
-int __item_insert(struct radix_tree_root *root, struct item *item,
- unsigned order);
int item_insert(struct radix_tree_root *root, unsigned long index);
-int item_insert_order(struct radix_tree_root *root, unsigned long index,
- unsigned order);
int item_delete(struct radix_tree_root *root, unsigned long index);
struct item *item_lookup(struct radix_tree_root *root, unsigned long index);
@@ -26,7 +22,6 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start,
void item_kill_tree(struct radix_tree_root *root);
void tag_check(void);
-void multiorder_checks(void);
struct item *
item_tag_set(struct radix_tree_root *root, unsigned long index, int tag);