Branch data Line data Source code
1 : : /* brass_table.cc: Btree implementation
2 : : *
3 : : * Copyright 1999,2000,2001 BrightStation PLC
4 : : * Copyright 2002 Ananova Ltd
5 : : * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010,2011 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 : : #include <config.h>
25 : :
26 : : #include "brass_table.h"
27 : :
28 : : #include <xapian/error.h>
29 : :
30 : : #include "safeerrno.h"
31 : : #ifdef __WIN32__
32 : : # include "msvc_posix_wrapper.h"
33 : : #endif
34 : :
35 : : #include "omassert.h"
36 : : #include "str.h"
37 : : #include "stringutils.h" // For STRINGIZE().
38 : :
39 : : // Define to use "dangerous" mode - in this mode we write modified btree
40 : : // blocks back in place. This is somewhat faster (especially once we're
41 : : // I/O bound) but the database can't be safely searched during indexing
42 : : // and if indexing is terminated uncleanly, the database may be corrupt.
43 : : //
44 : : // Despite the risks, it's useful for speeding up a full rebuild.
45 : : //
46 : : // FIXME: make this mode run-time selectable, and record that it is currently
47 : : // in use somewhere on disk, so readers can check and refuse to open the
48 : : // database.
49 : : //
50 : : // #define DANGEROUS
51 : :
52 : : #include <sys/types.h>
53 : :
54 : : // Trying to include the correct headers with the correct defines set to
55 : : // get pread() and pwrite() prototyped on every platform without breaking any
56 : : // other platform is a real can of worms. So instead we probe for what
57 : : // prototypes (if any) are required in configure and put them into
58 : : // PREAD_PROTOTYPE and PWRITE_PROTOTYPE.
59 : : #if defined HAVE_PREAD && defined PREAD_PROTOTYPE
60 : : PREAD_PROTOTYPE
61 : : #endif
62 : : #if defined HAVE_PWRITE && defined PWRITE_PROTOTYPE
63 : : PWRITE_PROTOTYPE
64 : : #endif
65 : :
66 : : #include <cstdio> /* for rename */
67 : : #include <cstring> /* for memmove */
68 : : #include <climits> /* for CHAR_BIT */
69 : :
70 : : #include "brass_btreebase.h"
71 : : #include "brass_cursor.h"
72 : :
73 : : #include "debuglog.h"
74 : : #include "io_utils.h"
75 : : #include "omassert.h"
76 : : #include "pack.h"
77 : : #include "unaligned.h"
78 : : #include "utils.h"
79 : :
80 : : #include <algorithm> // for std::min()
81 : : #include <string>
82 : :
83 : : using namespace Brass;
84 : : using namespace std;
85 : :
86 : : // Only try to compress tags longer than this many bytes.
87 : : const size_t COMPRESS_MIN = 4;
88 : :
89 : : //#define BTREE_DEBUG_FULL 1
90 : : #undef BTREE_DEBUG_FULL
91 : :
92 : : #ifdef BTREE_DEBUG_FULL
93 : : /*------debugging aids from here--------*/
94 : :
95 : : static void print_key(const byte * p, int c, int j);
96 : : static void print_tag(const byte * p, int c, int j);
97 : :
98 : : /*
99 : : static void report_cursor(int N, Btree * B, Brass::Cursor * C)
100 : : {
101 : : int i;
102 : : printf("%d)\n", N);
103 : : for (i = 0; i <= B->level; i++)
104 : : printf("p=%d, c=%d, n=[%d], rewrite=%d\n",
105 : : C[i].p, C[i].c, C[i].n, C[i].rewrite);
106 : : }
107 : : */
108 : :
109 : : /*------to here--------*/
110 : : #endif /* BTREE_DEBUG_FULL */
111 : :
112 : 11233 : static inline byte *zeroed_new(size_t size)
113 : : {
114 : 11233 : byte *temp = new byte[size];
115 : : // No need to check if temp is NULL, new throws std::bad_alloc if
116 : : // allocation fails.
117 : : Assert(temp);
118 : 11233 : memset(temp, 0, size);
119 : 11233 : return temp;
120 : : }
121 : :
122 : : /* A B-tree comprises (a) a base file, containing essential information (Block
123 : : size, number of the B-tree root block etc), (b) a bitmap, the Nth bit of the
124 : : bitmap being set if the Nth block of the B-tree file is in use, and (c) a
125 : : file DB containing the B-tree proper. The DB file is divided into a sequence
126 : : of equal sized blocks, numbered 0, 1, 2 ... some of which are free, some in
127 : : use. Those in use are arranged in a tree.
128 : :
129 : : Each block, b, has a structure like this:
130 : :
131 : : R L M T D o1 o2 o3 ... oN <gap> [item] .. [item] .. [item] ...
132 : : <---------- D ----------> <-M->
133 : :
134 : : And then,
135 : :
136 : : R = REVISION(b) is the revision number the B-tree had when the block was
137 : : written into the DB file.
138 : : L = GET_LEVEL(b) is the level of the block, which is the number of levels
139 : : towards the root of the B-tree structure. So leaf blocks
140 : : have level 0 and the one root block has the highest level
141 : : equal to the number of levels in the B-tree.
142 : : M = MAX_FREE(b) is the size of the gap between the end of the directory and
143 : : the first item of data. (It is not necessarily the maximum
144 : : size among the bits of space that are free, but I can't
145 : : think of a better name.)
146 : : T = TOTAL_FREE(b)is the total amount of free space left in b.
147 : : D = DIR_END(b) gives the offset to the end of the directory.
148 : :
149 : : o1, o2 ... oN are a directory of offsets to the N items held in the block.
150 : : The items are key-tag pairs, and as they occur in the directory are ordered
151 : : by the keys.
152 : :
153 : : An item has this form:
154 : :
155 : : I K key x C tag
156 : : <--K-->
157 : : <------I------>
158 : :
159 : : A long tag presented through the API is split up into C tags small enough to
160 : : be accommodated in the blocks of the B-tree. The key is extended to include
161 : : a counter, x, which runs from 1 to C. The key is preceded by a length, K,
162 : : and the whole item with a length, I, as depicted above.
163 : :
164 : : Here are the corresponding definitions:
165 : :
166 : : */
167 : :
168 : : /** Flip to sequential addition block-splitting after this number of observed
169 : : * sequential additions (in negated form). */
170 : : #define SEQ_START_POINT (-10)
171 : :
172 : : /* There are two bit maps in bit_map0 and bit_map. The nth bit of bitmap is 0
173 : : if the nth block is free, otherwise 1. bit_map0 is the initial state of
174 : : bitmap at the start of the current transaction.
175 : :
176 : : Note use of the limits.h values:
177 : : UCHAR_MAX = 255, an unsigned with all bits set, and
178 : : CHAR_BIT = 8, the number of bits per byte
179 : :
180 : : BYTE_PAIR_RANGE below is the smallest +ve number that can't be held in two
181 : : bytes -- 64K effectively.
182 : : */
183 : :
184 : : #define BYTE_PAIR_RANGE (1 << 2 * CHAR_BIT)
185 : :
186 : : /// read_block(n, p) reads block n of the DB file to address p.
187 : : void
188 : 6641155 : BrassTable::read_block(uint4 n, byte * p) const
189 : : {
190 : : // Log the value of p, not the contents of the block it points to...
191 : : LOGCALL_VOID(DB, "BrassTable::read_block", n | (void*)p);
192 : : /* Use the base bit_map_size not the bitmap's size, because
193 : : * the latter is uninitialised in readonly mode.
194 : : */
195 : : Assert(n / CHAR_BIT < base.get_bit_map_size());
196 : :
197 : : #ifdef HAVE_PREAD
198 : 6641155 : off_t offset = off_t(block_size) * n;
199 : 6641155 : int m = block_size;
200 : 0 : while (true) {
201 : : ssize_t bytes_read = pread(handle, reinterpret_cast<char *>(p), m,
202 : 6641155 : offset);
203 : : // normal case - read succeeded, so return.
204 [ + - ]: 6641155 : if (bytes_read == m) return;
205 [ # # ]: 0 : if (bytes_read == -1) {
206 [ # # ]: 0 : if (errno == EINTR) continue;
207 : 0 : string message = "Error reading block " + str(n) + ": ";
208 : 0 : message += strerror(errno);
209 : 0 : throw Xapian::DatabaseError(message);
210 [ # # ]: 0 : } else if (bytes_read == 0) {
211 : 0 : string message = "Error reading block " + str(n) + ": got end of file";
212 : 0 : throw Xapian::DatabaseError(message);
213 [ # # ]: 0 : } else if (bytes_read < m) {
214 : : /* Read part of the block, which is not an error. We should
215 : : * continue reading the rest of the block.
216 : : */
217 : 0 : m -= int(bytes_read);
218 : 0 : p += bytes_read;
219 : 0 : offset += bytes_read;
220 : : }
221 : : }
222 : : #else
223 : : if (lseek(handle, off_t(block_size) * n, SEEK_SET) == -1) {
224 : : string message = "Error seeking to block: ";
225 : : message += strerror(errno);
226 : : throw Xapian::DatabaseError(message);
227 : : }
228 : :
229 : : io_read(handle, reinterpret_cast<char *>(p), block_size, block_size);
230 : : #endif
231 : : }
232 : :
233 : : /** write_block(n, p) writes block n in the DB file from address p.
234 : : * When writing we check to see if the DB file has already been
235 : : * modified. If not (so this is the first write) the old base is
236 : : * deleted. This prevents the possibility of it being opened
237 : : * subsequently as an invalid base.
238 : : */
239 : : void
240 : 321693 : BrassTable::write_block(uint4 n, const byte * p) const
241 : : {
242 : : LOGCALL_VOID(DB, "BrassTable::write_block", n | p);
243 : : Assert(writable);
244 : : /* Check that n is in range. */
245 : : Assert(n / CHAR_BIT < base.get_bit_map_size());
246 : :
247 : : /* don't write to non-free */;
248 : : AssertParanoid(base.block_free_at_start(n));
249 : :
250 : : /* write revision is okay */
251 : : AssertEqParanoid(REVISION(p), latest_revision_number + 1);
252 : :
253 [ + + ]: 321693 : if (both_bases) {
254 : : // Delete the old base before modifying the database.
255 : : //
256 : : // If the file is on NFS, then io_unlink() may return false even if
257 : : // the file was removed, so on balance throwing an exception in this
258 : : // case is unhelpful, since we wanted the file gone anyway! The
259 : : // likely explanation is that somebody moved, deleted, or changed a
260 : : // symlink to the database directory.
261 : 586 : (void)io_unlink(name + "base" + other_base_letter());
262 : 586 : both_bases = false;
263 : 586 : latest_revision_number = revision_number;
264 : : }
265 : :
266 : : #ifdef HAVE_PWRITE
267 : 321693 : off_t offset = off_t(block_size) * n;
268 : 321693 : int m = block_size;
269 : 0 : while (true) {
270 : 321693 : ssize_t bytes_written = pwrite(handle, p, m, offset);
271 [ + - ]: 321693 : if (bytes_written == m) {
272 : : // normal case - write succeeded, so return.
273 : : return;
274 [ # # ]: 0 : } else if (bytes_written == -1) {
275 [ # # ]: 0 : if (errno == EINTR) continue;
276 : 0 : string message = "Error writing block: ";
277 : 0 : message += strerror(errno);
278 : 0 : throw Xapian::DatabaseError(message);
279 [ # # ]: 0 : } else if (bytes_written == 0) {
280 : 0 : string message = "Error writing block: wrote no data";
281 : 0 : throw Xapian::DatabaseError(message);
282 [ # # ]: 0 : } else if (bytes_written < m) {
283 : : /* Wrote part of the block, which is not an error. We should
284 : : * continue writing the rest of the block.
285 : : */
286 : 0 : m -= bytes_written;
287 : 0 : p += bytes_written;
288 : 0 : offset += bytes_written;
289 : : }
290 : : }
291 : : #else
292 : : if (lseek(handle, (off_t)block_size * n, SEEK_SET) == -1) {
293 : : string message = "Error seeking to block: ";
294 : : message += strerror(errno);
295 : : throw Xapian::DatabaseError(message);
296 : : }
297 : :
298 : : io_write(handle, reinterpret_cast<const char *>(p), block_size);
299 : : #endif
300 : : }
301 : :
302 : :
303 : : /* A note on cursors:
304 : :
305 : : Each B-tree level has a corresponding array element C[j] in a
306 : : cursor, C. C[0] is the leaf (or data) level, and C[B->level] is the
307 : : root block level. Within a level j,
308 : :
309 : : C[j].p addresses the block
310 : : C[j].c is the offset into the directory entry in the block
311 : : C[j].n is the number of the block at C[j].p
312 : :
313 : : A look up in the B-tree causes navigation of the blocks starting
314 : : from the root. In each block, p, we find an offset, c, to an item
315 : : which gives the number, n, of the block for the next level. This
316 : : leads to an array of values p,c,n which are held inside the cursor.
317 : :
318 : : Any Btree object B has a built-in cursor, at B->C. But other cursors may
319 : : be created. If BC is a created cursor, BC->C is the cursor in the
320 : : sense given above, and BC->B is the handle for the B-tree again.
321 : : */
322 : :
323 : :
324 : : void
325 : 5 : BrassTable::set_overwritten() const
326 : : {
327 : : LOGCALL_VOID(DB, "BrassTable::set_overwritten", NO_ARGS);
328 : : // If we're writable, there shouldn't be another writer who could cause
329 : : // overwritten to be flagged, so that's a DatabaseCorruptError.
330 [ - + ]: 5 : if (writable)
331 : 0 : throw Xapian::DatabaseCorruptError("Db block overwritten - are there multiple writers?");
332 : 5 : throw Xapian::DatabaseModifiedError("The revision being read has been discarded - you should call Xapian::Database::reopen() and retry the operation");
333 : : }
334 : :
335 : : /* block_to_cursor(C, j, n) puts block n into position C[j] of cursor
336 : : C, writing the block currently at C[j] back to disk if necessary.
337 : : Note that
338 : :
339 : : C[j].rewrite
340 : :
341 : : is true iff C[j].n is different from block n in file DB. If it is
342 : : false no rewriting is necessary.
343 : : */
344 : :
345 : : void
346 : 9520865 : BrassTable::block_to_cursor(Brass::Cursor * C_, int j, uint4 n) const
347 : : {
348 : : LOGCALL_VOID(DB, "BrassTable::block_to_cursor", (void*)C_ | j | n);
349 [ + + ]: 9520865 : if (n == C_[j].n) return;
350 : 6822148 : byte * p = C_[j].p;
351 : : Assert(p);
352 : :
353 : : // FIXME: only needs to be done in write mode
354 [ + + ]: 6822148 : if (C_[j].rewrite) {
355 : : Assert(writable);
356 : : Assert(C == C_);
357 : 303081 : write_block(C_[j].n, p);
358 : 303081 : C_[j].rewrite = false;
359 : : }
360 : :
361 : : // Check if the block is in the built-in cursor (potentially in
362 : : // modified form).
363 [ + + ][ + + ]: 7018081 : if (writable && n == C[j].n) {
364 [ + - ]: 195933 : if (p != C[j].p)
365 : 195933 : memcpy(p, C[j].p, block_size);
366 : : } else {
367 : 6626215 : read_block(n, p);
368 : : }
369 : :
370 : 6822148 : C_[j].n = n;
371 [ + + ]: 6822148 : if (j < level) {
372 : : /* unsigned comparison */
373 [ + + ]: 6814092 : if (rare(REVISION(p) > REVISION(C_[j + 1].p))) {
374 : 5 : set_overwritten();
375 : : return;
376 : : }
377 : : }
378 : :
379 [ - + ]: 6822143 : if (rare(j != GET_LEVEL(p))) {
380 : 0 : string msg = "Expected block ";
381 : 0 : msg += str(j);
382 : 0 : msg += ", not ";
383 : 0 : msg += str(GET_LEVEL(p));
384 : 9520860 : throw Xapian::DatabaseCorruptError(msg);
385 : : }
386 : : }
387 : :
388 : : /** Btree::alter(); is called when the B-tree is to be altered.
389 : :
390 : : It causes new blocks to be forced for the current set of blocks in
391 : : the cursor.
392 : :
393 : : The point is that if a block at level 0 is to be altered it may get
394 : : a new number. Then the pointer to this block from level 1 will need
395 : : changing. So the block at level 1 needs altering and may get a new
396 : : block number. Then the pointer to this block from level 2 will need
397 : : changing ... and so on back to the root.
398 : :
399 : : The clever bit here is spotting the cases when we can make an early
400 : : exit from this process. If C[j].rewrite is true, C[j+k].rewrite
401 : : will be true for k = 1,2 ... We have been through all this before,
402 : : and there is no need to do it again. If C[j].n was free at the
403 : : start of the transaction, we can copy it back to the same place
404 : : without violating the integrity of the B-tree. We don't then need a
405 : : new n and can return. The corresponding C[j].rewrite may be true or
406 : : false in that case.
407 : : */
408 : :
409 : : void
410 : 1401740 : BrassTable::alter()
411 : : {
412 : : LOGCALL_VOID(DB, "BrassTable::alter", NO_ARGS);
413 : : Assert(writable);
414 : : #ifdef DANGEROUS
415 : : C[0].rewrite = true;
416 : : #else
417 : 1401740 : int j = 0;
418 : 1401740 : byte * p = C[j].p;
419 : 1402634 : while (true) {
420 [ + + ]: 1402634 : if (C[j].rewrite) return; /* all new, so return */
421 : 303912 : C[j].rewrite = true;
422 : :
423 : 303912 : uint4 n = C[j].n;
424 [ + + ]: 303912 : if (base.block_free_at_start(n)) {
425 : : Assert(REVISION(p) == latest_revision_number + 1);
426 : 302425 : return;
427 : : }
428 : : Assert(REVISION(p) < latest_revision_number + 1);
429 : 1487 : base.free_block(n);
430 : 1487 : n = base.next_free_block();
431 : 1487 : C[j].n = n;
432 : 1487 : SET_REVISION(p, latest_revision_number + 1);
433 : :
434 [ + + ]: 1487 : if (j == level) return;
435 : 894 : j++;
436 : 894 : p = C[j].p;
437 : 894 : Item_wr(p, C[j].c).set_block_given_by(n);
438 : : }
439 : : #endif
440 : : }
441 : :
442 : : /** find_in_block(p, key, leaf, c) searches for the key in the block at p.
443 : :
444 : : leaf is true for a data block, and false for an index block (when the
445 : : first key is dummy and never needs to be tested). What we get is the
446 : : directory entry to the last key <= the key being searched for.
447 : :
448 : : The lookup is by binary chop, with i and j set to the left and
449 : : right ends of the search area. In sequential addition, c will often
450 : : be the answer, so we test the keys round c and move i and j towards
451 : : c if possible.
452 : : */
453 : :
454 : : int
455 : 11611641 : BrassTable::find_in_block(const byte * p, Key key, bool leaf, int c)
456 : : {
457 : : LOGCALL_STATIC(DB, int, "BrassTable::find_in_block", (void*)p | (const void *)key.get_address() | leaf | c);
458 : 11611641 : int i = DIR_START;
459 [ + + ]: 11611641 : if (leaf) i -= D2;
460 : 11611641 : int j = DIR_END(p);
461 : :
462 [ + + ]: 11611641 : if (c != -1) {
463 [ + + ][ + + ]: 5870586 : if (c < j && i < c && Item(p, c).key() <= key)
[ + + ][ + + ]
464 : 5172917 : i = c;
465 : 5870586 : c += D2;
466 [ + + ][ + + ]: 5870586 : if (c < j && i < c && key < Item(p, c).key())
[ + + ][ + + ]
467 : 1618359 : j = c;
468 : : }
469 : :
470 [ + + ]: 41654167 : while (j - i > D2) {
471 : 30042526 : int k = i + ((j - i)/(D2 * 2))*D2; /* mid way */
472 [ + + ]: 30042526 : if (key < Item(p, k).key()) j = k; else i = k;
473 : : }
474 : 11611641 : RETURN(i);
475 : : }
476 : :
477 : : /** find(C_) searches for the key of B->kt in the B-tree.
478 : :
479 : : Result is true if found, false otherwise. When false, the B_tree
480 : : cursor is positioned at the last key in the B-tree <= the search
481 : : key. Goes to first (null) item in B-tree when key length == 0.
482 : : */
483 : :
484 : : bool
485 : 4541018 : BrassTable::find(Brass::Cursor * C_) const
486 : : {
487 : : LOGCALL(DB, bool, "BrassTable::find", (void*)C_);
488 : : // Note: the parameter is needed when we're called by BrassCursor
489 : : const byte * p;
490 : : int c;
491 : 4541018 : Key key = kt.key();
492 [ + + ]: 11594916 : for (int j = level; j > 0; --j) {
493 : 7053903 : p = C_[j].p;
494 : 7053903 : c = find_in_block(p, key, false, C_[j].c);
495 : : #ifdef BTREE_DEBUG_FULL
496 : : printf("Block in BrassTable:find - code position 1");
497 : : report_block_full(j, C_[j].n, p);
498 : : #endif /* BTREE_DEBUG_FULL */
499 : 7053903 : C_[j].c = c;
500 : 7053903 : block_to_cursor(C_, j - 1, Item(p, c).block_given_by());
501 : : }
502 : 4541013 : p = C_[0].p;
503 : 4541013 : c = find_in_block(p, key, true, C_[0].c);
504 : : #ifdef BTREE_DEBUG_FULL
505 : : printf("Block in BrassTable:find - code position 2");
506 : : report_block_full(0, C_[0].n, p);
507 : : #endif /* BTREE_DEBUG_FULL */
508 : 4541013 : C_[0].c = c;
509 [ + + ]: 4541013 : if (c < DIR_START) RETURN(false);
510 : 4541013 : RETURN(Item(p, c).key() == key);
511 : : }
512 : :
513 : : /** compact(p) compact the block at p by shuffling all the items up to the end.
514 : :
515 : : MAX_FREE(p) is then maximized, and is equal to TOTAL_FREE(p).
516 : : */
517 : :
518 : : void
519 : 34605 : BrassTable::compact(byte * p)
520 : : {
521 : : LOGCALL_VOID(DB, "BrassTable::compact", (void*)p);
522 : : Assert(writable);
523 : 34605 : int e = block_size;
524 : 34605 : byte * b = buffer;
525 : 34605 : int dir_end = DIR_END(p);
526 [ + + ]: 1734765 : for (int c = DIR_START; c < dir_end; c += D2) {
527 : 1700160 : Item item(p, c);
528 : 1700160 : int l = item.size();
529 : 1700160 : e -= l;
530 : 1700160 : memmove(b + e, item.get_address(), l);
531 : 1700160 : setD(p, c, e); /* reform in b */
532 : : }
533 : 34605 : memmove(p + e, b + e, block_size - e); /* copy back */
534 : 34605 : e -= dir_end;
535 : 34605 : SET_TOTAL_FREE(p, e);
536 : 34605 : SET_MAX_FREE(p, e);
537 : 34605 : }
538 : :
539 : : /** Btree needs to gain a new level to insert more items: so split root block
540 : : * and construct a new one.
541 : : */
542 : : void
543 : 206 : BrassTable::split_root(uint4 split_n)
544 : : {
545 : : LOGCALL_VOID(DB, "BrassTable::split_root", split_n);
546 : : /* gain a level */
547 : 206 : ++level;
548 : :
549 : : /* check level overflow - this isn't something that should ever happen
550 : : * but deserves more than an Assert()... */
551 [ - + ]: 206 : if (level == BTREE_CURSOR_LEVELS) {
552 : 0 : throw Xapian::DatabaseCorruptError("Btree has grown impossibly large ("STRINGIZE(BTREE_CURSOR_LEVELS)" levels)");
553 : : }
554 : :
555 : 206 : byte * q = zeroed_new(block_size);
556 : 206 : C[level].p = q;
557 : 206 : C[level].c = DIR_START;
558 : 206 : C[level].n = base.next_free_block();
559 : 206 : C[level].rewrite = true;
560 : 206 : SET_REVISION(q, latest_revision_number + 1);
561 : 206 : SET_LEVEL(q, level);
562 : 206 : SET_DIR_END(q, DIR_START);
563 : 206 : compact(q); /* to reset TOTAL_FREE, MAX_FREE */
564 : :
565 : : /* form a null key in b with a pointer to the old root */
566 : : byte b[10]; /* 7 is exact */
567 : 206 : Item_wr item(b);
568 : 206 : item.form_null_key(split_n);
569 : 206 : add_item(item, level);
570 : 206 : }
571 : :
572 : : /** enter_key(j, prevkey, newkey) is called after a block split.
573 : :
574 : : It enters in the block at level C[j] a separating key for the block
575 : : at level C[j - 1]. The key itself is newkey. prevkey is the
576 : : preceding key, and at level 1 newkey can be trimmed down to the
577 : : first point of difference to prevkey for entry in C[j].
578 : :
579 : : This code looks longer than it really is. If j exceeds the number
580 : : of B-tree levels the root block has split and we have to construct
581 : : a new one, but this is a rare event.
582 : :
583 : : The key is constructed in b, with block number C[j - 1].n as tag,
584 : : and this is added in with add_item. add_item may itself cause a
585 : : block split, with a further call to enter_key. Hence the recursion.
586 : : */
587 : : void
588 : 16725 : BrassTable::enter_key(int j, Key prevkey, Key newkey)
589 : : {
590 : : LOGCALL_VOID(DB, "BrassTable::enter_key", j | Literal("prevkey") | Literal("newkey"));
591 : : Assert(writable);
592 : : Assert(prevkey < newkey);
593 : : AssertRel(j,>=,1);
594 : :
595 : 16725 : uint4 blocknumber = C[j - 1].n;
596 : :
597 : : // FIXME update to use Key
598 : : // Keys are truncated here: but don't truncate the count at the end away.
599 : 16725 : const int newkey_len = newkey.length();
600 : : AssertRel(newkey_len,>,0);
601 : : int i;
602 : :
603 [ + + ]: 16725 : if (j == 1) {
604 : : // Truncate the key to the minimal key which differs from prevkey,
605 : : // the preceding key in the block.
606 : 16601 : i = 0;
607 : 16601 : const int min_len = min(newkey_len, prevkey.length());
608 [ + + ][ + + ]: 89084 : while (i < min_len && prevkey[i] == newkey[i]) {
[ + + ]
609 : 72483 : i++;
610 : : }
611 : :
612 : : // Want one byte of difference.
613 [ + + ]: 16601 : if (i < newkey_len) i++;
614 : : } else {
615 : : /* Can't truncate between branch levels, since the separated keys
616 : : * are in at the leaf level, and truncating again will change the
617 : : * branch point.
618 : : */
619 : 124 : i = newkey_len;
620 : : }
621 : :
622 : : byte b[UCHAR_MAX + 6];
623 : 16725 : Item_wr item(b);
624 : : Assert(i <= 256 - I2 - C2);
625 : : Assert(i <= (int)sizeof(b) - I2 - C2 - 4);
626 : 16725 : item.set_key_and_block(newkey, i, blocknumber);
627 : :
628 : : // When j > 1 we can make the first key of block p null. This is probably
629 : : // worthwhile as it trades a small amount of CPU and RAM use for a small
630 : : // saving in disk use. Other redundant keys will still creep in though.
631 [ + + ]: 16725 : if (j > 1) {
632 : 124 : byte * p = C[j - 1].p;
633 : 124 : uint4 n = getint4(newkey.get_address(), newkey_len + K1 + C2);
634 : 124 : int new_total_free = TOTAL_FREE(p) + newkey_len + C2;
635 : : // FIXME: incredibly icky going from key to item like this...
636 : 124 : Item_wr(const_cast<byte*>(newkey.get_address()) - I2).form_null_key(n);
637 : 124 : SET_TOTAL_FREE(p, new_total_free);
638 : : }
639 : :
640 : 16725 : C[j].c = find_in_block(C[j].p, item.key(), false, 0) + D2;
641 : 16725 : C[j].rewrite = true; /* a subtle point: this *is* required. */
642 : 16725 : add_item(item, j);
643 : 16725 : }
644 : :
645 : : /** mid_point(p) finds the directory entry in c that determines the
646 : : approximate mid point of the data in the block at p.
647 : : */
648 : :
649 : : int
650 : 7823 : BrassTable::mid_point(byte * p)
651 : : {
652 : : LOGCALL(DB, int, "BrassTable::mid_point", (void*)p);
653 : 7823 : int n = 0;
654 : 7823 : int dir_end = DIR_END(p);
655 : 7823 : int size = block_size - TOTAL_FREE(p) - dir_end;
656 [ + - ]: 346567 : for (int c = DIR_START; c < dir_end; c += D2) {
657 : 346567 : int l = Item(p, c).size();
658 : 346567 : n += 2 * l;
659 [ + + ]: 346567 : if (n >= size) {
660 [ + + ]: 7823 : if (l < n - size) RETURN(c);
661 : 4319 : RETURN(c + D2);
662 : : }
663 : : }
664 : :
665 : : /* falling out of mid_point */
666 : : Assert(false);
667 : 7823 : RETURN(0); /* Stop compiler complaining about end of method. */
668 : : }
669 : :
670 : : /** add_item_to_block(p, kt_, c) adds item kt_ to the block at p.
671 : :
672 : : c is the offset in the directory that needs to be expanded to accommodate
673 : : the new entry for the item. We know before this is called that there is
674 : : enough contiguous room for the item in the block, so it's just a matter of
675 : : shuffling up any directory entries after where we're inserting and copying
676 : : in the item.
677 : : */
678 : :
679 : : void
680 : 1334868 : BrassTable::add_item_to_block(byte * p, Item_wr kt_, int c)
681 : : {
682 : : LOGCALL_VOID(DB, "BrassTable::add_item_to_block", (void*)p | Literal("kt_") | c);
683 : : Assert(writable);
684 : 1334868 : int dir_end = DIR_END(p);
685 : 1334868 : int kt_len = kt_.size();
686 : 1334868 : int needed = kt_len + D2;
687 : 1334868 : int new_total = TOTAL_FREE(p) - needed;
688 : 1334868 : int new_max = MAX_FREE(p) - needed;
689 : :
690 : : Assert(new_total >= 0);
691 : :
692 : : AssertRel(MAX_FREE(p),>=,needed);
693 : :
694 : : Assert(dir_end >= c);
695 : :
696 : 1334868 : memmove(p + c + D2, p + c, dir_end - c);
697 : 1334868 : dir_end += D2;
698 : 1334868 : SET_DIR_END(p, dir_end);
699 : :
700 : 1334868 : int o = dir_end + new_max;
701 : 1334868 : setD(p, c, o);
702 : 1334868 : memmove(p + o, kt_.get_address(), kt_len);
703 : :
704 : 1334868 : SET_MAX_FREE(p, new_max);
705 : :
706 : 1334868 : SET_TOTAL_FREE(p, new_total);
707 : 1334868 : }
708 : :
709 : : /** BrassTable::add_item(kt_, j) adds item kt_ to the block at cursor level C[j].
710 : : *
711 : : * If there is not enough room the block splits and the item is then
712 : : * added to the appropriate half.
713 : : */
714 : : void
715 : 1334868 : BrassTable::add_item(Item_wr kt_, int j)
716 : : {
717 : : LOGCALL_VOID(DB, "BrassTable::add_item", Literal("kt_") | j);
718 : : Assert(writable);
719 : 1334868 : byte * p = C[j].p;
720 : 1334868 : int c = C[j].c;
721 : : uint4 n;
722 : :
723 : 1334868 : int needed = kt_.size() + D2;
724 [ + + ]: 1334868 : if (TOTAL_FREE(p) < needed) {
725 : : int m;
726 : : // Prepare to split p. After splitting, the block is in two halves, the
727 : : // lower half is split_p, the upper half p again. add_to_upper_half
728 : : // becomes true when the item gets added to p, false when it gets added
729 : : // to split_p.
730 : :
731 [ + + ]: 16725 : if (seq_count < 0) {
732 : : // If we're not in sequential mode, we split at the mid point
733 : : // of the node.
734 : 7823 : m = mid_point(p);
735 : : } else {
736 : : // During sequential addition, split at the insert point
737 : 8902 : m = c;
738 : : }
739 : :
740 : 16725 : uint4 split_n = C[j].n;
741 : 16725 : C[j].n = base.next_free_block();
742 : :
743 : 16725 : memcpy(split_p, p, block_size); // replicate the whole block in split_p
744 : 16725 : SET_DIR_END(split_p, m);
745 : 16725 : compact(split_p); /* to reset TOTAL_FREE, MAX_FREE */
746 : :
747 : : {
748 : 16725 : int residue = DIR_END(p) - m;
749 : 16725 : int new_dir_end = DIR_START + residue;
750 : 16725 : memmove(p + DIR_START, p + m, residue);
751 : 16725 : SET_DIR_END(p, new_dir_end);
752 : : }
753 : :
754 : 16725 : compact(p); /* to reset TOTAL_FREE, MAX_FREE */
755 : :
756 : : bool add_to_upper_half;
757 [ + + ]: 16725 : if (seq_count < 0) {
758 : 7823 : add_to_upper_half = (c >= m);
759 : : } else {
760 : : // And add item to lower half if split_p has room, otherwise upper
761 : : // half
762 : 8902 : add_to_upper_half = (TOTAL_FREE(split_p) < needed);
763 : : }
764 : :
765 [ + + ]: 16725 : if (add_to_upper_half) {
766 : 15175 : c -= (m - DIR_START);
767 : : Assert(seq_count < 0 || c <= DIR_START + D2);
768 : : Assert(c >= DIR_START);
769 : : Assert(c <= DIR_END(p));
770 : 15175 : add_item_to_block(p, kt_, c);
771 : 15175 : n = C[j].n;
772 : : } else {
773 : : Assert(c >= DIR_START);
774 : : Assert(c <= DIR_END(split_p));
775 : 1550 : add_item_to_block(split_p, kt_, c);
776 : 1550 : n = split_n;
777 : : }
778 : 16725 : write_block(split_n, split_p);
779 : :
780 : : // Check if we're splitting the root block.
781 [ + + ]: 16725 : if (j == level) split_root(split_n);
782 : :
783 : : /* Enter a separating key at level j + 1 between */
784 : : /* the last key of block split_p, and the first key of block p */
785 : : enter_key(j + 1,
786 : : Item(split_p, DIR_END(split_p) - D2).key(),
787 : 16725 : Item(p, DIR_START).key());
788 : : } else {
789 : : AssertRel(TOTAL_FREE(p),>=,needed);
790 : :
791 [ + + ]: 1318143 : if (MAX_FREE(p) < needed) {
792 : 949 : compact(p);
793 : : AssertRel(MAX_FREE(p),>=,needed);
794 : : }
795 : :
796 : 1318143 : add_item_to_block(p, kt_, c);
797 : 1318143 : n = C[j].n;
798 : : }
799 [ + + ]: 1334868 : if (j == 0) {
800 : 1317937 : changed_n = n;
801 : 1317937 : changed_c = c;
802 : : }
803 : 1334868 : }
804 : :
805 : : /** BrassTable::delete_item(j, repeatedly) is (almost) the converse of add_item.
806 : : *
807 : : * If repeatedly is true, the process repeats at the next level when a
808 : : * block has been completely emptied, freeing the block and taking out
809 : : * the pointer to it. Emptied root blocks are also removed, which
810 : : * reduces the number of levels in the B-tree.
811 : : */
812 : : void
813 : 43330 : BrassTable::delete_item(int j, bool repeatedly)
814 : : {
815 : : LOGCALL_VOID(DB, "BrassTable::delete_item", j | repeatedly);
816 : : Assert(writable);
817 : 43330 : byte * p = C[j].p;
818 : 43330 : int c = C[j].c;
819 : 43330 : int kt_len = Item(p, c).size(); /* size of the item to be deleted */
820 : 43330 : int dir_end = DIR_END(p) - D2; /* directory length will go down by 2 bytes */
821 : :
822 : 43330 : memmove(p + c, p + c + D2, dir_end - c);
823 : 43330 : SET_DIR_END(p, dir_end);
824 : 43330 : SET_MAX_FREE(p, MAX_FREE(p) + D2);
825 : 43330 : SET_TOTAL_FREE(p, TOTAL_FREE(p) + kt_len + D2);
826 : :
827 [ + + ]: 43330 : if (!repeatedly) return;
828 [ + + ]: 42116 : if (j < level) {
829 [ + + ]: 41215 : if (dir_end == DIR_START) {
830 : 410 : base.free_block(C[j].n);
831 : 410 : C[j].rewrite = false;
832 : 410 : C[j].n = BLK_UNUSED;
833 : 410 : C[j + 1].rewrite = true; /* *is* necessary */
834 : 410 : delete_item(j + 1, true);
835 : : }
836 : : } else {
837 : : Assert(j == level);
838 [ + + ][ + + ]: 43345 : while (dir_end == DIR_START + D2 && level > 0) {
[ + + ]
839 : : /* single item in the root block, so lose a level */
840 : 15 : uint4 new_root = Item(p, DIR_START).block_given_by();
841 [ + - ]: 15 : delete [] p;
842 : 15 : C[level].p = 0;
843 : 15 : base.free_block(C[level].n);
844 : 15 : C[level].rewrite = false;
845 : 15 : C[level].n = BLK_UNUSED;
846 : 15 : level--;
847 : :
848 : 15 : block_to_cursor(C, level, new_root);
849 : :
850 : 15 : p = C[level].p;
851 : 15 : dir_end = DIR_END(p); /* prepare for the loop */
852 : : }
853 : : }
854 : : }
855 : :
856 : : /* debugging aid:
857 : : static addcount = 0;
858 : : */
859 : :
860 : : /** add_kt(found) adds the item (key-tag pair) at B->kt into the
861 : : B-tree, using cursor C.
862 : :
863 : : found == find() is handed over as a parameter from Btree::add.
864 : : Btree::alter() prepares for the alteration to the B-tree. Then
865 : : there are a number of cases to consider:
866 : :
867 : : If an item with the same key is in the B-tree (found is true),
868 : : the new kt replaces it.
869 : :
870 : : If then kt is smaller, or the same size as, the item it replaces,
871 : : kt is put in the same place as the item it replaces, and the
872 : : TOTAL_FREE measure is reduced.
873 : :
874 : : If kt is larger than the item it replaces it is put in the
875 : : MAX_FREE space if there is room, and the directory entry and
876 : : space counts are adjusted accordingly.
877 : :
878 : : - But if there is not room we do it the long way: the old item is
879 : : deleted with delete_item and kt is added in with add_item.
880 : :
881 : : If the key of kt is not in the B-tree (found is false), the new
882 : : kt is added in with add_item.
883 : : */
884 : :
885 : : int
886 : 1360034 : BrassTable::add_kt(bool found)
887 : : {
888 : : LOGCALL(DB, int, "BrassTable::add_kt", found);
889 : : Assert(writable);
890 : 1360034 : int components = 0;
891 : :
892 : : /*
893 : : {
894 : : printf("%d) %s ", addcount++, (found ? "replacing" : "adding"));
895 : : print_bytes(kt[I2] - K1 - C2, kt + I2 + K1); putchar('\n');
896 : : }
897 : : */
898 : 1360034 : alter();
899 : :
900 [ + + ]: 1360034 : if (found) { /* replacement */
901 : 43311 : seq_count = SEQ_START_POINT;
902 : 43311 : sequential = false;
903 : :
904 : 43311 : byte * p = C[0].p;
905 : 43311 : int c = C[0].c;
906 : 43311 : Item item(p, c);
907 : 43311 : int kt_size = kt.size();
908 : 43311 : int needed = kt_size - item.size();
909 : :
910 : 43311 : components = item.components_of();
911 : :
912 [ + + ]: 43311 : if (needed <= 0) {
913 : : /* simple replacement */
914 : : memmove(const_cast<byte *>(item.get_address()),
915 : 35612 : kt.get_address(), kt_size);
916 : 35612 : SET_TOTAL_FREE(p, TOTAL_FREE(p) - needed);
917 : : } else {
918 : : /* new item into the block's freespace */
919 : 7699 : int new_max = MAX_FREE(p) - kt_size;
920 [ + + ]: 7699 : if (new_max >= 0) {
921 : 6485 : int o = DIR_END(p) + new_max;
922 : 6485 : memmove(p + o, kt.get_address(), kt_size);
923 : 6485 : setD(p, c, o);
924 : 6485 : SET_MAX_FREE(p, new_max);
925 : 6485 : SET_TOTAL_FREE(p, TOTAL_FREE(p) - needed);
926 : : } else {
927 : : /* do it the long way */
928 : 1214 : delete_item(0, false);
929 : 1214 : add_item(kt, 0);
930 : : }
931 : : }
932 : : } else {
933 : : /* addition */
934 [ + + ][ + + ]: 2265675 : if (changed_n == C[0].n && changed_c == C[0].c) {
935 [ + + ]: 948952 : if (seq_count < 0) seq_count++;
936 : : } else {
937 : 367771 : seq_count = SEQ_START_POINT;
938 : 367771 : sequential = false;
939 : : }
940 : 1316723 : C[0].c += D2;
941 : 1316723 : add_item(kt, 0);
942 : : }
943 : 1360034 : RETURN(components);
944 : : }
945 : :
946 : : /* delete_kt() corresponds to add_kt(found), but there are only
947 : : two cases: if the key is not found nothing is done, and if it is
948 : : found the corresponding item is deleted with delete_item.
949 : : */
950 : :
951 : : int
952 : 41846 : BrassTable::delete_kt()
953 : : {
954 : : LOGCALL(DB, int, "BrassTable::delete_kt", NO_ARGS);
955 : : Assert(writable);
956 : :
957 : 41846 : bool found = find(C);
958 : :
959 : 41846 : int components = 0;
960 : 41846 : seq_count = SEQ_START_POINT;
961 : 41846 : sequential = false;
962 : :
963 : : /*
964 : : {
965 : : printf("%d) %s ", addcount++, (found ? "deleting " : "ignoring "));
966 : : print_bytes(B->kt[I2] - K1 - C2, B->kt + I2 + K1); putchar('\n');
967 : : }
968 : : */
969 [ + + ]: 41846 : if (found) {
970 : 41706 : components = Item(C[0].p, C[0].c).components_of();
971 : 41706 : alter();
972 : 41706 : delete_item(0, true);
973 : : }
974 : 41846 : RETURN(components);
975 : : }
976 : :
977 : : /* BrassTable::form_key(key) treats address kt as an item holder and fills in
978 : : the key part:
979 : :
980 : : (I) K key c (C tag)
981 : :
982 : : The bracketed parts are left blank. The key is filled in with key_len bytes and
983 : : K set accordingly. c is set to 1.
984 : : */
985 : :
986 : 4532321 : void BrassTable::form_key(const string & key) const
987 : : {
988 : : LOGCALL_VOID(DB, "BrassTable::form_key", key);
989 : 4532321 : kt.form_key(key);
990 : 4532313 : }
991 : :
992 : : /* BrassTable::add(key, tag) adds the key/tag item to the
993 : : B-tree, replacing any existing item with the same key.
994 : :
995 : : For a long tag, we end up having to add m components, of the form
996 : :
997 : : key 1 m tag1
998 : : key 2 m tag2
999 : : ...
1000 : : key m m tagm
1001 : :
1002 : : and tag1+tag2+...+tagm are equal to tag. These in their turn may be replacing
1003 : : n components of the form
1004 : :
1005 : : key 1 n TAG1
1006 : : key 2 n TAG2
1007 : : ...
1008 : : key n n TAGn
1009 : :
1010 : : and n may be greater than, equal to, or less than m. These cases are dealt
1011 : : with in the code below. If m < n for example, we end up with a series of
1012 : : deletions.
1013 : : */
1014 : :
1015 : : void
1016 : 1351704 : BrassTable::add(const string &key, string tag, bool already_compressed)
1017 : : {
1018 : : LOGCALL_VOID(DB, "BrassTable::add", key | tag | already_compressed);
1019 : : Assert(writable);
1020 : :
1021 [ + + ]: 1351704 : if (handle < 0) create_and_open(block_size);
1022 : :
1023 : 1351704 : form_key(key);
1024 : :
1025 : 1351696 : bool compressed = false;
1026 [ + + ]: 1351696 : if (already_compressed) {
1027 : 157 : compressed = true;
1028 [ + + ][ + + ]: 1351539 : } else if (compress_strategy != DONT_COMPRESS && tag.size() > COMPRESS_MIN) {
[ + + ]
1029 : : CompileTimeAssert(DONT_COMPRESS != Z_DEFAULT_STRATEGY);
1030 : : CompileTimeAssert(DONT_COMPRESS != Z_FILTERED);
1031 : : CompileTimeAssert(DONT_COMPRESS != Z_HUFFMAN_ONLY);
1032 : : #ifdef Z_RLE
1033 : : CompileTimeAssert(DONT_COMPRESS != Z_RLE);
1034 : : #endif
1035 : :
1036 : 58202 : lazy_alloc_deflate_zstream();
1037 : :
1038 : 58202 : deflate_zstream->next_in = (Bytef *)const_cast<char *>(tag.data());
1039 : 58202 : deflate_zstream->avail_in = (uInt)tag.size();
1040 : :
1041 : : // If compressed size is >= tag.size(), we don't want to compress.
1042 : 58202 : unsigned long blk_len = tag.size() - 1;
1043 : 58202 : unsigned char * blk = new unsigned char[blk_len];
1044 : 58202 : deflate_zstream->next_out = blk;
1045 : 58202 : deflate_zstream->avail_out = (uInt)blk_len;
1046 : :
1047 : 58202 : int err = deflate(deflate_zstream, Z_FINISH);
1048 [ + + ]: 58202 : if (err == Z_STREAM_END) {
1049 : : // If deflate succeeded, then the output was at least one byte
1050 : : // smaller than the input.
1051 : 14632 : tag.assign(reinterpret_cast<const char *>(blk), deflate_zstream->total_out);
1052 : 14632 : compressed = true;
1053 : : } else {
1054 : : // Deflate failed - presumably the data wasn't compressible.
1055 : : }
1056 : :
1057 [ + - ]: 58202 : delete [] blk;
1058 : : }
1059 : :
1060 : : // sort of matching kt.append_chunk(), but setting the chunk
1061 : 1351696 : const size_t cd = kt.key().length() + K1 + I2 + C2 + C2; // offset to the tag data
1062 : 1351696 : const size_t L = max_item_size - cd; // largest amount of tag data for any chunk
1063 : 1351696 : size_t first_L = L; // - amount for tag1
1064 : 1351696 : bool found = find(C);
1065 [ + + ]: 1351696 : if (!found) {
1066 : 1308706 : byte * p = C[0].p;
1067 : 1308706 : size_t n = TOTAL_FREE(p) % (max_item_size + D2);
1068 [ + + ]: 1308706 : if (n > D2 + cd) {
1069 : 1271038 : n -= (D2 + cd);
1070 : : // if n >= last then fully filling this block won't produce
1071 : : // an extra item, so we might as well do this even if
1072 : : // full_compaction isn't active.
1073 : : //
1074 : : // In the full_compaction case, it turns out we shouldn't always
1075 : : // try to fill every last byte. Doing so can actually increase the
1076 : : // total space required (I believe this effect is due to longer
1077 : : // dividing keys being required in the index blocks). Empirically,
1078 : : // n >= key.size() + K appears a good criterion for K ~= 34. This
1079 : : // seems to save about 0.2% in total database size over always
1080 : : // splitting the tag. It'll also give be slightly faster retrieval
1081 : : // as we can avoid reading an extra block occasionally.
1082 : 1271038 : size_t last = tag.length() % L;
1083 [ + + + + ]: 1271038 : if (n >= last || (full_compaction && n >= key.size() + 34))
[ + + ][ + + ]
1084 : 1263911 : first_L = n;
1085 : : }
1086 : : }
1087 : :
1088 : : // a null tag must be added in of course
1089 [ + + ]: 1351696 : int m = tag.empty() ? 1 : (tag.length() - first_L + L - 1) / L + 1;
1090 : : // there are m items to add
1091 : : /* FIXME: sort out this error higher up and turn this into
1092 : : * an assert.
1093 : : */
1094 [ - + ]: 1351696 : if (m >= BYTE_PAIR_RANGE)
1095 : 0 : throw Xapian::UnimplementedError("Can't handle insanely large tags");
1096 : :
1097 : 1351696 : int n = 0; // initialise to shut off warning
1098 : : // - and there will be n to delete
1099 : 1351696 : int o = 0; // Offset into the tag
1100 : 1351696 : size_t residue = tag.length(); // Bytes of the tag remaining to add in
1101 : 1351696 : int replacement = false; // Has there been a replacement ?
1102 : : int i;
1103 : 1351696 : kt.set_components_of(m);
1104 [ + + ]: 2711730 : for (i = 1; i <= m; i++) {
1105 [ + + ][ + + ]: 1360034 : size_t l = (i == m ? residue : (i == 1 ? first_L : L));
1106 : : Assert(cd + l <= block_size);
1107 : : Assert(string::size_type(o + l) <= tag.length());
1108 : 1360034 : kt.set_tag(cd, tag.data() + o, l, compressed);
1109 : 1360034 : kt.set_component_of(i);
1110 : :
1111 : 1360034 : o += l;
1112 : 1360034 : residue -= l;
1113 : :
1114 [ + + ]: 1360034 : if (i > 1) found = find(C);
1115 : 1360034 : n = add_kt(found);
1116 [ + + ]: 1360034 : if (n > 0) replacement = true;
1117 : : }
1118 : : /* o == tag.length() here, and n may be zero */
1119 [ - + ]: 1351696 : for (i = m + 1; i <= n; i++) {
1120 : 0 : kt.set_component_of(i);
1121 : 0 : delete_kt();
1122 : : }
1123 [ + + ]: 1351696 : if (!replacement) ++item_count;
1124 : 1351696 : Btree_modified = true;
1125 [ + + ]: 1351696 : if (cursor_created_since_last_modification) {
1126 : 188107 : cursor_created_since_last_modification = false;
1127 : 188107 : ++cursor_version;
1128 : : }
1129 : 1351696 : }
1130 : :
1131 : : /* BrassTable::del(key) returns false if the key is not in the B-tree,
1132 : : otherwise deletes it and returns true.
1133 : :
1134 : : Again, this is parallel to BrassTable::add, but simpler in form.
1135 : : */
1136 : :
1137 : : bool
1138 : 45922 : BrassTable::del(const string &key)
1139 : : {
1140 : : LOGCALL(DB, bool, "BrassTable::del", key);
1141 : : Assert(writable);
1142 : :
1143 [ + + ]: 45922 : if (handle < 0) {
1144 [ - + ]: 4443 : if (handle == -2) {
1145 : 0 : BrassTable::throw_database_closed();
1146 : : }
1147 : 4443 : RETURN(false);
1148 : : }
1149 : :
1150 : : // We can't delete a key which we is too long for us to store.
1151 [ - + ]: 41479 : if (key.size() > BRASS_BTREE_MAX_KEY_LEN) RETURN(false);
1152 : :
1153 [ - + ]: 41479 : if (key.empty()) RETURN(false);
1154 : 41479 : form_key(key);
1155 : :
1156 : 41479 : int n = delete_kt(); /* there are n items to delete */
1157 [ + + ]: 41479 : if (n <= 0) RETURN(false);
1158 : :
1159 [ + + ]: 41706 : for (int i = 2; i <= n; i++) {
1160 : 367 : kt.set_component_of(i);
1161 : 367 : delete_kt();
1162 : : }
1163 : :
1164 : 41339 : item_count--;
1165 : 41339 : Btree_modified = true;
1166 [ + + ]: 41339 : if (cursor_created_since_last_modification) {
1167 : 192 : cursor_created_since_last_modification = false;
1168 : 192 : ++cursor_version;
1169 : : }
1170 : 45922 : RETURN(true);
1171 : : }
1172 : :
1173 : : bool
1174 : 1088424 : BrassTable::get_exact_entry(const string &key, string & tag) const
1175 : : {
1176 : : LOGCALL(DB, bool, "BrassTable::get_exact_entry", key | tag);
1177 : : Assert(!key.empty());
1178 : :
1179 [ + + ]: 1088424 : if (handle < 0) {
1180 [ - + ]: 50956 : if (handle == -2) {
1181 : 0 : BrassTable::throw_database_closed();
1182 : : }
1183 : 50956 : RETURN(false);
1184 : : }
1185 : :
1186 : : // An oversized key can't exist, so attempting to search for it should fail.
1187 [ + + ]: 1037468 : if (key.size() > BRASS_BTREE_MAX_KEY_LEN) RETURN(false);
1188 : :
1189 : 1037436 : form_key(key);
1190 [ + + ]: 1037436 : if (!find(C)) RETURN(false);
1191 : :
1192 : 748915 : (void)read_tag(C, &tag, false);
1193 : 1088422 : RETURN(true);
1194 : : }
1195 : :
1196 : : bool
1197 : 1060 : BrassTable::key_exists(const string &key) const
1198 : : {
1199 : : LOGCALL(DB, bool, "BrassTable::key_exists", key);
1200 : : Assert(!key.empty());
1201 : :
1202 : : // An oversized key can't exist, so attempting to search for it should fail.
1203 [ - + ]: 1060 : if (key.size() > BRASS_BTREE_MAX_KEY_LEN) RETURN(false);
1204 : :
1205 : 1060 : form_key(key);
1206 : 1060 : RETURN(find(C));
1207 : : }
1208 : :
1209 : : bool
1210 : 2681462 : BrassTable::read_tag(Brass::Cursor * C_, string *tag, bool keep_compressed) const
1211 : : {
1212 : : LOGCALL(DB, bool, "BrassTable::read_tag", Literal("C_") | tag | keep_compressed);
1213 : 2681462 : Item item(C_[0].p, C_[0].c);
1214 : :
1215 : : /* n components to join */
1216 : 2681462 : int n = item.components_of();
1217 : :
1218 : 2681462 : tag->resize(0);
1219 : : // max_item_size also includes K1 + I2 + C2 + C2 bytes overhead and the key
1220 : : // (which is at least 1 byte long).
1221 [ + + ]: 2681462 : if (n > 1) tag->reserve((max_item_size - (1 + K1 + I2 + C2 + C2)) * n);
1222 : :
1223 : 2681462 : item.append_chunk(tag);
1224 : 2681462 : bool compressed = item.get_compressed();
1225 : :
1226 [ + + ]: 6948760 : for (int i = 2; i <= n; i++) {
1227 [ - + ]: 4267298 : if (!next(C_, 0)) {
1228 : 0 : throw Xapian::DatabaseCorruptError("Unexpected end of table when reading continuation of tag");
1229 : : }
1230 : 4267298 : (void)Item(C_[0].p, C_[0].c).append_chunk(tag);
1231 : : }
1232 : : // At this point the cursor is on the last item - calling next will move
1233 : : // it to the next key (BrassCursor::get_tag() relies on this).
1234 [ + + ][ + + ]: 2681462 : if (!compressed || keep_compressed) RETURN(compressed);
1235 : :
1236 : : // FIXME: Perhaps we should we decompress each chunk as we read it so we
1237 : : // don't need both the full compressed and uncompressed tags in memory
1238 : : // at once.
1239 : :
1240 : 207427 : string utag;
1241 : : // May not be enough for a compressed tag, but it's a reasonable guess.
1242 : 207427 : utag.reserve(tag->size() + tag->size() / 2);
1243 : :
1244 : : Bytef buf[8192];
1245 : :
1246 : 207427 : lazy_alloc_inflate_zstream();
1247 : :
1248 : 207427 : inflate_zstream->next_in = (Bytef*)const_cast<char *>(tag->data());
1249 : 207427 : inflate_zstream->avail_in = (uInt)tag->size();
1250 : :
1251 : 207427 : int err = Z_OK;
1252 [ + + ]: 414854 : while (err != Z_STREAM_END) {
1253 : 207427 : inflate_zstream->next_out = buf;
1254 : 207427 : inflate_zstream->avail_out = (uInt)sizeof(buf);
1255 : 207427 : err = inflate(inflate_zstream, Z_SYNC_FLUSH);
1256 [ - + # # ]: 207427 : if (err == Z_BUF_ERROR && inflate_zstream->avail_in == 0) {
1257 : : LOGLINE(DB, "Z_BUF_ERROR - faking checksum of " << inflate_zstream->adler);
1258 : : Bytef header2[4];
1259 : 0 : setint4(header2, 0, inflate_zstream->adler);
1260 : 0 : inflate_zstream->next_in = header2;
1261 : 0 : inflate_zstream->avail_in = 4;
1262 : 0 : err = inflate(inflate_zstream, Z_SYNC_FLUSH);
1263 [ # # ]: 0 : if (err == Z_STREAM_END) break;
1264 : : }
1265 : :
1266 [ + - ][ - + ]: 207427 : if (err != Z_OK && err != Z_STREAM_END) {
1267 [ # # ]: 0 : if (err == Z_MEM_ERROR) throw std::bad_alloc();
1268 : 0 : string msg = "inflate failed";
1269 [ # # ]: 0 : if (inflate_zstream->msg) {
1270 : 0 : msg += " (";
1271 : 0 : msg += inflate_zstream->msg;
1272 : 0 : msg += ')';
1273 : : }
1274 : 0 : throw Xapian::DatabaseError(msg);
1275 : : }
1276 : :
1277 : : utag.append(reinterpret_cast<const char *>(buf),
1278 : 207427 : inflate_zstream->next_out - buf);
1279 : : }
1280 [ - + ]: 207427 : if (utag.size() != inflate_zstream->total_out) {
1281 : 0 : string msg = "compressed tag didn't expand to the expected size: ";
1282 : 0 : msg += str(utag.size());
1283 : 0 : msg += " != ";
1284 : : // OpenBSD's zlib.h uses off_t instead of uLong for total_out.
1285 : 0 : msg += str((size_t)inflate_zstream->total_out);
1286 : 0 : throw Xapian::DatabaseCorruptError(msg);
1287 : : }
1288 : :
1289 : 207427 : swap(*tag, utag);
1290 : :
1291 : 2681462 : RETURN(false);
1292 : : }
1293 : :
1294 : : void
1295 : 40 : BrassTable::set_full_compaction(bool parity)
1296 : : {
1297 : : LOGCALL_VOID(DB, "BrassTable::set_full_compaction", parity);
1298 : : Assert(writable);
1299 : :
1300 [ + - ]: 40 : if (parity) seq_count = 0;
1301 : 40 : full_compaction = parity;
1302 : 40 : }
1303 : :
1304 : 2004150 : BrassCursor * BrassTable::cursor_get() const {
1305 : : LOGCALL(DB, BrassCursor *, "BrassTable::cursor_get", NO_ARGS);
1306 [ + + ]: 2004150 : if (handle < 0) {
1307 [ + + ]: 9 : if (handle == -2) {
1308 : 7 : BrassTable::throw_database_closed();
1309 : : }
1310 : 2 : RETURN(NULL);
1311 : : }
1312 : : // FIXME Ick - casting away const is nasty
1313 : 2004143 : RETURN(new BrassCursor(const_cast<BrassTable *>(this)));
1314 : : }
1315 : :
1316 : : /************ B-tree opening and closing ************/
1317 : :
1318 : : bool
1319 : 8793 : BrassTable::basic_open(bool revision_supplied, brass_revision_number_t revision_)
1320 : : {
1321 : : LOGCALL(DB, bool, "BrassTable::basic_open", revision_supplied | revision_);
1322 : 8793 : int ch = 'X'; /* will be 'A' or 'B' */
1323 : :
1324 : : {
1325 : 8793 : const size_t BTREE_BASES = 2;
1326 : 8793 : string err_msg;
1327 : : static const char basenames[BTREE_BASES] = { 'A', 'B' };
1328 : :
1329 [ + + ][ # # ]: 26379 : BrassTable_base bases[BTREE_BASES];
[ # # ]
1330 : : bool base_ok[BTREE_BASES];
1331 : :
1332 : 8793 : both_bases = true;
1333 : 8793 : bool valid_base = false;
1334 : : {
1335 [ + + ]: 26379 : for (size_t i = 0; i < BTREE_BASES; ++i) {
1336 : 17586 : bool ok = bases[i].read(name, basenames[i], writable, err_msg);
1337 : 17586 : base_ok[i] = ok;
1338 [ + + ]: 17586 : if (ok) {
1339 : 15152 : valid_base = true;
1340 : : } else {
1341 : 2434 : both_bases = false;
1342 : : }
1343 : : }
1344 : : }
1345 : :
1346 [ - + ]: 8793 : if (!valid_base) {
1347 [ # # ]: 0 : if (handle >= 0) {
1348 : 0 : ::close(handle);
1349 : 0 : handle = -1;
1350 : : }
1351 : 0 : string message = "Error opening table `";
1352 : 0 : message += name;
1353 : 0 : message += "':\n";
1354 : 0 : message += err_msg;
1355 : 0 : throw Xapian::DatabaseOpeningError(message);
1356 : : }
1357 : :
1358 [ + + ]: 8793 : if (revision_supplied) {
1359 : 5255 : bool found_revision = false;
1360 [ + - ]: 9535 : for (size_t i = 0; i < BTREE_BASES; ++i) {
1361 [ + + ][ + + ]: 9535 : if (base_ok[i] && bases[i].get_revision() == revision_) {
[ + + ]
1362 : 5255 : ch = basenames[i];
1363 : 5255 : found_revision = true;
1364 : 5255 : break;
1365 : : }
1366 : : }
1367 [ - + ]: 5255 : if (!found_revision) {
1368 : : /* Couldn't open the revision that was asked for.
1369 : : * This shouldn't throw an exception, but should just return
1370 : : * false to upper levels.
1371 : : */
1372 : 0 : RETURN(false);
1373 : : }
1374 : : } else {
1375 : 3538 : brass_revision_number_t highest_revision = 0;
1376 [ + + ]: 10614 : for (size_t i = 0; i < BTREE_BASES; ++i) {
1377 [ + + ][ + + ]: 7076 : if (base_ok[i] && bases[i].get_revision() >= highest_revision) {
[ + + ]
1378 : 5444 : ch = basenames[i];
1379 : 5444 : highest_revision = bases[i].get_revision();
1380 : : }
1381 : : }
1382 : : }
1383 : :
1384 : 8793 : BrassTable_base *basep = 0;
1385 : 8793 : BrassTable_base *other_base = 0;
1386 : :
1387 [ + - ]: 14979 : for (size_t i = 0; i < BTREE_BASES; ++i) {
1388 : : LOGLINE(DB, "Checking (ch == " << ch << ") against "
1389 : : "basenames[" << i << "] == " << basenames[i]);
1390 : : LOGLINE(DB, "bases[" << i << "].get_revision() == " <<
1391 : : bases[i].get_revision());
1392 : : LOGLINE(DB, "base_ok[" << i << "] == " << base_ok[i]);
1393 [ + + ]: 14979 : if (ch == basenames[i]) {
1394 : 8793 : basep = &bases[i];
1395 : :
1396 : : // FIXME: assuming only two bases for other_base
1397 : 8793 : size_t otherbase_num = 1-i;
1398 [ + + ]: 8793 : if (base_ok[otherbase_num]) {
1399 : 6359 : other_base = &bases[otherbase_num];
1400 : : }
1401 : 8793 : break;
1402 : : }
1403 : : }
1404 : : Assert(basep);
1405 : :
1406 : : /* basep now points to the most recent base block */
1407 : :
1408 : : /* Avoid copying the bitmap etc. - swap contents with the base
1409 : : * object in the vector, since it'll be destroyed anyway soon.
1410 : : */
1411 : 8793 : base.swap(*basep);
1412 : :
1413 : 8793 : revision_number = base.get_revision();
1414 : 8793 : block_size = base.get_block_size();
1415 : 8793 : root = base.get_root();
1416 : 8793 : level = base.get_level();
1417 : : //bit_map_size = basep->get_bit_map_size();
1418 : 8793 : item_count = base.get_item_count();
1419 : 8793 : faked_root_block = base.get_have_fakeroot();
1420 : 8793 : sequential = base.get_sequential();
1421 : :
1422 [ + + ]: 8793 : if (other_base != 0) {
1423 : 6359 : latest_revision_number = other_base->get_revision();
1424 [ + - ]: 6359 : if (revision_number > latest_revision_number)
1425 : 6359 : latest_revision_number = revision_number;
1426 : : } else {
1427 : 8793 : latest_revision_number = revision_number;
1428 [ # # ][ + + ]: 26379 : }
[ - + ][ + - ]
1429 : : }
1430 : :
1431 : : /* kt holds constructed items as well as keys */
1432 : 8793 : kt = Item_wr(zeroed_new(block_size));
1433 : :
1434 : 8793 : set_max_item_size(BLOCK_CAPACITY);
1435 : :
1436 : 8793 : base_letter = ch;
1437 : :
1438 : : /* ready to open the main file */
1439 : :
1440 : 8793 : RETURN(true);
1441 : : }
1442 : :
1443 : : void
1444 : 11001 : BrassTable::read_root()
1445 : : {
1446 : : LOGCALL_VOID(DB, "BrassTable::read_root", NO_ARGS);
1447 [ + + ]: 11001 : if (faked_root_block) {
1448 : : /* root block for an unmodified database. */
1449 : 2960 : byte * p = C[0].p;
1450 : : Assert(p);
1451 : :
1452 : : /* clear block - shouldn't be necessary, but is a bit nicer,
1453 : : * and means that the same operations should always produce
1454 : : * the same database. */
1455 : 2960 : memset(p, 0, block_size);
1456 : :
1457 : 2960 : int o = block_size - I2 - K1 - C2 - C2;
1458 : 2960 : Item_wr(p + o).fake_root_item();
1459 : :
1460 : 2960 : setD(p, DIR_START, o); // its directory entry
1461 : 2960 : SET_DIR_END(p, DIR_START + D2);// the directory size
1462 : :
1463 : 2960 : o -= (DIR_START + D2);
1464 : 2960 : SET_MAX_FREE(p, o);
1465 : 2960 : SET_TOTAL_FREE(p, o);
1466 : 2960 : SET_LEVEL(p, 0);
1467 : :
1468 [ + + ]: 2960 : if (!writable) {
1469 : : /* reading - revision number doesn't matter as long as
1470 : : * it's not greater than the current one. */
1471 : 572 : SET_REVISION(p, 0);
1472 : 572 : C[0].n = 0;
1473 : : } else {
1474 : : /* writing - */
1475 : 2388 : SET_REVISION(p, latest_revision_number + 1);
1476 : 2388 : C[0].n = base.next_free_block();
1477 : : }
1478 : : } else {
1479 : : /* using a root block stored on disk */
1480 : 8041 : block_to_cursor(C, level, root);
1481 : :
1482 [ - + ]: 8041 : if (REVISION(C[level].p) > revision_number) set_overwritten();
1483 : : /* although this is unlikely */
1484 : : }
1485 : 11001 : }
1486 : :
1487 : : bool
1488 : 3159 : BrassTable::do_open_to_write(bool revision_supplied,
1489 : : brass_revision_number_t revision_,
1490 : : bool create_db)
1491 : : {
1492 : : LOGCALL(DB, bool, "BrassTable::do_open_to_write", revision_supplied | revision_ | create_db);
1493 [ - + ]: 3159 : if (handle == -2) {
1494 : 0 : BrassTable::throw_database_closed();
1495 : : }
1496 : 3159 : int flags = O_RDWR | O_BINARY;
1497 [ + + ]: 3159 : if (create_db) flags |= O_CREAT | O_TRUNC;
1498 : 3159 : handle = ::open((name + "DB").c_str(), flags, 0666);
1499 [ + + ]: 3159 : if (handle < 0) {
1500 : : // lazy doesn't make a lot of sense with create_db anyway, but ENOENT
1501 : : // with O_CREAT means a parent directory doesn't exist.
1502 [ + - ][ + - ]: 925 : if (lazy && !create_db && errno == ENOENT) {
[ + - ]
1503 : 925 : revision_number = revision_;
1504 : 925 : RETURN(true);
1505 : : }
1506 [ # # ]: 0 : string message(create_db ? "Couldn't create " : "Couldn't open ");
1507 : 0 : message += name;
1508 : 0 : message += "DB read/write: ";
1509 : 0 : message += strerror(errno);
1510 : 0 : throw Xapian::DatabaseOpeningError(message);
1511 : : }
1512 : :
1513 [ - + ]: 2234 : if (!basic_open(revision_supplied, revision_)) {
1514 : 0 : ::close(handle);
1515 : 0 : handle = -1;
1516 [ # # ]: 0 : if (!revision_supplied) {
1517 : 0 : throw Xapian::DatabaseOpeningError("Failed to open for writing");
1518 : : }
1519 : : /* When the revision is supplied, it's not an exceptional
1520 : : * case when open failed, so we just return false here.
1521 : : */
1522 : 0 : RETURN(false);
1523 : : }
1524 : :
1525 : 2234 : writable = true;
1526 : :
1527 [ + + ]: 4532 : for (int j = 0; j <= level; j++) {
1528 : 2298 : C[j].n = BLK_UNUSED;
1529 : 2298 : C[j].p = new byte[block_size];
1530 [ - + ]: 2298 : if (C[j].p == 0) {
1531 : 0 : throw std::bad_alloc();
1532 : : }
1533 : : }
1534 : 2234 : split_p = new byte[block_size];
1535 [ - + ]: 2234 : if (split_p == 0) {
1536 : 0 : throw std::bad_alloc();
1537 : : }
1538 : 2234 : read_root();
1539 : :
1540 : 2234 : buffer = zeroed_new(block_size);
1541 : :
1542 : 2234 : changed_n = 0;
1543 : 2234 : changed_c = DIR_START;
1544 : 2234 : seq_count = SEQ_START_POINT;
1545 : :
1546 : 3159 : RETURN(true);
1547 : : }
1548 : :
1549 : 13402 : BrassTable::BrassTable(const char * tablename_, const string & path_,
1550 : : bool readonly_, int compress_strategy_, bool lazy_)
1551 : : : tablename(tablename_),
1552 : : revision_number(0),
1553 : : item_count(0),
1554 : : block_size(0),
1555 : : latest_revision_number(0),
1556 : : both_bases(false),
1557 : : base_letter('A'),
1558 : : faked_root_block(true),
1559 : : sequential(true),
1560 : : handle(-1),
1561 : : level(0),
1562 : : root(0),
1563 : : kt(0),
1564 : : buffer(0),
1565 : : base(),
1566 : : name(path_),
1567 : : seq_count(0),
1568 : : changed_n(0),
1569 : : changed_c(0),
1570 : : max_item_size(0),
1571 : : Btree_modified(false),
1572 : : full_compaction(false),
1573 : : writable(!readonly_),
1574 : : cursor_created_since_last_modification(false),
1575 : : cursor_version(0),
1576 : : split_p(0),
1577 : : compress_strategy(compress_strategy_),
1578 : : deflate_zstream(NULL),
1579 : : inflate_zstream(NULL),
1580 [ + + ][ + + ]: 147422 : lazy(lazy_)
1581 : : {
1582 : : LOGCALL_CTOR(DB, "BrassTable", tablename_ | path_ | readonly_ | compress_strategy_ | lazy_);
1583 : 13402 : }
1584 : :
1585 : : bool
1586 : 893 : BrassTable::really_empty() const
1587 : : {
1588 [ + + ]: 893 : if (handle < 0) {
1589 [ - + ]: 426 : if (handle == -2) {
1590 : 0 : BrassTable::throw_database_closed();
1591 : : }
1592 : 426 : return true;
1593 : : }
1594 : 467 : BrassCursor cur(const_cast<BrassTable*>(this));
1595 : 467 : cur.find_entry(string());
1596 : 893 : return !cur.next();
1597 : : }
1598 : :
1599 : : void
1600 : 58202 : BrassTable::lazy_alloc_deflate_zstream() const {
1601 [ + + ]: 58202 : if (usual(deflate_zstream)) {
1602 [ + - ]: 57844 : if (usual(deflateReset(deflate_zstream) == Z_OK)) return;
1603 : : // Try to recover by deleting the stream and starting from scratch.
1604 : 0 : delete deflate_zstream;
1605 : : }
1606 : :
1607 : 358 : deflate_zstream = new z_stream;
1608 : :
1609 : 358 : deflate_zstream->zalloc = reinterpret_cast<alloc_func>(0);
1610 : 358 : deflate_zstream->zfree = reinterpret_cast<free_func>(0);
1611 : 358 : deflate_zstream->opaque = (voidpf)0;
1612 : :
1613 : : // -15 means raw deflate with 32K LZ77 window (largest)
1614 : : // memLevel 9 is the highest (8 is default)
1615 : : int err;
1616 : : err = deflateInit2(deflate_zstream, Z_DEFAULT_COMPRESSION, Z_DEFLATED,
1617 : 358 : -15, 9, compress_strategy);
1618 [ - + ]: 358 : if (rare(err != Z_OK)) {
1619 [ # # ]: 0 : if (err == Z_MEM_ERROR) {
1620 : 0 : delete deflate_zstream;
1621 : 0 : deflate_zstream = 0;
1622 : 0 : throw std::bad_alloc();
1623 : : }
1624 : 0 : string msg = "deflateInit2 failed (";
1625 [ # # ]: 0 : if (deflate_zstream->msg) {
1626 : 0 : msg += deflate_zstream->msg;
1627 : : } else {
1628 : 0 : msg += str(err);
1629 : : }
1630 : 0 : msg += ')';
1631 : 0 : delete deflate_zstream;
1632 : 0 : deflate_zstream = 0;
1633 : 58202 : throw Xapian::DatabaseError(msg);
1634 : : }
1635 : : }
1636 : :
1637 : : void
1638 : 207427 : BrassTable::lazy_alloc_inflate_zstream() const {
1639 [ + + ]: 207427 : if (usual(inflate_zstream)) {
1640 [ + - ]: 207217 : if (usual(inflateReset(inflate_zstream) == Z_OK)) return;
1641 : : // Try to recover by deleting the stream and starting from scratch.
1642 : 0 : delete inflate_zstream;
1643 : : }
1644 : :
1645 : 210 : inflate_zstream = new z_stream;
1646 : :
1647 : 210 : inflate_zstream->zalloc = reinterpret_cast<alloc_func>(0);
1648 : 210 : inflate_zstream->zfree = reinterpret_cast<free_func>(0);
1649 : :
1650 : 210 : inflate_zstream->next_in = Z_NULL;
1651 : 210 : inflate_zstream->avail_in = 0;
1652 : :
1653 : 210 : int err = inflateInit2(inflate_zstream, -15);
1654 [ - + ]: 210 : if (rare(err != Z_OK)) {
1655 [ # # ]: 0 : if (err == Z_MEM_ERROR) {
1656 : 0 : delete inflate_zstream;
1657 : 0 : inflate_zstream = 0;
1658 : 0 : throw std::bad_alloc();
1659 : : }
1660 : 0 : string msg = "inflateInit2 failed (";
1661 [ # # ]: 0 : if (inflate_zstream->msg) {
1662 : 0 : msg += inflate_zstream->msg;
1663 : : } else {
1664 : 0 : msg += str(err);
1665 : : }
1666 : 0 : msg += ')';
1667 : 0 : delete inflate_zstream;
1668 : 0 : inflate_zstream = 0;
1669 : 207427 : throw Xapian::DatabaseError(msg);
1670 : : }
1671 : : }
1672 : :
1673 : : bool
1674 : 588 : BrassTable::exists() const {
1675 : : LOGCALL(DB, bool, "BrassTable::exists", NO_ARGS);
1676 : : return (file_exists(name + "DB") &&
1677 [ + + ][ - + ]: 588 : (file_exists(name + "baseA") || file_exists(name + "baseB")));
[ # # ][ - + ]
[ # # ][ # # ]
[ + + ][ # # ]
[ + - ]
1678 : : }
1679 : :
1680 : : void
1681 : 931 : BrassTable::erase()
1682 : : {
1683 : : LOGCALL_VOID(DB, "BrassTable::erase", NO_ARGS);
1684 : 931 : close();
1685 : :
1686 : 931 : (void)io_unlink(name + "baseA");
1687 : 931 : (void)io_unlink(name + "baseB");
1688 : 931 : (void)io_unlink(name + "DB");
1689 : 931 : }
1690 : :
1691 : : void
1692 : 9761 : BrassTable::set_block_size(unsigned int block_size_)
1693 : : {
1694 : : LOGCALL_VOID(DB, "BrassTable::set_block_size", block_size_);
1695 : : // Block size must in the range 2048..BYTE_PAIR_RANGE, and a power of two.
1696 [ + - ][ + - ]: 9761 : if (block_size_ < 2048 || block_size_ > BYTE_PAIR_RANGE ||
[ - + ]
1697 : : (block_size_ & (block_size_ - 1)) != 0) {
1698 : 0 : block_size_ = BRASS_DEFAULT_BLOCK_SIZE;
1699 : : }
1700 : 9761 : block_size = block_size_;
1701 : 9761 : }
1702 : :
1703 : : void
1704 : 1134 : BrassTable::create_and_open(unsigned int block_size_)
1705 : : {
1706 : : LOGCALL_VOID(DB, "BrassTable::create_and_open", block_size_);
1707 [ - + ]: 1134 : if (handle == -2) {
1708 : 0 : BrassTable::throw_database_closed();
1709 : : }
1710 : : Assert(writable);
1711 : 1134 : close();
1712 : :
1713 [ - + ]: 1134 : if (block_size_ == 0) abort();
1714 : 1134 : set_block_size(block_size_);
1715 : :
1716 : : // FIXME: it would be good to arrange that this works such that there's
1717 : : // always a valid table in place if you run create_and_open() on an
1718 : : // existing table.
1719 : :
1720 : : /* write initial values to files */
1721 : :
1722 : : /* create the base file */
1723 : 1134 : BrassTable_base base_;
1724 : 1134 : base_.set_revision(revision_number);
1725 : 1134 : base_.set_block_size(block_size_);
1726 : 1134 : base_.set_have_fakeroot(true);
1727 : 1134 : base_.set_sequential(true);
1728 : 1134 : base_.write_to_file(name + "baseA", 'A', string(), -1, NULL);
1729 : :
1730 : : /* remove the alternative base file, if any */
1731 : 1134 : (void)io_unlink(name + "baseB");
1732 : :
1733 : : // Any errors are thrown if revision_supplied is false.
1734 : 1134 : (void)do_open_to_write(false, 0, true);
1735 : 1134 : }
1736 : :
1737 : 13402 : BrassTable::~BrassTable() {
1738 : : LOGCALL_DTOR(DB, "BrassTable");
1739 : 13402 : BrassTable::close();
1740 : :
1741 [ + + + + ]: 13402 : if (deflate_zstream) {
1742 : : // Errors which we care about have already been handled, so just ignore
1743 : : // any which get returned here.
1744 : 358 : (void) deflateEnd(deflate_zstream);
1745 : 358 : delete deflate_zstream;
1746 : : }
1747 : :
1748 [ - + ][ + + ]: 13402 : if (inflate_zstream) {
1749 : : // Errors which we care about have already been handled, so just ignore
1750 : : // any which get returned here.
1751 : 210 : (void) inflateEnd(inflate_zstream);
1752 : 210 : delete inflate_zstream;
1753 : : }
1754 : 13402 : }
1755 : :
1756 : 27575 : void BrassTable::close(bool permanent) {
1757 : : LOGCALL_VOID(DB, "BrassTable::close", NO_ARGS);
1758 : :
1759 [ + + ]: 27575 : if (handle >= 0) {
1760 : : // If an error occurs here, we just ignore it, since we're just
1761 : : // trying to free everything.
1762 : 8793 : (void)::close(handle);
1763 : 8793 : handle = -1;
1764 : : }
1765 : :
1766 [ + + ]: 27575 : if (permanent) {
1767 : 78 : handle = -2;
1768 : : // Don't delete the resources in the table, since they may
1769 : : // still be used to look up cached content.
1770 : 78 : return;
1771 : : }
1772 [ + + ]: 57354 : for (int j = level; j >= 0; j--) {
1773 [ + + ]: 29857 : delete [] C[j].p;
1774 : 29857 : C[j].p = 0;
1775 : : }
1776 [ + + ]: 27497 : delete [] split_p;
1777 : 27497 : split_p = 0;
1778 : :
1779 [ + + ]: 27497 : delete [] kt.get_address();
1780 : 27497 : kt = 0;
1781 [ + + ]: 27497 : delete [] buffer;
1782 : 27575 : buffer = 0;
1783 : : }
1784 : :
1785 : : void
1786 : 2878 : BrassTable::flush_db()
1787 : : {
1788 : : LOGCALL_VOID(DB, "BrassTable::flush_db", NO_ARGS);
1789 : : Assert(writable);
1790 [ + + ]: 2878 : if (handle < 0) {
1791 [ - + ]: 1139 : if (handle == -2) {
1792 : 0 : BrassTable::throw_database_closed();
1793 : : }
1794 : 1139 : return;
1795 : : }
1796 : :
1797 [ + + ]: 3828 : for (int j = level; j >= 0; j--) {
1798 [ + + ]: 2089 : if (C[j].rewrite) {
1799 : 1887 : write_block(C[j].n, C[j].p);
1800 : : }
1801 : : }
1802 : :
1803 [ + + ]: 1739 : if (Btree_modified) {
1804 : 2878 : faked_root_block = false;
1805 : : }
1806 : : }
1807 : :
1808 : : void
1809 : 2878 : BrassTable::commit(brass_revision_number_t revision, int changes_fd,
1810 : : const string * changes_tail)
1811 : : {
1812 : : LOGCALL_VOID(DB, "BrassTable::commit", revision | changes_fd | changes_tail);
1813 : : Assert(writable);
1814 : :
1815 [ - + ]: 2878 : if (revision <= revision_number) {
1816 : 0 : throw Xapian::DatabaseError("New revision too low");
1817 : : }
1818 : :
1819 [ + + ]: 2878 : if (handle < 0) {
1820 [ - + ]: 1139 : if (handle == -2) {
1821 : 0 : BrassTable::throw_database_closed();
1822 : : }
1823 : 1139 : latest_revision_number = revision_number = revision;
1824 : 1139 : return;
1825 : : }
1826 : :
1827 : : try {
1828 [ + + ]: 1739 : if (faked_root_block) {
1829 : : /* We will use a dummy bitmap. */
1830 : 102 : base.clear_bit_map();
1831 : : }
1832 : :
1833 : 1739 : base.set_revision(revision);
1834 : 1739 : base.set_root(C[level].n);
1835 : 1739 : base.set_level(level);
1836 : 1739 : base.set_item_count(item_count);
1837 : 1739 : base.set_have_fakeroot(faked_root_block);
1838 : 1739 : base.set_sequential(sequential);
1839 : :
1840 : 1739 : base_letter = other_base_letter();
1841 : :
1842 : 1739 : both_bases = true;
1843 : 1739 : latest_revision_number = revision_number = revision;
1844 : 1739 : root = C[level].n;
1845 : :
1846 : 1739 : Btree_modified = false;
1847 : :
1848 [ + + ]: 19129 : for (int i = 0; i < BTREE_CURSOR_LEVELS; ++i) {
1849 : 17390 : C[i].n = BLK_UNUSED;
1850 : 17390 : C[i].c = -1;
1851 : 17390 : C[i].rewrite = false;
1852 : : }
1853 : :
1854 : : // Save to "<table>.tmp" and then rename to "<table>.base<letter>" so
1855 : : // that a reader can't try to read a partially written base file.
1856 : 1739 : string tmp = name;
1857 : 1739 : tmp += "tmp";
1858 : 1739 : string basefile = name;
1859 : 1739 : basefile += "base";
1860 : 1739 : basefile += char(base_letter);
1861 : 1739 : base.write_to_file(tmp, base_letter, tablename, changes_fd, changes_tail);
1862 : :
1863 : : // Do this as late as possible to allow maximum time for writes to
1864 : : // happen, and so the calls to io_sync() are adjacent which may be
1865 : : // more efficient, at least with some Linux kernel versions.
1866 [ - + ]: 1739 : if (!io_sync(handle)) {
1867 : 0 : (void)::close(handle);
1868 : 0 : handle = -1;
1869 : 0 : (void)unlink(tmp);
1870 : 0 : throw Xapian::DatabaseError("Can't commit new revision - failed to flush DB to disk");
1871 : : }
1872 : :
1873 : : #if defined __WIN32__
1874 : : if (msvc_posix_rename(tmp.c_str(), basefile.c_str()) < 0)
1875 : : #else
1876 [ - + ]: 1739 : if (rename(tmp.c_str(), basefile.c_str()) < 0)
1877 : : #endif
1878 : : {
1879 : : // With NFS, rename() failing may just mean that the server crashed
1880 : : // after successfully renaming, but before reporting this, and then
1881 : : // the retried operation fails. So we need to check if the source
1882 : : // file still exists, which we do by calling unlink(), since we want
1883 : : // to remove the temporary file anyway.
1884 : 0 : int saved_errno = errno;
1885 [ # # # # ]: 0 : if (unlink(tmp) == 0 || errno != ENOENT) {
[ # # ]
1886 : 0 : string msg("Couldn't update base file ");
1887 : 0 : msg += basefile;
1888 : 0 : msg += ": ";
1889 : 0 : msg += strerror(saved_errno);
1890 : 0 : throw Xapian::DatabaseError(msg);
1891 : : }
1892 : : }
1893 : 1739 : base.commit();
1894 : :
1895 : 1739 : read_root();
1896 : :
1897 : 1739 : changed_n = 0;
1898 : 1739 : changed_c = DIR_START;
1899 : 1739 : seq_count = SEQ_START_POINT;
1900 : 2878 : } catch (...) {
1901 : 0 : BrassTable::close();
1902 : 0 : throw;
1903 : : }
1904 : : }
1905 : :
1906 : : void
1907 : 372 : BrassTable::write_changed_blocks(int changes_fd)
1908 : : {
1909 : : LOGCALL_VOID(DB, "BrassTable::write_changed_blocks", changes_fd);
1910 : : Assert(changes_fd >= 0);
1911 [ + + ]: 372 : if (handle < 0) return;
1912 [ + + ]: 228 : if (faked_root_block) return;
1913 : :
1914 : 207 : string buf;
1915 : 207 : pack_uint(buf, 2u); // Indicate the item is a list of blocks
1916 : 207 : pack_string(buf, tablename);
1917 : 207 : pack_uint(buf, block_size);
1918 : 207 : io_write(changes_fd, buf.data(), buf.size());
1919 : :
1920 : : // Compare the old and new bitmaps to find blocks which have changed, and
1921 : : // write them to the file descriptor.
1922 : 207 : uint4 n = 0;
1923 : 207 : byte * p = new byte[block_size];
1924 : : try {
1925 : 207 : base.calculate_last_block();
1926 [ + + ]: 646 : while (base.find_changed_block(&n)) {
1927 : 439 : buf.resize(0);
1928 : 439 : pack_uint(buf, n + 1);
1929 : 439 : io_write(changes_fd, buf.data(), buf.size());
1930 : :
1931 : : // Read block n.
1932 : 439 : read_block(n, p);
1933 : :
1934 : : // Write block n to the file.
1935 : 439 : io_write(changes_fd, reinterpret_cast<const char *>(p), block_size);
1936 : 439 : ++n;
1937 : : }
1938 [ + - ]: 207 : delete[] p;
1939 : 207 : p = 0;
1940 : 0 : } catch (...) {
1941 [ # # ]: 0 : delete[] p;
1942 : 0 : throw;
1943 : : }
1944 : 207 : buf.resize(0);
1945 : 207 : pack_uint(buf, 0u);
1946 : 372 : io_write(changes_fd, buf.data(), buf.size());
1947 : : }
1948 : :
1949 : : void
1950 : 914 : BrassTable::cancel()
1951 : : {
1952 : : LOGCALL_VOID(DB, "BrassTable::cancel", NO_ARGS);
1953 : : Assert(writable);
1954 : :
1955 [ + + ]: 914 : if (handle < 0) {
1956 [ + + ]: 445 : if (handle == -2) {
1957 : 2 : BrassTable::throw_database_closed();
1958 : : }
1959 : 443 : latest_revision_number = revision_number; // FIXME: we can end up reusing a revision if we opened a btree at an older revision, start to modify it, then cancel...
1960 : 443 : return;
1961 : : }
1962 : :
1963 : : // This causes problems: if (!Btree_modified) return;
1964 : :
1965 : 469 : string err_msg;
1966 [ - + ]: 469 : if (!base.read(name, base_letter, writable, err_msg)) {
1967 : 0 : throw Xapian::DatabaseCorruptError(string("Couldn't reread base ") + base_letter);
1968 : : }
1969 : :
1970 : 469 : revision_number = base.get_revision();
1971 : 469 : block_size = base.get_block_size();
1972 : 469 : root = base.get_root();
1973 : 469 : level = base.get_level();
1974 : : //bit_map_size = basep->get_bit_map_size();
1975 : 469 : item_count = base.get_item_count();
1976 : 469 : faked_root_block = base.get_have_fakeroot();
1977 : 469 : sequential = base.get_sequential();
1978 : :
1979 : 469 : latest_revision_number = revision_number; // FIXME: we can end up reusing a revision if we opened a btree at an older revision, start to modify it, then cancel...
1980 : :
1981 : 469 : Btree_modified = false;
1982 : :
1983 [ + + ]: 976 : for (int j = 0; j <= level; j++) {
1984 : 507 : C[j].n = BLK_UNUSED;
1985 : 507 : C[j].rewrite = false;
1986 : : }
1987 : 469 : read_root();
1988 : :
1989 : 469 : changed_n = 0;
1990 : 469 : changed_c = DIR_START;
1991 : 912 : seq_count = SEQ_START_POINT;
1992 : : }
1993 : :
1994 : : /************ B-tree reading ************/
1995 : :
1996 : : bool
1997 : 10005 : BrassTable::do_open_to_read(bool revision_supplied, brass_revision_number_t revision_)
1998 : : {
1999 : : LOGCALL(DB, bool, "BrassTable::do_open_to_read", revision_supplied | revision_);
2000 [ + + ]: 10005 : if (handle == -2) {
2001 : 4 : BrassTable::throw_database_closed();
2002 : : }
2003 : 10001 : handle = ::open((name + "DB").c_str(), O_RDONLY | O_BINARY);
2004 [ + + ]: 10001 : if (handle < 0) {
2005 [ + - ]: 3442 : if (lazy) {
2006 : : // This table is optional when reading!
2007 : 3442 : revision_number = revision_;
2008 : 3442 : RETURN(true);
2009 : : }
2010 : 0 : string message("Couldn't open ");
2011 : 0 : message += name;
2012 : 0 : message += "DB to read: ";
2013 : 0 : message += strerror(errno);
2014 : 0 : throw Xapian::DatabaseOpeningError(message);
2015 : : }
2016 : :
2017 [ - + ]: 6559 : if (!basic_open(revision_supplied, revision_)) {
2018 : 0 : ::close(handle);
2019 : 0 : handle = -1;
2020 [ # # ]: 0 : if (revision_supplied) {
2021 : : // The requested revision was not available.
2022 : : // This could be because the database was modified underneath us, or
2023 : : // because a base file is missing. Return false, and work out what
2024 : : // the problem was at a higher level.
2025 : 0 : RETURN(false);
2026 : : }
2027 : 0 : throw Xapian::DatabaseOpeningError("Failed to open table for reading");
2028 : : }
2029 : :
2030 [ + + ]: 15223 : for (int j = 0; j <= level; j++) {
2031 : 8664 : C[j].n = BLK_UNUSED;
2032 : 8664 : C[j].p = new byte[block_size];
2033 [ - + ]: 8664 : if (C[j].p == 0) {
2034 : 0 : throw std::bad_alloc();
2035 : : }
2036 : : }
2037 : :
2038 : 6559 : read_root();
2039 : 10001 : RETURN(true);
2040 : : }
2041 : :
2042 : : void
2043 : 2410 : BrassTable::open()
2044 : : {
2045 : : LOGCALL_VOID(DB, "BrassTable::open", NO_ARGS);
2046 : : LOGLINE(DB, "opening at path " << name);
2047 : 2410 : close();
2048 : :
2049 [ + + ]: 2410 : if (!writable) {
2050 : : // Any errors are thrown if revision_supplied is false
2051 : 2070 : (void)do_open_to_read(false, 0);
2052 : 2066 : return;
2053 : : }
2054 : :
2055 : : // Any errors are thrown if revision_supplied is false.
2056 : 2406 : (void)do_open_to_write(false, 0);
2057 : : }
2058 : :
2059 : : bool
2060 : 9620 : BrassTable::open(brass_revision_number_t revision)
2061 : : {
2062 : : LOGCALL(DB, bool, "BrassTable::open", revision);
2063 : : LOGLINE(DB, "opening for particular revision at path " << name);
2064 : 9620 : close();
2065 : :
2066 [ + + ]: 9620 : if (!writable) {
2067 [ + - ]: 7935 : if (do_open_to_read(true, revision)) {
2068 : : AssertEq(revision_number, revision);
2069 : 7935 : RETURN(true);
2070 : : } else {
2071 : 0 : close();
2072 : 0 : RETURN(false);
2073 : : }
2074 : : }
2075 : :
2076 [ - + ]: 1685 : if (!do_open_to_write(true, revision)) {
2077 : : // Can't open at the requested revision.
2078 : 0 : close();
2079 : 0 : RETURN(false);
2080 : : }
2081 : :
2082 : : AssertEq(revision_number, revision);
2083 : 9620 : RETURN(true);
2084 : : }
2085 : :
2086 : : bool
2087 : 30 : BrassTable::prev_for_sequential(Brass::Cursor * C_, int /*dummy*/) const
2088 : : {
2089 : : LOGCALL(DB, bool, "BrassTable::prev_for_sequential", Literal("C_") | Literal("/*dummy*/"));
2090 : 30 : int c = C_[0].c;
2091 [ - + ]: 30 : if (c == DIR_START) {
2092 : 0 : byte * p = C_[0].p;
2093 : : Assert(p);
2094 : 0 : uint4 n = C_[0].n;
2095 : 0 : while (true) {
2096 [ # # ]: 0 : if (n == 0) RETURN(false);
2097 : 0 : n--;
2098 [ # # ]: 0 : if (writable) {
2099 [ # # ]: 0 : if (n == C[0].n) {
2100 : : // Block is a leaf block in the built-in cursor
2101 : : // (potentially in modified form).
2102 : 0 : memcpy(p, C[0].p, block_size);
2103 : : } else {
2104 : : // Blocks in the built-in cursor may not have been written
2105 : : // to disk yet, so we have to check that the block number
2106 : : // isn't in the built-in cursor or we'll read an
2107 : : // uninitialised block (for which GET_LEVEL(p) will
2108 : : // probably return 0).
2109 : : int j;
2110 [ # # ]: 0 : for (j = 1; j <= level; ++j) {
2111 [ # # ]: 0 : if (n == C[j].n) break;
2112 : : }
2113 [ # # ]: 0 : if (j <= level) continue;
2114 : :
2115 : : // Block isn't in the built-in cursor, so the form on disk
2116 : : // is valid, so read it to check if it's the next level 0
2117 : : // block.
2118 : 0 : read_block(n, p);
2119 : : }
2120 : : } else {
2121 : 0 : read_block(n, p);
2122 : : }
2123 : 0 : if (writable) AssertEq(revision_number, latest_revision_number);
2124 [ # # ]: 0 : if (REVISION(p) > revision_number + writable) {
2125 : 0 : set_overwritten();
2126 : : RETURN(false);
2127 : : }
2128 [ # # ]: 0 : if (GET_LEVEL(p) == 0) break;
2129 : : }
2130 : 0 : c = DIR_END(p);
2131 : 0 : C_[0].n = n;
2132 : : }
2133 : 30 : c -= D2;
2134 : 30 : C_[0].c = c;
2135 : 30 : RETURN(true);
2136 : : }
2137 : :
2138 : : bool
2139 : 116217 : BrassTable::next_for_sequential(Brass::Cursor * C_, int /*dummy*/) const
2140 : : {
2141 : : LOGCALL(DB, bool, "BrassTable::next_for_sequential", Literal("C_") | Literal("/*dummy*/"));
2142 : 116217 : byte * p = C_[0].p;
2143 : : Assert(p);
2144 : 116217 : int c = C_[0].c;
2145 : 116217 : c += D2;
2146 : : Assert((unsigned)c < block_size);
2147 [ + + ]: 116217 : if (c == DIR_END(p)) {
2148 : 14821 : uint4 n = C_[0].n;
2149 : 19 : while (true) {
2150 : 14840 : n++;
2151 [ + + ]: 14840 : if (n > base.get_last_block()) RETURN(false);
2152 [ + + ]: 14507 : if (writable) {
2153 [ - + ]: 48 : if (n == C[0].n) {
2154 : : // Block is a leaf block in the built-in cursor
2155 : : // (potentially in modified form).
2156 : 0 : memcpy(p, C[0].p, block_size);
2157 : : } else {
2158 : : // Blocks in the built-in cursor may not have been written
2159 : : // to disk yet, so we have to check that the block number
2160 : : // isn't in the built-in cursor or we'll read an
2161 : : // uninitialised block (for which GET_LEVEL(p) will
2162 : : // probably return 0).
2163 : : int j;
2164 [ + + ]: 90 : for (j = 1; j <= level; ++j) {
2165 [ + + ]: 48 : if (n == C[j].n) break;
2166 : : }
2167 [ + + ]: 48 : if (j <= level) continue;
2168 : :
2169 : : // Block isn't in the built-in cursor, so the form on disk
2170 : : // is valid, so read it to check if it's the next level 0
2171 : : // block.
2172 : 42 : read_block(n, p);
2173 : : }
2174 : : } else {
2175 : 14459 : read_block(n, p);
2176 : : }
2177 : 14501 : if (writable) AssertEq(revision_number, latest_revision_number);
2178 [ - + ]: 14501 : if (REVISION(p) > revision_number + writable) {
2179 : 0 : set_overwritten();
2180 : : RETURN(false);
2181 : : }
2182 [ + + ]: 14501 : if (GET_LEVEL(p) == 0) break;
2183 : : }
2184 : 14488 : c = DIR_START;
2185 : 14488 : C_[0].n = n;
2186 : : }
2187 : 115884 : C_[0].c = c;
2188 : 116217 : RETURN(true);
2189 : : }
2190 : :
2191 : : bool
2192 : 4814747 : BrassTable::prev_default(Brass::Cursor * C_, int j) const
2193 : : {
2194 : : LOGCALL(DB, bool, "BrassTable::prev_default", Literal("C_") | j);
2195 : 4814747 : byte * p = C_[j].p;
2196 : 4814747 : int c = C_[j].c;
2197 : : Assert(c >= DIR_START);
2198 : : Assert((unsigned)c < block_size);
2199 : : Assert(c <= DIR_END(p));
2200 [ + + ]: 4814747 : if (c == DIR_START) {
2201 [ - + ]: 933400 : if (j == level) RETURN(false);
2202 [ - + ]: 933400 : if (!prev_default(C_, j + 1)) RETURN(false);
2203 : 933400 : c = DIR_END(p);
2204 : : }
2205 : 4814747 : c -= D2;
2206 : 4814747 : C_[j].c = c;
2207 [ + + ]: 4814747 : if (j > 0) {
2208 : 933400 : block_to_cursor(C_, j - 1, Item(p, c).block_given_by());
2209 : : }
2210 : 4814747 : RETURN(true);
2211 : : }
2212 : :
2213 : : bool
2214 : 7797500 : BrassTable::next_default(Brass::Cursor * C_, int j) const
2215 : : {
2216 : : LOGCALL(DB, bool, "BrassTable::next_default", Literal("C_") | j);
2217 : 7797500 : byte * p = C_[j].p;
2218 : 7797500 : int c = C_[j].c;
2219 : : Assert(c >= DIR_START);
2220 : 7797500 : c += D2;
2221 : : Assert((unsigned)c < block_size);
2222 : : // Sometimes c can be DIR_END(p) + 2 here it appears...
2223 [ + + ]: 7797500 : if (c >= DIR_END(p)) {
2224 [ + + ]: 1567596 : if (j == level) RETURN(false);
2225 [ + + ]: 1546005 : if (!next_default(C_, j + 1)) RETURN(false);
2226 : 1525506 : c = DIR_START;
2227 : : }
2228 : 7755410 : C_[j].c = c;
2229 [ + + ]: 7755410 : if (j > 0) {
2230 : 1525506 : block_to_cursor(C_, j - 1, Item(p, c).block_given_by());
2231 : : #ifdef BTREE_DEBUG_FULL
2232 : : printf("Block in BrassTable:next_default");
2233 : : report_block_full(j - 1, C_[j - 1].n, C_[j - 1].p);
2234 : : #endif /* BTREE_DEBUG_FULL */
2235 : : }
2236 : 7797500 : RETURN(true);
2237 : : }
2238 : :
2239 : : void
2240 : 13 : BrassTable::throw_database_closed()
2241 : : {
2242 : 13 : throw Xapian::DatabaseError("Database has been closed");
2243 : : }
2244 : :
2245 : : /** Compares this key with key2.
2246 : :
2247 : : The result is true if this key precedes key2. The comparison is for byte
2248 : : sequence collating order, taking lengths into account. So if the keys are
2249 : : made up of lower case ASCII letters we get alphabetical ordering.
2250 : :
2251 : : Now remember that items are added into the B-tree in fastest time
2252 : : when they are preordered by their keys. This is therefore the piece
2253 : : of code that needs to be followed to arrange for the preordering.
2254 : :
2255 : : This is complicated by the fact that keys have two parts - a value
2256 : : and then a count. We first compare the values, and only if they
2257 : : are equal do we compare the counts.
2258 : : */
2259 : :
2260 : 38389196 : bool Key::operator<(Key key2) const
2261 : : {
2262 : : LOGCALL(DB, bool, "Key::operator<", static_cast<const void*>(key2.p));
2263 : 38389196 : int key1_len = length();
2264 : 38389196 : int key2_len = key2.length();
2265 [ + + ]: 38389196 : if (key1_len == key2_len) {
2266 : : // The keys are the same length, so we can compare the counts
2267 : : // in the same operation since they're stored as 2 byte
2268 : : // bigendian numbers.
2269 : 23344438 : RETURN(memcmp(p + K1, key2.p + K1, key1_len + C2) < 0);
2270 : : }
2271 : :
2272 [ + + ]: 15044758 : int k_smaller = (key2_len < key1_len ? key2_len : key1_len);
2273 : :
2274 : : // Compare the common part of the keys
2275 : 15044758 : int diff = memcmp(p + K1, key2.p + K1, k_smaller);
2276 [ + + ]: 15044758 : if (diff != 0) RETURN(diff < 0);
2277 : :
2278 : : // We dealt with the "same length" case above so we never need to check
2279 : : // the count here.
2280 : 38389196 : RETURN(key1_len < key2_len);
2281 : : }
2282 : :
2283 : 4502843 : bool Key::operator==(Key key2) const
2284 : : {
2285 : : LOGCALL(DB, bool, "Key::operator==", static_cast<const void*>(key2.p));
2286 : 4502843 : int key1_len = length();
2287 [ + + ]: 4502843 : if (key1_len != key2.length()) RETURN(false);
2288 : : // The keys are the same length, so we can compare the counts
2289 : : // in the same operation since they're stored as 2 byte
2290 : : // bigendian numbers.
2291 : 4502843 : RETURN(memcmp(p + K1, key2.p + K1, key1_len + C2) == 0);
2292 : : }
|
