LCOV - code coverage report
Current view: top level - backends/glass - glass_cursor.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core c2b6f1024d3a Lines: 116 130 89.2 %
Date: 2019-05-16 09:13:18 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 <xapian/error.h>
      28                 :            : 
      29                 :            : #include "glass_table.h"
      30                 :            : #include "debuglog.h"
      31                 :            : #include "omassert.h"
      32                 :            : 
      33                 :            : using namespace Glass;
      34                 :            : 
      35                 :            : #ifdef XAPIAN_DEBUG_LOG
      36                 :            : static string
      37                 :            : hex_display_encode(const string & input)
      38                 :            : {
      39                 :            :     const char * table = "0123456789abcdef";
      40                 :            :     string result;
      41                 :            :     for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
      42                 :            :         unsigned char val = *i;
      43                 :            :         result += "\\x";
      44                 :            :         result += table[val / 16];
      45                 :            :         result += table[val % 16];
      46                 :            :     }
      47                 :            : 
      48                 :            :     return result;
      49                 :            : }
      50                 :            : #endif
      51                 :            : 
      52                 :            : #define DIR_START        11
      53                 :            : 
      54                 :     854321 : GlassCursor::GlassCursor(const GlassTable *B_, const Glass::Cursor * C_)
      55                 :            :         : is_positioned(false),
      56                 :            :           is_after_end(false),
      57                 :            :           tag_status(UNREAD),
      58                 :            :           B(B_),
      59                 :            :           version(B_->cursor_version),
      60         [ +  - ]:     854321 :           level(B_->level)
      61                 :            : {
      62                 :     854321 :     B->cursor_created_since_last_modification = true;
      63 [ +  - ][ +  - ]:    2639838 :     C = new Glass::Cursor[level + 1];
                 [ +  + ]
      64         [ +  + ]:     854321 :     if (!C_) C_ = B->C;
      65         [ +  + ]:    2639838 :     for (int j = 0; j <= level; ++j) {
      66         [ +  - ]:    1785517 :         C[j].clone(C_[j]);
      67                 :            :     }
      68                 :     854321 : }
      69                 :            : 
      70                 :            : void
      71                 :         58 : GlassCursor::rebuild()
      72                 :            : {
      73                 :         58 :     int new_level = B->level;
      74         [ +  + ]:         58 :     if (new_level <= level) {
      75         [ +  + ]:         90 :         for (int j = 0; j < new_level; ++j) {
      76                 :         33 :             C[j].clone(B->C[j]);
      77                 :            :         }
      78         [ +  + ]:        119 :         for (int j = new_level; j <= level; ++j) {
      79                 :         62 :             C[j].destroy();
      80                 :            :         }
      81                 :            :     } else {
      82                 :          1 :         Cursor * old_C = C;
      83 [ +  - ][ +  + ]:          3 :         C = new Cursor[new_level + 1];
      84         [ -  + ]:          1 :         for (int i = 0; i < level; ++i) {
      85                 :          0 :             C[i].swap(old_C[i]);
      86                 :          0 :             C[i].clone(B->C[i]);
      87                 :            :         }
      88 [ +  - ][ +  + ]:          2 :         delete [] old_C;
      89         [ +  + ]:          2 :         for (int j = level; j < new_level; ++j) {
      90                 :          1 :             C[j].init(B->block_size);
      91                 :            :         }
      92                 :            :     }
      93                 :         58 :     level = new_level;
      94                 :         58 :     C[level].clone(B->C[level]);
      95                 :         58 :     version = B->cursor_version;
      96                 :         58 :     B->cursor_created_since_last_modification = true;
      97                 :         58 : }
      98                 :            : 
      99                 :    1708642 : GlassCursor::~GlassCursor()
     100                 :            : {
     101                 :            :     // We must not use B here, as it may have already been destroyed.
     102 [ +  - ][ +  + ]:    2639839 :     delete [] C;
     103                 :     854321 : }
     104                 :            : 
     105                 :            : bool
     106                 :    1415322 : GlassCursor::next()
     107                 :            : {
     108                 :            :     LOGCALL(DB, bool, "GlassCursor::next", NO_ARGS);
     109                 :            :     Assert(!is_after_end);
     110         [ -  + ]:    1415322 :     if (B->cursor_version != version) {
     111                 :            :         // find_entry() will call rebuild().
     112                 :          0 :         (void)find_entry(current_key);
     113                 :            :         // If the key was found, we're now pointing to it, otherwise we're
     114                 :            :         // pointing to the entry before.  Either way, we now want to move to
     115                 :            :         // the next key.
     116                 :            :     }
     117 [ +  + ][ +  + ]:    1415322 :     if (tag_status == UNREAD || tag_status == UNREAD_ON_LAST_CHUNK) {
     118                 :            :         while (true) {
     119         [ +  + ]:     262967 :             if (! B->next(C, 0)) {
     120                 :      10492 :                 is_positioned = false;
     121                 :      10492 :                 break;
     122                 :            :             }
     123   [ +  +  +  - ]:     518284 :             if (tag_status == UNREAD_ON_LAST_CHUNK ||
                 [ +  - ]
     124 [ +  - ][ +  + ]:     265809 :                 LeafItem(C[0].get_p(), C[0].c).first_component()) {
                 [ #  # ]
     125                 :     252475 :                 is_positioned = true;
     126                 :     252475 :                 break;
     127                 :            :             }
     128                 :            :         }
     129                 :            :     }
     130                 :            : 
     131         [ +  + ]:    1415322 :     if (!is_positioned) {
     132                 :      21665 :         is_after_end = true;
     133                 :      21665 :         RETURN(false);
     134                 :            :     }
     135                 :            : 
     136                 :    1393657 :     get_key(&current_key);
     137                 :    1393657 :     tag_status = UNREAD;
     138                 :            : 
     139                 :            :     LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
     140                 :    1415322 :     RETURN(true);
     141                 :            : }
     142                 :            : 
     143                 :            : bool
     144                 :    2907876 : GlassCursor::find_entry(const string &key)
     145                 :            : {
     146                 :            :     LOGCALL(DB, bool, "GlassCursor::find_entry", key);
     147         [ +  + ]:    2907876 :     if (B->cursor_version != version) {
     148                 :         32 :         rebuild();
     149                 :            :     }
     150                 :            : 
     151                 :    2907876 :     is_after_end = false;
     152                 :            : 
     153                 :            :     bool found;
     154                 :            : 
     155                 :    2907876 :     is_positioned = true;
     156         [ +  + ]:    2907876 :     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) {
     157                 :            :         // Can't find key - too long to possibly be present, so find the
     158                 :            :         // truncated form but ignore "found".
     159         [ +  - ]:         36 :         B->form_key(key.substr(0, GLASS_BTREE_MAX_KEY_LEN));
     160                 :         36 :         (void)(B->find(C));
     161                 :         36 :         found = false;
     162                 :            :     } else {
     163                 :    2907840 :         B->form_key(key);
     164                 :    2907840 :         found = B->find(C);
     165                 :            :     }
     166                 :            : 
     167         [ +  + ]:    2907876 :     if (found) {
     168                 :     296858 :         tag_status = UNREAD;
     169                 :     296858 :         current_key = key;
     170                 :            :     } else {
     171                 :            :         // Be lazy about stepping back to the first chunk, as we may never be
     172                 :            :         // asked to read the tag.
     173                 :    2611018 :         tag_status = UNREAD_ON_LAST_CHUNK;
     174         [ +  + ]:    2611018 :         if (C[0].c < DIR_START) {
     175                 :            :             // It would be nice to be lazy about this too, but we need to
     176                 :            :             // be on an actual entry in order to read the key.
     177                 :        702 :             C[0].c = DIR_START;
     178         [ -  + ]:        702 :             if (! B->prev(C, 0)) {
     179                 :          0 :                 tag_status = UNREAD;
     180                 :            :             }
     181                 :            :         }
     182                 :    2611018 :         get_key(&current_key);
     183                 :            :     }
     184                 :            : 
     185                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     186                 :    2907876 :     RETURN(found);
     187                 :            : }
     188                 :            : 
     189                 :            : void
     190                 :      30893 : GlassCursor::find_entry_lt(const string &key)
     191                 :            : {
     192                 :            :     LOGCALL_VOID(DB, "GlassCursor::find_entry_lt", key);
     193         [ +  + ]:      30893 :     if (!find_entry(key)) {
     194                 :            :         // The entry wasn't found, so find_entry() left us on the entry before
     195                 :            :         // the one we asked for and we're done.
     196                 :      20325 :         return;
     197                 :            :     }
     198                 :            : 
     199                 :            :     Assert(!is_after_end);
     200                 :            :     Assert(is_positioned);
     201                 :            : 
     202         [ -  + ]:      10568 :     if (! B->prev(C, 0)) {
     203                 :          0 :         is_positioned = false;
     204                 :          0 :         return;
     205                 :            :     }
     206                 :      10568 :     tag_status = UNREAD_ON_LAST_CHUNK;
     207                 :      10568 :     get_key(&current_key);
     208                 :            : 
     209                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     210                 :            : }
     211                 :            : 
     212                 :            : bool
     213                 :       3192 : GlassCursor::find_exact(const string &key)
     214                 :            : {
     215                 :            :     LOGCALL(DB, bool, "GlassCursor::find_exact", key);
     216                 :       3192 :     is_after_end = false;
     217                 :       3192 :     is_positioned = false;
     218         [ -  + ]:       3192 :     if (rare(key.size() > GLASS_BTREE_MAX_KEY_LEN)) {
     219                 :            :         // There can't be a match
     220                 :          0 :         RETURN(false);
     221                 :            :     }
     222                 :            : 
     223         [ -  + ]:       3192 :     if (B->cursor_version != version) {
     224                 :          0 :         rebuild();
     225                 :            :     }
     226                 :            : 
     227                 :       3192 :     B->form_key(key);
     228         [ +  + ]:       3192 :     if (!B->find(C)) {
     229                 :         12 :         RETURN(false);
     230                 :            :     }
     231                 :       3180 :     current_key = key;
     232                 :       3180 :     B->read_tag(C, &current_tag, false);
     233                 :            : 
     234                 :       3180 :     RETURN(true);
     235                 :            : }
     236                 :            : 
     237                 :            : bool
     238                 :      51711 : GlassCursor::find_entry_ge(const string &key)
     239                 :            : {
     240                 :            :     LOGCALL(DB, bool, "GlassCursor::find_entry_ge", key);
     241         [ +  + ]:      51711 :     if (B->cursor_version != version) {
     242                 :         26 :         rebuild();
     243                 :            :     }
     244                 :            : 
     245                 :      51711 :     is_after_end = false;
     246                 :            : 
     247                 :            :     bool found;
     248                 :            : 
     249                 :      51711 :     is_positioned = true;
     250         [ -  + ]:      51711 :     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) {
     251                 :            :         // Can't find key - too long to possibly be present, so find the
     252                 :            :         // truncated form but ignore "found".
     253         [ #  # ]:          0 :         B->form_key(key.substr(0, GLASS_BTREE_MAX_KEY_LEN));
     254                 :          0 :         (void)(B->find(C));
     255                 :          0 :         found = false;
     256                 :            :     } else {
     257                 :      51711 :         B->form_key(key);
     258                 :      51711 :         found = B->find(C);
     259                 :            :     }
     260                 :            : 
     261         [ +  + ]:      51711 :     if (found) {
     262                 :      23608 :         current_key = key;
     263                 :            :     } else {
     264         [ +  + ]:      28103 :         if (! B->next(C, 0)) {
     265                 :      10261 :             is_after_end = true;
     266                 :      10261 :             is_positioned = false;
     267                 :      10261 :             RETURN(false);
     268                 :            :         }
     269                 :            :         Assert(LeafItem(C[0].get_p(), C[0].c).first_component());
     270                 :      17842 :         get_key(&current_key);
     271                 :            :     }
     272                 :      41450 :     tag_status = UNREAD;
     273                 :            : 
     274                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     275                 :      51711 :     RETURN(found);
     276                 :            : }
     277                 :            : 
     278                 :            : void
     279                 :    4033085 : GlassCursor::get_key(string * key) const
     280                 :            : {
     281                 :            :     Assert(B->level <= level);
     282                 :            :     Assert(is_positioned);
     283                 :            : 
     284         [ +  - ]:    4033085 :     (void)LeafItem(C[0].get_p(), C[0].c).key().read(key);
     285                 :    4033085 : }
     286                 :            : 
     287                 :            : bool
     288                 :    3776371 : GlassCursor::read_tag(bool keep_compressed)
     289                 :            : {
     290                 :            :     LOGCALL(DB, bool, "GlassCursor::read_tag", keep_compressed);
     291         [ +  + ]:    3776371 :     if (tag_status == UNREAD_ON_LAST_CHUNK) {
     292                 :            :         // Back up to first chunk of this tag.
     293         [ +  + ]:    6420190 :         while (!LeafItem(C[0].get_p(), C[0].c).first_component()) {
     294         [ -  + ]:    4082340 :             if (! B->prev(C, 0)) {
     295                 :          0 :                 is_positioned = false;
     296 [ #  # ][ #  # ]:          0 :                 throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
                 [ #  # ]
     297                 :            :             }
     298                 :            :         }
     299                 :    2337850 :         tag_status = UNREAD;
     300                 :            :     }
     301         [ +  + ]:    3776371 :     if (tag_status == UNREAD) {
     302                 :            :         Assert(B->level <= level);
     303                 :            :         Assert(is_positioned);
     304                 :            : 
     305         [ +  + ]:    3776257 :         if (B->read_tag(C, &current_tag, keep_compressed)) {
     306                 :      12190 :             tag_status = COMPRESSED;
     307                 :            :         } else {
     308                 :    3764067 :             tag_status = UNCOMPRESSED;
     309                 :            :         }
     310                 :            : 
     311                 :            :         // We need to call B->next(...) after B->read_tag(...) so that the
     312                 :            :         // cursor ends up on the next key.
     313                 :    3776257 :         is_positioned = B->next(C, 0);
     314                 :            : 
     315                 :            :         LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
     316                 :            :     }
     317                 :    3776371 :     RETURN(tag_status == COMPRESSED);
     318                 :            : }
     319                 :            : 
     320                 :            : bool
     321                 :         26 : MutableGlassCursor::del()
     322                 :            : {
     323                 :            :     Assert(!is_after_end);
     324                 :            : 
     325                 :            :     // MutableGlassCursor is only constructable from a non-const GlassTable*
     326                 :            :     // but we store that in the const GlassTable* "B" member of the GlassCursor
     327                 :            :     // class to avoid duplicating storage.  So we know it is safe to cast away
     328                 :            :     // that const again here.
     329                 :         26 :     (const_cast<GlassTable*>(B))->del(current_key);
     330                 :            : 
     331                 :            :     // If we're iterating an older revision of the tree, then the deletion
     332                 :            :     // happens in a new (uncommitted) revision and the cursor still sees
     333                 :            :     // the deleted key.  But if we're iterating the new uncommitted revision
     334                 :            :     // then the deleted key is no longer visible.  We need to handle both
     335                 :            :     // cases - either find_entry_ge() finds the deleted key or not.
     336         [ +  - ]:         26 :     if (!find_entry_ge(current_key)) return is_positioned;
     337                 :          0 :     return next();
     338                 :            : }
     339                 :            : 
     340                 :            : #ifdef DISABLE_GPL_LIBXAPIAN
     341                 :            : # error GPL source we cannot relicense included in libxapian
     342                 :            : #endif

Generated by: LCOV version 1.11