kernel/util/RadixBitmap.cpp

40  *	free contiguous range of blocks under the node.  It may contain a
46  *	the ALL-ALLOCATED state and the ALL-FREE state.  If a meta node is
48  *	the node is considered stale.  These states are used to optimize
66  *	linear array.  Each meta node is immediately followed (layed out
74  *	must be encompassed in larger root-node radix.
106 radix_bitmap_init(radix_node *node, uint32 radix, uint32 skip, uint32 slots)
111 	// leaf node
113 		if (node) {
114 			node->big_hint = big_hint;
116 				node->u.bitmap = 0;
118 				node->u.bitmap = (bitmap_t)-1 << big_hint;
123 	// not leaf node
124 	if (node) {
125 		node->big_hint = big_hint;
126 		node->u.available = big_hint;
135 			index = i + radix_bitmap_init(node ? &node[i] : NULL,
139 			index = i + radix_bitmap_init(node ? &node[i] : NULL,
143 			if (node)
144 				node[i].big_hint = TERMINATOR;
220 radix_node_alloc(radix_node *node, radix_slot_t slotIndex, int32 count,
227 		if (node[i].big_hint == TERMINATOR)  // TERMINATOR
230 		if (count <= node[i].big_hint) {
233 				addr = radix_leaf_alloc(&node[i], slotIndex, count);
235 				addr = radix_node_alloc(&node[i], slotIndex, count, radix,
238 				node->u.available -= count;
239 				if (node->big_hint > node->u.available)
240 					node->big_hint = node->u.available;
249 	if (node->big_hint >= count)
250 		node->big_hint = count - 1;
285 radix_node_dealloc(radix_node *node, radix_slot_t slotIndex, uint32 count,
288 	node->u.available += count;
303 			radix_leaf_dealloc(&node[i], slotIndex, v);
305 			radix_node_dealloc(&node[i], slotIndex, v, radix,
308 		if (node->big_hint < node[i].big_hint)
309 			node->big_hint = node[i].big_hint;