tools/testing/radix-tree/multiorder.c

Source file repositories/reference/linux-study-clean/tools/testing/radix-tree/multiorder.c

File Facts

System
Linux kernel
Corpus path
tools/testing/radix-tree/multiorder.c
Extension
.c
Size
6960 bytes
Lines
301
Domain
Support Tooling And Documentation
Bucket
tools
Inferred role
Support Tooling And Documentation: implementation source
Status
source implementation candidate

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

xas_for_each(&xas, item, ULONG_MAX) {
			int height = order[i] / XA_CHUNK_SHIFT;
			int shift = height * XA_CHUNK_SHIFT;
			unsigned long mask = (1UL << order[i]) - 1;

			assert((xas.xa_index | mask) == (index[i] | mask));
			assert(xas.xa_node->shift == shift);
			assert(!radix_tree_is_internal_node(item));
			assert((item->index | mask) == (index[i] | mask));
			assert(item->order == order[i]);
			i++;
		}
	}

	item_kill_tree(xa);
}

void multiorder_tagged_iteration(struct xarray *xa)
{
	XA_STATE(xas, xa, 0);
	struct item *item;
	int i, j;

#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};

	printv(1, "Multiorder tagged iteration test\n");

	for (i = 0; i < MT_NUM_ENTRIES; i++)
		assert(!item_insert_order(xa, index[i], order[i]));

	assert(!xa_marked(xa, XA_MARK_1));

	for (i = 0; i < TAG_ENTRIES; i++)
		xa_set_mark(xa, tag_index[i], XA_MARK_1);

	for (j = 0; j < 256; j++) {
		int 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;
		}

		xas_set(&xas, j);
		xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_1) {
			unsigned long mask;
			for (k = i; index[k] < tag_index[i]; k++)
				;
			mask = (1UL << order[k]) - 1;

			assert((xas.xa_index | mask) == (tag_index[i] | mask));
			assert(!xa_is_internal(item));
			assert((item->index | mask) == (tag_index[i] | mask));
			assert(item->order == order[k]);
			i++;
		}
	}

	assert(tag_tagged_items(xa, 0, ULONG_MAX, TAG_ENTRIES, XA_MARK_1,
				XA_MARK_2) == TAG_ENTRIES);

	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;
		}

		xas_set(&xas, j);
		xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_2) {
			for (k = i; index[k] < tag_index[i]; k++)
				;
			mask = (1 << order[k]) - 1;

			assert((xas.xa_index | mask) == (tag_index[i] | mask));
			assert(!xa_is_internal(item));
			assert((item->index | mask) == (tag_index[i] | mask));
			assert(item->order == order[k]);
			i++;
		}

Annotation

Implementation Notes