souffle::detail::binary_search Struct Reference

A binary search strategy for looking up keys in b-tree nodes. More...

#include <BTree.h>

Inheritance diagram for souffle::detail::binary_search:

Collaboration diagram for souffle::detail::binary_search:

Public Member Functions
	binary_search ()=default
	Required user-defined default constructor. More...
template<typename Key , typename Iter , typename Comp >
Iter	lower_bound (const Key &k, Iter a, Iter b, Comp &comp) const
	Obtains a reference to the first element in the given range that is not less than the given key. More...
template<typename Key , typename Iter , typename Comp >
Iter	operator() (const Key &k, Iter a, Iter b, Comp &comp) const
	Obtains an iterator pointing to some element within the given range that is equal to the given key, if available. More...
template<typename Key , typename Iter , typename Comp >
Iter	upper_bound (const Key &k, Iter a, Iter b, Comp &comp) const
	Obtains a reference to the first element in the given range that such that the given key is less than the referenced element. More...

Detailed Description

A binary search strategy for looking up keys in b-tree nodes.

Definition at line 141 of file BTree.h.

Constructor & Destructor Documentation

binary_search()

souffle::detail::binary_search::binary_search ( )

default

Required user-defined default constructor.

Referenced by souffle::detail::linear_search::upper_bound().

Member Function Documentation

lower_bound()

template<typename Key , typename Iter , typename Comp >

Iter souffle::detail::binary_search::lower_bound ( const Key &  k, Iter  a, Iter  b, Comp &  comp  ) const

inline

Obtains a reference to the first element in the given range that is not less than the given key.

Definition at line 181 of file BTree.h.

                                                                     {
        Iter c;
        auto count = b - a;
        while (count > 0) {
            auto step = count >> 1;
            c = a + step;
            if (comp(k, *c) >= 0) {
                a = ++c;

operator()()

template<typename Key , typename Iter , typename Comp >

Iter souffle::detail::binary_search::operator() ( const Key &  k, Iter  a, Iter  b, Comp &  comp  ) const

inline

Obtains an iterator pointing to some element within the given range that is equal to the given key, if available.

If multiple elements are equal to the given key, an undefined instance will be obtained (no guaranteed lower or upper boundary). If no such element is present, a reference to the first element not less than the given key will be returned.

Definition at line 156 of file BTree.h.

                                                                     {
        Iter c;
        auto count = b - a;
        while (count > 0) {
            auto step = count >> 1;
            c = a + step;
            if (comp(*c, k) < 0) {
                a = ++c;

upper_bound()

template<typename Key , typename Iter , typename Comp >

Iter souffle::detail::binary_search::upper_bound ( const Key &  k, Iter  a, Iter  b, Comp &  comp  ) const

inline

Obtains a reference to the first element in the given range that such that the given key is less than the referenced element.

Definition at line 202 of file BTree.h.

                          {
    using type = S;
};
 
struct linear : public strategy_selection<linear_search> {};

---

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

• include/souffle/datastructure/BTree.h