foedus::storage::masstree::MasstreeComposeContext::PathLevel Struct Reference

One level in the path. More...

Detailed Description

One level in the path.

Each level consists of one or more pages with contiguous key ranges. Initially, head==tail. Whenever tail becomes full, it adds a new page which becomes the new tail.

Note

We move records in the original page when they are either

• Smaller, equal to, or containing (already next-layer pointer) the current key
• Will create a next layer with the current key The second condition means that, even if the original record is larger than the current key, we move it and trigger next layer creation. The reason behind this is that we don't want to cause next layer creation when the deeper levels are already closed. However, this approach instead violates "always append" policy. To work it around, if the record was copied because of the second condition, we move the record to a dummy original page in next layer, rather than the initial record. By doing so, we still keep the always-append policy as well as guarantee that deeper levels never receive records from upper levels.

Definition at line 194 of file masstree_composer_impl.hpp.

#include <masstree_composer_impl.hpp>

Public Member Functions
bool	has_next_original () const
void	set_no_more_next_original ()
bool	contains_slice (KeySlice slice) const
bool	contains_key (const char *key, KeyLength key_length) const
bool	needs_to_consume_original (KeySlice slice, KeyLength key_length) const

Public Attributes
memory::PagePoolOffset	head_
	Offset in page_base_. More...
memory::PagePoolOffset	tail_
	Offset in page_base_. More...
uint16_t	layer_
	B-tri layer of this level. More...
SlotIndex	next_original_
	If level is based on an existing snapshot page, the next entry (pointer or record) in the original page to copy. More...
SlotIndex	next_original_mini_
	for intermediate page More...
KeyLength	next_original_remainder_
	for border page. More...
uint32_t	page_count_
	number of pages in this level including head/tail, without original page (so, initial=1). More...
uint32_t	filler_
KeySlice	low_fence_
	same as low_fence of head More...
KeySlice	high_fence_
	same as high_fence of tail More...
KeySlice	next_original_slice_
	Slice of next entry. More...

Friends
std::ostream &	operator<< (std::ostream &o, const PathLevel &v)

Member Function Documentation

bool foedus::storage::masstree::MasstreeComposeContext::PathLevel::contains_key ( const char *  key, KeyLength  key_length  ) const

inline

Definition at line 236 of file masstree_composer_impl.hpp.

References ASSERT_ND, contains_slice(), foedus::storage::masstree::is_key_aligned_and_zero_padded(), foedus::storage::masstree::kSliceLen, and foedus::storage::masstree::normalize_be_bytes_full_aligned().

                                                                   {
      ASSERT_ND(is_key_aligned_and_zero_padded(key, key_length));
      KeySlice slice = normalize_be_bytes_full_aligned(key + layer_ * kSliceLen);
      return contains_slice(slice);
    }

Here is the call graph for this function:

bool foedus::storage::masstree::MasstreeComposeContext::PathLevel::contains_slice ( KeySlice  slice ) const

inline

Definition at line 232 of file masstree_composer_impl.hpp.

References ASSERT_ND, high_fence_, and foedus::storage::masstree::kSupremumSlice.

Referenced by contains_key().

                                              {
      ASSERT_ND(low_fence_ <= slice);  // as logs are sorted, this must not happen
      return high_fence_ == kSupremumSlice || slice < high_fence_;  // careful on supremum case
    }

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeComposeContext::PathLevel::has_next_original ( ) const

inline

Definition at line 225 of file masstree_composer_impl.hpp.

Referenced by needs_to_consume_original().

{ return next_original_ != 0xFFFFU; }

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeComposeContext::PathLevel::needs_to_consume_original ( KeySlice  slice, KeyLength  key_length  ) const

inline

Definition at line 241 of file masstree_composer_impl.hpp.

References has_next_original(), and foedus::storage::masstree::kSliceLen.

                                                                               {
      return has_next_original()
        && (
          next_original_slice_ < slice
          || (next_original_slice_ == slice
              && next_original_remainder_ > kSliceLen
              && key_length > (layer_ + 1U) * kSliceLen));
    }

Here is the call graph for this function:

void foedus::storage::masstree::MasstreeComposeContext::PathLevel::set_no_more_next_original ( )

inline

Definition at line 226 of file masstree_composer_impl.hpp.

References foedus::storage::masstree::kInitiallyNextLayer, and foedus::storage::masstree::kSupremumSlice.

                                     {
      next_original_ = 0xFFFFU;
      next_original_mini_ = 0xFFFFU;
      next_original_remainder_ = kInitiallyNextLayer;
      next_original_slice_ = kSupremumSlice;
    }

Friends And Related Function Documentation

std::ostream& operator<< ( std::ostream &  o, const PathLevel &  v  )

friend

Definition at line 2851 of file masstree_composer_impl.cpp.

                                                                                {
  o << "<PathLevel>"
    << "<layer_>" << static_cast<int>(v.layer_) << "</layer_>"
    << "<next_original_>" << static_cast<int>(v.next_original_) << "</next_original_>"
    << "<next_original_mini>" << static_cast<int>(v.next_original_mini_) << "</next_original_mini>"
    << "<head>" << v.head_ << "</head>"
    << "<tail_>" << v.tail_ << "</tail_>"
    << "<page_count_>" << v.page_count_ << "</page_count_>"
    << "<low_fence_>" << assorted::Hex(v.low_fence_, 16) << "</low_fence_>"
    << "<high_fence_>" << assorted::Hex(v.high_fence_, 16) << "</high_fence_>"
    << "<next_original_slice_>"
      << assorted::Hex(v.next_original_slice_, 16) << "</next_original_slice_>"
    << "</PathLevel>";
  return o;
}

Member Data Documentation

uint32_t foedus::storage::masstree::MasstreeComposeContext::PathLevel::filler_

Definition at line 213 of file masstree_composer_impl.hpp.

memory::PagePoolOffset foedus::storage::masstree::MasstreeComposeContext::PathLevel::head_

Offset in page_base_.

Definition at line 196 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

KeySlice foedus::storage::masstree::MasstreeComposeContext::PathLevel::high_fence_

same as high_fence of tail

Definition at line 217 of file masstree_composer_impl.hpp.

Referenced by contains_slice(), and foedus::storage::masstree::operator<<().

uint16_t foedus::storage::masstree::MasstreeComposeContext::PathLevel::layer_

B-tri layer of this level.

Definition at line 200 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

KeySlice foedus::storage::masstree::MasstreeComposeContext::PathLevel::low_fence_

same as low_fence of head

Definition at line 215 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

SlotIndex foedus::storage::masstree::MasstreeComposeContext::PathLevel::next_original_

If level is based on an existing snapshot page, the next entry (pointer or record) in the original page to copy.

Remember, we copy the entries when it is same as or less than the next key so that we always append. 0xFFFF means no more entry to copy.

Definition at line 206 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

SlotIndex foedus::storage::masstree::MasstreeComposeContext::PathLevel::next_original_mini_

for intermediate page

Definition at line 208 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

KeyLength foedus::storage::masstree::MasstreeComposeContext::PathLevel::next_original_remainder_

for border page.

The record's remainder length.

Definition at line 210 of file masstree_composer_impl.hpp.

KeySlice foedus::storage::masstree::MasstreeComposeContext::PathLevel::next_original_slice_

Slice of next entry.

Depending on the key length, this might be not enough to determine the current key is smaller than or larger than that, in that case we have to go check the entry each time (but hopefully that's rare).

Definition at line 223 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

uint32_t foedus::storage::masstree::MasstreeComposeContext::PathLevel::page_count_

number of pages in this level including head/tail, without original page (so, initial=1).

Definition at line 212 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

memory::PagePoolOffset foedus::storage::masstree::MasstreeComposeContext::PathLevel::tail_

Offset in page_base_.

Definition at line 198 of file masstree_composer_impl.hpp.

Referenced by foedus::storage::masstree::operator<<().

---

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

• /home/shino/foedus_code/foedus-core/include/foedus/storage/masstree/masstree_composer_impl.hpp