foedus::storage::masstree::MasstreeCursor::Route Struct Reference

Represents one page in the current search path from layer0-root. More...

Detailed Description

Represents one page in the current search path from layer0-root.

Either it's interior or border, this object stores some kind of a marker to note up to where we read the page so far.

Definition at line 83 of file masstree_cursor.hpp.

#include <masstree_cursor.hpp>

Collaboration diagram for foedus::storage::masstree::MasstreeCursor::Route:

Public Types
enum	MovedPageSearchStatus { kNone = 0, kMovedPageSearchedNeither = 1, kMovedPageSearchedOne = 2, kMovedPageSearchedBoth = 3 }

Public Member Functions
SlotIndex	get_cur_original_index () const __attribute__((always_inline))
SlotIndex	get_original_index (SlotIndex index) const __attribute__((always_inline))
bool	is_valid_record () const __attribute__((always_inline))
bool	was_stably_moved () const
	In almost all places of the cursor code, we check is_moved() only on the stable version so that the cursor can consistently decide whether to follow foster-twins or not. More...
void	setup_order ()

Public Attributes
MasstreePage *	page_
PageVersionStatus	stable_
	version as of calculating order_. More...
SlotIndex	index_
	index in ordered keys. More...
SlotIndex	index_mini_
	only for interior. More...
SlotIndex	key_count_
	same as stable_.get_key_count() More...
SlotIndex	key_count_mini_
	only for interior. More...
bool	snapshot_
	whether page_ is a snapshot page More...
Layer	layer_
	Shorthand for page_->get_layer() More...
MovedPageSearchStatus	moved_page_search_status_
	only when stable_ indicates that this page is a moved page More...
KeySlice	latest_separator_
	Upto which separator we are done. More...
SlotIndex	order_ [kBorderPageMaxSlots]
	only for border. More...

Member Enumeration Documentation

enum foedus::storage::masstree::MasstreeCursor::Route::MovedPageSearchStatus

Enumerator
kNone	This means either was_stably_moved() is false or it's intermediate page, in which case we don't neeed to follow foster twins. If it's a border page whose was_stably_moved() returns true, the status might be one of the followings.
kMovedPageSearchedNeither
kMovedPageSearchedOne
kMovedPageSearchedBoth

Definition at line 84 of file masstree_cursor.hpp.

                               {
      kNone = 0,
      kMovedPageSearchedNeither = 1,
      kMovedPageSearchedOne = 2,
      kMovedPageSearchedBoth = 3,
    };

Member Function Documentation

SlotIndex foedus::storage::masstree::MasstreeCursor::Route::get_cur_original_index ( ) const

inline

Definition at line 147 of file masstree_cursor.hpp.

References index_.

                                                           {
      return order_[index_];
    }

SlotIndex foedus::storage::masstree::MasstreeCursor::Route::get_original_index ( SlotIndex  index ) const

inline

Definition at line 150 of file masstree_cursor.hpp.

                                                                      {
      return order_[index];
    }

bool foedus::storage::masstree::MasstreeCursor::Route::is_valid_record ( ) const

inline

Definition at line 153 of file masstree_cursor.hpp.

References key_count_.

Referenced by foedus::storage::masstree::MasstreeCursor::is_valid_record().

                                                  {
      return index_ < key_count_;
    }

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeCursor::Route::setup_order ( )

inline

Definition at line 564 of file masstree_cursor.cpp.

References ASSERT_ND, foedus::storage::masstree::MasstreePage::is_border(), key_count_, order_, and page_.

                                             {
  ASSERT_ND(page_->is_border());
  // sort entries in this page
  // we have already called prefetch_general(), which prefetches 4 cachelines (256 bytes).
  // as we are reading up to slices_[key_count - 1], we might want to prefetch more.
  MasstreeBorderPage* page = reinterpret_cast<MasstreeBorderPage*>(page_);
  for (SlotIndex i = 0; i < key_count_; ++i) {
    order_[i] = i;
  }

  if (page->is_consecutive_inserts()) {
    DVLOG(2) << "lucky, an already sorted border page.";
    return;
  }

  page->prefetch_additional_if_needed(key_count_);
  struct Sorter {
    explicit Sorter(const MasstreeBorderPage* target) : target_(target) {}
    bool operator() (SlotIndex left, SlotIndex right) {
      KeySlice left_slice = target_->get_slice(left);
      KeySlice right_slice = target_->get_slice(right);
      if (left_slice < right_slice) {
        return true;
      } else if (left_slice == right_slice) {
        return target_->get_remainder_length(left) < target_->get_remainder_length(right);
      } else {
        return false;
      }
    }
    const MasstreeBorderPage* target_;
  };

  // this sort order in page is correct even without evaluating the suffix.
  // however, to compare with our searching key, we need to consider suffix
  std::sort(order_, order_ + key_count_, Sorter(page));
}

Here is the call graph for this function:

bool foedus::storage::masstree::MasstreeCursor::Route::was_stably_moved ( ) const

inline

In almost all places of the cursor code, we check is_moved() only on the stable version so that the cursor can consistently decide whether to follow foster-twins or not.

So, we shouldn't have any "is_moved" in the file other than this.

Definition at line 161 of file masstree_cursor.hpp.

References foedus::storage::PageVersionStatus::is_moved().

{ return stable_.is_moved(); }

Here is the call graph for this function:

Member Data Documentation

SlotIndex foedus::storage::masstree::MasstreeCursor::Route::index_

index in ordered keys.

in interior, same.

Definition at line 113 of file masstree_cursor.hpp.

Referenced by get_cur_original_index().

SlotIndex foedus::storage::masstree::MasstreeCursor::Route::index_mini_

only for interior.

Definition at line 115 of file masstree_cursor.hpp.

SlotIndex foedus::storage::masstree::MasstreeCursor::Route::key_count_

same as stable_.get_key_count()

Note

Even in a border page, key_count_ might be zero. Such a case might happen right after no-record-split, split for a super-long key/value etc. We tolerate such a page in routes_, and just skip over it in next() etc.

Definition at line 122 of file masstree_cursor.hpp.

Referenced by is_valid_record(), and setup_order().

SlotIndex foedus::storage::masstree::MasstreeCursor::Route::key_count_mini_

only for interior.

Definition at line 124 of file masstree_cursor.hpp.

KeySlice foedus::storage::masstree::MasstreeCursor::Route::latest_separator_

Upto which separator we are done.

only for interior. If forward search, we followed a pointer before this separator. If backward search, we followed a pointer after this separator. This is updated whenever we follow a pointer from this interior page, and used when we have to re-find the separator. In Master-tree, a separator never disappears from the page, so we can surely find this.

Definition at line 142 of file masstree_cursor.hpp.

Layer foedus::storage::masstree::MasstreeCursor::Route::layer_

Shorthand for page_->get_layer()

Definition at line 129 of file masstree_cursor.hpp.

Referenced by foedus::storage::masstree::MasstreeCursor::copy_combined_key(), and foedus::storage::masstree::MasstreeCursor::copy_combined_key_part().

MovedPageSearchStatus foedus::storage::masstree::MasstreeCursor::Route::moved_page_search_status_

only when stable_ indicates that this page is a moved page

Definition at line 132 of file masstree_cursor.hpp.

SlotIndex foedus::storage::masstree::MasstreeCursor::Route::order_[kBorderPageMaxSlots]

only for border.

order_[0] is the index of smallest record, [1] second smallest...

Definition at line 145 of file masstree_cursor.hpp.

Referenced by setup_order().

MasstreePage* foedus::storage::masstree::MasstreeCursor::Route::page_

Definition at line 95 of file masstree_cursor.hpp.

Referenced by foedus::storage::masstree::MasstreeCursor::copy_combined_key(), foedus::storage::masstree::MasstreeCursor::copy_combined_key_part(), and setup_order().

bool foedus::storage::masstree::MasstreeCursor::Route::snapshot_

whether page_ is a snapshot page

Definition at line 127 of file masstree_cursor.hpp.

PageVersionStatus foedus::storage::masstree::MasstreeCursor::Route::stable_

version as of calculating order_.

We also guarantee that we retrieved key_count_ and key_count_mini_ as-of OR after this version.

Q: Why it could be "after"? A: When we find that an intermediate page now has more separators, we need to re-search (rebase) in the page. In that case, the only thing we care is key_count_ and key_count_mini_. Version number of intermediate pages has no effect .. except is_moved(). But, even in that case, intermediate page has an invariant that we can just search in the old page. Thus, in either case, we don't update stable_ but only re-retrieve key_count_ and key_count_mini_.

Invariant

Once constructed this Route object, stable_ is immutable. We won't update it.

Definition at line 111 of file masstree_cursor.hpp.

---

The documentation for this struct was generated from the following files:

• /home/shino/foedus_code/foedus-core/include/foedus/storage/masstree/masstree_cursor.hpp
• /home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_cursor.cpp