common/src/linux_radix.c

46 	return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);
50 radix_pos(long id, int height)
52 	return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
62 		root->height = 0;
71 	int height;
75 	height = root->height - 1;
78 	while (height && node)
79 		node = node->slots[radix_pos(index, height--)];
93 	int height;
99 	height = root->height - 1;
100 	if (height == -1 || index > radix_max(root))
103 		unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height);
104 		unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height);
105 		int pos = radix_pos(index, height);
119 			height--;
121 	} while (height != -1);
132 	int height;
137 	height = root->height - 1;
143 	while (height && node) {
144 		stack[height] = node;
145 		node = node->slots[radix_pos(index, height--)];
151 	 * If we removed something reduce the height of the tree.
162 				root->height = 0;
165 			height++;
166 			node = stack[height];
167 			idx = radix_pos(index, height);
185 	int height;
201 		root->height++;
207 		if (root->height == RADIX_TREE_MAX_HEIGHT) {
232 		root->height++;
235 	/* get radix tree height index */
236 	height = root->height - 1;
239 	for ( ; height != 0; height--) {
240 		idx = radix_pos(index, height);
247 	for (idx = 0; idx != height; idx++) {
259 	for ( ; height != 0; height--) {
260 		idx = radix_pos(index, height);
261 		node->slots[idx] = temp[height - 1];
284 	int height;
305 		root->height++;
311 		if (root->height == RADIX_TREE_MAX_HEIGHT) {
336 		root->height++;
339 	/* get radix tree height index */
340 	height = root->height - 1;
343 	for ( ; height != 0; height--) {
344 		idx = radix_pos(index, height);
351 	for (idx = 0; idx != height; idx++) {
363 	for ( ; height != 0; height--) {
364 		idx = radix_pos(index, height);
365 		node->slots[idx] = temp[height - 1];