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
46namespace ue2 {
47
48// Existence check for associative containers.
49template<typename C>
50bool contains(const C &container, const typename C::key_type &key) {
51 return container.find(key) != container.end();
52}
53
54template<typename C, typename It>
55bool 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
60template<typename C, typename It>
61void insert(C *container, const std::pair<It, It> &range) {
62 container->insert(range.first, range.second);
63}
64
65template<typename C, typename It>
66void insert(C *container, typename C::iterator pos,
67 const std::pair<It, It> &range) {
68 container->insert(pos, range.first, range.second);
69}
70
71template<typename C, typename D>
72void insert(C *container, const D &donor) {
73 container->insert(donor.begin(), donor.end());
74}
75
76template<typename C, typename D>
77void 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 */
85template <typename It>
86auto 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. */
93template <typename C, typename Compare = std::less<typename C::value_type>>
94void 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. */
102template <typename C>
103std::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 */
114template <typename T, typename Alloc>
115typename std::vector<T, Alloc>::size_type
116byte_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 */
125template<typename T, typename Alloc>
126void *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
141template<typename OrderedContainer1, typename OrderedContainer2>
142bool 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
172template<typename OrderedContainer1, typename OrderedContainer2>
173bool 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 */
198template<typename C, typename D>
199void erase_all(C *container, const D &donor) {
200 for (const auto &elem : donor) {
201 container->erase(elem);
202 }
203}
204
205
206template<typename C, typename Pred>
207bool any_of_in(const C &c, Pred p) {
208 return std::any_of(c.begin(), c.end(), std::move(p));
209}
210
211template<typename C, typename Pred>
212bool 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
223namespace ue2 {
224
225/**
226 * \brief Dump a container of stream-printable objects into a comma-separated
227 * list in a string.
228 */
229template<class C>
230std::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