liblzma/common/index.c

72 	/// Every Record group is part of index_stream.groups tree.
75 	/// Number of Blocks in this Stream before this group.
92 	/// is records[last].unpadded_sum in the last Record group of
455 	// thus at least one group.
459 	// Amount of memory needed per group.
674 		// There is space in the last group at least for one Record.
677 		// We need to allocate a new group.
691 		// Set the start offsets of this group.
696 		// Add the new group to the Stream.
700 	// Add the new Record to the group.
793 	// Optimize the last group to minimize memory usage. Allocation has
889 	// a single group. It's simplest and also tends to make
918 	// Add the group to the new Stream.
982 	const index_group *group = iter->internal[ITER_GROUP].p;
986 	// group in the index, because that may be reallocated by
988 	if (group == NULL) {
994 			|| stream->groups.rightmost != &group->node) {
995 		// The group is not not the last group in the index.
998 	} else if (stream->groups.leftmost != &group->node) {
999 		// The group isn't the only group in the Stream, thus we
1000 		// know that it must have a parent group i.e. it's not
1002 		assert(stream->groups.root != &group->node);
1003 		assert(group->node.parent->right == &group->node);
1005 		iter->internal[ITER_GROUP].p = group->node.parent;
1008 		// The Stream has only one group.
1009 		assert(stream->groups.root == &group->node);
1010 		assert(group->node.parent == NULL);
1046 	if (group != NULL) {
1047 		iter->block.number_in_stream = group->number_base + record;
1052 				= record == 0 ? group->node.compressed_base
1053 				: vli_ceil4(group->records[
1056 				= record == 0 ? group->node.uncompressed_base
1057 				: group->records[record - 1].uncompressed_sum;
1060 				= group->records[record].uncompressed_sum
1063 				= group->records[record].unpadded_sum
1111 	const index_group *group = NULL;
1114 	// If we are being asked for the next Stream, leave group to NULL
1118 		// Get the pointer to the current group. See iter_set_inf()
1122 			group = iter->internal[ITER_GROUP].p;
1126 			group = index_tree_next(iter->internal[ITER_GROUP].p);
1130 			group = (const index_group *)(
1153 		group = (const index_group *)(stream->groups.leftmost);
1156 	} else if (group != NULL && record < group->last) {
1157 		// The next Record is in the same group.
1161 		// This group has no more Records or this Stream has
1165 		// If group is not NULL, this Stream has at least one Block
1166 		// and thus at least one group. Find the next group.
1167 		if (group != NULL)
1168 			group = index_tree_next(&group->node);
1170 		if (group == NULL) {
1181 			group = (const index_group *)(
1190 			if (group->node.uncompressed_base
1191 					== group->records[0].uncompressed_sum)
1193 		} else if (group->records[record - 1].uncompressed_sum
1194 				== group->records[record].uncompressed_sum) {
1200 	iter->internal[ITER_GROUP].p = group;
1223 	// Locate the group containing the target offset.
1224 	const index_group *group = index_tree_locate(&stream->groups, target);
1225 	assert(group != NULL);
1233 	size_t right = group->last;
1237 		if (group->records[pos].uncompressed_sum <= target)
1244 	iter->internal[ITER_GROUP].p = group;