1 /* brass_table.h: Btree implementation 2 * 3 * Copyright 1999,2000,2001 BrightStation PLC 4 * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010 Olly Betts 5 * Copyright 2008 Lemur Consulting Ltd 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License as 9 * published by the Free Software Foundation; either version 2 of the 10 * License, or (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 20 * USA 21 */ 22 23 #ifndef OM_HGUARD_BRASS_TABLE_H 24 #define OM_HGUARD_BRASS_TABLE_H 25 26 #include <xapian/error.h> 27 #include <xapian/visibility.h> 28 29 #include "brass_types.h" 30 #include "brass_btreebase.h" 31 #include "brass_cursor.h" 32 33 #include "noreturn.h" 34 #include "omassert.h" 35 #include "str.h" 36 #include "stringutils.h" 37 #include "unaligned.h" 38 39 #include <algorithm> 40 #include <string> 41 42 #include <zlib.h> 43 44 #define DONT_COMPRESS -1 45 46 /** Even for items of at maximum size, it must be possible to get this number of 47 * items in a block */ 48 #define BLOCK_CAPACITY 4 49 50 /** The largest possible value of a key_len. 51 * 52 * This gives the upper limit of the size of a key that may be stored in the 53 * B-tree (252 bytes with the present implementation). 54 */ 55 #define BRASS_BTREE_MAX_KEY_LEN 252 56 57 // FIXME: This named constant probably isn't used everywhere it should be... 58 #define BYTES_PER_BLOCK_NUMBER 4 59 60 /* The B-tree blocks have a number of internal lengths and offsets held in 1, 2 61 or 4 bytes. To make the coding a little clearer, 62 we use for 63 ------ --- 64 K1 the 1 byte length of key 65 I2 the 2 byte length of an item (key-tag pair) 66 D2 the 2 byte offset to the item from the directory 67 C2 the 2 byte counter that ends each key and begins each tag 68 */ 69 70 #define K1 1 71 #define I2 2 72 #define D2 2 73 #define C2 2 74 75 /* and when getting K1 or setting D2, we use getK, setD defined as: */ 76 77 #define getK(p, c) getint1(p, c) 78 #define setD(p, c, x) setint2(p, c, x) 79 80 /* if you've been reading the comments from the top, the next four procedures 81 will not cause any headaches. 82 83 Recall that item has this form: 84 85 i k 86 | | 87 I K key x C tag 88 <--K--> 89 <------I------> 90 91 92 item_of(p, c) returns i, the address of the item at block address p, 93 directory offset c, 94 95 component_of(p, c) returns the number marked 'x' above, 96 97 components_of(p, c) returns the number marked 'C' above, 98 */ 99 100 #define REVISION(b) static_cast<unsigned int>(getint4(b, 0)) 101 #define GET_LEVEL(b) getint1(b, 4) 102 #define MAX_FREE(b) getint2(b, 5) 103 #define TOTAL_FREE(b) getint2(b, 7) 104 #define DIR_END(b) getint2(b, 9) 105 #define DIR_START 11 106 107 #define SET_REVISION(b, x) setint4(b, 0, x) 108 #define SET_LEVEL(b, x) setint1(b, 4, x) 109 #define SET_MAX_FREE(b, x) setint2(b, 5, x) 110 #define SET_TOTAL_FREE(b, x) setint2(b, 7, x) 111 #define SET_DIR_END(b, x) setint2(b, 9, x) 112 113 namespace Brass { 114 115 class XAPIAN_VISIBILITY_DEFAULT Key { 116 const byte *p; 117 public: Key(const byte * p_)118 explicit Key(const byte * p_) : p(p_) { } get_address()119 const byte * get_address() const { return p; } read(std::string * key)120 void read(std::string * key) const { 121 key->assign(reinterpret_cast<const char *>(p + K1), length()); 122 } 123 bool operator==(Key key2) const; 124 bool operator!=(Key key2) const { return !(*this == key2); } 125 bool operator<(Key key2) const; 126 bool operator>=(Key key2) const { return !(*this < key2); } 127 bool operator>(Key key2) const { return key2 < *this; } 128 bool operator<=(Key key2) const { return !(key2 < *this); } length()129 int length() const { 130 AssertRel(getK(p, 0),>=,3); 131 return getK(p, 0) - C2 - K1; 132 } 133 char operator[](size_t i) const { 134 AssertRel(i,<,(size_t)length()); 135 return p[i + K1]; 136 } 137 }; 138 139 // Item_wr wants to be "Item with non-const p and more methods" - we can't 140 // achieve that nicely with inheritance, so we use a template base class. 141 template <class T> class Item_base { 142 protected: 143 T p; 144 public: 145 /* Item from block address and offset to item pointer */ Item_base(T p_,int c)146 Item_base(T p_, int c) : p(p_ + getint2(p_, c)) { } Item_base(T p_)147 Item_base(T p_) : p(p_) { } get_address()148 T get_address() const { return p; } 149 /** I in diagram above. */ size()150 int size() const { 151 int item_size = getint2(p, 0) & 0x7fff; 152 AssertRel(item_size,>=,5); 153 return item_size; 154 } get_compressed()155 bool get_compressed() const { return *p & 0x80; } component_of()156 int component_of() const { 157 return getint2(p, getK(p, I2) + I2 - C2); 158 } components_of()159 int components_of() const { 160 return getint2(p, getK(p, I2) + I2); 161 } key()162 Key key() const { return Key(p + I2); } append_chunk(std::string * tag)163 void append_chunk(std::string * tag) const { 164 /* number of bytes to extract from current component */ 165 int cd = getK(p, I2) + I2 + C2; 166 int l = size() - cd; 167 tag->append(reinterpret_cast<const char *>(p + cd), l); 168 } 169 /** Get this item's tag as a block number (this block should not be at 170 * level 0). 171 */ block_given_by()172 uint4 block_given_by() const { 173 AssertRel(size(),>=,BYTES_PER_BLOCK_NUMBER); 174 return getint4(p, size() - BYTES_PER_BLOCK_NUMBER); 175 } 176 }; 177 178 class Item : public Item_base<const byte *> { 179 public: 180 /* Item from block address and offset to item pointer */ Item(const byte * p_,int c)181 Item(const byte * p_, int c) : Item_base<const byte *>(p_, c) { } Item(const byte * p_)182 Item(const byte * p_) : Item_base<const byte *>(p_) { } 183 }; 184 185 class Item_wr : public Item_base<byte *> { set_key_len(int x)186 void set_key_len(int x) { setint1(p, I2, x); } 187 public: 188 /* Item_wr from block address and offset to item pointer */ Item_wr(byte * p_,int c)189 Item_wr(byte * p_, int c) : Item_base<byte *>(p_, c) { } Item_wr(byte * p_)190 Item_wr(byte * p_) : Item_base<byte *>(p_) { } set_component_of(int i)191 void set_component_of(int i) { 192 setint2(p, getK(p, I2) + I2 - C2, i); 193 } set_components_of(int m)194 void set_components_of(int m) { 195 setint2(p, getK(p, I2) + I2, m); 196 } 197 // Takes size as we may be truncating newkey. set_key_and_block(Key newkey,int truncate_size,uint4 n)198 void set_key_and_block(Key newkey, int truncate_size, uint4 n) { 199 int i = truncate_size; 200 // Read the length now because we may be copying the key over itself. 201 // FIXME that's stupid! sort this out 202 int newkey_len = newkey.length(); 203 AssertRel(i,<=,newkey_len); 204 int newsize = I2 + K1 + i + C2; 205 // Item size (BYTES_PER_BLOCK_NUMBER since tag contains block number) 206 setint2(p, 0, newsize + BYTES_PER_BLOCK_NUMBER); 207 // Key size 208 setint1(p, I2, newsize - I2); 209 // Copy the main part of the key, possibly truncating. 210 std::memmove(p + I2 + K1, newkey.get_address() + K1, i); 211 // Copy the count part. 212 std::memmove(p + I2 + K1 + i, newkey.get_address() + K1 + newkey_len, C2); 213 // Set tag contents to block number 214 // set_block_given_by(n); 215 setint4(p, newsize, n); 216 } 217 218 /** Set this item's tag to point to block n (this block should not be at 219 * level 0). 220 */ set_block_given_by(uint4 n)221 void set_block_given_by(uint4 n) { 222 setint4(p, size() - BYTES_PER_BLOCK_NUMBER, n); 223 } set_size(int l)224 void set_size(int l) { 225 AssertRel(l,>=,5); 226 setint2(p, 0, l); 227 } 228 /** Form an item with a null key and with block number n in the tag. 229 */ form_null_key(uint4 n)230 void form_null_key(uint4 n) { 231 setint4(p, I2 + K1, n); 232 set_key_len(K1); /* null key */ 233 set_size(I2 + K1 + BYTES_PER_BLOCK_NUMBER); /* total length */ 234 } form_key(const std::string & key_)235 void form_key(const std::string & key_) { 236 std::string::size_type key_len = key_.length(); 237 if (key_len > BRASS_BTREE_MAX_KEY_LEN) { 238 // We check term length when a term is added to a document but 239 // brass doubles zero bytes, so this can still happen for terms 240 // which contain one or more zero bytes. 241 std::string msg("Key too long: length was "); 242 msg += str(key_len); 243 msg += " bytes, maximum length of a key is " 244 STRINGIZE(BRASS_BTREE_MAX_KEY_LEN) " bytes"; 245 throw Xapian::InvalidArgumentError(msg); 246 } 247 248 set_key_len(key_len + K1 + C2); 249 std::memmove(p + I2 + K1, key_.data(), key_len); 250 set_component_of(1); 251 } 252 // FIXME passing cd here is icky set_tag(int cd,const char * start,int len,bool compressed)253 void set_tag(int cd, const char *start, int len, bool compressed) { 254 std::memmove(p + cd, start, len); 255 set_size(cd + len); 256 if (compressed) *p |= 0x80; 257 } fake_root_item()258 void fake_root_item() { 259 set_key_len(K1 + C2); // null key length 260 set_size(I2 + K1 + 2 * C2); // length of the item 261 set_component_of(1); 262 set_components_of(1); 263 } 264 }; 265 266 } 267 268 // Allow for BTREE_CURSOR_LEVELS levels in the B-tree. 269 // With 10, overflow is practically impossible 270 // FIXME: but we want it to be completely impossible... 271 #define BTREE_CURSOR_LEVELS 10 272 273 /** Class managing a Btree table in a Brass database. 274 * 275 * A table is a store holding a set of key/tag pairs. 276 * 277 * A key is used to access a block of data in a brass table. 278 * 279 * Keys are of limited length. 280 * 281 * Keys may not be empty (each Btree has a special empty key for internal use). 282 * 283 * A tag is a piece of data associated with a given key. The contents 284 * of the tag are opaque to the Btree. 285 * 286 * Tags may be of arbitrary length (the Btree imposes a very large limit). 287 * Note though that they will be loaded into memory in their entirety, so 288 * should not be permitted to grow without bound in normal usage. 289 * 290 * Tags which are null strings _are_ valid, and are different from a 291 * tag simply not being in the table. 292 */ 293 class XAPIAN_VISIBILITY_DEFAULT BrassTable { 294 friend class BrassCursor; /* Should probably fix this. */ 295 private: 296 /// Copying not allowed 297 BrassTable(const BrassTable &); 298 299 /// Assignment not allowed 300 BrassTable & operator=(const BrassTable &); 301 302 public: 303 /** Create a new Btree object. 304 * 305 * This does not create the table on disk - the create_and_open() 306 * method must be called to create the table on disk. 307 * 308 * This also does not open the table - either the create_and_open() 309 * or open() methods must be called before use is made of the table. 310 * 311 * @param tablename_ The name of the table (used in changesets). 312 * @param path_ Path at which the table is stored. 313 * @param readonly_ whether to open the table for read only access. 314 * @param compress_strategy_ DONT_COMPRESS, Z_DEFAULT_STRATEGY, 315 * Z_FILTERED, Z_HUFFMAN_ONLY, or Z_RLE. 316 * @param lazy If true, don't create the table until it's 317 * needed. 318 */ 319 BrassTable(const char * tablename_, const std::string & path_, 320 bool readonly_, int compress_strategy_ = DONT_COMPRESS, 321 bool lazy = false); 322 323 /** Close the Btree. 324 * 325 * Any outstanding changes (ie, changes made without commit() having 326 * subsequently been called) will be lost. 327 */ 328 ~BrassTable(); 329 330 /** Close the Btree. This closes and frees any of the btree 331 * structures which have been created and opened. 332 * 333 * @param permanent If true, the Btree will not reopen on demand. 334 */ 335 void close(bool permanent=false); 336 337 /** Determine whether the btree exists on disk. 338 */ 339 bool exists() const; 340 341 /** Open the btree at the latest revision. 342 * 343 * @exception Xapian::DatabaseCorruptError will be thrown if the table 344 * is in a corrupt state. 345 * @exception Xapian::DatabaseOpeningError will be thrown if the table 346 * cannot be opened (but is not corrupt - eg, permission problems, 347 * not present, etc). 348 */ 349 void open(); 350 351 /** Open the btree at a given revision. 352 * 353 * Like Btree::open, but try to open at the given revision number 354 * and fail if that isn't possible. 355 * 356 * @param revision_ - revision number to open. 357 * 358 * @return true if table is successfully opened at desired revision; 359 * false if table cannot be opened at desired revision (but 360 * table is otherwise consistent). 361 * 362 * @exception Xapian::DatabaseCorruptError will be thrown if the table 363 * is in a corrupt state. 364 * @exception Xapian::DatabaseOpeningError will be thrown if the table 365 * cannot be opened (but is not corrupt - eg, permission problems, 366 * not present, etc). 367 */ 368 bool open(brass_revision_number_t revision_); 369 370 /** Return true if this table is open. 371 * 372 * NB If the table is lazy and doesn't yet exist, returns false. 373 */ is_open()374 bool is_open() const { return handle >= 0; } 375 376 /** Flush any outstanding changes to the DB file of the table. 377 * 378 * This must be called before commit, to ensure that the DB file is 379 * ready to be switched to a new version by the commit. 380 */ 381 void flush_db(); 382 383 /** Commit any outstanding changes to the table. 384 * 385 * Commit changes made by calling add() and del() to the Btree. 386 * 387 * If an error occurs during the operation, this will be signalled 388 * by an exception. In case of error, changes made will not be 389 * committed to the Btree - they will be discarded. 390 * 391 * @param new_revision The new revision number to store. This must 392 * be greater than the latest revision number (see 393 * get_latest_revision_number()), or an exception will be 394 * thrown. 395 * 396 * @param changes_fd The file descriptor to write changes to. 397 * Defaults to -1, meaning no changes will be written. 398 */ 399 void commit(brass_revision_number_t revision, int changes_fd = -1, 400 const std::string * changes_tail = NULL); 401 402 /** Append the list of blocks changed to a changeset file. 403 * 404 * @param changes_fd The file descriptor to write changes to. 405 */ 406 void write_changed_blocks(int changes_fd); 407 408 /** Cancel any outstanding changes. 409 * 410 * This will discard any modifications which haven't been committed 411 * by calling commit(). 412 */ 413 void cancel(); 414 415 /** Read an entry from the table, if and only if it is exactly that 416 * being asked for. 417 * 418 * If the key is found in the table, then the tag is copied to @a 419 * tag. If the key is not found tag is left unchanged. 420 * 421 * The result is true iff the specified key is found in the Btree. 422 * 423 * @param key The key to look for in the table. 424 * @param tag A tag object to fill with the value if found. 425 * 426 * @return true if key is found in table, 427 * false if key is not found in table. 428 */ 429 bool get_exact_entry(const std::string & key, std::string & tag) const; 430 431 /** Check if a key exists in the Btree. 432 * 433 * This is just like get_exact_entry() except it doesn't read the tag 434 * value so is more efficient if you only want to check that the key 435 * exists. 436 * 437 * @param key The key to look for in the table. 438 * 439 * @return true if key is found in table, 440 * false if key is not found in table. 441 */ 442 bool key_exists(const std::string &key) const; 443 444 /** Read the tag value for the key pointed to by cursor C_. 445 * 446 * @param keep_compressed Don't uncompress the tag - e.g. useful 447 * if it's just being opaquely copied. 448 * 449 * @return true if current_tag holds compressed data (always 450 * false if keep_compressed was false). 451 */ 452 bool read_tag(Brass::Cursor * C_, std::string *tag, bool keep_compressed) const; 453 454 /** Add a key/tag pair to the table, replacing any existing pair with 455 * the same key. 456 * 457 * If an error occurs during the operation, an exception will be 458 * thrown. 459 * 460 * If key is empty, then the null item is replaced. 461 * 462 * e.g. btree.add("TODAY", "Mon 9 Oct 2000"); 463 * 464 * @param key The key to store in the table. 465 * @param tag The tag to store in the table. 466 * @param already_compressed true if tag is already compressed, 467 * for example because it is being opaquely copied 468 * (default: false). 469 */ 470 void add(const std::string &key, std::string tag, bool already_compressed = false); 471 472 /** Delete an entry from the table. 473 * 474 * The entry will be removed from the table, if it exists. If 475 * it does not exist, no action will be taken. The item with 476 * an empty key can't be removed, and false is returned. 477 * 478 * If an error occurs during the operation, this will be signalled 479 * by an exception. 480 * 481 * e.g. bool deleted = btree.del("TODAY") 482 * 483 * @param key The key to remove from the table. 484 * 485 * @return true if an entry was removed; false if it did not exist. 486 */ 487 bool del(const std::string &key); 488 489 /// Erase this table from disk. 490 void erase(); 491 492 /** Set the block size. 493 * 494 * It's only safe to do this before the table is created. 495 */ 496 void set_block_size(unsigned int block_size_); 497 498 /** Get the block size. 499 */ get_block_size()500 unsigned int get_block_size() const { return block_size; } 501 502 /** Create a new empty btree structure on disk and open it at the 503 * initial revision. 504 * 505 * The table must be writable - it doesn't make sense to create 506 * a table that is read-only! 507 * 508 * The block size must be less than 64K, where K = 1024. It is unwise 509 * to use a small block size (less than 1024 perhaps), so we enforce a 510 * minimum block size of 2K. 511 * 512 * Example: 513 * 514 * Btree btree("X-"); 515 * btree.create_and_open(8192); 516 * // Files will be X-DB, X-baseA (and X-baseB). 517 * 518 * @param blocksize - Size of blocks to use. 519 * 520 * @exception Xapian::DatabaseCreateError if the table can't be 521 * created. 522 * @exception Xapian::InvalidArgumentError if the requested blocksize 523 * is unsuitable. 524 */ 525 void create_and_open(unsigned int blocksize); 526 527 void set_full_compaction(bool parity); 528 529 /** Get the latest revision number stored in this table. 530 * 531 * This gives the higher of the revision numbers held in the base 532 * files of the B-tree, or just the revision number if there's only 533 * one base file. 534 * 535 * It is possible that there are other, older, revisions of this 536 * table available, and indeed that the revision currently open 537 * is one of these older revisions. 538 */ get_latest_revision_number()539 brass_revision_number_t get_latest_revision_number() const { 540 return latest_revision_number; 541 } 542 543 /** Get the revision number at which this table 544 * is currently open. 545 * 546 * It is possible that there are other, more recent or older 547 * revisions available. 548 * 549 * @return the current revision number. 550 */ get_open_revision_number()551 brass_revision_number_t get_open_revision_number() const { 552 return revision_number; 553 } 554 555 /** Return a count of the number of entries in the table. 556 * 557 * The count does not include the ever-present item with null key. 558 * 559 * Use @a empty() if you only want to know if the table is empty or 560 * not. 561 * 562 * @return The number of entries in the table. 563 */ get_entry_count()564 brass_tablesize_t get_entry_count() const { 565 return item_count; 566 } 567 568 /// Return true if there are no entries in the table. empty()569 bool empty() const { 570 return (item_count == 0); 571 } 572 573 /** Get a cursor for reading from the table. 574 * 575 * The cursor is owned by the caller - it is the caller's 576 * responsibility to ensure that it is deleted. 577 */ 578 BrassCursor * cursor_get() const; 579 580 /** Determine whether the object contains uncommitted modifications. 581 * 582 * @return true if there have been modifications since the last 583 * the last call to commit(). 584 */ is_modified()585 bool is_modified() const { return Btree_modified; } 586 587 /** Set the maximum item size given the block capacity. 588 * 589 * At least this many items of maximum size must fit into a block. 590 * The default is BLOCK_CAPACITY (which is currently 4). 591 */ set_max_item_size(size_t block_capacity)592 void set_max_item_size(size_t block_capacity) { 593 if (block_capacity > BLOCK_CAPACITY) block_capacity = BLOCK_CAPACITY; 594 max_item_size = (block_size - DIR_START - block_capacity * D2) 595 / block_capacity; 596 } 597 598 /// Throw an exception indicating that the database is closed. 599 XAPIAN_NORETURN(static void throw_database_closed()); 600 601 protected: 602 603 /** Perform the opening operation to read. 604 * 605 * Return true iff the open succeeded. 606 */ 607 bool do_open_to_read(bool revision_supplied, brass_revision_number_t revision_); 608 609 /** Perform the opening operation to write. 610 * 611 * Return true iff the open succeeded. 612 */ 613 bool do_open_to_write(bool revision_supplied, 614 brass_revision_number_t revision_, 615 bool create_db = false); 616 bool basic_open(bool revision_supplied, brass_revision_number_t revision); 617 618 bool find(Brass::Cursor *) const; 619 int delete_kt(); 620 void read_block(uint4 n, byte *p) const; 621 void write_block(uint4 n, const byte *p) const; 622 XAPIAN_NORETURN(void set_overwritten() const); 623 void block_to_cursor(Brass::Cursor *C_, int j, uint4 n) const; 624 void alter(); 625 void compact(byte *p); 626 void enter_key(int j, Brass::Key prevkey, Brass::Key newkey); 627 int mid_point(byte *p); 628 void add_item_to_block(byte *p, Brass::Item_wr kt, int c); 629 void add_item(Brass::Item_wr kt, int j); 630 void delete_item(int j, bool repeatedly); 631 int add_kt(bool found); 632 void read_root(); 633 void split_root(uint4 split_n); 634 void form_key(const std::string & key) const; 635 other_base_letter()636 char other_base_letter() const { 637 return (base_letter == 'A') ? 'B' : 'A'; 638 } 639 640 /// The name of the table (used when writing changesets). 641 const char * tablename; 642 643 /// Allocate the zstream for deflating, if not already allocated. 644 void lazy_alloc_deflate_zstream() const; 645 646 /// Allocate the zstream for inflating, if not already allocated. 647 void lazy_alloc_inflate_zstream() const; 648 649 /** revision number of the opened B-tree. */ 650 brass_revision_number_t revision_number; 651 652 /** keeps a count of the number of items in the B-tree. */ 653 brass_tablesize_t item_count; 654 655 /** block size of the B tree in bytes */ 656 unsigned int block_size; 657 658 /** Revision number of the other base, or zero if there is only one 659 * base file. 660 */ 661 mutable brass_revision_number_t latest_revision_number; 662 663 /** set to true if baseA and baseB both exist as valid bases. 664 * 665 * The unused base is deleted as soon as a write to the Btree takes 666 * place. */ 667 mutable bool both_bases; 668 669 /** the value 'A' or 'B' of the current base */ 670 char base_letter; 671 672 /** true if the root block is faked (not written to disk). 673 * false otherwise. This is true when the btree hasn't been 674 * modified yet. 675 */ 676 bool faked_root_block; 677 678 /** true iff the data has been written in a single write in 679 * sequential order. 680 */ 681 bool sequential; 682 683 /** File descriptor of the table. 684 * 685 * If the table is lazily created and doesn't yet exist, this will be 686 * -1. 687 * 688 * If close() has been called, this will be -2. 689 */ 690 int handle; 691 692 /// number of levels, counting from 0 693 int level; 694 695 /// the root block of the B-tree 696 uint4 root; 697 698 /// buffer of size block_size for making up key-tag items 699 mutable Brass::Item_wr kt; 700 701 /// buffer of size block_size for reforming blocks 702 byte * buffer; 703 704 /// For writing back as file baseA or baseB. 705 BrassTable_base base; 706 707 /// The path name of the B tree. 708 std::string name; 709 710 /** count of the number of successive instances of purely 711 * sequential addition, starting at SEQ_START_POINT (neg) and 712 * going up to zero. */ 713 int seq_count; 714 715 /** the last block to be changed by an addition */ 716 uint4 changed_n; 717 718 /** directory offset corresponding to last block to be changed 719 * by an addition */ 720 int changed_c; 721 722 /// maximum size of an item (key-tag pair) 723 size_t max_item_size; 724 725 /// Set to true the first time the B-tree is modified. 726 mutable bool Btree_modified; 727 728 /// set to true when full compaction is to be achieved 729 bool full_compaction; 730 731 /// Set to true when the database is opened to write. 732 bool writable; 733 734 /// Flag for tracking when cursors need to rebuild. 735 mutable bool cursor_created_since_last_modification; 736 737 /// Version count for tracking when cursors need to rebuild. 738 unsigned long cursor_version; 739 740 /* B-tree navigation functions */ prev(Brass::Cursor * C_,int j)741 bool prev(Brass::Cursor *C_, int j) const { 742 if (sequential) return prev_for_sequential(C_, j); 743 return prev_default(C_, j); 744 } 745 next(Brass::Cursor * C_,int j)746 bool next(Brass::Cursor *C_, int j) const { 747 if (sequential) return next_for_sequential(C_, j); 748 return next_default(C_, j); 749 } 750 751 /* Default implementations. */ 752 bool prev_default(Brass::Cursor *C_, int j) const; 753 bool next_default(Brass::Cursor *C_, int j) const; 754 755 /* Implementations for sequential mode. */ 756 bool prev_for_sequential(Brass::Cursor *C_, int dummy) const; 757 bool next_for_sequential(Brass::Cursor *C_, int dummy) const; 758 759 static int find_in_block(const byte * p, Brass::Key key, bool leaf, int c); 760 761 /** block_given_by(p, c) finds the item at block address p, directory 762 * offset c, and returns its tag value as an integer. 763 */ 764 static uint4 block_given_by(const byte * p, int c); 765 766 mutable Brass::Cursor C[BTREE_CURSOR_LEVELS]; 767 768 /** Buffer used when splitting a block. 769 * 770 * This buffer holds the split off part of the block. It's only used 771 * when updating (in BrassTable::add_item(). 772 */ 773 byte * split_p; 774 775 /** DONT_COMPRESS or Z_DEFAULT_STRATEGY, Z_FILTERED, Z_HUFFMAN_ONLY, 776 * Z_RLE. */ 777 int compress_strategy; 778 779 /// Zlib state object for deflating 780 mutable z_stream *deflate_zstream; 781 782 /// Zlib state object for inflating 783 mutable z_stream *inflate_zstream; 784 785 /// If true, don't create the table until it's needed. 786 bool lazy; 787 788 /* Debugging methods */ 789 // void report_block_full(int m, int n, const byte * p); 790 }; 791 792 #endif /* OM_HGUARD_BRASS_TABLE_H */ 793