souffle::detail::linear_search Struct Reference

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

#include <BTree.h>

Inheritance diagram for souffle::detail::linear_search:

Collaboration diagram for souffle::detail::linear_search:

Public Member Functions
	linear_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 referencing an element equivalent to the given key in the given range. 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 linear search strategy for looking up keys in b-tree nodes.

Definition at line 87 of file BTree.h.

Constructor & Destructor Documentation

linear_search()

souffle::detail::linear_search::linear_search ( )

default

Required user-defined default constructor.

Member Function Documentation

lower_bound()

template<typename Key , typename Iter , typename Comp >

Iter souffle::detail::linear_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 109 of file BTree.h.

                                                                            {
        auto c = a;
        while (c < b) {
            if (comp(*c, k) > 0) {
                return c;
            }
            ++c;
        }

References b, and k.

operator()()

template<typename Key , typename Iter , typename Comp >

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

inline

Obtains an iterator referencing an element equivalent to the given key in the given range.

If no such element is present, a reference to the first element not less than the given key is returned.

Definition at line 100 of file BTree.h.

                                                                            {

upper_bound()

template<typename Key , typename Iter , typename Comp >

Iter souffle::detail::linear_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 126 of file BTree.h.

                     : public search_strategy {
    /**
     * Required user-defined default constructor.
     */
    binary_search() = default;
 
    /**
     * Obtains an iterator pointing to some element within the given
     * range that is equal to the given key, if available. If multiple

References souffle::detail::binary_search::binary_search().

Here is the call graph for this function:

---

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

• include/souffle/datastructure/BTree.h