#include <flint_table.h>
Inheritance diagram for FlintTable:
Public Member Functions | |
FlintTable (string path_, bool readonly_, int compress_strategy_=DONT_COMPRESS, bool lazy=false) | |
Create a new Btree object. | |
~FlintTable () | |
Close the Btree. | |
void | close (bool permanent=false) |
Close the Btree. | |
bool | exists () const |
Determine whether the btree exists on disk. | |
void | open () |
Open the btree at the latest revision. | |
bool | open (flint_revision_number_t revision_) |
Open the btree at a given revision. | |
void | commit (flint_revision_number_t revision) |
Commit any outstanding changes to the table. | |
void | cancel () |
Cancel any outstanding changes. | |
bool | get_exact_entry (const string &key, string &tag) const |
Read an entry from the table, if and only if it is exactly that being asked for. | |
bool | key_exists (const string &key) const |
Check if a key exists in the Btree. | |
bool | find_tag (const string &key, string *tag) const |
Find a key in the Btree and read its tag. | |
bool | read_tag (Cursor_ *C_, string *tag, bool keep_compressed) const |
Read the tag value for the key pointed to by cursor C_. | |
bool | add (const string &key, string tag, bool already_compressed=false) |
Add a key/tag pair to the table, replacing any existing pair with the same key. | |
bool | del (const string &key) |
Delete an entry from the table. | |
void | erase () |
Erase this table from disk. | |
void | set_block_size (unsigned int block_size_) |
Set the block size. | |
unsigned int | get_block_size () const |
Get the block size. | |
void | create_and_open (unsigned int blocksize) |
Create a new empty btree structure on disk and open it at the initial revision. | |
void | set_full_compaction (bool parity) |
flint_revision_number_t | get_latest_revision_number () const |
Get the latest revision number stored in this table. | |
flint_revision_number_t | get_open_revision_number () const |
Get the revision number at which this table is currently open. | |
flint_tablesize_t | get_entry_count () const |
Return a count of the number of entries in the table. | |
FlintCursor * | cursor_get () const |
Get a cursor for reading from the table. | |
bool | is_modified () const |
Determine whether the object contains uncommitted modifications. | |
void | set_max_item_size (size_t block_capacity) |
Set the maximum item size given the block capacity. | |
Protected Member Functions | |
bool | do_open_to_read (bool revision_supplied, flint_revision_number_t revision_) |
Perform the opening operation to read. | |
bool | do_open_to_write (bool revision_supplied, flint_revision_number_t revision_, bool create_db=false) |
Perform the opening operation to write. | |
bool | basic_open (bool revision_supplied, flint_revision_number_t revision) |
bool | find (Cursor_ *) const |
find(C_) searches for the key of B->kt in the B-tree. | |
int | delete_kt () |
void | read_block (uint4 n, byte *p) const |
read_block(n, p) reads block n of the DB file to address p. | |
void | write_block (uint4 n, const byte *p) const |
write_block(n, p) writes block n in the DB file from address p. | |
XAPIAN_NORETURN (void set_overwritten() const) | |
void | block_to_cursor (Cursor_ *C_, int j, uint4 n) const |
void | alter () |
Btree::alter(); is called when the B-tree is to be altered. | |
void | compact (byte *p) |
compact(p) compact the block at p by shuffling all the items up to the end. | |
void | enter_key (int j, Key_ prevkey, Key_ newkey) |
enter_key(j, prevkey, newkey) is called after a block split. | |
int | mid_point (byte *p) |
mid_point(p) finds the directory entry in c that determines the approximate mid point of the data in the block at p. | |
void | add_item_to_block (byte *p, Item_wr_ kt, int c) |
add_item_to_block(p, kt_, c) adds item kt_ to the block at p. | |
void | add_item (Item_wr_ kt, int j) |
FlintTable::add_item(kt_, j) adds item kt_ to the block at cursor level C[j]. | |
void | delete_item (int j, bool repeatedly) |
FlintTable::delete_item(j, repeatedly) is (almost) the converse of add_item. | |
int | add_kt (bool found) |
add_kt(found) adds the item (key-tag pair) at B->kt into the B-tree, using cursor C. | |
void | read_root () |
void | split_root (uint4 split_n) |
Btree needs to gain a new level to insert more items: so split root block and construct a new one. | |
void | form_key (const string &key) const |
char | other_base_letter () const |
bool | prev (Cursor_ *C_, int j) const |
bool | next (Cursor_ *C_, int j) const |
bool | prev_default (Cursor_ *C_, int j) const |
bool | next_default (Cursor_ *C_, int j) const |
bool | prev_for_sequential (Cursor_ *C_, int dummy) const |
bool | next_for_sequential (Cursor_ *C_, int dummy) const |
Static Protected Member Functions | |
static int | find_in_block (const byte *p, Key_ key, bool leaf, int c) |
find_in_block(p, key, leaf, c) searches for the key in the block at p. | |
static uint4 | block_given_by (const byte *p, int c) |
block_given_by(p, c) finds the item at block address p, directory offset c, and returns its tag value as an integer. | |
Protected Attributes | |
flint_revision_number_t | revision_number |
revision number of the opened B-tree. | |
uint4 | item_count |
keeps a count of the number of items in the B-tree. | |
unsigned int | block_size |
block size of the B tree in bytes | |
flint_revision_number_t | latest_revision_number |
Revision number of the other base, or zero if there is only one base file. | |
bool | both_bases |
set to true if baseA and baseB both exist as valid bases. | |
char | base_letter |
the value 'A' or 'B' of the current base | |
bool | faked_root_block |
true if the root block is faked (not written to disk). | |
bool | sequential |
true iff the data has been written in a single write in sequential order. | |
int | handle |
corresponding file handle | |
int | level |
number of levels, counting from 0 | |
uint4 | root |
the root block of the B-tree | |
Item_wr_ | kt |
buffer of size block_size for making up key-tag items | |
byte * | buffer |
buffer of size block_size for reforming blocks | |
FlintTable_base | base |
For writing back as file baseA or baseB. | |
string | name |
The path name of the B tree. | |
int | seq_count |
count of the number of successive instances of purely sequential addition, starting at SEQ_START_POINT (neg) and going up to zero. | |
uint4 | changed_n |
the last block to be changed by an addition | |
int | changed_c |
directory offset corresponding to last block to be changed by an addition | |
size_t | max_item_size |
maximum size of an item (key-tag pair) | |
bool | Btree_modified |
Set to true the first time the B-tree is modified. | |
bool | full_compaction |
set to true when full compaction is to be achieved | |
bool | writable |
Set to true when the database is opened to write. | |
Cursor_ | C [BTREE_CURSOR_LEVELS] |
byte * | split_p |
Buffer used when splitting a block. | |
int | compress_strategy |
DONT_COMPRESS or Z_DEFAULT_STRATEGY, Z_FILTERED, Z_HUFFMAN_ONLY, Z_RLE. | |
bool | lazy |
If true, don't create the table until it's needed. | |
Private Member Functions | |
FlintTable (const FlintTable &) | |
Copying not allowed. | |
FlintTable & | operator= (const FlintTable &) |
Assignment not allowed. | |
Friends | |
class | FlintCursor |
A table is a store holding a set of key/tag pairs.
A key is used to access a block of data in a flint table.
Keys are of limited length.
Keys may not be empty (each Btree has a special empty key for internal use).
A tag is a piece of data associated with a given key. The contents of the tag are opaque to the Btree.
Tags may be of arbitrary length (the Btree imposes a very large limit). Note though that they will be loaded into memory in their entirety, so should not be permitted to grow without bound in normal usage.
Tags which are null strings _are_ valid, and are different from a tag simply not being in the table.
Definition at line 259 of file flint_table.h.
FlintTable::FlintTable | ( | const FlintTable & | ) | [private] |
Copying not allowed.
FlintTable::FlintTable | ( | string | path_, | |
bool | readonly_, | |||
int | compress_strategy_ = DONT_COMPRESS , |
|||
bool | lazy = false | |||
) |
Create a new Btree object.
This does not create the table on disk - the create_and_open() method must be called to create the table on disk.
This also does not open the table - either the create_and_open() or open() methods must be called before use is made of the table.
path_ | Path at which the table is stored. | |
readonly_ | whether to open the table for read only access. | |
compress_strategy_ | DONT_COMPRESS, Z_DEFAULT_STRATEGY, Z_FILTERED, Z_HUFFMAN_ONLY, or Z_RLE. | |
lazy | If true, don't create the table until it's needed. |
Definition at line 1589 of file flint_table.cc.
References DEBUGCALL.
FlintTable::~FlintTable | ( | ) |
FlintTable& FlintTable::operator= | ( | const FlintTable & | ) | [private] |
Assignment not allowed.
void FlintTable::close | ( | bool | permanent = false |
) |
Close the Btree.
This closes and frees any of the btree structures which have been created and opened.
permanent | If true, the Btree will not reopen on demand. |
Definition at line 1704 of file flint_table.cc.
References buffer, C, DEBUGCALL, Item_base_< T >::get_address(), handle, kt, level, Cursor_::p, and split_p.
Referenced by basic_open(), commit(), create_and_open(), do_open_to_read(), do_open_to_write(), erase(), open(), and ~FlintTable().
bool FlintTable::exists | ( | ) | const |
Determine whether the btree exists on disk.
Definition at line 1623 of file flint_table.cc.
References DEBUGCALL, and file_exists().
Referenced by FlintDatabase::database_exists().
void FlintTable::open | ( | ) |
Open the btree at the latest revision.
Xapian::DatabaseCorruptError | will be thrown if the table is in a corrupt state. | |
Xapian::DatabaseOpeningError | will be thrown if the table cannot be opened (but is not corrupt - eg, permission problems, not present, etc). |
Definition at line 1923 of file flint_table.cc.
References close(), DEBUGCALL, DEBUGLINE, do_open_to_read(), do_open_to_write(), and writable.
Referenced by check_table(), do_open_to_read(), do_open_to_write(), main(), merge_docid_keyed(), FlintDatabase::open_tables(), and FlintDatabase::open_tables_consistent().
bool FlintTable::open | ( | flint_revision_number_t | revision_ | ) |
Open the btree at a given revision.
Like Btree::open, but try to open at the given revision number and fail if that isn't possible.
revision_ | - revision number to open. |
Xapian::DatabaseCorruptError | will be thrown if the table is in a corrupt state. | |
Xapian::DatabaseOpeningError | will be thrown if the table cannot be opened (but is not corrupt - eg, permission problems, not present, etc). |
Definition at line 1940 of file flint_table.cc.
References AssertEq, close(), DEBUGCALL, DEBUGLINE, do_open_to_read(), do_open_to_write(), RETURN, revision_number, and writable.
void FlintTable::commit | ( | flint_revision_number_t | revision | ) |
Commit any outstanding changes to the table.
Commit changes made by calling add() and del() to the Btree.
If an error occurs during the operation, this will be signalled by an exception. In case of error, changes made will not be committed to the Btree - they will be discarded.
new_revision | The new revision number to store. This must be greater than the latest revision number (see get_latest_revision_number()), or an exception will be thrown. |
Reimplemented in FlintSpellingTable, and FlintSynonymTable.
Definition at line 1732 of file flint_table.cc.
References Assert, base, base_letter, BLK_UNUSED, both_bases, BTREE_CURSOR_LEVELS, Btree_modified, Cursor_::c, C, changed_c, changed_n, FlintTable_base::clear_bit_map(), close(), FlintTable_base::commit(), DEBUGCALL, DIR_START, faked_root_block, flint_io_sync(), handle, item_count, latest_revision_number, level, msvc_posix_rename(), Cursor_::n, other_base_letter(), read_root(), revision_number, Cursor_::rewrite, root, seq_count, SEQ_START_POINT, sequential, FlintTable_base::set_have_fakeroot(), FlintTable_base::set_item_count(), FlintTable_base::set_level(), FlintTable_base::set_revision(), FlintTable_base::set_root(), FlintTable_base::set_sequential(), unlink(), writable, write_block(), and FlintTable_base::write_to_file().
Referenced by FlintSynonymTable::commit(), FlintSpellingTable::commit(), multimerge_postlists(), and FlintDatabase::set_revision_number().
void FlintTable::cancel | ( | ) |
Cancel any outstanding changes.
This will discard any modifications which haven't been committed by calling commit().
Reimplemented in FlintSpellingTable, and FlintSynonymTable.
Definition at line 1836 of file flint_table.cc.
References Assert, base, base_letter, BLK_UNUSED, block_size, C, changed_c, changed_n, DEBUGCALL, DIR_START, faked_root_block, FlintTable_base::get_block_size(), FlintTable_base::get_have_fakeroot(), FlintTable_base::get_item_count(), FlintTable_base::get_level(), FlintTable_base::get_revision(), FlintTable_base::get_root(), FlintTable_base::get_sequential(), handle, item_count, latest_revision_number, level, FlintTable_base::read(), read_root(), revision_number, Cursor_::rewrite, root, seq_count, SEQ_START_POINT, sequential, and writable.
Referenced by FlintSynonymTable::cancel(), FlintSpellingTable::cancel(), and FlintDatabase::cancel().
bool FlintTable::get_exact_entry | ( | const string & | key, | |
string & | tag | |||
) | const |
Read an entry from the table, if and only if it is exactly that being asked for.
If the key is found in the table, the tag will be filled with the data associated with the key. If the key is not found, the tag will be unmodified.
key | The key to look for in the table. | |
tag | A tag object to fill with the value if found. |
Definition at line 1196 of file flint_table.cc.
References Assert, DEBUGCALL, find_tag(), FLINT_BTREE_MAX_KEY_LEN, handle, and RETURN.
Referenced by PostlistChunkWriter::flush(), FlintValueTable::get_all_values(), FlintTermListTable::get_doclength(), FlintDatabase::get_metadata(), FlintRecordTable::get_record(), FlintValueTable::get_value(), FlintSpellingTable::get_word_frequency(), FlintSpellingTable::merge_changes(), FlintPostListTable::merge_changes(), FlintPositionListTable::positionlist_count(), FlintPositionList::read_data(), and FlintDatabase::read_metainfo().
bool FlintTable::key_exists | ( | const string & | key | ) | const |
Check if a key exists in the Btree.
This is just like get_exact_entry() except it doesn't read the tag value so is more efficient if you only want to check that the key exists.
key | The key to look for in the table. |
Definition at line 1210 of file flint_table.cc.
References Assert, C, DEBUGCALL, find(), FLINT_BTREE_MAX_KEY_LEN, form_key(), and RETURN.
Referenced by FlintPostListTable::term_exists().
bool FlintTable::find_tag | ( | const string & | key, | |
string * | tag | |||
) | const |
Find a key in the Btree and read its tag.
If the key is found the tag is copied to tag. If the key is not found tag is left unchanged.
The result is true iff the specified key is found in the Btree.
e.g.
string t; btree.find_tag("TODAY", &t); // get today's date
Definition at line 1223 of file flint_table.cc.
References C, DEBUGCALL, find(), FLINT_BTREE_MAX_KEY_LEN, form_key(), handle, read_tag(), and RETURN.
Referenced by get_exact_entry().
bool FlintTable::read_tag | ( | Cursor_ * | C_, | |
string * | tag, | |||
bool | keep_compressed | |||
) | const |
Read the tag value for the key pointed to by cursor C_.
keep_compressed | Don't uncompress the tag - e.g. useful if it's just being opaquely copied. |
Definition at line 1239 of file flint_table.cc.
References Item_base_< T >::append_chunk(), C2, Item_base_< T >::components_of(), DEBUGLINE, Item_base_< T >::get_compressed(), I2, K1, max_item_size, next(), om_tostring(), and setint4().
Referenced by find_tag(), and FlintCursor::read_tag().
bool FlintTable::add | ( | const string & | key, | |
string | tag, | |||
bool | already_compressed = false | |||
) |
Add a key/tag pair to the table, replacing any existing pair with the same key.
If an error occurs during the operation, this will be signalled by a return value of false. All modifications since the previous commit() will be lost.
If key is empty, then the null item is replaced. If key.length() exceeds the limit on key size, false is returned.
e.g. ok = btree.add("TODAY", "Mon 9 Oct 2000");
key | The key to store in the table. | |
tag | The tag to store in the table. | |
already_compressed | true if tag is already compressed, for example because it is being opaquely copied (default: false). |
Definition at line 1020 of file flint_table.cc.
References add_kt(), Assert, block_size, Btree_modified, BYTE_PAIR_RANGE, C, C2, CompileTimeAssert, COMPRESS_MIN, compress_strategy, create_and_open(), D2, DEBUGCALL, delete_kt(), DONT_COMPRESS, find(), form_key(), full_compaction, handle, I2, item_count, K1, Item_base_< T >::key(), kt, Key_::length(), max_item_size, Cursor_::p, RETURN, Item_wr_::set_component_of(), Item_wr_::set_components_of(), Item_wr_::set_tag(), TOTAL_FREE, and writable.
Referenced by PostlistChunkWriter::flush(), FlintWritableDatabase::flush_postlist_changes(), merge_docid_keyed(), merge_postlists(), merge_spellings(), merge_synonyms(), and FlintWritableDatabase::set_metadata().
bool FlintTable::del | ( | const string & | key | ) |
Delete an entry from the table.
The entry will be removed from the table, if it exists. If it does not exist, no action will be taken. The item with an empty key can't be removed, and false is returned.
If an error occurs during the operation, this will be signalled by a return value of false. All modifications since the previous commit() will be lost.
e.g. ok = btree.del("TODAY")
key | The key to remove from the table. |
Definition at line 1169 of file flint_table.cc.
References Assert, Btree_modified, DEBUGCALL, delete_kt(), FLINT_BTREE_MAX_KEY_LEN, form_key(), handle, item_count, kt, RETURN, Item_wr_::set_component_of(), and writable.
Referenced by FlintCursor::del(), FlintValueTable::delete_all_values(), FlintPositionListTable::delete_positionlist(), FlintRecordTable::delete_record(), FlintTermListTable::delete_termlist(), PostlistChunkWriter::flush(), FlintSynonymTable::merge_changes(), FlintSpellingTable::merge_changes(), FlintPostListTable::merge_changes(), and FlintWritableDatabase::set_metadata().
void FlintTable::erase | ( | ) |
Erase this table from disk.
Definition at line 1643 of file flint_table.cc.
References close(), DEBUGCALL, and sys_unlink_if_exists().
Referenced by FlintSynonymTable::create_and_open(), FlintSpellingTable::create_and_open(), and FlintDatabase::create_and_open_tables().
void FlintTable::set_block_size | ( | unsigned int | block_size_ | ) |
Set the block size.
It's only safe to do this before the table is created.
Definition at line 1654 of file flint_table.cc.
References block_size, BYTE_PAIR_RANGE, DEBUGCALL, and FLINT_DEFAULT_BLOCK_SIZE.
Referenced by create_and_open(), FlintSynonymTable::create_and_open(), FlintSpellingTable::create_and_open(), FlintDatabase::create_and_open_tables(), FlintDatabase::open_tables(), and FlintDatabase::open_tables_consistent().
unsigned int FlintTable::get_block_size | ( | ) | const [inline] |
Get the block size.
Definition at line 461 of file flint_table.h.
Referenced by FlintDatabase::open_tables(), and FlintDatabase::open_tables_consistent().
void FlintTable::create_and_open | ( | unsigned int | blocksize | ) |
Create a new empty btree structure on disk and open it at the initial revision.
The table must be writable - it doesn't make sense to create a table that is read-only!
The block size must be less than 64K, where K = 1024. It is unwise to use a small block size (less than 1024 perhaps), so we enforce a minimum block size of 2K.
Example:
Btree btree("X-"); btree.create_and_open(8192); // Files will be X-DB, X-baseA (and X-baseB).
blocksize | - Size of blocks to use. |
Xapian::DatabaseCreateError | if the table can't be created. | |
Xapian::InvalidArgumentError | if the requested blocksize is unsuitable. |
Reimplemented in FlintSpellingTable, and FlintSynonymTable.
Definition at line 1666 of file flint_table.cc.
References Assert, close(), DEBUGCALL, do_open_to_write(), handle, revision_number, FlintTable_base::set_block_size(), set_block_size(), FlintTable_base::set_have_fakeroot(), FlintTable_base::set_revision(), FlintTable_base::set_sequential(), sys_unlink_if_exists(), writable, and FlintTable_base::write_to_file().
Referenced by add(), FlintDatabase::create_and_open_tables(), and multimerge_postlists().
void FlintTable::set_full_compaction | ( | bool | parity | ) |
Definition at line 1345 of file flint_table.cc.
References Assert, full_compaction, seq_count, and writable.
flint_revision_number_t FlintTable::get_latest_revision_number | ( | ) | const [inline] |
Get the latest revision number stored in this table.
This gives the higher of the revision numbers held in the base files of the B-tree, or just the revision number if there's only one base file.
It is possible that there are other, older, revisions of this table available, and indeed that the revision currently open is one of these older revisions.
Definition at line 500 of file flint_table.h.
Referenced by FlintDatabase::FlintDatabase(), and FlintDatabase::get_next_revision_number().
flint_revision_number_t FlintTable::get_open_revision_number | ( | ) | const [inline] |
Get the revision number at which this table is currently open.
It is possible that there are other, more recent or older revisions available.
Definition at line 512 of file flint_table.h.
Referenced by FlintDatabase::create_and_open_tables(), FlintDatabase::FlintDatabase(), FlintDatabase::get_revision_number(), and FlintDatabase::open_tables_consistent().
flint_tablesize_t FlintTable::get_entry_count | ( | ) | const [inline] |
Return a count of the number of entries in the table.
The count does not include the ever-present item with null key.
Definition at line 522 of file flint_table.h.
Referenced by FlintRecordTable::get_doccount(), FlintDatabase::has_positions(), main(), merge_docid_keyed(), and FlintDatabase::open_synonym_keylist().
FlintCursor * FlintTable::cursor_get | ( | ) | const |
Get a cursor for reading from the table.
The cursor is owned by the caller - it is the caller's responsibility to ensure that it is deleted.
Definition at line 1353 of file flint_table.cc.
References FlintCursor, and handle.
Referenced by check_table(), PostlistChunkWriter::flush(), FlintPostListTable::get_chunk(), FlintPostListTable::merge_changes(), FlintDatabase::open_metadata_keylist(), FlintDatabase::open_spelling_wordlist(), and FlintDatabase::open_synonym_keylist().
bool FlintTable::is_modified | ( | ) | const [inline] |
Determine whether the object contains uncommitted modifications.
Reimplemented in FlintSpellingTable, and FlintSynonymTable.
Definition at line 538 of file flint_table.h.
Referenced by FlintDatabase::apply(), FlintSynonymTable::is_modified(), and FlintSpellingTable::is_modified().
void FlintTable::set_max_item_size | ( | size_t | block_capacity | ) | [inline] |
Set the maximum item size given the block capacity.
At least this many items of maximum size must fit into a block. The default is BLOCK_CAPACITY (which is currently 4).
Definition at line 545 of file flint_table.h.
References D2.
Referenced by basic_open().
bool FlintTable::do_open_to_read | ( | bool | revision_supplied, | |
flint_revision_number_t | revision_ | |||
) | [protected] |
Perform the opening operation to read.
Return true iff the open succeeded.
Definition at line 1878 of file flint_table.cc.
References basic_open(), BLK_UNUSED, block_size, C, close(), handle, lazy, level, O_BINARY, open(), Cursor_::p, read_root(), and revision_number.
Referenced by open().
bool FlintTable::do_open_to_write | ( | bool | revision_supplied, | |
flint_revision_number_t | revision_, | |||
bool | create_db = false | |||
) | [protected] |
Perform the opening operation to write.
Return true iff the open succeeded.
Definition at line 1529 of file flint_table.cc.
References basic_open(), BLK_UNUSED, block_size, buffer, C, changed_c, changed_n, close(), DIR_START, handle, lazy, level, O_BINARY, open(), Cursor_::p, read_root(), revision_number, seq_count, SEQ_START_POINT, split_p, writable, and zeroed_new().
Referenced by create_and_open(), and open().
bool FlintTable::basic_open | ( | bool | revision_supplied, | |
flint_revision_number_t | revision | |||
) | [protected] |
Definition at line 1362 of file flint_table.cc.
References Assert, base, base_letter, BLOCK_CAPACITY, block_size, both_bases, close(), DEBUGLINE, faked_root_block, FlintTable_base::get_block_size(), FlintTable_base::get_have_fakeroot(), FlintTable_base::get_item_count(), FlintTable_base::get_level(), FlintTable_base::get_revision(), FlintTable_base::get_root(), FlintTable_base::get_sequential(), handle, item_count, kt, latest_revision_number, level, revision_number, root, sequential, set_max_item_size(), FlintTable_base::swap(), and zeroed_new().
Referenced by do_open_to_read(), and do_open_to_write().
bool FlintTable::find | ( | Cursor_ * | C_ | ) | const [protected] |
find(C_) searches for the key of B->kt in the B-tree.
Result is true if found, false otherwise. When false, the B_tree cursor is positioned at the last key in the B-tree <= the search key. Goes to first (null) item in B-tree when key length == 0.
Definition at line 503 of file flint_table.cc.
References block_given_by(), block_to_cursor(), DEBUGCALL, DIR_START, find_in_block(), Item_base_< T >::key(), kt, level, and RETURN.
Referenced by add(), delete_kt(), FlintCursor::find_entry(), FlintCursor::find_entry_ge(), find_tag(), and key_exists().
int FlintTable::delete_kt | ( | ) | [protected] |
Definition at line 958 of file flint_table.cc.
References alter(), Assert, C, delete_item(), find(), seq_count, SEQ_START_POINT, sequential, and writable.
void FlintTable::read_block | ( | uint4 | n, | |
byte * | p | |||
) | const [protected] |
read_block(n, p) reads block n of the DB file to address p.
Definition at line 222 of file flint_table.cc.
References Assert, base, block_size, DEBUGCALL, flint_io_read(), FlintTable_base::get_bit_map_size(), handle, and om_tostring().
Referenced by block_to_cursor(), next_for_sequential(), and prev_for_sequential().
void FlintTable::write_block | ( | uint4 | n, | |
const byte * | p | |||
) | const [protected] |
write_block(n, p) writes block n in the DB file from address p.
When writing we check to see if the DB file has already been modified. If not (so this is the first write) the old base is deleted. This prevents the possibility of it being opened subsequently as an invalid base.
Definition at line 274 of file flint_table.cc.
References Assert, AssertEqParanoid, AssertParanoid, base, FlintTable_base::block_free_at_start(), block_size, both_bases, DEBUGCALL, flint_io_write(), FlintTable_base::get_bit_map_size(), handle, latest_revision_number, other_base_letter(), REVISION, revision_number, sys_unlink(), and writable.
Referenced by add_item(), block_to_cursor(), and commit().
FlintTable::XAPIAN_NORETURN | ( | void set_overwritten() | const | ) | [protected] |
void FlintTable::block_to_cursor | ( | Cursor_ * | C_, | |
int | j, | |||
uint4 | n | |||
) | const [protected] |
Definition at line 374 of file flint_table.cc.
References Assert, AssertEq, block_size, C, DEBUGCALL, GET_LEVEL, level, Cursor_::n, Cursor_::p, read_block(), REVISION, Cursor_::rewrite, writable, and write_block().
Referenced by BtreeCheck::block_check(), delete_item(), find(), next_default(), prev_default(), and read_root().
void FlintTable::alter | ( | ) | [protected] |
Btree::alter(); is called when the B-tree is to be altered.
It causes new blocks to be forced for the current set of blocks in the cursor.
The point is that if a block at level 0 is to be altered it may get a new number. Then the pointer to this block from level 1 will need changing. So the block at level 1 needs altering and may get a new block number. Then the pointer to this block from level 2 will need changing ... and so on back to the root.
The clever bit here is spotting the cases when we can make an early exit from this process. If C[j].rewrite is true, C[j+k].rewrite will be true for k = 1,2 ... We have been through all this before, and there is no need to do it again. If C[j].n was free at the start of the transaction, we can copy it back to the same place without violating the integrity of the B-tree. We don't then need a new n and can return. The corresponding C[j].rewrite may be true or false in that case.
Definition at line 429 of file flint_table.cc.
References Assert, base, FlintTable_base::block_free_at_start(), C, DEBUGCALL, FlintTable_base::free_block(), latest_revision_number, level, Cursor_::n, FlintTable_base::next_free_block(), Cursor_::p, REVISION, Cursor_::rewrite, SET_REVISION, and writable.
Referenced by add_kt(), and delete_kt().
void FlintTable::compact | ( | byte * | p | ) | [protected] |
compact(p) compact the block at p by shuffling all the items up to the end.
MAX_FREE(p) is then maximized, and is equal to TOTAL_FREE(p).
Definition at line 537 of file flint_table.cc.
References Assert, block_size, buffer, D2, DEBUGCALL, DIR_END, DIR_START, SET_MAX_FREE, SET_TOTAL_FREE, setD, and writable.
Referenced by add_item(), add_item_to_block(), and split_root().
enter_key(j, prevkey, newkey) is called after a block split.
It enters in the block at level C[j] a separating key for the block at level C[j - 1]. The key itself is newkey. prevkey is the preceding key, and at level 1 newkey can be trimmed down to the first point of difference to prevkey for entry in C[j].
This code looks longer than it really is. If j exceeds the number of B-tree levels the root block has split and we have to construct a new one, but this is a rare event.
The key is constructed in b, with block number C[j - 1].n as tag, and this is added in with add_item. add_item may itself cause a block split, with a further call to enter_key. Hence the recursion.
Definition at line 606 of file flint_table.cc.
References add_item(), Assert, Cursor_::c, C, C2, D2, find_in_block(), Key_::get_address(), getint4(), I2, K1, Item_base_< T >::key(), Key_::length(), Cursor_::n, Cursor_::p, Cursor_::rewrite, Item_wr_::set_key_and_block(), SET_TOTAL_FREE, TOTAL_FREE, and writable.
Referenced by add_item().
int FlintTable::mid_point | ( | byte * | p | ) | [protected] |
mid_point(p) finds the directory entry in c that determines the approximate mid point of the data in the block at p.
Definition at line 666 of file flint_table.cc.
References Assert, block_size, D2, DIR_END, DIR_START, size, and TOTAL_FREE.
Referenced by add_item().
add_item_to_block(p, kt_, c) adds item kt_ to the block at p.
c is the offset in the directory that needs to be expanded to accommodate the new entry for the item. We know before this is called that there is enough room, so it's just a matter of byte shuffling.
Definition at line 694 of file flint_table.cc.
References Assert, compact(), D2, DIR_END, Item_base_< T >::get_address(), MAX_FREE, SET_DIR_END, SET_MAX_FREE, SET_TOTAL_FREE, setD, Item_base_< T >::size(), TOTAL_FREE, and writable.
Referenced by add_item().
void FlintTable::add_item | ( | Item_wr_ | kt_, | |
int | j | |||
) | [protected] |
FlintTable::add_item(kt_, j) adds item kt_ to the block at cursor level C[j].
If there is not enough room the block splits and the item is then added to the appropriate half.
Definition at line 731 of file flint_table.cc.
References add_item_to_block(), Assert, base, block_size, Cursor_::c, C, changed_c, changed_n, compact(), D2, DIR_END, DIR_START, enter_key(), level, mid_point(), Cursor_::n, FlintTable_base::next_free_block(), Cursor_::p, seq_count, SET_DIR_END, Item_base_< T >::size(), split_p, split_root(), TOTAL_FREE, writable, and write_block().
Referenced by add_kt(), enter_key(), and split_root().
void FlintTable::delete_item | ( | int | j, | |
bool | repeatedly | |||
) | [protected] |
FlintTable::delete_item(j, repeatedly) is (almost) the converse of add_item.
If repeatedly is true, the process repeats at the next level when a block has been completely emptied, freeing the block and taking out the pointer to it. Emptied root blocks are also removed, which reduces the number of levels in the B-tree.
Definition at line 821 of file flint_table.cc.
References Assert, base, BLK_UNUSED, block_to_cursor(), Cursor_::c, C, D2, DIR_END, DIR_START, FlintTable_base::free_block(), level, MAX_FREE, Cursor_::n, Cursor_::p, Cursor_::rewrite, SET_DIR_END, SET_MAX_FREE, SET_TOTAL_FREE, TOTAL_FREE, and writable.
Referenced by add_kt(), and delete_kt().
int FlintTable::add_kt | ( | bool | found | ) | [protected] |
add_kt(found) adds the item (key-tag pair) at B->kt into the B-tree, using cursor C.
found == find() is handed over as a parameter from Btree::add. Btree::alter() prepares for the alteration to the B-tree. Then there are a number of cases to consider:
If an item with the same key is in the B-tree (found is true), the new kt replaces it.
If then kt is smaller, or the same size as, the item it replaces, kt is put in the same place as the item it replaces, and the TOTAL_FREE measure is reduced.
If kt is larger than the item it replaces it is put in the MAX_FREE space if there is room, and the directory entry and space counts are adjusted accordingly.
If the key of kt is not in the B-tree (found is false), the new kt is added in with add_item.
Definition at line 893 of file flint_table.cc.
References add_item(), alter(), Assert, Cursor_::c, C, changed_c, changed_n, D2, delete_item(), DIR_END, Item_base_< T >::get_address(), kt, MAX_FREE, Cursor_::p, seq_count, SEQ_START_POINT, sequential, SET_MAX_FREE, SET_TOTAL_FREE, setD, Item_base_< T >::size(), TOTAL_FREE, and writable.
Referenced by add().
void FlintTable::read_root | ( | ) | [protected] |
Definition at line 1486 of file flint_table.cc.
References Assert, base, block_size, block_to_cursor(), C, C2, D2, DIR_START, faked_root_block, I2, K1, latest_revision_number, level, Cursor_::n, FlintTable_base::next_free_block(), Cursor_::p, REVISION, revision_number, root, SET_DIR_END, SET_LEVEL, SET_MAX_FREE, SET_REVISION, SET_TOTAL_FREE, setD, and writable.
Referenced by cancel(), commit(), do_open_to_read(), and do_open_to_write().
void FlintTable::split_root | ( | uint4 | split_n | ) | [protected] |
Btree needs to gain a new level to insert more items: so split root block and construct a new one.
Definition at line 561 of file flint_table.cc.
References add_item(), base, block_size, BTREE_CURSOR_LEVELS, Cursor_::c, C, compact(), DEBUGCALL, DIR_START, Item_wr_::form_null_key(), latest_revision_number, level, Cursor_::n, FlintTable_base::next_free_block(), Cursor_::p, Cursor_::rewrite, SET_DIR_END, SET_LEVEL, SET_REVISION, STRINGIZE, and zeroed_new().
Referenced by add_item().
void FlintTable::form_key | ( | const string & | key | ) | const [protected] |
Definition at line 991 of file flint_table.cc.
References Item_wr_::form_key(), and kt.
Referenced by add(), del(), FlintCursor::find_entry(), FlintCursor::find_entry_ge(), find_tag(), and key_exists().
char FlintTable::other_base_letter | ( | ) | const [inline, protected] |
bool FlintTable::prev | ( | Cursor_ * | C_, | |
int | j | |||
) | const [inline, protected] |
Definition at line 670 of file flint_table.h.
Referenced by FlintCursor::find_entry(), and FlintCursor::prev().
bool FlintTable::next | ( | Cursor_ * | C_, | |
int | j | |||
) | const [inline, protected] |
Definition at line 675 of file flint_table.h.
Referenced by FlintCursor::find_entry_ge(), FlintCursor::next(), read_tag(), and FlintCursor::read_tag().
bool FlintTable::prev_default | ( | Cursor_ * | C_, | |
int | j | |||
) | const [protected] |
Definition at line 2071 of file flint_table.cc.
References Assert, block_given_by(), block_size, block_to_cursor(), Cursor_::c, D2, DIR_END, DIR_START, level, and Cursor_::p.
bool FlintTable::next_default | ( | Cursor_ * | C_, | |
int | j | |||
) | const [protected] |
Definition at line 2092 of file flint_table.cc.
References Assert, block_given_by(), block_size, block_to_cursor(), Cursor_::c, D2, DIR_END, DIR_START, level, and Cursor_::p.
bool FlintTable::prev_for_sequential | ( | Cursor_ * | C_, | |
int | dummy | |||
) | const [protected] |
Definition at line 1967 of file flint_table.cc.
References Assert, AssertEq, block_size, C, Cursor_::c, D2, DIR_END, DIR_START, GET_LEVEL, latest_revision_number, level, Cursor_::n, Cursor_::p, read_block(), REVISION, revision_number, and writable.
bool FlintTable::next_for_sequential | ( | Cursor_ * | C_, | |
int | dummy | |||
) | const [protected] |
Definition at line 2018 of file flint_table.cc.
References Assert, AssertEq, base, block_size, C, Cursor_::c, D2, DIR_END, DIR_START, FlintTable_base::get_last_block(), GET_LEVEL, latest_revision_number, level, Cursor_::n, Cursor_::p, read_block(), REVISION, revision_number, and writable.
find_in_block(p, key, leaf, c) searches for the key in the block at p.
leaf is true for a data block, and false for an index block (when the first key is dummy and never needs to be tested). What we get is the directory entry to the last key <= the key being searched for.
The lookup is by binary chop, with i and j set to the left and right ends of the search area. In sequential addition, c will often be the answer, so we test the keys round c and move i and j towards c if possible.
Definition at line 473 of file flint_table.cc.
References D2, DEBUGCALL_STATIC, DIR_END, DIR_START, Key_::get_address(), and RETURN.
Referenced by enter_key(), and find().
static uint4 FlintTable::block_given_by | ( | const byte * | p, | |
int | c | |||
) | [static, protected] |
block_given_by(p, c) finds the item at block address p, directory offset c, and returns its tag value as an integer.
Referenced by BtreeCheck::block_check(), find(), next_default(), and prev_default().
friend class FlintCursor [friend] |
flint_revision_number_t FlintTable::revision_number [protected] |
revision number of the opened B-tree.
Definition at line 591 of file flint_table.h.
Referenced by basic_open(), cancel(), commit(), create_and_open(), do_open_to_read(), do_open_to_write(), next_for_sequential(), open(), prev_for_sequential(), read_root(), and write_block().
uint4 FlintTable::item_count [protected] |
keeps a count of the number of items in the B-tree.
Definition at line 594 of file flint_table.h.
Referenced by add(), basic_open(), cancel(), commit(), and del().
unsigned int FlintTable::block_size [protected] |
block size of the B tree in bytes
Definition at line 597 of file flint_table.h.
Referenced by add(), add_item(), basic_open(), BtreeCheck::block_check(), block_to_cursor(), BtreeCheck::block_usage(), cancel(), compact(), do_open_to_read(), do_open_to_write(), FlintCursor::FlintCursor(), mid_point(), next_default(), next_for_sequential(), prev_default(), prev_for_sequential(), read_block(), read_root(), set_block_size(), split_root(), and write_block().
flint_revision_number_t FlintTable::latest_revision_number [mutable, protected] |
Revision number of the other base, or zero if there is only one base file.
Definition at line 602 of file flint_table.h.
Referenced by alter(), basic_open(), cancel(), commit(), next_for_sequential(), prev_for_sequential(), read_root(), split_root(), and write_block().
bool FlintTable::both_bases [mutable, protected] |
set to true if baseA and baseB both exist as valid bases.
The unused base is deleted as soon as a write to the Btree takes place.
Definition at line 608 of file flint_table.h.
Referenced by basic_open(), commit(), and write_block().
char FlintTable::base_letter [protected] |
the value 'A' or 'B' of the current base
Definition at line 611 of file flint_table.h.
Referenced by basic_open(), cancel(), and commit().
bool FlintTable::faked_root_block [protected] |
true if the root block is faked (not written to disk).
false otherwise. This is true when the btree hasn't been modified yet.
Definition at line 617 of file flint_table.h.
Referenced by basic_open(), cancel(), commit(), and read_root().
bool FlintTable::sequential [protected] |
true iff the data has been written in a single write in sequential order.
Definition at line 622 of file flint_table.h.
Referenced by add_kt(), basic_open(), cancel(), commit(), and delete_kt().
int FlintTable::handle [protected] |
corresponding file handle
Definition at line 625 of file flint_table.h.
Referenced by add(), basic_open(), cancel(), close(), commit(), create_and_open(), cursor_get(), del(), do_open_to_read(), do_open_to_write(), find_tag(), get_exact_entry(), read_block(), and write_block().
int FlintTable::level [protected] |
number of levels, counting from 0
Definition at line 628 of file flint_table.h.
Referenced by add_item(), alter(), basic_open(), BtreeCheck::block_check(), block_to_cursor(), cancel(), close(), commit(), delete_item(), do_open_to_read(), do_open_to_write(), find(), FlintCursor::find_entry(), FlintCursor::find_entry_ge(), FlintCursor::get_key(), FlintCursor::next(), next_default(), next_for_sequential(), FlintCursor::prev(), prev_default(), prev_for_sequential(), read_root(), FlintCursor::read_tag(), BtreeCheck::report_cursor(), and split_root().
uint4 FlintTable::root [protected] |
the root block of the B-tree
Definition at line 631 of file flint_table.h.
Referenced by basic_open(), cancel(), commit(), and read_root().
Item_wr_ FlintTable::kt [mutable, protected] |
buffer of size block_size for making up key-tag items
Definition at line 634 of file flint_table.h.
Referenced by add(), add_kt(), basic_open(), close(), del(), find(), and form_key().
byte* FlintTable::buffer [protected] |
buffer of size block_size for reforming blocks
Definition at line 637 of file flint_table.h.
Referenced by close(), compact(), and do_open_to_write().
FlintTable_base FlintTable::base [protected] |
For writing back as file baseA or baseB.
Definition at line 640 of file flint_table.h.
Referenced by add_item(), alter(), basic_open(), BtreeCheck::block_check(), cancel(), commit(), delete_item(), next_for_sequential(), read_block(), read_root(), split_root(), and write_block().
string FlintTable::name [protected] |
int FlintTable::seq_count [protected] |
count of the number of successive instances of purely sequential addition, starting at SEQ_START_POINT (neg) and going up to zero.
Definition at line 648 of file flint_table.h.
Referenced by add_item(), add_kt(), cancel(), commit(), delete_kt(), do_open_to_write(), and set_full_compaction().
uint4 FlintTable::changed_n [protected] |
the last block to be changed by an addition
Definition at line 651 of file flint_table.h.
Referenced by add_item(), add_kt(), cancel(), commit(), and do_open_to_write().
int FlintTable::changed_c [protected] |
directory offset corresponding to last block to be changed by an addition
Definition at line 655 of file flint_table.h.
Referenced by add_item(), add_kt(), cancel(), commit(), and do_open_to_write().
size_t FlintTable::max_item_size [protected] |
maximum size of an item (key-tag pair)
Definition at line 658 of file flint_table.h.
Referenced by add(), and read_tag().
bool FlintTable::Btree_modified [mutable, protected] |
bool FlintTable::full_compaction [protected] |
set to true when full compaction is to be achieved
Definition at line 664 of file flint_table.h.
Referenced by add(), and set_full_compaction().
bool FlintTable::writable [protected] |
Set to true when the database is opened to write.
Definition at line 667 of file flint_table.h.
Referenced by add(), add_item(), add_item_to_block(), add_kt(), alter(), block_to_cursor(), cancel(), commit(), compact(), create_and_open(), del(), delete_item(), delete_kt(), do_open_to_write(), enter_key(), next_for_sequential(), open(), prev_for_sequential(), read_root(), set_full_compaction(), and write_block().
Cursor_ FlintTable::C[BTREE_CURSOR_LEVELS] [mutable, protected] |
Definition at line 695 of file flint_table.h.
Referenced by add(), add_item(), add_kt(), alter(), block_to_cursor(), cancel(), close(), commit(), delete_item(), delete_kt(), do_open_to_read(), do_open_to_write(), enter_key(), find_tag(), FlintCursor::FlintCursor(), key_exists(), next_for_sequential(), prev_for_sequential(), read_root(), and split_root().
byte* FlintTable::split_p [protected] |
Buffer used when splitting a block.
This buffer holds the split off part of the block. It's only used when updating (in FlintTable::add_item().
Definition at line 702 of file flint_table.h.
Referenced by add_item(), close(), and do_open_to_write().
int FlintTable::compress_strategy [protected] |
DONT_COMPRESS or Z_DEFAULT_STRATEGY, Z_FILTERED, Z_HUFFMAN_ONLY, Z_RLE.
Definition at line 706 of file flint_table.h.
Referenced by add().
bool FlintTable::lazy [protected] |
If true, don't create the table until it's needed.
Definition at line 709 of file flint_table.h.
Referenced by do_open_to_read(), and do_open_to_write().