xapian-core/backends/glass/glass_cursor.cc

   1 /* glass_cursor.cc: Btree cursor implementation
   2  *
   3  * Copyright 1999,2000,2001 BrightStation PLC
   4  * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010,2012,2013,2015,2016 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 "glass_cursor.h"
  25
  26 #include "safeerrno.h"
  27
  28 #include <xapian/error.h>
  29
  30 #include "glass_table.h"
  31 #include "debuglog.h"
  32 #include "omassert.h"
  33
  34 using namespace Glass;
  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 GlassCursor::GlassCursor(const GlassTable *B_, const Glass::Cursor * C_)
  56         : is_positioned(false),
  57           is_after_end(false),
  58           tag_status(UNREAD),
  59           B(B_),
  60           version(B_->cursor_version),
  61           level(B_->level)
  62 {
  63     B->cursor_created_since_last_modification = true;
  64     C = new Glass::Cursor[level + 1];
  65     if (!C_) C_ = B->C;
  66     for (int j = 0; j <= level; j++) {
  67         C[j].clone(C_[j]);
  68     }
  69 }
  70
  71 void
  72 GlassCursor::rebuild()
  73 {
  74     int new_level = B->level;
  75     if (new_level <= level) {
  76         for (int j = new_level; j <= level; ++j) {
  77             C[j].destroy();
  78         }
  79     } else {
  80         Cursor * old_C = C;
  81         C = new Cursor[new_level + 1];
  82         for (int i = 0; i < level; i++) {
  83             C[i].swap(old_C[i]);
  84         }
  85         delete [] old_C;
  86         for (int j = level; j < new_level; j++) {
  87             C[j].init(B->block_size);
  88         }
  89     }
  90     level = new_level;
  91     C[level].clone(B->C[level]);
  92     version = B->cursor_version;
  93     B->cursor_created_since_last_modification = true;
  94 }
  95
  96 GlassCursor::~GlassCursor()
  97 {
  98     // We must not use B here, as it may have already been destroyed.
  99     delete [] C;
 100 }
 101
 102 bool
 103 GlassCursor::next()
 104 {
 105     LOGCALL(DB, bool, "GlassCursor::next", NO_ARGS);
 106     Assert(!is_after_end);
 107     if (B->cursor_version != version) {
 108         // find_entry() will call rebuild().
 109         (void)find_entry(current_key);
 110         // If the key was found, we're now pointing to it, otherwise we're
 111         // pointing to the entry before.  Either way, we now want to move to
 112         // the next key.
 113     }
 114     if (tag_status == UNREAD || tag_status == UNREAD_ON_LAST_CHUNK) {
 115         while (true) {
 116             if (! B->next(C, 0)) {
 117                 is_positioned = false;
 118                 break;
 119             }
 120             if (tag_status == UNREAD_ON_LAST_CHUNK ||
 121                 LeafItem(C[0].get_p(), C[0].c).first_component()) {
 122                 is_positioned = true;
 123                 break;
 124             }
 125         }
 126     }
 127
 128     if (!is_positioned) {
 129         is_after_end = true;
 130         RETURN(false);
 131     }
 132
 133     get_key(&current_key);
 134     tag_status = UNREAD;
 135
 136     LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
 137     RETURN(true);
 138 }
 139
 140 bool
 141 GlassCursor::find_entry(const string &key)
 142 {
 143     LOGCALL(DB, bool, "GlassCursor::find_entry", key);
 144     if (B->cursor_version != version) {
 145         rebuild();
 146     }
 147
 148     is_after_end = false;
 149
 150     bool found;
 151
 152     is_positioned = true;
 153     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) {
 154         // Can't find key - too long to possibly be present, so find the
 155         // truncated form but ignore "found".
 156         B->form_key(key.substr(0, GLASS_BTREE_MAX_KEY_LEN));
 157         (void)(B->find(C));
 158         found = false;
 159     } else {
 160         B->form_key(key);
 161         found = B->find(C);
 162     }
 163
 164     if (found) {
 165         tag_status = UNREAD;
 166         current_key = key;
 167     } else {
 168         // Be lazy about stepping back to the first chunk, as we may never be
 169         // asked to read the tag.
 170         tag_status = UNREAD_ON_LAST_CHUNK;
 171         if (C[0].c < DIR_START) {
 172             // It would be nice to be lazy about this too, but we need to
 173             // be on an actual entry in order to read the key.
 174             C[0].c = DIR_START;
 175             if (! B->prev(C, 0)) {
 176                 tag_status = UNREAD;
 177             }
 178         }
 179         get_key(&current_key);
 180     }
 181
 182     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
 183     RETURN(found);
 184 }
 185
 186 void
 187 GlassCursor::find_entry_lt(const string &key)
 188 {
 189     LOGCALL_VOID(DB, "GlassCursor::find_entry_lt", key);
 190     if (!find_entry(key)) {
 191         // The entry wasn't found, so find_entry() left us on the entry before
 192         // the one we asked for and we're done.
 193         return;
 194     }
 195
 196     Assert(!is_after_end);
 197     Assert(is_positioned);
 198
 199     if (! B->prev(C, 0)) {
 200         is_positioned = false;
 201         return;
 202     }
 203     tag_status = UNREAD_ON_LAST_CHUNK;
 204     get_key(&current_key);
 205
 206     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
 207 }
 208
 209 bool
 210 GlassCursor::find_exact(const string &key)
 211 {
 212     LOGCALL(DB, bool, "GlassCursor::find_exact", key);
 213     is_after_end = false;
 214     is_positioned = false;
 215     if (rare(key.size() > GLASS_BTREE_MAX_KEY_LEN)) {
 216         // There can't be a match
 217         RETURN(false);
 218     }
 219
 220     if (B->cursor_version != version) {
 221         rebuild();
 222     }
 223
 224     B->form_key(key);
 225     if (!B->find(C)) {
 226         RETURN(false);
 227     }
 228     current_key = key;
 229     B->read_tag(C, &current_tag, false);
 230
 231     RETURN(true);
 232 }
 233
 234 bool
 235 GlassCursor::find_entry_ge(const string &key)
 236 {
 237     LOGCALL(DB, bool, "GlassCursor::find_entry_ge", key);
 238     if (B->cursor_version != version) {
 239         rebuild();
 240     }
 241
 242     is_after_end = false;
 243
 244     bool found;
 245
 246     is_positioned = true;
 247     if (key.size() > GLASS_BTREE_MAX_KEY_LEN) {
 248         // Can't find key - too long to possibly be present, so find the
 249         // truncated form but ignore "found".
 250         B->form_key(key.substr(0, GLASS_BTREE_MAX_KEY_LEN));
 251         (void)(B->find(C));
 252         found = false;
 253     } else {
 254         B->form_key(key);
 255         found = B->find(C);
 256     }
 257
 258     if (found) {
 259         current_key = key;
 260     } else {
 261         if (! B->next(C, 0)) {
 262             is_after_end = true;
 263             is_positioned = false;
 264             RETURN(false);
 265         }
 266         Assert(LeafItem(C[0].get_p(), C[0].c).first_component());
 267         get_key(&current_key);
 268     }
 269     tag_status = UNREAD;
 270
 271     LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
 272     RETURN(found);
 273 }
 274
 275 void
 276 GlassCursor::get_key(string * key) const
 277 {
 278     Assert(B->level <= level);
 279     Assert(is_positioned);
 280
 281     (void)LeafItem(C[0].get_p(), C[0].c).key().read(key);
 282 }
 283
 284 bool
 285 GlassCursor::read_tag(bool keep_compressed)
 286 {
 287     LOGCALL(DB, bool, "GlassCursor::read_tag", keep_compressed);
 288     if (tag_status == UNREAD_ON_LAST_CHUNK) {
 289         // Back up to first chunk of this tag.
 290         while (!LeafItem(C[0].get_p(), C[0].c).first_component()) {
 291             if (! B->prev(C, 0)) {
 292                 is_positioned = false;
 293                 throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
 294             }
 295         }
 296         tag_status = UNREAD;
 297     }
 298     if (tag_status == UNREAD) {
 299         Assert(B->level <= level);
 300         Assert(is_positioned);
 301
 302         if (B->read_tag(C, &current_tag, keep_compressed)) {
 303             tag_status = COMPRESSED;
 304         } else {
 305             tag_status = UNCOMPRESSED;
 306         }
 307
 308         // We need to call B->next(...) after B->read_tag(...) so that the
 309         // cursor ends up on the next key.
 310         is_positioned = B->next(C, 0);
 311
 312         LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
 313     }
 314     RETURN(tag_status == COMPRESSED);
 315 }
 316
 317 bool
 318 MutableGlassCursor::del()
 319 {
 320     Assert(!is_after_end);
 321
 322     // MutableGlassCursor is only constructable from a non-const GlassTable*
 323     // but we store that in the const GlassTable* "B" member of the GlassCursor
 324     // class to avoid duplicating storage.  So we know it is safe to cast away
 325     // that const again here.
 326     (const_cast<GlassTable*>(B))->del(current_key);
 327
 328     // If we're iterating an older revision of the tree, then the deletion
 329     // happens in a new (uncommitted) revision and the cursor still sees
 330     // the deleted key.  But if we're iterating the new uncommitted revision
 331     // then the deleted key is no longer visible.  We need to handle both
 332     // cases - either find_entry_ge() finds the deleted key or not.
 333     if (!find_entry_ge(current_key)) return is_positioned;
 334     return next();
 335 }