chert_cursor.cc

Go to the documentation of this file.

/* chert_cursor.cc: Btree cursor implementation
 *
 * Copyright 1999,2000,2001 BrightStation PLC
 * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010,2012,2015 Olly Betts
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
 * USA
 */

#include <config.h>

#include "chert_cursor.h"

#include <cerrno>

#include <xapian/error.h>

#include "chert_table.h"
#include "debuglog.h"
#include "omassert.h"

#ifdef XAPIAN_DEBUG_LOG
static string
hex_display_encode(const string & input)
{
    const char * table = "0123456789abcdef";
    string result;
    for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
        unsigned char val = *i;
        result += "\\x";
        result += table[val / 16];
        result += table[val % 16];
    }

    return result;
}
#endif

#define DIR_START        11

ChertCursor::ChertCursor(const ChertTable *B_)
        : is_positioned(false),
          is_after_end(false),
          tag_status(UNREAD),
          B(B_),
          version(B_->cursor_version),
          level(B_->level)
{
    B->cursor_created_since_last_modification = true;
    C = new Cursor[level + 1];

    for (int j = 0; j < level; j++) {
        C[j].n = BLK_UNUSED;
        C[j].p = new uint8_t[B->block_size];
    }
    C[level].n = B->C[level].n;
    C[level].p = B->C[level].p;
}

void
ChertCursor::rebuild()
{
    int new_level = B->level;
    if (new_level <= level) {
        for (int i = 0; i < new_level; i++) {
            C[i].n = BLK_UNUSED;
        }
        for (int j = new_level; j < level; ++j) {
            delete [] C[j].p;
        }
    } else {
        Cursor * old_C = C;
        C = new Cursor[new_level + 1];
        for (int i = 0; i < level; i++) {
            C[i].p = old_C[i].p;
            C[i].n = BLK_UNUSED;
        }
        delete [] old_C;
        for (int j = level; j < new_level; j++) {
            C[j].p = new uint8_t[B->block_size];
            C[j].n = BLK_UNUSED;
        }
    }
    level = new_level;
    C[level].n = B->C[level].n;
    C[level].p = B->C[level].p;
    version = B->cursor_version;
    B->cursor_created_since_last_modification = true;
}

ChertCursor::~ChertCursor()
{
    // Use the value of level stored in the cursor rather than the
    // Btree, since the Btree might have been deleted already.
    for (int j = 0; j < level; j++) {
        delete [] C[j].p;
    }
    delete [] C;
}

bool
ChertCursor::prev()
{
    LOGCALL(DB, bool, "ChertCursor::prev", NO_ARGS);
    Assert(!is_after_end);
    if (B->cursor_version != version || !is_positioned) {
        // Either the cursor needs rebuilding (in which case find_entry() will
        // call rebuild() and then reposition the cursor), or we've read the
        // last key and tag, and we're now not positioned (in which case we
        // seek to the current key, and then it's as if we read the key but not
        // the tag).
        if (!find_entry(current_key)) {
            // Exact entry was no longer there after rebuild(), and we've
            // automatically ended up on the entry before it.
            RETURN(true);
        }
    } else if (tag_status != UNREAD) {
        while (true) {
            if (! B->prev(C, 0)) {
                is_positioned = false;
                RETURN(false);
            }
            if (Item(C[0].p, C[0].c).component_of() == 1) {
                break;
            }
        }
    }

    while (true) {
        if (! B->prev(C, 0)) {
            is_positioned = false;
            RETURN(false);
        }
        if (Item(C[0].p, C[0].c).component_of() == 1) {
            break;
        }
    }
    get_key(&current_key);
    tag_status = UNREAD;

    LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
    RETURN(true);
}

bool
ChertCursor::next()
{
    LOGCALL(DB, bool, "ChertCursor::next", NO_ARGS);
    Assert(!is_after_end);
    if (B->cursor_version != version) {
        // find_entry() will call rebuild().
        (void)find_entry(current_key);
        // If the key was found, we're now pointing to it, otherwise we're
        // pointing to the entry before.  Either way, we now want to move to
        // the next key.
    }
    if (tag_status == UNREAD) {
        while (true) {
            if (! B->next(C, 0)) {
                is_positioned = false;
                break;
            }
            if (Item(C[0].p, C[0].c).component_of() == 1) {
                is_positioned = true;
                break;
            }
        }
    }

    if (!is_positioned) {
        is_after_end = true;
        RETURN(false);
    }

    get_key(&current_key);
    tag_status = UNREAD;

    LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
    RETURN(true);
}

bool
ChertCursor::find_entry(const string &key)
{
    LOGCALL(DB, bool, "ChertCursor::find_entry", key);
    if (B->cursor_version != version) {
        rebuild();
    }

    is_after_end = false;

    bool found;

    is_positioned = true;
    if (key.size() > CHERT_BTREE_MAX_KEY_LEN) {
        // Can't find key - too long to possibly be present, so find the
        // truncated form but ignore "found".
        B->form_key(key.substr(0, CHERT_BTREE_MAX_KEY_LEN));
        (void)(B->find(C));
        found = false;
    } else {
        B->form_key(key);
        found = B->find(C);
    }

    if (!found) {
        if (C[0].c < DIR_START) {
            C[0].c = DIR_START;
            if (! B->prev(C, 0)) goto done;
        }
        while (Item(C[0].p, C[0].c).component_of() != 1) {
            if (! B->prev(C, 0)) {
                is_positioned = false;
                throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
            }
        }
    }
done:

    if (found)
        current_key = key;
    else
        get_key(&current_key);
    tag_status = UNREAD;

    LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
    RETURN(found);
}

bool
ChertCursor::find_entry_ge(const string &key)
{
    LOGCALL(DB, bool, "ChertCursor::find_entry_ge", key);
    if (B->cursor_version != version) {
        rebuild();
    }

    is_after_end = false;

    bool found;

    is_positioned = true;
    if (key.size() > CHERT_BTREE_MAX_KEY_LEN) {
        // Can't find key - too long to possibly be present, so find the
        // truncated form but ignore "found".
        B->form_key(key.substr(0, CHERT_BTREE_MAX_KEY_LEN));
        (void)(B->find(C));
        found = false;
    } else {
        B->form_key(key);
        found = B->find(C);
    }

    if (found) {
        current_key = key;
    } else {
        if (! B->next(C, 0)) {
            is_after_end = true;
            is_positioned = false;
            RETURN(false);
        }
        Assert(Item(C[0].p, C[0].c).component_of() == 1);
        get_key(&current_key);
    }
    tag_status = UNREAD;

    LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
    RETURN(found);
}

void
ChertCursor::get_key(string * key) const
{
    Assert(B->level <= level);
    Assert(is_positioned);

    (void)Item(C[0].p, C[0].c).key().read(key);
}

bool
ChertCursor::read_tag(bool keep_compressed)
{
    LOGCALL(DB, bool, "ChertCursor::read_tag", keep_compressed);
    if (tag_status == UNREAD) {
        Assert(B->level <= level);
        Assert(is_positioned);

        if (B->read_tag(C, &current_tag, keep_compressed)) {
            tag_status = COMPRESSED;
        } else {
            tag_status = UNCOMPRESSED;
        }

        // We need to call B->next(...) after B->read_tag(...) so that the
        // cursor ends up on the next key.
        is_positioned = B->next(C, 0);

        LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
    }
    RETURN(tag_status == COMPRESSED);
}

bool
MutableChertCursor::del()
{
    Assert(!is_after_end);

    // MutableChertCursor is only constructable from a non-const ChertTable*
    // but we store that in the const ChertTable* "B" member of the ChertCursor
    // class to avoid duplicating storage.  So we know it is safe to cast away
    // that const again here.
    (const_cast<ChertTable*>(B))->del(current_key);

    // If we're iterating an older revision of the tree, then the deletion
    // happens in a new (uncommitted) revision and the cursor still sees
    // the deleted key.  But if we're iterating the new uncommitted revision
    // then the deleted key is no longer visible.  We need to handle both
    // cases - either find_entry_ge() finds the deleted key or not.
    if (!find_entry_ge(current_key)) return is_positioned;
    return next();
}