LCOV - code coverage report
Current view: top level - backends/brass - brass_cursor.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core r Lines: 103 130 79.2 %
Date: 2011-08-21 Functions: 12 12 100.0 %
Branches: 60 88 68.2 %

           Branch data     Line data    Source code
       1                 :            : /* brass_cursor.cc: Btree cursor implementation
       2                 :            :  *
       3                 :            :  * Copyright 1999,2000,2001 BrightStation PLC
       4                 :            :  * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010 Olly Betts
       5                 :            :  *
       6                 :            :  * This program is free software; you can redistribute it and/or
       7                 :            :  * modify it under the terms of the GNU General Public License as
       8                 :            :  * published by the Free Software Foundation; either version 2 of the
       9                 :            :  * License, or (at your option) any later version.
      10                 :            :  *
      11                 :            :  * This program is distributed in the hope that it will be useful,
      12                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            :  * GNU General Public License for more details.
      15                 :            :  *
      16                 :            :  * You should have received a copy of the GNU General Public License
      17                 :            :  * along with this program; if not, write to the Free Software
      18                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
      19                 :            :  * USA
      20                 :            :  */
      21                 :            : 
      22                 :            : #include <config.h>
      23                 :            : 
      24                 :            : #include "brass_cursor.h"
      25                 :            : 
      26                 :            : #include "safeerrno.h"
      27                 :            : 
      28                 :            : #include <xapian/error.h>
      29                 :            : 
      30                 :            : #include "brass_table.h"
      31                 :            : #include "debuglog.h"
      32                 :            : #include "omassert.h"
      33                 :            : 
      34                 :            : using namespace Brass;
      35                 :            : 
      36                 :            : #ifdef XAPIAN_DEBUG_LOG
      37                 :            : static string
      38                 :            : hex_display_encode(const string & input)
      39                 :            : {
      40                 :            :     const char * table = "0123456789abcdef";
      41                 :            :     string result;
      42                 :            :     for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
      43                 :            :         unsigned char val = *i;
      44                 :            :         result += "\\x";
      45                 :            :         result += table[val/16];
      46                 :            :         result += table[val%16];
      47                 :            :     }
      48                 :            : 
      49                 :            :     return result;
      50                 :            : }
      51                 :            : #endif
      52                 :            : 
      53                 :            : #define DIR_START        11
      54                 :            : 
      55                 :    2004692 : BrassCursor::BrassCursor(const BrassTable *B_)
      56                 :            :         : is_positioned(false),
      57                 :            :           is_after_end(false),
      58                 :            :           tag_status(UNREAD),
      59                 :            :           B(B_),
      60                 :            :           version(B_->cursor_version),
      61                 :    2004692 :           level(B_->level)
      62                 :            : {
      63                 :    2004692 :     B->cursor_created_since_last_modification = true;
      64 [ +  + ][ +  + ]:    7740727 :     C = new Brass::Cursor[level + 1];
      65                 :            : 
      66 [ +  + ][ +  + ]:    5736035 :     for (int j = 0; j < level; j++) {
      67                 :    3731343 :         C[j].n = BLK_UNUSED;
      68                 :    3731343 :         C[j].p = new byte[B->block_size];
      69                 :            :     }
      70                 :    2004692 :     C[level].n = B->C[level].n;
      71                 :    2004692 :     C[level].p = B->C[level].p;
      72                 :    2004692 : }
      73                 :            : 
      74                 :            : void
      75                 :          6 : BrassCursor::rebuild()
      76                 :            : {
      77                 :          6 :     int new_level = B->level;
      78         [ +  - ]:          6 :     if (new_level <= level) {
      79         [ +  + ]:         12 :         for (int i = 0; i < new_level; i++) {
      80                 :          6 :             C[i].n = BLK_UNUSED;
      81                 :            :         }
      82         [ -  + ]:          6 :         for (int j = new_level; j < level; ++j) {
      83                 :          0 :             delete C[j].p;
      84                 :            :         }
      85                 :            :     } else {
      86                 :          0 :         Cursor * old_C = C;
      87         [ #  # ]:          0 :         C = new Cursor[new_level + 1];
      88         [ #  # ]:          0 :         for (int i = 0; i < level; i++) {
      89                 :          0 :             C[i].p = old_C[i].p;
      90                 :          0 :             C[i].n = BLK_UNUSED;
      91                 :            :         }
      92                 :          0 :         delete old_C;
      93         [ #  # ]:          0 :         for (int j = level; j < new_level; j++) {
      94                 :          0 :             C[j].p = new byte[B->block_size];
      95                 :          0 :             C[j].n = BLK_UNUSED;
      96                 :            :         }
      97                 :            :     }
      98                 :          6 :     level = new_level;
      99                 :          6 :     C[level].n = B->C[level].n;
     100                 :          6 :     C[level].p = B->C[level].p;
     101                 :          6 :     version = B->cursor_version;
     102                 :          6 : }
     103                 :            : 
     104                 :    2004692 : BrassCursor::~BrassCursor()
     105                 :            : {
     106                 :            :     // Use the value of level stored in the cursor rather than the
     107                 :            :     // Btree, since the Btree might have been deleted already.
     108 [ +  + ][ +  + ]:    5736035 :     for (int j = 0; j < level; j++) {
     109 [ +  - ][ +  - ]:    3731343 :         delete [] C[j].p;
     110                 :            :     }
     111 [ +  - ][ +  - ]:    2004692 :     delete [] C;
     112                 :    2004692 : }
     113                 :            : 
     114                 :            : bool
     115                 :          8 : BrassCursor::prev()
     116                 :            : {
     117                 :            :     LOGCALL(DB, bool, "BrassCursor::prev", NO_ARGS);
     118                 :            :     Assert(!is_after_end);
     119 [ +  - ][ -  + ]:          8 :     if (B->cursor_version != version || !is_positioned) {
     120                 :            :         // Either the cursor needs rebuilding (in which case find_entry() will
     121                 :            :         // call rebuild() and then reposition the cursor), or we've read the
     122                 :            :         // last key and tag, and we're now not positioned (in which case we
     123                 :            :         // seek to the current key, and then it's as if we read the key but not
     124                 :            :         // the tag).
     125         [ #  # ]:          0 :         if (!find_entry(current_key)) {
     126                 :            :             // Exact entry was no longer there after rebuild(), and we've
     127                 :            :             // automatically ended up on the entry before it.
     128                 :          0 :             RETURN(true);
     129                 :            :         }
     130         [ -  + ]:          8 :     } else if (tag_status != UNREAD) {
     131                 :          0 :         while (true) {
     132         [ #  # ]:          0 :             if (! B->prev(C, 0)) {
     133                 :          0 :                 is_positioned = false;
     134                 :          0 :                 RETURN(false);
     135                 :            :             }
     136         [ #  # ]:          0 :             if (Item(C[0].p, C[0].c).component_of() == 1) {
     137                 :          0 :                 break;
     138                 :            :             }
     139                 :            :         }
     140                 :            :     }
     141                 :            : 
     142                 :          8 :     while (true) {
     143         [ -  + ]:          8 :         if (! B->prev(C, 0)) {
     144                 :          0 :             is_positioned = false;
     145                 :          0 :             RETURN(false);
     146                 :            :         }
     147         [ +  - ]:          8 :         if (Item(C[0].p, C[0].c).component_of() == 1) {
     148                 :            :             break;
     149                 :            :         }
     150                 :            :     }
     151                 :          8 :     get_key(&current_key);
     152                 :          8 :     tag_status = UNREAD;
     153                 :            : 
     154                 :            :     LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
     155                 :          8 :     RETURN(true);
     156                 :            : }
     157                 :            : 
     158                 :            : bool
     159                 :     192732 : BrassCursor::next()
     160                 :            : {
     161                 :            :     LOGCALL(DB, bool, "BrassCursor::next", NO_ARGS);
     162                 :            :     Assert(!is_after_end);
     163         [ -  + ]:     192732 :     if (B->cursor_version != version) {
     164                 :            :         // find_entry() will call rebuild().
     165                 :          0 :         (void)find_entry(current_key);
     166                 :            :         // If the key was found, we're now pointing to it, otherwise we're
     167                 :            :         // pointing to the entry before.  Either way, we now want to move to
     168                 :            :         // the next key.
     169                 :            :     }
     170         [ +  + ]:     192732 :     if (tag_status == UNREAD) {
     171                 :        291 :         while (true) {
     172         [ +  + ]:     167430 :             if (! B->next(C, 0)) {
     173                 :         77 :                 is_positioned = false;
     174                 :         77 :                 break;
     175                 :            :             }
     176         [ +  + ]:     167353 :             if (Item(C[0].p, C[0].c).component_of() == 1) {
     177                 :     167062 :                 is_positioned = true;
     178                 :     167062 :                 break;
     179                 :            :             }
     180                 :            :         }
     181                 :            :     }
     182                 :            : 
     183         [ +  + ]:     192732 :     if (!is_positioned) {
     184                 :        266 :         is_after_end = true;
     185                 :        266 :         RETURN(false);
     186                 :            :     }
     187                 :            : 
     188                 :     192466 :     get_key(&current_key);
     189                 :     192466 :     tag_status = UNREAD;
     190                 :            : 
     191                 :            :     LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
     192                 :     192732 :     RETURN(true);
     193                 :            : }
     194                 :            : 
     195                 :            : bool
     196                 :    2098823 : BrassCursor::find_entry(const string &key)
     197                 :            : {
     198                 :            :     LOGCALL(DB, bool, "BrassCursor::find_entry", key);
     199         [ -  + ]:    2098823 :     if (B->cursor_version != version) {
     200                 :          0 :         rebuild();
     201                 :            :     }
     202                 :            : 
     203                 :    2098823 :     is_after_end = false;
     204                 :            : 
     205                 :            :     bool found;
     206                 :            : 
     207                 :    2098823 :     is_positioned = true;
     208         [ +  + ]:    2098823 :     if (key.size() > BRASS_BTREE_MAX_KEY_LEN) {
     209                 :            :         // Can't find key - too long to possibly be present, so find the
     210                 :            :         // truncated form but ignore "found".
     211                 :         30 :         B->form_key(key.substr(0, BRASS_BTREE_MAX_KEY_LEN));
     212                 :         30 :         (void)(B->find(C));
     213                 :         30 :         found = false;
     214                 :            :     } else {
     215                 :    2098793 :         B->form_key(key);
     216                 :    2098793 :         found = B->find(C);
     217                 :            :     }
     218                 :            : 
     219         [ +  + ]:    2098823 :     if (!found) {
     220         [ +  + ]:    1906282 :         if (C[0].c < DIR_START) {
     221                 :      38080 :             C[0].c = DIR_START;
     222         [ -  + ]:      38080 :             if (! B->prev(C, 0)) goto done;
     223                 :            :         }
     224         [ +  + ]:    5749571 :         while (Item(C[0].p, C[0].c).component_of() != 1) {
     225         [ -  + ]:    3843289 :             if (! B->prev(C, 0)) {
     226                 :          0 :                 is_positioned = false;
     227                 :          0 :                 throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
     228                 :            :             }
     229                 :            :         }
     230                 :            :     }
     231                 :            : done:
     232                 :            : 
     233         [ +  + ]:    2098823 :     if (found)
     234                 :     192541 :         current_key = key;
     235                 :            :     else
     236                 :    1906282 :         get_key(&current_key);
     237                 :    2098823 :     tag_status = UNREAD;
     238                 :            : 
     239                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     240                 :    2098823 :     RETURN(found);
     241                 :            : }
     242                 :            : 
     243                 :            : bool
     244                 :       1819 : BrassCursor::find_entry_ge(const string &key)
     245                 :            : {
     246                 :            :     LOGCALL(DB, bool, "BrassCursor::find_entry_ge", key);
     247         [ +  + ]:       1819 :     if (B->cursor_version != version) {
     248                 :          6 :         rebuild();
     249                 :            :     }
     250                 :            : 
     251                 :       1819 :     is_after_end = false;
     252                 :            : 
     253                 :            :     bool found;
     254                 :            : 
     255                 :       1819 :     is_positioned = true;
     256         [ -  + ]:       1819 :     if (key.size() > BRASS_BTREE_MAX_KEY_LEN) {
     257                 :            :         // Can't find key - too long to possibly be present, so find the
     258                 :            :         // truncated form but ignore "found".
     259                 :          0 :         B->form_key(key.substr(0, BRASS_BTREE_MAX_KEY_LEN));
     260                 :          0 :         (void)(B->find(C));
     261                 :          0 :         found = false;
     262                 :            :     } else {
     263                 :       1819 :         B->form_key(key);
     264                 :       1819 :         found = B->find(C);
     265                 :            :     }
     266                 :            : 
     267         [ +  + ]:       1816 :     if (found) {
     268                 :       1379 :         current_key = key;
     269                 :            :     } else {
     270         [ +  + ]:        437 :         if (! B->next(C, 0)) {
     271                 :         40 :             is_after_end = true;
     272                 :         40 :             is_positioned = false;
     273                 :         40 :             RETURN(false);
     274                 :            :         }
     275                 :            :         Assert(Item(C[0].p, C[0].c).component_of() == 1);
     276                 :        397 :         get_key(&current_key);
     277                 :            :     }
     278                 :       1776 :     tag_status = UNREAD;
     279                 :            : 
     280                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     281                 :       1816 :     RETURN(found);
     282                 :            : }
     283                 :            : 
     284                 :            : void
     285                 :    2099153 : BrassCursor::get_key(string * key) const
     286                 :            : {
     287                 :            :     Assert(B->level <= level);
     288                 :            :     Assert(is_positioned);
     289                 :            : 
     290                 :    2099153 :     (void)Item(C[0].p, C[0].c).key().read(key);
     291                 :    2099153 : }
     292                 :            : 
     293                 :            : bool
     294                 :    1932604 : BrassCursor::read_tag(bool keep_compressed)
     295                 :            : {
     296                 :            :     LOGCALL(DB, bool, "BrassCursor::read_tag", keep_compressed);
     297         [ +  + ]:    1932604 :     if (tag_status == UNREAD) {
     298                 :            :         Assert(B->level <= level);
     299                 :            :         Assert(is_positioned);
     300                 :            : 
     301         [ +  + ]:    1932547 :         if (B->read_tag(C, &current_tag, keep_compressed)) {
     302                 :        157 :             tag_status = COMPRESSED;
     303                 :            :         } else {
     304                 :    1932390 :             tag_status = UNCOMPRESSED;
     305                 :            :         }
     306                 :            : 
     307                 :            :         // We need to call B->next(...) after B->read_tag(...) so that the
     308                 :            :         // cursor ends up on the next key.
     309                 :    1932547 :         is_positioned = B->next(C, 0);
     310                 :            : 
     311                 :            :         LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
     312                 :            :     }
     313                 :    1932604 :     RETURN(tag_status == COMPRESSED);
     314                 :            : }
     315                 :            : 
     316                 :            : bool
     317                 :         18 : MutableBrassCursor::del()
     318                 :            : {
     319                 :            :     Assert(!is_after_end);
     320                 :            : 
     321                 :            :     // MutableBrassCursor is only constructable from a non-const BrassTable*
     322                 :            :     // but we store that in the const BrassTable* "B" member of the BrassCursor
     323                 :            :     // class to avoid duplicating storage.  So we know it is safe to cast away
     324                 :            :     // that const again here.
     325                 :         18 :     (const_cast<BrassTable*>(B))->del(current_key);
     326                 :            : 
     327                 :            :     // If we're iterating an older revision of the tree, then the deletion
     328                 :            :     // happens in a new (uncommitted) revision and the cursor still sees
     329                 :            :     // the deleted key.  But if we're iterating the new uncommitted revision
     330                 :            :     // then the deleted key is no longer visible.  We need to handle both
     331                 :            :     // cases - either find_entry_ge() finds the deleted key or not.
     332         [ +  + ]:         18 :     if (!find_entry_ge(current_key)) return is_positioned;
     333                 :         18 :     return next();
     334                 :            : }

Generated by: LCOV version 1.8