LCOV - code coverage report
Current view: top level - backends/glass - glass_table.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core c2b6f1024d3a Lines: 780 855 91.2 %
Date: 2019-05-16 09:13:18 Functions: 51 53 96.2 %
Branches: 512 860 59.5 %

           Branch data     Line data    Source code
       1                 :            : /** @file glass_table.cc
       2                 :            :  * @brief Btree implementation
       3                 :            :  */
       4                 :            : /* Copyright 1999,2000,2001 BrightStation PLC
       5                 :            :  * Copyright 2002 Ananova Ltd
       6                 :            :  * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010,2011,2012,2013,2014,2015,2016 Olly Betts
       7                 :            :  * Copyright 2008 Lemur Consulting Ltd
       8                 :            :  *
       9                 :            :  * This program is free software; you can redistribute it and/or
      10                 :            :  * modify it under the terms of the GNU General Public License as
      11                 :            :  * published by the Free Software Foundation; either version 2 of the
      12                 :            :  * License, or (at your option) any later version.
      13                 :            :  *
      14                 :            :  * This program is distributed in the hope that it will be useful,
      15                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      16                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      17                 :            :  * GNU General Public License for more details.
      18                 :            :  *
      19                 :            :  * You should have received a copy of the GNU General Public License
      20                 :            :  * along with this program; if not, write to the Free Software
      21                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
      22                 :            :  * USA
      23                 :            :  */
      24                 :            : 
      25                 :            : #include <config.h>
      26                 :            : 
      27                 :            : #include "glass_table.h"
      28                 :            : 
      29                 :            : #include <xapian/error.h>
      30                 :            : 
      31                 :            : #include "omassert.h"
      32                 :            : #include "posixy_wrapper.h"
      33                 :            : #include "str.h"
      34                 :            : #include "stringutils.h" // For STRINGIZE().
      35                 :            : 
      36                 :            : #include <sys/types.h>
      37                 :            : 
      38                 :            : #include <cerrno>
      39                 :            : #include <cstring>   /* for memmove */
      40                 :            : #include <climits>   /* for CHAR_BIT */
      41                 :            : 
      42                 :            : #include "glass_freelist.h"
      43                 :            : #include "glass_changes.h"
      44                 :            : #include "glass_cursor.h"
      45                 :            : #include "glass_defs.h"
      46                 :            : #include "glass_version.h"
      47                 :            : 
      48                 :            : #include "debuglog.h"
      49                 :            : #include "filetests.h"
      50                 :            : #include "io_utils.h"
      51                 :            : #include "pack.h"
      52                 :            : #include "wordaccess.h"
      53                 :            : 
      54                 :            : #include <algorithm>  // for std::min()
      55                 :            : #include <string>
      56                 :            : 
      57                 :            : #include "xapian/constants.h"
      58                 :            : 
      59                 :            : using namespace Glass;
      60                 :            : using namespace std;
      61                 :            : 
      62                 :            : //#define BTREE_DEBUG_FULL 1
      63                 :            : #undef BTREE_DEBUG_FULL
      64                 :            : 
      65                 :            : #ifdef BTREE_DEBUG_FULL
      66                 :            : /*------debugging aids from here--------*/
      67                 :            : 
      68                 :            : static void print_key(const uint8_t * p, int c, int j);
      69                 :            : static void print_tag(const uint8_t * p, int c, int j);
      70                 :            : 
      71                 :            : /*
      72                 :            : static void report_cursor(int N, Btree * B, Glass::Cursor * C)
      73                 :            : {
      74                 :            :     int i;
      75                 :            :     printf("%d)\n", N);
      76                 :            :     for (i = 0; i <= B->level; i++)
      77                 :            :         printf("p=%d, c=%d, n=[%d], rewrite=%d\n",
      78                 :            :                 C[i].p, C[i].c, C[i].n, C[i].rewrite);
      79                 :            : }
      80                 :            : */
      81                 :            : 
      82                 :            : /*------to here--------*/
      83                 :            : #endif /* BTREE_DEBUG_FULL */
      84                 :            : 
      85                 :      22810 : static inline uint8_t *zeroed_new(size_t size)
      86                 :            : {
      87                 :      22810 :     uint8_t *temp = new uint8_t[size];
      88                 :      22810 :     memset(temp, 0, size);
      89                 :      22810 :     return temp;
      90                 :            : }
      91                 :            : 
      92                 :            : /* A B-tree consists of a file with extension GLASS_TABLE_EXTENSION divided
      93                 :            :    into a sequence of equal sized blocks, numbered 0, 1, 2 ... some of which
      94                 :            :    are free, some in use. Those in use are arranged in a tree.  Lists of
      95                 :            :    currently unused blocks are stored in a freelist which is itself stored in
      96                 :            :    unused blocks.
      97                 :            : 
      98                 :            :    Some "root info" is needed to locate a particular revision of the B-tree
      99                 :            :    - this is stored in the "version file" (we store this data for all tables
     100                 :            :    at a particular revision together).
     101                 :            : 
     102                 :            :    Each block, b, has a structure like this:
     103                 :            : 
     104                 :            :      R L M T D o1 o2 o3 ... oN <gap> [item] .. [item] .. [item] ...
     105                 :            :      <---------- D ----------> <-M->
     106                 :            : 
     107                 :            :    And then,
     108                 :            : 
     109                 :            :    R = REVISION(b)  is the revision number the B-tree had when the block was
     110                 :            :                     written into the DB file.
     111                 :            :    L = GET_LEVEL(b) is the level of the block, which is the number of levels
     112                 :            :                     towards the root of the B-tree structure. So leaf blocks
     113                 :            :                     have level 0 and the one root block has the highest level
     114                 :            :                     equal to the number of levels in the B-tree.  For blocks
     115                 :            :                     storing the freelist, the level is set to 254.
     116                 :            :    M = MAX_FREE(b)  is the size of the gap between the end of the directory and
     117                 :            :                     the first item of data. (It is not necessarily the maximum
     118                 :            :                     size among the bits of space that are free, but I can't
     119                 :            :                     think of a better name.)
     120                 :            :    T = TOTAL_FREE(b)is the total amount of free space left in b.
     121                 :            :    D = DIR_END(b)   gives the offset to the end of the directory.
     122                 :            : 
     123                 :            :    o1, o2 ... oN are a directory of offsets to the N items held in the block.
     124                 :            :    The items are key-tag pairs, and as they occur in the directory are ordered
     125                 :            :    by the keys.
     126                 :            : 
     127                 :            :    An item has this form:
     128                 :            : 
     129                 :            :            I K key X tag
     130                 :            :                ←K→
     131                 :            :            <------I---->
     132                 :            : 
     133                 :            :    A long tag presented through the API is split up into C pieces small enough
     134                 :            :    to be accommodated in the blocks of the B-tree. The key is extended to
     135                 :            :    include a counter, x, which runs from 1 to C. The key is preceded by a
     136                 :            :    length, K, and the whole item with a length, I, as depicted above.  The
     137                 :            :    upper bits of I encode a flag indicating if this item is compressed, and a
     138                 :            :    flag saying if this is the last piece of a tag (i.e. if x == C).
     139                 :            : 
     140                 :            :    Here are the corresponding definitions:
     141                 :            : 
     142                 :            : */
     143                 :            : 
     144                 :            : /** Flip to sequential addition block-splitting after this number of observed
     145                 :            :  *  sequential additions (in negated form). */
     146                 :            : #define SEQ_START_POINT (-10)
     147                 :            : 
     148                 :            : /* Note use of the limits.h values:
     149                 :            :    UCHAR_MAX = 255, an unsigned with all bits set, and
     150                 :            :    CHAR_BIT = 8, the number of bits per byte
     151                 :            : 
     152                 :            :    BYTE_PAIR_RANGE below is the smallest +ve number that can't be held in two
     153                 :            :    bytes -- 64K effectively.
     154                 :            : */
     155                 :            : 
     156                 :            : #define BYTE_PAIR_RANGE (1 << 2 * CHAR_BIT)
     157                 :            : 
     158                 :            : /// read_block(n, p) reads block n of the DB file to address p.
     159                 :            : void
     160                 :    5108190 : GlassTable::read_block(uint4 n, uint8_t * p) const
     161                 :            : {
     162                 :            :     // Log the value of p, not the contents of the block it points to...
     163                 :            :     LOGCALL_VOID(DB, "GlassTable::read_block", n | (void*)p);
     164         [ +  + ]:    5108190 :     if (rare(handle == -2))
     165                 :          1 :         GlassTable::throw_database_closed();
     166                 :            :     AssertRel(n,<,free_list.get_first_unused_block());
     167                 :            : 
     168                 :    5108189 :     io_read_block(handle, reinterpret_cast<char *>(p), block_size, n, offset);
     169                 :            : 
     170         [ +  + ]:    5108189 :     if (GET_LEVEL(p) != LEVEL_FREELIST) {
     171                 :    5107824 :         int dir_end = DIR_END(p);
     172 [ +  - ][ -  + ]:    5107824 :         if (rare(dir_end < DIR_START || unsigned(dir_end) > block_size)) {
                 [ -  + ]
     173         [ #  # ]:          0 :             string msg("dir_end invalid in block ");
     174 [ #  # ][ #  # ]:          0 :             msg += str(n);
     175 [ #  # ][ #  # ]:    5107824 :             throw Xapian::DatabaseCorruptError(msg);
     176                 :            :         }
     177                 :            :     }
     178                 :    5108189 : }
     179                 :            : 
     180                 :            : /** write_block(n, p, appending) writes block n in the DB file from address p.
     181                 :            :  *
     182                 :            :  *  If appending is true (not specified it defaults to false), then this
     183                 :            :  *  indicates that we've added data to a block in space which was previously
     184                 :            :  *  unused, and are writing the block back in place - we use this to add
     185                 :            :  *  free list entries (the information about where the freelist data for a
     186                 :            :  *  revision begins and ends is stored in the "iamglass" file).  We don't
     187                 :            :  *  currently use this flag for much, but it signifies that we don't risk
     188                 :            :  *  invalidating any existing revisions, which may be useful information.
     189                 :            :  */
     190                 :            : void
     191                 :     631804 : GlassTable::write_block(uint4 n, const uint8_t * p, bool appending) const
     192                 :            : {
     193                 :            :     LOGCALL_VOID(DB, "GlassTable::write_block", n | p | appending);
     194                 :            :     Assert(writable);
     195                 :            :     /* Check that n is in range. */
     196                 :            :     AssertRel(n,<,free_list.get_first_unused_block());
     197                 :            : 
     198                 :            :     /* don't write to non-free */
     199                 :            :     // FIXME: We can no longer check this easily.
     200                 :            :     // AssertParanoid(free_list.block_free_at_start(block_size, n));
     201                 :            : 
     202                 :            :     /* write revision is okay */
     203                 :            :     AssertEqParanoid(REVISION(p), revision_number + 1);
     204                 :            : 
     205         [ +  + ]:     631804 :     if (appending) {
     206                 :            :         // In the case of the freelist, new entries can safely be written into
     207                 :            :         // the space at the end of the latest freelist block, as that's unused
     208                 :            :         // by previous revisions.  It is also safe to write into a block which
     209                 :            :         // wasn't used in the previous revision.
     210                 :            :         //
     211                 :            :         // It's only when we start a new freelist block that we need to worry
     212                 :            :         // about invalidating old revisions.
     213                 :     615118 :     } else if (flags & Xapian::DB_DANGEROUS) {
     214                 :            :         // FIXME: We should somehow flag this to prevent readers opening the
     215                 :            :         // database.  Removing "iamglass" or setting a flag in it doesn't deal
     216                 :            :         // with any existing readers though.  Perhaps we want to have readers
     217                 :            :         // read lock and try to take an exclusive lock here?
     218                 :            :     }
     219                 :            : 
     220                 :     631804 :     const char * p_char = reinterpret_cast<const char *>(p);
     221         [ +  - ]:     631804 :     io_write_block(handle, p_char, block_size, n, offset);
     222                 :            : 
     223         [ +  + ]:     631904 :     if (!changes_obj) return;
     224                 :            : 
     225                 :            :     unsigned char v;
     226                 :            :     // FIXME: track table_type in this class?
     227         [ +  + ]:        100 :     if (strcmp(tablename, "position") == 0) {
     228                 :         16 :         v = int(Glass::POSITION);
     229         [ +  + ]:         84 :     } else if (strcmp(tablename, "postlist") == 0) {
     230                 :         28 :         v = int(Glass::POSTLIST);
     231         [ +  + ]:         56 :     } else if (strcmp(tablename, "docdata") == 0) {
     232                 :         28 :         v = int(Glass::DOCDATA);
     233         [ -  + ]:         28 :     } else if (strcmp(tablename, "spelling") == 0) {
     234                 :          0 :         v = int(Glass::SPELLING);
     235         [ -  + ]:         28 :     } else if (strcmp(tablename, "synonym") == 0) {
     236                 :          0 :         v = int(Glass::SYNONYM);
     237         [ +  - ]:         28 :     } else if (strcmp(tablename, "termlist") == 0) {
     238                 :         28 :         v = int(Glass::TERMLIST);
     239                 :            :     } else {
     240                 :          0 :         return; // FIXME
     241                 :            :     }
     242                 :            : 
     243         [ +  - ]:        100 :     if (block_size == 2048) {
     244                 :        100 :         v |= 0 << 3;
     245         [ #  # ]:          0 :     } else if (block_size == 4096) {
     246                 :          0 :         v |= 1 << 3;
     247         [ #  # ]:          0 :     } else if (block_size == 8192) {
     248                 :          0 :         v |= 2 << 3;
     249         [ #  # ]:          0 :     } else if (block_size == 16384) {
     250                 :          0 :         v |= 3 << 3;
     251         [ #  # ]:          0 :     } else if (block_size == 32768) {
     252                 :          0 :         v |= 4 << 3;
     253         [ #  # ]:          0 :     } else if (block_size == 65536) {
     254                 :          0 :         v |= 5 << 3;
     255                 :            :     } else {
     256                 :          0 :         return; // FIXME
     257                 :            :     }
     258                 :            : 
     259         [ +  - ]:        100 :     string buf;
     260         [ +  - ]:        100 :     buf += char(v);
     261                 :            :     // Write the block number to the file
     262         [ +  - ]:        100 :     pack_uint(buf, n);
     263                 :            : 
     264         [ +  - ]:        100 :     changes_obj->write_block(buf);
     265         [ +  - ]:        100 :     changes_obj->write_block(reinterpret_cast<const char *>(p), block_size);
     266                 :            : }
     267                 :            : 
     268                 :            : /* A note on cursors:
     269                 :            : 
     270                 :            :    Each B-tree level has a corresponding array element C[j] in a
     271                 :            :    cursor, C. C[0] is the leaf (or data) level, and C[B->level] is the
     272                 :            :    root block level. Within a level j,
     273                 :            : 
     274                 :            :        C[j].p  addresses the block
     275                 :            :        C[j].c  is the offset into the directory entry in the block
     276                 :            :        C[j].n  is the number of the block at C[j].p
     277                 :            : 
     278                 :            :    A look up in the B-tree causes navigation of the blocks starting
     279                 :            :    from the root. In each block, p, we find an offset, c, to an item
     280                 :            :    which gives the number, n, of the block for the next level. This
     281                 :            :    leads to an array of values p,c,n which are held inside the cursor.
     282                 :            : 
     283                 :            :    Any Btree object B has a built-in cursor, at B->C. But other cursors may
     284                 :            :    be created.  If BC is a created cursor, BC->C is the cursor in the
     285                 :            :    sense given above, and BC->B is the handle for the B-tree again.
     286                 :            : */
     287                 :            : 
     288                 :            : void
     289                 :          2 : GlassTable::set_overwritten() const
     290                 :            : {
     291                 :            :     LOGCALL_VOID(DB, "GlassTable::set_overwritten", NO_ARGS);
     292                 :            :     // If we're writable, there shouldn't be another writer who could cause
     293                 :            :     // overwritten to be flagged, so that's a DatabaseCorruptError.
     294         [ -  + ]:          2 :     if (writable)
     295 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Db block overwritten - are there multiple writers?");
                 [ #  # ]
     296 [ +  - ][ +  - ]:          2 :     throw Xapian::DatabaseModifiedError("The revision being read has been discarded - you should call Xapian::Database::reopen() and retry the operation");
                 [ +  - ]
     297                 :            : }
     298                 :            : 
     299                 :            : /* block_to_cursor(C, j, n) puts block n into position C[j] of cursor
     300                 :            :    C, writing the block currently at C[j] back to disk if necessary.
     301                 :            :    Note that
     302                 :            : 
     303                 :            :        C[j].rewrite
     304                 :            : 
     305                 :            :    is true iff C[j].n is different from block n in file DB. If it is
     306                 :            :    false no rewriting is necessary.
     307                 :            : */
     308                 :            : 
     309                 :            : void
     310                 :   13131381 : GlassTable::block_to_cursor(Glass::Cursor * C_, int j, uint4 n) const
     311                 :            : {
     312                 :            :     LOGCALL_VOID(DB, "GlassTable::block_to_cursor", (void*)C_ | j | n);
     313         [ +  + ]:   18297593 :     if (n == C_[j].get_n()) return;
     314                 :            : 
     315 [ +  + ][ +  + ]:    5166215 :     if (writable && C_[j].rewrite) {
     316                 :            :         Assert(C == C_);
     317                 :     558509 :         write_block(C_[j].get_n(), C_[j].get_p());
     318                 :     558509 :         C_[j].rewrite = false;
     319                 :            :     }
     320                 :            : 
     321                 :            :     // Check if the block is in the built-in cursor (potentially in
     322                 :            :     // modified form).
     323                 :            :     const uint8_t * p;
     324         [ +  + ]:    5166215 :     if (n == C[j].get_n()) {
     325                 :      60365 :         p = C_[j].clone(C[j]);
     326                 :            :     } else {
     327                 :    5105850 :         uint8_t * q = C_[j].init(block_size);
     328                 :    5105850 :         read_block(n, q);
     329                 :    5105849 :         p = q;
     330                 :    5105849 :         C_[j].set_n(n);
     331                 :            :     }
     332                 :            : 
     333         [ +  + ]:    5166214 :     if (j < level) {
     334                 :            :         /* unsigned comparison */
     335         [ +  + ]:    5111559 :         if (rare(REVISION(p) > REVISION(C_[j + 1].get_p()))) {
     336                 :          2 :             set_overwritten();
     337                 :            :             return;
     338                 :            :         }
     339                 :            :     }
     340                 :            : 
     341         [ -  + ]:    5166212 :     if (rare(j != GET_LEVEL(p))) {
     342         [ #  # ]:          0 :         string msg = "Expected block ";
     343 [ #  # ][ #  # ]:          0 :         msg += str(n);
     344         [ #  # ]:          0 :         msg += " to be level ";
     345 [ #  # ][ #  # ]:          0 :         msg += str(j);
     346         [ #  # ]:          0 :         msg += ", not ";
     347 [ #  # ][ #  # ]:          0 :         msg += str(GET_LEVEL(p));
     348 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError(msg);
     349                 :            :     }
     350                 :            : }
     351                 :            : 
     352                 :            : /** Btree::alter(); is called when the B-tree is to be altered.
     353                 :            : 
     354                 :            :    It causes new blocks to be forced for the current set of blocks in
     355                 :            :    the cursor.
     356                 :            : 
     357                 :            :    The point is that if a block at level 0 is to be altered it may get
     358                 :            :    a new number. Then the pointer to this block from level 1 will need
     359                 :            :    changing. So the block at level 1 needs altering and may get a new
     360                 :            :    block number. Then the pointer to this block from level 2 will need
     361                 :            :    changing ... and so on back to the root.
     362                 :            : 
     363                 :            :    The clever bit here is spotting the cases when we can make an early
     364                 :            :    exit from this process. If C[j].rewrite is true, C[j+k].rewrite
     365                 :            :    will be true for k = 1,2 ... We have been through all this before,
     366                 :            :    and there is no need to do it again. If C[j].n was free at the
     367                 :            :    start of the transaction, we can copy it back to the same place
     368                 :            :    without violating the integrity of the B-tree. We don't then need a
     369                 :            :    new n and can return. The corresponding C[j].rewrite may be true or
     370                 :            :    false in that case.
     371                 :            : */
     372                 :            : 
     373                 :            : void
     374                 :    3727603 : GlassTable::alter()
     375                 :            : {
     376                 :            :     LOGCALL_VOID(DB, "GlassTable::alter", NO_ARGS);
     377                 :            :     Assert(writable);
     378         [ +  + ]:    3727603 :     if (flags & Xapian::DB_DANGEROUS) {
     379                 :      89475 :         C[0].rewrite = true;
     380                 :      89475 :         return;
     381                 :            :     }
     382                 :    3638128 :     int j = 0;
     383                 :            :     while (true) {
     384         [ +  + ]:    3761872 :         if (C[j].rewrite) return; /* all new, so return */
     385                 :     589720 :         C[j].rewrite = true;
     386                 :            : 
     387                 :     589720 :         glass_revision_number_t rev = REVISION(C[j].get_p());
     388         [ +  + ]:     589720 :         if (rev == revision_number + 1) {
     389                 :     449305 :             return;
     390                 :            :         }
     391                 :            :         Assert(rev < revision_number + 1);
     392                 :     140415 :         uint4 n = C[j].get_n();
     393                 :     140415 :         free_list.mark_block_unused(this, block_size, n);
     394                 :     140415 :         SET_REVISION(C[j].get_modifiable_p(block_size), revision_number + 1);
     395                 :     140415 :         n = free_list.get_block(this, block_size);
     396                 :     140415 :         C[j].set_n(n);
     397                 :            : 
     398         [ +  + ]:     140415 :         if (j == level) return;
     399                 :     123744 :         j++;
     400         [ +  - ]:     123744 :         BItem_wr(C[j].get_modifiable_p(block_size), C[j].c).set_block_given_by(n);
     401                 :    3851347 :     }
     402                 :            : }
     403                 :            : 
     404                 :            : /** find_in_leaf(p, key, c, exact) searches for the key in the leaf block at p.
     405                 :            : 
     406                 :            :    What we get is the directory entry to the last key <= the key being searched
     407                 :            :    for.
     408                 :            : 
     409                 :            :    The lookup is by binary chop, with i and j set to the left and
     410                 :            :    right ends of the search area. In sequential addition, c will often
     411                 :            :    be the answer, so we test the keys round c and move i and j towards
     412                 :            :    c if possible.
     413                 :            : 
     414                 :            :    exact is set to true if the match was exact (otherwise exact is unchanged).
     415                 :            : */
     416                 :            : 
     417                 :            : int
     418                 :    9110713 : GlassTable::find_in_leaf(const uint8_t * p, LeafItem item, int c, bool& exact)
     419                 :            : {
     420                 :            :     LOGCALL_STATIC(DB, int, "GlassTable::find_in_leaf", (const void*)p | (const void *)item.get_address() | c | Literal("bool&"));
     421                 :            :     // c should be odd (either -1, or an even offset from DIR_START).
     422                 :            :     Assert((c & 1) == 1);
     423                 :    9110713 :     int i = DIR_START;
     424                 :    9110713 :     i -= D2;
     425                 :            :     if (c != -1) {
     426                 :            :         AssertRel(i,<=,c);
     427                 :            :     }
     428                 :    9110713 :     int j = DIR_END(p);
     429                 :            : 
     430         [ +  + ]:    9110713 :     if (c != -1) {
     431 [ +  + ][ +  + ]:    6230390 :         if (c < j && i < c) {
     432         [ +  - ]:    6214209 :             int r = compare(LeafItem(p, c), item);
     433         [ +  + ]:    6214209 :             if (r == 0) {
     434                 :    1122810 :                 exact = true;
     435                 :    1122810 :                 return c;
     436                 :            :             }
     437         [ +  + ]:    5091399 :             if (r < 0) i = c;
     438                 :            :         }
     439                 :    5107580 :         c += D2;
     440 [ +  + ][ +  - ]:    5107580 :         if (c < j && i < c) {
     441         [ +  - ]:    1940858 :             int r = compare(item, LeafItem(p, c));
     442         [ +  + ]:    1940858 :             if (r == 0) {
     443                 :     515964 :                 exact = true;
     444                 :     515964 :                 return c;
     445                 :            :             }
     446         [ +  + ]:    4591616 :             if (r < 0) j = c;
     447                 :            :         }
     448                 :            :     }
     449                 :            : 
     450         [ +  + ]:   22344288 :     while (j - i > D2) {
     451                 :   16161097 :         int k = i + ((j - i) / (D2 * 2)) * D2; /* mid way */
     452         [ +  - ]:   16161097 :         int r = compare(item, LeafItem(p, k));
     453         [ +  + ]:   16161097 :         if (r < 0) {
     454                 :    5650427 :             j = k;
     455                 :            :         } else {
     456                 :   10510670 :             i = k;
     457         [ +  + ]:   10510670 :             if (r == 0) {
     458                 :    1288748 :                 exact = true;
     459                 :    1288748 :                 break;
     460                 :            :             }
     461                 :            :         }
     462                 :            :     }
     463                 :            :     AssertRel(DIR_START - D2,<=,i);
     464                 :            :     AssertRel(i,<,DIR_END(p));
     465                 :    9110713 :     RETURN(i);
     466                 :            : }
     467                 :            : 
     468                 :            : template<typename ITEM> int
     469                 :   10623642 : find_in_branch_(const uint8_t * p, ITEM item, int c)
     470                 :            : {
     471                 :            :     // c should be odd (either -1, or an even offset from DIR_START).
     472                 :            :     Assert((c & 1) == 1);
     473                 :   10623642 :     int i = DIR_START;
     474                 :            :     if (c != -1) {
     475                 :            :         AssertRel(i,<=,c);
     476                 :            :     }
     477                 :   10623642 :     int j = DIR_END(p);
     478                 :            : 
     479   [ #  #  +  + ]:   10623642 :     if (c != -1) {
     480 [ #  # ][ #  # ]:    9515323 :         if (c < j && i < c) {
         [ +  + ][ +  + ]
     481 [ #  # ][ +  - ]:    9258327 :             int r = compare(BItem(p, c), item);
     482 [ #  # ][ +  + ]:    9258327 :             if (r == 0) return c;
     483 [ #  # ][ +  + ]:    9056882 :             if (r < 0) i = c;
     484                 :            :         }
     485                 :    9313878 :         c += D2;
     486 [ #  # ][ #  # ]:    9313878 :         if (c < j && i < c) {
         [ +  + ][ +  - ]
     487 [ #  # ][ +  - ]:    5778587 :             int r = compare(item, BItem(p, c));
     488 [ #  # ][ +  + ]:    5778587 :             if (r == 0) return c;
     489 [ #  # ][ +  + ]:    9150921 :             if (r < 0) j = c;
     490                 :            :         }
     491                 :            :     }
     492                 :            : 
     493 [ #  # ][ +  + ]:   22732894 :     while (j - i > D2) {
     494                 :   12645967 :         int k = i + ((j - i) / (D2 * 2)) * D2; /* mid way */
     495 [ #  # ][ +  - ]:   12645967 :         int r = compare(item, BItem(p, k));
     496 [ #  # ][ +  + ]:   12645967 :         if (r < 0) {
     497                 :    5172392 :             j = k;
     498                 :            :         } else {
     499                 :    7473575 :             i = k;
     500 [ #  # ][ +  + ]:    7473575 :             if (r == 0) break;
     501                 :            :         }
     502                 :            :     }
     503                 :            :     AssertRel(DIR_START,<=,i);
     504                 :            :     AssertRel(i,<,DIR_END(p));
     505                 :   10623642 :     return i;
     506                 :            : }
     507                 :            : 
     508                 :            : int
     509                 :   10623642 : GlassTable::find_in_branch(const uint8_t * p, LeafItem item, int c)
     510                 :            : {
     511                 :            :     LOGCALL_STATIC(DB, int, "GlassTable::find_in_branch", (const void*)p | (const void *)item.get_address() | c);
     512                 :   10623642 :     RETURN(find_in_branch_(p, item, c));
     513                 :            : }
     514                 :            : 
     515                 :            : int
     516                 :          0 : GlassTable::find_in_branch(const uint8_t * p, BItem item, int c)
     517                 :            : {
     518                 :            :     LOGCALL_STATIC(DB, int, "GlassTable::find_in_branch", (const void*)p | (const void *)item.get_address() | c);
     519                 :          0 :     RETURN(find_in_branch_(p, item, c));
     520                 :            : }
     521                 :            : 
     522                 :            : /** find(C_) searches for the key of B->kt in the B-tree.
     523                 :            : 
     524                 :            :    Result is true if found, false otherwise.  When false, the B_tree
     525                 :            :    cursor is positioned at the last key in the B-tree <= the search
     526                 :            :    key.  Goes to first (null) item in B-tree when key length == 0.
     527                 :            : */
     528                 :            : 
     529                 :            : bool
     530                 :    9110716 : GlassTable::find(Glass::Cursor * C_) const
     531                 :            : {
     532                 :            :     LOGCALL(DB, bool, "GlassTable::find", (void*)C_);
     533                 :            :     // Note: the parameter is needed when we're called by GlassCursor
     534                 :            :     const uint8_t * p;
     535                 :            :     int c;
     536         [ +  + ]:   19537860 :     for (int j = level; j > 0; --j) {
     537                 :   10427147 :         p = C_[j].get_p();
     538 [ +  - ][ +  - ]:   10427147 :         c = find_in_branch(p, kt, C_[j].c);
     539                 :            : #ifdef BTREE_DEBUG_FULL
     540                 :            :         printf("Block in GlassTable:find - code position 1");
     541                 :            :         report_block_full(j, C_[j].get_n(), p);
     542                 :            : #endif /* BTREE_DEBUG_FULL */
     543                 :   10427147 :         C_[j].c = c;
     544 [ +  - ][ +  - ]:   10427147 :         block_to_cursor(C_, j - 1, BItem(p, c).block_given_by());
                 [ +  + ]
     545                 :            :     }
     546                 :    9110713 :     p = C_[0].get_p();
     547                 :    9110713 :     bool exact = false;
     548 [ +  - ][ +  - ]:    9110713 :     c = find_in_leaf(p, kt, C_[0].c, exact);
     549                 :            : #ifdef BTREE_DEBUG_FULL
     550                 :            :     printf("Block in GlassTable:find - code position 2");
     551                 :            :     report_block_full(0, C_[0].get_n(), p);
     552                 :            : #endif /* BTREE_DEBUG_FULL */
     553                 :    9110713 :     C_[0].c = c;
     554                 :    9110713 :     RETURN(exact);
     555                 :            : }
     556                 :            : 
     557                 :            : /** compact(p) compact the block at p by shuffling all the items up to the end.
     558                 :            : 
     559                 :            :    MAX_FREE(p) is then maximized, and is equal to TOTAL_FREE(p).
     560                 :            : */
     561                 :            : 
     562                 :            : void
     563                 :     114154 : GlassTable::compact(uint8_t * p)
     564                 :            : {
     565                 :            :     LOGCALL_VOID(DB, "GlassTable::compact", (void*)p);
     566                 :            :     Assert(p != buffer);
     567                 :            :     Assert(writable);
     568                 :     114154 :     int e = block_size;
     569                 :     114154 :     uint8_t * b = buffer;
     570                 :     114154 :     int dir_end = DIR_END(p);
     571         [ +  + ]:     114154 :     if (GET_LEVEL(p) == 0) {
     572                 :            :         // Leaf.
     573         [ +  + ]:    4294146 :         for (int c = DIR_START; c < dir_end; c += D2) {
     574         [ +  - ]:    4180541 :             LeafItem item(p, c);
     575         [ +  - ]:    4180541 :             int l = item.size();
     576                 :    4180541 :             e -= l;
     577                 :    4180541 :             memcpy(b + e, item.get_address(), l);
     578         [ +  - ]:    4180541 :             LeafItem_wr::setD(p, c, e);  /* reform in b */
     579                 :            :         }
     580                 :            :     } else {
     581                 :            :         // Branch.
     582         [ +  + ]:      14381 :         for (int c = DIR_START; c < dir_end; c += D2) {
     583         [ +  - ]:      13832 :             BItem item(p, c);
     584         [ +  - ]:      13832 :             int l = item.size();
     585                 :      13832 :             e -= l;
     586                 :      13832 :             memcpy(b + e, item.get_address(), l);
     587         [ +  - ]:      13832 :             BItem_wr::setD(p, c, e);  /* reform in b */
     588                 :            :         }
     589                 :            :     }
     590                 :     114154 :     memcpy(p + e, b + e, block_size - e);  /* copy back */
     591                 :     114154 :     e -= dir_end;
     592                 :     114154 :     SET_TOTAL_FREE(p, e);
     593                 :     114154 :     SET_MAX_FREE(p, e);
     594                 :     114154 : }
     595                 :            : 
     596                 :            : /** Btree needs to gain a new level to insert more items: so split root block
     597                 :            :  *  and construct a new one.
     598                 :            :  */
     599                 :            : void
     600                 :        352 : GlassTable::split_root(uint4 split_n)
     601                 :            : {
     602                 :            :     LOGCALL_VOID(DB, "GlassTable::split_root", split_n);
     603                 :            :     /* gain a level */
     604                 :        352 :     ++level;
     605                 :            : 
     606                 :            :     /* check level overflow - this isn't something that should ever happen
     607                 :            :      * but deserves more than an Assert()... */
     608         [ -  + ]:        352 :     if (level == BTREE_CURSOR_LEVELS) {
     609 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Btree has grown impossibly large (" STRINGIZE(BTREE_CURSOR_LEVELS) " levels)");
                 [ #  # ]
     610                 :            :     }
     611                 :            : 
     612         [ +  - ]:        352 :     uint8_t * q = C[level].init(block_size);
     613                 :        352 :     memset(q, 0, block_size);
     614                 :        352 :     C[level].c = DIR_START;
     615 [ +  - ][ +  - ]:        352 :     C[level].set_n(free_list.get_block(this, block_size));
     616                 :        352 :     C[level].rewrite = true;
     617         [ +  - ]:        352 :     SET_REVISION(q, revision_number + 1);
     618                 :        352 :     SET_LEVEL(q, level);
     619         [ +  - ]:        352 :     SET_DIR_END(q, DIR_START);
     620         [ +  - ]:        352 :     compact(q);   /* to reset TOTAL_FREE, MAX_FREE */
     621                 :            : 
     622                 :            :     /* form a null key in b with a pointer to the old root */
     623                 :            :     uint8_t b[10]; /* 7 is exact */
     624         [ +  - ]:        352 :     BItem_wr item(b);
     625         [ +  - ]:        352 :     item.form_null_key(split_n);
     626 [ +  - ][ +  - ]:        352 :     add_branch_item(item, level);
     627                 :        352 : }
     628                 :            : 
     629                 :            : /** enter_key_above_leaf(previtem, newitem) is called after a leaf block split.
     630                 :            : 
     631                 :            :    It enters in the block at level C[1] a separating key for the block
     632                 :            :    at level C[0]. The key itself is newitem.key(). previtem is the
     633                 :            :    preceding item, and at level 1 newitem.key() can be trimmed down to the
     634                 :            :    first point of difference to previtem.key() for entry in C[j].
     635                 :            : 
     636                 :            :    This code looks longer than it really is. If j exceeds the number
     637                 :            :    of B-tree levels the root block has split and we have to construct
     638                 :            :    a new one, but this is a rare event.
     639                 :            : 
     640                 :            :    The key is constructed in b, with block number C[0].n as tag,
     641                 :            :    and this is added in with add_item. add_item may itself cause a
     642                 :            :    block split, with a further call to enter_key. Hence the recursion.
     643                 :            : */
     644                 :            : void
     645                 :      20356 : GlassTable::enter_key_above_leaf(LeafItem previtem, LeafItem newitem)
     646                 :            : {
     647                 :            :     LOGCALL_VOID(DB, "GlassTable::enter_key_above_leaf", Literal("previtem") | Literal("newitem"));
     648                 :            :     Assert(writable);
     649                 :            :     Assert(compare(previtem, newitem) < 0);
     650                 :            : 
     651                 :      20356 :     Key prevkey = previtem.key();
     652                 :      20356 :     Key newkey = newitem.key();
     653         [ +  - ]:      20356 :     int new_comp = newitem.component_of();
     654                 :            : 
     655         [ +  - ]:      20356 :     uint4 blocknumber = C[0].get_n();
     656                 :            : 
     657                 :            :     // FIXME update to use Key
     658                 :            :     // Keys are truncated here: but don't truncate the count at the end away.
     659                 :      20356 :     const int newkey_len = newkey.length();
     660                 :            :     AssertRel(newkey_len,>,0);
     661                 :            : 
     662                 :            :     // Truncate the key to the minimal key which differs from prevkey,
     663                 :            :     // the preceding key in the block.
     664                 :      20356 :     int i = 0;
     665                 :      20356 :     const int min_len = min(newkey_len, prevkey.length());
     666 [ +  + ][ +  + ]:     114449 :     while (i < min_len && prevkey[i] == newkey[i]) {
                 [ +  + ]
     667                 :      94093 :         i++;
     668                 :            :     }
     669                 :            : 
     670                 :            :     // Want one byte of difference.
     671         [ +  + ]:      20356 :     if (i < newkey_len) i++;
     672                 :            : 
     673                 :            :     // Enough space for a branch item with maximum length key.
     674                 :            :     uint8_t b[BYTES_PER_BLOCK_NUMBER + K1 + 255 + X2];
     675         [ +  - ]:      20356 :     BItem_wr item(b);
     676                 :            :     AssertRel(i, <=, 255);
     677         [ +  - ]:      20356 :     item.set_truncated_key_and_block(newkey, new_comp, i, blocknumber);
     678                 :            : 
     679                 :            :     // The split block gets inserted into the parent after the pointer to the
     680                 :            :     // current child.
     681                 :            :     AssertEq(C[1].c, find_in_branch(C[1].get_p(), item, C[1].c));
     682                 :      20356 :     C[1].c += D2;
     683                 :      20356 :     C[1].rewrite = true; /* a subtle point: this *is* required. */
     684 [ +  - ][ +  - ]:      20356 :     add_branch_item(item, 1);
     685                 :      20356 : }
     686                 :            : 
     687                 :            : /** enter_key_above_branch(j, newkey) is called after a branch block split.
     688                 :            : 
     689                 :            :    It enters in the block at level C[j] a separating key for the block
     690                 :            :    at level C[j - 1]. The key itself is newkey.
     691                 :            : 
     692                 :            :    This code looks longer than it really is. If j exceeds the number
     693                 :            :    of B-tree levels the root block has split and we have to construct
     694                 :            :    a new one, but this is a rare event.
     695                 :            : 
     696                 :            :    The key is constructed in b, with block number C[j - 1].n as tag,
     697                 :            :    and this is added in with add_item. add_item may itself cause a
     698                 :            :    block split, with a further call to enter_key. Hence the recursion.
     699                 :            : */
     700                 :            : void
     701                 :         89 : GlassTable::enter_key_above_branch(int j, BItem newitem)
     702                 :            : {
     703                 :            :     LOGCALL_VOID(DB, "GlassTable::enter_key_above_branch", j | Literal("newitem"));
     704                 :            :     Assert(writable);
     705                 :            :     AssertRel(j,>,1);
     706                 :            : 
     707                 :            :     /* Can't truncate between branch levels, since the separated keys
     708                 :            :      * are in at the leaf level, and truncating again will change the
     709                 :            :      * branch point.
     710                 :            :      */
     711                 :            : 
     712         [ +  - ]:         89 :     uint4 blocknumber = C[j - 1].get_n();
     713                 :            : 
     714                 :            :     // Enough space for a branch item with maximum length key.
     715                 :            :     uint8_t b[BYTES_PER_BLOCK_NUMBER + K1 + 255 + X2];
     716         [ +  - ]:         89 :     BItem_wr item(b);
     717         [ +  - ]:         89 :     item.set_key_and_block(newitem.key(), blocknumber);
     718                 :            : 
     719                 :            :     // The split block gets inserted into the parent after the pointer to the
     720                 :            :     // current child.
     721                 :            :     AssertEq(C[j].c, find_in_branch(C[j].get_p(), item, C[j].c));
     722                 :         89 :     C[j].c += D2;
     723                 :         89 :     C[j].rewrite = true; /* a subtle point: this *is* required. */
     724 [ +  - ][ +  - ]:         89 :     add_branch_item(item, j);
     725                 :         89 : }
     726                 :            : 
     727                 :            : /** mid_point(p) finds the directory entry in c that determines the
     728                 :            :    approximate mid point of the data in the block at p.
     729                 :            :  */
     730                 :            : 
     731                 :            : int
     732                 :       8726 : GlassTable::mid_point(uint8_t * p) const
     733                 :            : {
     734                 :            :     LOGCALL(DB, int, "GlassTable::mid_point", (void*)p);
     735                 :       8726 :     int n = 0;
     736                 :       8726 :     int dir_end = DIR_END(p);
     737                 :       8726 :     int size = block_size - TOTAL_FREE(p) - dir_end;
     738         [ +  - ]:     539798 :     for (int c = DIR_START; c < dir_end; c += D2) {
     739                 :            :         int l;
     740         [ +  + ]:     539798 :         if (GET_LEVEL(p) == 0) {
     741         [ +  - ]:     536328 :             l = LeafItem(p, c).size();
     742                 :            :         } else {
     743         [ +  - ]:       3470 :             l = BItem(p, c).size();
     744                 :            :         }
     745                 :     539798 :         n += 2 * l;
     746         [ +  + ]:     539798 :         if (n >= size) {
     747         [ +  + ]:       8726 :             if (l < n - size) RETURN(c);
     748                 :       4794 :             RETURN(c + D2);
     749                 :            :         }
     750                 :            :     }
     751                 :            : 
     752                 :            :     /* This shouldn't happen, as the sum of the item sizes should be the same
     753                 :            :      * as the value calculated in size, so assert but return a sane value just
     754                 :            :      * in case. */
     755                 :            :     Assert(false);
     756                 :       8726 :     RETURN(dir_end);
     757                 :            : }
     758                 :            : 
     759                 :            : /** add_item_to_leaf(p, kt_, c) adds item kt_ to the leaf block at p.
     760                 :            : 
     761                 :            :    c is the offset in the directory that needs to be expanded to accommodate
     762                 :            :    the new entry for the item.  We know before this is called that there is
     763                 :            :    enough contiguous room for the item in the block, so it's just a matter of
     764                 :            :    shuffling up any directory entries after where we're inserting and copying
     765                 :            :    in the item.
     766                 :            : */
     767                 :            : 
     768                 :            : void
     769                 :    2807916 : GlassTable::add_item_to_leaf(uint8_t * p, LeafItem kt_, int c)
     770                 :            : {
     771                 :            :     LOGCALL_VOID(DB, "GlassTable::add_item_to_leaf", (void*)p | Literal("kt_") | c);
     772                 :            :     Assert(writable);
     773                 :    2807916 :     int dir_end = DIR_END(p);
     774                 :    2807916 :     int kt_len = kt_.size();
     775                 :    2807916 :     int needed = kt_len + D2;
     776                 :    2807916 :     int new_total = TOTAL_FREE(p) - needed;
     777                 :    2807916 :     int new_max = MAX_FREE(p) - needed;
     778                 :            : 
     779                 :            :     Assert(new_total >= 0);
     780                 :            : 
     781                 :            :     AssertRel(MAX_FREE(p),>=,needed);
     782                 :            : 
     783                 :            :     AssertRel(DIR_START,<=,c);
     784                 :            :     AssertRel(c,<=,dir_end);
     785                 :            : 
     786                 :    2807916 :     memmove(p + c + D2, p + c, dir_end - c);
     787                 :    2807916 :     dir_end += D2;
     788                 :    2807916 :     SET_DIR_END(p, dir_end);
     789                 :            : 
     790                 :    2807916 :     int o = dir_end + new_max;
     791                 :    2807916 :     LeafItem_wr::setD(p, c, o);
     792                 :    2807916 :     memmove(p + o, kt_.get_address(), kt_len);
     793                 :            : 
     794                 :    2807916 :     SET_MAX_FREE(p, new_max);
     795                 :            : 
     796                 :    2807916 :     SET_TOTAL_FREE(p, new_total);
     797                 :    2807916 : }
     798                 :            : 
     799                 :            : /** add_item_to_branch(p, kt_, c) adds item kt_ to the branch block at p.
     800                 :            : 
     801                 :            :    c is the offset in the directory that needs to be expanded to accommodate
     802                 :            :    the new entry for the item.  We know before this is called that there is
     803                 :            :    enough contiguous room for the item in the block, so it's just a matter of
     804                 :            :    shuffling up any directory entries after where we're inserting and copying
     805                 :            :    in the item.
     806                 :            : */
     807                 :            : 
     808                 :            : void
     809                 :      20797 : GlassTable::add_item_to_branch(uint8_t * p, BItem kt_, int c)
     810                 :            : {
     811                 :            :     LOGCALL_VOID(DB, "GlassTable::add_item_to_branch", (void*)p | Literal("kt_") | c);
     812                 :            :     Assert(writable);
     813                 :      20797 :     int dir_end = DIR_END(p);
     814                 :      20797 :     int kt_len = kt_.size();
     815                 :      20797 :     int needed = kt_len + D2;
     816                 :      20797 :     int new_total = TOTAL_FREE(p) - needed;
     817                 :      20797 :     int new_max = MAX_FREE(p) - needed;
     818                 :            : 
     819                 :            :     Assert(new_total >= 0);
     820                 :            : 
     821                 :            :     AssertRel(MAX_FREE(p),>=,needed);
     822                 :            : 
     823                 :            :     AssertRel(DIR_START,<=,c);
     824                 :            :     AssertRel(c,<=,dir_end);
     825                 :            : 
     826                 :      20797 :     memmove(p + c + D2, p + c, dir_end - c);
     827                 :      20797 :     dir_end += D2;
     828                 :      20797 :     SET_DIR_END(p, dir_end);
     829                 :            : 
     830                 :      20797 :     int o = dir_end + new_max;
     831                 :      20797 :     BItem_wr::setD(p, c, o);
     832                 :      20797 :     memmove(p + o, kt_.get_address(), kt_len);
     833                 :            : 
     834                 :      20797 :     SET_MAX_FREE(p, new_max);
     835                 :            : 
     836                 :      20797 :     SET_TOTAL_FREE(p, new_total);
     837                 :      20797 : }
     838                 :            : 
     839                 :            : /** GlassTable::add_leaf_item(kt_) adds item kt_ to the leaf block.
     840                 :            :  *
     841                 :            :  *  If there is not enough room the block splits and the item is then
     842                 :            :  *  added to the appropriate half.
     843                 :            :  */
     844                 :            : void
     845                 :    2807916 : GlassTable::add_leaf_item(LeafItem kt_)
     846                 :            : {
     847                 :            :     LOGCALL_VOID(DB, "GlassTable::add_leaf_item", Literal("kt_"));
     848                 :            :     Assert(writable);
     849                 :    2807916 :     uint8_t * p = C[0].get_modifiable_p(block_size);
     850                 :    2807916 :     int c = C[0].c;
     851                 :            :     uint4 n;
     852                 :            : 
     853                 :    2807916 :     int needed = kt_.size() + D2;
     854         [ +  + ]:    2807916 :     if (TOTAL_FREE(p) < needed) {
     855                 :            :         int m;
     856                 :            :         // Prepare to split p. After splitting, the block is in two halves, the
     857                 :            :         // lower half is split_p, the upper half p again. add_to_upper_half
     858                 :            :         // becomes true when the item gets added to p, false when it gets added
     859                 :            :         // to split_p.
     860                 :            : 
     861         [ +  + ]:      20356 :         if (seq_count < 0) {
     862                 :            :             // If we're not in sequential mode, we split at the mid point
     863                 :            :             // of the node.
     864                 :       8674 :             m = mid_point(p);
     865                 :            :         } else {
     866                 :            :             // During sequential addition, split at the insert point
     867                 :            :             AssertRel(c,>=,DIR_START);
     868                 :      11682 :             m = c;
     869                 :            :         }
     870                 :            : 
     871                 :      20356 :         uint4 split_n = C[0].get_n();
     872                 :      20356 :         C[0].set_n(free_list.get_block(this, block_size));
     873                 :            : 
     874                 :      20356 :         memcpy(split_p, p, block_size);  // replicate the whole block in split_p
     875                 :      20356 :         SET_DIR_END(split_p, m);
     876                 :      20356 :         compact(split_p);      /* to reset TOTAL_FREE, MAX_FREE */
     877                 :            : 
     878                 :            :         {
     879                 :      20356 :             int residue = DIR_END(p) - m;
     880                 :      20356 :             int new_dir_end = DIR_START + residue;
     881                 :      20356 :             memmove(p + DIR_START, p + m, residue);
     882                 :      20356 :             SET_DIR_END(p, new_dir_end);
     883                 :            :         }
     884                 :            : 
     885                 :      20356 :         compact(p);      /* to reset TOTAL_FREE, MAX_FREE */
     886                 :            : 
     887                 :            :         bool add_to_upper_half;
     888         [ +  + ]:      20356 :         if (seq_count < 0) {
     889                 :       8674 :             add_to_upper_half = (c >= m);
     890                 :            :         } else {
     891                 :            :             // And add item to lower half if split_p has room, otherwise upper
     892                 :            :             // half
     893                 :      11682 :             add_to_upper_half = (TOTAL_FREE(split_p) < needed);
     894                 :            :         }
     895                 :            : 
     896         [ +  + ]:      20356 :         if (add_to_upper_half) {
     897                 :      18632 :             c -= (m - DIR_START);
     898                 :            :             Assert(seq_count < 0 || c <= DIR_START + D2);
     899                 :            :             Assert(c >= DIR_START);
     900                 :            :             Assert(c <= DIR_END(p));
     901                 :      18632 :             add_item_to_leaf(p, kt_, c);
     902                 :      18632 :             n = C[0].get_n();
     903                 :            :         } else {
     904                 :            :             Assert(c >= DIR_START);
     905                 :            :             Assert(c <= DIR_END(split_p));
     906                 :       1724 :             add_item_to_leaf(split_p, kt_, c);
     907                 :       1724 :             n = split_n;
     908                 :            :         }
     909                 :      20356 :         write_block(split_n, split_p);
     910                 :            : 
     911                 :            :         // Check if we're splitting the root block.
     912         [ +  + ]:      20356 :         if (0 == level) split_root(split_n);
     913                 :            : 
     914                 :            :         /* Enter a separating key at level 1 between */
     915                 :            :         /* the last key of block split_p, and the first key of block p */
     916         [ +  - ]:      20356 :         enter_key_above_leaf(LeafItem(split_p, DIR_END(split_p) - D2),
     917 [ +  - ][ +  - ]:      40712 :                              LeafItem(p, DIR_START));
     918                 :            :     } else {
     919                 :            :         AssertRel(TOTAL_FREE(p),>=,needed);
     920                 :            : 
     921         [ +  + ]:    2787560 :         if (MAX_FREE(p) < needed) {
     922                 :      72893 :             compact(p);
     923                 :            :             AssertRel(MAX_FREE(p),>=,needed);
     924                 :            :         }
     925                 :            : 
     926                 :    2787560 :         add_item_to_leaf(p, kt_, c);
     927                 :    2787560 :         n = C[0].get_n();
     928                 :            :     }
     929                 :            : 
     930                 :    2807916 :     changed_n = n;
     931                 :    2807916 :     changed_c = c;
     932                 :    2807916 : }
     933                 :            : 
     934                 :            : /** GlassTable::add_item(kt_, j) adds item kt_ to the block at cursor level C[j].
     935                 :            :  *
     936                 :            :  *  If there is not enough room the block splits and the item is then
     937                 :            :  *  added to the appropriate half.
     938                 :            :  */
     939                 :            : void
     940                 :      20797 : GlassTable::add_branch_item(BItem kt_, int j)
     941                 :            : {
     942                 :            :     LOGCALL_VOID(DB, "GlassTable::add_branch_item", Literal("kt_") | j);
     943                 :            :     Assert(writable);
     944                 :      20797 :     uint8_t * p = C[j].get_modifiable_p(block_size);
     945                 :      20797 :     int c = C[j].c;
     946                 :            : 
     947                 :      20797 :     int needed = kt_.size() + D2;
     948         [ +  + ]:      20797 :     if (TOTAL_FREE(p) < needed) {
     949                 :            :         int m;
     950                 :            :         // Prepare to split p. After splitting, the block is in two halves, the
     951                 :            :         // lower half is split_p, the upper half p again. add_to_upper_half
     952                 :            :         // becomes true when the item gets added to p, false when it gets added
     953                 :            :         // to split_p.
     954                 :            : 
     955         [ +  + ]:         89 :         if (seq_count < 0) {
     956                 :            :             // If we're not in sequential mode, we split at the mid point
     957                 :            :             // of the node.
     958         [ +  - ]:         52 :             m = mid_point(p);
     959                 :            :         } else {
     960                 :            :             // During sequential addition, split at the insert point
     961                 :            :             AssertRel(c,>=,DIR_START);
     962                 :         37 :             m = c;
     963                 :            :         }
     964                 :            : 
     965         [ +  - ]:         89 :         uint4 split_n = C[j].get_n();
     966 [ +  - ][ +  - ]:         89 :         C[j].set_n(free_list.get_block(this, block_size));
     967                 :            : 
     968                 :         89 :         memcpy(split_p, p, block_size);  // replicate the whole block in split_p
     969         [ +  - ]:         89 :         SET_DIR_END(split_p, m);
     970         [ +  - ]:         89 :         compact(split_p);      /* to reset TOTAL_FREE, MAX_FREE */
     971                 :            : 
     972                 :            :         {
     973         [ +  - ]:         89 :             int residue = DIR_END(p) - m;
     974                 :         89 :             int new_dir_end = DIR_START + residue;
     975                 :         89 :             memmove(p + DIR_START, p + m, residue);
     976         [ +  - ]:         89 :             SET_DIR_END(p, new_dir_end);
     977                 :            :         }
     978                 :            : 
     979         [ +  - ]:         89 :         compact(p);      /* to reset TOTAL_FREE, MAX_FREE */
     980                 :            : 
     981                 :            :         bool add_to_upper_half;
     982         [ +  + ]:         89 :         if (seq_count < 0) {
     983                 :         52 :             add_to_upper_half = (c >= m);
     984                 :            :         } else {
     985                 :            :             // And add item to lower half if split_p has room, otherwise upper
     986                 :            :             // half
     987         [ +  - ]:         37 :             add_to_upper_half = (TOTAL_FREE(split_p) < needed);
     988                 :            :         }
     989                 :            : 
     990         [ +  + ]:         89 :         if (add_to_upper_half) {
     991                 :         76 :             c -= (m - DIR_START);
     992                 :            :             Assert(seq_count < 0 || c <= DIR_START + D2);
     993                 :            :             Assert(c >= DIR_START);
     994                 :            :             Assert(c <= DIR_END(p));
     995         [ +  - ]:         76 :             add_item_to_branch(p, kt_, c);
     996                 :            :         } else {
     997                 :            :             Assert(c >= DIR_START);
     998                 :            :             Assert(c <= DIR_END(split_p));
     999         [ +  - ]:         13 :             add_item_to_branch(split_p, kt_, c);
    1000                 :            :         }
    1001         [ +  - ]:         89 :         write_block(split_n, split_p);
    1002                 :            : 
    1003                 :            :         // Check if we're splitting the root block.
    1004 [ +  + ][ +  - ]:         89 :         if (j == level) split_root(split_n);
    1005                 :            : 
    1006                 :            :         /* Enter a separating key at level j + 1 between */
    1007                 :            :         /* the last key of block split_p, and the first key of block p */
    1008 [ +  - ][ +  - ]:         89 :         enter_key_above_branch(j + 1, BItem(p, DIR_START));
    1009                 :            : 
    1010                 :            :         // In branch levels, we can make the first key of block p null and
    1011                 :            :         // save a bit of disk space.  Other redundant keys will still creep
    1012                 :            :         // in though.
    1013         [ +  - ]:         89 :         BItem_wr item(p, DIR_START);
    1014         [ +  - ]:         89 :         int new_total_free = TOTAL_FREE(p) + item.key().length();
    1015 [ +  - ][ +  - ]:         89 :         item.form_null_key(item.block_given_by());
    1016         [ +  - ]:         89 :         SET_TOTAL_FREE(p, new_total_free);
    1017                 :            :     } else {
    1018                 :            :         AssertRel(TOTAL_FREE(p),>=,needed);
    1019                 :            : 
    1020         [ +  + ]:      20708 :         if (MAX_FREE(p) < needed) {
    1021                 :         19 :             compact(p);
    1022                 :            :             AssertRel(MAX_FREE(p),>=,needed);
    1023                 :            :         }
    1024                 :            : 
    1025                 :      20708 :         add_item_to_branch(p, kt_, c);
    1026                 :            :     }
    1027                 :      20797 : }
    1028                 :            : 
    1029                 :            : /** GlassTable::delete_leaf_item(repeatedly) is (almost) the converse of add_leaf_item.
    1030                 :            :  *
    1031                 :            :  * If repeatedly is true, the process repeats at the next level when a
    1032                 :            :  * block has been completely emptied, freeing the block and taking out
    1033                 :            :  * the pointer to it.  Emptied root blocks are also removed, which
    1034                 :            :  * reduces the number of levels in the B-tree.
    1035                 :            :  */
    1036                 :            : void
    1037                 :     114155 : GlassTable::delete_leaf_item(bool repeatedly)
    1038                 :            : {
    1039                 :            :     LOGCALL_VOID(DB, "GlassTable::delete_leaf_item", repeatedly);
    1040                 :            :     Assert(writable);
    1041                 :     114155 :     uint8_t * p = C[0].get_modifiable_p(block_size);
    1042                 :     114155 :     int c = C[0].c;
    1043                 :            :     AssertRel(DIR_START,<=,c);
    1044                 :            :     AssertRel(c,<,DIR_END(p));
    1045         [ +  - ]:     114155 :     int kt_len = LeafItem(p, c).size(); /* size of the item to be deleted */
    1046                 :     114155 :     int dir_end = DIR_END(p) - D2;   /* directory length will go down by 2 bytes */
    1047                 :            : 
    1048                 :     114155 :     memmove(p + c, p + c + D2, dir_end - c);
    1049                 :     114155 :     SET_DIR_END(p, dir_end);
    1050                 :     114155 :     SET_MAX_FREE(p, MAX_FREE(p) + D2);
    1051                 :     114155 :     SET_TOTAL_FREE(p, TOTAL_FREE(p) + kt_len + D2);
    1052                 :            : 
    1053         [ +  + ]:     156166 :     if (!repeatedly) return;
    1054         [ +  + ]:      42011 :     if (0 < level) {
    1055         [ +  + ]:      40468 :         if (dir_end == DIR_START) {
    1056                 :        357 :             free_list.mark_block_unused(this, block_size, C[0].get_n());
    1057                 :        357 :             C[0].rewrite = false;
    1058                 :        357 :             C[0].set_n(BLK_UNUSED);
    1059                 :        357 :             C[1].rewrite = true;  /* *is* necessary */
    1060                 :        357 :             delete_branch_item(1);
    1061                 :            :         }
    1062                 :            :     }
    1063                 :            : }
    1064                 :            : 
    1065                 :            : /** GlassTable::delete_branch_item(j, repeatedly) is (almost) the converse of add_branch_item.
    1066                 :            :  *
    1067                 :            :  * The process repeats at the next level when a block has been completely
    1068                 :            :  * emptied, freeing the block and taking out the pointer to it.  Emptied root
    1069                 :            :  * blocks are also removed, which reduces the number of levels in the B-tree.
    1070                 :            :  */
    1071                 :            : void
    1072                 :        357 : GlassTable::delete_branch_item(int j)
    1073                 :            : {
    1074                 :            :     LOGCALL_VOID(DB, "GlassTable::delete_branch_item", j);
    1075                 :            :     Assert(writable);
    1076                 :        357 :     uint8_t * p = C[j].get_modifiable_p(block_size);
    1077                 :        357 :     int c = C[j].c;
    1078                 :            :     AssertRel(DIR_START,<=,c);
    1079                 :            :     AssertRel(c,<,DIR_END(p));
    1080         [ +  - ]:        357 :     int kt_len = BItem(p, c).size(); /* size of the item to be deleted */
    1081                 :        357 :     int dir_end = DIR_END(p) - D2;   /* directory length will go down by 2 bytes */
    1082                 :            : 
    1083                 :        357 :     memmove(p + c, p + c + D2, dir_end - c);
    1084                 :        357 :     SET_DIR_END(p, dir_end);
    1085                 :        357 :     SET_MAX_FREE(p, MAX_FREE(p) + D2);
    1086                 :        357 :     SET_TOTAL_FREE(p, TOTAL_FREE(p) + kt_len + D2);
    1087                 :            : 
    1088         [ -  + ]:        357 :     if (j < level) {
    1089         [ #  # ]:          0 :         if (dir_end == DIR_START) {
    1090                 :          0 :             free_list.mark_block_unused(this, block_size, C[j].get_n());
    1091                 :          0 :             C[j].rewrite = false;
    1092                 :          0 :             C[j].set_n(BLK_UNUSED);
    1093                 :          0 :             C[j + 1].rewrite = true;  /* *is* necessary */
    1094                 :          0 :             delete_branch_item(j + 1);
    1095                 :            :         }
    1096                 :            :     } else {
    1097                 :            :         Assert(j == level);
    1098 [ +  + ][ +  + ]:        374 :         while (dir_end == DIR_START + D2 && level > 0) {
    1099                 :            :             /* single item in the root block, so lose a level */
    1100         [ +  - ]:         17 :             uint4 new_root = BItem(C[level].get_p(), DIR_START).block_given_by();
    1101                 :         17 :             free_list.mark_block_unused(this, block_size, C[level].get_n());
    1102                 :         17 :             C[level].destroy();
    1103                 :         17 :             level--;
    1104                 :            : 
    1105                 :         17 :             block_to_cursor(C, level, new_root);
    1106                 :            : 
    1107                 :         17 :             dir_end = DIR_END(C[level].get_p()); /* prepare for the loop */
    1108                 :            :         }
    1109                 :            :     }
    1110                 :        357 : }
    1111                 :            : 
    1112                 :            : /* debugging aid:
    1113                 :            : static addcount = 0;
    1114                 :            : */
    1115                 :            : 
    1116                 :            : /** add_kt(found) adds the item (key-tag pair) at B->kt into the
    1117                 :            :    B-tree, using cursor C.
    1118                 :            : 
    1119                 :            :    found == find() is handed over as a parameter from Btree::add.
    1120                 :            :    Btree::alter() prepares for the alteration to the B-tree. Then
    1121                 :            :    there are a number of cases to consider:
    1122                 :            : 
    1123                 :            :      If an item with the same key is in the B-tree (found is true),
    1124                 :            :      the new kt replaces it.
    1125                 :            : 
    1126                 :            :      If then kt is smaller, or the same size as, the item it replaces,
    1127                 :            :      kt is put in the same place as the item it replaces, and the
    1128                 :            :      TOTAL_FREE measure is reduced.
    1129                 :            : 
    1130                 :            :      If kt is larger than the item it replaces it is put in the
    1131                 :            :      MAX_FREE space if there is room, and the directory entry and
    1132                 :            :      space counts are adjusted accordingly.
    1133                 :            : 
    1134                 :            :      - But if there is not room we do it the long way: the old item is
    1135                 :            :      deleted with delete_leaf_item and kt is added in with add_item.
    1136                 :            : 
    1137                 :            :      If the key of kt is not in the B-tree (found is false), the new
    1138                 :            :      kt is added in with add_item.
    1139                 :            : 
    1140                 :            :      Returns:
    1141                 :            :          0 : added kt
    1142                 :            :          1 : replaced kt
    1143                 :            :          2 : replaced kt and it was the final one
    1144                 :            : */
    1145                 :            : 
    1146                 :            : int
    1147                 :    3685592 : GlassTable::add_kt(bool found)
    1148                 :            : {
    1149                 :            :     LOGCALL(DB, int, "GlassTable::add_kt", found);
    1150                 :            :     Assert(writable);
    1151                 :            : 
    1152                 :            :     /*
    1153                 :            :     {
    1154                 :            :         printf("%d) %s ", addcount++, (found ? "replacing" : "adding"));
    1155                 :            :         print_bytes(kt[I2], kt + I2 + K1); putchar('\n');
    1156                 :            :     }
    1157                 :            :     */
    1158                 :    3685592 :     alter();
    1159                 :            : 
    1160                 :    3685592 :     int result = 0;
    1161         [ +  + ]:    3685592 :     if (found) { /* replacement */
    1162                 :     949820 :         seq_count = SEQ_START_POINT;
    1163                 :     949820 :         sequential = false;
    1164                 :            : 
    1165         [ +  - ]:     949820 :         uint8_t * p = C[0].get_modifiable_p(block_size);
    1166                 :     949820 :         int c = C[0].c;
    1167                 :            :         AssertRel(DIR_START,<=,c);
    1168                 :            :         AssertRel(c,<,DIR_END(p));
    1169         [ +  - ]:     949820 :         LeafItem item(p, c);
    1170         [ +  - ]:     949820 :         int kt_size = kt.size();
    1171         [ +  - ]:     949820 :         int needed = kt_size - item.size();
    1172                 :            : 
    1173         [ +  + ]:     949820 :         result = item.last_component() ? 2 : 1;
    1174                 :            : 
    1175         [ +  + ]:     949820 :         if (needed <= 0) {
    1176                 :            :             /* simple replacement */
    1177                 :     711201 :             memmove(const_cast<uint8_t *>(item.get_address()),
    1178                 :     711201 :                     kt.get_address(), kt_size);
    1179 [ +  - ][ +  - ]:     711201 :             SET_TOTAL_FREE(p, TOTAL_FREE(p) - needed);
    1180                 :            :         } else {
    1181                 :            :             /* new item into the block's freespace */
    1182         [ +  - ]:     238619 :             int new_max = MAX_FREE(p) - kt_size;
    1183         [ +  + ]:     238619 :             if (new_max >= 0) {
    1184         [ +  - ]:     166475 :                 int o = DIR_END(p) + new_max;
    1185                 :     166475 :                 memmove(p + o, kt.get_address(), kt_size);
    1186         [ +  - ]:     166475 :                 LeafItem_wr::setD(p, c, o);
    1187         [ +  - ]:     166475 :                 SET_MAX_FREE(p, new_max);
    1188 [ +  - ][ +  - ]:     166475 :                 SET_TOTAL_FREE(p, TOTAL_FREE(p) - needed);
    1189                 :            :             } else {
    1190                 :            :                 /* do it the long way */
    1191         [ +  - ]:      72144 :                 delete_leaf_item(false);
    1192 [ +  - ][ +  - ]:     949820 :                 add_leaf_item(kt);
    1193                 :            :             }
    1194                 :            :         }
    1195                 :            :     } else {
    1196                 :            :         /* addition */
    1197 [ +  + ][ +  + ]:    2735772 :         if (changed_n == C[0].get_n() && changed_c == C[0].c) {
                 [ +  + ]
    1198         [ +  + ]:    2232767 :             if (seq_count < 0) seq_count++;
    1199                 :            :         } else {
    1200                 :     503005 :             seq_count = SEQ_START_POINT;
    1201                 :     503005 :             sequential = false;
    1202                 :            :         }
    1203                 :    2735772 :         C[0].c += D2;
    1204                 :    2735772 :         add_leaf_item(kt);
    1205                 :            :     }
    1206                 :    3685592 :     RETURN(result);
    1207                 :            : }
    1208                 :            : 
    1209                 :            : /* delete_kt() corresponds to add_kt(found), but there are only
    1210                 :            :    two cases: if the key is not found nothing is done, and if it is
    1211                 :            :    found the corresponding item is deleted with delete_leaf_item.
    1212                 :            : 
    1213                 :            :      Returns:
    1214                 :            :          0 : nothing to delete
    1215                 :            :          1 : deleted kt
    1216                 :            :          2 : deleted kt and it was the final one
    1217                 :            : */
    1218                 :            : 
    1219                 :            : int
    1220                 :     118459 : GlassTable::delete_kt()
    1221                 :            : {
    1222                 :            :     LOGCALL(DB, int, "GlassTable::delete_kt", NO_ARGS);
    1223                 :            :     Assert(writable);
    1224                 :            : 
    1225                 :     118459 :     seq_count = SEQ_START_POINT;
    1226                 :     118459 :     sequential = false;
    1227                 :            : 
    1228         [ +  + ]:     118459 :     if (!find(C))
    1229                 :      76448 :         return 0;
    1230                 :            : 
    1231         [ +  + ]:      42011 :     int result = LeafItem(C[0].get_p(), C[0].c).last_component() ? 2 : 1;
    1232                 :      42011 :     alter();
    1233                 :      42011 :     delete_leaf_item(true);
    1234                 :            : 
    1235                 :      42011 :     RETURN(result);
    1236                 :            : }
    1237                 :            : 
    1238                 :            : /* GlassTable::form_key(key) treats address kt as an item holder and fills in
    1239                 :            : the key part:
    1240                 :            : 
    1241                 :            :            (I) K key c (C tag)
    1242                 :            : 
    1243                 :            : The bracketed parts are left blank. The key is filled in with key_len bytes and
    1244                 :            : K set accordingly. c is set to 1.
    1245                 :            : */
    1246                 :            : 
    1247                 :    8877410 : void GlassTable::form_key(const string & key) const
    1248                 :            : {
    1249                 :            :     LOGCALL_VOID(DB, "GlassTable::form_key", key);
    1250                 :    8877410 :     kt.form_key(key);
    1251                 :    8877400 : }
    1252                 :            : 
    1253                 :            : /* GlassTable::add(key, tag) adds the key/tag item to the
    1254                 :            :    B-tree, replacing any existing item with the same key.
    1255                 :            : 
    1256                 :            :    For a long tag, we end up having to add m components, of the form
    1257                 :            : 
    1258                 :            :        key 1 m tag1
    1259                 :            :        key 2 m tag2
    1260                 :            :        ...
    1261                 :            :        key m m tagm
    1262                 :            : 
    1263                 :            :    and tag1+tag2+...+tagm are equal to tag. These in their turn may be replacing
    1264                 :            :    n components of the form
    1265                 :            : 
    1266                 :            :        key 1 n TAG1
    1267                 :            :        key 2 n TAG2
    1268                 :            :        ...
    1269                 :            :        key n n TAGn
    1270                 :            : 
    1271                 :            :    and n may be greater than, equal to, or less than m. These cases are dealt
    1272                 :            :    with in the code below. If m < n for example, we end up with a series of
    1273                 :            :    deletions.
    1274                 :            : */
    1275                 :            : 
    1276                 :            : void
    1277                 :    3256160 : GlassTable::add(const string &key, string tag, bool already_compressed)
    1278                 :            : {
    1279                 :            :     LOGCALL_VOID(DB, "GlassTable::add", key | tag | already_compressed);
    1280                 :            :     Assert(writable);
    1281                 :            : 
    1282         [ +  + ]:    3256160 :     if (handle < 0) {
    1283         [ +  + ]:        889 :         if (handle == -2) {
    1284                 :          2 :             GlassTable::throw_database_closed();
    1285                 :            :         }
    1286         [ +  - ]:        887 :         RootInfo root_info;
    1287         [ +  - ]:        887 :         root_info.init(block_size, compress_min);
    1288         [ +  - ]:        889 :         do_open_to_write(&root_info);
    1289                 :            :     }
    1290                 :            : 
    1291         [ +  + ]:    3256158 :     form_key(key);
    1292                 :            : 
    1293                 :    3256148 :     const char* tag_data = tag.data();
    1294                 :    3256148 :     size_t tag_size = tag.size();
    1295                 :            : 
    1296                 :    3256148 :     bool compressed = false;
    1297         [ +  + ]:    3256148 :     if (already_compressed) {
    1298                 :       2560 :         compressed = true;
    1299 [ +  + ][ +  + ]:    3253588 :     } else if (compress_min > 0 && tag_size > compress_min) {
    1300         [ +  - ]:     137708 :         const char * res = comp_stream.compress(tag_data, &tag_size);
    1301         [ +  + ]:     137708 :         if (res) {
    1302                 :      58044 :             compressed = true;
    1303                 :     137708 :             tag_data = res;
    1304                 :            :         }
    1305                 :            :     }
    1306                 :            : 
    1307                 :            :     // sort of matching kt.append_chunk(), but setting the chunk
    1308                 :    3256148 :     const size_t cd = kt.key().length() + K1 + I2 + X2;  // offset to the tag data
    1309                 :    3256148 :     const size_t L = max_item_size - cd; // largest amount of tag data for any chunk
    1310                 :    3256148 :     size_t first_L = L + X2;             // - amount for tag1 (we don't store X there)
    1311         [ +  - ]:    3256148 :     bool found = find(C);
    1312         [ +  + ]:    3256148 :     if (tag_size <= first_L) {
    1313                 :            :         // The whole tag clearly fits in one item, so no need to make this
    1314                 :            :         // complicated.
    1315                 :    3048355 :         first_L = tag_size;
    1316         [ +  + ]:     207793 :     } else if (!found) {
    1317                 :       6106 :         const uint8_t * p = C[0].get_p();
    1318         [ +  - ]:       6106 :         size_t n = TOTAL_FREE(p) % (max_item_size + D2);
    1319         [ +  + ]:       6106 :         if (n > D2 + cd) {
    1320                 :       6031 :             n -= (D2 + cd);
    1321                 :            :             // if n >= last then fully filling this block won't produce
    1322                 :            :             // an extra item, so we might as well do this even if
    1323                 :            :             // full_compaction isn't active.
    1324                 :            :             //
    1325                 :            :             // In the full_compaction case, it turns out we shouldn't always
    1326                 :            :             // try to fill every last byte.  Doing so can actually increase the
    1327                 :            :             // total space required (I believe this effect is due to longer
    1328                 :            :             // dividing keys being required in the index blocks).  Empirically,
    1329                 :            :             // n >= key.size() + K appears a good criterion for K ~= 34.  This
    1330                 :            :             // seems to save about 0.2% in total database size over always
    1331                 :            :             // splitting the tag.  It'll also give be slightly faster retrieval
    1332                 :            :             // as we can avoid reading an extra block occasionally.
    1333                 :       6031 :             size_t last = (tag_size - X2) % L;
    1334 [ +  + ][ -  + ]:       6031 :             if (n >= last || (full_compaction && n >= key.size() + 34)) {
         [ #  # ][ +  + ]
    1335                 :            :                 // first_L < max_item_size + D2 - D2 - cd
    1336                 :            :                 // Total size of first item = cd + first_L < max_item_size
    1337                 :       6106 :                 first_L = n + X2;
    1338                 :            :             }
    1339                 :            :         }
    1340                 :            :     }
    1341                 :            : 
    1342                 :            :     // There are m items to add.
    1343                 :    3256148 :     int m = (tag_size - first_L + L - 1) / L + 1;
    1344                 :            :     /* FIXME: sort out this error higher up and turn this into
    1345                 :            :      * an assert.
    1346                 :            :      */
    1347         [ -  + ]:    3256148 :     if (m >= BYTE_PAIR_RANGE)
    1348 [ #  # ][ #  # ]:          0 :         throw Xapian::UnimplementedError("Can't handle insanely large tags");
                 [ #  # ]
    1349                 :            : 
    1350                 :    3256148 :     size_t o = 0;                     // Offset into the tag
    1351                 :    3256148 :     size_t residue = tag_size;        // Bytes of the tag remaining to add in
    1352                 :    3256148 :     bool replacement = false;         // Has there been a replacement?
    1353                 :    3256148 :     bool components_to_del = false;   // Are there components to delete?
    1354                 :            :     int i;
    1355         [ +  + ]:    6941740 :     for (i = 1; i <= m; ++i) {
    1356 [ +  + ][ +  + ]:    3685592 :         size_t l = (i == m ? residue : (i == 1 ? first_L : L));
    1357         [ +  + ]:    3685592 :         size_t this_cd = (i == 1 ? cd - X2 : cd);
    1358                 :            :         Assert(this_cd + l <= block_size);
    1359                 :            :         Assert(o + l <= tag_size);
    1360         [ +  - ]:    3685592 :         kt.set_tag(this_cd, tag_data + o, l, compressed, i, m);
    1361                 :            : 
    1362                 :    3685592 :         o += l;
    1363                 :    3685592 :         residue -= l;
    1364                 :            : 
    1365 [ +  + ][ +  - ]:    3685592 :         if (i > 1) found = find(C);
    1366         [ +  - ]:    3685592 :         int result = add_kt(found);
    1367         [ +  + ]:    3685592 :         if (result) replacement = true;
    1368                 :    3685592 :         components_to_del = (result == 1);
    1369                 :            :     }
    1370                 :            :     AssertEq(o, tag_size);
    1371         [ +  + ]:    3256148 :     if (components_to_del) {
    1372                 :          3 :         i = m;
    1373         [ -  + ]:          3 :         do {
    1374         [ +  - ]:          3 :             kt.set_component_of(++i);
    1375         [ +  - ]:          3 :         } while (delete_kt() == 1);
    1376                 :            :     }
    1377         [ +  + ]:    3256148 :     if (!replacement) ++item_count;
    1378                 :    3256148 :     Btree_modified = true;
    1379         [ +  + ]:    3256148 :     if (cursor_created_since_last_modification) {
    1380                 :     574978 :         cursor_created_since_last_modification = false;
    1381                 :     574978 :         ++cursor_version;
    1382                 :            :     }
    1383                 :    3256148 : }
    1384                 :            : 
    1385                 :            : /* GlassTable::del(key) returns false if the key is not in the B-tree,
    1386                 :            :    otherwise deletes it and returns true.
    1387                 :            : 
    1388                 :            :    Again, this is parallel to GlassTable::add, but simpler in form.
    1389                 :            : */
    1390                 :            : 
    1391                 :            : bool
    1392                 :     158925 : GlassTable::del(const string &key)
    1393                 :            : {
    1394                 :            :     LOGCALL(DB, bool, "GlassTable::del", key);
    1395                 :            :     Assert(writable);
    1396                 :            : 
    1397         [ +  + ]:     158925 :     if (handle < 0) {
    1398         [ +  + ]:      40833 :         if (handle == -2) {
    1399                 :         10 :             GlassTable::throw_database_closed();
    1400                 :            :         }
    1401                 :      40823 :         RETURN(false);
    1402                 :            :     }
    1403                 :            : 
    1404                 :            :     // We can't delete a key which we is too long for us to store.
    1405         [ -  + ]:     118092 :     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) RETURN(false);
    1406                 :            : 
    1407         [ -  + ]:     118092 :     if (key.empty()) RETURN(false);
    1408                 :     118092 :     form_key(key);
    1409                 :            : 
    1410                 :     118092 :     int r = delete_kt();
    1411         [ +  + ]:     118092 :     if (r == 0) RETURN(false);
    1412                 :      41644 :     int i = 1;
    1413         [ +  + ]:      42008 :     while (r == 1) {
    1414                 :        364 :         kt.set_component_of(++i);
    1415                 :        364 :         r = delete_kt();
    1416                 :            :     }
    1417                 :            : 
    1418                 :      41644 :     item_count--;
    1419                 :      41644 :     Btree_modified = true;
    1420         [ +  + ]:      41644 :     if (cursor_created_since_last_modification) {
    1421                 :        277 :         cursor_created_since_last_modification = false;
    1422                 :        277 :         ++cursor_version;
    1423                 :            :     }
    1424                 :      41644 :     RETURN(true);
    1425                 :            : }
    1426                 :            : 
    1427                 :            : bool
    1428                 :     206364 : GlassTable::readahead_key(const string &key) const
    1429                 :            : {
    1430                 :            :     LOGCALL(DB, bool, "GlassTable::readahead_key", key);
    1431                 :            :     Assert(!key.empty());
    1432                 :            : 
    1433                 :            :     // Three cases:
    1434                 :            :     //
    1435                 :            :     // handle == -1:  Lazy table in a multi-file database which isn't yet open.
    1436                 :            :     //
    1437                 :            :     // handle == -2:  Table has been closed.  Since the readahead is just a
    1438                 :            :     // hint, we can safely ignore it for a closed table.
    1439                 :            :     //
    1440                 :            :     // handle <= -3:  Lazy table in a single-file database which isn't yet
    1441                 :            :     // open.
    1442         [ -  + ]:     206364 :     if (handle < 0)
    1443                 :          0 :         RETURN(false);
    1444                 :            : 
    1445                 :            :     // If the table only has one level, there are no branch blocks to preread.
    1446         [ +  + ]:     206364 :     if (level == 0)
    1447                 :       9869 :         RETURN(false);
    1448                 :            : 
    1449                 :     196495 :     form_key(key);
    1450                 :            : 
    1451                 :            :     // We'll only readahead the first level, since descending the B-tree would
    1452                 :            :     // require actual reads that would likely hurt performance more than help.
    1453                 :     196495 :     const uint8_t * p = C[level].get_p();
    1454                 :     196495 :     int c = find_in_branch(p, kt, C[level].c);
    1455         [ +  - ]:     196495 :     uint4 n = BItem(p, c).block_given_by();
    1456                 :            :     // Don't preread if it's the block we last preread or already in the
    1457                 :            :     // cursor.
    1458 [ +  + ][ +  + ]:     196495 :     if (n != last_readahead && n != C[level - 1].get_n()) {
                 [ +  + ]
    1459                 :       1134 :         last_readahead = n;
    1460         [ -  + ]:       1134 :         if (!io_readahead_block(handle, block_size, n, offset))
    1461                 :          0 :             RETURN(false);
    1462                 :            :     }
    1463                 :     206364 :     RETURN(true);
    1464                 :            : }
    1465                 :            : 
    1466                 :            : bool
    1467                 :    2413341 : GlassTable::get_exact_entry(const string &key, string & tag) const
    1468                 :            : {
    1469                 :            :     LOGCALL(DB, bool, "GlassTable::get_exact_entry", key | tag);
    1470                 :            :     Assert(!key.empty());
    1471                 :            : 
    1472         [ +  + ]:    2413341 :     if (handle < 0) {
    1473         [ +  + ]:      80894 :         if (handle == -2) {
    1474                 :         44 :             GlassTable::throw_database_closed();
    1475                 :            :         }
    1476                 :      80850 :         RETURN(false);
    1477                 :            :     }
    1478                 :            : 
    1479                 :            :     // An oversized key can't exist, so attempting to search for it should fail.
    1480         [ +  + ]:    2332447 :     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) RETURN(false);
    1481                 :            : 
    1482                 :    2332413 :     form_key(key);
    1483         [ +  + ]:    2332413 :     if (!find(C)) RETURN(false);
    1484                 :            : 
    1485                 :    1601366 :     (void)read_tag(C, &tag, false);
    1486                 :    1601366 :     RETURN(true);
    1487                 :            : }
    1488                 :            : 
    1489                 :            : bool
    1490                 :      11473 : GlassTable::key_exists(const string &key) const
    1491                 :            : {
    1492                 :            :     LOGCALL(DB, bool, "GlassTable::key_exists", key);
    1493                 :            :     Assert(!key.empty());
    1494                 :            : 
    1495                 :            :     // An oversized key can't exist, so attempting to search for it should fail.
    1496         [ -  + ]:      11473 :     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) RETURN(false);
    1497                 :            : 
    1498                 :      11473 :     form_key(key);
    1499                 :      11473 :     RETURN(find(C));
    1500                 :            : }
    1501                 :            : 
    1502                 :            : bool
    1503                 :    5380803 : GlassTable::read_tag(Glass::Cursor * C_, string *tag, bool keep_compressed) const
    1504                 :            : {
    1505                 :            :     LOGCALL(DB, bool, "GlassTable::read_tag", Literal("C_") | tag | keep_compressed);
    1506                 :            : 
    1507                 :    5380803 :     tag->resize(0);
    1508                 :            : 
    1509                 :    5380803 :     bool first = true;
    1510                 :    5380803 :     bool compressed = false;
    1511                 :    5380803 :     bool decompress = false;
    1512                 :            :     while (true) {
    1513         [ +  - ]:   10276418 :         LeafItem item(C_[0].get_p(), C_[0].c);
    1514         [ +  + ]:   10276418 :         if (first) {
    1515                 :    5380803 :             first = false;
    1516                 :    5380803 :             compressed = item.get_compressed();
    1517 [ +  + ][ +  + ]:    5380803 :             if (compressed && !keep_compressed) {
    1518         [ +  - ]:     234226 :                 comp_stream.decompress_start();
    1519                 :     234226 :                 decompress = true;
    1520                 :            :             }
    1521                 :            :         }
    1522                 :   10276418 :         bool last = item.last_component();
    1523         [ +  + ]:   10276418 :         if (decompress) {
    1524                 :            :             // Decompress each chunk as we read it so we don't need both the
    1525                 :            :             // full compressed and uncompressed tags in memory at once.
    1526         [ +  - ]:     284958 :             bool done = item.decompress_chunk(comp_stream, *tag);
    1527         [ -  + ]:     284958 :             if (done != last) {
    1528                 :            :                 throw Xapian::DatabaseCorruptError(done ?
    1529                 :            :                     "Too many chunks of compressed data" :
    1530 [ #  # ][ #  # ]:     284958 :                     "Too few chunks of compressed data");
         [ #  # ][ #  # ]
    1531                 :            :             }
    1532                 :            :         } else {
    1533         [ +  - ]:    9991460 :             item.append_chunk(tag);
    1534                 :            :         }
    1535         [ +  + ]:   10276418 :         if (last) break;
    1536 [ +  - ][ -  + ]:    4895615 :         if (!next(C_, 0)) {
    1537 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Unexpected end of table when reading continuation of tag");
                 [ #  # ]
    1538                 :            :         }
    1539                 :            :     }
    1540                 :            :     // At this point the cursor is on the last item - calling next will move
    1541                 :            :     // it to the next key (GlassCursor::read_tag() relies on this).
    1542                 :            : 
    1543 [ +  + ][ +  + ]:   10276418 :     RETURN(compressed && keep_compressed);
    1544                 :            : }
    1545                 :            : 
    1546                 :            : void
    1547                 :        243 : GlassTable::set_full_compaction(bool parity)
    1548                 :            : {
    1549                 :            :     LOGCALL_VOID(DB, "GlassTable::set_full_compaction", parity);
    1550                 :            :     Assert(writable);
    1551                 :            : 
    1552         [ -  + ]:        243 :     if (parity) seq_count = 0;
    1553                 :        243 :     full_compaction = parity;
    1554                 :        243 : }
    1555                 :            : 
    1556                 :     752577 : GlassCursor * GlassTable::cursor_get() const {
    1557                 :            :     LOGCALL(DB, GlassCursor *, "GlassTable::cursor_get", NO_ARGS);
    1558         [ +  + ]:     752577 :     if (handle < 0) {
    1559         [ +  + ]:         28 :         if (handle == -2) {
    1560                 :         24 :             GlassTable::throw_database_closed();
    1561                 :            :         }
    1562                 :          4 :         RETURN(NULL);
    1563                 :            :     }
    1564                 :            :     // FIXME Ick - casting away const is nasty
    1565         [ +  - ]:     752553 :     RETURN(new GlassCursor(const_cast<GlassTable *>(this)));
    1566                 :            : }
    1567                 :            : 
    1568                 :            : /************ B-tree opening and closing ************/
    1569                 :            : 
    1570                 :            : void
    1571                 :      16739 : GlassTable::basic_open(const RootInfo * root_info, glass_revision_number_t rev)
    1572                 :            : {
    1573                 :            :     LOGCALL_VOID(DB, "GlassTable::basic_open", root_info|rev);
    1574                 :      16739 :     revision_number = rev;
    1575                 :      16739 :     root =                 root_info->get_root();
    1576                 :      16739 :     level =                root_info->get_level();
    1577                 :      16739 :     item_count =           root_info->get_num_entries();
    1578                 :      16739 :     faked_root_block = root_info->get_root_is_fake();
    1579                 :      16739 :     sequential =           root_info->get_sequential();
    1580                 :      16739 :     const string & fl_serialised = root_info->get_free_list();
    1581         [ +  + ]:      16739 :     if (!fl_serialised.empty()) {
    1582         [ -  + ]:       9471 :         if (!free_list.unpack(fl_serialised))
    1583 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Bad freelist metadata");
                 [ #  # ]
    1584                 :            :     } else {
    1585                 :       7268 :         free_list.reset();
    1586                 :            :     }
    1587                 :            : 
    1588                 :      16739 :     compress_min = root_info->get_compress_min();
    1589                 :            : 
    1590                 :            :     /* kt holds constructed items as well as keys */
    1591                 :      16739 :     kt = LeafItem_wr(zeroed_new(block_size));
    1592                 :            : 
    1593                 :      16739 :     set_max_item_size(BLOCK_CAPACITY);
    1594                 :            : 
    1595         [ +  + ]:      35492 :     for (int j = 0; j <= level; ++j) {
    1596                 :      18753 :         C[j].init(block_size);
    1597                 :            :     }
    1598                 :            : 
    1599                 :      16739 :     read_root();
    1600                 :            : 
    1601         [ +  + ]:      16739 :     if (cursor_created_since_last_modification) {
    1602                 :          9 :         cursor_created_since_last_modification = false;
    1603                 :          9 :         ++cursor_version;
    1604                 :            :     }
    1605                 :      16739 : }
    1606                 :            : 
    1607                 :            : void
    1608                 :      73914 : GlassTable::read_root()
    1609                 :            : {
    1610                 :            :     LOGCALL_VOID(DB, "GlassTable::read_root", NO_ARGS);
    1611         [ +  + ]:      73914 :     if (faked_root_block) {
    1612                 :            :         /* root block for an unmodified database. */
    1613                 :      10198 :         uint8_t * p = C[0].init(block_size);
    1614                 :            :         Assert(p);
    1615                 :            : 
    1616                 :            :         /* clear block - shouldn't be necessary, but is a bit nicer,
    1617                 :            :          * and means that the same operations should always produce
    1618                 :            :          * the same database. */
    1619                 :      10198 :         memset(p, 0, block_size);
    1620                 :            : 
    1621                 :      10198 :         int o = block_size - I2 - K1;
    1622         [ +  - ]:      10198 :         LeafItem_wr(p + o).fake_root_item();
    1623                 :            : 
    1624                 :      10198 :         LeafItem_wr::setD(p, DIR_START, o);         // its directory entry
    1625                 :      10198 :         SET_DIR_END(p, DIR_START + D2);// the directory size
    1626                 :            : 
    1627                 :      10198 :         o -= (DIR_START + D2);
    1628                 :      10198 :         SET_MAX_FREE(p, o);
    1629                 :      10198 :         SET_TOTAL_FREE(p, o);
    1630                 :      10198 :         SET_LEVEL(p, 0);
    1631                 :            : 
    1632         [ +  + ]:      10198 :         if (!writable) {
    1633                 :            :             /* reading - revision number doesn't matter as long as
    1634                 :            :              * it's not greater than the current one. */
    1635                 :       3180 :             SET_REVISION(p, 0);
    1636                 :       3180 :             C[0].set_n(0);
    1637                 :            :         } else {
    1638                 :            :             /* writing - */
    1639                 :       7018 :             SET_REVISION(p, revision_number + 1);
    1640                 :       7018 :             C[0].set_n(free_list.get_block(this, block_size));
    1641                 :      10198 :             C[0].rewrite = true;
    1642                 :            :         }
    1643                 :            :     } else {
    1644                 :            :         /* using a root block stored on disk */
    1645                 :      63716 :         block_to_cursor(C, level, root);
    1646                 :            : 
    1647         [ -  + ]:      63716 :         if (REVISION(C[level].get_p()) > revision_number) set_overwritten();
    1648                 :            :         /* although this is unlikely */
    1649                 :            :     }
    1650                 :      73914 : }
    1651                 :            : 
    1652                 :            : void
    1653                 :       6175 : GlassTable::do_open_to_write(const RootInfo * root_info,
    1654                 :            :                              glass_revision_number_t rev)
    1655                 :            : {
    1656                 :            :     LOGCALL_VOID(DB, "GlassTable::do_open_to_write", root_info|rev);
    1657         [ -  + ]:       6175 :     if (handle == -2) {
    1658                 :          0 :         GlassTable::throw_database_closed();
    1659                 :            :     }
    1660         [ +  + ]:       6175 :     if (handle <= -2) {
    1661                 :            :         // Single file database.
    1662                 :        148 :         handle = -3 - handle;
    1663                 :            :     } else {
    1664         [ +  - ]:       6027 :         handle = io_open_block_wr(name + GLASS_TABLE_EXTENSION, (rev == 0));
    1665         [ +  + ]:       6027 :         if (handle < 0) {
    1666                 :            :             // lazy doesn't make a lot of sense when we're creating a DB (which
    1667                 :            :             // is the case when rev==0), but ENOENT with O_CREAT means a parent
    1668                 :            :             // directory doesn't exist.
    1669 [ +  - ][ +  - ]:        104 :             if (lazy && rev && errno == ENOENT) {
                 [ +  - ]
    1670                 :        104 :                 revision_number = rev;
    1671                 :       6279 :                 return;
    1672                 :            :             }
    1673 [ #  # ][ #  # ]:          0 :             string message((rev == 0) ? "Couldn't create " : "Couldn't open ");
    1674         [ #  # ]:          0 :             message += name;
    1675         [ #  # ]:          0 :             message += GLASS_TABLE_EXTENSION" read/write";
    1676         [ #  # ]:        104 :             throw Xapian::DatabaseOpeningError(message, errno);
    1677                 :            :         }
    1678                 :            :     }
    1679                 :            : 
    1680                 :       6071 :     writable = true;
    1681                 :       6071 :     basic_open(root_info, rev);
    1682                 :            : 
    1683                 :       6071 :     split_p = new uint8_t[block_size];
    1684                 :            : 
    1685                 :       6071 :     buffer = zeroed_new(block_size);
    1686                 :            : 
    1687                 :       6071 :     changed_n = 0;
    1688                 :       6071 :     changed_c = DIR_START;
    1689                 :       6071 :     seq_count = SEQ_START_POINT;
    1690                 :            : }
    1691                 :            : 
    1692                 :      22152 : GlassTable::GlassTable(const char * tablename_, const string & path_,
    1693                 :            :                        bool readonly_, bool lazy_)
    1694                 :            :         : tablename(tablename_),
    1695                 :            :           revision_number(0),
    1696                 :            :           item_count(0),
    1697                 :            :           block_size(0),
    1698                 :            :           faked_root_block(true),
    1699                 :            :           sequential(true),
    1700                 :            :           handle(-1),
    1701                 :            :           level(0),
    1702                 :            :           root(0),
    1703                 :            :           kt(0),
    1704                 :            :           buffer(0),
    1705                 :            :           free_list(),
    1706                 :            :           name(path_),
    1707                 :            :           seq_count(0),
    1708                 :            :           changed_n(0),
    1709                 :            :           changed_c(0),
    1710                 :            :           max_item_size(0),
    1711                 :            :           Btree_modified(false),
    1712                 :            :           full_compaction(false),
    1713                 :      22152 :           writable(!readonly_),
    1714                 :            :           cursor_created_since_last_modification(false),
    1715                 :            :           cursor_version(0),
    1716                 :            :           changes_obj(NULL),
    1717                 :            :           split_p(0),
    1718                 :            :           compress_min(0),
    1719                 :            :           comp_stream(Z_DEFAULT_STRATEGY),
    1720                 :            :           lazy(lazy_),
    1721                 :            :           last_readahead(BLK_UNUSED),
    1722 [ +  - ][ +  + ]:     243672 :           offset(0)
    1723                 :            : {
    1724                 :            :     LOGCALL_CTOR(DB, "GlassTable", tablename_ | path_ | readonly_ | lazy_);
    1725                 :      22152 : }
    1726                 :            : 
    1727                 :       1996 : GlassTable::GlassTable(const char * tablename_, int fd, off_t offset_,
    1728                 :            :                        bool readonly_, bool lazy_)
    1729                 :            :         : tablename(tablename_),
    1730                 :            :           revision_number(0),
    1731                 :            :           item_count(0),
    1732                 :            :           block_size(0),
    1733                 :            :           faked_root_block(true),
    1734                 :            :           sequential(true),
    1735                 :       1996 :           handle(-3 - fd),
    1736                 :            :           level(0),
    1737                 :            :           root(0),
    1738                 :            :           kt(0),
    1739                 :            :           buffer(0),
    1740                 :            :           free_list(),
    1741                 :            :           name(),
    1742                 :            :           seq_count(0),
    1743                 :            :           changed_n(0),
    1744                 :            :           changed_c(0),
    1745                 :            :           max_item_size(0),
    1746                 :            :           Btree_modified(false),
    1747                 :            :           full_compaction(false),
    1748                 :       1996 :           writable(!readonly_),
    1749                 :            :           cursor_created_since_last_modification(false),
    1750                 :            :           cursor_version(0),
    1751                 :            :           changes_obj(NULL),
    1752                 :            :           split_p(0),
    1753                 :            :           compress_min(0),
    1754                 :            :           comp_stream(Z_DEFAULT_STRATEGY),
    1755                 :            :           lazy(lazy_),
    1756                 :            :           last_readahead(BLK_UNUSED),
    1757 [ +  - ][ +  + ]:      21956 :           offset(offset_)
    1758                 :            : {
    1759                 :            :     LOGCALL_CTOR(DB, "GlassTable", tablename_ | fd | offset_ | readonly_ | lazy_);
    1760                 :       1996 : }
    1761                 :            : 
    1762                 :            : bool
    1763                 :       1278 : GlassTable::exists() const {
    1764                 :            :     LOGCALL(DB, bool, "GlassTable::exists", NO_ARGS);
    1765                 :            :     // We know a single-file database exists, since we have an fd open on it!
    1766 [ +  - ][ +  - ]:       1278 :     return single_file() || file_exists(name + GLASS_TABLE_EXTENSION);
         [ +  + ][ +  - ]
                 [ #  # ]
    1767                 :            : }
    1768                 :            : 
    1769                 :            : void
    1770                 :       5809 : GlassTable::create_and_open(int flags_, const RootInfo & root_info)
    1771                 :            : {
    1772                 :            :     LOGCALL_VOID(DB, "GlassTable::create_and_open", flags_|root_info);
    1773         [ -  + ]:       5809 :     if (handle == -2) {
    1774                 :          0 :         GlassTable::throw_database_closed();
    1775                 :            :     }
    1776                 :            :     Assert(writable);
    1777                 :       5809 :     close();
    1778                 :            : 
    1779                 :       5809 :     unsigned int block_size_ = root_info.get_blocksize();
    1780                 :            :     Assert(block_size_ >= GLASS_MIN_BLOCKSIZE);
    1781                 :            :     Assert(block_size_ <= BYTE_PAIR_RANGE);
    1782                 :            :     // Must be a power of two.
    1783                 :            :     Assert((block_size_ & (block_size_ - 1)) == 0);
    1784                 :            : 
    1785                 :       5809 :     flags = flags_;
    1786                 :       5809 :     block_size = block_size_;
    1787                 :            : 
    1788         [ +  + ]:       5809 :     if (lazy) {
    1789                 :       3842 :         close();
    1790         [ +  - ]:       3842 :         (void)io_unlink(name + GLASS_TABLE_EXTENSION);
    1791                 :       3842 :         compress_min = root_info.get_compress_min();
    1792                 :            :     } else {
    1793                 :            :         // FIXME: it would be good to arrange that this works such that there's
    1794                 :            :         // always a valid table in place if you run create_and_open() on an
    1795                 :            :         // existing table.
    1796                 :            : 
    1797                 :       1967 :         do_open_to_write(&root_info);
    1798                 :            :     }
    1799                 :       5809 : }
    1800                 :            : 
    1801 [ +  - ][ +  + ]:     289560 : GlassTable::~GlassTable() {
    1802                 :            :     LOGCALL_DTOR(DB, "GlassTable");
    1803                 :      24130 :     GlassTable::close();
    1804                 :      24130 : }
    1805                 :            : 
    1806                 :      55972 : void GlassTable::close(bool permanent) {
    1807                 :            :     LOGCALL_VOID(DB, "GlassTable::close", permanent);
    1808                 :            : 
    1809         [ +  + ]:      55972 :     if (handle >= 0) {
    1810         [ +  + ]:      16733 :         if (single_file()) {
    1811                 :       1996 :             handle = -3 - handle;
    1812                 :            :         } else {
    1813                 :            :             // If an error occurs here, we just ignore it, since we're just
    1814                 :            :             // trying to free everything.
    1815                 :      14737 :             (void)::close(handle);
    1816                 :      16733 :             handle = -1;
    1817                 :            :         }
    1818                 :            :     }
    1819                 :            : 
    1820         [ +  + ]:      55972 :     if (permanent) {
    1821                 :       3780 :         handle = -2;
    1822                 :            :         // Don't delete the resources in the table, since they may
    1823                 :            :         // still be used to look up cached content.
    1824                 :       3780 :         return;
    1825                 :            :     }
    1826         [ +  + ]:     106733 :     for (int j = level; j >= 0; --j) {
    1827                 :      54541 :         C[j].destroy();
    1828                 :            :     }
    1829         [ +  + ]:      52192 :     delete [] split_p;
    1830                 :      52192 :     split_p = 0;
    1831                 :            : 
    1832         [ +  + ]:      52192 :     delete [] kt.get_address();
    1833                 :      52192 :     kt = LeafItem_wr(0);
    1834         [ +  + ]:      52192 :     delete [] buffer;
    1835                 :      52192 :     buffer = 0;
    1836                 :            : }
    1837                 :            : 
    1838                 :            : void
    1839                 :      54787 : GlassTable::flush_db()
    1840                 :            : {
    1841                 :            :     LOGCALL_VOID(DB, "GlassTable::flush_db", NO_ARGS);
    1842                 :            :     Assert(writable);
    1843         [ +  + ]:      54787 :     if (handle < 0) {
    1844         [ +  + ]:       9568 :         if (handle == -2) {
    1845                 :          2 :             GlassTable::throw_database_closed();
    1846                 :            :         }
    1847                 :       9566 :         return;
    1848                 :            :     }
    1849                 :            : 
    1850         [ +  + ]:     105782 :     for (int j = level; j >= 0; --j) {
    1851         [ +  + ]:      60563 :         if (C[j].rewrite) {
    1852                 :      35930 :             write_block(C[j].get_n(), C[j].get_p());
    1853                 :            :         }
    1854                 :            :     }
    1855                 :            : 
    1856                 :      45219 :     faked_root_block = false;
    1857                 :            : }
    1858                 :            : 
    1859                 :            : void
    1860                 :      54785 : GlassTable::commit(glass_revision_number_t revision, RootInfo * root_info)
    1861                 :            : {
    1862                 :            :     LOGCALL_VOID(DB, "GlassTable::commit", revision|root_info);
    1863                 :            :     Assert(writable);
    1864                 :            : 
    1865         [ -  + ]:      54785 :     if (revision <= revision_number) {
    1866 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseError("New revision too low");
                 [ #  # ]
    1867                 :            :     }
    1868                 :            : 
    1869         [ +  + ]:      54785 :     if (handle < 0) {
    1870         [ -  + ]:       9566 :         if (handle == -2) {
    1871                 :          0 :             GlassTable::throw_database_closed();
    1872                 :            :         }
    1873                 :       9566 :         revision_number = revision;
    1874                 :       9566 :         root_info->set_blocksize(block_size);
    1875                 :       9566 :         root_info->set_level(0);
    1876                 :       9566 :         root_info->set_num_entries(0);
    1877                 :       9566 :         root_info->set_root_is_fake(true);
    1878                 :       9566 :         root_info->set_sequential(true);
    1879                 :       9566 :         root_info->set_root(0);
    1880                 :      54785 :         return;
    1881                 :            :     }
    1882                 :            : 
    1883                 :            :     try {
    1884         [ +  - ]:      45219 :         root = C[level].get_n();
    1885                 :            : 
    1886                 :      45219 :         root_info->set_blocksize(block_size);
    1887                 :      45219 :         root_info->set_level(level);
    1888                 :      45219 :         root_info->set_num_entries(item_count);
    1889                 :      45219 :         root_info->set_root_is_fake(faked_root_block);
    1890                 :      45219 :         root_info->set_sequential(sequential);
    1891                 :      45219 :         root_info->set_root(root);
    1892                 :            : 
    1893                 :      45219 :         Btree_modified = false;
    1894                 :            : 
    1895         [ +  + ]:     497409 :         for (int i = 0; i < BTREE_CURSOR_LEVELS; ++i) {
    1896         [ +  - ]:     452190 :             C[i].init(block_size);
    1897                 :            :         }
    1898                 :            : 
    1899                 :      45219 :         free_list.set_revision(revision);
    1900         [ +  - ]:      45219 :         free_list.commit(this, block_size);
    1901                 :            : 
    1902                 :            :         // Save the freelist details into the root_info.
    1903         [ +  - ]:      45219 :         string serialised;
    1904         [ +  - ]:      45219 :         free_list.pack(serialised);
    1905         [ +  - ]:      45219 :         root_info->set_free_list(serialised);
    1906                 :            : 
    1907                 :      45219 :         revision_number = revision;
    1908                 :            : 
    1909         [ +  - ]:      45219 :         read_root();
    1910                 :            : 
    1911                 :      45219 :         changed_n = 0;
    1912                 :      45219 :         changed_c = DIR_START;
    1913                 :      45219 :         seq_count = SEQ_START_POINT;
    1914                 :          0 :     } catch (...) {
    1915         [ #  # ]:          0 :         GlassTable::close();
    1916                 :          0 :         throw;
    1917                 :            :     }
    1918                 :            : }
    1919                 :            : 
    1920                 :            : void
    1921                 :       1520 : GlassTable::cancel(const RootInfo & root_info, glass_revision_number_t rev)
    1922                 :            : {
    1923                 :            :     LOGCALL_VOID(DB, "GlassTable::cancel", root_info|rev);
    1924                 :            :     Assert(writable);
    1925                 :            : 
    1926         [ +  + ]:       1520 :     if (handle < 0) {
    1927         [ +  + ]:        232 :         if (handle == -2) {
    1928                 :         14 :             GlassTable::throw_database_closed();
    1929                 :            :         }
    1930                 :       1506 :         return;
    1931                 :            :     }
    1932                 :            : 
    1933                 :            :     // This causes problems: if (!Btree_modified) return;
    1934                 :            : 
    1935         [ -  + ]:       1288 :     if (flags & Xapian::DB_DANGEROUS)
    1936 [ #  # ][ #  # ]:          0 :         throw Xapian::InvalidOperationError("cancel() not supported under Xapian::DB_DANGEROUS");
                 [ #  # ]
    1937                 :            : 
    1938                 :       1288 :     revision_number = rev;
    1939                 :       1288 :     block_size =       root_info.get_blocksize();
    1940                 :       1288 :     root =             root_info.get_root();
    1941                 :       1288 :     level =            root_info.get_level();
    1942                 :       1288 :     item_count =       root_info.get_num_entries();
    1943                 :       1288 :     faked_root_block = root_info.get_root_is_fake();
    1944                 :       1288 :     sequential =       root_info.get_sequential();
    1945                 :       1288 :     const string & fl_serialised = root_info.get_free_list();
    1946         [ +  + ]:       1288 :     if (!fl_serialised.empty()) {
    1947         [ -  + ]:         66 :         if (!free_list.unpack(fl_serialised))
    1948 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Bad freelist metadata");
                 [ #  # ]
    1949                 :            :     } else {
    1950                 :       1222 :         free_list.reset();
    1951                 :            :     }
    1952                 :            : 
    1953                 :       1288 :     Btree_modified = false;
    1954                 :            : 
    1955         [ +  + ]:       2595 :     for (int j = 0; j <= level; ++j) {
    1956                 :       1307 :         C[j].init(block_size);
    1957                 :       1307 :         C[j].rewrite = false;
    1958                 :            :     }
    1959                 :       1288 :     read_root();
    1960                 :            : 
    1961                 :       1288 :     changed_n = 0;
    1962                 :       1288 :     changed_c = DIR_START;
    1963                 :       1288 :     seq_count = SEQ_START_POINT;
    1964                 :            : 
    1965         [ -  + ]:       1288 :     if (cursor_created_since_last_modification) {
    1966                 :          0 :         cursor_created_since_last_modification = false;
    1967                 :          0 :         ++cursor_version;
    1968                 :            :     }
    1969                 :            : }
    1970                 :            : 
    1971                 :            : /************ B-tree reading ************/
    1972                 :            : 
    1973                 :            : void
    1974                 :      15090 : GlassTable::do_open_to_read(const RootInfo * root_info,
    1975                 :            :                             glass_revision_number_t rev)
    1976                 :            : {
    1977                 :            :     LOGCALL(DB, bool, "GlassTable::do_open_to_read", root_info|rev);
    1978         [ -  + ]:      15090 :     if (handle == -2) {
    1979                 :          0 :         GlassTable::throw_database_closed();
    1980                 :            :     }
    1981         [ +  + ]:      15090 :     if (single_file()) {
    1982                 :       1848 :         handle = -3 - handle;
    1983                 :            :     } else {
    1984         [ +  - ]:      13242 :         handle = io_open_block_rd(name + GLASS_TABLE_EXTENSION);
    1985         [ +  + ]:      13242 :         if (handle < 0) {
    1986         [ +  - ]:       4422 :             if (lazy) {
    1987                 :            :                 // This table is optional when reading!
    1988                 :       4422 :                 revision_number = rev;
    1989                 :      19512 :                 return;
    1990                 :            :             }
    1991         [ #  # ]:          0 :             string message("Couldn't open ");
    1992         [ #  # ]:          0 :             message += name;
    1993         [ #  # ]:          0 :             message += GLASS_TABLE_EXTENSION" to read";
    1994         [ #  # ]:       4422 :             throw Xapian::DatabaseOpeningError(message, errno);
    1995                 :            :         }
    1996                 :            :     }
    1997                 :            : 
    1998                 :      10668 :     basic_open(root_info, rev);
    1999                 :            : 
    2000                 :      10668 :     read_root();
    2001                 :            : }
    2002                 :            : 
    2003                 :            : void
    2004                 :      18411 : GlassTable::open(int flags_, const RootInfo & root_info,
    2005                 :            :                  glass_revision_number_t rev)
    2006                 :            : {
    2007                 :            :     LOGCALL_VOID(DB, "GlassTable::open", flags_|root_info|rev);
    2008                 :      18411 :     close();
    2009                 :            : 
    2010                 :      18411 :     flags = flags_;
    2011                 :      18411 :     block_size = root_info.get_blocksize();
    2012                 :      18411 :     root = root_info.get_root();
    2013                 :            : 
    2014         [ +  + ]:      18411 :     if (!writable) {
    2015                 :      15090 :         do_open_to_read(&root_info, rev);
    2016                 :      15090 :         return;
    2017                 :            :     }
    2018                 :            : 
    2019                 :       3321 :     do_open_to_write(&root_info, rev);
    2020                 :            : }
    2021                 :            : 
    2022                 :            : bool
    2023                 :      10040 : GlassTable::prev_for_sequential(Glass::Cursor * C_, int /*dummy*/) const
    2024                 :            : {
    2025                 :            :     LOGCALL(DB, bool, "GlassTable::prev_for_sequential", Literal("C_") | Literal("/*dummy*/"));
    2026                 :      10040 :     int c = C_[0].c;
    2027                 :            :     AssertRel(DIR_START,<=,c);
    2028                 :            :     AssertRel(c,<,DIR_END(C_[0].get_p()));
    2029         [ -  + ]:      10040 :     if (c == DIR_START) {
    2030                 :          0 :         uint4 n = C_[0].get_n();
    2031                 :            :         const uint8_t * p;
    2032                 :            :         while (true) {
    2033         [ #  # ]:          0 :             if (n == 0) RETURN(false);
    2034                 :          0 :             n--;
    2035         [ #  # ]:          0 :             if (n == C[0].get_n()) {
    2036                 :            :                 // Block is a leaf block in the built-in cursor (potentially in
    2037                 :            :                 // modified form if the table is writable).
    2038                 :          0 :                 p = C_[0].clone(C[0]);
    2039                 :            :             } else {
    2040         [ #  # ]:          0 :                 if (writable) {
    2041                 :            :                     // Blocks in the built-in cursor may not have been written
    2042                 :            :                     // to disk yet, so we have to check that the block number
    2043                 :            :                     // isn't in the built-in cursor or we'll read an
    2044                 :            :                     // uninitialised block (for which GET_LEVEL(p) will
    2045                 :            :                     // probably return 0).
    2046                 :            :                     int j;
    2047         [ #  # ]:          0 :                     for (j = 1; j <= level; ++j) {
    2048         [ #  # ]:          0 :                         if (n == C[j].get_n()) break;
    2049                 :            :                     }
    2050         [ #  # ]:          0 :                     if (j <= level) continue;
    2051                 :            :                 }
    2052                 :            : 
    2053                 :            :                 // Block isn't in the built-in cursor, so the form on disk
    2054                 :            :                 // is valid, so read it to check if it's the next level 0
    2055                 :            :                 // block.
    2056                 :          0 :                 uint8_t * q = C_[0].init(block_size);
    2057                 :          0 :                 read_block(n, q);
    2058                 :          0 :                 p = q;
    2059                 :          0 :                 C_[0].set_n(n);
    2060                 :            :             }
    2061         [ #  # ]:          0 :             if (REVISION(p) > revision_number + writable) {
    2062                 :          0 :                 set_overwritten();
    2063                 :            :                 RETURN(false);
    2064                 :            :             }
    2065         [ #  # ]:          0 :             if (GET_LEVEL(p) == 0) break;
    2066                 :            :         }
    2067                 :          0 :         c = DIR_END(p);
    2068                 :          0 :         AssertRel(DIR_START,<,c);
    2069                 :            :     }
    2070                 :      10040 :     c -= D2;
    2071                 :      10040 :     C_[0].c = c;
    2072                 :      10040 :     RETURN(true);
    2073                 :            : }
    2074                 :            : 
    2075                 :            : bool
    2076                 :    1135123 : GlassTable::next_for_sequential(Glass::Cursor * C_, int /*dummy*/) const
    2077                 :            : {
    2078                 :            :     LOGCALL(DB, bool, "GlassTable::next_for_sequential", Literal("C_") | Literal("/*dummy*/"));
    2079                 :    1135123 :     const uint8_t * p = C_[0].get_p();
    2080                 :            :     Assert(p);
    2081                 :    1135123 :     int c = C_[0].c;
    2082                 :            :     AssertRel(c,<,DIR_END(p));
    2083                 :    1135123 :     c += D2;
    2084                 :            :     Assert((unsigned)c < block_size);
    2085         [ +  + ]:    1135123 :     if (c == DIR_END(p)) {
    2086                 :     192196 :         uint4 n = C_[0].get_n();
    2087                 :            :         while (true) {
    2088                 :     192254 :             n++;
    2089         [ +  + ]:     192254 :             if (n >= free_list.get_first_unused_block()) RETURN(false);
    2090         [ +  + ]:       2012 :             if (writable) {
    2091         [ +  + ]:       1549 :                 if (n == C[0].get_n()) {
    2092                 :            :                     // Block is a leaf block in the built-in cursor
    2093                 :            :                     // (potentially in modified form).
    2094                 :          2 :                     p = C_[0].clone(C[0]);
    2095                 :            :                 } else {
    2096                 :            :                     // Blocks in the built-in cursor may not have been written
    2097                 :            :                     // to disk yet, so we have to check that the block number
    2098                 :            :                     // isn't in the built-in cursor or we'll read an
    2099                 :            :                     // uninitialised block (for which GET_LEVEL(p) will
    2100                 :            :                     // probably return 0).
    2101                 :            :                     int j;
    2102         [ +  + ]:       3059 :                     for (j = 1; j <= level; ++j) {
    2103         [ +  + ]:       1547 :                         if (n == C[j].get_n()) break;
    2104                 :            :                     }
    2105         [ +  + ]:       1547 :                     if (j <= level) continue;
    2106                 :            : 
    2107                 :            :                     // Block isn't in the built-in cursor, so the form on disk
    2108                 :            :                     // is valid, so read it to check if it's the next level 0
    2109                 :            :                     // block.
    2110                 :       1512 :                     uint8_t * q = C_[0].init(block_size);
    2111                 :       1512 :                     read_block(n, q);
    2112                 :       1514 :                     p = q;
    2113                 :            :                 }
    2114                 :            :             } else {
    2115                 :        463 :                 uint8_t * q = C_[0].init(block_size);
    2116                 :        463 :                 read_block(n, q);
    2117                 :        463 :                 p = q;
    2118                 :            :             }
    2119         [ -  + ]:       1977 :             if (REVISION(p) > revision_number + writable) {
    2120                 :          0 :                 set_overwritten();
    2121                 :            :                 RETURN(false);
    2122                 :            :             }
    2123         [ +  + ]:       1977 :             if (GET_LEVEL(p) == 0) break;
    2124                 :            :         }
    2125                 :       1954 :         c = DIR_START;
    2126                 :       2012 :         C_[0].set_n(n);
    2127                 :            :     }
    2128                 :     944881 :     C_[0].c = c;
    2129                 :     944881 :     RETURN(true);
    2130                 :            : }
    2131                 :            : 
    2132                 :            : bool
    2133                 :    5065808 : GlassTable::prev_default(Glass::Cursor * C_, int j) const
    2134                 :            : {
    2135                 :            :     LOGCALL(DB, bool, "GlassTable::prev_default", Literal("C_") | j);
    2136                 :    5065808 :     const uint8_t * p = C_[j].get_p();
    2137                 :    5065808 :     int c = C_[j].c;
    2138                 :            :     AssertRel(DIR_START,<=,c);
    2139                 :            :     AssertRel(c,<,DIR_END(p));
    2140                 :            :     AssertRel((unsigned)DIR_END(p),<=,block_size);
    2141         [ +  + ]:    5065808 :     if (c == DIR_START) {
    2142         [ -  + ]:     982238 :         if (j == level) RETURN(false);
    2143         [ -  + ]:     982238 :         if (!prev_default(C_, j + 1)) RETURN(false);
    2144                 :     982238 :         p = C_[j].get_p();
    2145                 :     982238 :         c = DIR_END(p);
    2146                 :            :         AssertRel(DIR_START,<,c);
    2147                 :            :     }
    2148                 :    5065808 :     c -= D2;
    2149                 :    5065808 :     C_[j].c = c;
    2150         [ +  + ]:    5065808 :     if (j > 0) {
    2151 [ +  - ][ +  - ]:     982238 :         block_to_cursor(C_, j - 1, BItem(p, c).block_given_by());
    2152                 :            :     }
    2153                 :    5065808 :     RETURN(true);
    2154                 :            : }
    2155                 :            : 
    2156                 :            : bool
    2157                 :    9634036 : GlassTable::next_default(Glass::Cursor * C_, int j) const
    2158                 :            : {
    2159                 :            :     LOGCALL(DB, bool, "GlassTable::next_default", Literal("C_") | j);
    2160                 :    9634036 :     const uint8_t * p = C_[j].get_p();
    2161                 :    9634036 :     int c = C_[j].c;
    2162                 :            :     AssertRel(c,<,DIR_END(p));
    2163                 :            :     AssertRel((unsigned)DIR_END(p),<=,block_size);
    2164                 :    9634036 :     c += D2;
    2165                 :            :     if (j > 0) {
    2166                 :            :         AssertRel(DIR_START,<,c);
    2167                 :            :     } else {
    2168                 :            :         AssertRel(DIR_START,<=,c);
    2169                 :            :     }
    2170                 :            :     // Sometimes c can be DIR_END(p) + 2 here it appears...
    2171         [ +  + ]:    9634036 :     if (c >= DIR_END(p)) {
    2172         [ +  + ]:    1988279 :         if (j == level) RETURN(false);
    2173         [ +  + ]:    1806217 :         if (!next_default(C_, j + 1)) RETURN(false);
    2174                 :    1658252 :         p = C_[j].get_p();
    2175                 :    1658252 :         c = DIR_START;
    2176                 :            :     }
    2177                 :    9304009 :     C_[j].c = c;
    2178         [ +  + ]:    9304009 :     if (j > 0) {
    2179 [ +  - ][ +  - ]:    1658252 :         block_to_cursor(C_, j - 1, BItem(p, c).block_given_by());
    2180                 :            : #ifdef BTREE_DEBUG_FULL
    2181                 :            :         printf("Block in GlassTable:next_default");
    2182                 :            :         report_block_full(j - 1, C_[j - 1].get_n(), C_[j - 1].get_p());
    2183                 :            : #endif /* BTREE_DEBUG_FULL */
    2184                 :            :     }
    2185                 :    9634036 :     RETURN(true);
    2186                 :            : }
    2187                 :            : 
    2188                 :            : void
    2189                 :        108 : GlassTable::throw_database_closed()
    2190                 :            : {
    2191 [ +  - ][ +  - ]:        108 :     throw Xapian::DatabaseClosedError("Database has been closed");
                 [ +  - ]
    2192                 :            : }
    2193                 :            : 
    2194                 :            : #ifdef DISABLE_GPL_LIBXAPIAN
    2195                 :            : # error GPL source we cannot relicense included in libxapian
    2196                 :            : #endif

Generated by: LCOV version 1.11