LCOV - code coverage report
Current view: top level - backends/flint - flint_cursor.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core r Lines: 101 130 77.7 %
Date: 2011-08-21 Functions: 12 12 100.0 %
Branches: 57 88 64.8 %

           Branch data     Line data    Source code
       1                 :            : /* flint_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 "flint_cursor.h"
      25                 :            : 
      26                 :            : #include "safeerrno.h"
      27                 :            : 
      28                 :            : #include <xapian/error.h>
      29                 :            : 
      30                 :            : #include "debuglog.h"
      31                 :            : #include "flint_table.h"
      32                 :            : #include "omassert.h"
      33                 :            : 
      34                 :            : #ifdef XAPIAN_DEBUG_LOG
      35                 :            : static string
      36                 :            : hex_display_encode(const string & input)
      37                 :            : {
      38                 :            :     const char * table = "0123456789abcdef";
      39                 :            :     string result;
      40                 :            :     for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
      41                 :            :         unsigned char val = *i;
      42                 :            :         result += "\\x";
      43                 :            :         result += table[val/16];
      44                 :            :         result += table[val%16];
      45                 :            :     }
      46                 :            : 
      47                 :            :     return result;
      48                 :            : }
      49                 :            : #endif
      50                 :            : 
      51                 :            : #define DIR_START        11
      52                 :            : 
      53                 :     166790 : FlintCursor::FlintCursor(FlintTable *B_)
      54                 :            :         : is_positioned(false),
      55                 :            :           is_after_end(false),
      56                 :            :           tag_status(UNREAD),
      57                 :            :           B(B_),
      58                 :            :           version(B_->cursor_version),
      59                 :     166790 :           level(B_->level)
      60                 :            : {
      61                 :     166790 :     B->cursor_created_since_last_modification = true;
      62 [ +  + ][ +  + ]:     543930 :     C = new Cursor_[level + 1];
      63                 :            : 
      64 [ +  + ][ +  + ]:     377140 :     for (int j = 0; j < level; j++) {
      65                 :     210350 :         C[j].n = BLK_UNUSED;
      66                 :     210350 :         C[j].p = new byte[B->block_size];
      67                 :            :     }
      68                 :     166790 :     C[level].n = B->C[level].n;
      69                 :     166790 :     C[level].p = B->C[level].p;
      70                 :     166790 : }
      71                 :            : 
      72                 :            : void
      73                 :         10 : FlintCursor::rebuild()
      74                 :            : {
      75                 :         10 :     int new_level = B->level;
      76         [ +  - ]:         10 :     if (new_level <= level) {
      77         [ +  + ]:         20 :         for (int i = 0; i < new_level; i++) {
      78                 :         10 :             C[i].n = BLK_UNUSED;
      79                 :            :         }
      80         [ -  + ]:         10 :         for (int j = new_level; j < level; ++j) {
      81                 :          0 :             delete C[j].p;
      82                 :            :         }
      83                 :            :     } else {
      84                 :          0 :         Cursor_ * old_C = C;
      85         [ #  # ]:          0 :         C = new Cursor_[new_level + 1];
      86         [ #  # ]:          0 :         for (int i = 0; i < level; i++) {
      87                 :          0 :             C[i].p = old_C[i].p;
      88                 :          0 :             C[i].n = BLK_UNUSED;
      89                 :            :         }
      90                 :          0 :         delete old_C;
      91         [ #  # ]:          0 :         for (int j = level; j < new_level; j++) {
      92                 :          0 :             C[j].p = new byte[B->block_size];
      93                 :          0 :             C[j].n = BLK_UNUSED;
      94                 :            :         }
      95                 :            :     }
      96                 :         10 :     level = new_level;
      97                 :         10 :     C[level].n = B->C[level].n;
      98                 :         10 :     C[level].p = B->C[level].p;
      99                 :         10 :     version = B->cursor_version;
     100                 :         10 : }
     101                 :            : 
     102                 :     166790 : FlintCursor::~FlintCursor()
     103                 :            : {
     104                 :            :     // Use the value of level stored in the cursor rather than the
     105                 :            :     // Btree, since the Btree might have been deleted already.
     106 [ +  + ][ +  + ]:     377140 :     for (int j = 0; j < level; j++) {
     107 [ +  - ][ +  - ]:     210350 :         delete [] C[j].p;
     108                 :            :     }
     109 [ +  - ][ +  - ]:     166790 :     delete [] C;
     110                 :     166790 : }
     111                 :            : 
     112                 :            : bool
     113                 :          8 : FlintCursor::prev()
     114                 :            : {
     115                 :            :     LOGCALL(DB, bool, "FlintCursor::prev", NO_ARGS);
     116                 :            :     Assert(!is_after_end);
     117 [ +  - ][ -  + ]:          8 :     if (B->cursor_version != version || !is_positioned) {
     118                 :            :         // Either the cursor needs rebuilding (in which case find_entry() will
     119                 :            :         // call rebuild() and then reposition the cursor), or we've read the
     120                 :            :         // last key and tag, and we're now not positioned (in which case we
     121                 :            :         // seek to the current key, and then it's as if we read the key but not
     122                 :            :         // the tag).
     123         [ #  # ]:          0 :         if (!find_entry(current_key)) {
     124                 :            :             // Exact entry was no longer there after rebuild(), and we've
     125                 :            :             // automatically ended up on the entry before it.
     126                 :          0 :             RETURN(true);
     127                 :            :         }
     128         [ -  + ]:          8 :     } else if (tag_status != UNREAD) {
     129                 :          0 :         while (true) {
     130         [ #  # ]:          0 :             if (! B->prev(C, 0)) {
     131                 :          0 :                 is_positioned = false;
     132                 :          0 :                 RETURN(false);
     133                 :            :             }
     134         [ #  # ]:          0 :             if (Item_(C[0].p, C[0].c).component_of() == 1) {
     135                 :          0 :                 break;
     136                 :            :             }
     137                 :            :         }
     138                 :            :     }
     139                 :            : 
     140                 :          8 :     while (true) {
     141         [ -  + ]:          8 :         if (! B->prev(C, 0)) {
     142                 :          0 :             is_positioned = false;
     143                 :          0 :             RETURN(false);
     144                 :            :         }
     145         [ +  - ]:          8 :         if (Item_(C[0].p, C[0].c).component_of() == 1) {
     146                 :            :             break;
     147                 :            :         }
     148                 :            :     }
     149                 :          8 :     get_key(&current_key);
     150                 :          8 :     tag_status = UNREAD;
     151                 :            : 
     152                 :            :     LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
     153                 :          8 :     RETURN(true);
     154                 :            : }
     155                 :            : 
     156                 :            : bool
     157                 :      38093 : FlintCursor::next()
     158                 :            : {
     159                 :            :     LOGCALL(DB, bool, "FlintCursor::next", NO_ARGS);
     160                 :            :     Assert(!is_after_end);
     161         [ -  + ]:      38093 :     if (B->cursor_version != version) {
     162                 :            :         // find_entry() will call rebuild().
     163                 :          0 :         (void)find_entry(current_key);
     164                 :            :         // If the key was found, we're now pointing to it, otherwise we're
     165                 :            :         // pointing to the entry before.  Either way, we now want to move to
     166                 :            :         // the next key.
     167                 :            :     }
     168         [ +  + ]:      38093 :     if (tag_status == UNREAD) {
     169                 :         12 :         while (true) {
     170         [ +  + ]:       4478 :             if (! B->next(C, 0)) {
     171                 :         93 :                 is_positioned = false;
     172                 :         93 :                 break;
     173                 :            :             }
     174         [ +  + ]:       4385 :             if (Item_(C[0].p, C[0].c).component_of() == 1) {
     175                 :       4373 :                 is_positioned = true;
     176                 :       4373 :                 break;
     177                 :            :             }
     178                 :            :         }
     179                 :            :     }
     180                 :            : 
     181         [ +  + ]:      38093 :     if (!is_positioned) {
     182                 :        306 :         is_after_end = true;
     183                 :        306 :         RETURN(false);
     184                 :            :     }
     185                 :            : 
     186                 :      37787 :     get_key(&current_key);
     187                 :      37787 :     tag_status = UNREAD;
     188                 :            : 
     189                 :            :     LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
     190                 :      38093 :     RETURN(true);
     191                 :            : }
     192                 :            : 
     193                 :            : bool
     194                 :     166682 : FlintCursor::find_entry(const string &key)
     195                 :            : {
     196                 :            :     LOGCALL(DB, bool, "FlintCursor::find_entry", key);
     197         [ -  + ]:     166682 :     if (B->cursor_version != version) {
     198                 :          0 :         rebuild();
     199                 :            :     }
     200                 :            : 
     201                 :     166682 :     is_after_end = false;
     202                 :            : 
     203                 :            :     bool found;
     204                 :            : 
     205                 :     166682 :     is_positioned = true;
     206         [ +  + ]:     166682 :     if (key.size() > FLINT_BTREE_MAX_KEY_LEN) {
     207                 :            :         // Can't find key - too long to possibly be present, so find the
     208                 :            :         // truncated form but ignore "found".
     209                 :         30 :         B->form_key(key.substr(0, FLINT_BTREE_MAX_KEY_LEN));
     210                 :         30 :         (void)(B->find(C));
     211                 :         30 :         found = false;
     212                 :            :     } else {
     213                 :     166652 :         B->form_key(key);
     214                 :     166652 :         found = B->find(C);
     215                 :            :     }
     216                 :            : 
     217         [ +  + ]:     166682 :     if (!found) {
     218         [ -  + ]:      45696 :         if (C[0].c < DIR_START) {
     219                 :          0 :             C[0].c = DIR_START;
     220         [ #  # ]:          0 :             if (! B->prev(C, 0)) goto done;
     221                 :            :         }
     222         [ +  + ]:      45795 :         while (Item_(C[0].p, C[0].c).component_of() != 1) {
     223         [ -  + ]:         99 :             if (! B->prev(C, 0)) {
     224                 :          0 :                 is_positioned = false;
     225                 :          0 :                 throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
     226                 :            :             }
     227                 :            :         }
     228                 :            :     }
     229                 :            : done:
     230                 :            : 
     231         [ +  + ]:     166682 :     if (found)
     232                 :     120986 :         current_key = key;
     233                 :            :     else
     234                 :      45696 :         get_key(&current_key);
     235                 :     166682 :     tag_status = UNREAD;
     236                 :            : 
     237                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     238                 :     166682 :     RETURN(found);
     239                 :            : }
     240                 :            : 
     241                 :            : bool
     242                 :        500 : FlintCursor::find_entry_ge(const string &key)
     243                 :            : {
     244                 :            :     LOGCALL(DB, bool, "FlintCursor::find_entry_ge", key);
     245         [ +  + ]:        500 :     if (B->cursor_version != version) {
     246                 :         10 :         rebuild();
     247                 :            :     }
     248                 :            : 
     249                 :        500 :     is_after_end = false;
     250                 :            : 
     251                 :            :     bool found;
     252                 :            : 
     253                 :        500 :     is_positioned = true;
     254         [ -  + ]:        500 :     if (key.size() > FLINT_BTREE_MAX_KEY_LEN) {
     255                 :            :         // Can't find key - too long to possibly be present, so find the
     256                 :            :         // truncated form but ignore "found".
     257                 :          0 :         B->form_key(key.substr(0, FLINT_BTREE_MAX_KEY_LEN));
     258                 :          0 :         (void)(B->find(C));
     259                 :          0 :         found = false;
     260                 :            :     } else {
     261                 :        500 :         B->form_key(key);
     262                 :        500 :         found = B->find(C);
     263                 :            :     }
     264                 :            : 
     265         [ +  + ]:        497 :     if (found) {
     266                 :         36 :         current_key = key;
     267                 :            :     } else {
     268         [ +  + ]:        461 :         if (! B->next(C, 0)) {
     269                 :        216 :             is_after_end = true;
     270                 :        216 :             is_positioned = false;
     271                 :        216 :             RETURN(false);
     272                 :            :         }
     273                 :            :         Assert(Item_(C[0].p, C[0].c).component_of() == 1);
     274                 :        245 :         get_key(&current_key);
     275                 :            :     }
     276                 :        281 :     tag_status = UNREAD;
     277                 :            : 
     278                 :            :     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
     279                 :        497 :     RETURN(found);
     280                 :            : }
     281                 :            : 
     282                 :            : void
     283                 :      83736 : FlintCursor::get_key(string * key) const
     284                 :            : {
     285                 :            :     Assert(B->level <= level);
     286                 :            :     Assert(is_positioned);
     287                 :            : 
     288                 :      83736 :     (void)Item_(C[0].p, C[0].c).key().read(key);
     289                 :      83736 : }
     290                 :            : 
     291                 :            : bool
     292                 :     175405 : FlintCursor::read_tag(bool keep_compressed)
     293                 :            : {
     294                 :            :     LOGCALL(DB, bool, "FlintCursor::read_tag", keep_compressed);
     295         [ +  - ]:     175405 :     if (tag_status == UNREAD) {
     296                 :            :         Assert(B->level <= level);
     297                 :            :         Assert(is_positioned);
     298                 :            : 
     299         [ +  + ]:     175405 :         if (B->read_tag(C, &current_tag, keep_compressed)) {
     300                 :        113 :             tag_status = COMPRESSED;
     301                 :            :         } else {
     302                 :     175292 :             tag_status = UNCOMPRESSED;
     303                 :            :         }
     304                 :            : 
     305                 :            :         // We need to call B->next(...) after B->read_tag(...) so that the
     306                 :            :         // cursor ends up on the next key.
     307                 :     175405 :         is_positioned = B->next(C, 0);
     308                 :            : 
     309                 :            :         LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
     310                 :            :     }
     311                 :     175405 :     RETURN(tag_status == COMPRESSED);
     312                 :            : }
     313                 :            : 
     314                 :            : bool
     315                 :         38 : FlintCursor::del()
     316                 :            : {
     317                 :            :     Assert(!is_after_end);
     318                 :            : 
     319                 :         38 :     B->del(current_key);
     320                 :            : 
     321                 :            :     // If we're iterating an older revision of the tree, then the deletion
     322                 :            :     // happens in a new (uncommitted) revision and the cursor still sees
     323                 :            :     // the deleted key.  But if we're iterating the new uncommitted revision
     324                 :            :     // then the deleted key is no longer visible.  We need to handle both
     325                 :            :     // cases - either find_entry_ge() finds the deleted key or not.
     326         [ +  + ]:         38 :     if (!find_entry_ge(current_key)) return is_positioned;
     327                 :         38 :     return next();
     328                 :            : }

Generated by: LCOV version 1.8