#include #include #include #include #include #include #include "test.h" struct item * item_tag_set(struct radix_tree_root *root, unsigned long index, int tag) { return radix_tree_tag_set(root, index, tag); } struct item * item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) { return radix_tree_tag_clear(root, index, tag); } 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); } int item_delete(struct radix_tree_root *root, unsigned long index) { struct item *item = radix_tree_delete(root, index); if (item) { assert(item->index == index); free(item); return 1; } return 0; } struct item *item_create(unsigned long index) { struct item *ret = malloc(sizeof(*ret)); ret->index = index; return ret; } void item_check_present(struct radix_tree_root *root, unsigned long index) { struct item *item; item = radix_tree_lookup(root, index); assert(item != 0); assert(item->index == index); } struct item *item_lookup(struct radix_tree_root *root, unsigned long index) { return radix_tree_lookup(root, index); } void item_check_absent(struct radix_tree_root *root, unsigned long index) { struct item *item; item = radix_tree_lookup(root, index); assert(item == 0); } /* * Scan only the passed (start, start+nr] for present items */ void item_gang_check_present(struct radix_tree_root *root, unsigned long start, unsigned long nr, int chunk, int hop) { struct item *items[chunk]; unsigned long into; for (into = 0; into < nr; ) { int nfound; int nr_to_find = chunk; int i; if (nr_to_find > (nr - into)) nr_to_find = nr - into; nfound = radix_tree_gang_lookup(root, (void **)items, start + into, nr_to_find); assert(nfound == nr_to_find); for (i = 0; i < nfound; i++) assert(items[i]->index == start + into + i); into += hop; } } /* * Scan the entire tree, only expecting present items (start, start+nr] */ void item_full_scan(struct radix_tree_root *root, unsigned long start, unsigned long nr, int chunk) { struct item *items[chunk]; unsigned long into = 0; unsigned long this_index = start; int nfound; int i; // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, chunk))) { // printf("At 0x%08lx, nfound=%d\n", into, nfound); for (i = 0; i < nfound; i++) { assert(items[i]->index == this_index); this_index++; } // printf("Found 0x%08lx->0x%08lx\n", // items[0]->index, items[nfound-1]->index); into = this_index; } if (chunk) assert(this_index == start + nr); nfound = radix_tree_gang_lookup(root, (void **)items, this_index, chunk); assert(nfound == 0); } static int verify_node(struct radix_tree_node *slot, unsigned int tag, int tagged) { int anyset = 0; int i; int j; slot = entry_to_node(slot); /* Verify consistency at this level */ for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { if (slot->tags[tag][i]) { anyset = 1; break; } } if (tagged != anyset) { printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", tag, slot->shift, tagged, anyset); for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { printf("tag %d: ", j); for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) printf("%016lx ", slot->tags[j][i]); printf("\n"); } return 1; } assert(tagged == anyset); /* Go for next level */ if (slot->shift > 0) { for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) if (slot->slots[i]) if (verify_node(slot->slots[i], tag, !!test_bit(i, slot->tags[tag]))) { printf("Failure at off %d\n", i); for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { printf("tag %d: ", j); for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) printf("%016lx ", slot->tags[j][i]); printf("\n"); } return 1; } } return 0; } void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) { struct radix_tree_node *node = root->rnode; if (!radix_tree_is_internal_node(node)) return; verify_node(node, tag, !!root_tag_get(root, tag)); } void item_kill_tree(struct radix_tree_root *root) { struct item *items[32]; int nfound; while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { int i; for (i = 0; i < nfound; i++) { void *ret; ret = radix_tree_delete(root, items[i]->index); assert(ret == items[i]); free(items[i]); } } assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); assert(root->rnode == NULL); } void tree_verify_min_height(struct radix_tree_root *root, int maxindex) { unsigned shift; struct radix_tree_node *node = root->rnode; if (!radix_tree_is_internal_node(node)) { assert(maxindex == 0); return; } node = entry_to_node(node); assert(maxindex <= node_maxindex(node)); shift = node->shift; if (shift > 0) assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); else assert(maxindex > 0); }