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