lhf.hpp File Reference

Defines the LatticeHashForest structure and related tools. More...

#include <cstddef>
#include <iostream>
#include <memory>
#include <sstream>
#include <stdexcept>
#include <tuple>
#include <utility>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <string>
#include "lhf_config.hpp"
#include "profiling.hpp"

Include dependency graph for lhf.hpp:

Go to the source code of this file.

Classes
struct	lhf::DefaultPrinter< T >
struct	lhf::AbsentValueAccessError
	Thrown if an Optional is accessed when the value is absent. More...
class	lhf::OptionalRef< T >
	Describes an optional reference of some type T. The value may either be present or absent. More...
class	lhf::Optional< T >
	Describes an optional of some type T. The value may either be present or absent. More...
struct	lhf::OperationNode
	This struct contains the information about the operands of an operation (union, intersection, etc.) More...
struct	std::hash< lhf::OperationNode >
struct	lhf::SetLess< OrderedSetT, ElementT, PropertyLess >
	Generic Less-than comparator for set types. More...
struct	lhf::SetHash< SetT, ElementT, ElementHash >
	Hasher for set types. More...
struct	lhf::SetEqual< SetT, ElementT, PropertyEqual >
	Generic Equality comparator for set types. More...
struct	lhf::AssertError
	Struct that is thrown on an assertion failure. More...
struct	lhf::Unreachable
	Thrown if code region is unreachable. More...
struct	lhf::NestingNone< PropertyT >
	The nesting type for non-nested data structures. Act as "leaf" nodes in a tree of nested LHFs. More...
struct	lhf::NestingNone< PropertyT >::Empty
	Placeholder value to mark the reference lists and value lists as empty. More...
struct	lhf::NestingNone< PropertyT >::PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >
	Base-case type for the elements for a property set. The template arguments are for the 'key' type. More...
struct	lhf::NestingNone< PropertyT >::PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >::Hash
struct	lhf::NestingNone< PropertyT >::PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >::FullEqual
	This forces a comparison of both the key and the value instead of only the key. Required in instances where distinguishing this is necessary (like in the property set storage array). More...
class	lhf::MapAdapter< MapClass >
struct	lhf::NestingBase< PropertyT, ChildT >
	Describes the standard nesting structure. Act as "non-leaf" nodes in a tree of nested LHFs. More...
struct	lhf::NestingBase< PropertyT, ChildT >::PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >
	Type for the elements for a property set in the nested. The template arguments are for the 'key' type. More...
struct	lhf::NestingBase< PropertyT, ChildT >::PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >::Hash
struct	lhf::NestingBase< PropertyT, ChildT >::PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >::FullEqual
	This forces a comparison of both the key and the value instead of only the key. Required in instances where distinguishing this is necessary (like in the property set storage array) More...
struct	lhf::OperationPerf
	Operation performance Statistics. More...
class	lhf::LatticeHashForest< PropertyT, PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter, Nesting, BLOCK_SIZE, BLOCK_MASK >
	The main LatticeHashForest structure. This class can be used as-is with a type or derived for additional functionality as needed. More...
struct	lhf::LatticeHashForest< PropertyT, PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter, Nesting, BLOCK_SIZE, BLOCK_MASK >::Index
	Index returned by an operation. Being defined inside the class ensures type safety and possible future extensions. More...
struct	lhf::LatticeHashForest< PropertyT, PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter, Nesting, BLOCK_SIZE, BLOCK_MASK >::Index::Hash
struct	lhf::LatticeHashForest< PropertyT, PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter, Nesting, BLOCK_SIZE, BLOCK_MASK >::PropertySetHolder
class	lhf::LatticeHashForest< PropertyT, PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter, Nesting, BLOCK_SIZE, BLOCK_MASK >::PropertySetStorage
struct	lhf::Deduplicator< PropertyT, PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >
	An LHF-like structure for scalar values. It does not implement any special operations besides deduplication. More...
struct	lhf::Deduplicator< PropertyT, PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter >::Index
	Index returned by an operation. The struct ensures type safety and possible future extensions. More...

Namespaces
namespace	lhf

Macros
#define	LHF_DEBUG(x)   { x };
#define	____LHF__STR(x)   #x
#define	__LHF_STR(x)   ____LHF__STR(x)
#define	__LHF_EXCEPT(x)   AssertError(x " [At: " __FILE__ ":" __LHF_STR(__LINE__) "]")
#define	LHF_PROPERTY_SET_INTEGRITY_VALID(__set)    verify_property_set_integrity<PropertySet, PropertyElement>(__set);
	Macro and switch for verify_property_set_integrity inside LHF.
#define	LHF_PROPERTY_SET_INDEX_VALID(__index)
	Check whether the index is a valid index within the property set.
#define	LHF_PROPERTY_SET_PAIR_VALID(__index1, __index2)
	Check whether the pair of indexes is a valid within the property set.
#define	LHF_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2)
	Check whether the pair of indexes are unequal. Used for sanity checking.
#define	LHF_PARALLEL(__x)
#define	LHF_EVICTION(__x)
#define	LHF_PUSH_ONE(__cont, __val)   (__cont).push_back((__val))
	Pushes one element to a PropertySet. Use this when implementing operations.
#define	LHF_PUSH_RANGE(__cont, __start, __end)   (__cont).insert((__cont).end(), (__start), (__end))
	Pushes a range of elements to a PropertySet using an iterator. Use this when implementing operations.
#define	LHF_REGISTER_SET_INTERNAL(__set, __cold)   register_set<LHF_DISABLE_INTERNAL_INTEGRITY_CHECK>((__set), (__cold))
	Registers a set with behaviours defined for internal processing.
#define	LHF_BINARY_NESTED_OPERATION(__op_name)
	Declares a struct that enables the recursive/nesting behaviour of an operation.
#define	LHF_PERFORM_BINARY_NESTED_OPERATION(__op_name, __reflist, __arg1, __arg2)    ((__arg1) . template apply<__NestingOperation_ ## __op_name>((__reflist), (__arg2)))
	Actually enables the nesting. this must be placed in the operation body where the nested behaviour is needed.
#define	LHF_PERF_INC(__oper, __category)   (perf[__LHF_STR(__oper)] . __category ++)
	Increments the invocation count of the given category and operator.

Typedefs
using	lhf::Size = std::size_t
using	lhf::String = std::string
using	lhf::IndexValue = Size
template<typename T >
using	lhf::UniquePointer = std::unique_ptr< T >
template<typename T >
using	lhf::Vector = std::vector< T >
template<typename K , typename V >
using	lhf::HashMap = std::unordered_map< K, V >
template<typename K , typename V >
using	lhf::OrderedMap = std::map< K, V >
template<typename T >
using	lhf::HashSet = std::unordered_set< T >
template<typename T >
using	lhf::OrderedSet = std::set< T >
template<typename T >
using	lhf::DefaultLess = std::less< T >
template<typename T >
using	lhf::DefaultHash = std::hash< T >
template<typename T >
using	lhf::DefaultEqual = std::equal_to< T >
template<typename K , typename V >
using	lhf::InternalMap = MapAdapter< HashMap< K, V > >
template<typename T >
using	lhf::OperationMap = InternalMap< T, IndexValue >

Enumerations
enum	lhf::SubsetRelation { lhf::UNKNOWN = 0 , lhf::SUBSET = 1 , lhf::SUPERSET = 2 }
	Used to store a subset relation between two set indices. Because the index pair must be in sorted order to prevent duplicates, it necessitates this enum. More...

Functions
template<typename T , typename Hash = DefaultHash<T>>
Size	lhf::compose_hash (const Size prev, T next)
	Composes a preexisting hash with another variable. Useful for Hashing containers. Adapted from boost::hash_combine.
std::ostream &	lhf::operator<< (std::ostream &os, const OperationNode &op)

Detailed Description

Defines the LatticeHashForest structure and related tools.

Definition in file lhf.hpp.

Macro Definition Documentation

____LHF__STR

#define ____LHF__STR

(

x

)

#x

Definition at line 397 of file lhf.hpp.

__LHF_EXCEPT

#define __LHF_EXCEPT

(

x

)

AssertError(x " [At: " __FILE__ ":" __LHF_STR(__LINE__) "]")

Definition at line 399 of file lhf.hpp.

__LHF_STR

#define __LHF_STR

(

x

)

____LHF__STR(x)

Definition at line 398 of file lhf.hpp.

LHF_BINARY_NESTED_OPERATION

#define LHF_BINARY_NESTED_OPERATION

(

__op_name

)

Value:

    struct __NestingOperation_ ## __op_name { \
        template<typename ArgIndex, typename LHF> \
        void operator()(ArgIndex &ret, LHF &lhf, const ArgIndex &c, const ArgIndex &d) { \
            ret = lhf . __op_name (c, d); \
        } \
    };

Declares a struct that enables the recursive/nesting behaviour of an operation.

Parameters

__op_name

The operation name. Must match the function name (e.g. set_union, set_intersection etc.)

Returns

The set declaration.

Definition at line 819 of file lhf.hpp.

LHF_DEBUG

#define LHF_DEBUG

(

x

)

{ x };

Definition at line 43 of file lhf.hpp.

LHF_EVICTION

#define LHF_EVICTION

(

__x

)

Definition at line 504 of file lhf.hpp.

LHF_PARALLEL

#define LHF_PARALLEL

(

__x

)

Definition at line 498 of file lhf.hpp.

LHF_PERF_INC

#define LHF_PERF_INC	(		__oper,
			__category
	)		(perf[__LHF_STR(__oper)] . __category ++)

Increments the invocation count of the given category and operator.

Note

Conditionally enabled if LHF_ENABLE_PERFORMANCE_METRICS is set.

Parameters

__oper	The operator (e.g. unions)
__category	The category (e.g. hits)

Definition at line 1066 of file lhf.hpp.

LHF_PERFORM_BINARY_NESTED_OPERATION

#define LHF_PERFORM_BINARY_NESTED_OPERATION	(		__op_name,
			__reflist,
			__arg1,
			__arg2
	)		((__arg1) . template apply<__NestingOperation_ ## __op_name>((__reflist), (__arg2)))

Actually enables the nesting. this must be placed in the operation body where the nested behaviour is needed.

Parameters

__op_name	The operation name.
__reflist	The reference list of the LHF
__arg1	LHS argument of the binary operation
__arg2	RHS argument of the binary operation

Definition at line 838 of file lhf.hpp.

LHF_PROPERTY_SET_INDEX_VALID

#define LHF_PROPERTY_SET_INDEX_VALID

(

__index

)

Value:

    { \
    _Pragma("GCC diagnostic push"); \
    _Pragma("GCC diagnostic ignored \"-Wtype-limits\"") \
    if ((__index.value) < 0 || ((__index.value) > property_sets.size() - 1)) { \
        throw __LHF_EXCEPT("Invalid index supplied"); \
    } \
    _Pragma("GCC diagnostic pop") \
}

Check whether the index is a valid index within the property set.

Note

Signed/unsigned is made to be ignored here for the sanity checking.

Check whether the index is a valid index within the property set.

Note

Signed/unsigned is made to be ignored here for the sanity checking.

Definition at line 467 of file lhf.hpp.

LHF_PROPERTY_SET_INTEGRITY_VALID

#define LHF_PROPERTY_SET_INTEGRITY_VALID

(

__set

)

verify_property_set_integrity<PropertySet, PropertyElement>(__set);

Macro and switch for verify_property_set_integrity inside LHF.

Parameters

__set

The property set.

Definition at line 440 of file lhf.hpp.

LHF_PROPERTY_SET_PAIR_UNEQUAL

#define LHF_PROPERTY_SET_PAIR_UNEQUAL	(		__index1,
			__index2
	)

Value:

    if ((__index1) == (__index2)) { \
        throw __LHF_EXCEPT("Equal set condition not handled by caller"); \
    }

Check whether the pair of indexes are unequal. Used for sanity checking.

Definition at line 482 of file lhf.hpp.

LHF_PROPERTY_SET_PAIR_VALID

#define LHF_PROPERTY_SET_PAIR_VALID	(		__index1,
			__index2
	)

Value:

    LHF_PROPERTY_SET_INDEX_VALID(__index1); \
    LHF_PROPERTY_SET_INDEX_VALID(__index2);

Check whether the pair of indexes is a valid within the property set.

Definition at line 477 of file lhf.hpp.

LHF_PUSH_ONE

#define LHF_PUSH_ONE	(		__cont,
			__val
	)		(__cont).push_back((__val))

Pushes one element to a PropertySet. Use this when implementing operations.

Parameters

__cont	The container object
__val	The value

Definition at line 516 of file lhf.hpp.

LHF_PUSH_RANGE

#define LHF_PUSH_RANGE	(		__cont,
			__start,
			__end
	)		(__cont).insert((__cont).end(), (__start), (__end))

Pushes a range of elements to a PropertySet using an iterator. Use this when implementing operations.

Parameters

__cont	The container object
__start	The start of the range (e.g. input.begin())
__end	The end of the range (e.g. input.end())

Definition at line 528 of file lhf.hpp.

LHF_REGISTER_SET_INTERNAL

#define LHF_REGISTER_SET_INTERNAL	(		__set,
			__cold
	)		register_set<LHF_DISABLE_INTERNAL_INTEGRITY_CHECK>((__set), (__cold))

Registers a set with behaviours defined for internal processing.

Parameters

__set	The set
__cold	Whether this was a cold miss or not (pointer to bool)

Definition at line 538 of file lhf.hpp.