SkipHeapAddressing< blocking > Struct Template Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MutablePriorityQueue.hpp>

Static Public Member Functions
static std::size_t	child_of (std::size_t node_no) noexcept
static std::size_t	parent_of (std::size_t node_no) noexcept
static bool	is_block_leaf (std::size_t node_no) noexcept
static bool	is_padding (std::size_t node_no) noexcept
static bool	is_block_root (std::size_t node_no) noexcept
static std::size_t	block_offset (std::size_t node_no) noexcept
static std::size_t	block_base (std::size_t node_no) noexcept
static std::size_t	child_no (std::size_t node_no) noexcept

Static Public Attributes
static const constexpr std::size_t	block_size = blocking
static const constexpr std::size_t	block_mask = block_size - 1

Detailed Description

template<std::size_t blocking>
struct SkipHeapAddressing< blocking >

Member Function Documentation

block_base()

template<std::size_t blocking>

std::size_t SkipHeapAddressing< blocking >::block_base ( std::size_t node_no )

inlinestaticnoexcept

{ return node_no & ~block_mask; }

References block_mask.

Referenced by child_of(), and parent_of().

Here is the caller graph for this function:

block_offset()

template<std::size_t blocking>

std::size_t SkipHeapAddressing< blocking >::block_offset ( std::size_t node_no )

inlinestaticnoexcept

{ return node_no & block_mask; }

References block_mask.

Referenced by child_of(), is_block_root(), is_padding(), and parent_of().

Here is the caller graph for this function:

child_no()

template<std::size_t blocking>

std::size_t SkipHeapAddressing< blocking >::child_no ( std::size_t node_no )

inlinestaticnoexcept

{ assert(is_block_leaf(node_no)); return node_no & (block_mask >> 1); }

References block_mask, and is_block_leaf().

Referenced by child_of().

Here is the call graph for this function:

Here is the caller graph for this function:

child_of()

template<std::size_t blocking>

std::size_t SkipHeapAddressing< blocking >::child_of ( std::size_t node_no )

inlinestaticnoexcept

                                                               {
      if (! is_block_leaf(node_no))
        // If not a leaf, then it is sufficient to just traverse down inside a miniheap.
        // The following line is equivalent to, but quicker than
        // return block_base(node_no) + 2 * block_offset(node_no);
      return node_no + block_offset(node_no);
    // Otherwise skip to a root of a child miniheap.
    return (block_base(node_no) + 1 + child_no(node_no) * 2) * block_size + 1;
  }

References block_base(), block_offset(), block_size, child_no(), and is_block_leaf().

Referenced by MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update_heap_down().

Here is the call graph for this function:

Here is the caller graph for this function:

is_block_leaf()

template<std::size_t blocking>

bool SkipHeapAddressing< blocking >::is_block_leaf ( std::size_t node_no )

inlinestaticnoexcept

{ return (node_no & (block_size >> 1)) != 0U; }

References block_size.

Referenced by child_no(), child_of(), and MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update_heap_down().

Here is the caller graph for this function:

is_block_root()

template<std::size_t blocking>

bool SkipHeapAddressing< blocking >::is_block_root ( std::size_t node_no )

inlinestaticnoexcept

{ return block_offset(node_no) == 1U; }

References block_offset().

Referenced by parent_of().

Here is the call graph for this function:

Here is the caller graph for this function:

is_padding()

template<std::size_t blocking>

bool SkipHeapAddressing< blocking >::is_padding ( std::size_t node_no )

inlinestaticnoexcept

{ return block_offset(node_no) == 0U; }

References block_offset().

Referenced by MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::clear(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator[](), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator[](), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::pop_back(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::push(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::push(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::remove(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update_heap_down(), and MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update_heap_up().

Here is the call graph for this function:

Here is the caller graph for this function:

parent_of()

template<std::size_t blocking>

std::size_t SkipHeapAddressing< blocking >::parent_of ( std::size_t node_no )

inlinestaticnoexcept

                                                                {
      auto const node_root = block_base(node_no); // 16
      if (! is_block_root(node_no))
        // If not a block (miniheap) root, then it is sufficient to just traverse up inside a miniheap.
      return node_root + block_offset(node_no) / 2;
    // Otherwise skipping from a root of one miniheap into leaf of another miniheap.
    // Address of a parent miniheap block. One miniheap branches at (block_size / 2) leaves to (block_size) miniheaps.
    auto const parent_base = block_base(node_root / block_size - 1); // 0
    // Index of a leaf of a parent miniheap, which is a parent of node_no.
    auto const child       = ((node_no - block_size) / block_size - parent_base) / 2;
    return 
      // Address of a parent miniheap
      parent_base + 
      // Address of a leaf of a parent miniheap
      block_size / 2 + child; // 30
  }

References block_base(), block_offset(), block_size, and is_block_root().

Referenced by MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update_heap_up().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

block_mask

template<std::size_t blocking>

const constexpr std::size_t SkipHeapAddressing< blocking >::block_mask = block_size - 1

staticconstexpr

Referenced by block_base(), block_offset(), and child_no().

block_size

template<std::size_t blocking>

const constexpr std::size_t SkipHeapAddressing< blocking >::block_size = blocking

staticconstexpr

Referenced by child_of(), is_block_leaf(), parent_of(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::reserve(), MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::size(), and MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update_heap_down().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MutablePriorityQueue.hpp