///////////////////////////////////////////////////////////////////////////////

//

/// \file index.c

/// \brief Handling of .xz Indexes and some other Stream information

//

// Author: Lasse Collin

//

// This file has been put into the public domain.

// You can do whatever you want with this file.

//

///////////////////////////////////////////////////////////////////////////////

#include "index.h"

#include "stream_flags_common.h"

/// \brief How many Records to allocate at once

///

/// This should be big enough to avoid making lots of tiny allocations

/// but small enough to avoid too much unused memory at once.

#define INDEX_GROUP_SIZE 512

/// \brief How many Records can be allocated at once at maximum

#define PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))

/// \brief Base structure for index_stream and index_group structures

typedef struct index_tree_node_s index_tree_node;

struct index_tree_node_s {

/// Uncompressed start offset of this Stream (relative to the

/// beginning of the file) or Block (relative to the beginning

/// of the Stream)

lzma_vli uncompressed_base;

/// Compressed start offset of this Stream or Block

lzma_vli compressed_base;

index_tree_node *parent;

index_tree_node *left;

index_tree_node *right;

};

/// \brief AVL tree to hold index_stream or index_group structures

typedef struct {

/// Root node

index_tree_node *root;

/// Leftmost node. Since the tree will be filled sequentially,

/// this won't change after the first node has been added to

/// the tree.

index_tree_node *leftmost;

/// The rightmost node in the tree. Since the tree is filled

/// sequentially, this is always the node where to add the new data.

index_tree_node *rightmost;

/// Number of nodes in the tree

uint32_t count;

} index_tree;

typedef struct {

lzma_vli uncompressed_sum;

lzma_vli unpadded_sum;

} index_record;

typedef struct {

/// Every Record group is part of index_stream.groups tree.

index_tree_node node;

/// Number of Blocks in this Stream before this group.

lzma_vli number_base;

/// Number of Records that can be put in records[].

size_t allocated;

/// Index of the last Record in use.

size_t last;

/// The sizes in this array are stored as cumulative sums relative

/// to the beginning of the Stream. This makes it possible to

/// use binary search in lzma_index_locate().

///

/// Note that the cumulative summing is done specially for

/// unpadded_sum: The previous value is rounded up to the next

/// multiple of four before adding the Unpadded Size of the new

/// Block. The total encoded size of the Blocks in the Stream

/// is records[last].unpadded_sum in the last Record group of

/// the Stream.

///

/// For example, if the Unpadded Sizes are 39, 57, and 81, the

/// stored values are 39, 97 (40 + 57), and 181 (100 + 181).

/// The total encoded size of these Blocks is 184.

///

/// This is a flexible array, because it makes easy to optimize

/// memory usage in case someone concatenates many Streams that

/// have only one or few Blocks.

index_record records[];

} index_group;

typedef struct {

/// Every index_stream is a node in the tree of Sreams.

index_tree_node node;

/// Number of this Stream (first one is 1)

uint32_t number;

/// Total number of Blocks before this Stream

lzma_vli block_number_base;

/// Record groups of this Stream are stored in a tree.

/// It's a T-tree with AVL-tree balancing. There are

/// INDEX_GROUP_SIZE Records per node by default.

/// This keeps the number of memory allocations reasonable

/// and finding a Record is fast.

index_tree groups;

/// Number of Records in this Stream

lzma_vli record_count;

/// Size of the List of Records field in this Stream. This is used

/// together with record_count to calculate the size of the Index

/// field and thus the total size of the Stream.

lzma_vli index_list_size;

/// Stream Flags of this Stream. This is meaningful only if

/// the Stream Flags have been told us with lzma_index_stream_flags().

/// Initially stream_flags.version is set to UINT32_MAX to indicate

/// that the Stream Flags are unknown.

lzma_stream_flags stream_flags;

/// Amount of Stream Padding after this Stream. This defaults to

/// zero and can be set with lzma_index_stream_padding().

lzma_vli stream_padding;

} index_stream;

struct lzma_index_s {

/// AVL-tree containing the Stream(s). Often there is just one

/// Stream, but using a tree keeps lookups fast even when there

/// are many concatenated Streams.

index_tree streams;

/// Uncompressed size of all the Blocks in the Stream(s)

lzma_vli uncompressed_size;

/// Total size of all the Blocks in the Stream(s)

lzma_vli total_size;

/// Total number of Records in all Streams in this lzma_index

lzma_vli record_count;

/// Size of the List of Records field if all the Streams in this

/// lzma_index were packed into a single Stream (makes it simpler to

/// take many .xz files and combine them into a single Stream).

///

/// This value together with record_count is needed to calculate

/// Backward Size that is stored into Stream Footer.

lzma_vli index_list_size;

/// How many Records to allocate at once in lzma_index_append().

/// lzma_index_prealloc().

size_t prealloc;

/// Bitmask indicating what integrity check types have been used

/// as set by lzma_index_stream_flags(). The bit of the last Stream

/// is not included here, since it is possible to change it by

/// calling lzma_index_stream_flags() again.

uint32_t checks;

};

static void

index_tree_init(index_tree *tree)

{

tree->root = NULL;

tree->leftmost = NULL;

tree->rightmost = NULL;

tree->count = 0;

return;

}

/// Helper for index_tree_end()

static void

index_tree_node_end(index_tree_node *node, lzma_allocator *allocator,

void (*free_func)(void *node, lzma_allocator *allocator))

{

// The tree won't ever be very huge, so recursion should be fine.

// 20 levels in the tree is likely quite a lot already in practice.

if (node->left != NULL)

index_tree_node_end(node->left, allocator, free_func);

if (node->right != NULL)

index_tree_node_end(node->right, allocator, free_func);

if (free_func != NULL)

free_func(node, allocator);

lzma_free(node, allocator);

return;

}

/// Free the meory allocated for a tree. If free_func is not NULL,

/// it is called on each node before freeing the node. This is used

/// to free the Record groups from each index_stream before freeing

/// the index_stream itself.

static void

index_tree_end(index_tree *tree, lzma_allocator *allocator,

void (*free_func)(void *node, lzma_allocator *allocator))

{

if (tree->root != NULL)

index_tree_node_end(tree->root, allocator, free_func);

return;

}

/// Add a new node to the tree. node->uncompressed_base and

/// node->compressed_base must have been set by the caller already.

static void

index_tree_append(index_tree *tree, index_tree_node *node)

{

node->parent = tree->rightmost;

node->left = NULL;

node->right = NULL;

++tree->count;

// Handle the special case of adding the first node.

if (tree->root == NULL) {

tree->root = node;

tree->leftmost = node;

tree->rightmost = node;

return;

}

// The tree is always filled sequentially.

assert(tree->rightmost->uncompressed_base <= node->uncompressed_base);

assert(tree->rightmost->compressed_base < node->compressed_base);

// Add the new node after the rightmost node. It's the correct

// place due to the reason above.

tree->rightmost->right = node;

tree->rightmost = node;

// Balance the AVL-tree if needed. We don't need to keep the balance

// factors in nodes, because we always fill the tree sequentially,

// and thus know the state of the tree just by looking at the node

// count. From the node count we can calculate how many steps to go

// up in the tree to find the rotation root.

uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count));

if (up != 0) {

// Locate the root node for the rotation.

up = ctz32(tree->count) + 2;

do {

node = node->parent;

} while (--up > 0);

// Rotate left using node as the rotation root.

index_tree_node *pivot = node->right;

if (node->parent == NULL) {

tree->root = pivot;

} else {

assert(node->parent->right == node);

node->parent->right = pivot;

}

pivot->parent = node->parent;

node->right = pivot->left;

if (node->right != NULL)

node->right->parent = node;

pivot->left = node;

node->parent = pivot;

}

return;

}

/// Get the next node in the tree. Return NULL if there are no more nodes.

static void *

index_tree_next(const index_tree_node *node)

{

if (node->right != NULL) {

node = node->right;

while (node->left != NULL)

node = node->left;

return (void *)(node);

}

while (node->parent != NULL && node->parent->right == node)

node = node->parent;

return (void *)(node->parent);

}

/// Locate a node that contains the given uncompressed offset. It is

/// caller's job to check that target is not bigger than the uncompressed

/// size of the tree (the last node would be returned in that case still).

static void *

index_tree_locate(const index_tree *tree, lzma_vli target)

{

const index_tree_node *result = NULL;

const index_tree_node *node = tree->root;

assert(tree->leftmost == NULL

|| tree->leftmost->uncompressed_base == 0);

// Consecutive nodes may have the same uncompressed_base.

// We must pick the rightmost one.

while (node != NULL) {

if (node->uncompressed_base > target) {

node = node->left;

} else {

result = node;

node = node->right;

}

}

return (void *)(result);

}

/// Allocate and initialize a new Stream using the given base offsets.

static index_stream *

index_stream_init(lzma_vli compressed_base, lzma_vli uncompressed_base,

lzma_vli stream_number, lzma_vli block_number_base,

lzma_allocator *allocator)

{

index_stream *s = lzma_alloc(sizeof(index_stream), allocator);

if (s == NULL)

return NULL;

s->node.uncompressed_base = uncompressed_base;

s->node.compressed_base = compressed_base;

s->node.parent = NULL;

s->node.left = NULL;

s->node.right = NULL;

s->number = stream_number;

s->block_number_base = block_number_base;

index_tree_init(&s->groups);

s->record_count = 0;

s->index_list_size = 0;

s->stream_flags.version = UINT32_MAX;

s->stream_padding = 0;

return s;

}

/// Free the memory allocated for a Stream and its Record groups.

static void

index_stream_end(void *node, lzma_allocator *allocator)

{

index_stream *s = node;

index_tree_end(&s->groups, allocator, NULL);

return;

}

static lzma_index *

index_init_plain(lzma_allocator *allocator)

{

lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator);

if (i != NULL) {

index_tree_init(&i->streams);

i->uncompressed_size = 0;

i->total_size = 0;

i->record_count = 0;

i->index_list_size = 0;

i->prealloc = INDEX_GROUP_SIZE;

i->checks = 0;

}

return i;

}

extern LZMA_API(lzma_index *)

lzma_index_init(lzma_allocator *allocator)

{

lzma_index *i = index_init_plain(allocator);

if (i == NULL)

return NULL;

}

index_tree_append(&i->streams, &s->node);

return i;

}

extern LZMA_API(void)

lzma_index_end(lzma_index *i, lzma_allocator *allocator)

{

// NOTE: If you modify this function, check also the bottom

// of lzma_index_cat().

if (i != NULL) {

index_tree_end(&i->streams, allocator, &index_stream_end);

lzma_free(i, allocator);

}

return;

}

extern void

lzma_index_prealloc(lzma_index *i, lzma_vli records)

{

if (records > PREALLOC_MAX)

records = PREALLOC_MAX;

i->prealloc = (size_t)(records);

return;

}

extern LZMA_API(uint64_t)

lzma_index_memusage(lzma_vli streams, lzma_vli blocks)

{

// This calculates an upper bound that is only a little bit

// bigger than the exact maximum memory usage with the given

// parameters.

// Typical malloc() overhead is 2 * sizeof(void *) but we take

// a little bit extra just in case. Using LZMA_MEMUSAGE_BASE

// instead would give too inaccurate estimate.

const size_t alloc_overhead = 4 * sizeof(void *);

// Amount of memory needed for each Stream base structures.

// We assume that every Stream has at least one Block and

// thus at least one group.

const size_t stream_base = sizeof(index_stream)

+ sizeof(index_group) + 2 * alloc_overhead;

// Amount of memory needed per group.

const size_t group_base = sizeof(index_group)

+ INDEX_GROUP_SIZE * sizeof(index_record)

+ alloc_overhead;

// Number of groups. There may actually be more, but that overhead

// has been taken into account in stream_base already.

const lzma_vli groups

= (blocks + INDEX_GROUP_SIZE - 1) / INDEX_GROUP_SIZE;

// Memory used by index_stream and index_group structures.

const uint64_t streams_mem = streams * stream_base;

const uint64_t groups_mem = groups * group_base;

// Memory used by the base structure.

const uint64_t index_base = sizeof(lzma_index) + alloc_overhead;

// Validate the arguments and catch integer overflows.

// Maximum number of Streams is "only" UINT32_MAX, because

// that limit is used by the tree containing the Streams.

const uint64_t limit = UINT64_MAX - index_base;

if (streams == 0 || streams > UINT32_MAX || blocks > LZMA_VLI_MAX

|| streams > limit / stream_base

|| groups > limit / group_base

|| limit - streams_mem < groups_mem)

return UINT64_MAX;

return index_base + streams_mem + groups_mem;

}

extern LZMA_API(uint64_t)

lzma_index_memused(const lzma_index *i)

{

return lzma_index_memusage(i->streams.count, i->record_count);

}

extern LZMA_API(lzma_vli)

lzma_index_block_count(const lzma_index *i)

{

return i->record_count;

}

extern LZMA_API(lzma_vli)

lzma_index_stream_count(const lzma_index *i)

{

return i->streams.count;

}

extern LZMA_API(lzma_vli)

lzma_index_size(const lzma_index *i)

{

return index_size(i->record_count, i->index_list_size);

}

extern LZMA_API(lzma_vli)

lzma_index_total_size(const lzma_index *i)

{

return i->total_size;

}

extern LZMA_API(lzma_vli)

lzma_index_stream_size(const lzma_index *i)

{

// Stream Header + Blocks + Index + Stream Footer

return LZMA_STREAM_HEADER_SIZE + i->total_size

+ index_size(i->record_count, i->index_list_size)

+ LZMA_STREAM_HEADER_SIZE;

}

static lzma_vli

index_file_size(lzma_vli compressed_base, lzma_vli unpadded_sum,

lzma_vli record_count, lzma_vli index_list_size,

lzma_vli stream_padding)

{

// Earlier Streams and Stream Paddings + Stream Header

// + Blocks + Index + Stream Footer + Stream Padding

//

// This might go over LZMA_VLI_MAX due to too big unpadded_sum

// when this function is used in lzma_index_append().

lzma_vli file_size = compressed_base + 2 * LZMA_STREAM_HEADER_SIZE

+ stream_padding + vli_ceil4(unpadded_sum);

if (file_size > LZMA_VLI_MAX)

return LZMA_VLI_UNKNOWN;

// The same applies here.

file_size += index_size(record_count, index_list_size);

if (file_size > LZMA_VLI_MAX)

return LZMA_VLI_UNKNOWN;

return file_size;

}

extern LZMA_API(lzma_vli)

lzma_index_file_size(const lzma_index *i)

{

const index_stream *s = (const index_stream *)(i->streams.rightmost);

const index_group *g = (const index_group *)(s->groups.rightmost);

return index_file_size(s->node.compressed_base,

g == NULL ? 0 : g->records[g->last].unpadded_sum,

s->record_count, s->index_list_size,

s->stream_padding);

}

extern LZMA_API(lzma_vli)

lzma_index_uncompressed_size(const lzma_index *i)

{

return i->uncompressed_size;

}

extern LZMA_API(uint32_t)

lzma_index_checks(const lzma_index *i)

{

uint32_t checks = i->checks;

// Get the type of the Check of the last Stream too.

const index_stream *s = (const index_stream *)(i->streams.rightmost);

if (s->stream_flags.version != UINT32_MAX)

checks |= UINT32_C(1) << s->stream_flags.check;

return checks;

}

extern uint32_t

lzma_index_padding_size(const lzma_index *i)

{

return (LZMA_VLI_C(4) - index_size_unpadded(

i->record_count, i->index_list_size)) & 3;

}

extern LZMA_API(lzma_ret)

lzma_index_stream_flags(lzma_index *i, const lzma_stream_flags *stream_flags)

{

if (i == NULL || stream_flags == NULL)

return LZMA_PROG_ERROR;

// Validate the Stream Flags.

return_if_error(lzma_stream_flags_compare(

stream_flags, stream_flags));

index_stream *s = (index_stream *)(i->streams.rightmost);

s->stream_flags = *stream_flags;

return LZMA_OK;

}

extern LZMA_API(lzma_ret)

lzma_index_stream_padding(lzma_index *i, lzma_vli stream_padding)

{

if (i == NULL || stream_padding > LZMA_VLI_MAX

|| (stream_padding & 3) != 0)

return LZMA_PROG_ERROR;

index_stream *s = (index_stream *)(i->streams.rightmost);

// Check that the new value won't make the file grow too big.

const lzma_vli old_stream_padding = s->stream_padding;

s->stream_padding = 0;

if (lzma_index_file_size(i) + stream_padding > LZMA_VLI_MAX) {

s->stream_padding = old_stream_padding;

return LZMA_DATA_ERROR;

}

s->stream_padding = stream_padding;

return LZMA_OK;

}

extern LZMA_API(lzma_ret)

lzma_index_append(lzma_index *i, lzma_allocator *allocator,

lzma_vli unpadded_size, lzma_vli uncompressed_size)

{

// Validate.

if (i == NULL || unpadded_size < UNPADDED_SIZE_MIN

|| unpadded_size > UNPADDED_SIZE_MAX

|| uncompressed_size > LZMA_VLI_MAX)

return LZMA_PROG_ERROR;

index_stream *s = (index_stream *)(i->streams.rightmost);

index_group *g = (index_group *)(s->groups.rightmost);

const lzma_vli compressed_base = g == NULL ? 0

: vli_ceil4(g->records[g->last].unpadded_sum);

const lzma_vli uncompressed_base = g == NULL ? 0

: g->records[g->last].uncompressed_sum;

const uint32_t index_list_size_add = lzma_vli_size(unpadded_size)

+ lzma_vli_size(uncompressed_size);

// Check that the file size will stay within limits.

if (index_file_size(s->node.compressed_base,

compressed_base + unpadded_size, s->record_count + 1,

s->index_list_size + index_list_size_add,

s->stream_padding) == LZMA_VLI_UNKNOWN)

return LZMA_DATA_ERROR;

// The size of the Index field must not exceed the maximum value

// that can be stored in the Backward Size field.

if (index_size(i->record_count + 1,

i->index_list_size + index_list_size_add)

> LZMA_BACKWARD_SIZE_MAX)

return LZMA_DATA_ERROR;

if (g != NULL && g->last + 1 < g->allocated) {

// There is space in the last group at least for one Record.

++g->last;

} else {

// We need to allocate a new group.

g = lzma_alloc(sizeof(index_group)

+ i->prealloc * sizeof(index_record),

allocator);

if (g == NULL)

return LZMA_MEM_ERROR;

g->last = 0;

g->allocated = i->prealloc;

// Reset prealloc so that if the application happens to

// add new Records, the allocation size will be sane.

i->prealloc = INDEX_GROUP_SIZE;

// Set the start offsets of this group.

g->node.uncompressed_base = uncompressed_base;

g->node.compressed_base = compressed_base;

g->number_base = s->record_count + 1;

// Add the new group to the Stream.

index_tree_append(&s->groups, &g->node);

}

// Add the new Record to the group.

g->records[g->last].uncompressed_sum

= uncompressed_base + uncompressed_size;

g->records[g->last].unpadded_sum

= compressed_base + unpadded_size;

// Update the totals.

++s->record_count;

s->index_list_size += index_list_size_add;

i->total_size += vli_ceil4(unpadded_size);

i->uncompressed_size += uncompressed_size;

++i->record_count;

i->index_list_size += index_list_size_add;

return LZMA_OK;

}

/// Structure to pass info to index_cat_helper()

typedef struct {

/// Uncompressed size of the destination

lzma_vli uncompressed_size;

/// Compressed file size of the destination

lzma_vli file_size;

/// Same as above but for Block numbers

lzma_vli block_number_add;

/// Number of Streams that were in the destination index before we

/// started appending new Streams from the source index. This is

/// used to fix the Stream numbering.

uint32_t stream_number_add;

/// Destination index' Stream tree

index_tree *streams;

} index_cat_info;

/// Add the Stream nodes from the source index to dest using recursion.

/// Simplest iterative traversal of the source tree wouldn't work, because

/// we update the pointers in nodes when moving them to the destination tree.

static void

index_cat_helper(const index_cat_info *info, index_stream *this)

{

index_stream *left = (index_stream *)(this->node.left);

index_stream *right = (index_stream *)(this->node.right);

if (left != NULL)

index_cat_helper(info, left);

this->node.uncompressed_base += info->uncompressed_size;

this->node.compressed_base += info->file_size;

this->number += info->stream_number_add;

this->block_number_base += info->block_number_add;

index_tree_append(info->streams, &this->node);

if (right != NULL)

index_cat_helper(info, right);

return;

}

extern LZMA_API(lzma_ret)

lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src,

lzma_allocator *allocator)

{

const lzma_vli dest_file_size = lzma_index_file_size(dest);

// Check that we don't exceed the file size limits.

if (dest_file_size + lzma_index_file_size(src) > LZMA_VLI_MAX

|| dest->uncompressed_size + src->uncompressed_size

> LZMA_VLI_MAX)

return LZMA_DATA_ERROR;

// Check that the encoded size of the combined lzma_indexes stays

// within limits. In theory, this should be done only if we know

// that the user plans to actually combine the Streams and thus

// construct a single Index (probably rare). However, exceeding

// this limit is quite theoretical, so we do this check always

// to simplify things elsewhere.

{

const lzma_vli dest_size = index_size_unpadded(

dest->record_count, dest->index_list_size);

const lzma_vli src_size = index_size_unpadded(

src->record_count, src->index_list_size);

if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX)

return LZMA_DATA_ERROR;

}

// Optimize the last group to minimize memory usage. Allocation has

// to be done before modifying dest or src.

{

index_stream *s = (index_stream *)(dest->streams.rightmost);

index_group *g = (index_group *)(s->groups.rightmost);

if (g != NULL && g->last + 1 < g->allocated) {

assert(g->node.left == NULL);

assert(g->node.right == NULL);

index_group *newg = lzma_alloc(sizeof(index_group)

+ (g->last + 1)

* sizeof(index_record),

allocator);

if (newg == NULL)

return LZMA_MEM_ERROR;

newg->node = g->node;

newg->allocated = g->last + 1;

newg->last = g->last;

newg->number_base = g->number_base;

memcpy(newg->records, g->records, newg->allocated

* sizeof(index_record));

if (g->node.parent != NULL) {

assert(g->node.parent->right == &g->node);

g->node.parent->right = &newg->node;

}

if (s->groups.leftmost == &g->node) {

assert(s->groups.root == &g->node);

s->groups.leftmost = &newg->node;

s->groups.root = &newg->node;

}

if (s->groups.rightmost == &g->node)

s->groups.rightmost = &newg->node;

lzma_free(g, allocator);

}

}

// Add all the Streams from src to dest. Update the base offsets

// of each Stream from src.

const index_cat_info info = {

.uncompressed_size = dest->uncompressed_size,

.file_size = dest_file_size,

.stream_number_add = dest->streams.count,

.block_number_add = dest->record_count,

.streams = &dest->streams,

};

index_cat_helper(&info, (index_stream *)(src->streams.root));

// Update info about all the combined Streams.

dest->uncompressed_size += src->uncompressed_size;

dest->total_size += src->total_size;

dest->record_count += src->record_count;

dest->index_list_size += src->index_list_size;

dest->checks = lzma_index_checks(dest) | src->checks;

// There's nothing else left in src than the base structure.

lzma_free(src, allocator);

return LZMA_OK;

}

/// Duplicate an index_stream.

static index_stream *

index_dup_stream(const index_stream *src, lzma_allocator *allocator)

{

// Catch a somewhat theoretical integer overflow.

if (src->record_count > PREALLOC_MAX)

return NULL;

// Allocate and initialize a new Stream.

index_stream *dest = index_stream_init(src->node.compressed_base,

src->node.uncompressed_base, src->number,

src->block_number_base, allocator);

// Return immediately if allocation failed or if there are

// no groups to duplicate.

if (dest == NULL || src->groups.leftmost == NULL)

return dest;

// Copy the overall information.

dest->record_count = src->record_count;

dest->index_list_size = src->index_list_size;

dest->stream_flags = src->stream_flags;

dest->stream_padding = src->stream_padding;

// Allocate memory for the Records. We put all the Records into

// a single group. It's simplest and also tends to make

// lzma_index_locate() a little bit faster with very big Indexes.

index_group *destg = lzma_alloc(sizeof(index_group)

+ src->record_count * sizeof(index_record),

allocator);

if (destg == NULL) {

index_stream_end(dest, allocator);

return NULL;

}

// Initialize destg.

destg->node.uncompressed_base = 0;

destg->node.compressed_base = 0;

destg->number_base = 1;

destg->allocated = src->record_count;

destg->last = src->record_count - 1;

// Go through all the groups in src and copy the Records into destg.

const index_group *srcg = (const index_group *)(src->groups.leftmost);

size_t i = 0;

do {

memcpy(destg->records + i, srcg->records,

(srcg->last + 1) * sizeof(index_record));

i += srcg->last + 1;

srcg = index_tree_next(&srcg->node);

} while (srcg != NULL);

assert(i == destg->allocated);

// Add the group to the new Stream.

index_tree_append(&dest->groups, &destg->node);

return dest;

}

extern LZMA_API(lzma_index *)

lzma_index_dup(const lzma_index *src, lzma_allocator *allocator)

{

// Allocate the base structure (no initial Stream).

lzma_index *dest = index_init_plain(allocator);

if (dest == NULL)

return NULL;

// Copy the totals.

dest->uncompressed_size = src->uncompressed_size;

dest->total_size = src->total_size;

dest->record_count = src->record_count;

dest->index_list_size = src->index_list_size;

// Copy the Streams and the groups in them.

const index_stream *srcstream

= (const index_stream *)(src->streams.leftmost);

do {

index_stream *deststream = index_dup_stream(

srcstream, allocator);

if (deststream == NULL) {

lzma_index_end(dest, allocator);

return NULL;

}

index_tree_append(&dest->streams, &deststream->node);

srcstream = index_tree_next(&srcstream->node);

} while (srcstream != NULL);

return dest;

}

/// Indexing for lzma_index_iter.internal[]

enum {

ITER_INDEX,

ITER_STREAM,

ITER_GROUP,

ITER_RECORD,

ITER_METHOD,

};

/// Values for lzma_index_iter.internal[ITER_METHOD].s

enum {

ITER_METHOD_NORMAL,

ITER_METHOD_NEXT,

ITER_METHOD_LEFTMOST,

};

static void

iter_set_info(lzma_index_iter *iter)

{

const lzma_index *i = iter->internal[ITER_INDEX].p;

const index_stream *stream = iter->internal[ITER_STREAM].p;

const index_group *group = iter->internal[ITER_GROUP].p;

const size_t record = iter->internal[ITER_RECORD].s;

// lzma_index_iter.internal must not contain a pointer to the last

// group in the index, because that may be reallocated by

// lzma_index_cat().

if (group == NULL) {

// There are no groups.

assert(stream->groups.root == NULL);

iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;

} else if (i->streams.rightmost != &stream->node

|| stream->groups.rightmost != &group->node) {

// The group is not not the last group in the index.

iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;

} else if (stream->groups.leftmost != &group->node) {

// The group isn't the only group in the Stream, thus we

// know that it must have a parent group i.e. it's not

// the root node.

assert(stream->groups.root != &group->node);

assert(group->node.parent->right == &group->node);

iter->internal[ITER_METHOD].s = ITER_METHOD_NEXT;