/tmp/buildd/xz-utils-5.0.0/src/liblzma/common/index.c File Reference

Handling of .xz Indexes and some other Stream information. More...

#include "index.h"
#include "stream_flags_common.h"

Data Structures
struct	index_tree_node_s
struct	index_tree
	AVL tree to hold index_stream or index_group structures. More...
struct	index_record
struct	index_group
struct	index_stream
struct	lzma_index_s
struct	index_cat_info
	Structure to pass info to index_cat_helper(). More...
Defines
#define	INDEX_GROUP_SIZE   512
	How many Records to allocate at once.
#define	PREALLOC_MAX   ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))
	How many Records can be allocated at once at maximum.
Typedefs
typedef struct index_tree_node_s	index_tree_node
	Base structure for index_stream and index_group structures.
Enumerations
enum	{   ITER_INDEX, ITER_STREAM, ITER_GROUP, ITER_RECORD,   ITER_METHOD }
	Indexing for lzma_index_iter.internal[]. More...
enum	{ ITER_METHOD_NORMAL, ITER_METHOD_NEXT, ITER_METHOD_LEFTMOST }
	Values for lzma_index_iter.internal[ITER_METHOD].s. More...
Functions
static void	index_tree_init (index_tree *tree)
static void	index_tree_node_end (index_tree_node *node, lzma_allocator *allocator, void(*free_func)(void *node, lzma_allocator *allocator))
	Helper for index_tree_end().
static void	index_tree_end (index_tree *tree, lzma_allocator *allocator, void(*free_func)(void *node, lzma_allocator *allocator))
static void	index_tree_append (index_tree *tree, index_tree_node *node)
static void *	index_tree_next (const index_tree_node *node)
	Get the next node in the tree. Return NULL if there are no more nodes.
static void *	index_tree_locate (const index_tree *tree, lzma_vli target)
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)
	Allocate and initialize a new Stream using the given base offsets.
static void	index_stream_end (void *node, lzma_allocator *allocator)
	Free the memory allocated for a Stream and its Record groups.
static lzma_index *	index_init_plain (lzma_allocator *allocator)
lzma_index *	lzma_index_init (lzma_allocator *allocator)
	Allocate and initialize a new lzma_index structure.
void	lzma_index_end (lzma_index *i, lzma_allocator *allocator)
	Deallocate lzma_index.
void	lzma_index_prealloc (lzma_index *i, lzma_vli records)
uint64_t	lzma_index_memusage (lzma_vli streams, lzma_vli blocks)
	Calculate memory usage of lzma_index.
uint64_t	lzma_index_memused (const lzma_index *i)
	Calculate the memory usage of an existing lzma_index.
lzma_vli	lzma_index_block_count (const lzma_index *i)
	Get the number of Blocks.
lzma_vli	lzma_index_stream_count (const lzma_index *i)
	Get the number of Streams.
lzma_vli	lzma_index_size (const lzma_index *i)
	Get the size of the Index field as bytes.
lzma_vli	lzma_index_total_size (const lzma_index *i)
	Get the total size of the Blocks.
lzma_vli	lzma_index_stream_size (const lzma_index *i)
	Get the total size of the Stream.
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)
lzma_vli	lzma_index_file_size (const lzma_index *i)
	Get the total size of the file.
lzma_vli	lzma_index_uncompressed_size (const lzma_index *i)
	Get the uncompressed size of the file.
uint32_t	lzma_index_checks (const lzma_index *i)
	Get the types of integrity Checks.
uint32_t	lzma_index_padding_size (const lzma_index *i)
lzma_ret	lzma_index_stream_flags (lzma_index *i, const lzma_stream_flags *stream_flags)
	Set the Stream Flags.
lzma_ret	lzma_index_stream_padding (lzma_index *i, lzma_vli stream_padding)
	Set the amount of Stream Padding.
lzma_ret	lzma_index_append (lzma_index *i, lzma_allocator *allocator, lzma_vli unpadded_size, lzma_vli uncompressed_size)
	Add a new Block to lzma_index.
static void	index_cat_helper (const index_cat_info *info, index_stream *this)
lzma_ret	lzma_index_cat (lzma_index *restrict dest, lzma_index *restrict src, lzma_allocator *allocator)
static index_stream *	index_dup_stream (const index_stream *src, lzma_allocator *allocator)
	Duplicate an index_stream.
lzma_index *	lzma_index_dup (const lzma_index *src, lzma_allocator *allocator)
	Duplicate lzma_index.
static void	iter_set_info (lzma_index_iter *iter)
void	lzma_index_iter_init (lzma_index_iter *iter, const lzma_index *i)
	Initialize an iterator.
void	lzma_index_iter_rewind (lzma_index_iter *iter)
	Rewind the iterator.
lzma_bool	lzma_index_iter_next (lzma_index_iter *iter, lzma_index_iter_mode mode)
	Get the next Block or Stream.
lzma_bool	lzma_index_iter_locate (lzma_index_iter *iter, lzma_vli target)
	Locate a Block.

---

Detailed Description

Handling of .xz Indexes and some other Stream information.

---

Define Documentation

#define INDEX_GROUP_SIZE   512

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.

Referenced by lzma_index_memusage().

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

How many Records can be allocated at once at maximum.

Referenced by index_dup_stream(), and lzma_index_prealloc().

---

Typedef Documentation

typedef struct index_tree_node_s index_tree_node

Base structure for index_stream and index_group structures.

---

Enumeration Type Documentation

anonymous enum

Indexing for lzma_index_iter.internal[].

anonymous enum

Values for lzma_index_iter.internal[ITER_METHOD].s.

---

Function Documentation

static void index_tree_node_end	(	index_tree_node *	node,
		lzma_allocator *	allocator,
		void(*)(void *node, lzma_allocator *allocator)	free_func
	)			[static]

Helper for index_tree_end().

Referenced by index_tree_end().

static void index_tree_end	(	index_tree *	tree,
		lzma_allocator *	allocator,
		void(*)(void *node, lzma_allocator *allocator)	free_func
	)			[static]

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.

References index_tree_node_end(), and index_tree::root.

Referenced by index_stream_end(), and lzma_index_end().

static void index_tree_append	(	index_tree *	tree,
		index_tree_node *	node
	)			[static]

Add a new node to the tree. node->uncompressed_base and node->compressed_base must have been set by the caller already.

References index_tree_node_s::compressed_base, index_tree::count, index_tree::leftmost, index_tree::rightmost, index_tree::root, and index_tree_node_s::uncompressed_base.

Referenced by index_cat_helper(), index_dup_stream(), lzma_index_append(), lzma_index_dup(), and lzma_index_init().

static void* index_tree_next

(

const index_tree_node *

node

)

[static]

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

Referenced by index_dup_stream(), lzma_index_dup(), and lzma_index_iter_next().

static void* index_tree_locate	(	const index_tree *	tree,
		lzma_vli	target
	)			[static]

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).

References index_tree::leftmost, index_tree::root, and index_tree_node_s::uncompressed_base.

Referenced by lzma_index_iter_locate().

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
	)			[static]

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

References index_stream::block_number_base, index_tree_node_s::compressed_base, index_stream::groups, index_stream::index_list_size, lzma_alloc(), index_stream::node, index_stream::number, index_stream::record_count, index_stream::stream_flags, index_stream::stream_padding, index_tree_node_s::uncompressed_base, and lzma_stream_flags::version.

Referenced by index_dup_stream(), and lzma_index_init().

static void index_stream_end	(	void *	node,
		lzma_allocator *	allocator
	)			[static]

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

References index_stream::groups, and index_tree_end().

Referenced by index_dup_stream(), lzma_index_end(), and lzma_index_init().

lzma_index* lzma_index_init

(

lzma_allocator *

allocator

)

Allocate and initialize a new lzma_index structure.

Returns:

On success, a pointer to an empty initialized lzma_index is returned. If allocation fails, NULL is returned.

References index_stream_end(), index_stream_init(), index_tree_append(), index_stream::node, and lzma_index_s::streams.

Referenced by lzma_stream_buffer_encode().

void lzma_index_end	(	lzma_index *	i,
		lzma_allocator *	allocator
	)

Deallocate lzma_index.

If i is NULL, this does nothing.

References index_stream_end(), and index_tree_end().

Referenced by list_file(), lzma_index_buffer_decode(), lzma_index_dup(), lzma_stream_buffer_encode(), and parse_indexes().

void lzma_index_prealloc	(	lzma_index *	i,
		lzma_vli	records
	)

Set for how many Records to allocate memory the next time lzma_index_append() needs to allocate space for a new Record. This is used only by the Index decoder.

References lzma_index_s::prealloc, and PREALLOC_MAX.

uint64_t lzma_index_memusage	(	lzma_vli	streams,
		lzma_vli	blocks
	)

Calculate memory usage of lzma_index.

On disk, the size of the Index field depends on both the number of Records stored and how big values the Records store (due to variable-length integer encoding). When the Index is kept in lzma_index structure, the memory usage depends only on the number of Records/Blocks stored in the Index(es), and in case of concatenated lzma_indexes, the number of Streams. The size in RAM is almost always significantly bigger than in the encoded form on disk.

This function calculates an approximate amount of memory needed hold the given number of Streams and Blocks in lzma_index structure. This value may vary between CPU architectures and also between liblzma versions if the internal implementation is modified.

References INDEX_GROUP_SIZE, and LZMA_VLI_MAX.

Referenced by lzma_index_buffer_decode(), and lzma_index_memused().

uint64_t lzma_index_memused

(

const lzma_index *

i

)

Calculate the memory usage of an existing lzma_index.

This is a shorthand for lzma_index_memusage(lzma_index_stream_count(i), lzma_index_block_count(i)).

References lzma_index_memusage().

Referenced by parse_indexes().

lzma_vli lzma_index_block_count

(

const lzma_index *

i

)

Get the number of Blocks.

This returns the total number of Blocks in lzma_index. To get number of Blocks in individual Streams, use lzma_index_iter.

lzma_vli lzma_index_stream_count

(

const lzma_index *

i

)

Get the number of Streams.

lzma_vli lzma_index_size

(

const lzma_index *

i

)

Get the size of the Index field as bytes.

This is needed to verify the Backward Size field in the Stream Footer.

Referenced by lzma_index_buffer_encode(), and lzma_stream_buffer_encode().

lzma_vli lzma_index_total_size

(

const lzma_index *

i

)

Get the total size of the Blocks.

This doesn't include the Stream Header, Stream Footer, Stream Padding, or Index fields.

Referenced by parse_indexes().

lzma_vli lzma_index_stream_size

(

const lzma_index *

i

)

Get the total size of the Stream.

If multiple lzma_indexes have been combined, this works as if the Blocks were in a single Stream. This is useful if you are going to combine Blocks from multiple Streams into a single new Stream.

References LZMA_STREAM_HEADER_SIZE.

lzma_vli lzma_index_file_size

(

const lzma_index *

i

)

Get the total size of the file.

When no lzma_indexes have been combined with lzma_index_cat() and there is no Stream Padding, this function is identical to lzma_index_stream_size(). If multiple lzma_indexes have been combined, this includes also the headers of each separate Stream and the possible Stream Padding fields.

References index_tree_node_s::compressed_base, index_stream::groups, index_stream::index_list_size, index_group::last, index_stream::node, index_stream::record_count, index_group::records, index_tree::rightmost, and index_stream::stream_padding.

Referenced by lzma_index_stream_padding().

lzma_vli lzma_index_uncompressed_size

(

const lzma_index *

i

)

Get the uncompressed size of the file.

uint32_t lzma_index_checks

(

const lzma_index *

i

)

Get the types of integrity Checks.

If lzma_index_stream_flags() is used to set the Stream Flags for every Stream, lzma_index_checks() can be used to get a bitmask to indicate which Check types have been used. It can be useful e.g. if showing the Check types to the user.

The bitmask is 1 << check_id, e.g. CRC32 is 1 << 1 and SHA-256 is 1 << 10.

References lzma_stream_flags::check, index_stream::stream_flags, and lzma_stream_flags::version.

uint32_t lzma_index_padding_size

(

const lzma_index *

i

)

Get the size of the Index Padding field. This is needed by Index encoder and decoder, but applications should have no use for this.

References lzma_index_s::index_list_size, LZMA_VLI_C, and lzma_index_s::record_count.

lzma_ret lzma_index_stream_flags	(	lzma_index *	i,
		const lzma_stream_flags *	stream_flags
	)

Set the Stream Flags.

Set the Stream Flags of the last (and typically the only) Stream in lzma_index. This can be useful when reading information from the lzma_index, because to decode Blocks, knowing the integrity check type is needed.

The given Stream Flags are copied into internal preallocated structure in the lzma_index, thus the caller doesn't need to keep the *stream_flags available after calling this function.

Returns:

- LZMA_OK

• LZMA_OPTIONS_ERROR: Unsupported stream_flags->version.
• LZMA_PROG_ERROR

References lzma_stream_flags_compare(), return_if_error, and index_stream::stream_flags.

Referenced by parse_indexes().

lzma_ret lzma_index_stream_padding	(	lzma_index *	i,
		lzma_vli	stream_padding
	)

Set the amount of Stream Padding.

Set the amount of Stream Padding of the last (and typically the only) Stream in the lzma_index. This is needed when planning to do random-access reading within multiple concatenated Streams.

By default, the amount of Stream Padding is assumed to be zero bytes.

Returns:

- LZMA_OK

• LZMA_DATA_ERROR: The file size would grow too big.
• LZMA_PROG_ERROR

References lzma_index_file_size(), LZMA_VLI_MAX, and index_stream::stream_padding.

Referenced by parse_indexes().

lzma_ret lzma_index_append	(	lzma_index *	i,
		lzma_allocator *	allocator,
		lzma_vli	unpadded_size,
		lzma_vli	uncompressed_size
	)

Add a new Block to lzma_index.

Parameters:

	i	Pointer to a lzma_index structure
	allocator	Pointer to lzma_allocator, or NULL to use malloc()
	unpadded_size	Unpadded Size of a Block. This can be calculated with lzma_block_unpadded_size() after encoding or decoding the Block.
	uncompressed_size	Uncompressed Size of a Block. This can be taken directly from lzma_block structure after encoding or decoding the Block.

Appending a new Block does not invalidate iterators. For example, if an iterator was pointing to the end of the lzma_index, after lzma_index_append() it is possible to read the next Block with an existing iterator.

Returns:

- LZMA_OK

• LZMA_MEM_ERROR
• LZMA_DATA_ERROR: Compressed or uncompressed size of the Stream or size of the Index field would grow too big.
• LZMA_PROG_ERROR

References index_group::allocated, index_tree_node_s::compressed_base, index_stream::groups, index_stream::index_list_size, index_tree_append(), index_group::last, lzma_alloc(), LZMA_VLI_MAX, lzma_vli_size(), LZMA_VLI_UNKNOWN, index_group::node, index_stream::node, index_group::number_base, index_stream::record_count, index_group::records, index_tree::rightmost, index_stream::stream_padding, and index_tree_node_s::uncompressed_base.

Referenced by lzma_stream_buffer_encode().

static void index_cat_helper	(	const index_cat_info *	info,
		index_stream *	this
	)			[static]

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.

References index_cat_info::block_number_add, index_tree_node_s::compressed_base, index_cat_info::file_size, index_tree_append(), index_cat_info::stream_number_add, index_cat_info::streams, index_tree_node_s::uncompressed_base, and index_cat_info::uncompressed_size.

static index_stream* index_dup_stream	(	const index_stream *	src,
		lzma_allocator *	allocator
	)			[static]

Duplicate an index_stream.

References index_group::allocated, index_stream::block_number_base, index_tree_node_s::compressed_base, index_stream::groups, index_stream::index_list_size, index_stream_end(), index_stream_init(), index_tree_append(), index_tree_next(), index_group::last, index_tree::leftmost, lzma_alloc(), index_group::node, index_stream::node, index_stream::number, index_group::number_base, PREALLOC_MAX, index_stream::record_count, index_group::records, index_stream::stream_flags, index_stream::stream_padding, and index_tree_node_s::uncompressed_base.

Referenced by lzma_index_dup().

lzma_index* lzma_index_dup	(	const lzma_index *	i,
		lzma_allocator *	allocator
	)

Duplicate lzma_index.

Returns:

A copy of the lzma_index, or NULL if memory allocation failed.

References index_dup_stream(), lzma_index_s::index_list_size, index_tree_append(), index_tree_next(), lzma_index_end(), index_stream::node, lzma_index_s::record_count, lzma_index_s::streams, lzma_index_s::total_size, and lzma_index_s::uncompressed_size.

void lzma_index_iter_init	(	lzma_index_iter *	iter,
		const lzma_index *	i
	)

Initialize an iterator.

Parameters:

	iter	Pointer to a lzma_index_iter structure
	i	lzma_index to which the iterator will be associated

This function associates the iterator with the given lzma_index, and calls lzma_index_iter_rewind() on the iterator.

This function doesn't allocate any memory, thus there is no lzma_index_iter_end(). The iterator is valid as long as the associated lzma_index is valid, that is, until lzma_index_end() or using it as source in lzma_index_cat(). Specifically, lzma_index doesn't become invalid if new Blocks are added to it with lzma_index_append() or if it is used as the destination in lzma_index_cat().

It is safe to make copies of an initialized lzma_index_iter, for example, to easily restart reading at some particular position.

References lzma_index_iter_rewind().

void lzma_index_iter_rewind

(

lzma_index_iter *

iter

)

Rewind the iterator.

Rewind the iterator so that next call to lzma_index_iter_next() will return the first Block or Stream.

Referenced by lzma_index_iter_init().

lzma_bool lzma_index_iter_next	(	lzma_index_iter *	iter,
		lzma_index_iter_mode	mode
	)

Get the next Block or Stream.

Parameters:

	iter	Iterator initialized with lzma_index_iter_init()
	mode	Specify what kind of information the caller wants to get. See lzma_index_iter_mode for details.

Returns:

If next Block or Stream matching the mode was found, *iter is updated and this function returns false. If no Block or Stream matching the mode is found, *iter is not modified and this function returns true. If mode is set to an unknown value, *iter is not modified and this function returns true.

References index_stream::groups, index_tree_next(), index_tree::leftmost, LZMA_INDEX_ITER_BLOCK, LZMA_INDEX_ITER_NONEMPTY_BLOCK, LZMA_INDEX_ITER_STREAM, index_group::node, index_stream::node, index_group::records, lzma_index_s::streams, and index_tree_node_s::uncompressed_base.

lzma_bool lzma_index_iter_locate	(	lzma_index_iter *	iter,
		lzma_vli	target
	)

Locate a Block.

If it is possible to seek in the .xz file, it is possible to parse the Index field(s) and use lzma_index_iter_locate() to do random-access reading with granularity of Block size.

Parameters:

	iter	Iterator that was earlier initialized with lzma_index_iter_init().
	target	Uncompressed target offset which the caller would like to locate from the Stream

If the target is smaller than the uncompressed size of the Stream (can be checked with lzma_index_uncompressed_size()):

• Information about the Stream and Block containing the requested uncompressed offset is stored into *iter.
• Internal state of the iterator is adjusted so that lzma_index_iter_next() can be used to read subsequent Blocks or Streams.
• This function returns false.

If target is greater than the uncompressed size of the Stream, *iter is not modified, and this function returns true.

References index_stream::groups, index_tree_locate(), index_group::last, index_stream::node, index_group::records, lzma_index_s::streams, index_tree_node_s::uncompressed_base, and lzma_index_s::uncompressed_size.