masstree_key.hh

/* Masstree
 * Eddie Kohler, Yandong Mao, Robert Morris
 * Copyright (c) 2012-2014 President and Fellows of Harvard College
 * Copyright (c) 2012-2014 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Masstree LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Masstree LICENSE file; the license in that file
 * is legally binding.
 */
#ifndef MASSTREE_KEY_HH
#define MASSTREE_KEY_HH
#include "masstree.hh"
#include "string_slice.hh"

namespace Masstree {

/** @brief Strings used as Masstree keys.

    Masstree key strings are divided into parts: an initial slice, called
    the <em>ikey</em>, and a suffix. The ikey is stored as a byte-swapped
    integer, which is faster to compare than a string.

    Keys can be <em>shifted</em> by the shift() method. <code>k.shift()</code>
    is like <code>k = key(k.suffix())</code>: the key is reconstructed from
    the original key's suffix. This corresponds to descending a layer in
    Masstree. However, <code>k.shift()</code> is faster than the assignment,
    and its effects can be undone by the <code>k.unshift_all()</code>
    method. */
template <typename I>
class key {
  public:
    static constexpr int nikey = 1;
    /** @brief Type of ikeys. */
    typedef I ikey_type;
    /** @brief Size of ikeys in bytes. */
    static constexpr int ikey_size = sizeof(ikey_type);

    /** @brief Construct an uninitialized key. */
    key() {
    }
    /** @brief Construct a key for string @a s. */
    key(Str s)
        : ikey0_(string_slice<ikey_type>::make_comparable(s.s, s.len)),
          len_(s.len), s_(s.s), first_(s.s) {
    }
    /** @brief Construct a key for string @a s with length @a len.
        @pre @a len >= 0 */
    key(const char* s, int len)
        : ikey0_(string_slice<ikey_type>::make_comparable(s, len)),
          len_(len), s_(s), first_(s) {
    }
    /** @brief Construct a key for ikey @a ikey.

        Any trailing zero bytes in @a ikey are not counted towards the key's
        length. */
    explicit key(ikey_type ikey)
        : ikey0_(ikey),
          len_(ikey ? ikey_size - ctz(ikey) / 8 : 0), s_(0), first_(0) {
    }
    /** @brief Construct a key for ikey @a ikey with length @a len.
        @pre @a len >= 0
        @post length() >= 0 && length() <= ikey_size */
    key(ikey_type ikey, int len)
        : ikey0_(ikey),
          len_(std::min(len, ikey_size)), s_(0), first_(0) {
    }
    /** @brief Construct a key with ikey @a ikey and suffix @a suf. */
    key(ikey_type ikey, Str suf)
        : ikey0_(ikey),
          len_(ikey_size + suf.len), s_(suf.s - ikey_size), first_(s_) {
    }

    /** @brief Test if this key is empty (holds the empty string). */
    bool empty() const {
        return ikey0_ == 0 && len_ == 0;
    }
    /** @brief Return the ikey. */
    ikey_type ikey() const {
        return ikey0_;
    }
    /** @brief Return the key's length. */
    int length() const {
        return len_;
    }
    /** @brief Test whether this key has a suffix (length() > ikey_size). */
    bool has_suffix() const {
        return len_ > ikey_size;
    }
    /** @brief Return this key's suffix.
        @pre has_suffix() */
    Str suffix() const {
        return Str(s_ + ikey_size, len_ - ikey_size);
    }
    /** @brief Return the length of this key's suffix.
        @pre has_suffix() */
    int suffix_length() const {
        return len_ - ikey_size;
    }

    /** @brief Shift this key forward to model the current key's suffix.
        @pre has_suffix() */
    void shift() {
        s_ += ikey_size;
        len_ -= ikey_size;
        ikey0_ = string_slice<ikey_type>::make_comparable_sloppy(s_, len_);
    }
    /** @brief Shift this key forward to model the current key's suffix.
        @pre has_suffix() */
    void shift_by(int delta) {
        s_ += delta;
        len_ -= delta;
        ikey0_ = string_slice<ikey_type>::make_comparable_sloppy(s_, len_);
    }
    /** @brief Test whether this key has been shifted by shift(). */
    bool is_shifted() const {
        return first_ != s_;
    }
    /** @brief Undo all previous shift() calls. */
    void unshift_all() {
        if (s_ != first_) {
            len_ += s_ - first_;
            s_ = first_;
            ikey0_ = string_slice<ikey_type>::make_comparable(s_, len_);
        }
    }

    int compare(ikey_type ikey, int keylenx) const {
        int cmp = ::compare(this->ikey(), ikey);
        if (cmp == 0) {
            int al = this->length();
            if (al > ikey_size)
                cmp = keylenx <= ikey_size;
            else
                cmp = al - keylenx;
        }
        return cmp;
    }
    int compare(const key<I>& x) const {
        return compare(x.ikey(), x.length());
    }

    int unparse(char* data, int datalen) const {
        int cplen = std::min(len_, datalen);
        string_slice<ikey_type>::unparse_comparable(data, cplen, ikey0_, ikey_size);
        if (cplen > ikey_size)
            memcpy(data + ikey_size, s_ + ikey_size, cplen - ikey_size);
        return cplen;
    }
    String unparse() const {
        String s = String::make_uninitialized(len_);
        unparse(s.mutable_data(), s.length());
        return s;
    }
    int unparse_printable(char* data, int datalen) const {
        String s = unparse_printable();
        int cplen = std::min(s.length(), datalen);
        memcpy(data, s.data(), cplen);
        return cplen;
    }
    String unparse_printable() const {
        return unparse().printable();
    }
    static String unparse_ikey(ikey_type ikey) {
        key<ikey_type> k(ikey);
        return k.unparse();
    }
    static String unparse_printable_ikey(ikey_type ikey) {
        key<ikey_type> k(ikey);
        return k.unparse_printable();
    }

    // used during scan
    Str prefix_string() const {
        return Str(first_, s_);
    }
    int prefix_length() const {
        return s_ - first_;
    }
    Str full_string() const {
        return Str(first_, s_ + len_);
    }
    operator Str() const {
        return full_string();
    }
    bool increment() {
        // Return true iff wrapped.
        if (has_suffix()) {
            ++ikey0_;
            len_ = 1;
            return unlikely(!ikey0_);
        } else {
            ++len_;
            return false;
        }
    }
    void assign_store_ikey(ikey_type ikey) {
        ikey0_ = ikey;
        *reinterpret_cast<ikey_type*>(const_cast<char*>(s_)) = host_to_net_order(ikey);
    }
    int assign_store_suffix(Str s) {
        memcpy(const_cast<char*>(s_ + ikey_size), s.s, s.len);
        return ikey_size + s.len;
    }
    void assign_store_length(int len) {
        len_ = len;
    }
    void unshift() {
        masstree_precondition(is_shifted());
        s_ -= ikey_size;
        ikey0_ = string_slice<ikey_type>::make_comparable_sloppy(s_, ikey_size);
        len_ = ikey_size + 1;
    }
    void shift_clear() {
        ikey0_ = 0;
        len_ = 0;
        s_ += ikey_size;
    }
    void shift_clear_reverse() {
        ikey0_ = ~ikey_type(0);
        len_ = ikey_size + 1;
        s_ += ikey_size;
    }

  private:
    ikey_type ikey0_;
    int len_;
    const char* s_;
    const char* first_;
};

template <typename I> constexpr int key<I>::ikey_size;

} // namespace Masstree

template <typename I>
inline std::ostream& operator<<(std::ostream& stream,
                                const Masstree::key<I>& x) {
    return stream << x.unparse();
}

#endif