LCOV - code coverage report
Current view: top level - backends/glass - glass_cursor.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 7028d852e609 Lines: 116 130 89.2 %
Date: 2019-02-17 14:59:59 Functions: 11 11 100.0 %
Branches: 79 110 71.8 %

           Branch data     Line data    Source code
       1                 :            : /** @file glass_cursor.cc
       2                 :            :  * @brief Btree cursor implementation
       3                 :            :  */
       4                 :            : /* Copyright 1999,2000,2001 BrightStation PLC
       5                 :            :  * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010,2012,2013,2015,2016 Olly Betts
       6                 :            :  *
       7                 :            :  * This program is free software; you can redistribute it and/or
       8                 :            :  * modify it under the terms of the GNU General Public License as
       9                 :            :  * published by the Free Software Foundation; either version 2 of the
      10                 :            :  * License, or (at your option) any later version.
      11                 :            :  *
      12                 :            :  * This program is distributed in the hope that it will be useful,
      13                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            :  * GNU General Public License for more details.
      16                 :            :  *
      17                 :            :  * You should have received a copy of the GNU General Public License
      18                 :            :  * along with this program; if not, write to the Free Software
      19                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
      20                 :            :  * USA
      21                 :            :  */
      22                 :            : 
      23                 :            : #include <config.h>
      24                 :            : 
      25                 :            : #include "glass_cursor.h"
      26                 :            : 
      27                 :            : #include <cerrno>
      28                 :            : 
      29                 :            : #include <xapian/error.h>
      30                 :            : 
      31                 :            : #include "glass_table.h"
      32                 :            : #include "debuglog.h"
      33                 :            : #include "omassert.h"
      34                 :            : 
      35                 :            : using namespace Glass;
      36                 :            : 
      37                 :            : #ifdef XAPIAN_DEBUG_LOG
      38                 :            : static string
      39                 :            : hex_display_encode(const string & input)
      40                 :            : {
      41                 :            :     const char * table = "0123456789abcdef";
      42                 :            :     string result;
      43                 :            :     for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
      44                 :            :         unsigned char val = *i;
      45                 :            :         result += "\\x";
      46                 :            :         result += table[val / 16];
      47                 :            :         result += table[val % 16];
      48                 :            :     }
      49                 :            : 
      50                 :            :     return result;
      51                 :            : }
      52                 :            : #endif
      53                 :            : 
      54                 :            : #define DIR_START        11
      55                 :            : 
      56                 :     846594 : GlassCursor::GlassCursor(const GlassTable *B_, const Glass::Cursor * C_)
      57                 :            :         : is_positioned(false),
      58                 :            :           is_after_end(false),
      59                 :            :           tag_status(UNREAD),
      60                 :            :           B(B_),
      61                 :            :           version(B_->cursor_version),
      62         [ +  - ]:     846594 :           level(B_->level)
      63                 :            : {
      64                 :     846594 :     B->cursor_created_since_last_modification = true;
      65 [ +  - ][ +  - ]:    2617837 :     C = new Glass::Cursor[level + 1];
                 [ +  + ]
      66         [ +  + ]:     846594 :     if (!C_) C_ = B->C;
      67         [ +  + ]:    2617837 :     for (int j = 0; j <= level; ++j) {
      68         [ +  - ]:    1771243 :         C[j].clone(C_[j]);
      69                 :            :     }
      70                 :     846594 : }
      71                 :            : 
      72                 :            : void
      73                 :         58 : GlassCursor::rebuild()
      74                 :            : {
      75                 :         58 :     int new_level = B->level;
      76         [ +  + ]:         58 :     if (new_level <= level) {
      77         [ +  + ]:         90 :         for (int j = 0; j < new_level; ++j) {
      78                 :         33 :             C[j].clone(B->C[j]);
      79                 :            :         }
      80         [ +  + ]:        119 :         for (int j = new_level; j <= level; ++j) {
      81                 :         62 :             C[j].destroy();
      82                 :            :         }
      83                 :            :     } else {
      84                 :          1 :         Cursor * old_C = C;
      85 [ +  - ][ +  + ]:          3 :         C = new Cursor[new_level + 1];
      86         [ -  + ]:          1 :         for (int i = 0; i < level; ++i) {
      87                 :          0 :             C[i].swap(old_C[i]);
      88                 :          0 :             C[i].clone(B->C[i]);
      89                 :            :         }
      90 [ +  - ][ +  + ]:          2 :         delete [] old_C;
      91         [ +  + ]:          2 :         for (int j = level; j < new_level; ++j) {
      92                 :          1 :             C[j].init(B->block_size);
      93                 :            :         }
      94                 :            :     }
      95                 :         58 :     level = new_level;
      96                 :         58 :     C[level].clone(B->C[level]);
      97                 :         58 :     version = B->cursor_version;
      98                 :         58 :     B->cursor_created_since_last_modification = true;
      99                 :         58 : }
     100                 :            : 
     101                 :    1693188 : GlassCursor::~GlassCursor()
     102                 :            : {
     103                 :            :     // We must not use B here, as it may have already been destroyed.
     104 [ +  - ][ +  + ]:    2617838 :     delete [] C;
     105                 :     846594 : }
     106                 :            : 
     107                 :            : bool
     108                 :    1359841 : GlassCursor::next()
     109                 :            : {
     110                 :            :     LOGCALL(DB, bool, "GlassCursor::next", NO_ARGS);
     111                 :            :     Assert(!is_after_end);
     112         [ -  + ]:    1359841 :     if (B->cursor_version != version) {
     113                 :            :         // find_entry() will call rebuild().
     114                 :          0 :         (void)find_entry(current_key);
     115                 :            :         // If the key was found, we're now pointing to it, otherwise we're
     116                 :            :         // pointing to the entry before.  Either way, we now want to move to
     117                 :            :         // the next key.
     118                 :            :     }
     119 [ +  + ][ +  + ]:    1359841 :     if (tag_status == UNREAD || tag_status == UNREAD_ON_LAST_CHUNK) {
     120                 :            :         while (true) {
     121         [ +  + ]:     259962 :             if (! B->next(C, 0)) {
     122                 :      10421 :                 is_positioned = false;
     123                 :      10421 :                 break;
     124                 :            :             }
     125   [ +  +  +  - ]:     506660 :             if (tag_status == UNREAD_ON_LAST_CHUNK ||
                 [ +  - ]
     126 [ +  - ][ +  + ]:     257119 :                 LeafItem(C[0].get_p(), C[0].c).first_component()) {
                 [ #  # ]
     127                 :     249541 :                 is_positioned = true;
     128                 :     249541 :                 break;
     129                 :            :             }
     130                 :            :         }
     131                 :            :     }
     132                 :            : 
     133         [ +  + ]:    1359841 :     if (!is_positioned) {
     134                 :      21562 :         is_after_end = true;
     135                 :      21562 :         RETURN(false);
     136                 :            :     }
     137                 :            : 
     138                 :    1338279 :     get_key(&current_key);
     139                 :    1338279 :     tag_status = UNREAD;
     140                 :            : 
     141                 :            :     LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
     142                 :    1359841 :     RETURN(true);
     143                 :            : }
     144                 :            : 
     145                 :            : bool
     146                 :    2900245 : GlassCursor::find_entry(const string &key)
     147                 :            : {
     148                 :            :     LOGCALL(DB, bool, "GlassCursor::find_entry", key);
     149         [ +  + ]:    2900245 :     if (B->cursor_version != version) {
     150                 :         32 :         rebuild();
     151                 :            :     }
     152                 :            : 
     153                 :    2900245 :     is_after_end = false;
     154                 :            : 
     155                 :            :     bool found;
     156                 :            : 
     157                 :    2900245 :     is_positioned = true;
     158         [ +  + ]:    2900245 :     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) {
     159                 :            :         // Can't find key - too long to possibly be present, so find the
     160                 :            :         // truncated form but ignore "found".
     161         [ +  - ]:         36 :         B->form_key(key.substr(0, GLASS_BTREE_MAX_KEY_LEN));
     162                 :         36 :         (void)(B->find(C));
     163                 :         36 :         found = false;
     164                 :            :     } else {
     165                 :    2900209 :         B->form_key(key);
     166                 :    2900209 :         found = B->find(C);
     167                 :            :     }
     168                 :            : 
     169         [ +  + ]:    2900245 :     if (found) {
     170                 :     296467 :         tag_status = UNREAD;
     171                 :     296467 :         current_key = key;
     172                 :            :     } else {
     173                 :            :         // Be lazy about stepping back to the first chunk, as we may never be
     174                 :            :         // asked to read the tag.
     175                 :    2603778 :         tag_status = UNREAD_ON_LAST_CHUNK;
     176         [ +  + ]:    2603778 :         if (C[0].c < DIR_START) {
     177                 :            :             // It would be nice to be lazy about this too, but we need to
     178                 :            :             // be on an actual entry in order to read the key.
     179                 :        702 :             C[0].c = DIR_START;
     180         [ -  + ]:        702 :             if (! B->prev(C, 0)) {
     181                 :          0 :                 tag_status = UNREAD;
     182                 :            :             }
     183                 :            :         }
     184                 :    2603778 :         get_key(&current_key);
     185                 :            :     }
     186                 :            : 
     187                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     188                 :    2900245 :     RETURN(found);
     189                 :            : }
     190                 :            : 
     191                 :            : void
     192                 :      30893 : GlassCursor::find_entry_lt(const string &key)
     193                 :            : {
     194                 :            :     LOGCALL_VOID(DB, "GlassCursor::find_entry_lt", key);
     195         [ +  + ]:      30893 :     if (!find_entry(key)) {
     196                 :            :         // The entry wasn't found, so find_entry() left us on the entry before
     197                 :            :         // the one we asked for and we're done.
     198                 :      20325 :         return;
     199                 :            :     }
     200                 :            : 
     201                 :            :     Assert(!is_after_end);
     202                 :            :     Assert(is_positioned);
     203                 :            : 
     204         [ -  + ]:      10568 :     if (! B->prev(C, 0)) {
     205                 :          0 :         is_positioned = false;
     206                 :          0 :         return;
     207                 :            :     }
     208                 :      10568 :     tag_status = UNREAD_ON_LAST_CHUNK;
     209                 :      10568 :     get_key(&current_key);
     210                 :            : 
     211                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     212                 :            : }
     213                 :            : 
     214                 :            : bool
     215                 :       3192 : GlassCursor::find_exact(const string &key)
     216                 :            : {
     217                 :            :     LOGCALL(DB, bool, "GlassCursor::find_exact", key);
     218                 :       3192 :     is_after_end = false;
     219                 :       3192 :     is_positioned = false;
     220         [ -  + ]:       3192 :     if (rare(key.size() > GLASS_BTREE_MAX_KEY_LEN)) {
     221                 :            :         // There can't be a match
     222                 :          0 :         RETURN(false);
     223                 :            :     }
     224                 :            : 
     225         [ -  + ]:       3192 :     if (B->cursor_version != version) {
     226                 :          0 :         rebuild();
     227                 :            :     }
     228                 :            : 
     229                 :       3192 :     B->form_key(key);
     230         [ +  + ]:       3192 :     if (!B->find(C)) {
     231                 :         12 :         RETURN(false);
     232                 :            :     }
     233                 :       3180 :     current_key = key;
     234                 :       3180 :     B->read_tag(C, &current_tag, false);
     235                 :            : 
     236                 :       3180 :     RETURN(true);
     237                 :            : }
     238                 :            : 
     239                 :            : bool
     240                 :      51558 : GlassCursor::find_entry_ge(const string &key)
     241                 :            : {
     242                 :            :     LOGCALL(DB, bool, "GlassCursor::find_entry_ge", key);
     243         [ +  + ]:      51558 :     if (B->cursor_version != version) {
     244                 :         26 :         rebuild();
     245                 :            :     }
     246                 :            : 
     247                 :      51558 :     is_after_end = false;
     248                 :            : 
     249                 :            :     bool found;
     250                 :            : 
     251                 :      51558 :     is_positioned = true;
     252         [ -  + ]:      51558 :     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) {
     253                 :            :         // Can't find key - too long to possibly be present, so find the
     254                 :            :         // truncated form but ignore "found".
     255         [ #  # ]:          0 :         B->form_key(key.substr(0, GLASS_BTREE_MAX_KEY_LEN));
     256                 :          0 :         (void)(B->find(C));
     257                 :          0 :         found = false;
     258                 :            :     } else {
     259                 :      51558 :         B->form_key(key);
     260                 :      51558 :         found = B->find(C);
     261                 :            :     }
     262                 :            : 
     263         [ +  + ]:      51558 :     if (found) {
     264                 :      23574 :         current_key = key;
     265                 :            :     } else {
     266         [ +  + ]:      27984 :         if (! B->next(C, 0)) {
     267                 :      10248 :             is_after_end = true;
     268                 :      10248 :             is_positioned = false;
     269                 :      10248 :             RETURN(false);
     270                 :            :         }
     271                 :            :         Assert(LeafItem(C[0].get_p(), C[0].c).first_component());
     272                 :      17736 :         get_key(&current_key);
     273                 :            :     }
     274                 :      41310 :     tag_status = UNREAD;
     275                 :            : 
     276                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     277                 :      51558 :     RETURN(found);
     278                 :            : }
     279                 :            : 
     280                 :            : void
     281                 :    3970361 : GlassCursor::get_key(string * key) const
     282                 :            : {
     283                 :            :     Assert(B->level <= level);
     284                 :            :     Assert(is_positioned);
     285                 :            : 
     286         [ +  - ]:    3970361 :     (void)LeafItem(C[0].get_p(), C[0].c).key().read(key);
     287                 :    3970361 : }
     288                 :            : 
     289                 :            : bool
     290                 :    3716341 : GlassCursor::read_tag(bool keep_compressed)
     291                 :            : {
     292                 :            :     LOGCALL(DB, bool, "GlassCursor::read_tag", keep_compressed);
     293         [ +  + ]:    3716341 :     if (tag_status == UNREAD_ON_LAST_CHUNK) {
     294                 :            :         // Back up to first chunk of this tag.
     295         [ +  + ]:    6413027 :         while (!LeafItem(C[0].get_p(), C[0].c).first_component()) {
     296         [ -  + ]:    4082340 :             if (! B->prev(C, 0)) {
     297                 :          0 :                 is_positioned = false;
     298 [ #  # ][ #  # ]:          0 :                 throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
                 [ #  # ]
     299                 :            :             }
     300                 :            :         }
     301                 :    2330687 :         tag_status = UNREAD;
     302                 :            :     }
     303         [ +  + ]:    3716341 :     if (tag_status == UNREAD) {
     304                 :            :         Assert(B->level <= level);
     305                 :            :         Assert(is_positioned);
     306                 :            : 
     307         [ +  + ]:    3716227 :         if (B->read_tag(C, &current_tag, keep_compressed)) {
     308                 :      11739 :             tag_status = COMPRESSED;
     309                 :            :         } else {
     310                 :    3704488 :             tag_status = UNCOMPRESSED;
     311                 :            :         }
     312                 :            : 
     313                 :            :         // We need to call B->next(...) after B->read_tag(...) so that the
     314                 :            :         // cursor ends up on the next key.
     315                 :    3716227 :         is_positioned = B->next(C, 0);
     316                 :            : 
     317                 :            :         LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
     318                 :            :     }
     319                 :    3716341 :     RETURN(tag_status == COMPRESSED);
     320                 :            : }
     321                 :            : 
     322                 :            : bool
     323                 :         26 : MutableGlassCursor::del()
     324                 :            : {
     325                 :            :     Assert(!is_after_end);
     326                 :            : 
     327                 :            :     // MutableGlassCursor is only constructable from a non-const GlassTable*
     328                 :            :     // but we store that in the const GlassTable* "B" member of the GlassCursor
     329                 :            :     // class to avoid duplicating storage.  So we know it is safe to cast away
     330                 :            :     // that const again here.
     331                 :         26 :     (const_cast<GlassTable*>(B))->del(current_key);
     332                 :            : 
     333                 :            :     // If we're iterating an older revision of the tree, then the deletion
     334                 :            :     // happens in a new (uncommitted) revision and the cursor still sees
     335                 :            :     // the deleted key.  But if we're iterating the new uncommitted revision
     336                 :            :     // then the deleted key is no longer visible.  We need to handle both
     337                 :            :     // cases - either find_entry_ge() finds the deleted key or not.
     338         [ +  - ]:         26 :     if (!find_entry_ge(current_key)) return is_positioned;
     339                 :          0 :     return next();
     340                 :            : }
     341                 :            : 
     342                 :            : #ifdef DISABLE_GPL_LIBXAPIAN
     343                 :            : # error GPL source we cannot relicense included in libxapian
     344                 :            : #endif

Generated by: LCOV version 1.11