Branch data Line data Source code
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:
118 : 50934082 : explicit Key(const byte * p_) : p(p_) { }
119 : 33698 : const byte * get_address() const { return p; }
120 : 2099153 : void read(std::string * key) const {
121 : 2099153 : key->assign(reinterpret_cast<const char *>(p + K1), length());
122 : 2099153 : }
123 : : bool operator==(Key key2) const;
124 : : bool operator!=(Key key2) const { return !(*this == key2); }
125 : : bool operator<(Key key2) const;
126 : 1 : bool operator>=(Key key2) const { return !(*this < key2); }
127 : : bool operator>(Key key2) const { return key2 < *this; }
128 : 5657106 : bool operator<=(Key key2) const { return !(key2 < *this); }
129 : 89284978 : int length() const {
130 : : AssertRel(getK(p, 0),>=,3);
131 : 89284978 : return getK(p, 0) - C2 - K1;
132 : : }
133 : 172688 : char operator[](size_t i) const {
134 : : AssertRel(i,<,(size_t)length());
135 : 172688 : 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 */
146 : 69579130 : Item_base(T p_, int c) : p(p_ + getint2(p_, c)) { }
147 : 69707 : Item_base(T p_) : p(p_) { }
148 : 3140238 : T get_address() const { return p; }
149 : : /** I in diagram above. */
150 : 21308897 : int size() const {
151 : 21308897 : int item_size = getint2(p, 0) & 0x7fff;
152 : : AssertRel(item_size,>=,5);
153 : 21308897 : return item_size;
154 : : }
155 : 2681462 : bool get_compressed() const { return *p & 0x80; }
156 : 5916932 : int component_of() const {
157 : 5916932 : return getint2(p, getK(p, I2) + I2 - C2);
158 : : }
159 : 2766479 : int components_of() const {
160 : 2766479 : return getint2(p, getK(p, I2) + I2);
161 : : }
162 : 50934082 : Key key() const { return Key(p + I2); }
163 : 6948760 : void append_chunk(std::string * tag) const {
164 : : /* number of bytes to extract from current component */
165 : 6948760 : int cd = getK(p, I2) + I2 + C2;
166 : 6948760 : int l = size() - cd;
167 : 6948760 : tag->append(reinterpret_cast<const char *>(p + cd), l);
168 : 6948760 : }
169 : : /** Get this item's tag as a block number (this block should not be at
170 : : * level 0).
171 : : */
172 : 9512824 : uint4 block_given_by() const {
173 : : AssertRel(size(),>=,BYTES_PER_BLOCK_NUMBER);
174 : 9512824 : 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 */
181 : 69578236 : Item(const byte * p_, int c) : Item_base<const byte *>(p_, c) { }
182 : : Item(const byte * p_) : Item_base<const byte *>(p_) { }
183 : : };
184 : :
185 : : class Item_wr : public Item_base<byte *> {
186 : 4535603 : void set_key_len(int x) { setint1(p, I2, x); }
187 : : public:
188 : : /* Item_wr from block address and offset to item pointer */
189 : 894 : Item_wr(byte * p_, int c) : Item_base<byte *>(p_, c) { }
190 : 69707 : Item_wr(byte * p_) : Item_base<byte *>(p_) { }
191 : 5895674 : void set_component_of(int i) {
192 : 5895674 : setint2(p, getK(p, I2) + I2 - C2, i);
193 : 5895674 : }
194 : 1354656 : void set_components_of(int m) {
195 : 1354656 : setint2(p, getK(p, I2) + I2, m);
196 : 1354656 : }
197 : : // Takes size as we may be truncating newkey.
198 : 16725 : void set_key_and_block(Key newkey, int truncate_size, uint4 n) {
199 : 16725 : 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 : 16725 : int newkey_len = newkey.length();
203 : : AssertRel(i,<=,newkey_len);
204 : 16725 : int newsize = I2 + K1 + i + C2;
205 : : // Item size (BYTES_PER_BLOCK_NUMBER since tag contains block number)
206 : 16725 : setint2(p, 0, newsize + BYTES_PER_BLOCK_NUMBER);
207 : : // Key size
208 : 16725 : setint1(p, I2, newsize - I2);
209 : : // Copy the main part of the key, possibly truncating.
210 : 16725 : std::memmove(p + I2 + K1, newkey.get_address() + K1, i);
211 : : // Copy the count part.
212 : 16725 : 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 : 16725 : setint4(p, newsize, n);
216 : 16725 : }
217 : :
218 : : /** Set this item's tag to point to block n (this block should not be at
219 : : * level 0).
220 : : */
221 : 894 : void set_block_given_by(uint4 n) {
222 : 894 : setint4(p, size() - BYTES_PER_BLOCK_NUMBER, n);
223 : 894 : }
224 : 1363324 : void set_size(int l) {
225 : : AssertRel(l,>=,5);
226 : 1363324 : setint2(p, 0, l);
227 : 1363324 : }
228 : : /** Form an item with a null key and with block number n in the tag.
229 : : */
230 : 330 : void form_null_key(uint4 n) {
231 : 330 : setint4(p, I2 + K1, n);
232 : 330 : set_key_len(K1); /* null key */
233 : 330 : set_size(I2 + K1 + BYTES_PER_BLOCK_NUMBER); /* total length */
234 : 330 : }
235 : 4532321 : void form_key(const std::string & key_) {
236 : 4532321 : std::string::size_type key_len = key_.length();
237 [ + + ]: 4532321 : 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 : 8 : std::string msg("Key too long: length was ");
242 : 8 : msg += str(key_len);
243 : : msg += " bytes, maximum length of a key is "
244 : 8 : STRINGIZE(BRASS_BTREE_MAX_KEY_LEN) " bytes";
245 : 16 : throw Xapian::InvalidArgumentError(msg);
246 : : }
247 : :
248 : 4532313 : set_key_len(key_len + K1 + C2);
249 : 4532313 : std::memmove(p + I2 + K1, key_.data(), key_len);
250 : 4532313 : set_component_of(1);
251 : 4532313 : }
252 : : // FIXME passing cd here is icky
253 : 1360034 : void set_tag(int cd, const char *start, int len, bool compressed) {
254 : 1360034 : std::memmove(p + cd, start, len);
255 : 1360034 : set_size(cd + len);
256 [ + + ]: 1360034 : if (compressed) *p |= 0x80;
257 : 1360034 : }
258 : 2960 : void fake_root_item() {
259 : 2960 : set_key_len(K1 + C2); // null key length
260 : 2960 : set_size(I2 + K1 + 2 * C2); // length of the item
261 : 2960 : set_component_of(1);
262 : 2960 : set_components_of(1);
263 : 2960 : }
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 : : /// Return true if there are no entries in the table.
303 : : bool really_empty() const;
304 : :
305 : : public:
306 : : /** Create a new Btree object.
307 : : *
308 : : * This does not create the table on disk - the create_and_open()
309 : : * method must be called to create the table on disk.
310 : : *
311 : : * This also does not open the table - either the create_and_open()
312 : : * or open() methods must be called before use is made of the table.
313 : : *
314 : : * @param tablename_ The name of the table (used in changesets).
315 : : * @param path_ Path at which the table is stored.
316 : : * @param readonly_ whether to open the table for read only access.
317 : : * @param compress_strategy_ DONT_COMPRESS, Z_DEFAULT_STRATEGY,
318 : : * Z_FILTERED, Z_HUFFMAN_ONLY, or Z_RLE.
319 : : * @param lazy If true, don't create the table until it's
320 : : * needed.
321 : : */
322 : : BrassTable(const char * tablename_, const std::string & path_,
323 : : bool readonly_, int compress_strategy_ = DONT_COMPRESS,
324 : : bool lazy = false);
325 : :
326 : : /** Close the Btree.
327 : : *
328 : : * Any outstanding changes (ie, changes made without commit() having
329 : : * subsequently been called) will be lost.
330 : : */
331 : : ~BrassTable();
332 : :
333 : : /** Close the Btree. This closes and frees any of the btree
334 : : * structures which have been created and opened.
335 : : *
336 : : * @param permanent If true, the Btree will not reopen on demand.
337 : : */
338 : : void close(bool permanent=false);
339 : :
340 : : /** Determine whether the btree exists on disk.
341 : : */
342 : : bool exists() const;
343 : :
344 : : /** Open the btree at the latest revision.
345 : : *
346 : : * @exception Xapian::DatabaseCorruptError will be thrown if the table
347 : : * is in a corrupt state.
348 : : * @exception Xapian::DatabaseOpeningError will be thrown if the table
349 : : * cannot be opened (but is not corrupt - eg, permission problems,
350 : : * not present, etc).
351 : : */
352 : : void open();
353 : :
354 : : /** Open the btree at a given revision.
355 : : *
356 : : * Like Btree::open, but try to open at the given revision number
357 : : * and fail if that isn't possible.
358 : : *
359 : : * @param revision_ - revision number to open.
360 : : *
361 : : * @return true if table is successfully opened at desired revision;
362 : : * false if table cannot be opened at desired revision (but
363 : : * table is otherwise consistent).
364 : : *
365 : : * @exception Xapian::DatabaseCorruptError will be thrown if the table
366 : : * is in a corrupt state.
367 : : * @exception Xapian::DatabaseOpeningError will be thrown if the table
368 : : * cannot be opened (but is not corrupt - eg, permission problems,
369 : : * not present, etc).
370 : : */
371 : : bool open(brass_revision_number_t revision_);
372 : :
373 : : /** Return true if this table is open.
374 : : *
375 : : * NB If the table is lazy and doesn't yet exist, returns false.
376 : : */
377 : 611881 : bool is_open() const { return handle >= 0; }
378 : :
379 : : /** Flush any outstanding changes to the DB file of the table.
380 : : *
381 : : * This must be called before commit, to ensure that the DB file is
382 : : * ready to be switched to a new version by the commit.
383 : : */
384 : : void flush_db();
385 : :
386 : : /** Commit any outstanding changes to the table.
387 : : *
388 : : * Commit changes made by calling add() and del() to the Btree.
389 : : *
390 : : * If an error occurs during the operation, this will be signalled
391 : : * by an exception. In case of error, changes made will not be
392 : : * committed to the Btree - they will be discarded.
393 : : *
394 : : * @param new_revision The new revision number to store. This must
395 : : * be greater than the latest revision number (see
396 : : * get_latest_revision_number()), or an exception will be
397 : : * thrown.
398 : : *
399 : : * @param changes_fd The file descriptor to write changes to.
400 : : * Defaults to -1, meaning no changes will be written.
401 : : */
402 : : void commit(brass_revision_number_t revision, int changes_fd = -1,
403 : : const std::string * changes_tail = NULL);
404 : :
405 : : /** Append the list of blocks changed to a changeset file.
406 : : *
407 : : * @param changes_fd The file descriptor to write changes to.
408 : : */
409 : : void write_changed_blocks(int changes_fd);
410 : :
411 : : /** Cancel any outstanding changes.
412 : : *
413 : : * This will discard any modifications which haven't been committed
414 : : * by calling commit().
415 : : */
416 : : void cancel();
417 : :
418 : : /** Read an entry from the table, if and only if it is exactly that
419 : : * being asked for.
420 : : *
421 : : * If the key is found in the table, then the tag is copied to @a
422 : : * tag. If the key is not found tag is left unchanged.
423 : : *
424 : : * The result is true iff the specified key is found in the Btree.
425 : : *
426 : : * @param key The key to look for in the table.
427 : : * @param tag A tag object to fill with the value if found.
428 : : *
429 : : * @return true if key is found in table,
430 : : * false if key is not found in table.
431 : : */
432 : : bool get_exact_entry(const std::string & key, std::string & tag) const;
433 : :
434 : : /** Check if a key exists in the Btree.
435 : : *
436 : : * This is just like get_exact_entry() except it doesn't read the tag
437 : : * value so is more efficient if you only want to check that the key
438 : : * exists.
439 : : *
440 : : * @param key The key to look for in the table.
441 : : *
442 : : * @return true if key is found in table,
443 : : * false if key is not found in table.
444 : : */
445 : : bool key_exists(const std::string &key) const;
446 : :
447 : : /** Read the tag value for the key pointed to by cursor C_.
448 : : *
449 : : * @param keep_compressed Don't uncompress the tag - e.g. useful
450 : : * if it's just being opaquely copied.
451 : : *
452 : : * @return true if current_tag holds compressed data (always
453 : : * false if keep_compressed was false).
454 : : */
455 : : bool read_tag(Brass::Cursor * C_, std::string *tag, bool keep_compressed) const;
456 : :
457 : : /** Add a key/tag pair to the table, replacing any existing pair with
458 : : * the same key.
459 : : *
460 : : * If an error occurs during the operation, an exception will be
461 : : * thrown.
462 : : *
463 : : * If key is empty, then the null item is replaced.
464 : : *
465 : : * e.g. btree.add("TODAY", "Mon 9 Oct 2000");
466 : : *
467 : : * @param key The key to store in the table.
468 : : * @param tag The tag to store in the table.
469 : : * @param already_compressed true if tag is already compressed,
470 : : * for example because it is being opaquely copied
471 : : * (default: false).
472 : : */
473 : : void add(const std::string &key, std::string tag, bool already_compressed = false);
474 : :
475 : : /** Delete an entry from the table.
476 : : *
477 : : * The entry will be removed from the table, if it exists. If
478 : : * it does not exist, no action will be taken. The item with
479 : : * an empty key can't be removed, and false is returned.
480 : : *
481 : : * If an error occurs during the operation, this will be signalled
482 : : * by an exception.
483 : : *
484 : : * e.g. bool deleted = btree.del("TODAY")
485 : : *
486 : : * @param key The key to remove from the table.
487 : : *
488 : : * @return true if an entry was removed; false if it did not exist.
489 : : */
490 : : bool del(const std::string &key);
491 : :
492 : : /// Erase this table from disk.
493 : : void erase();
494 : :
495 : : /** Set the block size.
496 : : *
497 : : * It's only safe to do this before the table is created.
498 : : */
499 : : void set_block_size(unsigned int block_size_);
500 : :
501 : : /** Get the block size.
502 : : */
503 : 1924 : unsigned int get_block_size() const { return block_size; }
504 : :
505 : : /** Create a new empty btree structure on disk and open it at the
506 : : * initial revision.
507 : : *
508 : : * The table must be writable - it doesn't make sense to create
509 : : * a table that is read-only!
510 : : *
511 : : * The block size must be less than 64K, where K = 1024. It is unwise
512 : : * to use a small block size (less than 1024 perhaps), so we enforce a
513 : : * minimum block size of 2K.
514 : : *
515 : : * Example:
516 : : *
517 : : * Btree btree("X-");
518 : : * btree.create_and_open(8192);
519 : : * // Files will be X-DB, X-baseA (and X-baseB).
520 : : *
521 : : * @param blocksize - Size of blocks to use.
522 : : *
523 : : * @exception Xapian::DatabaseCreateError if the table can't be
524 : : * created.
525 : : * @exception Xapian::InvalidArgumentError if the requested blocksize
526 : : * is unsuitable.
527 : : */
528 : : void create_and_open(unsigned int blocksize);
529 : :
530 : : void set_full_compaction(bool parity);
531 : :
532 : : /** Get the latest revision number stored in this table.
533 : : *
534 : : * This gives the higher of the revision numbers held in the base
535 : : * files of the B-tree, or just the revision number if there's only
536 : : * one base file.
537 : : *
538 : : * It is possible that there are other, older, revisions of this
539 : : * table available, and indeed that the revision currently open
540 : : * is one of these older revisions.
541 : : */
542 : 810 : brass_revision_number_t get_latest_revision_number() const {
543 : 810 : return latest_revision_number;
544 : : }
545 : :
546 : : /** Get the revision number at which this table
547 : : * is currently open.
548 : : *
549 : : * It is possible that there are other, more recent or older
550 : : * revisions available.
551 : : *
552 : : * @return the current revision number.
553 : : */
554 : 6320 : brass_revision_number_t get_open_revision_number() const {
555 : 6320 : return revision_number;
556 : : }
557 : :
558 : : /** Return a count of the number of entries in the table.
559 : : *
560 : : * The count does not include the ever-present item with null key.
561 : : *
562 : : * Use @a empty() if you only want to know if the table is empty or
563 : : * not.
564 : : *
565 : : * @return The number of entries in the table.
566 : : */
567 : 225901 : brass_tablesize_t get_entry_count() const {
568 : 225901 : return item_count;
569 : : }
570 : :
571 : : /// Return true if there are no entries in the table.
572 : 1674 : bool empty() const {
573 : : // Prior to 1.1.4/1.0.18, item_count was stored in 32 bits, so we
574 : : // can't trust it as there could be more than 1<<32 entries.
575 : : //
576 : : // In theory it should wrap, so if non-zero the table isn't empty,
577 : : // but the table this was first noticed in wasn't off by a multiple
578 : : // of 1<<32.
579 : :
580 : : // An empty table will always have level == 0, and most non-empty
581 : : // tables will have more levels, so use that as a short-cut.
582 [ + + ][ + + ]: 1674 : return (level == 0) && really_empty();
583 : : }
584 : :
585 : : /** Get a cursor for reading from the table.
586 : : *
587 : : * The cursor is owned by the caller - it is the caller's
588 : : * responsibility to ensure that it is deleted.
589 : : */
590 : : BrassCursor * cursor_get() const;
591 : :
592 : : /** Determine whether the object contains uncommitted modifications.
593 : : *
594 : : * @return true if there have been modifications since the last
595 : : * the last call to commit().
596 : : */
597 : 4544 : bool is_modified() const { return Btree_modified; }
598 : :
599 : : /** Set the maximum item size given the block capacity.
600 : : *
601 : : * At least this many items of maximum size must fit into a block.
602 : : * The default is BLOCK_CAPACITY (which is currently 4).
603 : : */
604 : 8793 : void set_max_item_size(size_t block_capacity) {
605 [ - + ]: 8793 : if (block_capacity > BLOCK_CAPACITY) block_capacity = BLOCK_CAPACITY;
606 : : max_item_size = (block_size - DIR_START - block_capacity * D2)
607 : 8793 : / block_capacity;
608 : 8793 : }
609 : :
610 : : protected:
611 : :
612 : : /** Perform the opening operation to read.
613 : : *
614 : : * Return true iff the open succeeded.
615 : : */
616 : : bool do_open_to_read(bool revision_supplied, brass_revision_number_t revision_);
617 : :
618 : : /** Perform the opening operation to write.
619 : : *
620 : : * Return true iff the open succeeded.
621 : : */
622 : : bool do_open_to_write(bool revision_supplied,
623 : : brass_revision_number_t revision_,
624 : : bool create_db = false);
625 : : bool basic_open(bool revision_supplied, brass_revision_number_t revision);
626 : :
627 : : bool find(Brass::Cursor *) const;
628 : : int delete_kt();
629 : : void read_block(uint4 n, byte *p) const;
630 : : void write_block(uint4 n, const byte *p) const;
631 : : XAPIAN_NORETURN(void set_overwritten() const);
632 : : void block_to_cursor(Brass::Cursor *C_, int j, uint4 n) const;
633 : : void alter();
634 : : void compact(byte *p);
635 : : void enter_key(int j, Brass::Key prevkey, Brass::Key newkey);
636 : : int mid_point(byte *p);
637 : : void add_item_to_block(byte *p, Brass::Item_wr kt, int c);
638 : : void add_item(Brass::Item_wr kt, int j);
639 : : void delete_item(int j, bool repeatedly);
640 : : int add_kt(bool found);
641 : : void read_root();
642 : : void split_root(uint4 split_n);
643 : : void form_key(const std::string & key) const;
644 : :
645 : 2325 : char other_base_letter() const {
646 [ + + ]: 2325 : return (base_letter == 'A') ? 'B' : 'A';
647 : : }
648 : :
649 : : /// The name of the table (used when writing changesets).
650 : : const char * tablename;
651 : :
652 : : /// Allocate the zstream for deflating, if not already allocated.
653 : : void lazy_alloc_deflate_zstream() const;
654 : :
655 : : /// Allocate the zstream for inflating, if not already allocated.
656 : : void lazy_alloc_inflate_zstream() const;
657 : :
658 : : /** revision number of the opened B-tree. */
659 : : brass_revision_number_t revision_number;
660 : :
661 : : /** keeps a count of the number of items in the B-tree. */
662 : : brass_tablesize_t item_count;
663 : :
664 : : /** block size of the B tree in bytes */
665 : : unsigned int block_size;
666 : :
667 : : /** Revision number of the other base, or zero if there is only one
668 : : * base file.
669 : : */
670 : : mutable brass_revision_number_t latest_revision_number;
671 : :
672 : : /** set to true if baseA and baseB both exist as valid bases.
673 : : *
674 : : * The unused base is deleted as soon as a write to the Btree takes
675 : : * place. */
676 : : mutable bool both_bases;
677 : :
678 : : /** the value 'A' or 'B' of the current base */
679 : : char base_letter;
680 : :
681 : : /** true if the root block is faked (not written to disk).
682 : : * false otherwise. This is true when the btree hasn't been
683 : : * modified yet.
684 : : */
685 : : bool faked_root_block;
686 : :
687 : : /** true iff the data has been written in a single write in
688 : : * sequential order.
689 : : */
690 : : bool sequential;
691 : :
692 : : /** File descriptor of the table.
693 : : *
694 : : * If the table is lazily created and doesn't yet exist, this will be
695 : : * -1.
696 : : *
697 : : * If close() has been called, this will be -2.
698 : : */
699 : : int handle;
700 : :
701 : : /// number of levels, counting from 0
702 : : int level;
703 : :
704 : : /// the root block of the B-tree
705 : : uint4 root;
706 : :
707 : : /// buffer of size block_size for making up key-tag items
708 : : mutable Brass::Item_wr kt;
709 : :
710 : : /// buffer of size block_size for reforming blocks
711 : : byte * buffer;
712 : :
713 : : /// For writing back as file baseA or baseB.
714 : : BrassTable_base base;
715 : :
716 : : /// The path name of the B tree.
717 : : std::string name;
718 : :
719 : : /** count of the number of successive instances of purely
720 : : * sequential addition, starting at SEQ_START_POINT (neg) and
721 : : * going up to zero. */
722 : : int seq_count;
723 : :
724 : : /** the last block to be changed by an addition */
725 : : uint4 changed_n;
726 : :
727 : : /** directory offset corresponding to last block to be changed
728 : : * by an addition */
729 : : int changed_c;
730 : :
731 : : /// maximum size of an item (key-tag pair)
732 : : size_t max_item_size;
733 : :
734 : : /// Set to true the first time the B-tree is modified.
735 : : mutable bool Btree_modified;
736 : :
737 : : /// set to true when full compaction is to be achieved
738 : : bool full_compaction;
739 : :
740 : : /// Set to true when the database is opened to write.
741 : : bool writable;
742 : :
743 : : /// Flag for tracking when cursors need to rebuild.
744 : : mutable bool cursor_created_since_last_modification;
745 : :
746 : : /// Version count for tracking when cursors need to rebuild.
747 : : unsigned long cursor_version;
748 : :
749 : : /* B-tree navigation functions */
750 : 3881377 : bool prev(Brass::Cursor *C_, int j) const {
751 [ + + ]: 3881377 : if (sequential) return prev_for_sequential(C_, j);
752 : 3881377 : return prev_default(C_, j);
753 : : }
754 : :
755 : 6367712 : bool next(Brass::Cursor *C_, int j) const {
756 [ + + ]: 6367712 : if (sequential) return next_for_sequential(C_, j);
757 : 6367712 : return next_default(C_, j);
758 : : }
759 : :
760 : : /* Default implementations. */
761 : : bool prev_default(Brass::Cursor *C_, int j) const;
762 : : bool next_default(Brass::Cursor *C_, int j) const;
763 : :
764 : : /* Implementations for sequential mode. */
765 : : bool prev_for_sequential(Brass::Cursor *C_, int dummy) const;
766 : : bool next_for_sequential(Brass::Cursor *C_, int dummy) const;
767 : :
768 : : static int find_in_block(const byte * p, Brass::Key key, bool leaf, int c);
769 : :
770 : : /** block_given_by(p, c) finds the item at block address p, directory
771 : : * offset c, and returns its tag value as an integer.
772 : : */
773 : : static uint4 block_given_by(const byte * p, int c);
774 : :
775 : : mutable Brass::Cursor C[BTREE_CURSOR_LEVELS];
776 : :
777 : : /** Buffer used when splitting a block.
778 : : *
779 : : * This buffer holds the split off part of the block. It's only used
780 : : * when updating (in BrassTable::add_item().
781 : : */
782 : : byte * split_p;
783 : :
784 : : /** DONT_COMPRESS or Z_DEFAULT_STRATEGY, Z_FILTERED, Z_HUFFMAN_ONLY,
785 : : * Z_RLE. */
786 : : int compress_strategy;
787 : :
788 : : /// Zlib state object for deflating
789 : : mutable z_stream *deflate_zstream;
790 : :
791 : : /// Zlib state object for inflating
792 : : mutable z_stream *inflate_zstream;
793 : :
794 : : /// If true, don't create the table until it's needed.
795 : : bool lazy;
796 : :
797 : : /* Debugging methods */
798 : : // void report_block_full(int m, int n, const byte * p);
799 : :
800 : : /// Throw an exception indicating that the database is closed.
801 : : XAPIAN_NORETURN(static void throw_database_closed());
802 : : };
803 : :
804 : : #endif /* OM_HGUARD_BRASS_TABLE_H */
|
