1 | /* |
2 | * Copyright (c) 2015-2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | /** \file |
30 | * \brief Convenience template functions for containers. |
31 | */ |
32 | |
33 | #ifndef UTIL_CONTAINER_H |
34 | #define UTIL_CONTAINER_H |
35 | |
36 | #include "ue2common.h" |
37 | |
38 | #include <algorithm> |
39 | #include <cassert> |
40 | #include <cstring> |
41 | #include <set> |
42 | #include <type_traits> |
43 | #include <utility> |
44 | #include <vector> |
45 | |
46 | namespace ue2 { |
47 | |
48 | // Existence check for associative containers. |
49 | template<typename C> |
50 | bool contains(const C &container, const typename C::key_type &key) { |
51 | return container.find(key) != container.end(); |
52 | } |
53 | |
54 | template<typename C, typename It> |
55 | bool contains_any_of(const C &container, const std::pair<It, It> &range) { |
56 | return std::find_first_of(range.first, range.second, container.begin(), |
57 | container.end()) != range.second; |
58 | } |
59 | |
60 | template<typename C, typename It> |
61 | void insert(C *container, const std::pair<It, It> &range) { |
62 | container->insert(range.first, range.second); |
63 | } |
64 | |
65 | template<typename C, typename It> |
66 | void insert(C *container, typename C::iterator pos, |
67 | const std::pair<It, It> &range) { |
68 | container->insert(pos, range.first, range.second); |
69 | } |
70 | |
71 | template<typename C, typename D> |
72 | void insert(C *container, const D &donor) { |
73 | container->insert(donor.begin(), donor.end()); |
74 | } |
75 | |
76 | template<typename C, typename D> |
77 | void insert(C *container, typename C::iterator pos, const D &donor) { |
78 | container->insert(pos, donor.begin(), donor.end()); |
79 | } |
80 | |
81 | /** |
82 | * \brief Constructs a vector from a range bounded by the given pair of |
83 | * iterators. |
84 | */ |
85 | template <typename It> |
86 | auto make_vector_from(const std::pair<It, It> &range) |
87 | -> std::vector<decltype(*range.first)> { |
88 | using T = decltype(*range.first); |
89 | return std::vector<T>(range.first, range.second); |
90 | } |
91 | |
92 | /** \brief Sort a sequence container and remove duplicates. */ |
93 | template <typename C, typename Compare = std::less<typename C::value_type>> |
94 | void sort_and_unique(C &container, Compare comp = Compare()) { |
95 | std::sort(std::begin(container), std::end(container), comp); |
96 | container.erase(std::unique(std::begin(container), std::end(container)), |
97 | std::end(container)); |
98 | } |
99 | |
100 | /** \brief Returns a set containing the keys in the given associative |
101 | * container. */ |
102 | template <typename C> |
103 | std::set<typename C::key_type> assoc_keys(const C &container) { |
104 | std::set<typename C::key_type> keys; |
105 | for (const auto &elem : container) { |
106 | keys.insert(elem.first); |
107 | } |
108 | return keys; |
109 | } |
110 | |
111 | /** |
112 | * \brief Return the length in bytes of the given vector of (POD) objects. |
113 | */ |
114 | template <typename T, typename Alloc> |
115 | typename std::vector<T, Alloc>::size_type |
116 | byte_length(const std::vector<T, Alloc> &vec) { |
117 | static_assert(std::is_pod<T>::value, "should be pod" ); |
118 | return vec.size() * sizeof(T); |
119 | } |
120 | |
121 | /** |
122 | * \brief Copy the given vector of POD objects to the given location in memory. |
123 | * It is safe to give this function an empty vector. |
124 | */ |
125 | template<typename T, typename Alloc> |
126 | void *copy_bytes(void *dest, const std::vector<T, Alloc> &vec) { |
127 | static_assert(std::is_pod<T>::value, "should be pod" ); |
128 | assert(dest); |
129 | |
130 | // Since we're generally using this function to write into the bytecode, |
131 | // dest should be appropriately aligned for T. |
132 | assert(ISALIGNED_N(dest, alignof(T))); |
133 | |
134 | if (vec.empty()) { |
135 | return dest; // Protect memcpy against null pointers. |
136 | } |
137 | assert(vec.data() != nullptr); |
138 | return std::memcpy(dest, vec.data(), byte_length(vec)); |
139 | } |
140 | |
141 | template<typename OrderedContainer1, typename OrderedContainer2> |
142 | bool is_subset_of(const OrderedContainer1 &small, const OrderedContainer2 &big) { |
143 | static_assert(std::is_same<typename OrderedContainer1::value_type, |
144 | typename OrderedContainer2::value_type>::value, |
145 | "Both containers should have the same value_type" ); |
146 | auto sit = small.begin(); |
147 | auto bit = big.begin(); |
148 | if (small.size() > big.size()) { |
149 | return false; |
150 | } |
151 | |
152 | while (sit != small.end()) { |
153 | if (bit == big.end()) { |
154 | return false; |
155 | } |
156 | |
157 | if (*sit == *bit) { |
158 | ++sit; |
159 | ++bit; |
160 | continue; |
161 | } |
162 | if (*bit < *sit) { |
163 | ++bit; |
164 | continue; |
165 | } |
166 | |
167 | return false; |
168 | } |
169 | return true; |
170 | } |
171 | |
172 | template<typename OrderedContainer1, typename OrderedContainer2> |
173 | bool has_intersection(const OrderedContainer1 &a, const OrderedContainer2 &b) { |
174 | static_assert(std::is_same<typename OrderedContainer1::value_type, |
175 | typename OrderedContainer2::value_type>::value, |
176 | "Both containers should have the same value_type" ); |
177 | auto ait = a.begin(); |
178 | auto bit = b.begin(); |
179 | while (ait != a.end() && bit != b.end()) { |
180 | if (*ait == *bit) { |
181 | return true; |
182 | } |
183 | |
184 | if (*ait < *bit) { |
185 | ++ait; |
186 | } else { |
187 | ++bit; |
188 | } |
189 | } |
190 | |
191 | return false; |
192 | } |
193 | |
194 | /** |
195 | * \brief Erase the elements (by value) in the donor container from the given |
196 | * container. |
197 | */ |
198 | template<typename C, typename D> |
199 | void erase_all(C *container, const D &donor) { |
200 | for (const auto &elem : donor) { |
201 | container->erase(elem); |
202 | } |
203 | } |
204 | |
205 | |
206 | template<typename C, typename Pred> |
207 | bool any_of_in(const C &c, Pred p) { |
208 | return std::any_of(c.begin(), c.end(), std::move(p)); |
209 | } |
210 | |
211 | template<typename C, typename Pred> |
212 | bool all_of_in(const C &c, Pred p) { |
213 | return std::all_of(c.begin(), c.end(), std::move(p)); |
214 | } |
215 | |
216 | } // namespace ue2 |
217 | |
218 | #ifdef DUMP_SUPPORT |
219 | |
220 | #include <sstream> |
221 | #include <string> |
222 | |
223 | namespace ue2 { |
224 | |
225 | /** |
226 | * \brief Dump a container of stream-printable objects into a comma-separated |
227 | * list in a string. |
228 | */ |
229 | template<class C> |
230 | std::string as_string_list(const C &c) { |
231 | std::ostringstream oss; |
232 | for (auto it = c.begin(); it != c.end(); ++it) { |
233 | if (it != c.begin()) { |
234 | oss << ", " ; |
235 | } |
236 | oss << *it; |
237 | } |
238 | return oss.str(); |
239 | } |
240 | |
241 | } // namespace ue2 |
242 | |
243 | #endif // DUMP_SUPPORT |
244 | |
245 | #endif // UTIL_CONTAINER_H |
246 | |