silo/masstree/masstree_key.hh

   1 /* Masstree
   2  * Eddie Kohler, Yandong Mao, Robert Morris
   3  * Copyright (c) 2012-2014 President and Fellows of Harvard College
   4  * Copyright (c) 2012-2014 Massachusetts Institute of Technology
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the "Software"),
   8  * to deal in the Software without restriction, subject to the conditions
   9  * listed in the Masstree LICENSE file. These conditions include: you must
  10  * preserve this copyright notice, and you cannot mention the copyright
  11  * holders in advertising related to the Software without their permission.
  12  * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
  13  * notice is a summary of the Masstree LICENSE file; the license in that file
  14  * is legally binding.
  15  */
  16 #ifndef MASSTREE_KEY_HH
  17 #define MASSTREE_KEY_HH
  18 #include "masstree.hh"
  19 #include "string_slice.hh"
  20
  21 namespace Masstree {
  22
  23 /** @brief Strings used as Masstree keys.
  24
  25     Masstree key strings are divided into parts: an initial slice, called
  26     the <em>ikey</em>, and a suffix. The ikey is stored as a byte-swapped
  27     integer, which is faster to compare than a string.
  28
  29     Keys can be <em>shifted</em> by the shift() method. <code>k.shift()</code>
  30     is like <code>k = key(k.suffix())</code>: the key is reconstructed from
  31     the original key's suffix. This corresponds to descending a layer in
  32     Masstree. However, <code>k.shift()</code> is faster than the assignment,
  33     and its effects can be undone by the <code>k.unshift_all()</code>
  34     method. */
  35 template <typename I>
  36 class key {
  37   public:
  38     static constexpr int nikey = 1;
  39     /** @brief Type of ikeys. */
  40     typedef I ikey_type;
  41     /** @brief Size of ikeys in bytes. */
  42     static constexpr int ikey_size = sizeof(ikey_type);
  43
  44     /** @brief Construct an uninitialized key. */
  45     key() {
  46     }
  47     /** @brief Construct a key for string @a s. */
  48     key(Str s)
  49         : ikey0_(string_slice<ikey_type>::make_comparable(s.s, s.len)),
  50           len_(s.len), s_(s.s), first_(s.s) {
  51     }
  52     /** @brief Construct a key for string @a s with length @a len.
  53         @pre @a len >= 0 */
  54     key(const char* s, int len)
  55         : ikey0_(string_slice<ikey_type>::make_comparable(s, len)),
  56           len_(len), s_(s), first_(s) {
  57     }
  58     /** @brief Construct a key for ikey @a ikey.
  59
  60         Any trailing zero bytes in @a ikey are not counted towards the key's
  61         length. */
  62     explicit key(ikey_type ikey)
  63         : ikey0_(ikey),
  64           len_(ikey ? ikey_size - ctz(ikey) / 8 : 0), s_(0), first_(0) {
  65     }
  66     /** @brief Construct a key for ikey @a ikey with length @a len.
  67         @pre @a len >= 0
  68         @post length() >= 0 && length() <= ikey_size */
  69     key(ikey_type ikey, int len)
  70         : ikey0_(ikey),
  71           len_(std::min(len, ikey_size)), s_(0), first_(0) {
  72     }
  73     /** @brief Construct a key with ikey @a ikey and suffix @a suf. */
  74     key(ikey_type ikey, Str suf)
  75         : ikey0_(ikey),
  76           len_(ikey_size + suf.len), s_(suf.s - ikey_size), first_(s_) {
  77     }
  78
  79     /** @brief Test if this key is empty (holds the empty string). */
  80     bool empty() const {
  81         return ikey0_ == 0 && len_ == 0;
  82     }
  83     /** @brief Return the ikey. */
  84     ikey_type ikey() const {
  85         return ikey0_;
  86     }
  87     /** @brief Return the key's length. */
  88     int length() const {
  89         return len_;
  90     }
  91     /** @brief Test whether this key has a suffix (length() > ikey_size). */
  92     bool has_suffix() const {
  93         return len_ > ikey_size;
  94     }
  95     /** @brief Return this key's suffix.
  96         @pre has_suffix() */
  97     Str suffix() const {
  98         return Str(s_ + ikey_size, len_ - ikey_size);
  99     }
 100     /** @brief Return the length of this key's suffix.
 101         @pre has_suffix() */
 102     int suffix_length() const {
 103         return len_ - ikey_size;
 104     }
 105
 106     /** @brief Shift this key forward to model the current key's suffix.
 107         @pre has_suffix() */
 108     void shift() {
 109         s_ += ikey_size;
 110         len_ -= ikey_size;
 111         ikey0_ = string_slice<ikey_type>::make_comparable_sloppy(s_, len_);
 112     }
 113     /** @brief Shift this key forward to model the current key's suffix.
 114         @pre has_suffix() */
 115     void shift_by(int delta) {
 116         s_ += delta;
 117         len_ -= delta;
 118         ikey0_ = string_slice<ikey_type>::make_comparable_sloppy(s_, len_);
 119     }
 120     /** @brief Test whether this key has been shifted by shift(). */
 121     bool is_shifted() const {
 122         return first_ != s_;
 123     }
 124     /** @brief Undo all previous shift() calls. */
 125     void unshift_all() {
 126         if (s_ != first_) {
 127             len_ += s_ - first_;
 128             s_ = first_;
 129             ikey0_ = string_slice<ikey_type>::make_comparable(s_, len_);
 130         }
 131     }
 132
 133     int compare(ikey_type ikey, int keylenx) const {
 134         int cmp = ::compare(this->ikey(), ikey);
 135         if (cmp == 0) {
 136             int al = this->length();
 137             if (al > ikey_size)
 138                 cmp = keylenx <= ikey_size;
 139             else
 140                 cmp = al - keylenx;
 141         }
 142         return cmp;
 143     }
 144     int compare(const key<I>& x) const {
 145         return compare(x.ikey(), x.length());
 146     }
 147
 148     int unparse(char* data, int datalen) const {
 149         int cplen = std::min(len_, datalen);
 150         string_slice<ikey_type>::unparse_comparable(data, cplen, ikey0_, ikey_size);
 151         if (cplen > ikey_size)
 152             memcpy(data + ikey_size, s_ + ikey_size, cplen - ikey_size);
 153         return cplen;
 154     }
 155     String unparse() const {
 156         String s = String::make_uninitialized(len_);
 157         unparse(s.mutable_data(), s.length());
 158         return s;
 159     }
 160     int unparse_printable(char* data, int datalen) const {
 161         String s = unparse().printable();
 162         int cplen = std::min(s.length(), datalen);
 163         memcpy(data, s.data(), cplen);
 164         return cplen;
 165     }
 166     static String unparse_ikey(ikey_type ikey) {
 167         key<ikey_type> k(ikey);
 168         return k.unparse();
 169     }
 170
 171     // used during scan
 172     Str prefix_string() const {
 173         return Str(first_, s_);
 174     }
 175     int prefix_length() const {
 176         return s_ - first_;
 177     }
 178     Str full_string() const {
 179         return Str(first_, s_ + len_);
 180     }
 181     operator Str() const {
 182         return full_string();
 183     }
 184     bool increment() {
 185         // Return true iff wrapped.
 186         if (has_suffix()) {
 187             ++ikey0_;
 188             len_ = 1;
 189             return unlikely(!ikey0_);
 190         } else {
 191             ++len_;
 192             return false;
 193         }
 194     }
 195     void assign_store_ikey(ikey_type ikey) {
 196         ikey0_ = ikey;
 197         *reinterpret_cast<ikey_type*>(const_cast<char*>(s_)) = host_to_net_order(ikey);
 198     }
 199     int assign_store_suffix(Str s) {
 200         memcpy(const_cast<char*>(s_ + ikey_size), s.s, s.len);
 201         return ikey_size + s.len;
 202     }
 203     void assign_store_length(int len) {
 204         len_ = len;
 205     }
 206     void unshift() {
 207         masstree_precondition(is_shifted());
 208         s_ -= ikey_size;
 209         ikey0_ = string_slice<ikey_type>::make_comparable_sloppy(s_, ikey_size);
 210         len_ = ikey_size + 1;
 211     }
 212     void shift_clear() {
 213         ikey0_ = 0;
 214         len_ = 0;
 215         s_ += ikey_size;
 216     }
 217     void shift_clear_reverse() {
 218         ikey0_ = ~ikey_type(0);
 219         len_ = ikey_size + 1;
 220         s_ += ikey_size;
 221     }
 222
 223   private:
 224     ikey_type ikey0_;
 225     int len_;
 226     const char* s_;
 227     const char* first_;
 228 };
 229
 230 template <typename I> constexpr int key<I>::ikey_size;
 231
 232 } // namespace Masstree
 233
 234 template <typename I>
 235 inline std::ostream& operator<<(std::ostream& stream,
 236                                 const Masstree::key<I>& x) {
 237     return stream << x.unparse();
 238 }
 239
 240 #endif