LatticeHashForest
Loading...
Searching...
No Matches
lhf.hpp
Go to the documentation of this file.
1
6#ifndef LHF_HPP
7#define LHF_HPP
8
9#include <cstddef>
10#include <iostream>
11#include <memory>
12#include <sstream>
13#include <stdexcept>
14#include <tuple>
15#include <utility>
16#include <vector>
17#include <map>
18#include <unordered_map>
19#include <set>
20#include <unordered_set>
21#include <functional>
22#include <algorithm>
23#include <string>
24
25#ifdef LHF_ENABLE_PARALLEL
26#include <atomic>
27#include <mutex>
28#include <shared_mutex>
29#endif
30
31#ifdef LHF_ENABLE_TBB
32#include <tbb/tbb.h>
33#include <tbb/concurrent_map.h>
34#include <tbb/concurrent_vector.h>
35#endif
36
37#include "lhf_config.hpp"
38#include "profiling.hpp"
39
40namespace lhf {
41
42#ifdef LHF_ENABLE_DEBUG
43#define LHF_DEBUG(x) { x };
44#else
45#define LHF_DEBUG(x)
46#endif
47
48using Size = std::size_t;
49
50using String = std::string;
51
52#ifdef LHF_ENABLE_PARALLEL
53
54using RWMutex = std::shared_mutex;
55
56using ReadLock = std::shared_lock<RWMutex>;
57
58using WriteLock = std::lock_guard<RWMutex>;
59
60#endif
61
63
64template<typename T>
65using UniquePointer = std::unique_ptr<T>;
66
67template<typename T>
68using Vector = std::vector<T>;
69
70template<typename K, typename V>
71using HashMap = std::unordered_map<K, V>;
72
73template<typename K, typename V>
74using OrderedMap = std::map<K, V>;
75
76template<typename T>
77using HashSet = std::unordered_set<T>;
78
79template<typename T>
80using OrderedSet = std::set<T>;
81
82template<typename T>
83using DefaultLess = std::less<T>;
84
85template<typename T>
86using DefaultHash = std::hash<T>;
87
88template<typename T>
89using DefaultEqual = std::equal_to<T>;
90
91template<typename T>
94 std::stringstream s;
95 s << x;
96 return s.str();
97 }
98};
99
103struct AbsentValueAccessError : public std::invalid_argument {
104 AbsentValueAccessError(const std::string &message):
105 std::invalid_argument(message.c_str()) {}
106};
107
114template<typename T>
116 const T *value = nullptr;
117 OptionalRef(): value(nullptr) {}
118
119public:
120 OptionalRef(const T &value): value(&value) {}
121
124 return OptionalRef();
125 }
126
128 bool is_present() const {
129 return value != nullptr;
130 }
131
133 const T &get() {
134 if (value) {
135 return *value;
136 } else {
137 throw AbsentValueAccessError("Tried to access an absent value. "
138 "A check is likely missing.");
139 }
140 }
141};
142
149template<typename T>
150class Optional {
151 const T value{};
152 const bool present;
153
154 Optional(): present(false) {}
155
156public:
157 Optional(const T &value): value(value), present(true) {}
158
160 static Optional absent() {
161 return Optional();
162 }
163
165 bool is_present() {
166 return present;
167 }
168
170 const T &get() {
171 if (present) {
172 return value;
173 } else {
174 throw AbsentValueAccessError("Tried to access an absent value. "
175 "A check is likely missing.");
176 }
177 }
178};
179
190
191
192// The index of the empty set. The first set that will ever be inserted
193// in the property set value storage is the empty set.
194static const constexpr Size EMPTY_SET_VALUE = 0;
195
208template<typename T, typename Hash = DefaultHash<T>>
209inline Size compose_hash(const Size prev, T next) {
210 return prev ^ (Hash()(next) + 0x9e3779b9 + (prev << 6) + (prev >> 2));
211}
212
220
221 std::string to_string() const {
222 std::stringstream s;
223 s << "(" << left << "," << right << ")";
224 return s.str();
225 }
226
227 bool operator<(const OperationNode &op) const {
228 return (left < op.left) || (right < op.right);
229 }
230
231 bool operator==(const OperationNode &op) const {
232 return (left == op.left) && (right == op.right);
233 }
234};
235
236inline std::ostream &operator<<(std::ostream &os, const OperationNode &op) {
237 return os << op.to_string();
238}
239
240};
241
242/************************** START GLOBAL NAMESPACE ****************************/
243
244template <>
245struct std::hash<lhf::OperationNode> {
247 return
248 std::hash<lhf::IndexValue>()(k.left) ^
249 (std::hash<lhf::IndexValue>()(k.right) << 1);
250 }
251};
252
253/************************** END GLOBAL NAMESPACE ******************************/
254
255namespace lhf {
256
265template<typename OrderedSetT, typename ElementT, typename PropertyLess>
266struct SetLess {
267 bool operator()(const OrderedSetT *a, const OrderedSetT *b) const {
268 PropertyLess less;
269
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();
274
275 while (cursor_1 != cursor_end_1 && cursor_2 != cursor_end_2) {
276 if (less(*cursor_1, *cursor_2)) {
277 return true;
278 }
279
280 if (less(*cursor_2, *cursor_1)) {
281 return false;
282 }
283
284 cursor_1++;
285 cursor_2++;
286 }
287
288 return a->size() < b->size();
289 }
290};
291
300template<
301 typename SetT,
302 typename ElementT,
303 typename ElementHash = DefaultHash<ElementT>>
304struct SetHash {
305 Size operator()(const SetT *k) const {
306 // Adapted from boost::hash_combine
307 size_t hash_value = 0;
308 for (const auto &value : *k) {
309 hash_value = compose_hash<ElementT, ElementHash>(hash_value, value);
310 }
311
312 return hash_value;
313 }
314};
315
324template<
325 typename SetT,
326 typename ElementT,
327 typename PropertyEqual = DefaultEqual<ElementT>>
328struct SetEqual {
329 inline bool operator()(const SetT *a, const SetT *b) const {
330 PropertyEqual eq;
331 if (a->size() != b->size()) {
332 return false;
333 }
334
335 if (a->size() == 0) {
336 return true;
337 }
338
339 auto cursor_1 = a->begin();
340 const auto &cursor_end_1 = a->end();
341 auto cursor_2 = b->begin();
342
343 while (cursor_1 != cursor_end_1) {
344 if (!eq(*cursor_1, *cursor_2)) {
345 return false;
346 }
347
348 cursor_1++;
349 cursor_2++;
350 }
351
352 return true;
353 }
354};
355
356#ifdef LHF_ENABLE_TBB
357
367template<typename T, typename Hash, typename Equal>
368struct TBBHashCompare {
369 Size hash(const T v) const {
370 return Hash()(v);
371 }
372
373 bool equal(const T a, const T b) const {
374 return Equal()(a, b);
375 }
376};
377
378#endif
379
380
384struct AssertError : public std::invalid_argument {
385 AssertError(const std::string &message):
386 std::invalid_argument(message.c_str()) {}
387};
388
392struct Unreachable : public std::runtime_error {
393 Unreachable(const std::string &message = "Hit a branch marked as unreachable."):
394 std::runtime_error(message.c_str()) {}
395};
396
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__) "]")
400
407template<typename PropertySetT, typename PropertyElementT>
408static inline void verify_property_set_integrity(const PropertySetT &cont) {
409 if (cont.size() == 1) {
410 return;
411 }
412
413 std::unordered_set<
414 PropertyElementT,
415 typename PropertyElementT::Hash> k;
416 const PropertyElementT *prev_val = nullptr;
417
418 for (const PropertyElementT &val : cont) {
419 if (prev_val && !(*prev_val < val)) {
420 throw AssertError("Supplied property set is not sorted.");
421 }
422
423 if (k.count(val) > 0) {
424 throw AssertError("Found duplicate key in given container.");
425 } else {
426 k.insert(val);
427 }
428
429 prev_val = &val;
430 }
431}
432
439#ifndef LHF_DISABLE_INTEGRITY_CHECKS
440#define LHF_PROPERTY_SET_INTEGRITY_VALID(__set) \
441 verify_property_set_integrity<PropertySet, PropertyElement>(__set);
442#else
443#define LHF_PROPERTY_SET_INTEGRITY_VALID(__set)
444#endif
445
446
463#ifdef LHF_ENABLE_DEBUG
464
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"); \
472 } \
473 _Pragma("GCC diagnostic pop") \
474}
475
477#define LHF_PROPERTY_SET_PAIR_VALID(__index1, __index2) \
478 LHF_PROPERTY_SET_INDEX_VALID(__index1); \
479 LHF_PROPERTY_SET_INDEX_VALID(__index2);
480
482#define LHF_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2) \
483 if ((__index1) == (__index2)) { \
484 throw __LHF_EXCEPT("Equal set condition not handled by caller"); \
485 }
486
487#else
488
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)
492
493#endif
494
495#if defined(LHF_ENABLE_PARALLEL) && !defined(LHF_ENABLE_TBB)
496#define LHF_PARALLEL(__x) __x
497#else
498#define LHF_PARALLEL(__x)
499#endif
500
501#ifdef LHF_ENABLE_EVICTION
502#define LHF_EVICTION(__x) __x
503#else
504#define LHF_EVICTION(__x)
505#endif
506
516#define LHF_PUSH_ONE(__cont, __val) (__cont).push_back((__val))
517
528#define LHF_PUSH_RANGE(__cont, __start, __end) (__cont).insert((__cont).end(), (__start), (__end))
529
530
538#define LHF_REGISTER_SET_INTERNAL(__set, __cold) register_set<LHF_DISABLE_INTERNAL_INTEGRITY_CHECK>((__set), (__cold))
539
546template<typename PropertyT>
549 static constexpr bool is_nested = false;
550
552 static constexpr Size num_children = 0;
553
555 struct Empty {
556 Empty() {}
557 };
558
561
564
574 template<
575 typename PropertyLess,
576 typename PropertyHash,
577 typename PropertyEqual,
578 typename PropertyPrinter>
580 public:
582 using InterfaceKeyType = PropertyT;
583
585 using InterfaceValueType = PropertyT;
586
587 protected:
588 PropertyT value;
589
590 public:
591 PropertyElement(const PropertyT &value): value(value) {}
592
598 const PropertyT &get_key() const {
599 return value;
600 }
601
608 const PropertyT &get_value() const {
609 return value;
610 }
611
619 return *this;
620 }
621
622 bool operator<(const PropertyElement &b) const {
623 return PropertyLess()(value, b.value);
624 }
625
626 bool operator==(const PropertyElement &b) const {
627 return PropertyEqual()(value, b.value);
628 }
629
631 return PropertyPrinter()(value);
632 }
633
634 friend std::ostream& operator<<(std::ostream& os, const PropertyElement& obj) {
635 os << obj.to_string();
636 return os;
637 }
638
639 struct Hash {
641 return PropertyHash()(p.value);
642 }
643 };
644
654 struct FullEqual {
655 bool operator()(const PropertyElement &a, const PropertyElement &b) const {
656 return PropertyEqual()(a.value, b.value);
657 }
658 };
659 };
660
661};
662
672#ifdef LHF_ENABLE_TBB
673
674template<typename MapClass>
675class MapAdapter {
676public:
677 using Map = MapClass;
678 using Key = typename Map::key_type;
679 using MappedType = typename Map::mapped_type;
680 using KeyValuePair = typename Map::value_type;
681
682protected:
683 using Accessor = typename Map::const_accessor;
684 Map data;
685
686public:
687 Optional<MappedType> find(const Key &key) const {
688 Accessor acc;
689 bool found = data.find(acc, key);
690 if (!found) {
692 } else {
693 return acc->second;
694 }
695 }
696
697 void insert(KeyValuePair &&v) {
698 data.insert(std::move(v));
699 }
700
701 Size size() const {
702 return data.size();
703 }
704
705 typename Map::const_iterator begin() const {
706 return data.begin();
707 }
708
709 typename Map::const_iterator end() const {
710 return data.end();
711 }
712
713 String to_string() const {
714 std::stringstream s;
715
716 for (auto i : data) {
717 s << " {" << i.first << " -> " << i.second << "} \n";
718 }
719
720 return s.str();
721 }
722
723};
724
725#else
726
727template<typename MapClass>
729public:
730 using Map = MapClass;
731 using Key = typename Map::key_type;
732 using MappedType = typename Map::mapped_type;
733 using KeyValuePair = typename Map::value_type;
734
735protected:
737 LHF_PARALLEL(mutable RWMutex mutex;)
738
739public:
740 Optional<MappedType> find(const Key &key) const {
741 LHF_PARALLEL(ReadLock m(mutex);)
742 auto value = data.find(key);
743 if (value == data.end()) {
745 } else {
746 return value->second;
747 }
748 }
749
751 LHF_PARALLEL(WriteLock m(mutex);)
752 data.insert(std::move(v));
753 }
754
755 Size size() const {
756 LHF_PARALLEL(ReadLock m(mutex);)
757 return data.size();
758 }
759
760 typename Map::const_iterator begin() const {
761 return data.begin();
762 }
763
764 typename Map::const_iterator end() const {
765 return data.end();
766 }
767
769 LHF_PARALLEL(ReadLock m(mutex);)
770 std::stringstream s;
771
772 for (auto i : data) {
773 s << " {" << i.first << " -> " << i.second << "} \n";
774 }
775
776 return s.str();
777 }
778
779};
780
781#endif
782
783
789#ifdef LHF_ENABLE_TBB
790
791template<typename K, typename V>
792using InternalMap = MapAdapter<tbb::concurrent_hash_map<K, V>>;
793
794#else
795
796template<typename K, typename V>
798
799#endif
800
805template<typename T>
807
808
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); \
824 } \
825 };
826
838#define LHF_PERFORM_BINARY_NESTED_OPERATION(__op_name, __reflist, __arg1, __arg2) \
839 ((__arg1) . template apply<__NestingOperation_ ## __op_name>((__reflist), (__arg2)))
840
848template<typename PropertyT, typename ...ChildT>
851 static constexpr bool is_nested = true;
852
855 static constexpr Size num_children = sizeof...(ChildT);
856
858 using LHFReferenceList = std::tuple<ChildT&...>;
859
862 using ChildValueList = std::tuple<typename ChildT::Index...>;
863
873 template<
874 typename PropertyLess,
875 typename PropertyHash,
876 typename PropertyEqual,
877 typename PropertyPrinter>
879 public:
881 using InterfaceKeyType = PropertyT;
882
884 using InterfaceValueType = PropertyT;
885
886 private:
887 PropertyT key;
888 ChildValueList value;
889
890 public:
892 const PropertyT &key,
893 const ChildValueList &value):
894 key(key),
895 value(value) {}
896
902 const PropertyT &get_key() const {
903 return key;
904 }
905
906
914 const ChildValueList &get_value() const {
915 return value;
916 }
917
934 template <typename Operation, Size... Indices>
936 ChildValueList &ret,
937 const LHFReferenceList &lhf,
938 const ChildValueList &arg_value,
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)
944 )), ...);
945 }
946
959 template<typename Operation>
961 const LHFReferenceList &lhf,
962 const PropertyElement &arg) const {
963 ChildValueList ret;
964 apply_internal<Operation>(
965 ret,
966 lhf,
967 arg.value,
968 std::make_index_sequence<num_children>{});
969 return PropertyElement(key, ret);
970 }
971
972 bool operator<(const PropertyElement &b) const {
973 return PropertyLess()(key, b.key);
974 }
975
976 bool operator==(const PropertyElement &b) const {
977 return PropertyEqual()(key, b.key);
978 }
979
981 std::stringstream s;
982 s << PropertyPrinter()(key);
983 s << " -> [ ";
984 std::apply(
985 [&s](auto&&... args) {
986 ((s << args.value << ' '), ...);
987 }, value);
988 s << "]";
989 return s.str();
990 }
991
992 friend std::ostream& operator<<(std::ostream& os, const PropertyElement& obj) {
993 os << obj.to_string();
994 return os;
995 }
996
997 struct Hash {
999 return PropertyHash()(p.key);
1000 }
1001 };
1002
1009 struct FullEqual {
1010 bool operator()(const PropertyElement &a, const PropertyElement &b) const {
1011 return PropertyEqual()(a.key, b.key) && (a.value == b.value);
1012 }
1013 };
1014 };
1015};
1016
1022 size_t hits = 0;
1023
1025 size_t equal_hits = 0;
1026
1029 size_t subset_hits = 0;
1030
1033 size_t empty_hits = 0;
1034
1037 size_t cold_misses = 0;
1038
1041 size_t edge_misses = 0;
1042
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";
1051 return s.str();
1052 }
1053};
1054
1065#ifdef LHF_ENABLE_PERFORMANCE_METRICS
1066#define LHF_PERF_INC(__oper, __category) (perf[__LHF_STR(__oper)] . __category ++)
1067#else
1068#define LHF_PERF_INC(__oper, __category)
1069#endif
1070
1071
1090template <
1091 typename PropertyT,
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>,
1097 Size BLOCK_SIZE = LHF_DEFAULT_BLOCK_SIZE,
1098 Size BLOCK_MASK = LHF_DEFAULT_BLOCK_MASK>
1100public:
1105 struct Index {
1107
1108 Index(IndexValue idx = EMPTY_SET_VALUE): value(idx) {}
1109
1110 bool is_empty() const {
1111 return value == EMPTY_SET_VALUE;
1112 }
1113
1114 bool operator==(const Index &b) const {
1115 return value == b.value;
1116 }
1117
1118 bool operator!=(const Index &b) const {
1119 return value != b.value;
1120 }
1121
1122 bool operator<(const Index &b) const {
1123 return value < b.value;
1124 }
1125
1126 bool operator>(const Index &b) const {
1127 return value > b.value;
1128 }
1129
1131 return std::to_string(value);
1132 }
1133
1134 friend std::ostream& operator<<(std::ostream& os, const Index& obj) {
1135 os << obj.to_string();
1136 return os;
1137 }
1138
1139 struct Hash {
1140 Size operator()(const Index &idx) const {
1141 return DefaultHash<IndexValue>()(idx.value);
1142 }
1143 };
1144 };
1145
1151 typename Nesting::template PropertyElement<
1152 PropertyLess,
1153 PropertyHash,
1154 PropertyEqual,
1155 PropertyPrinter>;
1156
1161 using PropertySet = std::vector<PropertyElement>;
1162
1164 SetHash<
1167 typename PropertyElement::Hash>;
1168
1170 SetEqual<
1173 typename PropertyElement::FullEqual>;
1174
1198#ifdef LHF_ENABLE_TBB
1199 using PropertySetMap =
1200 MapAdapter<tbb::concurrent_hash_map<
1201 const PropertySet *, IndexValue,
1202 TBBHashCompare<
1203 const PropertySet *,
1206#else
1208 MapAdapter<std::unordered_map<
1209 const PropertySet *, IndexValue,
1212#endif
1213
1216 using RefList = typename Nesting::LHFReferenceList;
1217
1218protected:
1220
1221#ifdef LHF_ENABLE_PERFORMANCE_METRICS
1224#endif
1225
1228 using Ptr = typename PtrContainer::pointer;
1229
1231
1232 PropertySetHolder(Ptr &&p): ptr(p) {}
1233
1234 Ptr get() const {
1235 return ptr.get();
1236 }
1237
1238 bool is_evicted() const {
1239#ifdef LHF_ENABLE_EVICTION
1240 return ptr.get() == nullptr;
1241#else
1242 return false;
1243#endif
1244 }
1245
1246#ifdef LHF_ENABLE_EVICTION
1247
1248 void evict() {
1249#if LHF_DEBUG
1250 if (!is_present()) {
1251 throw AssertError("Tried to evict an already absent property set");
1252 }
1253#endif
1254 ptr.release();
1255 }
1256
1257 void reassign(Ptr &&p) {
1258#if LHF_DEBUG
1259 if (is_present()) {
1260 throw AssertError("Tried to reassign when a property set is already present");
1261 }
1262#endif
1263 ptr.reset(p);
1264 }
1265
1266 void swap(PropertySetHolder &p) {
1267#if LHF_DEBUG
1268 if (is_present()) {
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");
1272 }
1273#endif
1274 ptr.swap(p.ptr);
1275 }
1276
1277#endif
1278 };
1279
1280#if defined(LHF_ENABLE_TBB)
1281
1282 class PropertySetStorage {
1283 protected:
1286 // is important for eviction to work.
1287 mutable tbb::concurrent_vector<PropertySetHolder> data = {};
1288
1289 public:
1299 PropertySetHolder &at_mutable(const Index &idx) const {
1300 return data.at(idx.value);
1301 }
1302
1303 const PropertySetHolder &at(const Index &idx) const {
1304 return data.at(idx.value);
1305 }
1306
1307 Index push_back(PropertySetHolder &&p) {
1308 auto it = data.push_back(std::move(p));
1309 return it - data.begin();
1310 }
1311
1312 Size size() const {
1313 return data.size();
1314 }
1315 };
1316
1317#elif defined(LHF_ENABLE_PARALLEL)
1318
1319 class PropertySetStorage {
1320 protected:
1323 // is important for eviction to work.
1324 mutable Vector<Vector<PropertySetHolder>> data = {};
1325
1326 mutable RWMutex mutex;
1327 mutable RWMutex realloc_mutex;
1328
1329 std::atomic<Size> total_elems = 0;
1330 std::atomic<Size> block_base = 0;
1331
1332 public:
1333 PropertySetStorage() {
1334 data.push_back({});
1335 data.back().reserve(BLOCK_SIZE);
1336 }
1337
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);
1351 } else {
1352 // TODO fix this
1353 return data.at((idx.value & (~BLOCK_MASK)) >> 5).at(idx.value & BLOCK_MASK);
1354 }
1355 }
1356
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);
1361 } else {
1362 // TODO fix this
1363 return data.at((idx.value & (~BLOCK_MASK)) >> 5).at(idx.value & BLOCK_MASK);
1364 }
1365 }
1366
1367 Index push_back(PropertySetHolder &&p) {
1368 WriteLock m(mutex);
1369 if (data.back().size() >= BLOCK_SIZE) {
1370 WriteLock r(realloc_mutex);
1371 data.push_back({});
1372 data.back().reserve(BLOCK_SIZE);
1373 block_base += BLOCK_SIZE;
1374 }
1375 data.back().push_back(std::move(p));
1376 total_elems++;
1377 return Index(total_elems - 1);
1378 }
1379
1380 Size size() const {
1381 return total_elems;
1382 }
1383 };
1384
1385#else
1386
1388 protected:
1391 // is important for eviction to work.
1392 mutable Vector<PropertySetHolder> data = {};
1393
1394 public:
1405 return data.at(idx.value);
1406 }
1407
1408 const PropertySetHolder &at(const Index &idx) const {
1409 return data.at(idx.value);
1410 }
1411
1413 data.push_back(std::move(p));
1414 return data.size() - 1;
1415 }
1416
1417 Size size() const {
1418 return data.size();
1419 }
1420 };
1421
1422#endif
1423
1424 // The property set storage array.
1425 PropertySetStorage property_sets = {};
1426
1427 // The property set -> Index in storage array mapping.
1428 PropertySetMap property_set_map = {};
1429
1431 BinaryOperationMap intersections = {};
1432 BinaryOperationMap differences = {};
1433
1435
1443 void store_subset(const Index &a, const Index &b) {
1446 __lhf_calc_functime(stat);
1447
1448 // We need to maintain the operation pair in index-order here as well.
1449 if (a > b) {
1450 subsets.insert({{b.value, a.value}, SUPERSET});
1451 } else {
1452 subsets.insert({{a.value, b.value}, SUBSET});
1453 }
1454 }
1455
1456public:
1457 explicit LatticeHashForest(RefList reflist = {}): reflist(reflist) {
1458 // INSERT EMPTY SET AT INDEX 0
1459 register_set({ });
1460 }
1461
1462 inline bool is_empty(const Index &i) const {
1463 return i.is_empty();
1464 }
1465
1475 SubsetRelation is_subset(const Index &a, const Index &b) const {
1477
1478 auto i = subsets.find({a.value, b.value});
1479
1480 if (!i.is_present()) {
1481 return UNKNOWN;
1482 } else {
1483 return i.get();
1484 }
1485 }
1486
1498 __lhf_calc_functime(stat);
1499
1501
1502 auto result = property_set_map.find(new_set.get());
1503
1504 if (!result.is_present()) {
1505 LHF_PERF_INC(property_sets, cold_misses);
1506
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));
1509
1510 return ret;
1511 }
1512 LHF_EVICTION(else if (is_evicted(result.get())) {
1513 property_sets.at_mutable(result.get()).swap(new_set);
1514 return Index(result.get());
1515 })
1516 else {
1517 LHF_PERF_INC(property_sets, hits);
1518 return Index(result.get());
1519 }
1520 }
1521
1533 __lhf_calc_functime(stat);
1534
1536 auto result = property_set_map.find(new_set.get());
1537
1538 if (!result.is_present()) {
1539 LHF_PERF_INC(property_sets, cold_misses);
1540
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));
1543
1544 cold = true;
1545 return ret;
1546 }
1547 LHF_EVICTION(else if (is_evicted(result.get())) {
1548 property_sets.at_mutable(result.get()).swap(new_set);
1549 cold = false;
1550 return Index(result.get());
1551 })
1552 else {
1553 LHF_PERF_INC(property_sets, hits);
1554 cold = false;
1555 return Index(result.get());
1556 }
1557 }
1558
1568 std::unordered_set<
1570 typename PropertyElement::Hash,
1571 typename PropertyElement::FullEqual> deduplicator;
1572
1573 for (auto &i : c) {
1574 deduplicator.insert(i);
1575 }
1576
1577 c.assign(deduplicator.begin(), deduplicator.end());
1578 std::sort(c.begin(), c.end());
1579 }
1580
1581 template <bool disable_integrity_check = false>
1583 __lhf_calc_functime(stat);
1584
1585 if (!disable_integrity_check) {
1587 }
1588
1589 auto result = property_set_map.find(&c);
1590
1591 if (!result.is_present()) {
1592 LHF_PERF_INC(property_sets, cold_misses);
1593
1594 PropertySetHolder new_set(new PropertySet(c));
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));
1597 return ret;
1598 }
1599 LHF_EVICTION(else if (is_evicted(result.get())) {
1600 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1601 return Index(result.get());
1602 })
1603 else {
1604 LHF_PERF_INC(property_sets, hits);
1605 return Index(result.get());
1606 }
1607 }
1608
1609 template <bool disable_integrity_check = false>
1610 Index register_set(const PropertySet &c, bool &cold) {
1611 __lhf_calc_functime(stat);
1612
1613 if (!disable_integrity_check) {
1615 }
1616
1617 auto result = property_set_map.find(&c);
1618
1619 if (!result.is_present()) {
1620 LHF_PERF_INC(property_sets, cold_misses);
1621
1622 PropertySetHolder new_set(new PropertySet(c));
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));
1625
1626 cold = true;
1627 return ret;
1628 }
1629 LHF_EVICTION(else if (is_evicted(result.get())) {
1630 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1631 cold = false;
1632 return Index(result.get());
1633 })
1634 else {
1635 LHF_PERF_INC(property_sets, hits);
1636 cold = false;
1637 return Index(result.get());
1638 }
1639 }
1640
1641 template <bool disable_integrity_check = false>
1643 __lhf_calc_functime(stat);
1644
1645 if (!disable_integrity_check) {
1647 }
1648
1649 auto result = property_set_map.find(&c);
1650
1651 if (!result.is_present()) {
1652 LHF_PERF_INC(property_sets, cold_misses);
1653
1654 PropertySetHolder new_set(new PropertySet(c));
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));
1657 return ret;
1658 }
1659 LHF_EVICTION(else if (is_evicted(result.get())) {
1660 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1661 return Index(result.get());
1662 })
1663 else {
1664 LHF_PERF_INC(property_sets, hits);
1665 return Index(result.get());
1666 }
1667 }
1668
1669 template <bool disable_integrity_check = false>
1670 Index register_set(PropertySet &&c, bool &cold) {
1671 __lhf_calc_functime(stat);
1672
1673 if (!disable_integrity_check) {
1675 }
1676
1677 auto result = property_set_map.find(&c);
1678
1679 if (!result.is_present()) {
1680 LHF_PERF_INC(property_sets, cold_misses);
1681
1682 PropertySetHolder new_set(new PropertySet(c));
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));
1685
1686 cold = true;
1687 return ret;
1688 }
1689 LHF_EVICTION(else if (is_evicted(result.get())) {
1690 property_sets.at_mutable(result.get()).reassign(new PropertySet(c));
1691 cold = false;
1692 return Index(result.get());
1693 })
1694 else {
1695 LHF_PERF_INC(property_sets, hits);
1696 cold = false;
1697 return Index(result.get());
1698 }
1699 }
1700
1701 template<typename Iterator, bool disable_integrity_check = false>
1702 Index register_set(Iterator begin, Iterator end) {
1703 __lhf_calc_functime(stat);
1704
1705 PropertySetHolder new_set(new PropertySet(begin, end));
1706
1707 if (!disable_integrity_check) {
1709 }
1710
1711 auto result = property_set_map.find(new_set.get());
1712
1713 if (!result.is_present()) {
1714 LHF_PERF_INC(property_sets, cold_misses);
1715
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));
1718 return ret;
1719 }
1720 LHF_EVICTION(else if (is_evicted(result.get())) {
1721 property_sets.at_mutable(result.get()).reassign(std::move(new_set));
1722 return Index(result.get());
1723 })
1724 else {
1725 LHF_PERF_INC(property_sets, hits);
1726 return Index(result.get());
1727 }
1728 }
1729
1730 template<typename Iterator, bool disable_integrity_check = false>
1731 Index register_set(Iterator begin, Iterator end, bool &cold) {
1732 __lhf_calc_functime(stat);
1733
1734 PropertySetHolder new_set(new PropertySet(begin, end));
1735
1736 if (!disable_integrity_check) {
1738 }
1739
1740 auto result = property_set_map.find(new_set.get());
1741
1742 if (!result.is_present()) {
1743 LHF_PERF_INC(property_sets, cold_misses);
1744
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));
1747 cold = true;
1748 return ret;
1749 }
1750 LHF_EVICTION(else if (is_evicted(result.get())) {
1751 property_sets.at_mutable(result.get()).reassign(std::move(new_set));
1752 cold = false;
1753 return Index(result.get());
1754 })
1755 else {
1756 LHF_PERF_INC(property_sets, hits);
1757 cold = false;
1758 return Index(result.get());
1759 }
1760 }
1761
1762#ifdef LHF_ENABLE_EVICTION
1763 bool is_evicted(const Index &index) const {
1764 return property_sets.at(index.value).is_evicted();
1765 }
1766#endif
1767
1768#ifdef LHF_ENABLE_EVICTION
1769 void evict_set(const Index &index) {
1770#ifdef LHF_DEBUG
1771 if (index.is_empty()) {
1772 throw AssertError("Tried to evict the empty set");
1773 }
1774#endif
1775 property_sets.at_mutable(index.value).evict();
1776 }
1777#endif
1778
1786 inline const PropertySet &get_value(const Index &index) const {
1788#if defined(LHF_DEBUG) && defined(LHF_ENABLE_EVICTION)
1789 if (is_evicted(index)) {
1790 throw AssertError("Tried to access and evicted set");
1791 }
1792#endif
1793 return *property_sets.at(index.value).get();
1794 }
1795
1802 inline Size property_set_count() const {
1803 return property_sets.size();
1804 }
1805
1813 inline Size size_of(const Index &index) const {
1814 if (index == EMPTY_SET_VALUE) {
1815 return 0;
1816 } else {
1817 return get_value(index).size();
1818 }
1819 }
1820
1830 static inline bool less(const PropertyElement &a, const PropertyElement &b) {
1831 return a < b;
1832 }
1833
1834 static inline bool less_key(const PropertyElement &a, const PropertyT &b) {
1835 return PropertyLess()(a.get_key(), b);
1836 }
1837
1838 static inline bool less_key(const PropertyElement &a, const PropertyElement &b) {
1839 return PropertyLess()(a.get_key(), b.get_key());
1840 }
1841
1851 static inline bool equal(const PropertyElement &a, const PropertyElement &b) {
1852 return a == b;
1853 }
1854
1855 static inline bool equal_key(const PropertyElement &a, const PropertyT &b) {
1856 return PropertyEqual()(a.get_key(), b);
1857 }
1858
1859 static inline bool equal_key(const PropertyElement &a, const PropertyElement &b) {
1860 return PropertyEqual()(a.get_key(), b.get_key());
1861 }
1862
1873 inline OptionalRef<PropertyElement> find_key(const Index &index, const PropertyT &p) const {
1874 if (is_empty(index)) {
1876 }
1877
1878 const PropertySet &s = get_value(index);
1879
1881 for (const PropertyElement &i : s) {
1882 if (equal_key(i, p)) {
1884 }
1885 }
1886 } else {
1887 // Binary search implementation
1888 long int low = 0;
1889 long int high = s.size() - 1;
1890
1891 while (low <= high) {
1892 long int mid = low + (high - low) / 2;
1893
1894 if (equal_key(s[mid], p)) {
1895 return OptionalRef<PropertyElement>(s[mid]);
1896 } else if (less_key(s[mid], p)) {
1897 low = mid + 1;
1898 } else {
1899 high = mid - 1;
1900 }
1901 }
1902 }
1903
1905 }
1906
1916 inline bool contains(const Index &index, const PropertyElement &prop) const {
1917 if (is_empty(index)) {
1918 return false;
1919 }
1920
1921 const PropertySet &s = get_value(index);
1922
1924 for (PropertyElement i : s) {
1925 if (equal_key(i, prop)) {
1926 return true;
1927 }
1928 }
1929 } else {
1930 // Binary search implementation
1931 long int low = 0;
1932 long int high = s.size() - 1;
1933
1934 while (low <= high) {
1935 long int mid = low + (high - low) / 2;
1936 if (equal_key(s[mid], prop)) {
1937 return true;
1938 } else if (less_key(s[mid], prop)) {
1939 low = mid + 1;
1940 } else {
1941 high = mid - 1;
1942 }
1943 }
1944 }
1945
1946 return false;
1947 }
1948
1959 Index set_union(const Index &_a, const Index &_b) {
1961 __lhf_calc_functime(stat);
1962
1963 if (_a == _b) {
1964 LHF_PERF_INC(unions, equal_hits);
1965 return Index(_a);
1966 }
1967
1968 if (is_empty(_a)) {
1969 LHF_PERF_INC(unions, empty_hits);
1970 return Index(_b);
1971 } else if (is_empty(_b)) {
1972 LHF_PERF_INC(unions,empty_hits);
1973 return Index(_a);
1974 }
1975
1976 const Index &a = std::min(_a, _b);
1977 const Index &b = std::max(_a, _b);
1978
1979 SubsetRelation r = is_subset(a, b);
1980
1981 if (r == SUBSET) {
1982 LHF_PERF_INC(unions, subset_hits);
1983 return Index(b);
1984 } else if (r == SUPERSET) {
1985 LHF_PERF_INC(unions, subset_hits);
1986 return Index(a);
1987 }
1988
1989 auto result = unions.find({a.value, b.value});
1990
1991 if (!result.is_present() LHF_EVICTION(|| is_evicted(result.get()))) {
1992 PropertySet new_set;
1993 const PropertySet &first = get_value(a);
1994 const PropertySet &second = get_value(b);
1995
1996 // The union implementation here is adapted from the example
1997 // suggested implementation provided of std::set_union from
1998 // cppreference.com
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();
2003
2004 while (cursor_1 != cursor_end_1) {
2005 if (cursor_2 == cursor_end_2) {
2006 LHF_PUSH_RANGE(new_set, cursor_1, cursor_end_1);
2007 break;
2008 }
2009
2010 if (less(*cursor_2, *cursor_1)) {
2011 LHF_PUSH_ONE(new_set, *cursor_2);
2012 cursor_2++;
2013 } else {
2014 if (!(less(*cursor_1, *cursor_2))) {
2015 if constexpr (Nesting::is_nested) {
2016 PropertyElement new_elem =
2018 set_union, reflist, *cursor_1, *cursor_2);
2019 LHF_PUSH_ONE(new_set, new_elem);
2020 } else {
2021 LHF_PUSH_ONE(new_set, *cursor_1);
2022 }
2023 cursor_2++;
2024 } else {
2025 LHF_PUSH_ONE(new_set, *cursor_1);
2026 }
2027 cursor_1++;
2028 }
2029 }
2030
2031 LHF_PUSH_RANGE(new_set, cursor_2, cursor_end_2);
2032
2033 bool cold = false;
2034 Index ret;
2035
2036 LHF_EVICTION(if (result.is_present() && is_evicted(result.get())) {
2037 ret = result.get();
2038 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2039 } else) {
2040 ret = LHF_REGISTER_SET_INTERNAL(std::move(new_set), cold);
2041
2042 unions.insert({{a.value, b.value}, ret.value});
2043
2044 if (ret == a) {
2045 store_subset(b, ret);
2046 } else if (ret == b) {
2047 store_subset(a, ret);
2048 } else {
2049 store_subset(a, ret);
2050 store_subset(b, ret);
2051 }
2052 }
2053
2054 if (cold) {
2055 LHF_PERF_INC(unions, cold_misses);
2056 } else {
2057 LHF_PERF_INC(unions, edge_misses);
2058 }
2059
2060 return Index(ret);
2061 } else {
2062 LHF_PERF_INC(unions, hits);
2063 return Index(result.get());
2064 }
2065 }
2066
2078 return set_union(a, register_set_single(b));
2079 }
2080
2090 LHF_BINARY_NESTED_OPERATION(set_difference)
2091 Index set_difference(const Index &a, const Index &b) {
2093 __lhf_calc_functime(stat);
2094
2095 if (a == b) {
2096 LHF_PERF_INC(differences, equal_hits);
2097 return Index(EMPTY_SET_VALUE);
2098 }
2099
2100 if (is_empty(a)) {
2101 LHF_PERF_INC(differences, empty_hits);
2102 return Index(EMPTY_SET_VALUE);
2103 } else if (is_empty(b)) {
2104 LHF_PERF_INC(differences, empty_hits);
2105 return Index(a);
2106 }
2107
2108 auto result = differences.find({a.value, b.value});
2109
2110 if (!result.is_present() LHF_EVICTION(|| is_evicted(result.get()))) {
2111 PropertySet new_set;
2112 const PropertySet &first = get_value(a);
2113 const PropertySet &second = get_value(b);
2114
2115 // The difference implementation here is adapted from the example
2116 // suggested implementation provided of std::set_difference from
2117 // cppreference.com
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();
2122
2123 while (cursor_1 != cursor_end_1) {
2124 if (cursor_2 == cursor_end_2) {
2125 LHF_PUSH_RANGE(new_set, cursor_1, cursor_end_1);
2126 break;
2127 }
2128
2129 if (less(*cursor_1, *cursor_2)) {
2130 LHF_PUSH_ONE(new_set, *cursor_1);
2131 cursor_1++;
2132 } else {
2133 if (!(less(*cursor_2, *cursor_1))) {
2134 if constexpr (Nesting::is_nested) {
2135 PropertyElement new_elem =
2137 set_difference, reflist, *cursor_1, *cursor_2);
2138 LHF_PUSH_ONE(new_set, new_elem);
2139 }
2140 cursor_1++;
2141 }
2142 cursor_2++;
2143 }
2144 }
2145
2146 bool cold = false;
2147 Index ret;
2148
2149 LHF_EVICTION(if (result.is_present() && is_evicted(result.get())) {
2150 ret = result.get();
2151 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2152 } else) {
2153 ret = LHF_REGISTER_SET_INTERNAL(std::move(new_set), cold);
2154 differences.insert({{a.value, b.value}, ret.value});
2155
2156 if (ret != a) {
2157 store_subset(ret, a);
2158 } else {
2159 intersections.insert({
2160 {
2161 std::min(a.value, b.value),
2162 std::max(a.value, b.value)
2163 }, EMPTY_SET_VALUE});
2164 }
2165 }
2166
2167 if (cold) {
2168 LHF_PERF_INC(differences, cold_misses);
2169 } else {
2170 LHF_PERF_INC(differences, edge_misses);
2171 }
2172
2173 return Index(ret);
2174 } else {
2175 LHF_PERF_INC(differences, hits);
2176 return Index(result.get());
2177 }
2178 }
2179
2191 return set_difference(a, register_set_single(b));
2192 }
2193
2203 Index set_remove_single_key(const Index &a, const PropertyT &p) {
2204 PropertySet new_set;
2205 const PropertySet &first = get_value(a);
2206
2207 auto cursor_1 = first.begin();
2208 const auto &cursor_end_1 = first.end();
2209
2210 for (;cursor_1 != cursor_end_1; cursor_1++) {
2211 if (!PropertyEqual()(cursor_1->get_key(), p)) {
2212 LHF_PUSH_ONE(new_set, *cursor_1);
2213 }
2214 }
2215 return register_set<true>(std::move(new_set));
2216 }
2217
2227 LHF_BINARY_NESTED_OPERATION(set_intersection)
2228 Index set_intersection(const Index &_a, const Index &_b) {
2230 __lhf_calc_functime(stat);
2231
2232 if (_a == _b) {
2233 LHF_PERF_INC(intersections, equal_hits);
2234 return Index(_a);
2235 }
2236
2237 if (is_empty(_a) || is_empty(_b)) {
2238 LHF_PERF_INC(intersections, empty_hits);
2239 return Index(EMPTY_SET_VALUE);
2240 }
2241
2242 const Index &a = std::min(_a, _b);
2243 const Index &b = std::max(_a, _b);
2244
2245 SubsetRelation r = is_subset(a, b);
2246
2247 if (r == SUBSET) {
2248 LHF_PERF_INC(intersections, subset_hits);
2249 return Index(a);
2250 } else if (r == SUPERSET) {
2251 LHF_PERF_INC(intersections, subset_hits);
2252 return Index(b);
2253 }
2254
2255 auto result = intersections.find({a.value, b.value});
2256
2257 if (!result.is_present() LHF_EVICTION(|| is_evicted(result.get()))) {
2258 PropertySet new_set;
2259 const PropertySet &first = get_value(a);
2260 const PropertySet &second = get_value(b);
2261
2262 // The intersection implementation here is adapted from the example
2263 // suggested implementation provided for std::set_intersection from
2264 // cppreference.com
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();
2269
2270 while (cursor_1 != cursor_end_1 && cursor_2 != cursor_end_2)
2271 {
2272 if (less(*cursor_1,*cursor_2)) {
2273 cursor_1++;
2274 } else {
2275 if (!(less(*cursor_2, *cursor_1))) {
2276 if constexpr (Nesting::is_nested) {
2277 PropertyElement new_elem =
2278 LHF_PERFORM_BINARY_NESTED_OPERATION(set_intersection, reflist, *cursor_1, *cursor_2);
2279 LHF_PUSH_ONE(new_set, new_elem);
2280 } else {
2281 LHF_PUSH_ONE(new_set, *cursor_1);
2282 }
2283 cursor_1++;
2284 }
2285 cursor_2++;
2286 }
2287 }
2288
2289 bool cold = false;
2290 Index ret;
2291
2292 LHF_EVICTION(if (result.is_present() && is_evicted(result.get())) {
2293 ret = result.get();
2294 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2295 } else){
2296 ret = LHF_REGISTER_SET_INTERNAL(std::move(new_set), cold);
2297 intersections.insert({{a.value, b.value}, ret.value});
2298
2299 if (ret != a) {
2300 store_subset(ret, a);
2301 } else if (ret != b) {
2302 store_subset(ret, b);
2303 } else {
2304 store_subset(ret, a);
2305 store_subset(ret, b);
2306 }
2307 }
2308
2309 if (cold) {
2310 LHF_PERF_INC(intersections, cold_misses);
2311 } else {
2312 LHF_PERF_INC(intersections, edge_misses);
2313 }
2314 return Index(ret);
2315 }
2316
2317 LHF_PERF_INC(intersections, hits);
2318 return Index(result.get());
2319 }
2320
2321
2343 Index s,
2344 std::function<bool(const PropertyElement &)> filter_func,
2345 UnaryOperationMap &cache) {
2347 __lhf_calc_functime(stat);
2348
2349 if (is_empty(s)) {
2350 return s;
2351 }
2352
2353 auto result = cache.find(s.value);
2354
2355 if (!result.is_present() LHF_EVICTION(|| is_evicted(result.get()))) {
2356 PropertySet new_set;
2357 for (const PropertyElement &value : get_value(s)) {
2358 if (filter_func(value)) {
2359 LHF_PUSH_ONE(new_set, value);
2360 }
2361 }
2362
2363 bool cold;
2364 Index ret;
2365
2366 LHF_EVICTION(if (result.is_present() && is_evicted(result.get())) {
2367 ret = result.get();
2368 property_sets.at_mutable(ret).reassign(new PropertySet(std::move(new_set)));
2369 } else) {
2370 ret = LHF_REGISTER_SET_INTERNAL(std::move(new_set), cold);
2371 cache.insert(std::make_pair(s.value, ret.value));
2372 }
2373
2374 if (cold) {
2375 LHF_PERF_INC(filter, cold_misses);
2376 } else {
2377 LHF_PERF_INC(filter, edge_misses);
2378 }
2379
2380 return Index(ret);
2381 } else {
2382 LHF_PERF_INC(filter, hits);
2383 return Index(result.get());
2384 }
2385 }
2386
2395 std::stringstream s;
2396 s << "{ ";
2397 for (const PropertyElement &p : set) {
2398 s << p.to_string() << " ";
2399 }
2400 s << "}";
2401
2402 return s.str();
2403 }
2404
2406 return property_set_to_string(get_value(idx));
2407 }
2408
2412 String dump() const {
2413 std::stringstream s;
2414
2415 s << "{\n";
2416
2417 s << " " << "Unions: " << "(Count: " << unions.size() << ")\n";
2418 s << unions.to_string();
2419 s << "\n";
2420
2421 s << " " << "Differences:" << "(Count: " << differences.size() << ")\n";
2422 s << differences.to_string();
2423 s << "\n";
2424
2425 s << " " << "Intersections: " << "(Count: " << intersections.size() << ")\n";
2426 s << intersections.to_string();
2427 s << "\n";
2428
2429 s << " " << "Subsets: " << "(Count: " << subsets.size() << ")\n";
2430 for (auto i : subsets) {
2431 s << " " << i.first << " -> " << (i.second == SUBSET ? "sub" : "sup") << "\n";
2432 }
2433 s << "\n";
2434
2435 s << " " << "PropertySets: " << "(Count: " << property_sets.size() << ")\n";
2436 for (size_t i = 0; i < property_sets.size(); i++) {
2437 s << " "
2438 << i << " : " << property_set_to_string(*property_sets.at(i).get()) << "\n";
2439 }
2440 s << "}\n";
2441
2442 return s.str();
2443 }
2444
2445 friend std::ostream& operator<<(std::ostream& os, const LatticeHashForest& obj) {
2446 os << obj.dump();
2447 return os;
2448 }
2449
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"
2463 << p.second.to_string() << "\n";
2464 }
2465 s << stat.dump();
2466 return s.str();
2467 }
2468#endif
2469
2470}; // END LatticeHashForest
2471
2486template <
2487 typename PropertyT,
2488 typename PropertyLess = DefaultLess<PropertyT>,
2489 typename PropertyHash = DefaultHash<PropertyT>,
2490 typename PropertyEqual = DefaultEqual<PropertyT>,
2491 typename PropertyPrinter = DefaultPrinter<PropertyT>>
2497 struct Index {
2499
2500 Index(IndexValue idx = EMPTY_SET_VALUE): value(idx) {}
2501
2502 bool empty() const {
2503 return value == EMPTY_SET_VALUE;
2504 }
2505
2506 bool operator==(const Index &b) const {
2507 return value == b.value;
2508 }
2509
2510 bool operator!=(const Index &b) const {
2511 return value != b.value;
2512 }
2513
2514 bool operator<(const Index &b) const {
2515 return value < b.value;
2516 }
2517
2518 bool operator>(const Index &b) const {
2519 return value > b.value;
2520 }
2521 };
2522
2523
2525 std::unordered_map<
2526 PropertyT *, IndexValue,
2527 PropertyHash,
2528 PropertyEqual>;
2529
2530 // The property storage array.
2532
2533 // The property -> Index in storage array mapping.
2534 PropertyMap property_map = {};
2535
2546 Index register_value(const PropertyT &c) {
2547
2548 UniquePointer<PropertyT> new_value =
2549 UniquePointer<PropertyT>(new PropertyT{c});
2550
2551 auto cursor = property_map.find(new_value.get());
2552
2553 if (cursor == property_map.end()) {
2554 // LHF_PERF_INC(property_sets, cold_misses);
2555 property_list.push_back(std::move(new_value));
2556 IndexValue ret = property_list.size() - 1;
2557 property_map.insert(std::make_pair(property_list[ret].get(), ret));
2558 return Index(ret);
2559 }
2560
2561 // LHF_PERF_INC(property_sets, hits);
2562 return Index(cursor->second);
2563 }
2564
2565};
2566
2567}; // END NAMESPACE
2568
2569#endif
Index push_back(PropertySetHolder &&p)
Definition lhf.hpp:1412
const PropertySetHolder & at(const Index &idx) const
Definition lhf.hpp:1408
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...
Definition lhf.hpp:1404
The main LatticeHashForest structure. This class can be used as-is with a type or derived for additio...
Definition lhf.hpp:1099
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 "...
Definition lhf.hpp:1830
Index register_set(const PropertySet &c)
Definition lhf.hpp:1582
Index register_set(const PropertySet &c, bool &cold)
Definition lhf.hpp:1610
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 ...
Definition lhf.hpp:2190
bool contains(const Index &index, const PropertyElement &prop) const
Determines whether the property set at index contains the element prop or not.
Definition lhf.hpp:1916
LatticeHashForest(RefList reflist={})
Definition lhf.hpp:1457
static bool equal(const PropertyElement &a, const PropertyElement &b)
Equality comparator for operations. You MUST use this instead of directly using anything else like "<...
Definition lhf.hpp:1851
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
Definition lhf.hpp:1443
static bool less_key(const PropertyElement &a, const PropertyT &b)
Definition lhf.hpp:1834
Index register_set(PropertySet &&c, bool &cold)
Definition lhf.hpp:1670
static bool less_key(const PropertyElement &a, const PropertyElement &b)
Definition lhf.hpp:1838
String property_set_to_string(const Index &idx) const
Definition lhf.hpp:2405
Index register_set_single(const PropertyElement &c)
Inserts a (or gets an existing) single-element set into property set storage.
Definition lhf.hpp:1497
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...
Definition lhf.hpp:2342
OptionalRef< PropertyElement > find_key(const Index &index, const PropertyT &p) const
Finds a property element in the set based on the key provided.
Definition lhf.hpp:1873
Index register_set(Iterator begin, Iterator end)
Definition lhf.hpp:1702
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.
Definition lhf.hpp:1475
Index register_set(PropertySet &&c)
Definition lhf.hpp:1642
String dump_perf() const
Dumps performance information as a string.
Definition lhf.hpp:2458
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 ...
Definition lhf.hpp:2077
bool is_empty(const Index &i) const
Definition lhf.hpp:1462
typename Nesting::template PropertyElement< PropertyLess, PropertyHash, PropertyEqual, PropertyPrinter > PropertyElement
Definition lhf.hpp:1155
static String property_set_to_string(const PropertySet &set)
Converts the property set to a string.
Definition lhf.hpp:2394
const PropertySet & get_value(const Index &index) const
Gets the actual property set specified by index.
Definition lhf.hpp:1786
Index set_remove_single_key(const Index &a, const PropertyT &p)
Removes a single element from a given set if the "key" element matches.
Definition lhf.hpp:2203
std::vector< PropertyElement > PropertySet
Definition lhf.hpp:1161
typename Nesting::LHFReferenceList RefList
Definition lhf.hpp:1216
static bool equal_key(const PropertyElement &a, const PropertyT &b)
Definition lhf.hpp:1855
Index register_set(Iterator begin, Iterator end, bool &cold)
Definition lhf.hpp:1731
static bool equal_key(const PropertyElement &a, const PropertyElement &b)
Definition lhf.hpp:1859
void prepare_vector_set(PropertySet &c)
Definition lhf.hpp:1567
PerformanceStatistics stat
Definition lhf.hpp:1222
Size size_of(const Index &index) const
Returns the size of the set at index
Definition lhf.hpp:1813
Size property_set_count() const
Returns the total number of property sets currently in the LHF.
Definition lhf.hpp:1802
HashMap< String, OperationPerf > perf
Definition lhf.hpp:1223
friend std::ostream & operator<<(std::ostream &os, const LatticeHashForest &obj)
Definition lhf.hpp:2445
String dump() const
Dumps the current state of the LHF to a string.
Definition lhf.hpp:2412
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...
Definition lhf.hpp:1532
void insert(KeyValuePair &&v)
Definition lhf.hpp:750
Optional< MappedType > find(const Key &key) const
Definition lhf.hpp:740
Size size() const
Definition lhf.hpp:755
Map::const_iterator end() const
Definition lhf.hpp:764
Map::const_iterator begin() const
Definition lhf.hpp:760
typename Map::value_type KeyValuePair
Definition lhf.hpp:733
typename Map::key_type Key
Definition lhf.hpp:731
MapClass Map
Definition lhf.hpp:730
String to_string() const
Definition lhf.hpp:768
typename Map::mapped_type MappedType
Definition lhf.hpp:732
Describes an optional reference of some type T. The value may either be present or absent.
Definition lhf.hpp:115
bool is_present() const
Informs if the value is present.
Definition lhf.hpp:128
const T & get()
Gets the underlying value. Throws an exception if it is absent.
Definition lhf.hpp:133
static OptionalRef absent()
Explicitly creates an absent value.
Definition lhf.hpp:123
OptionalRef(const T &value)
Definition lhf.hpp:120
Describes an optional of some type T. The value may either be present or absent.
Definition lhf.hpp:150
Optional(const T &value)
Definition lhf.hpp:157
static Optional absent()
Explicitly creates an absent value.
Definition lhf.hpp:160
const T & get()
Gets the underlying value. Throws an exception if it is absent.
Definition lhf.hpp:170
bool is_present()
Informs if the value is present.
Definition lhf.hpp:165
#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...
Definition lhf.hpp:838
#define LHF_PROPERTY_SET_INDEX_VALID(__index)
Check whether the index is a valid index within the property set.
Definition lhf.hpp:467
#define LHF_PROPERTY_SET_INTEGRITY_VALID(__set)
Macro and switch for verify_property_set_integrity inside LHF.
Definition lhf.hpp:440
#define LHF_PUSH_RANGE(__cont, __start, __end)
Pushes a range of elements to a PropertySet using an iterator. Use this when implementing operations.
Definition lhf.hpp:528
#define LHF_PERF_INC(__oper, __category)
Increments the invocation count of the given category and operator.
Definition lhf.hpp:1066
#define LHF_PROPERTY_SET_PAIR_UNEQUAL(__index1, __index2)
Check whether the pair of indexes are unequal. Used for sanity checking.
Definition lhf.hpp:482
#define LHF_PROPERTY_SET_PAIR_VALID(__index1, __index2)
Check whether the pair of indexes is a valid within the property set.
Definition lhf.hpp:477
#define LHF_PARALLEL(__x)
Definition lhf.hpp:498
#define LHF_PUSH_ONE(__cont, __val)
Pushes one element to a PropertySet. Use this when implementing operations.
Definition lhf.hpp:516
#define LHF_BINARY_NESTED_OPERATION(__op_name)
Declares a struct that enables the recursive/nesting behaviour of an operation.
Definition lhf.hpp:819
#define LHF_EVICTION(__x)
Definition lhf.hpp:504
#define LHF_REGISTER_SET_INTERNAL(__set, __cold)
Registers a set with behaviours defined for internal processing.
Definition lhf.hpp:538
Any configurable constants go into this file.
#define LHF_SORTED_VECTOR_BINARY_SEARCH_THRESHOLD
Definition lhf_config.hpp:9
#define LHF_DEFAULT_BLOCK_SIZE
#define LHF_DEFAULT_BLOCK_MASK
Definition lhf.hpp:40
Size compose_hash(const Size prev, T next)
Composes a preexisting hash with another variable. Useful for Hashing containers. Adapted from boost:...
Definition lhf.hpp:209
std::vector< T > Vector
Definition lhf.hpp:68
std::ostream & operator<<(std::ostream &os, const OperationNode &op)
Definition lhf.hpp:236
std::equal_to< T > DefaultEqual
Definition lhf.hpp:89
std::set< T > OrderedSet
Definition lhf.hpp:80
std::unordered_map< K, V > HashMap
Definition lhf.hpp:71
std::unordered_set< T > HashSet
Definition lhf.hpp:77
std::map< K, V > OrderedMap
Definition lhf.hpp:74
std::unique_ptr< T > UniquePointer
Definition lhf.hpp:65
std::size_t Size
Definition lhf.hpp:48
Size IndexValue
Definition lhf.hpp:62
std::hash< T > DefaultHash
Definition lhf.hpp:86
SubsetRelation
Used to store a subset relation between two set indices. Because the index pair must be in sorted ord...
Definition lhf.hpp:185
@ UNKNOWN
Definition lhf.hpp:186
@ SUBSET
Definition lhf.hpp:187
@ SUPERSET
Definition lhf.hpp:188
std::less< T > DefaultLess
Definition lhf.hpp:83
std::string String
Definition lhf.hpp:50
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.
Definition lhf.hpp:103
AbsentValueAccessError(const std::string &message)
Definition lhf.hpp:104
Struct that is thrown on an assertion failure.
Definition lhf.hpp:384
AssertError(const std::string &message)
Definition lhf.hpp:385
Index returned by an operation. The struct ensures type safety and possible future extensions.
Definition lhf.hpp:2497
bool operator>(const Index &b) const
Definition lhf.hpp:2518
bool operator!=(const Index &b) const
Definition lhf.hpp:2510
bool empty() const
Definition lhf.hpp:2502
bool operator==(const Index &b) const
Definition lhf.hpp:2506
Index(IndexValue idx=EMPTY_SET_VALUE)
Definition lhf.hpp:2500
bool operator<(const Index &b) const
Definition lhf.hpp:2514
An LHF-like structure for scalar values. It does not implement any special operations besides dedupli...
Definition lhf.hpp:2492
Index register_value(const PropertyT &c)
Inserts a (or gets an existing) element into property storage.
Definition lhf.hpp:2546
std::unordered_map< PropertyT *, IndexValue, PropertyHash, PropertyEqual > PropertyMap
Definition lhf.hpp:2528
String operator()(T x)
Definition lhf.hpp:93
Size operator()(const Index &idx) const
Definition lhf.hpp:1140
Index returned by an operation. Being defined inside the class ensures type safety and possible futur...
Definition lhf.hpp:1105
Index(IndexValue idx=EMPTY_SET_VALUE)
Definition lhf.hpp:1108
friend std::ostream & operator<<(std::ostream &os, const Index &obj)
Definition lhf.hpp:1134
String to_string() const
Definition lhf.hpp:1130
bool operator!=(const Index &b) const
Definition lhf.hpp:1118
bool operator==(const Index &b) const
Definition lhf.hpp:1114
bool operator>(const Index &b) const
Definition lhf.hpp:1126
bool operator<(const Index &b) const
Definition lhf.hpp:1122
UniquePointer< PropertySet > PtrContainer
Definition lhf.hpp:1227
typename PtrContainer::pointer Ptr
Definition lhf.hpp:1228
This forces a comparison of both the key and the value instead of only the key. Required in instances...
Definition lhf.hpp:1009
bool operator()(const PropertyElement &a, const PropertyElement &b) const
Definition lhf.hpp:1010
Size operator()(const PropertyElement &p) const
Definition lhf.hpp:998
Type for the elements for a property set in the nested. The template arguments are for the 'key' type...
Definition lhf.hpp:878
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...
Definition lhf.hpp:935
PropertyElement(const PropertyT &key, const ChildValueList &value)
Definition lhf.hpp:891
PropertyT InterfaceKeyType
Key type is made available here if required by user.
Definition lhf.hpp:881
PropertyT InterfaceValueType
Value type is made available here if required by user.
Definition lhf.hpp:884
const PropertyT & get_key() const
Gets the 'key' value.
Definition lhf.hpp:902
bool operator<(const PropertyElement &b) const
Definition lhf.hpp:972
const ChildValueList & get_value() const
Gets the nested value. It returns a tuple of values containing indices to each of the nested sets of ...
Definition lhf.hpp:914
friend std::ostream & operator<<(std::ostream &os, const PropertyElement &obj)
Definition lhf.hpp:992
PropertyElement apply(const LHFReferenceList &lhf, const PropertyElement &arg) const
Performs the "apply" operation on the list of nested children specified by the Operation parameter.
Definition lhf.hpp:960
bool operator==(const PropertyElement &b) const
Definition lhf.hpp:976
Describes the standard nesting structure. Act as "non-leaf" nodes in a tree of nested LHFs.
Definition lhf.hpp:849
std::tuple< typename ChildT::Index... > ChildValueList
Definition lhf.hpp:862
std::tuple< ChildT &... > LHFReferenceList
Reference list. References to all the nested LHFs are presented here.
Definition lhf.hpp:858
Placeholder value to mark the reference lists and value lists as empty.
Definition lhf.hpp:555
This forces a comparison of both the key and the value instead of only the key. Required in instances...
Definition lhf.hpp:654
bool operator()(const PropertyElement &a, const PropertyElement &b) const
Definition lhf.hpp:655
Size operator()(const PropertyElement &p) const
Definition lhf.hpp:640
Base-case type for the elements for a property set. The template arguments are for the 'key' type.
Definition lhf.hpp:579
PropertyElement(const PropertyT &value)
Definition lhf.hpp:591
PropertyT InterfaceValueType
Value type is made available here if required by user.
Definition lhf.hpp:585
bool operator==(const PropertyElement &b) const
Definition lhf.hpp:626
const PropertyT & get_key() const
Gets the 'key' value.
Definition lhf.hpp:598
bool operator<(const PropertyElement &b) const
Definition lhf.hpp:622
PropertyElement apply() const
Performs an "apply" operation. In the base case it is an identity operation and does not do anything.
Definition lhf.hpp:618
PropertyT InterfaceKeyType
Key type is made available here if required by user.
Definition lhf.hpp:582
friend std::ostream & operator<<(std::ostream &os, const PropertyElement &obj)
Definition lhf.hpp:634
const PropertyT & get_value() const
Gets the nested value. In the base case it simply returns the key.
Definition lhf.hpp:608
The nesting type for non-nested data structures. Act as "leaf" nodes in a tree of nested LHFs.
Definition lhf.hpp:547
static constexpr bool is_nested
Compile-time value that says this is not nested.
Definition lhf.hpp:549
static constexpr Size num_children
Compile-time value that says there are no nested children.
Definition lhf.hpp:552
This struct contains the information about the operands of an operation (union, intersection,...
Definition lhf.hpp:217
IndexValue right
Definition lhf.hpp:219
std::string to_string() const
Definition lhf.hpp:221
bool operator<(const OperationNode &op) const
Definition lhf.hpp:227
IndexValue left
Definition lhf.hpp:218
bool operator==(const OperationNode &op) const
Definition lhf.hpp:231
Operation performance Statistics.
Definition lhf.hpp:1020
String to_string() const
Definition lhf.hpp:1043
Utility class for enabling code-based profiling.
Definition profiling.hpp:26
Generic Equality comparator for set types.
Definition lhf.hpp:328
bool operator()(const SetT *a, const SetT *b) const
Definition lhf.hpp:329
Hasher for set types.
Definition lhf.hpp:304
Size operator()(const SetT *k) const
Definition lhf.hpp:305
Generic Less-than comparator for set types.
Definition lhf.hpp:266
bool operator()(const OrderedSetT *a, const OrderedSetT *b) const
Definition lhf.hpp:267
Thrown if code region is unreachable.
Definition lhf.hpp:392
Unreachable(const std::string &message="Hit a branch marked as unreachable.")
Definition lhf.hpp:393
lhf::Size operator()(const lhf::OperationNode &k) const
Definition lhf.hpp:246