liblzma/common/index.c

45 /// \brief      AVL tree to hold index_stream or index_group structures
50 	/// Leftmost node. Since the tree will be filled sequentially,
52 	/// the tree.
55 	/// The rightmost node in the tree. Since the tree is filled
59 	/// Number of nodes in the tree
72 	/// Every Record group is part of index_stream.groups tree.
108 	/// Every index_stream is a node in the tree of Sreams.
117 	/// Record groups of this Stream are stored in a tree.
118 	/// It's a T-tree with AVL-tree balancing. There are
146 	/// AVL-tree containing the Stream(s). Often there is just one
147 	/// Stream, but using a tree keeps lookups fast even when there
182 index_tree_init(index_tree *tree)
184 	tree->root = NULL;
185 	tree->leftmost = NULL;
186 	tree->rightmost = NULL;
187 	tree->count = 0;
197 	// The tree won't ever be very huge, so recursion should be fine.
198 	// 20 levels in the tree is likely quite a lot already in practice.
213 /// Free the meory allocated for a tree. If free_func is not NULL,
218 index_tree_end(index_tree *tree, lzma_allocator *allocator,
221 	if (tree->root != NULL)
222 		index_tree_node_end(tree->root, allocator, free_func);
228 /// Add a new node to the tree. node->uncompressed_base and
231 index_tree_append(index_tree *tree, index_tree_node *node)
233 	node->parent = tree->rightmost;
237 	++tree->count;
240 	if (tree->root == NULL) {
241 		tree->root = node;
242 		tree->leftmost = node;
243 		tree->rightmost = node;
247 	// The tree is always filled sequentially.
248 	assert(tree->rightmost->uncompressed_base <= node->uncompressed_base);
249 	assert(tree->rightmost->compressed_base < node->compressed_base);
253 	tree->rightmost->right = node;
254 	tree->rightmost = node;
256 	// Balance the AVL-tree if needed. We don't need to keep the balance
257 	// factors in nodes, because we always fill the tree sequentially,
258 	// and thus know the state of the tree just by looking at the node
260 	// up in the tree to find the rotation root.
261 	uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count));
264 		up = ctz32(tree->count) + 2;
273 			tree->root = pivot;
293 /// Get the next node in the tree. Return NULL if there are no more nodes.
314 /// size of the tree (the last node would be returned in that case still).
316 index_tree_locate(const index_tree *tree, lzma_vli target)
319 	const index_tree_node *node = tree->root;
321 	assert(tree->leftmost == NULL
322 			|| tree->leftmost->uncompressed_base == 0);
478 	// that limit is used by the tree containing the Streams.
735 	/// Destination index' Stream tree
742 /// Simplest iterative traversal of the source tree wouldn't work, because
743 /// we update the pointers in nodes when moving them to the destination tree.