liblzma/common/index.c

47 	/// Root node
50 	/// Leftmost node. Since the tree will be filled sequentially,
51 	/// this won't change after the first node has been added to
55 	/// The rightmost node in the tree. Since the tree is filled
56 	/// sequentially, this is always the node where to add the new data.
73 	index_tree_node node;
108 	/// Every index_stream is a node in the tree of Streams.
109 	index_tree_node node;
119 	/// INDEX_GROUP_SIZE Records per node by default.
194 index_tree_node_end(index_tree_node *node, const lzma_allocator *allocator,
195 		void (*free_func)(void *node, const lzma_allocator *allocator))
199 	if (node->left != NULL)
200 		index_tree_node_end(node->left, allocator, free_func);
202 	if (node->right != NULL)
203 		index_tree_node_end(node->right, allocator, free_func);
205 	free_func(node, allocator);
210 /// Free the memory allocated for a tree. Each node is freed using the
216 		void (*free_func)(void *node, const lzma_allocator *allocator))
227 /// Add a new node to the tree. node->uncompressed_base and
228 /// node->compressed_base must have been set by the caller already.
230 index_tree_append(index_tree *tree, index_tree_node *node)
232 	node->parent = tree->rightmost;
233 	node->left = NULL;
234 	node->right = NULL;
238 	// Handle the special case of adding the first node.
240 		tree->root = node;
241 		tree->leftmost = node;
242 		tree->rightmost = node;
247 	assert(tree->rightmost->uncompressed_base <= node->uncompressed_base);
248 	assert(tree->rightmost->compressed_base < node->compressed_base);
250 	// Add the new node after the rightmost node. It's the correct
252 	tree->rightmost->right = node;
253 	tree->rightmost = node;
257 	// and thus know the state of the tree just by looking at the node
258 	// count. From the node count we can calculate how many steps to go
262 		// Locate the root node for the rotation.
265 			node = node->parent;
268 		// Rotate left using node as the rotation root.
269 		index_tree_node *pivot = node->right;
271 		if (node->parent == NULL) {
274 			assert(node->parent->right == node);
275 			node->parent->right = pivot;
278 		pivot->parent = node->parent;
280 		node->right = pivot->left;
281 		if (node->right != NULL)
282 			node->right->parent = node;
284 		pivot->left = node;
285 		node->parent = pivot;
292 /// Get the next node in the tree. Return NULL if there are no more nodes.
294 index_tree_next(const index_tree_node *node)
296 	if (node->right != NULL) {
297 		node = node->right;
298 		while (node->left != NULL)
299 			node = node->left;
301 		return (void *)(node);
304 	while (node->parent != NULL && node->parent->right == node)
305 		node = node->parent;
307 	return (void *)(node->parent);
311 /// Locate a node that contains the given uncompressed offset. It is
313 /// size of the tree (the last node would be returned in that case still).
318 	const index_tree_node *node = tree->root;
325 	while (node != NULL) {
326 		if (node->uncompressed_base > target) {
327 			node = node->left;
329 			result = node;
330 			node = node->right;
348 	s->node.uncompressed_base = uncompressed_base;
349 	s->node.compressed_base = compressed_base;
350 	s->node.parent = NULL;
351 	s->node.left = NULL;
352 	s->node.right = NULL;
370 index_stream_end(void *node, const lzma_allocator *allocator)
372 	index_stream *s = node;
410 	index_tree_append(&i->streams, &s->node);
564 	return index_file_size(s->node.compressed_base,
660 	if (index_file_size(s->node.compressed_base,
692 		g->node.uncompressed_base = uncompressed_base;
693 		g->node.compressed_base = compressed_base;
697 		index_tree_append(&s->groups, &g->node);
747 	index_stream *left = (index_stream *)(this->node.left);
748 	index_stream *right = (index_stream *)(this->node.right);
753 	this->node.uncompressed_base += info->uncompressed_size;
754 	this->node.compressed_base += info->file_size;
757 	index_tree_append(info->streams, &this->node);
799 			assert(g->node.left == NULL);
800 			assert(g->node.right == NULL);
809 			newg->node = g->node;
817 			if (g->node.parent != NULL) {
818 				assert(g->node.parent->right == &g->node);
819 				g->node.parent->right = &newg->node;
822 			if (s->groups.leftmost == &g->node) {
823 				assert(s->groups.root == &g->node);
824 				s->groups.leftmost = &newg->node;
825 				s->groups.root = &newg->node;
828 			assert(s->groups.rightmost == &g->node);
829 			s->groups.rightmost = &newg->node;
834 			// newg == (void *)&newg->node.
872 	index_stream *dest = index_stream_init(src->node.compressed_base,
873 			src->node.uncompressed_base, src->number,
900 	destg->node.uncompressed_base = 0;
901 	destg->node.compressed_base = 0;
913 		srcg = index_tree_next(&srcg->node);
919 	index_tree_append(&dest->groups, &destg->node);
950 		index_tree_append(&dest->streams, &deststream->node);
952 		srcstream = index_tree_next(&srcstream->node);
993 	} else if (i->streams.rightmost != &stream->node
994 			|| stream->groups.rightmost != &group->node) {
998 	} else if (stream->groups.leftmost != &group->node) {
1001 		// the root node.
1002 		assert(stream->groups.root != &group->node);
1003 		assert(group->node.parent->right == &group->node);
1005 		iter->internal[ITER_GROUP].p = group->node.parent;
1009 		assert(stream->groups.root == &group->node);
1010 		assert(group->node.parent == NULL);
1019 	iter->stream.compressed_offset = stream->node.compressed_base;
1020 	iter->stream.uncompressed_offset = stream->node.uncompressed_base;
1052 				= record == 0 ? group->node.compressed_base
1056 				= record == 0 ? group->node.uncompressed_base
1146 				stream = index_tree_next(&stream->node);
1168 			group = index_tree_next(&group->node);
1175 				stream = index_tree_next(&stream->node);
1190 			if (group->node.uncompressed_base
1221 	target -= stream->node.uncompressed_base;