Xapian: Internal Source Documentation: backends/chert/chert_table.h File Reference

xapian-core 1.4.26

Btree implementation. More...

#include <xapian/error.h>
#include "chert_types.h"
#include "chert_btreebase.h"
#include "chert_cursor.h"
#include "noreturn.h"
#include "omassert.h"
#include "str.h"
#include "stringutils.h"
#include "wordaccess.h"
#include <algorithm>
#include <string>
#include <zlib.h>

Include dependency graph for chert_table.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Key

class	Item_base< T >

class	Item

class	Item_wr

class	ChertTable
	Class managing a Btree table in a Chert database. More...

Macros
#define	CHERT_BTREE_MAX_KEY_LEN 252
	The largest possible value of a key_len. More...

Functions
int	getint1 (const unsigned char *p, int c)

void	setint1 (unsigned char *p, int c, int x)

int	getint2 (const unsigned char *p, int c)

void	setint2 (unsigned char *p, int c, int x)

int	getint4 (const unsigned char *p, int c)

void	setint4 (unsigned char *p, int c, int x)

int	getK (const unsigned char *p, int c)

void	setD (unsigned char *p, int c, int x)

unsigned	REVISION (const uint8_t *b)

int	GET_LEVEL (const uint8_t *b)

int	MAX_FREE (const uint8_t *b)

int	TOTAL_FREE (const uint8_t *b)

int	DIR_END (const uint8_t *b)

void	SET_REVISION (uint8_t *b, uint4 rev)

void	SET_LEVEL (uint8_t *b, int x)

void	SET_MAX_FREE (uint8_t *b, int x)

void	SET_TOTAL_FREE (uint8_t *b, int x)

void	SET_DIR_END (uint8_t *b, int x)

Variables
const int	DONT_COMPRESS = -1

const size_t	BLOCK_CAPACITY = 4
	Even for items of at maximum size, it must be possible to get this number of items in a block. More...

const int	BYTES_PER_BLOCK_NUMBER = 4

const int	K1 = 1

const int	I2 = 2

const int	D2 = 2

const int	C2 = 2

const int	DIR_START = 11

const size_t	CHERT_MAX_ITEM_SIZE = 0x7fff

const int	BTREE_CURSOR_LEVELS = 10

Detailed Description

Btree implementation.

Definition in file chert_table.h.

Macro Definition Documentation

◆ CHERT_BTREE_MAX_KEY_LEN

#define CHERT_BTREE_MAX_KEY_LEN 252

The largest possible value of a key_len.

This gives the upper limit of the size of a key that may be stored in the B-tree (252 bytes with the present implementation).

Definition at line 101 of file chert_table.h.

Referenced by ChertTable::del(), ChertCursor::find_entry(), ChertCursor::find_entry_ge(), Item_wr::form_key(), ChertTable::get_exact_entry(), ChertTable::key_exists(), and ChertTable::readahead_key().

Function Documentation

◆ DIR_END()

int DIR_END ( const uint8_t * b )

inline

◆ GET_LEVEL()

int GET_LEVEL ( const uint8_t * b )

inline

Definition at line 151 of file chert_table.h.

References getint1().

Referenced by ChertTableCheck::block_check(), ChertTable::block_to_cursor(), ChertTableCheck::check(), ChertTable::next_for_sequential(), GlassTable::next_for_sequential(), ChertTable::prev_for_sequential(), GlassTable::prev_for_sequential(), GlassFreeList::read_block(), ChertTableCheck::report_block(), and ChertTableCheck::report_block_full().

◆ getint1()

int getint1	(	const unsigned char *	p,
		int	c
	)

inline

Definition at line 47 of file chert_table.h.

References AssertRel.

Referenced by GET_LEVEL(), and getK().

◆ getint2()

int getint2	(	const unsigned char *	p,
		int	c
	)

inline

Definition at line 63 of file chert_table.h.

References AssertRel, and unaligned_read2().

Referenced by Item_base< uint8_t *>::component_of(), Item_base< uint8_t *>::components_of(), DIR_END(), MAX_FREE(), Item_base< uint8_t *>::size(), and TOTAL_FREE().

◆ getint4()

int getint4	(	const unsigned char *	p,
		int	c
	)

inline

Definition at line 79 of file chert_table.h.

References AssertRel, and unaligned_read4().

Referenced by Item_base< uint8_t *>::block_given_by(), and ChertTable::enter_key().

◆ getK()

int getK	(	const unsigned char *	p,
		int	c
	)

inline

Definition at line 127 of file chert_table.h.

References getint1().

Referenced by Item_base< uint8_t *>::append_chunk(), Item_base< uint8_t *>::component_of(), Item_base< uint8_t *>::components_of(), Key::length(), Item_wr::set_component_of(), and Item_wr::set_components_of().

◆ MAX_FREE()

int MAX_FREE ( const uint8_t * b )

inline

Definition at line 152 of file chert_table.h.

References getint2().

Referenced by ChertTable::add_item(), ChertTable::add_item_to_block(), ChertTable::add_kt(), ChertTableCheck::block_check(), and ChertTable::delete_item().

◆ REVISION()

unsigned REVISION ( const uint8_t * b )

inline

Definition at line 150 of file chert_table.h.

References aligned_read4().

Referenced by ChertTable::alter(), ChertTableCheck::block_check(), ChertTable::block_to_cursor(), ChertTableCheck::check(), ChertTable::next_for_sequential(), GlassTable::next_for_sequential(), ChertTable::prev_for_sequential(), GlassTable::prev_for_sequential(), ChertTable::read_root(), ChertTableCheck::report_block(), ChertTableCheck::report_block_full(), and ChertTable::write_block().

◆ SET_DIR_END()

void SET_DIR_END	(	uint8_t *	b,
		int	x
	)

inline

Definition at line 161 of file chert_table.h.

References setint2().

Referenced by ChertTable::add_item(), ChertTable::add_item_to_block(), ChertTable::delete_item(), ChertTable::read_root(), and ChertTable::split_root().

◆ SET_LEVEL()

void SET_LEVEL	(	uint8_t *	b,
		int	x
	)

inline

Definition at line 158 of file chert_table.h.

References setint1().

Referenced by ChertTable::read_root(), ChertTable::split_root(), and GlassFreeList::write_block().

◆ SET_MAX_FREE()

void SET_MAX_FREE	(	uint8_t *	b,
		int	x
	)

inline

Definition at line 159 of file chert_table.h.

References setint2().

Referenced by ChertTable::add_item_to_block(), ChertTable::add_kt(), ChertTable::compact(), ChertTable::delete_item(), and ChertTable::read_root().

◆ SET_REVISION()

void SET_REVISION	(	uint8_t *	b,
		uint4	rev
	)

inline

Definition at line 157 of file chert_table.h.

References aligned_write4().

Referenced by ChertTable::alter(), ChertTable::read_root(), ChertTable::split_root(), and GlassFreeList::write_block().

◆ SET_TOTAL_FREE()

void SET_TOTAL_FREE	(	uint8_t *	b,
		int	x
	)

inline

Definition at line 160 of file chert_table.h.

References setint2().

Referenced by ChertTable::add_item_to_block(), ChertTable::add_kt(), ChertTable::compact(), ChertTable::delete_item(), ChertTable::enter_key(), and ChertTable::read_root().

◆ setD()

void setD	(	unsigned char *	p,
		int	c,
		int	x
	)

inline

Definition at line 128 of file chert_table.h.

References setint2().

Referenced by ChertTable::add_item_to_block(), ChertTable::add_kt(), ChertTable::compact(), and ChertTable::read_root().

◆ setint1()

void setint1	(	unsigned char *	p,
		int	c,
		int	x
	)

inline

Definition at line 55 of file chert_table.h.

References AssertRel.

Referenced by Item_wr::set_key_and_block(), Item_wr::set_key_len(), and SET_LEVEL().

◆ setint2()

void setint2	(	unsigned char *	p,
		int	c,
		int	x
	)

inline

Definition at line 71 of file chert_table.h.

References AssertRel, and unaligned_write2().

Referenced by Item_wr::set_component_of(), Item_wr::set_components_of(), SET_DIR_END(), Item_wr::set_key_and_block(), SET_MAX_FREE(), Item_wr::set_size(), SET_TOTAL_FREE(), and setD().

◆ setint4()

void setint4	(	unsigned char *	p,
		int	c,
		int	x
	)

inline

Definition at line 87 of file chert_table.h.

References AssertRel, and unaligned_write4().

Referenced by Item_wr::form_null_key(), Item_wr::set_block_given_by(), and Item_wr::set_key_and_block().

◆ TOTAL_FREE()

int TOTAL_FREE ( const uint8_t * b )

inline

Definition at line 153 of file chert_table.h.

References getint2().

Referenced by ChertTable::add(), ChertTable::add_item(), ChertTable::add_item_to_block(), ChertTable::add_kt(), ChertTableCheck::block_check(), ChertTableCheck::block_usage(), ChertTableCheck::check(), ChertTable::delete_item(), ChertTable::enter_key(), and ChertTable::mid_point().

Variable Documentation

◆ BLOCK_CAPACITY

const size_t BLOCK_CAPACITY = 4

Even for items of at maximum size, it must be possible to get this number of items in a block.

Definition at line 105 of file chert_table.h.

Referenced by ChertTable::basic_open(), and ChertTable::set_max_item_size().

◆ BTREE_CURSOR_LEVELS

const int BTREE_CURSOR_LEVELS = 10

Definition at line 325 of file chert_table.h.

Referenced by ChertTable::basic_open(), ChertTable::cancel(), ChertTable::commit(), and ChertTable::split_root().

◆ BYTES_PER_BLOCK_NUMBER

const int BYTES_PER_BLOCK_NUMBER = 4

Definition at line 108 of file chert_table.h.

Referenced by Item_base< uint8_t *>::block_given_by(), Item_wr::form_null_key(), Item_wr::set_block_given_by(), and Item_wr::set_key_and_block().

◆ C2

const int C2 = 2

Definition at line 123 of file chert_table.h.

Referenced by ChertTable::add(), Item_base< uint8_t *>::append_chunk(), Item_base< uint8_t *>::component_of(), ChertTable::enter_key(), Item_wr::fake_root_item(), Item_wr::form_key(), Key::length(), Key::operator<(), Key::operator==(), ChertTable::read_root(), ChertTable::read_tag(), Item_wr::set_component_of(), and Item_wr::set_key_and_block().

◆ CHERT_MAX_ITEM_SIZE

const size_t CHERT_MAX_ITEM_SIZE = 0x7fff

Definition at line 165 of file chert_table.h.

Referenced by ChertTable::set_max_item_size(), Item_wr::set_size(), and Item_base< uint8_t *>::size().

◆ D2

◆ DIR_START

const int DIR_START = 11

Definition at line 155 of file chert_table.h.

Referenced by ChertTable::add_item(), ChertTable::add_item_to_block(), ChertTable::add_kt(), ChertTableCheck::block_check(), ChertTable::cancel(), GlassTable::cancel(), ChertTableCheck::check(), ChertTable::commit(), GlassTable::commit(), ChertTable::compact(), ChertTable::delete_item(), ChertTable::do_open_to_write(), ChertTable::find(), ChertTable::find_in_block(), ChertTable::mid_point(), ChertTable::next_default(), GlassTable::next_default(), ChertTable::next_for_sequential(), GlassTable::next_for_sequential(), ChertTable::prev_default(), GlassTable::prev_default(), ChertTable::prev_for_sequential(), GlassTable::prev_for_sequential(), ChertTable::read_block(), ChertTable::read_root(), ChertTableCheck::report_block(), ChertTableCheck::report_block_full(), ChertTable::set_max_item_size(), and ChertTable::split_root().

◆ DONT_COMPRESS

const int DONT_COMPRESS = -1

Definition at line 94 of file chert_table.h.

Referenced by ChertTable::add(), and ChertDatabase::compact().

◆ I2

const int I2 = 2

Definition at line 121 of file chert_table.h.

Referenced by ChertTable::add(), Item_base< uint8_t *>::append_chunk(), Item_base< uint8_t *>::component_of(), Item_base< uint8_t *>::components_of(), ChertTable::enter_key(), Item_wr::fake_root_item(), Item_wr::form_key(), Item_wr::form_null_key(), Item_base< uint8_t *>::key(), ChertTable::read_root(), ChertTable::read_tag(), Item_wr::set_component_of(), Item_wr::set_components_of(), Item_wr::set_key_and_block(), and Item_wr::set_key_len().

◆ K1

const int K1 = 1

Definition at line 120 of file chert_table.h.

Referenced by ChertTable::add(), ChertTable::enter_key(), Item_wr::fake_root_item(), Item_wr::form_key(), Item_wr::form_null_key(), Key::length(), Key::operator<(), Key::operator==(), Key::operator[](), Key::read(), ChertTable::read_root(), ChertTable::read_tag(), and Item_wr::set_key_and_block().