18#include <unordered_map>
20#include <unordered_set>
25#ifdef LHF_ENABLE_PARALLEL
28#include <shared_mutex>
33#include <tbb/concurrent_map.h>
34#include <tbb/concurrent_vector.h>
42#ifdef LHF_ENABLE_DEBUG
43#define LHF_DEBUG(x) { x };
52#ifdef LHF_ENABLE_PARALLEL
54using RWMutex = std::shared_mutex;
56using ReadLock = std::shared_lock<RWMutex>;
58using WriteLock = std::lock_guard<RWMutex>;
70template<
typename K,
typename V>
73template<
typename K,
typename V>
105 std::invalid_argument(message.c_str()) {}
116 const T *value =
nullptr;
129 return value !=
nullptr;
138 "A check is likely missing.");
157 Optional(
const T &value): value(value), present(true) {}
175 "A check is likely missing.");
194static const constexpr Size EMPTY_SET_VALUE = 0;
208template<
typename T,
typename Hash = DefaultHash<T>>
210 return prev ^ (Hash()(next) + 0x9e3779b9 + (prev << 6) + (prev >> 2));
245struct std::hash<
lhf::OperationNode> {
248 std::hash<lhf::IndexValue>()(k.
left) ^
249 (std::hash<lhf::IndexValue>()(k.
right) << 1);
265template<
typename OrderedSetT,
typename ElementT,
typename PropertyLess>
267 bool operator()(
const OrderedSetT *a,
const OrderedSetT *b)
const {
270 auto cursor_1 = a->begin();
271 const auto &cursor_end_1 = a->end();
272 auto cursor_2 = b->begin();
273 const auto &cursor_end_2 = b->end();
275 while (cursor_1 != cursor_end_1 && cursor_2 != cursor_end_2) {
276 if (less(*cursor_1, *cursor_2)) {
280 if (less(*cursor_2, *cursor_1)) {
288 return a->size() < b->size();
303 typename ElementHash = DefaultHash<ElementT>>
307 size_t hash_value = 0;
308 for (
const auto &value : *k) {
309 hash_value = compose_hash<ElementT, ElementHash>(hash_value, value);
327 typename PropertyEqual = DefaultEqual<ElementT>>
331 if (a->size() != b->size()) {
335 if (a->size() == 0) {
339 auto cursor_1 = a->begin();
340 const auto &cursor_end_1 = a->end();
341 auto cursor_2 = b->begin();
343 while (cursor_1 != cursor_end_1) {
344 if (!eq(*cursor_1, *cursor_2)) {
367template<
typename T,
typename Hash,
typename Equal>
368struct TBBHashCompare {
369 Size hash(
const T v)
const {
373 bool equal(
const T a,
const T b)
const {
374 return Equal()(a, b);
386 std::invalid_argument(message.c_str()) {}
393 Unreachable(
const std::string &message =
"Hit a branch marked as unreachable."):
394 std::runtime_error(message.c_str()) {}
397#define ____LHF__STR(x) #x
398#define __LHF_STR(x) ____LHF__STR(x)
399#define __LHF_EXCEPT(x) AssertError(x " [At: " __FILE__ ":" __LHF_STR(__LINE__) "]")
407template<
typename PropertySetT,
typename PropertyElementT>
408static inline void verify_property_set_integrity(
const PropertySetT &cont) {
409 if (cont.size() == 1) {
415 typename PropertyElementT::Hash> k;
416 const PropertyElementT *prev_val =
nullptr;
418 for (
const PropertyElementT &val : cont) {
419 if (prev_val && !(*prev_val < val)) {
420 throw AssertError(
"Supplied property set is not sorted.");
423 if (k.count(val) > 0) {
424 throw AssertError(
"Found duplicate key in given container.");
439#ifndef LHF_DISABLE_INTEGRITY_CHECKS
440#define LHF_PROPERTY_SET_INTEGRITY_VALID(__set) \
441 verify_property_set_integrity<PropertySet, PropertyElement>(__set);
443#define LHF_PROPERTY_SET_INTEGRITY_VALID(__set)
463#ifdef LHF_ENABLE_DEBUG
467#define LHF_PROPERTY_SET_INDEX_VALID(__index) { \
468 _Pragma("GCC diagnostic push"); \
469 _Pragma("GCC diagnostic ignored \"-Wtype-limits\"") \
470 if ((__index.value) < 0 || ((__index.value) > property_sets.size() - 1)) { \
471 throw __LHF_EXCEPT("Invalid index supplied"); \
473 _Pragma("GCC diagnostic pop") \
477#define LHF_PROPERTY_SET_PAIR_VALID(__index1, __index2) \
478 LHF_PROPERTY_SET_INDEX_VALID(__index1); \
479 LHF_PROPERTY_SET_INDEX_VALID(__index2);
482#define LHF_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2) \
483 if ((__index1) == (__index2)) { \
484 throw __LHF_EXCEPT("Equal set condition not handled by caller"); \
489#define LHF_PROPERTY_SET_INDEX_VALID(__index)
490#define LHF_PROPERTY_SET_PAIR_VALID(__index1, __index2)
491#define LHF_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2)
495#if defined(LHF_ENABLE_PARALLEL) && !defined(LHF_ENABLE_TBB)
496#define LHF_PARALLEL(__x) __x
498#define LHF_PARALLEL(__x)
501#ifdef LHF_ENABLE_EVICTION
502#define LHF_EVICTION(__x) __x
504#define LHF_EVICTION(__x)
516#define LHF_PUSH_ONE(__cont, __val) (__cont).push_back((__val))
528#define LHF_PUSH_RANGE(__cont, __start, __end) (__cont).insert((__cont).end(), (__start), (__end))
538#define LHF_REGISTER_SET_INTERNAL(__set, __cold) register_set<LHF_DISABLE_INTERNAL_INTEGRITY_CHECK>((__set), (__cold))
546template<
typename PropertyT>
575 typename PropertyLess,
576 typename PropertyHash,
577 typename PropertyEqual,
578 typename PropertyPrinter>
631 return PropertyPrinter()(
value);
641 return PropertyHash()(p.
value);
674template<
typename MapClass>
677 using Map = MapClass;
678 using Key =
typename Map::key_type;
683 using Accessor =
typename Map::const_accessor;
687 Optional<MappedType>
find(
const Key &key)
const {
689 bool found =
data.find(acc, key);
698 data.insert(std::move(v));
705 typename Map::const_iterator
begin()
const {
709 typename Map::const_iterator
end()
const {
716 for (
auto i :
data) {
717 s <<
" {" << i.first <<
" -> " << i.second <<
"} \n";
727template<
typename MapClass>
731 using Key =
typename Map::key_type;
742 auto value =
data.find(key);
743 if (value ==
data.end()) {
746 return value->second;
752 data.insert(std::move(v));
760 typename Map::const_iterator
begin()
const {
764 typename Map::const_iterator
end()
const {
772 for (
auto i : data) {
773 s <<
" {" << i.first <<
" -> " << i.second <<
"} \n";
791template<
typename K,
typename V>
792using InternalMap = MapAdapter<tbb::concurrent_hash_map<K, V>>;
796template<
typename K,
typename V>
819#define LHF_BINARY_NESTED_OPERATION(__op_name) \
820 struct __NestingOperation_ ## __op_name { \
821 template<typename ArgIndex, typename LHF> \
822 void operator()(ArgIndex &ret, LHF &lhf, const ArgIndex &c, const ArgIndex &d) { \
823 ret = lhf . __op_name (c, d); \
838#define LHF_PERFORM_BINARY_NESTED_OPERATION(__op_name, __reflist, __arg1, __arg2) \
839 ((__arg1) . template apply<__NestingOperation_ ## __op_name>((__reflist), (__arg2)))
848template<
typename PropertyT,
typename ...ChildT>
851 static constexpr bool is_nested =
true;
855 static constexpr Size num_children =
sizeof...(ChildT);
874 typename PropertyLess,
875 typename PropertyHash,
876 typename PropertyEqual,
877 typename PropertyPrinter>
892 const PropertyT &key,
934 template <
typename Operation,
Size... Indices>
939 std::index_sequence<Indices...>)
const {
940 ((Operation()(std::get<Indices>(ret),
941 std::get<Indices>(
lhf),
942 std::get<Indices>(value),
943 std::get<Indices>(arg_value)
959 template<
typename Operation>
964 apply_internal<Operation>(
968 std::make_index_sequence<num_children>{});
973 return PropertyLess()(key, b.key);
977 return PropertyEqual()(key, b.key);
982 s << PropertyPrinter()(key);
985 [&s](
auto&&... args) {
986 ((s << args.value <<
' '), ...);
999 return PropertyHash()(p.key);
1011 return PropertyEqual()(a.key, b.key) && (a.value == b.value);
1025 size_t equal_hits = 0;
1029 size_t subset_hits = 0;
1033 size_t empty_hits = 0;
1037 size_t cold_misses = 0;
1041 size_t edge_misses = 0;
1044 std::stringstream s;
1045 s <<
" " <<
"Hits : " << hits <<
"\n"
1046 <<
" " <<
"Equal Hits : " << equal_hits <<
"\n"
1047 <<
" " <<
"Subset Hits: " << subset_hits <<
"\n"
1048 <<
" " <<
"Empty Hits : " << empty_hits <<
"\n"
1049 <<
" " <<
"Cold Misses: " << cold_misses <<
"\n"
1050 <<
" " <<
"Edge Misses: " << edge_misses <<
"\n";
1065#ifdef LHF_ENABLE_PERFORMANCE_METRICS
1066#define LHF_PERF_INC(__oper, __category) (perf[__LHF_STR(__oper)] . __category ++)
1068#define LHF_PERF_INC(__oper, __category)
1092 typename PropertyLess = DefaultLess<PropertyT>,
1093 typename PropertyHash = DefaultHash<PropertyT>,
1094 typename PropertyEqual = DefaultEqual<PropertyT>,
1095 typename PropertyPrinter = DefaultPrinter<PropertyT>,
1096 typename Nesting = NestingNone<PropertyT>,
1111 return value == EMPTY_SET_VALUE;
1115 return value == b.
value;
1119 return value != b.
value;
1123 return value < b.
value;
1127 return value > b.
value;
1131 return std::to_string(value);
1167 typename PropertyElement::Hash>;
1173 typename PropertyElement::FullEqual>;
1198#ifdef LHF_ENABLE_TBB
1216 using RefList =
typename Nesting::LHFReferenceList;
1221#ifdef LHF_ENABLE_PERFORMANCE_METRICS
1228 using Ptr =
typename PtrContainer::pointer;
1239#ifdef LHF_ENABLE_EVICTION
1240 return ptr.get() ==
nullptr;
1246#ifdef LHF_ENABLE_EVICTION
1250 if (!is_present()) {
1251 throw AssertError(
"Tried to evict an already absent property set");
1257 void reassign(Ptr &&p) {
1260 throw AssertError(
"Tried to reassign when a property set is already present");
1266 void swap(PropertySetHolder &p) {
1269 throw AssertError(
"Tried to reassign when a property set is already present");
1270 }
else if (!p.is_present()) {
1271 throw AssertError(
"Attempted to swap to a null pointer");
1280#if defined(LHF_ENABLE_TBB)
1282 class PropertySetStorage {
1287 mutable tbb::concurrent_vector<PropertySetHolder> data = {};
1299 PropertySetHolder &at_mutable(
const Index &idx)
const {
1300 return data.at(idx.value);
1303 const PropertySetHolder &at(
const Index &idx)
const {
1304 return data.at(idx.value);
1307 Index push_back(PropertySetHolder &&p) {
1308 auto it = data.push_back(std::move(p));
1309 return it - data.begin();
1317#elif defined(LHF_ENABLE_PARALLEL)
1319 class PropertySetStorage {
1324 mutable Vector<Vector<PropertySetHolder>> data = {};
1326 mutable RWMutex mutex;
1327 mutable RWMutex realloc_mutex;
1329 std::atomic<Size> total_elems = 0;
1330 std::atomic<Size> block_base = 0;
1333 PropertySetStorage() {
1335 data.back().reserve(BLOCK_SIZE);
1347 PropertySetHolder &at_mutable(
const Index &idx)
const {
1348 ReadLock m(realloc_mutex);
1349 if (idx.value >= block_base) {
1350 return data.back().at(idx.value & BLOCK_MASK);
1353 return data.at((idx.value & (~BLOCK_MASK)) >> 5).at(idx.value & BLOCK_MASK);
1357 const PropertySetHolder &at(
const Index &idx)
const {
1358 ReadLock m(realloc_mutex);
1359 if (idx.value >= block_base) {
1360 return data.back().at(idx.value & BLOCK_MASK);
1363 return data.at((idx.value & (~BLOCK_MASK)) >> 5).at(idx.value & BLOCK_MASK);
1367 Index push_back(PropertySetHolder &&p) {
1369 if (data.back().size() >= BLOCK_SIZE) {
1370 WriteLock r(realloc_mutex);
1372 data.back().reserve(BLOCK_SIZE);
1373 block_base += BLOCK_SIZE;
1375 data.back().push_back(std::move(p));
1377 return Index(total_elems - 1);
1405 return data.at(idx.
value);
1409 return data.at(idx.
value);
1413 data.push_back(std::move(p));
1414 return data.size() - 1;
1480 if (!i.is_present()) {
1502 auto result = property_set_map.
find(new_set.
get());
1504 if (!result.is_present()) {
1507 Index ret = property_sets.push_back(std::move(new_set));
1508 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1513 property_sets.at_mutable(result.get()).swap(new_set);
1514 return Index(result.get());
1536 auto result = property_set_map.
find(new_set.
get());
1538 if (!result.is_present()) {
1541 Index ret = property_sets.push_back(std::move(new_set));
1542 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1548 property_sets.at_mutable(result.get()).swap(new_set);
1550 return Index(result.get());
1570 typename PropertyElement::Hash,
1571 typename PropertyElement::FullEqual> deduplicator;
1574 deduplicator.insert(i);
1577 c.assign(deduplicator.begin(), deduplicator.end());
1578 std::sort(c.begin(), c.end());
1581 template <
bool disable_
integrity_check = false>
1585 if (!disable_integrity_check) {
1589 auto result = property_set_map.
find(&c);
1591 if (!result.is_present()) {
1595 Index ret = property_sets.push_back(std::move(new_set));
1596 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1600 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1601 return Index(result.get());
1605 return Index(result.get());
1609 template <
bool disable_
integrity_check = false>
1613 if (!disable_integrity_check) {
1617 auto result = property_set_map.
find(&c);
1619 if (!result.is_present()) {
1623 Index ret = property_sets.push_back(std::move(new_set));
1624 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1630 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1632 return Index(result.get());
1637 return Index(result.get());
1641 template <
bool disable_
integrity_check = false>
1645 if (!disable_integrity_check) {
1649 auto result = property_set_map.
find(&c);
1651 if (!result.is_present()) {
1655 Index ret = property_sets.push_back(std::move(new_set));
1656 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1660 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1661 return Index(result.get());
1665 return Index(result.get());
1669 template <
bool disable_
integrity_check = false>
1673 if (!disable_integrity_check) {
1677 auto result = property_set_map.
find(&c);
1679 if (!result.is_present()) {
1683 Index ret = property_sets.push_back(std::move(new_set));
1684 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1690 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1692 return Index(result.get());
1697 return Index(result.get());
1701 template<
typename Iterator,
bool disable_
integrity_check = false>
1707 if (!disable_integrity_check) {
1711 auto result = property_set_map.
find(new_set.
get());
1713 if (!result.is_present()) {
1716 Index ret = property_sets.push_back(std::move(new_set));
1717 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1721 property_sets.at_mutable(result.get()).reassign(std::move(new_set));
1722 return Index(result.get());
1726 return Index(result.get());
1730 template<
typename Iterator,
bool disable_
integrity_check = false>
1736 if (!disable_integrity_check) {
1740 auto result = property_set_map.
find(new_set.
get());
1742 if (!result.is_present()) {
1745 Index ret = property_sets.push_back(std::move(new_set));
1746 property_set_map.
insert(std::make_pair(property_sets.at(ret).get(), ret.
value));
1751 property_sets.at_mutable(result.get()).reassign(std::move(new_set));
1753 return Index(result.get());
1758 return Index(result.get());
1762#ifdef LHF_ENABLE_EVICTION
1763 bool is_evicted(
const Index &index)
const {
1764 return property_sets.at(index.value).is_evicted();
1768#ifdef LHF_ENABLE_EVICTION
1769 void evict_set(
const Index &index) {
1771 if (index.is_empty()) {
1772 throw AssertError(
"Tried to evict the empty set");
1775 property_sets.at_mutable(index.value).evict();
1788#if defined(LHF_DEBUG) && defined(LHF_ENABLE_EVICTION)
1789 if (is_evicted(index)) {
1790 throw AssertError(
"Tried to access and evicted set");
1793 return *property_sets.at(index.
value).get();
1803 return property_sets.size();
1814 if (index == EMPTY_SET_VALUE) {
1817 return get_value(index).size();
1835 return PropertyLess()(a.get_key(), b);
1839 return PropertyLess()(a.get_key(), b.get_key());
1856 return PropertyEqual()(a.get_key(), b);
1860 return PropertyEqual()(a.get_key(), b.get_key());
1874 if (is_empty(index)) {
1882 if (equal_key(i, p)) {
1889 long int high = s.size() - 1;
1891 while (low <= high) {
1892 long int mid = low + (high - low) / 2;
1894 if (equal_key(s[mid], p)) {
1896 }
else if (less_key(s[mid], p)) {
1917 if (is_empty(index)) {
1925 if (equal_key(i, prop)) {
1932 long int high = s.size() - 1;
1934 while (low <= high) {
1935 long int mid = low + (high - low) / 2;
1936 if (equal_key(s[mid], prop)) {
1938 }
else if (less_key(s[mid], prop)) {
1971 }
else if (is_empty(_b)) {
1976 const Index &a = std::min(_a, _b);
1977 const Index &b = std::max(_a, _b);
1991 if (!result.is_present()
LHF_EVICTION(|| is_evicted(result.get()))) {
1999 auto cursor_1 = first.begin();
2000 const auto &cursor_end_1 = first.end();
2001 auto cursor_2 = second.begin();
2002 const auto &cursor_end_2 = second.end();
2004 while (cursor_1 != cursor_end_1) {
2005 if (cursor_2 == cursor_end_2) {
2010 if (less(*cursor_2, *cursor_1)) {
2014 if (!(less(*cursor_1, *cursor_2))) {
2015 if constexpr (Nesting::is_nested) {
2018 set_union, reflist, *cursor_1, *cursor_2);
2036 LHF_EVICTION(
if (result.is_present() && is_evicted(result.get())) {
2038 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2045 store_subset(b, ret);
2046 }
else if (ret == b) {
2047 store_subset(a, ret);
2049 store_subset(a, ret);
2050 store_subset(b, ret);
2063 return Index(result.get());
2078 return set_union(a, register_set_single(b));
2097 return Index(EMPTY_SET_VALUE);
2102 return Index(EMPTY_SET_VALUE);
2103 }
else if (is_empty(b)) {
2108 auto result = differences.
find({a.value, b.value});
2110 if (!result.is_present()
LHF_EVICTION(|| is_evicted(result.get()))) {
2118 auto cursor_1 = first.begin();
2119 const auto &cursor_end_1 = first.end();
2120 auto cursor_2 = second.begin();
2121 const auto &cursor_end_2 = second.end();
2123 while (cursor_1 != cursor_end_1) {
2124 if (cursor_2 == cursor_end_2) {
2129 if (less(*cursor_1, *cursor_2)) {
2133 if (!(less(*cursor_2, *cursor_1))) {
2134 if constexpr (Nesting::is_nested) {
2137 set_difference, reflist, *cursor_1, *cursor_2);
2149 LHF_EVICTION(
if (result.is_present() && is_evicted(result.get())) {
2151 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2154 differences.
insert({{a.value, b.value}, ret.
value});
2157 store_subset(ret, a);
2161 std::min(a.value, b.value),
2162 std::max(a.value, b.value)
2163 }, EMPTY_SET_VALUE});
2176 return Index(result.get());
2191 return set_difference(a, register_set_single(b));
2207 auto cursor_1 = first.begin();
2208 const auto &cursor_end_1 = first.end();
2210 for (;cursor_1 != cursor_end_1; cursor_1++) {
2211 if (!PropertyEqual()(cursor_1->get_key(), p)) {
2215 return register_set<true>(std::move(new_set));
2237 if (is_empty(_a) || is_empty(_b)) {
2239 return Index(EMPTY_SET_VALUE);
2242 const Index &a = std::min(_a, _b);
2243 const Index &b = std::max(_a, _b);
2257 if (!result.is_present()
LHF_EVICTION(|| is_evicted(result.get()))) {
2265 auto cursor_1 = first.begin();
2266 const auto &cursor_end_1 = first.end();
2267 auto cursor_2 = second.begin();
2268 const auto &cursor_end_2 = second.end();
2270 while (cursor_1 != cursor_end_1 && cursor_2 != cursor_end_2)
2272 if (less(*cursor_1,*cursor_2)) {
2275 if (!(less(*cursor_2, *cursor_1))) {
2276 if constexpr (Nesting::is_nested) {
2292 LHF_EVICTION(
if (result.is_present() && is_evicted(result.get())) {
2294 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2300 store_subset(ret, a);
2301 }
else if (ret != b) {
2302 store_subset(ret, b);
2304 store_subset(ret, a);
2305 store_subset(ret, b);
2318 return Index(result.get());
2355 if (!result.is_present()
LHF_EVICTION(|| is_evicted(result.get()))) {
2358 if (filter_func(value)) {
2366 LHF_EVICTION(
if (result.is_present() && is_evicted(result.get())) {
2368 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2383 return Index(result.get());
2395 std::stringstream s;
2406 return property_set_to_string(get_value(idx));
2413 std::stringstream s;
2417 s <<
" " <<
"Unions: " <<
"(Count: " << unions.
size() <<
")\n";
2421 s <<
" " <<
"Differences:" <<
"(Count: " << differences.
size() <<
")\n";
2425 s <<
" " <<
"Intersections: " <<
"(Count: " << intersections.
size() <<
")\n";
2429 s <<
" " <<
"Subsets: " <<
"(Count: " << subsets.
size() <<
")\n";
2430 for (
auto i : subsets) {
2431 s <<
" " << i.first <<
" -> " << (i.second ==
SUBSET ?
"sub" :
"sup") <<
"\n";
2435 s <<
" " <<
"PropertySets: " <<
"(Count: " << property_sets.size() <<
")\n";
2436 for (
size_t i = 0; i < property_sets.size(); i++) {
2438 << i <<
" : " << property_set_to_string(*property_sets.at(i).get()) <<
"\n";
2450#ifdef LHF_ENABLE_PERFORMANCE_METRICS
2459 std::stringstream s;
2460 s <<
"Performance Profile: \n";
2461 for (
auto &p : perf) {
2462 s << p.first <<
"\n"
2488 typename PropertyLess = DefaultLess<PropertyT>,
2489 typename PropertyHash = DefaultHash<PropertyT>,
2490 typename PropertyEqual = DefaultEqual<PropertyT>,
2491 typename PropertyPrinter = DefaultPrinter<PropertyT>>
2503 return value == EMPTY_SET_VALUE;
2507 return value == b.
value;
2511 return value != b.
value;
2515 return value < b.
value;
2519 return value > b.
value;
2551 auto cursor = property_map.find(new_value.get());
2553 if (cursor == property_map.end()) {
2555 property_list.push_back(std::move(new_value));
2557 property_map.insert(std::make_pair(property_list[ret].get(), ret));
2562 return Index(cursor->second);
Index push_back(PropertySetHolder &&p)
const PropertySetHolder & at(const Index &idx) const
PropertySetHolder & at_mutable(const Index &idx) const
Retuns a mutable reference to the property set holder at a given set index. This is useful for evicti...
The main LatticeHashForest structure. This class can be used as-is with a type or derived for additio...
static bool less(const PropertyElement &a, const PropertyElement &b)
Less than comparator for operations. You MUST use this instead of directly using anything else like "...
Index register_set(const PropertySet &c)
Index register_set(const PropertySet &c, bool &cold)
Index set_remove_single(const Index &a, const PropertyElement &b)
Removes a single element from a given set (and returns the index of the set). This is a wrapper over ...
bool contains(const Index &index, const PropertyElement &prop) const
Determines whether the property set at index contains the element prop or not.
LatticeHashForest(RefList reflist={})
static bool equal(const PropertyElement &a, const PropertyElement &b)
Equality comparator for operations. You MUST use this instead of directly using anything else like "<...
void store_subset(const Index &a, const Index &b)
Stores index a as the subset of index b if a < b, else stores index a as the superset of index b
static bool less_key(const PropertyElement &a, const PropertyT &b)
Index register_set(PropertySet &&c, bool &cold)
static bool less_key(const PropertyElement &a, const PropertyElement &b)
String property_set_to_string(const Index &idx) const
Index register_set_single(const PropertyElement &c)
Inserts a (or gets an existing) single-element set into property set storage.
Index set_filter(Index s, std::function< bool(const PropertyElement &)> filter_func, UnaryOperationMap &cache)
Filters a set based on a criterion function. This is supposed to be an abstract filtering mechanism t...
OptionalRef< PropertyElement > find_key(const Index &index, const PropertyT &p) const
Finds a property element in the set based on the key provided.
Index register_set(Iterator begin, Iterator end)
SubsetRelation is_subset(const Index &a, const Index &b) const
Returns whether we currently know whether a is a subset or a superset of b.
Index register_set(PropertySet &&c)
String dump_perf() const
Dumps performance information as a string.
Index set_insert_single(const Index &a, const PropertyElement &b)
Inserts a single element from a given set (and returns the index of the set). This is a wrapper over ...
bool is_empty(const Index &i) const
typename Nesting::template PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter > PropertyElement
static String property_set_to_string(const PropertySet &set)
Converts the property set to a string.
const PropertySet & get_value(const Index &index) const
Gets the actual property set specified by index.
Index set_remove_single_key(const Index &a, const PropertyT &p)
Removes a single element from a given set if the "key" element matches.
std::vector< PropertyElement > PropertySet
typename Nesting::LHFReferenceList RefList
static bool equal_key(const PropertyElement &a, const PropertyT &b)
Index register_set(Iterator begin, Iterator end, bool &cold)
static bool equal_key(const PropertyElement &a, const PropertyElement &b)
void prepare_vector_set(PropertySet &c)
PerformanceStatistics stat
Size size_of(const Index &index) const
Returns the size of the set at index
Size property_set_count() const
Returns the total number of property sets currently in the LHF.
HashMap< String, OperationPerf > perf
friend std::ostream & operator<<(std::ostream &os, const LatticeHashForest &obj)
String dump() const
Dumps the current state of the LHF to a string.
Index register_set_single(const PropertyElement &c, bool &cold)
Inserts a (or gets an existing) single-element set into the property set storage, and reports whether...
void insert(KeyValuePair &&v)
Optional< MappedType > find(const Key &key) const
Map::const_iterator end() const
Map::const_iterator begin() const
typename Map::value_type KeyValuePair
typename Map::key_type Key
typename Map::mapped_type MappedType
Describes an optional reference of some type T. The value may either be present or absent.
bool is_present() const
Informs if the value is present.
const T & get()
Gets the underlying value. Throws an exception if it is absent.
static OptionalRef absent()
Explicitly creates an absent value.
OptionalRef(const T &value)
Describes an optional of some type T. The value may either be present or absent.
static Optional absent()
Explicitly creates an absent value.
const T & get()
Gets the underlying value. Throws an exception if it is absent.
bool is_present()
Informs if the value is present.
#define LHF_PERFORM_BINARY_NESTED_OPERATION(__op_name, __reflist, __arg1, __arg2)
Actually enables the nesting. this must be placed in the operation body where the nested behaviour is...
#define LHF_PROPERTY_SET_INDEX_VALID(__index)
Check whether the index is a valid index within the property set.
#define LHF_PROPERTY_SET_INTEGRITY_VALID(__set)
Macro and switch for verify_property_set_integrity inside LHF.
#define LHF_PUSH_RANGE(__cont, __start, __end)
Pushes a range of elements to a PropertySet using an iterator. Use this when implementing operations.
#define LHF_PERF_INC(__oper, __category)
Increments the invocation count of the given category and operator.
#define LHF_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2)
Check whether the pair of indexes are unequal. Used for sanity checking.
#define LHF_PROPERTY_SET_PAIR_VALID(__index1, __index2)
Check whether the pair of indexes is a valid within the property set.
#define LHF_PARALLEL(__x)
#define LHF_PUSH_ONE(__cont, __val)
Pushes one element to a PropertySet. Use this when implementing operations.
#define LHF_BINARY_NESTED_OPERATION(__op_name)
Declares a struct that enables the recursive/nesting behaviour of an operation.
#define LHF_EVICTION(__x)
#define LHF_REGISTER_SET_INTERNAL(__set, __cold)
Registers a set with behaviours defined for internal processing.
Any configurable constants go into this file.
#define LHF_SORTED_VECTOR_BINARY_SEARCH_THRESHOLD
#define LHF_DEFAULT_BLOCK_SIZE
#define LHF_DEFAULT_BLOCK_MASK
Size compose_hash(const Size prev, T next)
Composes a preexisting hash with another variable. Useful for Hashing containers. Adapted from boost:...
std::ostream & operator<<(std::ostream &os, const OperationNode &op)
std::equal_to< T > DefaultEqual
std::unordered_map< K, V > HashMap
std::unordered_set< T > HashSet
std::map< K, V > OrderedMap
std::unique_ptr< T > UniquePointer
std::hash< T > DefaultHash
SubsetRelation
Used to store a subset relation between two set indices. Because the index pair must be in sorted ord...
std::less< T > DefaultLess
Enables basic code-based profiling metrics in LHF.
#define __lhf_calc_functime(__stat)
Creates a timer object to capture duration of the current function when going out of scope.
Thrown if an Optional is accessed when the value is absent.
AbsentValueAccessError(const std::string &message)
Struct that is thrown on an assertion failure.
AssertError(const std::string &message)
Index returned by an operation. The struct ensures type safety and possible future extensions.
bool operator>(const Index &b) const
bool operator!=(const Index &b) const
bool operator==(const Index &b) const
Index(IndexValue idx=EMPTY_SET_VALUE)
bool operator<(const Index &b) const
An LHF-like structure for scalar values. It does not implement any special operations besides dedupli...
Index register_value(const PropertyT &c)
Inserts a (or gets an existing) element into property storage.
std::unordered_map< PropertyT *, IndexValue, PropertyHash, PropertyEqual > PropertyMap
Size operator()(const Index &idx) const
Index returned by an operation. Being defined inside the class ensures type safety and possible futur...
Index(IndexValue idx=EMPTY_SET_VALUE)
friend std::ostream & operator<<(std::ostream &os, const Index &obj)
bool operator!=(const Index &b) const
bool operator==(const Index &b) const
bool operator>(const Index &b) const
bool operator<(const Index &b) const
UniquePointer< PropertySet > PtrContainer
typename PtrContainer::pointer Ptr
PropertySetHolder(Ptr &&p)
This forces a comparison of both the key and the value instead of only the key. Required in instances...
bool operator()(const PropertyElement &a, const PropertyElement &b) const
Size operator()(const PropertyElement &p) const
Type for the elements for a property set in the nested. The template arguments are for the 'key' type...
void apply_internal(ChildValueList &ret, const LHFReferenceList &lhf, const ChildValueList &arg_value, std::index_sequence< Indices... >) const
Actually performs the template "apply" operation. This sets up template syntax to go over each elemen...
PropertyElement(const PropertyT &key, const ChildValueList &value)
PropertyT InterfaceKeyType
Key type is made available here if required by user.
PropertyT InterfaceValueType
Value type is made available here if required by user.
const PropertyT & get_key() const
Gets the 'key' value.
bool operator<(const PropertyElement &b) const
const ChildValueList & get_value() const
Gets the nested value. It returns a tuple of values containing indices to each of the nested sets of ...
friend std::ostream & operator<<(std::ostream &os, const PropertyElement &obj)
PropertyElement apply(const LHFReferenceList &lhf, const PropertyElement &arg) const
Performs the "apply" operation on the list of nested children specified by the Operation parameter.
bool operator==(const PropertyElement &b) const
Describes the standard nesting structure. Act as "non-leaf" nodes in a tree of nested LHFs.
std::tuple< typename ChildT::Index... > ChildValueList
std::tuple< ChildT &... > LHFReferenceList
Reference list. References to all the nested LHFs are presented here.
Placeholder value to mark the reference lists and value lists as empty.
This forces a comparison of both the key and the value instead of only the key. Required in instances...
bool operator()(const PropertyElement &a, const PropertyElement &b) const
Size operator()(const PropertyElement &p) const
Base-case type for the elements for a property set. The template arguments are for the 'key' type.
PropertyElement(const PropertyT &value)
PropertyT InterfaceValueType
Value type is made available here if required by user.
bool operator==(const PropertyElement &b) const
const PropertyT & get_key() const
Gets the 'key' value.
bool operator<(const PropertyElement &b) const
PropertyElement apply() const
Performs an "apply" operation. In the base case it is an identity operation and does not do anything.
PropertyT InterfaceKeyType
Key type is made available here if required by user.
friend std::ostream & operator<<(std::ostream &os, const PropertyElement &obj)
const PropertyT & get_value() const
Gets the nested value. In the base case it simply returns the key.
The nesting type for non-nested data structures. Act as "leaf" nodes in a tree of nested LHFs.
static constexpr bool is_nested
Compile-time value that says this is not nested.
static constexpr Size num_children
Compile-time value that says there are no nested children.
This struct contains the information about the operands of an operation (union, intersection,...
std::string to_string() const
bool operator<(const OperationNode &op) const
bool operator==(const OperationNode &op) const
Operation performance Statistics.
Generic Equality comparator for set types.
bool operator()(const SetT *a, const SetT *b) const
Size operator()(const SetT *k) const
Generic Less-than comparator for set types.
bool operator()(const OrderedSetT *a, const OrderedSetT *b) const
Thrown if code region is unreachable.
Unreachable(const std::string &message="Hit a branch marked as unreachable.")
lhf::Size operator()(const lhf::OperationNode &k) const