--- /dev/null
+/* 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;
+ }
+ static String unparse_ikey(ikey_type ikey) {
+ key<ikey_type> k(ikey);
+ return k.unparse();
+ }
+
+ // 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
projects / c11concurrency-benchmarks.git / blobdiff