Branch data Line data Source code
1 : : /** @file glass_table.h
2 : : * @brief Btree implementation
3 : : */
4 : : /* Copyright 1999,2000,2001 BrightStation PLC
5 : : * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010,2012,2013,2014,2015,2016 Olly Betts
6 : : * Copyright 2008 Lemur Consulting Ltd
7 : : *
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.
12 : : *
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.
17 : : *
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
21 : : * USA
22 : : */
23 : :
24 : : #ifndef XAPIAN_INCLUDED_GLASS_TABLE_H
25 : : #define XAPIAN_INCLUDED_GLASS_TABLE_H
26 : :
27 : : #include <xapian/constants.h>
28 : : #include <xapian/error.h>
29 : :
30 : : #include "glass_freelist.h"
31 : : #include "glass_cursor.h"
32 : : #include "glass_defs.h"
33 : :
34 : : #include "io_utils.h"
35 : : #include "omassert.h"
36 : : #include "str.h"
37 : : #include "stringutils.h"
38 : : #include "wordaccess.h"
39 : :
40 : : #include "common/compression_stream.h"
41 : :
42 : : #include <algorithm>
43 : : #include <string>
44 : :
45 : : namespace Glass {
46 : :
47 : : /** Even for items of at maximum size, it must be possible to get this number of
48 : : * items in a block */
49 : : const size_t BLOCK_CAPACITY = 4;
50 : :
51 : : /** The largest possible value of a key_len.
52 : : *
53 : : * This gives the upper limit of the size of a key that may be stored in the
54 : : * B-tree.
55 : : */
56 : : #define GLASS_BTREE_MAX_KEY_LEN 255
57 : :
58 : : // FIXME: This named constant probably isn't used everywhere it should be...
59 : : const int BYTES_PER_BLOCK_NUMBER = 4;
60 : :
61 : : /* The B-tree blocks have a number of internal lengths and offsets held in 1, 2
62 : : or 4 bytes. To make the coding a little clearer,
63 : : we use for
64 : : ------ ---
65 : : K1 the 1 byte length of key
66 : : I2 the 2 byte length of an item (key-tag pair)
67 : : D2 the 2 byte offset to the item from the directory
68 : : X2 the 2 byte component counter that ends each key
69 : : */
70 : :
71 : : const int K1 = 1;
72 : : const int I2 = 2;
73 : : const int D2 = 2;
74 : : const int X2 = 2;
75 : :
76 : : /* and when getting or setting them, we use these methods of the various
77 : : * *Item* classes: */
78 : :
79 : : // getD(p, c)
80 : : // setD(p, c, x)
81 : : // getI()
82 : : // setI(x)
83 : : // getX(p, c)
84 : : // setX(p, c, x)
85 : :
86 : : /* if you've been reading the comments from the top, the next four procedures
87 : : will not cause any headaches.
88 : :
89 : : Recall that a leaf item has this form:
90 : :
91 : : i k x
92 : : | | |
93 : : I K key X tag
94 : : ←K→
95 : : <---SIZE---->
96 : : <---I--->
97 : :
98 : : Except that X is omitted for the first component of a tag (there is a flag
99 : : bit in the upper bits of I which indicates these).
100 : :
101 : : item_of(p, c) returns i, the address of the item at block address p,
102 : : directory offset c,
103 : :
104 : : component_of(p, c) returns the number marked 'x' above,
105 : :
106 : : last_component(p, c) returns true if this is a final component.
107 : : */
108 : :
109 : 21763290 : inline uint4 REVISION(const uint8_t * b) { return aligned_read4(b); }
110 : 21868804 : inline int GET_LEVEL(const uint8_t * b) { return b[4]; }
111 : 12030882 : inline int MAX_FREE(const uint8_t * b) { return unaligned_read2(b + 5); }
112 : 13404912 : inline int TOTAL_FREE(const uint8_t * b) { return unaligned_read2(b + 7); }
113 : 79867710 : inline int DIR_END(const uint8_t * b) { return unaligned_read2(b + 9); }
114 : : const int DIR_START = 11;
115 : :
116 : 335996 : inline void SET_REVISION(uint8_t * b, uint4 rev) { aligned_write4(b, rev); }
117 : 27583 : inline void SET_LEVEL(uint8_t * b, int x) { AssertRel(x,<,256); b[4] = x; }
118 : 6494316 : inline void SET_MAX_FREE(uint8_t * b, int x) { unaligned_write2(b + 5, x); }
119 : 7918206 : inline void SET_TOTAL_FREE(uint8_t * b, int x) { unaligned_write2(b + 7, x); }
120 : 6015122 : inline void SET_DIR_END(uint8_t * b, int x) { unaligned_write2(b + 9, x); }
121 : :
122 : : // The item size is stored in 2 bytes, but the top bit is used to store a flag for
123 : : // "is the tag data compressed" and the next two bits are used to flag if this is the
124 : : // first and/or last item for this tag.
125 : : const int I_COMPRESSED_BIT = 0x80;
126 : : const int I_LAST_BIT = 0x40;
127 : : const int I_FIRST_BIT = 0x20;
128 : :
129 : : const int I_MASK = (I_COMPRESSED_BIT|I_LAST_BIT|I_FIRST_BIT);
130 : :
131 : : const int ITEM_SIZE_MASK = (0xffff &~ (I_MASK << 8));
132 : : const size_t MAX_ITEM_SIZE = (ITEM_SIZE_MASK + 3);
133 : :
134 : : /** Freelist blocks have their level set to LEVEL_FREELIST. */
135 : : const int LEVEL_FREELIST = 254;
136 : :
137 : : class RootInfo;
138 : :
139 : : class Key {
140 : : const uint8_t *p;
141 : : public:
142 : 111482032 : explicit Key(const uint8_t * p_) : p(p_) { }
143 : 41088 : const uint8_t * get_address() const { return p; }
144 : 208247848 : const uint8_t * data() const { return p + K1; }
145 : 4047674 : void read(std::string * key) const {
146 : 4047674 : key->assign(reinterpret_cast<const char *>(p + K1), length());
147 : 4047674 : }
148 : 111482032 : int length() const {
149 : 111482032 : return p[0];
150 : : }
151 : 220842 : char operator[](size_t i) const {
152 : : AssertRel(i,<,(size_t)length());
153 : 220842 : return p[i + K1];
154 : : }
155 : : };
156 : :
157 : : // LeafItem_wr wants to be "LeafItem with non-const p and more methods" - we can't
158 : : // achieve that nicely with inheritance, so we use a template base class.
159 : : template<class T> class LeafItem_base {
160 : : protected:
161 : : T p;
162 : 25707730 : int get_key_len() const { return p[I2]; }
163 : 51012527 : static int getD(const uint8_t * q, int c) {
164 : : AssertRel(c, >=, DIR_START);
165 : : AssertRel(c, <, 65535);
166 : : Assert((c & 1) == 1);
167 : 51012527 : return unaligned_read2(q + c);
168 : : }
169 : 45365602 : int getI() const { return unaligned_read2(p); }
170 : 4255626 : static int getX(const uint8_t * q, int c) { return unaligned_read2(q + c); }
171 : : public:
172 : : /* LeafItem from block address and offset to item pointer */
173 : 102025054 : LeafItem_base(T p_, int c) : p(p_ + getD(p_, c)) { }
174 : 22697263 : explicit LeafItem_base(T p_) : p(p_) { }
175 : 17317944 : T get_address() const { return p; }
176 : : /** SIZE in diagram above. */
177 : 22682801 : int size() const {
178 : 22682801 : return (getI() & ITEM_SIZE_MASK) + 3;
179 : : }
180 : 10800208 : bool get_compressed() const { return *p & I_COMPRESSED_BIT; }
181 : 50182982 : bool first_component() const { return *p & I_FIRST_BIT; }
182 : 22577612 : bool last_component() const { return *p & I_LAST_BIT; }
183 : 8366143 : int component_of() const {
184 [ + + ]: 8366143 : if (first_component()) return 1;
185 : 2127813 : return getX(p, get_key_len() + I2 + K1);
186 : : }
187 : 167562442 : Key key() const { return Key(p + I2); }
188 : 10010764 : void append_chunk(std::string * tag) const {
189 : : // Offset to the start of the tag data.
190 : 10010764 : int cd = get_key_len() + I2 + K1;
191 [ + + ]: 10010764 : if (!first_component()) cd += X2;
192 : : // Number of bytes to extract from current component.
193 : 10010764 : int l = size() - cd;
194 : 10010764 : const char * chunk = reinterpret_cast<const char *>(p + cd);
195 : 10010764 : tag->append(chunk, l);
196 : 10010764 : }
197 : 285346 : bool decompress_chunk(CompressionStream& comp_stream, string& tag) const {
198 : : // Offset to the start of the tag data.
199 : 285346 : int cd = get_key_len() + I2 + K1;
200 [ + + ]: 285346 : if (!first_component()) cd += X2;
201 : : // Number of bytes to extract from current component.
202 : 285346 : int l = size() - cd;
203 : 285346 : const char * chunk = reinterpret_cast<const char *>(p + cd);
204 : 285346 : return comp_stream.decompress_chunk(chunk, l, tag);
205 : : }
206 : : };
207 : :
208 : : class LeafItem : public LeafItem_base<const uint8_t *> {
209 : : public:
210 : : /* LeafItem from block address and offset to item pointer */
211 : 51012527 : LeafItem(const uint8_t * p_, int c)
212 : 51012527 : : LeafItem_base<const uint8_t *>(p_, c) { }
213 : 22590478 : explicit LeafItem(const uint8_t * p_)
214 : 22590478 : : LeafItem_base<const uint8_t *>(p_) { }
215 : : };
216 : :
217 : : class LeafItem_wr : public LeafItem_base<uint8_t *> {
218 : 8909492 : void set_key_len(int x) {
219 : : AssertRel(x, >=, 0);
220 : : AssertRel(x, <=, GLASS_BTREE_MAX_KEY_LEN);
221 : 8909492 : p[I2] = x;
222 : 8909492 : }
223 : 7418452 : void setI(int x) { unaligned_write2(p, x); }
224 : 859884 : static void setX(uint8_t * q, int c, int x) { unaligned_write2(q + c, x); }
225 : : public:
226 : : /* LeafItem_wr from block address and offset to item pointer */
227 : : LeafItem_wr(uint8_t * p_, int c) : LeafItem_base<uint8_t *>(p_, c) { }
228 : 213570 : explicit LeafItem_wr(uint8_t * p_) : LeafItem_base<uint8_t *>(p_) { }
229 : 429942 : void set_component_of(int i) {
230 : : AssertRel(i,>,1);
231 : 429942 : *p &=~ I_FIRST_BIT;
232 : 429942 : setX(p, get_key_len() + I2 + K1, i);
233 : 429942 : }
234 : 3709226 : void set_size(int new_size) {
235 : : AssertRel(new_size,>=,3);
236 : 3709226 : int I = new_size - 3;
237 : : // We should never be able to pass too large a size here, but don't
238 : : // corrupt the database if this somehow happens.
239 [ - + ][ # # ]: 3709226 : if (rare(I &~ ITEM_SIZE_MASK)) throw Xapian::DatabaseError("item too large!");
[ # # ][ # # ]
240 : 3709226 : setI(I);
241 : 3709226 : }
242 : 8899197 : void form_key(const std::string & key_) {
243 : 8899197 : std::string::size_type key_len = key_.length();
244 [ + + ]: 8899197 : if (key_len > GLASS_BTREE_MAX_KEY_LEN) {
245 : : // We check term length when a term is added to a document but
246 : : // glass doubles zero bytes, so this can still happen for terms
247 : : // which contain one or more zero bytes.
248 [ + - ]: 10 : std::string msg("Key too long: length was ");
249 [ + - ][ + - ]: 10 : msg += str(key_len);
250 : : msg += " bytes, maximum length of a key is "
251 [ + - ]: 10 : STRINGIZE(GLASS_BTREE_MAX_KEY_LEN) " bytes";
252 [ + - ][ + - ]: 10 : throw Xapian::InvalidArgumentError(msg);
253 : : }
254 : :
255 : 8899187 : set_key_len(key_len);
256 : 8899187 : std::memmove(p + I2 + K1, key_.data(), key_len);
257 : 8899187 : *p |= I_FIRST_BIT;
258 : 8899187 : }
259 : : // FIXME passing cd here is icky
260 : 3698921 : void set_tag(int cd, const char *start, int len, bool compressed, int i, int m) {
261 : 3698921 : std::memmove(p + cd, start, len);
262 : 3698921 : set_size(cd + len);
263 [ + + ]: 3698921 : if (compressed) *p |= I_COMPRESSED_BIT;
264 [ + + ]: 3698921 : if (i == m) *p |= I_LAST_BIT;
265 [ + + ]: 3698921 : if (i == 1) {
266 : 3269346 : *p |= I_FIRST_BIT;
267 : : } else {
268 : 429575 : set_component_of(i);
269 : : }
270 : 3698921 : }
271 : 10305 : void fake_root_item() {
272 : 10305 : set_key_len(0); // null key length
273 : 10305 : set_size(I2 + K1); // length of the item
274 : 10305 : *p |= I_FIRST_BIT|I_LAST_BIT;
275 : 10305 : }
276 : 45180956 : operator const LeafItem() const { return LeafItem(p); }
277 : 7188588 : static void setD(uint8_t * q, int c, int x) {
278 : : AssertRel(c, >=, DIR_START);
279 : : AssertRel(c, <, 65535);
280 : : Assert((c & 1) == 1);
281 : 7188588 : unaligned_write2(q + c, x);
282 : 7188588 : }
283 : : };
284 : :
285 : : /* A branch item has this form:
286 : :
287 : : k x
288 : : | |
289 : : tag K key X
290 : : ←B→ ←K→
291 : : <--SIZE--->
292 : :
293 : : B = BYTES_PER_BLOCK_NUMBER
294 : :
295 : : We can't omit X here, as we've nowhere to store the first and last bit
296 : : flags which we have in leaf items.
297 : : */
298 : :
299 : : // BItem_wr wants to be "BItem with non-const p and more methods" - we can't
300 : : // achieve that nicely with inheritance, so we use a template base class.
301 : : template<class T> class BItem_base {
302 : : protected:
303 : : T p;
304 : 2619806 : int get_key_len() const { return p[BYTES_PER_BLOCK_NUMBER]; }
305 : 41120944 : static int getD(const uint8_t * q, int c) {
306 : : AssertRel(c, >=, DIR_START);
307 : : AssertRel(c, <, 65535);
308 : : Assert((c & 1) == 1);
309 : 41120944 : return unaligned_read2(q + c);
310 : : }
311 : 2499964 : static int getX(const uint8_t * q, int c) { return unaligned_read2(q + c); }
312 : : public:
313 : : /* BItem from block address and offset to item pointer */
314 : 82241888 : BItem_base(T p_, int c) : p(p_ + getD(p_, c)) { }
315 : 41804 : explicit BItem_base(T p_) : p(p_) { }
316 : 69490 : T get_address() const { return p; }
317 : : /** SIZE in diagram above. */
318 : 59474 : int size() const {
319 : 59474 : return get_key_len() + K1 + X2 + BYTES_PER_BLOCK_NUMBER;
320 : : }
321 : 55401622 : Key key() const { return Key(p + BYTES_PER_BLOCK_NUMBER); }
322 : : /** Get this item's tag as a block number (this block should not be at
323 : : * level 0).
324 : : */
325 : 13278811 : uint4 block_given_by() const {
326 : 13278811 : return unaligned_read4(p);
327 : : }
328 : 1249982 : int component_of() const {
329 : 1249982 : return getX(p, get_key_len() + BYTES_PER_BLOCK_NUMBER + K1);
330 : : }
331 : : };
332 : :
333 : : class BItem : public BItem_base<const uint8_t *> {
334 : : public:
335 : : /* BItem from block address and offset to item pointer */
336 : 81994222 : BItem(const uint8_t * p_, int c) : BItem_base<const uint8_t *>(p_, c) { }
337 : 41804 : explicit BItem(const uint8_t * p_) : BItem_base<const uint8_t *>(p_) { }
338 : : };
339 : :
340 : : class BItem_wr : public BItem_base<uint8_t *> {
341 : 20902 : void set_key_len(int x) {
342 : : AssertRel(x, >=, 0);
343 : : AssertRel(x, <, GLASS_BTREE_MAX_KEY_LEN);
344 : 20902 : p[BYTES_PER_BLOCK_NUMBER] = x;
345 : 20902 : }
346 : 41804 : static void setX(uint8_t * q, int c, int x) { unaligned_write2(q + c, x); }
347 : : public:
348 : : /* BItem_wr from block address and offset to item pointer */
349 : 247666 : BItem_wr(uint8_t * p_, int c) : BItem_base<uint8_t *>(p_, c) { }
350 : 41804 : explicit BItem_wr(uint8_t * p_) : BItem_base<uint8_t *>(p_) { }
351 : 447 : void set_component_of(int i) {
352 : 447 : setX(p, get_key_len() + BYTES_PER_BLOCK_NUMBER + K1, i);
353 : 447 : }
354 : 89 : void set_key_and_block(Key newkey, uint4 n) {
355 : 89 : int len = newkey.length() + K1 + X2;
356 : : // Copy the key size, main part of the key and the count part.
357 : 89 : std::memcpy(p + BYTES_PER_BLOCK_NUMBER, newkey.get_address(), len);
358 : : // Set tag contents to block number
359 : 89 : set_block_given_by(n);
360 : 89 : }
361 : : // Takes size as we may be truncating newkey.
362 : 20455 : void set_truncated_key_and_block(Key newkey, int new_comp,
363 : : int truncate_size, uint4 n) {
364 : 20455 : int i = truncate_size;
365 : : AssertRel(i,<=,newkey.length());
366 : : // Key size
367 : 20455 : set_key_len(i);
368 : : // Copy the main part of the key, possibly truncating.
369 : 20455 : std::memcpy(p + BYTES_PER_BLOCK_NUMBER + K1, newkey.get_address() + K1, i);
370 : : // Set the component count.
371 : 20455 : setX(p, BYTES_PER_BLOCK_NUMBER + K1 + i, new_comp);
372 : : // Set tag contents to block number
373 : 20455 : set_block_given_by(n);
374 : 20455 : }
375 : :
376 : : /** Set this item's tag to point to block n (this block should not be at
377 : : * level 0).
378 : : */
379 : 144735 : void set_block_given_by(uint4 n) {
380 : 144735 : unaligned_write4(p, n);
381 : 144735 : }
382 : : /** Form an item with a null key and with block number n in the tag.
383 : : */
384 : 447 : void form_null_key(uint4 n) {
385 : 447 : set_block_given_by(n);
386 : 447 : set_key_len(0); /* null key */
387 : 447 : set_component_of(0);
388 : 447 : }
389 : 41804 : operator const BItem() const { return BItem(p); }
390 : 34734 : static void setD(uint8_t * q, int c, int x) {
391 : : AssertRel(c, >=, DIR_START);
392 : : AssertRel(c, <, 65535);
393 : : Assert((c & 1) == 1);
394 : 34734 : unaligned_write2(q + c, x);
395 : 34734 : }
396 : : };
397 : :
398 : : // Allow for BTREE_CURSOR_LEVELS levels in the B-tree.
399 : : // With 10, overflow is practically impossible
400 : : // FIXME: but we want it to be completely impossible...
401 : : const int BTREE_CURSOR_LEVELS = 10;
402 : :
403 : : }
404 : :
405 : : using Glass::RootInfo;
406 : :
407 : : class GlassChanges;
408 : :
409 : : /** Class managing a Btree table in a Glass database.
410 : : *
411 : : * A table is a store holding a set of key/tag pairs.
412 : : *
413 : : * A key is used to access a block of data in a glass table.
414 : : *
415 : : * Keys are of limited length.
416 : : *
417 : : * Keys may not be empty (each Btree has a special empty key for internal use).
418 : : *
419 : : * A tag is a piece of data associated with a given key. The contents
420 : : * of the tag are opaque to the Btree.
421 : : *
422 : : * Tags may be of arbitrary length (the Btree imposes a very large limit).
423 : : * Note though that they will be loaded into memory in their entirety, so
424 : : * should not be permitted to grow without bound in normal usage.
425 : : *
426 : : * Tags which are null strings _are_ valid, and are different from a
427 : : * tag simply not being in the table.
428 : : */
429 : : class GlassTable {
430 : : friend class GlassCursor; /* Should probably fix this. */
431 : : friend class GlassFreeList;
432 : :
433 : : private:
434 : : /// Copying not allowed
435 : : GlassTable(const GlassTable &);
436 : :
437 : : /// Assignment not allowed
438 : : GlassTable & operator=(const GlassTable &);
439 : :
440 : : void basic_open(const RootInfo * root_info,
441 : : glass_revision_number_t rev);
442 : :
443 : : /** Perform the opening operation to read. */
444 : : void do_open_to_read(const RootInfo * root_info,
445 : : glass_revision_number_t rev);
446 : :
447 : : /** Perform the opening operation to write. */
448 : : void do_open_to_write(const RootInfo * root_info,
449 : : glass_revision_number_t rev = 0);
450 : :
451 : : public:
452 : : /** Create a new Btree object.
453 : : *
454 : : * This does not create the table on disk - the create_and_open()
455 : : * method must be called to create the table on disk.
456 : : *
457 : : * This also does not open the table - either the create_and_open()
458 : : * or open() methods must be called before use is made of the table.
459 : : *
460 : : * @param tablename_ The name of the table (used in changesets).
461 : : * @param path_ Path at which the table is stored.
462 : : * @param readonly_ whether to open the table for read only access.
463 : : * @param lazy If true, don't create the table until it's
464 : : * needed.
465 : : */
466 : : GlassTable(const char * tablename_, const std::string & path_,
467 : : bool readonly_, bool lazy = false);
468 : :
469 : : GlassTable(const char * tablename_, int fd, off_t offset_,
470 : : bool readonly_, bool lazy = false);
471 : :
472 : : /** Close the Btree.
473 : : *
474 : : * Any outstanding changes (ie, changes made without commit() having
475 : : * subsequently been called) will be lost.
476 : : */
477 : : ~GlassTable();
478 : :
479 : : /** Close the Btree. This closes and frees any of the btree
480 : : * structures which have been created and opened.
481 : : *
482 : : * @param permanent If true, the Btree will not reopen on demand.
483 : : */
484 : : void close(bool permanent = false);
485 : :
486 : : bool readahead_key(const string &key) const;
487 : :
488 : : /** Determine whether the btree exists on disk.
489 : : */
490 : : bool exists() const;
491 : :
492 : : /** Open the btree.
493 : : *
494 : : * @param flags_ flags for opening
495 : : * @param root_info root block info
496 : : *
497 : : * @exception Xapian::DatabaseCorruptError will be thrown if the table
498 : : * is in a corrupt state.
499 : : * @exception Xapian::DatabaseOpeningError will be thrown if the table
500 : : * cannot be opened (but is not corrupt - eg, permission problems,
501 : : * not present, etc).
502 : : */
503 : : void open(int flags_, const RootInfo & root_info,
504 : : glass_revision_number_t rev);
505 : :
506 : : /** Return true if this table is open.
507 : : *
508 : : * NB If the table is lazy and doesn't yet exist, returns false.
509 : : */
510 : 2210586 : bool is_open() const { return handle >= 0; }
511 : :
512 : : /** Return true if this table is writable. */
513 : 199982 : bool is_writable() const { return writable; }
514 : :
515 : : /** Flush any outstanding changes to the DB file of the table.
516 : : *
517 : : * This must be called before commit, to ensure that the DB file is
518 : : * ready to be switched to a new version by the commit.
519 : : */
520 : : void flush_db();
521 : :
522 : : /** Commit any outstanding changes to the table.
523 : : *
524 : : * Commit changes made by calling add() and del() to the Btree.
525 : : *
526 : : * If an error occurs during the operation, this will be signalled
527 : : * by an exception. In case of error, changes made will not be
528 : : * committed to the Btree - they will be discarded.
529 : : *
530 : : * @param new_revision The new revision number to store. This must
531 : : * be greater than the current revision number. FIXME: If
532 : : * we support rewinding to a previous revision, maybe this
533 : : * needs to be greater than any previously used revision.
534 : : *
535 : : * @param root_info Information about the root is returned in this.
536 : : */
537 : : void commit(glass_revision_number_t revision, RootInfo * root_info);
538 : :
539 : 55236 : bool sync() {
540 [ + + ]: 55236 : return (flags & Xapian::DB_NO_SYNC) ||
541 [ + - + - ]: 110472 : handle < 0 ||
542 : 100778 : io_sync(handle);
543 : : }
544 : :
545 : : /** Cancel any outstanding changes.
546 : : *
547 : : * This will discard any modifications which haven't been committed
548 : : * by calling commit().
549 : : */
550 : : void cancel(const RootInfo & root_info, glass_revision_number_t rev);
551 : :
552 : : /** Read an entry from the table, if and only if it is exactly that
553 : : * being asked for.
554 : : *
555 : : * If the key is found in the table, then the tag is copied to @a
556 : : * tag. If the key is not found tag is left unchanged.
557 : : *
558 : : * The result is true iff the specified key is found in the Btree.
559 : : *
560 : : * @param key The key to look for in the table.
561 : : * @param tag A tag object to fill with the value if found.
562 : : *
563 : : * @return true if key is found in table,
564 : : * false if key is not found in table.
565 : : */
566 : : bool get_exact_entry(const std::string & key, std::string & tag) const;
567 : :
568 : : /** Check if a key exists in the Btree.
569 : : *
570 : : * This is just like get_exact_entry() except it doesn't read the tag
571 : : * value so is more efficient if you only want to check that the key
572 : : * exists.
573 : : *
574 : : * @param key The key to look for in the table.
575 : : *
576 : : * @return true if key is found in table,
577 : : * false if key is not found in table.
578 : : */
579 : : bool key_exists(const std::string &key) const;
580 : :
581 : : /** Read the tag value for the key pointed to by cursor C_.
582 : : *
583 : : * @param keep_compressed Don't uncompress the tag - e.g. useful
584 : : * if it's just being opaquely copied.
585 : : *
586 : : * @return true if current_tag holds compressed data (always
587 : : * false if keep_compressed was false).
588 : : */
589 : : bool read_tag(Glass::Cursor* C_,
590 : : std::string* tag,
591 : : bool keep_compressed) const;
592 : :
593 : : /** Add a key/tag pair to the table, replacing any existing pair with
594 : : * the same key.
595 : : *
596 : : * If an error occurs during the operation, an exception will be
597 : : * thrown.
598 : : *
599 : : * If key is empty, then the null item is replaced.
600 : : *
601 : : * e.g. btree.add("TODAY", "Mon 9 Oct 2000");
602 : : *
603 : : * @param key The key to store in the table.
604 : : * @param tag The tag to store in the table.
605 : : * @param already_compressed true if tag is already compressed,
606 : : * for example because it is being opaquely copied
607 : : * (default: false).
608 : : */
609 : : void add(const std::string& key,
610 : : std::string tag,
611 : : bool already_compressed = false);
612 : :
613 : : /** Delete an entry from the table.
614 : : *
615 : : * The entry will be removed from the table, if it exists. If
616 : : * it does not exist, no action will be taken. The item with
617 : : * an empty key can't be removed, and false is returned.
618 : : *
619 : : * If an error occurs during the operation, this will be signalled
620 : : * by an exception.
621 : : *
622 : : * e.g. bool deleted = btree.del("TODAY")
623 : : *
624 : : * @param key The key to remove from the table.
625 : : *
626 : : * @return true if an entry was removed; false if it did not exist.
627 : : */
628 : : bool del(const std::string &key);
629 : :
630 : 18414 : int get_flags() const { return flags; }
631 : :
632 : : /** Create a new empty btree structure on disk and open it at the
633 : : * initial revision.
634 : : *
635 : : * The table must be writable - it doesn't make sense to create
636 : : * a table that is read-only!
637 : : *
638 : : * The block size must be less than 64K, where K = 1024. It is unwise
639 : : * to use a small block size (less than 1024 perhaps), so we enforce a
640 : : * minimum block size of 2K.
641 : : *
642 : : * Example:
643 : : *
644 : : * // File will be "X." + GLASS_TABLE_EXTENSION (i.e. "X.glass")
645 : : * Btree btree("X.");
646 : : * btree.create_and_open(0, root_info);
647 : : *
648 : : * @param root_info RootInfo object
649 : : *
650 : : * @exception Xapian::DatabaseCreateError if the table can't be
651 : : * created.
652 : : * @exception Xapian::InvalidArgumentError if the requested blocksize
653 : : * is unsuitable.
654 : : */
655 : : void create_and_open(int flags_, const RootInfo & root_info);
656 : :
657 : : void set_full_compaction(bool parity);
658 : :
659 : : /** Get the revision number at which this table
660 : : * is currently open.
661 : : *
662 : : * It is possible that there are other, more recent or older
663 : : * revisions available.
664 : : *
665 : : * @return the current revision number.
666 : : */
667 : : glass_revision_number_t get_open_revision_number() const {
668 : : return revision_number;
669 : : }
670 : :
671 : : /** Return a count of the number of entries in the table.
672 : : *
673 : : * The count does not include the ever-present item with null key.
674 : : *
675 : : * Use @a empty() if you only want to know if the table is empty or
676 : : * not.
677 : : *
678 : : * @return The number of entries in the table.
679 : : */
680 : 20682 : glass_tablesize_t get_entry_count() const {
681 : 20682 : return item_count;
682 : : }
683 : :
684 : : /// Return true if there are no entries in the table.
685 : 88791 : bool empty() const {
686 : 88791 : return (item_count == 0);
687 : : }
688 : :
689 : : /** Get a cursor for reading from the table.
690 : : *
691 : : * The cursor is owned by the caller - it is the caller's
692 : : * responsibility to ensure that it is deleted.
693 : : */
694 : : GlassCursor * cursor_get() const;
695 : :
696 : : /** Determine whether the object contains uncommitted modifications.
697 : : *
698 : : * @return true if there have been modifications since the last
699 : : * the last call to commit().
700 : : */
701 : 68126 : bool is_modified() const { return Btree_modified; }
702 : :
703 : : /** Set the maximum item size given the block capacity.
704 : : *
705 : : * At least this many items of maximum size must fit into a block.
706 : : * The default is BLOCK_CAPACITY (which is currently 4).
707 : : */
708 : 17180 : void set_max_item_size(size_t block_capacity) {
709 [ - + ]: 17180 : if (block_capacity > Glass::BLOCK_CAPACITY)
710 : 0 : block_capacity = Glass::BLOCK_CAPACITY;
711 : : using Glass::DIR_START;
712 : : using Glass::D2;
713 : : max_item_size =
714 : 17180 : (block_size - DIR_START - block_capacity * D2) / block_capacity;
715 : : // Make sure we don't exceed the limit imposed by the format.
716 [ + + ]: 17180 : if (max_item_size > Glass::MAX_ITEM_SIZE)
717 : 8 : max_item_size = Glass::MAX_ITEM_SIZE;
718 : 17180 : }
719 : :
720 : : /** Set the GlassChanges object to write changed blocks to.
721 : : *
722 : : * The GlassChanges object is not owned by the table, so the table
723 : : * must not delete it.
724 : : */
725 : 58080 : void set_changes(GlassChanges * changes) {
726 : 58080 : changes_obj = changes;
727 : 58080 : }
728 : :
729 : : /// Throw an exception indicating that the database is closed.
730 : : [[noreturn]]
731 : : static void throw_database_closed();
732 : :
733 : 2594 : string get_path() const {
734 : 2594 : return name + GLASS_TABLE_EXTENSION;
735 : : }
736 : :
737 : : protected:
738 : : bool find(Glass::Cursor *) const;
739 : : int delete_kt();
740 : : void read_block(uint4 n, uint8_t *p) const;
741 : : void write_block(uint4 n, const uint8_t *p,
742 : : bool appending = false) const;
743 : : [[noreturn]]
744 : : void set_overwritten() const;
745 : : void block_to_cursor(Glass::Cursor *C_, int j, uint4 n) const;
746 : : void alter();
747 : : void compact(uint8_t *p);
748 : : void enter_key_above_leaf(Glass::LeafItem previtem,
749 : : Glass::LeafItem newitem);
750 : : void enter_key_above_branch(int j, Glass::BItem newitem);
751 : : int mid_point(uint8_t *p) const;
752 : : void add_item_to_leaf(uint8_t *p, Glass::LeafItem kt, int c);
753 : : void add_item_to_branch(uint8_t *p, Glass::BItem kt, int c);
754 : : void add_leaf_item(Glass::LeafItem kt);
755 : : void add_branch_item(Glass::BItem kt, int j);
756 : : void delete_leaf_item(bool repeatedly);
757 : : void delete_branch_item(int j);
758 : : int add_kt(bool found);
759 : : void read_root();
760 : : void split_root(uint4 split_n);
761 : : void form_key(const std::string & key) const;
762 : :
763 : : /// The name of the table (used when writing changesets).
764 : : const char * tablename;
765 : :
766 : : /** revision number of the opened B-tree. */
767 : : glass_revision_number_t revision_number;
768 : :
769 : : /** keeps a count of the number of items in the B-tree. */
770 : : glass_tablesize_t item_count;
771 : :
772 : : /** block size of the B tree in bytes */
773 : : unsigned int block_size;
774 : :
775 : : /** Flags like DB_NO_SYNC and DB_DANGEROUS. */
776 : : int flags;
777 : :
778 : : /** true if the root block is faked (not written to disk).
779 : : * false otherwise. This is true when the btree hasn't been
780 : : * modified yet.
781 : : */
782 : : bool faked_root_block;
783 : :
784 : : /** true iff the data has been written in a single write in
785 : : * sequential order.
786 : : */
787 : : bool sequential;
788 : :
789 : : /** File descriptor of the table.
790 : : *
791 : : * If close() has been called, this will be -2.
792 : : *
793 : : * If the table is lazily created and doesn't yet exist, this will be
794 : : * -1 (for a multi-file database) or -3-fd (for a single-file database).
795 : : */
796 : : int handle;
797 : :
798 : : /// number of levels, counting from 0
799 : : int level;
800 : :
801 : : /// the root block of the B-tree
802 : : uint4 root;
803 : :
804 : : /// buffer of size block_size for making up key-tag items
805 : : mutable Glass::LeafItem_wr kt;
806 : :
807 : : /// buffer of size block_size for reforming blocks
808 : : uint8_t * buffer;
809 : :
810 : : /// List of free blocks.
811 : : GlassFreeList free_list;
812 : :
813 : : /** The path name of the B tree.
814 : : *
815 : : * For a single-file database, this will be empty.
816 : : */
817 : : std::string name;
818 : :
819 : : /** count of the number of successive instances of purely
820 : : * sequential addition, starting at SEQ_START_POINT (neg) and
821 : : * going up to zero. */
822 : : int seq_count;
823 : :
824 : : /** the last block to be changed by an addition */
825 : : uint4 changed_n;
826 : :
827 : : /** directory offset corresponding to last block to be changed
828 : : * by an addition */
829 : : int changed_c;
830 : :
831 : : /// maximum size of an item (key-tag pair)
832 : : size_t max_item_size;
833 : :
834 : : /// Set to true the first time the B-tree is modified.
835 : : mutable bool Btree_modified;
836 : :
837 : : /// set to true when full compaction is to be achieved
838 : : bool full_compaction;
839 : :
840 : : /// Set to true when the database is opened to write.
841 : : bool writable;
842 : :
843 : : /// Flag for tracking when cursors need to rebuild.
844 : : mutable bool cursor_created_since_last_modification;
845 : :
846 : : /// Version count for tracking when cursors need to rebuild.
847 : : unsigned long cursor_version;
848 : :
849 : : /** The GlassChanges object to write block changes to.
850 : : *
851 : : * If NULL, no changes will be written.
852 : : */
853 : : GlassChanges * changes_obj;
854 : :
855 : 44198 : bool single_file() const {
856 : 44198 : return name.empty();
857 : : }
858 : :
859 : : /* B-tree navigation functions */
860 : 4093814 : bool prev(Glass::Cursor *C_, int j) const {
861 [ + + ][ + - ]: 4093814 : if (sequential && !single_file())
[ + + ]
862 : 10040 : return prev_for_sequential(C_, j);
863 : 4083774 : return prev_default(C_, j);
864 : : }
865 : :
866 : 8978728 : bool next(Glass::Cursor *C_, int j) const {
867 [ + + ]: 8978728 : if (sequential) return next_for_sequential(C_, j);
868 : 7832565 : return next_default(C_, j);
869 : : }
870 : :
871 : : /* Default implementations. */
872 : : bool prev_default(Glass::Cursor *C_, int j) const;
873 : : bool next_default(Glass::Cursor *C_, int j) const;
874 : :
875 : : /* Implementations for sequential mode. */
876 : : bool prev_for_sequential(Glass::Cursor *C_, int dummy) const;
877 : : bool next_for_sequential(Glass::Cursor *C_, int dummy) const;
878 : :
879 : : static int find_in_leaf(const uint8_t * p,
880 : : Glass::LeafItem item, int c, bool& exact);
881 : : static int find_in_branch(const uint8_t * p,
882 : : Glass::LeafItem item, int c);
883 : : static int find_in_branch(const uint8_t * p, Glass::BItem item, int c);
884 : :
885 : : /** block_given_by(p, c) finds the item at block address p, directory
886 : : * offset c, and returns its tag value as an integer.
887 : : */
888 : : static uint4 block_given_by(const uint8_t * p, int c);
889 : :
890 : : mutable Glass::Cursor C[Glass::BTREE_CURSOR_LEVELS];
891 : :
892 : : /** Buffer used when splitting a block.
893 : : *
894 : : * This buffer holds the split off part of the block. It's only used
895 : : * when updating (in GlassTable::add_item().
896 : : */
897 : : uint8_t * split_p;
898 : :
899 : : /** Minimum size tag to try compressing (0 for no compression). */
900 : : uint4 compress_min;
901 : :
902 : : mutable CompressionStream comp_stream;
903 : :
904 : : /// If true, don't create the table until it's needed.
905 : : bool lazy;
906 : :
907 : : /// Last block readahead_key() preread.
908 : : mutable uint4 last_readahead;
909 : :
910 : : /// offset to start of table in file.
911 : : off_t offset;
912 : :
913 : : /* Debugging methods */
914 : : // void report_block_full(int m, int n, const uint8_t * p);
915 : : };
916 : :
917 : : namespace Glass {
918 : :
919 : : /** Compare two items by their keys.
920 : :
921 : : The result is negative if a precedes b, positive is b precedes a, and
922 : : 0 if a and b are equal. The comparison is for byte sequence collating
923 : : order, taking lengths into account. So if the keys are made up of lower case
924 : : ASCII letters we get alphabetical ordering.
925 : :
926 : : Now remember that items are added into the B-tree in fastest time
927 : : when they are preordered by their keys. This is therefore the piece
928 : : of code that needs to be followed to arrange for the preordering.
929 : :
930 : : Note that keys have two parts - a string value and a "component_of" count.
931 : : If the string values are equal, the comparison is made based on
932 : : "component_of".
933 : : */
934 : :
935 : : template<typename ITEM1, typename ITEM2>
936 : 52061959 : int compare(ITEM1 a, ITEM2 b)
937 : : {
938 : 52061959 : Key key1 = a.key();
939 : 52061959 : Key key2 = b.key();
940 : 52061959 : const uint8_t* p1 = key1.data();
941 : 52061959 : const uint8_t* p2 = key2.data();
942 : 52061959 : int key1_len = key1.length();
943 : 52061959 : int key2_len = key2.length();
944 [ + + ][ + + ]: 52061959 : int k_smaller = (key2_len < key1_len ? key2_len : key1_len);
[ # # ]
945 : :
946 : : // Compare the common part of the keys.
947 : 52061959 : int diff = std::memcmp(p1, p2, k_smaller);
948 [ + + ][ + + ]: 52061959 : if (diff == 0) {
[ # # ]
949 : : // If the common part matches, compare the lengths.
950 : 8138107 : diff = key1_len - key2_len;
951 [ + + ][ + + ]: 8138107 : if (diff == 0) {
[ # # ]
952 : : // If the strings match, compare component_of().
953 [ + - ][ + - ]: 4797835 : diff = a.component_of() - b.component_of();
[ + - ][ + - ]
[ # # ][ # # ]
954 : : }
955 : : }
956 : 52061959 : return diff;
957 : : }
958 : :
959 : : /** Compare two BItem objects by their keys.
960 : : *
961 : : * Specialisation for comparing two BItems, where component_of is always
962 : : * explicitly stored.
963 : : */
964 : : inline int
965 : 3 : compare(BItem a, BItem b)
966 : : {
967 : 3 : Key key1 = a.key();
968 : 3 : Key key2 = b.key();
969 : 3 : const uint8_t* p1 = key1.data();
970 : 3 : const uint8_t* p2 = key2.data();
971 : 3 : int key1_len = key1.length();
972 : 3 : int key2_len = key2.length();
973 [ + + ]: 3 : if (key1_len == key2_len) {
974 : : // The keys are the same length, so we can compare the counts in the
975 : : // same operation since they're stored as 2 byte bigendian numbers.
976 : 1 : int len = key1_len + X2;
977 : 1 : return std::memcmp(p1, p2, len);
978 : : }
979 : :
980 [ + - ]: 2 : int k_smaller = (key2_len < key1_len ? key2_len : key1_len);
981 : :
982 : : // Compare the common part of the keys.
983 : 2 : int diff = std::memcmp(p1, p2, k_smaller);
984 [ - + ]: 2 : if (diff == 0) {
985 : : // If the common part matches, compare the lengths.
986 : 0 : diff = key1_len - key2_len;
987 : : // We dealt with the "same length" case above so we never need to check
988 : : // component_of here.
989 : : }
990 : 3 : return diff;
991 : : }
992 : :
993 : : }
994 : :
995 : : #ifdef DISABLE_GPL_LIBXAPIAN
996 : : # error GPL source we cannot relicense included in libxapian
997 : : #endif
998 : :
999 : : #endif /* XAPIAN_INCLUDED_GLASS_TABLE_H */
|
