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

## Macros

#define | INDEX_GROUP_SIZE 512
| How many Records to allocate at once. More...
#define | PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))
| How many Records can be allocated at once at maximum. More...

## Typedefs

typedef struct index_tree_node_s | index_tree_node
| Base structure for index_stream and index_group structures. More...

## 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, const lzma_allocator *allocator, void(*free_func)(void *node, const lzma_allocator *allocator))
| Helper for index_tree_end() More...
static void | index_tree_end (index_tree *tree, const lzma_allocator *allocator, void(*free_func)(void *node, const 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. More...
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, uint32_t stream_number, lzma_vli block_number_base, const lzma_allocator *allocator)
| Allocate and initialize a new Stream using the given base offsets. More...
static void | index_stream_end (void *node, const lzma_allocator *allocator)
| Free the memory allocated for a Stream and its Record groups. More...
static lzma_index * | index_init_plain (const lzma_allocator *allocator)
lzma_index * | lzma_index_init (const lzma_allocator *allocator)
| Allocate and initialize a new lzma_index structure. More...
void | lzma_index_end (lzma_index *i, const lzma_allocator *allocator)
| Deallocate lzma_index. More...
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. More...
uint64_t | lzma_index_memused (const lzma_index *i)
| Calculate the memory usage of an existing lzma_index. More...
lzma_vli | lzma_index_block_count (const lzma_index *i)
| Get the number of Blocks. More...
lzma_vli | lzma_index_stream_count (const lzma_index *i)
| Get the number of Streams. More...
lzma_vli | lzma_index_size (const lzma_index *i)
| Get the size of the Index field as bytes. More...
lzma_vli | lzma_index_total_size (const lzma_index *i)
| Get the total size of the Blocks. More...
lzma_vli | lzma_index_stream_size (const lzma_index *i)
| Get the total size of the Stream. More...
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. More...
lzma_vli | lzma_index_uncompressed_size (const lzma_index *i)
| Get the uncompressed size of the file. More...
uint32_t | lzma_index_checks (const lzma_index *i)
| Get the types of integrity Checks. More...
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. More...
lzma_ret | lzma_index_stream_padding (lzma_index *i, lzma_vli stream_padding)
| Set the amount of Stream Padding. More...
lzma_ret | lzma_index_append (lzma_index *i, const lzma_allocator *allocator, lzma_vli unpadded_size, lzma_vli uncompressed_size)
| Add a new Block to lzma_index. More...
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, const lzma_allocator *allocator)
static index_stream * | index_dup_stream (const index_stream *src, const lzma_allocator *allocator)
| Duplicate an index_stream. More...
lzma_index * | lzma_index_dup (const lzma_index *src, const lzma_allocator *allocator)
| Duplicate lzma_index. More...
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. More...
void | lzma_index_iter_rewind (lzma_index_iter *iter)
| Rewind the iterator. More...
lzma_bool | lzma_index_iter_next (lzma_index_iter *iter, lzma_index_iter_mode mode)
| Get the next Block or Stream. More...
lzma_bool | lzma_index_iter_locate (lzma_index_iter *iter, lzma_vli target)
| Locate a Block. More...

## Detailed Description

Handling of .xz Indexes and some other Stream information.

## Macro Definition Documentation

## INDEX_GROUP_SIZE

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

## PREALLOC_MAX

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

How many Records can be allocated at once at maximum.

## Typedef Documentation

## index_tree_node

typedef struct index_tree_node_s index_tree_node

Base structure for index_stream and index_group structures.

## Enumeration Type Documentation

## anonymous enum

anonymous enum

Indexing for lzma_index_iter.internal[].

## anonymous enum

anonymous enum

Values for lzma_index_iter.internal[ITER_METHOD].s.

## Function Documentation

## index_tree_node_end()

static void index_tree_node_end | ( | index_tree_node * | node,
|  | const lzma_allocator * | allocator,
|  | void(*)(void *node, const lzma_allocator *allocator) | free_func
| ) |  |

static

Helper for index_tree_end()

## index_tree_end()

static void index_tree_end | ( | index_tree * | tree,
|  | const lzma_allocator * | allocator,
|  | void(*)(void *node, const lzma_allocator *allocator) | free_func
| ) |  |

static

Free the memory allocated for a tree. Each node is freed using the given free_func which is either &lzma_free or &index_stream_end. The latter is used to free the Record groups from each index_stream before freeing the index_stream itself.

## index_tree_append()

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::count, index_tree::leftmost, index_tree::rightmost, and index_tree::root.

Referenced by index_cat_helper().

## index_tree_next()

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.

## index_tree_locate()

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::root.

## index_stream_init()

static index_stream* index_stream_init | ( | lzma_vli | compressed_base,
|  | lzma_vli | uncompressed_base,
|  | uint32_t | stream_number,
|  | lzma_vli | block_number_base,
|  | const lzma_allocator * | allocator
| ) |  |

static

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

## index_stream_end()

static void index_stream_end | ( | void * | node,
|  | const lzma_allocator * | allocator
| ) |  |

static

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

## lzma_index_init()

lzma_index* lzma_index_init | ( | const 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.

## lzma_index_end()

void lzma_index_end | ( | lzma_index * | i,
|  | const lzma_allocator * | allocator
| ) |  |

Deallocate lzma_index.

If i is NULL, this does nothing.

## lzma_index_prealloc()

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 INDEX_GROUP_SIZE, lzma_index_s::prealloc, and PREALLOC_MAX.

## lzma_index_memusage()

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.

Referenced by lzma_index_memused().

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

## lzma_index_block_count()

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_index_stream_count()

lzma_vli lzma_index_stream_count | ( | const lzma_index * | i | ) |

Get the number of Streams.

## lzma_index_size()

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.

References index_size().

Referenced by lzma_index_buffer_encode().

## lzma_index_total_size()

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.

## lzma_index_stream_size()

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 index_size(), and LZMA_STREAM_HEADER_SIZE.

## lzma_index_file_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.

## lzma_index_uncompressed_size()

lzma_vli lzma_index_uncompressed_size | ( | const lzma_index * | i | ) |

Get the uncompressed size of the file.

## lzma_index_checks()

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.

## lzma_index_padding_size()

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, index_size_unpadded(), LZMA_VLI_C, and lzma_index_s::record_count.

## lzma_index_stream_flags()

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_OK, LZMA_PROG_ERROR, lzma_stream_flags_compare(), return_if_error, and index_stream::stream_flags.

## lzma_index_stream_padding()

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

## lzma_index_append()

lzma_ret lzma_index_append | ( | lzma_index * | i,
|  | const 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

## index_cat_helper()

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.

## index_dup_stream()

static index_stream* index_dup_stream | ( | const index_stream * | src,
|  | const lzma_allocator * | allocator
| ) |  |

static

Duplicate an index_stream.

## lzma_index_dup()

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

Duplicate lzma_index.

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

## lzma_index_iter_init()

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.

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

## lzma_index_iter_next()

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

## lzma_index_iter_locate()

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.