MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
util.h
Go to the documentation of this file.
1#pragma once
2
3#include <queue>
4#include <stack>
5#include <type_traits>
6
7#include <absl/container/flat_hash_map.h>
8#include <absl/container/flat_hash_set.h>
9#include <absl/container/node_hash_map.h>
10#include <absl/container/node_hash_set.h>
11#include <fe/assert.h>
12
13#include "mim/util/hash.h"
14#include "mim/util/types.h"
15
16namespace mim {
17
18/// @name Utility Functions
19///@{
20
21/// A bitcast from @p src of type @p S to @p D.
22template<class D, class S>
23inline D bitcast(const S& src) {
24 D dst;
25 auto s = reinterpret_cast<const void*>(&src);
26 auto d = reinterpret_cast<void*>(&dst);
27
28 if constexpr (sizeof(D) == sizeof(S)) std::memcpy(d, s, sizeof(D));
29 if constexpr (sizeof(D) < sizeof(S)) std::memcpy(d, s, sizeof(D));
30 if constexpr (sizeof(D) > sizeof(S)) {
31 std::memset(d, 0, sizeof(D));
32 std::memcpy(d, s, sizeof(S));
33 }
34 return dst;
35}
36
37template<class T>
38bool get_sign(T val) {
39 static_assert(std::is_integral<T>(), "get_sign only supported for signed and unsigned integer types");
40 if constexpr (std::is_signed<T>())
41 return val < 0;
42 else
43 return val >> (T(sizeof(val)) * T(8) - T(1));
44}
45
46// TODO I guess we can do that with C++20 <bit>
47inline u64 pad(u64 offset, u64 align) {
48 auto mod = offset % align;
49 if (mod != 0) offset += align - mod;
50 return offset;
51}
52///@}
53
54/// @name Algorithms
55///@{
56template<class I, class T, class L>
57I binary_find(I begin, I end, T val, L lt) {
58 static_assert(std::random_access_iterator<I>);
59 I i;
60 if (std::distance(begin, end) < 16)
61 for (i = begin; i != end && lt(*i, val); ++i) {}
62 else
63 i = std::lower_bound(begin, end, val, lt);
64 return (i != end && !lt(val, *i)) ? i : end;
65}
66
67/// Like `std::string::substr`, but works on `std::string_view` instead.
68inline std::string_view subview(std::string_view s, size_t i, size_t n = std::string_view::npos) {
69 n = std::min(n, s.size());
70 return {s.data() + i, n - i};
71}
72
73/// Replaces all occurrences of @p what with @p repl.
74inline void find_and_replace(std::string& str, std::string_view what, std::string_view repl) {
75 for (size_t pos = str.find(what); pos != std::string::npos; pos = str.find(what, pos + repl.size()))
76 str.replace(pos, what.size(), repl);
77}
78///@}
79
80/// @name Helpers for Containers
81///@{
82template<class S>
83auto pop(S& s) -> decltype(s.top(), typename S::value_type()) {
84 auto val = s.top();
85 s.pop();
86 return val;
87}
88
89template<class Q>
90auto pop(Q& q) -> decltype(q.front(), typename Q::value_type()) {
91 auto val = q.front();
92 q.pop();
93 return val;
94}
95
96/// Yields pointer to element (or the element itself if it is already a pointer), if found and `nullptr` otherwise.
97/// @warning If the element is **not** already a pointer, this lookup will simply take the address of this element.
98/// This means that, e.g., a rehash of an `absl::flat_hash_map` will invalidate this pointer.
99template<class C, class K>
100auto lookup(const C& container, const K& key) {
101 auto i = container.find(key);
102 if constexpr (std::is_pointer_v<typename C::mapped_type>)
103 return i != container.end() ? i->second : nullptr;
104 else
105 return i != container.end() ? &i->second : nullptr;
106}
107
108/// Invokes `emplace` on @p container, asserts that insertion actually happened, and returns the iterator.
109template<class C, class... Args>
110auto assert_emplace(C& container, Args&&... args) {
111 auto [i, ins] = container.emplace(std::forward<Args>(args)...);
112 assert_unused(ins);
113 return i;
114}
115///@}
116
117template<class Set>
119public:
120 using T = typename std::remove_reference_t<Set>::value_type;
121
122 bool push(T val) {
123 if (done_.emplace(val).second) {
124 stack_.emplace(val);
125 return true;
126 }
127 return false;
128 }
129
130 bool empty() const { return stack_.empty(); }
131 const T& top() { return stack_.top(); }
132 T pop() { return mim::pop(stack_); }
133 void clear() {
134 done_.clear();
135 stack_ = {};
136 }
137
138private:
139 Set done_;
140 std::stack<T> stack_;
141};
142
143template<class Set>
145public:
146 using T = typename std::remove_reference_t<Set>::value_type;
147
148 unique_queue() = default;
150 : done_(set) {}
151
152 bool push(T val) {
153 if (done_.emplace(val).second) {
154 queue_.emplace(val);
155 return true;
156 }
157 return false;
158 }
159
160 bool empty() const { return queue_.empty(); }
161 T pop() { return mim::pop(queue_); }
162 T& front() { return queue_.front(); }
163 T& back() { return queue_.back(); }
164 void clear() {
165 done_.clear();
166 queue_ = {};
167 }
168
169private:
170 Set done_;
171 std::queue<T> queue_;
172};
173
174template<class T>
175struct GIDHash {
176 constexpr size_t operator()(T p) const noexcept { return hash(p->gid()); }
177};
178
179template<class T>
180struct GIDLt {
181 constexpr bool operator()(T a, T b) const noexcept { return a->gid() < b->gid(); }
182};
183
184// clang-format off
185/// @name GID
186///@{
187template<class K, class V> using GIDMap = absl::flat_hash_map<K, V, GIDHash<K>>;
188template<class K> using GIDSet = absl::flat_hash_set<K, GIDHash<K>>;
189template<class K, class V> using GIDNodeMap = absl::node_hash_map<K, V, GIDHash<K>>;
190template<class K> using GIDNodeSet = absl::node_hash_set<K, GIDHash<K>>;
191///@}
192
193} // namespace mim
bool empty() const
Definition util.h:160
unique_queue()=default
unique_queue(Set set)
Definition util.h:149
typename std::remove_reference_t< Set >::value_type T
Definition util.h:146
void clear()
Definition util.h:164
bool push(T val)
Definition util.h:152
typename std::remove_reference_t< Set >::value_type T
Definition util.h:120
const T & top()
Definition util.h:131
bool push(T val)
Definition util.h:122
bool empty() const
Definition util.h:130
void clear()
Definition util.h:133
Definition ast.h:14
auto pop(S &s) -> decltype(s.top(), typename S::value_type())
Definition util.h:83
D bitcast(const S &src)
A bitcast from src of type S to D.
Definition util.h:23
auto assert_emplace(C &container, Args &&... args)
Invokes emplace on container, asserts that insertion actually happened, and returns the iterator.
Definition util.h:110
auto lookup(const C &container, const K &key)
Yields pointer to element (or the element itself if it is already a pointer), if found and nullptr ot...
Definition util.h:100
I binary_find(I begin, I end, T val, L lt)
Definition util.h:57
absl::flat_hash_map< K, V, GIDHash< K > > GIDMap
Definition util.h:187
u64 pad(u64 offset, u64 align)
Definition util.h:47
void find_and_replace(std::string &str, std::string_view what, std::string_view repl)
Replaces all occurrences of what with repl.
Definition util.h:74
constexpr size_t hash(size_t h) noexcept
Definition hash.h:32
absl::node_hash_set< K, GIDHash< K > > GIDNodeSet
Definition util.h:190
uint64_t u64
Definition types.h:34
absl::node_hash_map< K, V, GIDHash< K > > GIDNodeMap
Definition util.h:189
bool get_sign(T val)
Definition util.h:38
absl::flat_hash_set< K, GIDHash< K > > GIDSet
Definition util.h:188
std::string_view subview(std::string_view s, size_t i, size_t n=std::string_view::npos)
Like std::string::substr, but works on std::string_view instead.
Definition util.h:68
constexpr size_t operator()(T p) const noexcept
Definition util.h:176
constexpr bool operator()(T a, T b) const noexcept
Definition util.h:181