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