1 /** @file chert_table.h
2 * @brief Btree implementation
4 /* Copyright 1999,2000,2001 BrightStation PLC
5 * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010,2012,2015,2016 Olly Betts
6 * Copyright 2008 Lemur Consulting Ltd
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License as
10 * published by the Free Software Foundation; either version 2 of the
11 * License, or (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
24 #ifndef OM_HGUARD_CHERT_TABLE_H
25 #define OM_HGUARD_CHERT_TABLE_H
27 #include <xapian/error.h>
29 #include "chert_types.h"
30 #include "chert_btreebase.h"
31 #include "chert_cursor.h"
36 #include "stringutils.h"
37 #include "wordaccess.h"
44 // FIXME: 65536 in Asserts below is the max chert block size. We should
45 // abstract this out, and use the current block_size to catch overruns better.
47 getint1(const unsigned char *p
, int c
)
50 AssertRel(c
, <, 65536);
55 setint1(unsigned char *p
, int c
, int x
)
58 AssertRel(c
, <, 65536);
63 getint2(const unsigned char *p
, int c
)
66 AssertRel(c
, <, 65536 - 1);
67 return unaligned_read2(p
+ c
);
71 setint2(unsigned char *p
, int c
, int x
)
74 AssertRel(c
, <, 65536 - 1);
75 unaligned_write2(p
+ c
, uint16_t(x
));
79 getint4(const unsigned char *p
, int c
)
82 AssertRel(c
, <, 65536 - 3);
83 return unaligned_read4(p
+ c
);
87 setint4(unsigned char *p
, int c
, int x
)
90 AssertRel(c
, <, 65536 - 3);
91 unaligned_write4(p
+ c
, uint32_t(x
));
94 const int DONT_COMPRESS
= -1;
96 /** The largest possible value of a key_len.
98 * This gives the upper limit of the size of a key that may be stored in the
99 * B-tree (252 bytes with the present implementation).
101 #define CHERT_BTREE_MAX_KEY_LEN 252
103 /** Even for items of at maximum size, it must be possible to get this number of
104 * items in a block */
105 const size_t BLOCK_CAPACITY
= 4;
107 // FIXME: This named constant probably isn't used everywhere it should be...
108 const int BYTES_PER_BLOCK_NUMBER
= 4;
110 /* The B-tree blocks have a number of internal lengths and offsets held in 1, 2
111 or 4 bytes. To make the coding a little clearer,
114 K1 the 1 byte length of key
115 I2 the 2 byte length of an item (key-tag pair)
116 D2 the 2 byte offset to the item from the directory
117 C2 the 2 byte counter that ends each key and begins each tag
125 /* and when getting K1 or setting D2, we use getK, setD defined as: */
127 inline int getK(const unsigned char *p
, int c
) { return getint1(p
, c
); }
128 inline void setD(unsigned char *p
, int c
, int x
) { setint2(p
, c
, x
); }
130 /* if you've been reading the comments from the top, the next four procedures
131 will not cause any headaches.
133 Recall that item has this form:
142 item_of(p, c) returns i, the address of the item at block address p,
145 component_of(p, c) returns the number marked 'x' above,
147 components_of(p, c) returns the number marked 'C' above,
150 inline unsigned REVISION(const byte
* b
) { return aligned_read4(b
); }
151 inline int GET_LEVEL(const byte
* b
) { return getint1(b
, 4); }
152 inline int MAX_FREE(const byte
* b
) { return getint2(b
, 5); }
153 inline int TOTAL_FREE(const byte
* b
) { return getint2(b
, 7); }
154 inline int DIR_END(const byte
* b
) { return getint2(b
, 9); }
155 const int DIR_START
= 11;
157 inline void SET_REVISION(byte
* b
, uint4 rev
) { aligned_write4(b
, rev
); }
158 inline void SET_LEVEL(byte
* b
, int x
) { setint1(b
, 4, x
); }
159 inline void SET_MAX_FREE(byte
* b
, int x
) { setint2(b
, 5, x
); }
160 inline void SET_TOTAL_FREE(byte
* b
, int x
) { setint2(b
, 7, x
); }
161 inline void SET_DIR_END(byte
* b
, int x
) { setint2(b
, 9, x
); }
163 // The item size is stored in 2 bytes, but the top bit is used to store a flag
164 // for "is the tag data compressed".
165 const size_t CHERT_MAX_ITEM_SIZE
= 0x7fff;
170 explicit Key(const byte
* p_
) : p(p_
) { }
171 const byte
* get_address() const { return p
; }
172 void read(std::string
* key
) const {
173 key
->assign(reinterpret_cast<const char *>(p
+ K1
), length());
175 bool operator==(Key key2
) const;
176 bool operator!=(Key key2
) const { return !(*this == key2
); }
177 bool operator<(Key key2
) const;
178 bool operator>=(Key key2
) const { return !(*this < key2
); }
179 bool operator>(Key key2
) const { return key2
< *this; }
180 bool operator<=(Key key2
) const { return !(key2
< *this); }
182 AssertRel(getK(p
, 0),>=,3);
183 return getK(p
, 0) - C2
- K1
;
185 char operator[](size_t i
) const {
186 AssertRel(i
,<,(size_t)length());
191 // Item_wr wants to be "Item with non-const p and more methods" - we can't
192 // achieve that nicely with inheritance, so we use a template base class.
193 template <class T
> class Item_base
{
197 /* Item from block address and offset to item pointer */
198 Item_base(T p_
, int c
) : p(p_
+ getint2(p_
, c
)) { }
199 Item_base(T p_
) : p(p_
) { }
200 T
get_address() const { return p
; }
201 /** I in diagram above. */
203 int item_size
= getint2(p
, 0) & CHERT_MAX_ITEM_SIZE
;
204 AssertRel(item_size
,>=,5);
207 bool get_compressed() const { return *p
& 0x80; }
208 int component_of() const {
209 return getint2(p
, getK(p
, I2
) + I2
- C2
);
211 int components_of() const {
212 return getint2(p
, getK(p
, I2
) + I2
);
214 Key
key() const { return Key(p
+ I2
); }
215 void append_chunk(std::string
* tag
) const {
216 /* number of bytes to extract from current component */
217 int cd
= getK(p
, I2
) + I2
+ C2
;
219 tag
->append(reinterpret_cast<const char *>(p
+ cd
), l
);
221 /** Get this item's tag as a block number (this block should not be at
224 uint4
block_given_by() const {
225 AssertRel(size(),>=,BYTES_PER_BLOCK_NUMBER
);
226 return getint4(p
, size() - BYTES_PER_BLOCK_NUMBER
);
230 class Item
: public Item_base
<const byte
*> {
232 /* Item from block address and offset to item pointer */
233 Item(const byte
* p_
, int c
) : Item_base
<const byte
*>(p_
, c
) { }
234 Item(const byte
* p_
) : Item_base
<const byte
*>(p_
) { }
237 class Item_wr
: public Item_base
<byte
*> {
238 void set_key_len(int x
) { setint1(p
, I2
, x
); }
240 /* Item_wr from block address and offset to item pointer */
241 Item_wr(byte
* p_
, int c
) : Item_base
<byte
*>(p_
, c
) { }
242 Item_wr(byte
* p_
) : Item_base
<byte
*>(p_
) { }
243 void set_component_of(int i
) {
244 setint2(p
, getK(p
, I2
) + I2
- C2
, i
);
246 void set_components_of(int m
) {
247 setint2(p
, getK(p
, I2
) + I2
, m
);
249 // Takes size as we may be truncating newkey.
250 void set_key_and_block(Key newkey
, int truncate_size
, uint4 n
) {
251 int i
= truncate_size
;
252 // Read the length now because we may be copying the key over itself.
253 // FIXME that's stupid! sort this out
254 int newkey_len
= newkey
.length();
255 AssertRel(i
,<=,newkey_len
);
256 int newsize
= I2
+ K1
+ i
+ C2
;
257 // Item size (BYTES_PER_BLOCK_NUMBER since tag contains block number)
258 setint2(p
, 0, newsize
+ BYTES_PER_BLOCK_NUMBER
);
260 setint1(p
, I2
, newsize
- I2
);
261 // Copy the main part of the key, possibly truncating.
262 std::memmove(p
+ I2
+ K1
, newkey
.get_address() + K1
, i
);
263 // Copy the count part.
264 std::memmove(p
+ I2
+ K1
+ i
, newkey
.get_address() + K1
+ newkey_len
, C2
);
265 // Set tag contents to block number
266 // set_block_given_by(n);
267 setint4(p
, newsize
, n
);
270 /** Set this item's tag to point to block n (this block should not be at
273 void set_block_given_by(uint4 n
) {
274 setint4(p
, size() - BYTES_PER_BLOCK_NUMBER
, n
);
276 void set_size(int l
) {
278 // We should never be able to pass too large a size here, but don't
279 // corrupt the database if this somehow happens.
280 if (rare(l
&~ CHERT_MAX_ITEM_SIZE
))
281 throw Xapian::DatabaseError("item too large!");
284 /** Form an item with a null key and with block number n in the tag.
286 void form_null_key(uint4 n
) {
287 setint4(p
, I2
+ K1
, n
);
288 set_key_len(K1
); /* null key */
289 set_size(I2
+ K1
+ BYTES_PER_BLOCK_NUMBER
); /* total length */
291 void form_key(const std::string
& key_
) {
292 std::string::size_type key_len
= key_
.length();
293 if (key_len
> CHERT_BTREE_MAX_KEY_LEN
) {
294 // We check term length when a term is added to a document but
295 // chert doubles zero bytes, so this can still happen for terms
296 // which contain one or more zero bytes.
297 std::string
msg("Key too long: length was ");
299 msg
+= " bytes, maximum length of a key is "
300 STRINGIZE(CHERT_BTREE_MAX_KEY_LEN
) " bytes";
301 throw Xapian::InvalidArgumentError(msg
);
304 set_key_len(key_len
+ K1
+ C2
);
305 std::memmove(p
+ I2
+ K1
, key_
.data(), key_len
);
308 // FIXME passing cd here is icky
309 void set_tag(int cd
, const char *start
, int len
, bool compressed
) {
310 std::memmove(p
+ cd
, start
, len
);
312 if (compressed
) *p
|= 0x80;
314 void fake_root_item() {
315 set_key_len(K1
+ C2
); // null key length
316 set_size(I2
+ K1
+ 2 * C2
); // length of the item
318 set_components_of(1);
322 // Allow for BTREE_CURSOR_LEVELS levels in the B-tree.
323 // With 10, overflow is practically impossible
324 // FIXME: but we want it to be completely impossible...
325 const int BTREE_CURSOR_LEVELS
= 10;
327 /** Class managing a Btree table in a Chert database.
329 * A table is a store holding a set of key/tag pairs.
331 * A key is used to access a block of data in a chert table.
333 * Keys are of limited length.
335 * Keys may not be empty (each Btree has a special empty key for internal use).
337 * A tag is a piece of data associated with a given key. The contents
338 * of the tag are opaque to the Btree.
340 * Tags may be of arbitrary length (the Btree imposes a very large limit).
341 * Note though that they will be loaded into memory in their entirety, so
342 * should not be permitted to grow without bound in normal usage.
344 * Tags which are null strings _are_ valid, and are different from a
345 * tag simply not being in the table.
348 friend class ChertCursor
; /* Should probably fix this. */
350 /// Copying not allowed
351 ChertTable(const ChertTable
&);
353 /// Assignment not allowed
354 ChertTable
& operator=(const ChertTable
&);
356 /// Return true if there are no entries in the table.
357 bool really_empty() const;
360 /** Create a new Btree object.
362 * This does not create the table on disk - the create_and_open()
363 * method must be called to create the table on disk.
365 * This also does not open the table - either the create_and_open()
366 * or open() methods must be called before use is made of the table.
368 * @param tablename_ The name of the table (used in changesets).
369 * @param path_ Path at which the table is stored.
370 * @param readonly_ whether to open the table for read only access.
371 * @param compress_strategy_ DONT_COMPRESS, Z_DEFAULT_STRATEGY,
372 * Z_FILTERED, Z_HUFFMAN_ONLY, or Z_RLE.
373 * @param lazy If true, don't create the table until it's
376 ChertTable(const char * tablename_
, const std::string
& path_
,
377 bool readonly_
, int compress_strategy_
= DONT_COMPRESS
,
382 * Any outstanding changes (ie, changes made without commit() having
383 * subsequently been called) will be lost.
387 /** Close the Btree. This closes and frees any of the btree
388 * structures which have been created and opened.
390 * @param permanent If true, the Btree will not reopen on demand.
392 void close(bool permanent
= false);
394 bool readahead_key(const string
&key
) const;
396 /** Determine whether the btree exists on disk.
400 /** Open the btree at the latest revision.
402 * @exception Xapian::DatabaseCorruptError will be thrown if the table
403 * is in a corrupt state.
404 * @exception Xapian::DatabaseOpeningError will be thrown if the table
405 * cannot be opened (but is not corrupt - eg, permission problems,
410 /** Open the btree at a given revision.
412 * Like Btree::open, but try to open at the given revision number
413 * and fail if that isn't possible.
415 * @param revision_ - revision number to open.
417 * @return true if table is successfully opened at desired revision;
418 * false if table cannot be opened at desired revision (but
419 * table is otherwise consistent).
421 * @exception Xapian::DatabaseCorruptError will be thrown if the table
422 * is in a corrupt state.
423 * @exception Xapian::DatabaseOpeningError will be thrown if the table
424 * cannot be opened (but is not corrupt - eg, permission problems,
427 bool open(chert_revision_number_t revision_
);
429 /** Return true if this table is open.
431 * NB If the table is lazy and doesn't yet exist, returns false.
433 bool is_open() const { return handle
>= 0; }
435 /** Flush any outstanding changes to the DB file of the table.
437 * This must be called before commit, to ensure that the DB file is
438 * ready to be switched to a new version by the commit.
442 /** Commit any outstanding changes to the table.
444 * Commit changes made by calling add() and del() to the Btree.
446 * If an error occurs during the operation, this will be signalled
447 * by an exception. In case of error, changes made will not be
448 * committed to the Btree - they will be discarded.
450 * @param new_revision The new revision number to store. This must
451 * be greater than the latest revision number (see
452 * get_latest_revision_number()), or an exception will be
455 * @param changes_fd The file descriptor to write changes to.
456 * Defaults to -1, meaning no changes will be written.
458 void commit(chert_revision_number_t revision
, int changes_fd
= -1,
459 const std::string
* changes_tail
= NULL
);
461 /** Append the list of blocks changed to a changeset file.
463 * @param changes_fd The file descriptor to write changes to.
465 void write_changed_blocks(int changes_fd
);
467 /** Cancel any outstanding changes.
469 * This will discard any modifications which haven't been committed
470 * by calling commit().
474 /** Read an entry from the table, if and only if it is exactly that
477 * If the key is found in the table, then the tag is copied to @a
478 * tag. If the key is not found tag is left unchanged.
480 * The result is true iff the specified key is found in the Btree.
482 * @param key The key to look for in the table.
483 * @param tag A tag object to fill with the value if found.
485 * @return true if key is found in table,
486 * false if key is not found in table.
488 bool get_exact_entry(const std::string
& key
, std::string
& tag
) const;
490 /** Check if a key exists in the Btree.
492 * This is just like get_exact_entry() except it doesn't read the tag
493 * value so is more efficient if you only want to check that the key
496 * @param key The key to look for in the table.
498 * @return true if key is found in table,
499 * false if key is not found in table.
501 bool key_exists(const std::string
&key
) const;
503 /** Read the tag value for the key pointed to by cursor C_.
505 * @param keep_compressed Don't uncompress the tag - e.g. useful
506 * if it's just being opaquely copied.
508 * @return true if current_tag holds compressed data (always
509 * false if keep_compressed was false).
511 bool read_tag(Cursor
* C_
, std::string
*tag
, bool keep_compressed
) const;
513 /** Add a key/tag pair to the table, replacing any existing pair with
516 * If an error occurs during the operation, an exception will be
519 * If key is empty, then the null item is replaced.
521 * e.g. btree.add("TODAY", "Mon 9 Oct 2000");
523 * @param key The key to store in the table.
524 * @param tag The tag to store in the table.
525 * @param already_compressed true if tag is already compressed,
526 * for example because it is being opaquely copied
529 void add(const std::string
&key
, std::string tag
, bool already_compressed
= false);
531 /** Delete an entry from the table.
533 * The entry will be removed from the table, if it exists. If
534 * it does not exist, no action will be taken. The item with
535 * an empty key can't be removed, and false is returned.
537 * If an error occurs during the operation, this will be signalled
540 * e.g. bool deleted = btree.del("TODAY")
542 * @param key The key to remove from the table.
544 * @return true if an entry was removed; false if it did not exist.
546 bool del(const std::string
&key
);
548 /// Erase this table from disk.
551 /** Set the block size.
553 * It's only safe to do this before the table is created.
555 void set_block_size(unsigned int block_size_
);
557 /** Get the block size.
559 unsigned int get_block_size() const { return block_size
; }
561 /** Create a new empty btree structure on disk and open it at the
564 * The table must be writable - it doesn't make sense to create
565 * a table that is read-only!
567 * The block size must be less than 64K, where K = 1024. It is unwise
568 * to use a small block size (less than 1024 perhaps), so we enforce a
569 * minimum block size of 2K.
574 * btree.create_and_open(8192);
575 * // Files will be X-DB, X-baseA (and X-baseB).
577 * @param blocksize - Size of blocks to use.
579 * @exception Xapian::DatabaseCreateError if the table can't be
581 * @exception Xapian::InvalidArgumentError if the requested blocksize
584 void create_and_open(unsigned int blocksize
);
586 void set_full_compaction(bool parity
);
588 /** Get the latest revision number stored in this table.
590 * This gives the higher of the revision numbers held in the base
591 * files of the B-tree, or just the revision number if there's only
594 * It is possible that there are other, older, revisions of this
595 * table available, and indeed that the revision currently open
596 * is one of these older revisions.
598 chert_revision_number_t
get_latest_revision_number() const {
599 return latest_revision_number
;
602 /** Get the revision number at which this table
605 * It is possible that there are other, more recent or older
606 * revisions available.
608 * @return the current revision number.
610 chert_revision_number_t
get_open_revision_number() const {
611 return revision_number
;
614 /** Return a count of the number of entries in the table.
616 * The count does not include the ever-present item with null key.
618 * Use @a empty() if you only want to know if the table is empty or
621 * @return The number of entries in the table.
623 chert_tablesize_t
get_entry_count() const {
627 /// Return true if there are no entries in the table.
629 // Prior to 1.1.4/1.0.18, item_count was stored in 32 bits, so we
630 // can't trust it as there could be more than 1<<32 entries.
632 // In theory it should wrap, so if non-zero the table isn't empty,
633 // but the table this was first noticed in wasn't off by a multiple
636 // An empty table will always have level == 0, and most non-empty
637 // tables will have more levels, so use that as a short-cut.
638 return (level
== 0) && really_empty();
641 /** Get a cursor for reading from the table.
643 * The cursor is owned by the caller - it is the caller's
644 * responsibility to ensure that it is deleted.
646 ChertCursor
* cursor_get() const;
648 /** Determine whether the object contains uncommitted modifications.
650 * @return true if there have been modifications since the last
651 * the last call to commit().
653 bool is_modified() const { return Btree_modified
; }
655 /** Set the maximum item size given the block capacity.
657 * At least this many items of maximum size must fit into a block.
658 * The default is BLOCK_CAPACITY (which is currently 4).
660 void set_max_item_size(size_t block_capacity
) {
661 if (block_capacity
> BLOCK_CAPACITY
) block_capacity
= BLOCK_CAPACITY
;
662 max_item_size
= (block_size
- DIR_START
- block_capacity
* D2
)
664 // Make sure we don't exceed the limit imposed by the format.
665 if (max_item_size
> CHERT_MAX_ITEM_SIZE
)
666 max_item_size
= CHERT_MAX_ITEM_SIZE
;
669 /// Throw an exception indicating that the database is closed.
670 XAPIAN_NORETURN(static void throw_database_closed());
672 string
get_path() const {
678 /** Perform the opening operation to read.
680 * Return true iff the open succeeded.
682 bool do_open_to_read(bool revision_supplied
, chert_revision_number_t revision_
);
684 /** Perform the opening operation to write.
686 * Return true iff the open succeeded.
688 bool do_open_to_write(bool revision_supplied
,
689 chert_revision_number_t revision_
,
690 bool create_db
= false);
691 bool basic_open(bool revision_supplied
, chert_revision_number_t revision
);
693 bool find(Cursor
*) const;
695 void read_block(uint4 n
, byte
*p
) const;
696 void write_block(uint4 n
, const byte
*p
) const;
697 XAPIAN_NORETURN(void set_overwritten() const);
698 void block_to_cursor(Cursor
*C_
, int j
, uint4 n
) const;
700 void compact(byte
*p
);
701 void enter_key(int j
, Key prevkey
, Key newkey
);
702 int mid_point(byte
*p
);
703 void add_item_to_block(byte
*p
, Item_wr kt
, int c
);
704 void add_item(Item_wr kt
, int j
);
705 void delete_item(int j
, bool repeatedly
);
706 int add_kt(bool found
);
708 void split_root(uint4 split_n
);
709 void form_key(const std::string
& key
) const;
711 char other_base_letter() const {
712 return (base_letter
== 'A') ? 'B' : 'A';
715 /// The name of the table (used when writing changesets).
716 const char * tablename
;
718 /// Allocate the zstream for deflating, if not already allocated.
719 void lazy_alloc_deflate_zstream() const;
721 /// Allocate the zstream for inflating, if not already allocated.
722 void lazy_alloc_inflate_zstream() const;
724 /** revision number of the opened B-tree. */
725 chert_revision_number_t revision_number
;
727 /** keeps a count of the number of items in the B-tree. */
728 chert_tablesize_t item_count
;
730 /** block size of the B tree in bytes */
731 unsigned int block_size
;
733 /** Revision number of the other base, or zero if there is only one
736 mutable chert_revision_number_t latest_revision_number
;
738 /** set to true if baseA and baseB both exist as valid bases.
740 * The unused base is deleted as soon as a write to the Btree takes
742 mutable bool both_bases
;
744 /** the value 'A' or 'B' of the current base */
747 /** true if the root block is faked (not written to disk).
748 * false otherwise. This is true when the btree hasn't been
751 bool faked_root_block
;
753 /** true iff the data has been written in a single write in
758 /** File descriptor of the table.
760 * If the table is lazily created and doesn't yet exist, this will be
763 * If close() has been called, this will be -2.
767 /// number of levels, counting from 0
770 /// the root block of the B-tree
773 /// buffer of size block_size for making up key-tag items
776 /// buffer of size block_size for reforming blocks
779 /// For writing back as file baseA or baseB.
780 ChertTable_base base
;
782 /// The path name of the B tree.
785 /** count of the number of successive instances of purely
786 * sequential addition, starting at SEQ_START_POINT (neg) and
787 * going up to zero. */
790 /** the last block to be changed by an addition */
793 /** directory offset corresponding to last block to be changed
797 /// maximum size of an item (key-tag pair)
798 size_t max_item_size
;
800 /// Set to true the first time the B-tree is modified.
801 mutable bool Btree_modified
;
803 /// set to true when full compaction is to be achieved
804 bool full_compaction
;
806 /// Set to true when the database is opened to write.
809 /// Flag for tracking when cursors need to rebuild.
810 mutable bool cursor_created_since_last_modification
;
812 /// Version count for tracking when cursors need to rebuild.
813 unsigned long cursor_version
;
815 /* B-tree navigation functions */
816 bool prev(Cursor
*C_
, int j
) const {
817 if (sequential
) return prev_for_sequential(C_
, j
);
818 return prev_default(C_
, j
);
821 bool next(Cursor
*C_
, int j
) const {
822 if (sequential
) return next_for_sequential(C_
, j
);
823 return next_default(C_
, j
);
826 /* Default implementations. */
827 bool prev_default(Cursor
*C_
, int j
) const;
828 bool next_default(Cursor
*C_
, int j
) const;
830 /* Implementations for sequential mode. */
831 bool prev_for_sequential(Cursor
*C_
, int dummy
) const;
832 bool next_for_sequential(Cursor
*C_
, int dummy
) const;
834 static int find_in_block(const byte
* p
, Key key
, bool leaf
, int c
);
836 /** block_given_by(p, c) finds the item at block address p, directory
837 * offset c, and returns its tag value as an integer.
839 static uint4
block_given_by(const byte
* p
, int c
);
841 mutable Cursor C
[BTREE_CURSOR_LEVELS
];
843 /** Buffer used when splitting a block.
845 * This buffer holds the split off part of the block. It's only used
846 * when updating (in ChertTable::add_item().
850 /** DONT_COMPRESS or Z_DEFAULT_STRATEGY, Z_FILTERED, Z_HUFFMAN_ONLY,
852 int compress_strategy
;
854 /// Zlib state object for deflating
855 mutable z_stream
*deflate_zstream
;
857 /// Zlib state object for inflating
858 mutable z_stream
*inflate_zstream
;
860 /// If true, don't create the table until it's needed.
863 /// Last block readahead_key() preread.
864 mutable uint4 last_readahead
;
866 /* Debugging methods */
867 // void report_block_full(int m, int n, const byte * p);
870 #endif /* OM_HGUARD_CHERT_TABLE_H */