foedus::storage::array::LookupRoute Union Reference

Compactly represents the route to reach the given offset. More...

Detailed Description

Compactly represents the route to reach the given offset.

Fanout cannot exceed 256 (as empty-payload is not allowed, minimal entry size is 16 bytes in both leaf and interior, 4096/16=256), uint8_t is enough to represent the route. Also, interior page always has a big fanout close to 256, so 8 levels are more than enough.

Definition at line 41 of file array_route.hpp.

#include <array_route.hpp>

Public Member Functions
ArrayRange	calculate_page_range (uint8_t page_level, uint8_t total_levels, uint16_t payload_size, ArrayOffset array_size) const
bool	operator== (const LookupRoute &rhs) const
bool	operator!= (const LookupRoute &rhs) const
bool	operator< (const LookupRoute &rhs) const
bool	operator<= (const LookupRoute &rhs) const

Public Attributes
uint64_t	word
	This is a 64bit data. More...
uint8_t	route [8]
	[0] means record ordinal in leaf, [1] in its parent page, [2]... More...

Member Function Documentation

ArrayRange foedus::storage::array::LookupRoute::calculate_page_range ( uint8_t  page_level, uint8_t  total_levels, uint16_t  payload_size, ArrayOffset  array_size  ) const

inline

Definition at line 179 of file array_route.hpp.

References ASSERT_ND, foedus::storage::array::ArrayRange::begin_, foedus::storage::array::ArrayRange::end_, foedus::storage::array::kInteriorFanout, route, and foedus::storage::array::to_records_in_leaf().

                                {
  ASSERT_ND(total_levels > page_level);
  ASSERT_ND(payload_size > 0);
  ASSERT_ND(array_size > 0);
  uint16_t records_in_leaf = to_records_in_leaf(payload_size);
  uint64_t interval = records_in_leaf;
  // for example:
  // page_level==0, route={xxx, 3, 4} (levels=3): r*3 + r*kInteriorFanout*4 ~ +r
  // page_level==1, route={xxx, yyy, 4}  (levels=3): r*kInteriorFanout*4 ~ +r*kInteriorFanout
  ArrayRange ret(0, 0);
  if (page_level == 0) {
    ret.end_ = records_in_leaf;
  }
  for (uint16_t level = 1; level < total_levels; ++level) {
    if (level == page_level) {
      ASSERT_ND(ret.begin_ == 0);
      ASSERT_ND(ret.end_ == 0);
      ret.end_ = interval * kInteriorFanout;
    } else if (level > page_level) {
      uint64_t shift = interval * route[level];
      ret.begin_ += shift;
      ret.end_ += shift;
    }
    interval *= kInteriorFanout;
  }
  ASSERT_ND(ret.begin_ < ret.end_);
  ASSERT_ND(ret.begin_ < array_size);
  if (ret.end_ > array_size) {
    ret.end_ = array_size;
  }
  return ret;
}

Here is the call graph for this function:

bool foedus::storage::array::LookupRoute::operator!= ( const LookupRoute &  rhs ) const

inline

Definition at line 57 of file array_route.hpp.

References word.

{ return word != rhs.word; }

bool foedus::storage::array::LookupRoute::operator< ( const LookupRoute &  rhs ) const

inline

Definition at line 58 of file array_route.hpp.

References route.

                                               {
    for (uint16_t i = 1; i <= 8U; ++i) {
      // compare the higher level first. if the machine is big-endian, we can just compare word.
      // but, this method is not used in performance-sensitive place, so let's be explicit.
      if (route[8U - i] != rhs.route[8U - i]) {
        return route[8U - i] < rhs.route[8U - i];
      }
    }
    return false;
  }

bool foedus::storage::array::LookupRoute::operator<= ( const LookupRoute &  rhs ) const

inline

Definition at line 68 of file array_route.hpp.

{ return *this == rhs || *this < rhs; }

bool foedus::storage::array::LookupRoute::operator== ( const LookupRoute &  rhs ) const

inline

Definition at line 56 of file array_route.hpp.

References word.

{ return word == rhs.word; }

Member Data Documentation

uint8_t foedus::storage::array::LookupRoute::route[8]

[0] means record ordinal in leaf, [1] in its parent page, [2]...

[levels - 1] is the ordinal in root page.

Definition at line 48 of file array_route.hpp.

Referenced by calculate_page_range(), foedus::storage::array::LookupRouteFinder::find_route(), foedus::storage::array::LookupRouteFinder::find_route_and_switch(), foedus::storage::array::ArrayStoragePimpl::lookup_for_read_batch(), foedus::storage::array::ArrayStoragePimpl::lookup_for_write_batch(), and operator<().

uint64_t foedus::storage::array::LookupRoute::word

This is a 64bit data.

Definition at line 43 of file array_route.hpp.

Referenced by foedus::storage::array::LookupRouteFinder::find_route(), foedus::storage::array::LookupRouteFinder::find_route_and_switch(), operator!=(), and operator==().

---

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

• /home/shino/foedus_code/foedus-core/include/foedus/storage/array/array_route.hpp