#include <btree.h>
Inheritance diagram for Btree:
Public Member Functions | |
| Btree (string path_, bool readonly_) | |
| Create a new Btree object. | |
| ~Btree () | |
| Close the Btree. | |
| void | close () |
| Close the Btree. | |
| bool | exists () const |
| Determine whether the btree exists on disk. | |
| void | open () |
| Open the btree at the latest revision. | |
| bool | open (quartz_revision_number_t revision_) |
| Open the btree at a given revision. | |
| void | commit (quartz_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 | find_tag (const string &key, string *tag) const |
| Find a key in the Btree and read its tag. | |
| void | read_tag (Cursor *C_, string *tag) const |
| Read the tag value for the key pointed to by cursor C_. | |
| bool | add (const string &key, string tag) |
| 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 | create (unsigned int blocksize) |
| Create a new empty btree structure on disk. | |
| void | set_full_compaction (bool parity) |
| quartz_revision_number_t | get_latest_revision_number () const |
| Get the latest revision number stored in this table. | |
| quartz_revision_number_t | get_open_revision_number () const |
| Get the revision number at which this table is currently open. | |
| quartz_tablesize_t | get_entry_count () const |
| Return a count of the number of entries in the table. | |
| Bcursor * | 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, quartz_revision_number_t revision_) |
| Perform the opening operation to read. | |
| bool | do_open_to_write (bool revision_supplied, quartz_revision_number_t revision_) |
| Perform the opening operation to write. | |
| bool | basic_open (bool revision_supplied, quartz_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) |
| Btree::add_item(kt_, j) adds item kt_ to the block at cursor level C[j]. | |
| void | delete_item (int j, bool repeatedly) |
| Btree::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 |
| 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 | |
| quartz_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 | |
| quartz_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. | |
| int | 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 | |
| Btree_base | base |
| For writing back as file baseA or baseB. | |
| char | other_base_letter |
| The base letter ('B' or 'A') of the next base. | |
| 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. | |
| bool | dont_close_handle |
| Set to true if we shouldn't close handle ourselves. | |
| bool(Btree::* | prev_ptr )(Cursor *, int) const |
| bool(Btree::* | next_ptr )(Cursor *, int) const |
| Cursor | C [BTREE_CURSOR_LEVELS] |
| byte * | split_p |
| Buffer used when splitting a block. | |
Private Member Functions | |
| Btree (const Btree &) | |
| Copying not allowed. | |
| Btree & | operator= (const Btree &) |
| Assignment not allowed. | |
Friends | |
| class | Bcursor |
A table is a store holding a set of key/tag pairs.
A key is used to access a block of data in a quartz 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 311 of file btree.h.
| Btree::Btree | ( | const Btree & | ) | [private] |
Copying not allowed.
| Btree::Btree | ( | string | path_, | |
| bool | readonly_ | |||
| ) |
Create a new Btree object.
This does not create the table on disk - the create() method must be called to create the table on disk.
This also does not open the table - the open() method 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. |
Definition at line 1484 of file btree.cc.
References DEBUGCALL.
| Btree::~Btree | ( | ) |
| void Btree::close | ( | ) |
Close the Btree.
This closes and frees any of the btree structures which have been created and opened.
Definition at line 1575 of file btree.cc.
References buffer, C, DEBUGCALL, dont_close_handle, Item_base< T >::get_address(), handle, kt, level, Cursor::p, split_p, and sys_close().
| bool Btree::exists | ( | ) | const |
Determine whether the btree exists on disk.
Definition at line 1515 of file btree.cc.
References DEBUGCALL, and file_exists().
Referenced by QuartzDatabase::database_exists().
| void Btree::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 1773 of file btree.cc.
References close(), DEBUGCALL, DEBUGLINE, do_open_to_read(), do_open_to_write(), and writable.
Referenced by check_table(), QuartzDatabase::create_and_open_tables(), do_update(), main(), QuartzDatabase::open_tables(), QuartzDatabase::open_tables_consistent(), test_bitmap1(), test_cursor1(), test_cursor2(), test_cursor3(), test_emptykey1(), test_insertdelete1(), test_overwrite1(), test_sequent1(), test_simple1(), test_table1(), test_table2(), test_table3(), test_table4(), test_table5(), and test_table6().
| bool Btree::open | ( | quartz_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 1790 of file btree.cc.
References AssertEq, close(), DEBUGCALL, DEBUGLINE, do_open_to_read(), do_open_to_write(), RETURN, revision_number, and writable.
| void Btree::commit | ( | quartz_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. |
Definition at line 1599 of file btree.cc.
References Assert, base, base_letter, BLK_UNUSED, both_bases, BTREE_CURSOR_LEVELS, Btree_modified, Cursor::c, C, changed_c, changed_n, Btree_base::clear_bit_map(), Btree_base::commit(), DEBUGCALL, DIR_START, dont_close_handle, faked_root_block, 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, Btree_base::set_have_fakeroot(), Btree_base::set_item_count(), Btree_base::set_level(), Btree_base::set_revision(), Btree_base::set_root(), Btree_base::set_sequential(), sys_close(), sys_flush(), unlink(), writable, write_block(), and Btree_base::write_to_file().
Referenced by QuartzDatabase::apply(), do_update(), main(), QuartzDatabase::QuartzDatabase(), QuartzDatabase::set_revision_number(), test_bitmap1(), test_cursor1(), test_cursor2(), test_cursor3(), test_emptykey1(), test_overwrite1(), test_table1(), test_table2(), test_table3(), test_table4(), test_table5(), and test_table6().
| void Btree::cancel | ( | ) |
Cancel any outstanding changes.
This will discard any modifications which haven't been committed by calling commit().
Definition at line 1697 of file btree.cc.
References Assert, base, BLK_UNUSED, block_size, C, changed_c, changed_n, DEBUGCALL, DIR_START, faked_root_block, Btree_base::get_block_size(), Btree_base::get_have_fakeroot(), Btree_base::get_item_count(), Btree_base::get_level(), Btree_base::get_revision(), Btree_base::get_root(), Btree_base::get_sequential(), item_count, latest_revision_number, level, next_default(), next_ptr, prev_default(), prev_ptr, Btree_base::read(), read_root(), revision_number, Cursor::rewrite, root, seq_count, SEQ_START_POINT, sequential, and writable.
Referenced by QuartzDatabase::cancel(), and test_table6().
| bool Btree::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 1204 of file btree.cc.
References Assert, BTREE_MAX_KEY_LEN, DEBUGCALL, find_tag(), and RETURN.
Referenced by check_table_values_empty(), check_table_values_hello(), QPostlistChunkWriter::flush(), QuartzValueTable::get_all_values(), QuartzRecordTable::get_lastdocid(), QuartzRecordTable::get_record(), QuartzRecordTable::get_total_length(), QuartzValueTable::get_value(), QuartzPostListTable::merge_changes(), QuartzTermList::QuartzTermList(), QuartzPositionList::read_data(), and test_overwrite1().
| bool Btree::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 1216 of file btree.cc.
References C, DEBUGCALL, find(), form_key(), read_tag(), and RETURN.
Referenced by get_exact_entry().
| void Btree::read_tag | ( | Cursor * | C_, | |
| string * | tag | |||
| ) | const |
Read the tag value for the key pointed to by cursor C_.
Definition at line 1227 of file btree.cc.
References Item_base< T >::append_chunk(), C2, Item_base< T >::components_of(), I2, K1, max_item_size, and next().
Referenced by find_tag(), and Bcursor::read_tag().
| bool Btree::add | ( | const string & | key, | |
| string | tag | |||
| ) |
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 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. |
Definition at line 1090 of file btree.cc.
References add_kt(), Assert, block_size, BTREE_MAX_KEY_LEN, Btree_modified, BYTE_PAIR_RANGE, C, C2, D2, DEBUGCALL, delete_kt(), find(), form_key(), full_compaction, I2, item_count, K1, Item_base< T >::key(), kt, Key::length(), max_item_size, om_tostring(), Cursor::p, RETURN, Item_wr::set_component_of(), Item_wr::set_components_of(), Item_wr::set_tag(), STRINGIZE, TOTAL_FREE, and writable.
Referenced by QPostlistChunkWriter::flush(), main(), process_lines(), test_bitmap1(), test_cursor1(), test_cursor2(), test_cursor3(), test_emptykey1(), test_overwrite1(), test_table1(), test_table2(), test_table3(), test_table4(), test_table5(), and test_table6().
| bool Btree::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 1179 of file btree.cc.
References Assert, BTREE_MAX_KEY_LEN, Btree_modified, DEBUGCALL, delete_kt(), form_key(), item_count, kt, RETURN, Item_wr::set_component_of(), and writable.
Referenced by Bcursor::del(), QuartzValueTable::delete_all_values(), QuartzPositionListTable::delete_positionlist(), QuartzRecordTable::delete_record(), QuartzTermListTable::delete_termlist(), QPostlistChunkWriter::flush(), QuartzPostListTable::merge_changes(), process_lines(), test_cursor1(), test_emptykey1(), test_table1(), and test_table4().
| void Btree::create | ( | unsigned int | blocksize | ) |
Create a new empty btree structure on disk.
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(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. |
Definition at line 1535 of file btree.cc.
References BYTE_PAIR_RANGE, close(), DEBUGCALL, Btree_base::set_block_size(), Btree_base::set_have_fakeroot(), Btree_base::set_sequential(), sys_close(), sys_open_to_write(), sys_unlink_if_exists(), and Btree_base::write_to_file().
Referenced by QuartzDatabase::create_and_open_tables(), main(), test_bitmap1(), test_cursor1(), test_cursor2(), test_cursor3(), test_overwrite1(), test_simple1(), test_table2(), test_table3(), test_table4(), test_table5(), and test_table6().
| void Btree::set_full_compaction | ( | bool | parity | ) |
Definition at line 1252 of file btree.cc.
References Assert, full_compaction, seq_count, and writable.
Referenced by do_update(), and main().
| quartz_revision_number_t Btree::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 505 of file btree.h.
Referenced by QuartzDatabase::get_next_revision_number(), QuartzDatabase::QuartzDatabase(), test_bitmap1(), test_cursor1(), test_cursor2(), test_cursor3(), test_overwrite1(), test_table1(), test_table2(), test_table3(), test_table4(), test_table5(), and test_table6().
| quartz_revision_number_t Btree::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 517 of file btree.h.
Referenced by QuartzDatabase::create_and_open_tables(), do_update(), QuartzDatabase::get_revision_number(), QuartzDatabase::open_tables_consistent(), QuartzDatabase::QuartzDatabase(), test_cursor3(), test_emptykey1(), test_table1(), test_table5(), and test_table6().
| quartz_tablesize_t Btree::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 527 of file btree.h.
Referenced by QuartzRecordTable::get_doccount(), QuartzDatabase::has_positions(), main(), QuartzWritableDatabase::open_allterms(), QuartzDatabase::open_allterms(), test_cursor3(), test_emptykey1(), test_insertdelete1(), test_sequent1(), test_table1(), test_table4(), test_table5(), and test_table6().
| Bcursor * Btree::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 1260 of file btree.cc.
References Bcursor.
Referenced by check_table(), check_table_values_empty(), check_table_values_hello(), QPostlistChunkWriter::flush(), QuartzPostListTable::get_chunk(), QuartzPostListTable::merge_changes(), QuartzWritableDatabase::open_allterms(), QuartzDatabase::open_allterms(), QuartzAllDocsPostList::QuartzAllDocsPostList(), QuartzDatabase::term_exists(), test_cursor1(), test_cursor2(), test_cursor3(), test_table3(), test_table5(), and test_table6().
| bool Btree::is_modified | ( | ) | const [inline] |
Determine whether the object contains uncommitted modifications.
Definition at line 543 of file btree.h.
Referenced by QuartzDatabase::apply().
| void Btree::set_max_item_size | ( | size_t | block_capacity | ) | [inline] |
| bool Btree::do_open_to_read | ( | bool | revision_supplied, | |
| quartz_revision_number_t | revision_ | |||
| ) | [protected] |
Perform the opening operation to read.
Return true iff the open succeeded.
Definition at line 1737 of file btree.cc.
References basic_open(), BLK_UNUSED, block_size, C, handle, level, next_default(), next_for_sequential(), next_ptr, Cursor::p, prev_default(), prev_for_sequential(), prev_ptr, read_root(), sequential, and sys_open_to_read().
Referenced by open().
| bool Btree::do_open_to_write | ( | bool | revision_supplied, | |
| quartz_revision_number_t | revision_ | |||
| ) | [protected] |
Perform the opening operation to write.
Return true iff the open succeeded.
Definition at line 1434 of file btree.cc.
References base_letter, basic_open(), BLK_UNUSED, block_size, buffer, C, changed_c, changed_n, DIR_START, handle, level, next_default(), next_ptr, other_base_letter, Cursor::p, prev_default(), prev_ptr, read_root(), seq_count, SEQ_START_POINT, split_p, sys_open_for_readwrite(), writable, and zeroed_new().
Referenced by open().
| bool Btree::basic_open | ( | bool | revision_supplied, | |
| quartz_revision_number_t | revision | |||
| ) | [protected] |
Definition at line 1268 of file btree.cc.
References Assert, base, base_letter, BLOCK_CAPACITY, block_size, both_bases, DEBUGLINE, faked_root_block, Item_base< T >::get_address(), Btree_base::get_block_size(), Btree_base::get_have_fakeroot(), Btree_base::get_item_count(), Btree_base::get_level(), Btree_base::get_revision(), Btree_base::get_root(), Btree_base::get_sequential(), item_count, kt, latest_revision_number, level, revision_number, root, sequential, set_max_item_size(), Btree_base::swap(), and zeroed_new().
Referenced by do_open_to_read(), and do_open_to_write().
| bool Btree::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 567 of file btree.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(), Bcursor::find_entry(), and find_tag().
| int Btree::delete_kt | ( | ) | [protected] |
Definition at line 1028 of file btree.cc.
References alter(), Assert, C, delete_item(), find(), seq_count, SEQ_START_POINT, sequential, and writable.
| void Btree::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 266 of file btree.cc.
References Assert, base, block_size, DEBUGCALL, Btree_base::get_bit_map_size(), handle, and om_tostring().
Referenced by block_to_cursor(), next_for_sequential(), and prev_for_sequential().
| void Btree::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 338 of file btree.cc.
References Assert, AssertEqParanoid, AssertParanoid, base, Btree_base::block_free_at_start(), block_size, both_bases, DEBUGCALL, Btree_base::get_bit_map_size(), handle, latest_revision_number, other_base_letter, REVISION, revision_number, sys_unlink(), sys_write_bytes(), and writable.
Referenced by add_item(), block_to_cursor(), and commit().
| Btree::XAPIAN_NORETURN | ( | void set_overwritten() | const | ) | [protected] |
| void Btree::block_to_cursor | ( | Cursor * | C_, | |
| int | j, | |||
| uint4 | n | |||
| ) | const [protected] |
Definition at line 438 of file btree.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 delete_item(), find(), next_default(), prev_default(), and read_root().
| void Btree::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 493 of file btree.cc.
References Assert, base, Btree_base::block_free_at_start(), C, DEBUGCALL, Btree_base::free_block(), latest_revision_number, level, Cursor::n, Btree_base::next_free_block(), Cursor::p, REVISION, Cursor::rewrite, SET_REVISION, and writable.
Referenced by add_kt(), and delete_kt().
| void Btree::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 601 of file btree.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 676 of file btree.cc.
References add_item(), Assert, Cursor::c, C, C2, D2, find_in_block(), Key::get_address(), get_int4(), 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 Btree::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 736 of file btree.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 764 of file btree.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 Btree::add_item | ( | Item_wr | kt_, | |
| int | j | |||
| ) | [protected] |
Btree::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 801 of file btree.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, Btree_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 Btree::delete_item | ( | int | j, | |
| bool | repeatedly | |||
| ) | [protected] |
Btree::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 891 of file btree.cc.
References Assert, base, BLK_UNUSED, block_to_cursor(), Cursor::c, C, D2, DIR_END, DIR_START, Btree_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 Btree::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 963 of file btree.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 Btree::read_root | ( | ) | [protected] |
Definition at line 1391 of file btree.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, Btree_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 Btree::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 628 of file btree.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, Btree_base::next_free_block(), Cursor::p, Cursor::rewrite, SET_DIR_END, SET_LEVEL, SET_REVISION, STRINGIZE, and zeroed_new().
Referenced by add_item().
| void Btree::form_key | ( | const string & | key | ) | const [protected] |
Definition at line 1061 of file btree.cc.
References Item_wr::form_key(), and kt.
Referenced by add(), del(), Bcursor::find_entry(), and find_tag().
| bool Btree::prev | ( | Cursor * | C_, | |
| int | j | |||
| ) | const [inline, protected] |
| bool Btree::next | ( | Cursor * | C_, | |
| int | j | |||
| ) | const [inline, protected] |
Definition at line 676 of file btree.h.
Referenced by Bcursor::next(), read_tag(), and Bcursor::read_tag().
| bool Btree::prev_default | ( | Cursor * | C_, | |
| int | j | |||
| ) | const [protected] |
Definition at line 1917 of file btree.cc.
References Assert, block_given_by(), block_size, block_to_cursor(), Cursor::c, D2, DIR_END, DIR_START, level, and Cursor::p.
Referenced by cancel(), do_open_to_read(), and do_open_to_write().
| bool Btree::next_default | ( | Cursor * | C_, | |
| int | j | |||
| ) | const [protected] |
Definition at line 1938 of file btree.cc.
References Assert, block_given_by(), block_size, block_to_cursor(), Cursor::c, D2, DIR_END, DIR_START, level, and Cursor::p.
Referenced by cancel(), do_open_to_read(), and do_open_to_write().
| bool Btree::prev_for_sequential | ( | Cursor * | C_, | |
| int | dummy | |||
| ) | const [protected] |
| bool Btree::next_for_sequential | ( | Cursor * | C_, | |
| int | dummy | |||
| ) | const [protected] |
Definition at line 1867 of file btree.cc.
References Assert, base, block_size, C, Cursor::c, D2, DIR_END, DIR_START, Btree_base::get_last_block(), GET_LEVEL, level, Cursor::n, Cursor::p, read_block(), REVISION, and writable.
Referenced by do_open_to_read().
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 537 of file btree.cc.
References D2, DEBUGCALL_STATIC, DIR_END, DIR_START, Key::get_address(), and RETURN.
Referenced by enter_key(), and find().
| static uint4 Btree::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 find(), next_default(), and prev_default().
friend class Bcursor [friend] |
quartz_revision_number_t Btree::revision_number [protected] |
revision number of the opened B-tree.
Definition at line 590 of file btree.h.
Referenced by basic_open(), cancel(), commit(), open(), read_root(), and write_block().
uint4 Btree::item_count [protected] |
unsigned int Btree::block_size [protected] |
block size of the B tree in bytes
Definition at line 596 of file btree.h.
Referenced by add(), add_item(), basic_open(), Bcursor::Bcursor(), block_to_cursor(), cancel(), compact(), do_open_to_read(), do_open_to_write(), mid_point(), next_default(), next_for_sequential(), prev_default(), prev_for_sequential(), read_block(), read_root(), split_root(), and write_block().
quartz_revision_number_t Btree::latest_revision_number [mutable, protected] |
Revision number of the other base, or zero if there is only one base file.
Definition at line 601 of file btree.h.
Referenced by alter(), basic_open(), cancel(), commit(), read_root(), split_root(), and write_block().
bool Btree::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 607 of file btree.h.
Referenced by basic_open(), commit(), and write_block().
int Btree::base_letter [protected] |
the value 'A' or 'B' of the current base
Definition at line 610 of file btree.h.
Referenced by basic_open(), commit(), and do_open_to_write().
bool Btree::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 616 of file btree.h.
Referenced by basic_open(), cancel(), commit(), and read_root().
bool Btree::sequential [protected] |
true iff the data has been written in a single write in sequential order.
Definition at line 621 of file btree.h.
Referenced by add_kt(), basic_open(), cancel(), commit(), delete_kt(), and do_open_to_read().
int Btree::handle [protected] |
corresponding file handle
Definition at line 624 of file btree.h.
Referenced by close(), commit(), do_open_to_read(), do_open_to_write(), read_block(), and write_block().
int Btree::level [protected] |
number of levels, counting from 0
Definition at line 627 of file btree.h.
Referenced by add_item(), alter(), basic_open(), block_to_cursor(), cancel(), close(), commit(), delete_item(), do_open_to_read(), do_open_to_write(), find(), Bcursor::find_entry(), Bcursor::get_key(), Bcursor::next(), next_default(), next_for_sequential(), Bcursor::prev(), prev_default(), prev_for_sequential(), read_root(), Bcursor::read_tag(), and split_root().
uint4 Btree::root [protected] |
the root block of the B-tree
Definition at line 630 of file btree.h.
Referenced by basic_open(), cancel(), commit(), and read_root().
buffer of size block_size for making up key-tag items
Definition at line 633 of file btree.h.
Referenced by add(), add_kt(), basic_open(), close(), del(), find(), and form_key().
byte* Btree::buffer [protected] |
buffer of size block_size for reforming blocks
Definition at line 636 of file btree.h.
Referenced by close(), compact(), and do_open_to_write().
Btree_base Btree::base [protected] |
For writing back as file baseA or baseB.
Definition at line 639 of file btree.h.
Referenced by add_item(), alter(), basic_open(), cancel(), commit(), delete_item(), next_for_sequential(), read_block(), read_root(), split_root(), and write_block().
char Btree::other_base_letter [protected] |
The base letter ('B' or 'A') of the next base.
Definition at line 642 of file btree.h.
Referenced by commit(), do_open_to_write(), and write_block().
string Btree::name [protected] |
int Btree::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 650 of file btree.h.
Referenced by add_item(), add_kt(), cancel(), commit(), delete_kt(), do_open_to_write(), and set_full_compaction().
uint4 Btree::changed_n [protected] |
the last block to be changed by an addition
Definition at line 653 of file btree.h.
Referenced by add_item(), add_kt(), cancel(), commit(), and do_open_to_write().
int Btree::changed_c [protected] |
directory offset corresponding to last block to be changed by an addition
Definition at line 657 of file btree.h.
Referenced by add_item(), add_kt(), cancel(), commit(), and do_open_to_write().
size_t Btree::max_item_size [protected] |
maximum size of an item (key-tag pair)
Definition at line 660 of file btree.h.
Referenced by add(), and read_tag().
bool Btree::Btree_modified [mutable, protected] |
bool Btree::full_compaction [protected] |
set to true when full compaction is to be achieved
Definition at line 666 of file btree.h.
Referenced by add(), and set_full_compaction().
bool Btree::writable [protected] |
Set to true when the database is opened to write.
Definition at line 669 of file btree.h.
Referenced by add(), add_item(), add_item_to_block(), add_kt(), alter(), block_to_cursor(), cancel(), commit(), compact(), 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().
bool Btree::dont_close_handle [protected] |
bool(Btree::* Btree::prev_ptr)(Cursor *, int) const [protected] |
Referenced by cancel(), do_open_to_read(), and do_open_to_write().
bool(Btree::* Btree::next_ptr)(Cursor *, int) const [protected] |
Referenced by cancel(), do_open_to_read(), and do_open_to_write().
Definition at line 694 of file btree.h.
Referenced by add(), add_item(), add_kt(), alter(), Bcursor::Bcursor(), block_to_cursor(), cancel(), close(), commit(), delete_item(), delete_kt(), do_open_to_read(), do_open_to_write(), enter_key(), find_tag(), next_for_sequential(), prev_for_sequential(), read_root(), and split_root().
byte* Btree::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 Btree::add_item().
Definition at line 701 of file btree.h.
Referenced by add_item(), close(), and do_open_to_write().