1 /*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ART_LIBARTBASE_BASE_STL_UTIL_H_
18 #define ART_LIBARTBASE_BASE_STL_UTIL_H_
19
20 #include <algorithm>
21 #include <iterator>
22 #include <set>
23 #include <sstream>
24
25 #include <android-base/logging.h>
26
27 #include "base/iteration_range.h"
28
29 namespace art {
30
31 // STLDeleteContainerPointers()
32 // For a range within a container of pointers, calls delete
33 // (non-array version) on these pointers.
34 // NOTE: for these three functions, we could just implement a DeleteObject
35 // functor and then call for_each() on the range and functor, but this
36 // requires us to pull in all of algorithm.h, which seems expensive.
37 // For hash_[multi]set, it is important that this deletes behind the iterator
38 // because the hash_set may call the hash function on the iterator when it is
39 // advanced, which could result in the hash function trying to deference a
40 // stale pointer.
41 template <class ForwardIterator>
STLDeleteContainerPointers(ForwardIterator begin,ForwardIterator end)42 void STLDeleteContainerPointers(ForwardIterator begin,
43 ForwardIterator end) {
44 while (begin != end) {
45 ForwardIterator temp = begin;
46 ++begin;
47 delete *temp;
48 }
49 }
50
51 // STLDeleteElements() deletes all the elements in an STL container and clears
52 // the container. This function is suitable for use with a vector, set,
53 // hash_set, or any other STL container which defines sensible begin(), end(),
54 // and clear() methods.
55 //
56 // If container is null, this function is a no-op.
57 //
58 // As an alternative to calling STLDeleteElements() directly, consider
59 // using a container of std::unique_ptr, which ensures that your container's
60 // elements are deleted when the container goes out of scope.
61 template <class T>
STLDeleteElements(T * container)62 void STLDeleteElements(T *container) {
63 if (container != nullptr) {
64 STLDeleteContainerPointers(container->begin(), container->end());
65 container->clear();
66 }
67 }
68
69 // Given an STL container consisting of (key, value) pairs, STLDeleteValues
70 // deletes all the "value" components and clears the container. Does nothing
71 // in the case it's given a null pointer.
72 template <class T>
STLDeleteValues(T * v)73 void STLDeleteValues(T *v) {
74 if (v != nullptr) {
75 for (typename T::iterator i = v->begin(); i != v->end(); ++i) {
76 delete i->second;
77 }
78 v->clear();
79 }
80 }
81
82 // Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below.
83 struct FreeDelete {
84 // NOTE: Deleting a const object is valid but free() takes a non-const pointer.
operatorFreeDelete85 void operator()(const void* ptr) const {
86 free(const_cast<void*>(ptr));
87 }
88 };
89
90 // Alias for std::unique_ptr<> that uses the C function free() to delete objects.
91 template <typename T>
92 using UniqueCPtr = std::unique_ptr<T, FreeDelete>;
93
94 // Find index of the first element with the specified value known to be in the container.
95 template <typename Container, typename T>
IndexOfElement(const Container & container,const T & value)96 size_t IndexOfElement(const Container& container, const T& value) {
97 auto it = std::find(container.begin(), container.end(), value);
98 DCHECK(it != container.end()); // Must exist.
99 return std::distance(container.begin(), it);
100 }
101
102 // Remove the first element with the specified value known to be in the container.
103 template <typename Container, typename T>
RemoveElement(Container & container,const T & value)104 void RemoveElement(Container& container, const T& value) {
105 auto it = std::find(container.begin(), container.end(), value);
106 DCHECK(it != container.end()); // Must exist.
107 container.erase(it);
108 }
109
110 // Replace the first element with the specified old_value known to be in the container.
111 template <typename Container, typename T>
ReplaceElement(Container & container,const T & old_value,const T & new_value)112 void ReplaceElement(Container& container, const T& old_value, const T& new_value) {
113 auto it = std::find(container.begin(), container.end(), old_value);
114 DCHECK(it != container.end()); // Must exist.
115 *it = new_value;
116 }
117
118 // Search for an element with the specified value and return true if it was found, false otherwise.
119 template <typename Container, typename T>
120 bool ContainsElement(const Container& container, const T& value, size_t start_pos = 0u) {
121 DCHECK_LE(start_pos, container.size());
122 auto start = container.begin();
123 std::advance(start, start_pos);
124 auto it = std::find(start, container.end(), value);
125 return it != container.end();
126 }
127
128 template <typename T>
ContainsElement(const std::set<T> & container,const T & value)129 bool ContainsElement(const std::set<T>& container, const T& value) {
130 return container.count(value) != 0u;
131 }
132
133 // 32-bit FNV-1a hash function suitable for std::unordered_map.
134 // It can be used with any container which works with range-based for loop.
135 // See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
136 template <typename Vector>
137 struct FNVHash {
operatorFNVHash138 size_t operator()(const Vector& vector) const {
139 uint32_t hash = 2166136261u;
140 for (const auto& value : vector) {
141 hash = (hash ^ value) * 16777619u;
142 }
143 return hash;
144 }
145 };
146
147 // Returns a copy of the passed vector that doesn't memory-own its entries.
148 template <typename T>
MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>> & src)149 static inline std::vector<T*> MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>>& src) {
150 std::vector<T*> result;
151 result.reserve(src.size());
152 for (const std::unique_ptr<T>& t : src) {
153 result.push_back(t.get());
154 }
155 return result;
156 }
157
158 template <typename IterLeft, typename IterRight>
159 class ZipLeftIter : public std::iterator<
160 std::forward_iterator_tag,
161 std::pair<typename IterLeft::value_type, typename IterRight::value_type>> {
162 public:
ZipLeftIter(IterLeft left,IterRight right)163 ZipLeftIter(IterLeft left, IterRight right) : left_iter_(left), right_iter_(right) {}
164 ZipLeftIter<IterLeft, IterRight>& operator++() {
165 ++left_iter_;
166 ++right_iter_;
167 return *this;
168 }
169 ZipLeftIter<IterLeft, IterRight> operator++(int) {
170 ZipLeftIter<IterLeft, IterRight> ret(left_iter_, right_iter_);
171 ++(*this);
172 return ret;
173 }
174 bool operator==(const ZipLeftIter<IterLeft, IterRight>& other) const {
175 return left_iter_ == other.left_iter_;
176 }
177 bool operator!=(const ZipLeftIter<IterLeft, IterRight>& other) const {
178 return !(*this == other);
179 }
180 std::pair<typename IterLeft::value_type, typename IterRight::value_type> operator*() const {
181 return std::make_pair(*left_iter_, *right_iter_);
182 }
183
184 private:
185 IterLeft left_iter_;
186 IterRight right_iter_;
187 };
188
189 class CountIter : public std::iterator<std::forward_iterator_tag, size_t, size_t, size_t, size_t> {
190 public:
CountIter()191 CountIter() : count_(0) {}
CountIter(size_t count)192 explicit CountIter(size_t count) : count_(count) {}
193 CountIter& operator++() {
194 ++count_;
195 return *this;
196 }
197 CountIter operator++(int) {
198 size_t ret = count_;
199 ++count_;
200 return CountIter(ret);
201 }
202 bool operator==(const CountIter& other) const {
203 return count_ == other.count_;
204 }
205 bool operator!=(const CountIter& other) const {
206 return !(*this == other);
207 }
208 size_t operator*() const {
209 return count_;
210 }
211
212 private:
213 size_t count_;
214 };
215
216 // Make an iteration range that returns a pair of the element and the index of the element.
217 template <typename Iter>
ZipCount(IterationRange<Iter> iter)218 static inline IterationRange<ZipLeftIter<Iter, CountIter>> ZipCount(IterationRange<Iter> iter) {
219 return IterationRange(ZipLeftIter(iter.begin(), CountIter(0)),
220 ZipLeftIter(iter.end(), CountIter(-1)));
221 }
222
223 // Make an iteration range that returns a pair of the outputs of two iterators. Stops when the first
224 // (left) one is exhausted. The left iterator must be at least as long as the right one.
225 template <typename IterLeft, typename IterRight>
ZipLeft(IterationRange<IterLeft> iter_left,IterationRange<IterRight> iter_right)226 static inline IterationRange<ZipLeftIter<IterLeft, IterRight>> ZipLeft(
227 IterationRange<IterLeft> iter_left, IterationRange<IterRight> iter_right) {
228 return IterationRange(ZipLeftIter(iter_left.begin(), iter_right.begin()),
229 ZipLeftIter(iter_left.end(), iter_right.end()));
230 }
231
Range(size_t start,size_t end)232 static inline IterationRange<CountIter> Range(size_t start, size_t end) {
233 return IterationRange(CountIter(start), CountIter(end));
234 }
235
Range(size_t end)236 static inline IterationRange<CountIter> Range(size_t end) {
237 return Range(0, end);
238 }
239
240 template <typename RealIter, typename Filter>
241 struct FilterIterator
242 : public std::iterator<std::forward_iterator_tag, typename RealIter::value_type> {
243 public:
244 FilterIterator(RealIter rl,
245 Filter cond,
246 std::optional<RealIter> end = std::nullopt)
real_iter_FilterIterator247 : real_iter_(rl), cond_(cond), end_(end) {
248 DCHECK(std::make_optional(rl) == end_ || cond_(*real_iter_));
249 }
250
251 FilterIterator<RealIter, Filter>& operator++() {
252 DCHECK(std::make_optional(real_iter_) != end_);
253 do {
254 if (std::make_optional(++real_iter_) == end_) {
255 break;
256 }
257 } while (!cond_(*real_iter_));
258 return *this;
259 }
260 FilterIterator<RealIter, Filter> operator++(int) {
261 FilterIterator<RealIter, Filter> ret(real_iter_, cond_, end_);
262 ++(*this);
263 return ret;
264 }
265 bool operator==(const FilterIterator<RealIter, Filter>& other) const {
266 return real_iter_ == other.real_iter_;
267 }
268 bool operator!=(const FilterIterator<RealIter, Filter>& other) const {
269 return !(*this == other);
270 }
271 typename RealIter::value_type operator*() const {
272 return *real_iter_;
273 }
274
275 private:
276 RealIter real_iter_;
277 Filter cond_;
278 std::optional<RealIter> end_;
279 };
280
281 template <typename Iter, typename Filter>
Filter(IterationRange<Iter> it,Filter cond)282 static inline IterationRange<FilterIterator<Iter, Filter>> Filter(
283 IterationRange<Iter> it, Filter cond) {
284 auto end = it.end();
285 auto start = std::find_if(it.begin(), end, cond);
286 return MakeIterationRange(FilterIterator(start, cond, std::make_optional(end)),
287 FilterIterator(end, cond, std::make_optional(end)));
288 }
289
290 template <typename Val>
291 struct NonNullFilter {
292 public:
293 static_assert(std::is_pointer<Val>::value, "Must be pointer type!");
operatorNonNullFilter294 constexpr bool operator()(Val v) const {
295 return v != nullptr;
296 }
297 };
298
299 template <typename InnerIter>
300 using FilterNull = FilterIterator<InnerIter, NonNullFilter<typename InnerIter::value_type>>;
301
302 template <typename InnerIter>
FilterOutNull(IterationRange<InnerIter> inner)303 static inline IterationRange<FilterNull<InnerIter>> FilterOutNull(IterationRange<InnerIter> inner) {
304 return Filter(inner, NonNullFilter<typename InnerIter::value_type>());
305 }
306
307 template <typename Val>
308 struct SafePrinter {
309 const Val* val_;
310 };
311
312 template<typename Val>
313 std::ostream& operator<<(std::ostream& os, const SafePrinter<Val>& v) {
314 if (v.val_ == nullptr) {
315 return os << "NULL";
316 } else {
317 return os << *v.val_;
318 }
319 }
320
321 template<typename Val>
SafePrint(const Val * v)322 SafePrinter<Val> SafePrint(const Val* v) {
323 return SafePrinter<Val>{v};
324 }
325
326 // Helper struct for iterating a split-string without allocation.
327 struct SplitStringIter : public std::iterator<std::forward_iterator_tag, std::string_view> {
328 public:
329 // Direct iterator constructor. The iteration state is only the current index.
330 // We use that with the split char and the full string to get the current and
331 // next segment.
SplitStringIterSplitStringIter332 SplitStringIter(size_t index, char split, std::string_view sv)
333 : cur_index_(index), split_on_(split), sv_(sv) {}
334 SplitStringIter(const SplitStringIter&) = default;
335 SplitStringIter(SplitStringIter&&) = default;
336 SplitStringIter& operator=(SplitStringIter&&) = default;
337 SplitStringIter& operator=(const SplitStringIter&) = default;
338
339 SplitStringIter& operator++() {
340 size_t nxt = sv_.find(split_on_, cur_index_);
341 if (nxt == std::string_view::npos) {
342 cur_index_ = std::string_view::npos;
343 } else {
344 cur_index_ = nxt + 1;
345 }
346 return *this;
347 }
348
349 SplitStringIter operator++(int) {
350 SplitStringIter ret(cur_index_, split_on_, sv_);
351 ++(*this);
352 return ret;
353 }
354
355 bool operator==(const SplitStringIter& other) const {
356 return sv_ == other.sv_ && split_on_ == other.split_on_ && cur_index_== other.cur_index_;
357 }
358
359 bool operator!=(const SplitStringIter& other) const {
360 return !(*this == other);
361 }
362
363 typename std::string_view operator*() const {
364 return sv_.substr(cur_index_, sv_.substr(cur_index_).find(split_on_));
365 }
366
367 private:
368 size_t cur_index_;
369 char split_on_;
370 std::string_view sv_;
371 };
372
373 // Create an iteration range over the string 'sv' split at each 'target' occurrence.
374 // Eg: SplitString(":foo::bar") -> ["", "foo", "", "bar"]
SplitString(std::string_view sv,char target)375 inline IterationRange<SplitStringIter> SplitString(std::string_view sv, char target) {
376 return MakeIterationRange(SplitStringIter(0, target, sv),
377 SplitStringIter(std::string_view::npos, target, sv));
378 }
379
380 } // namespace art
381
382 #endif // ART_LIBARTBASE_BASE_STL_UTIL_H_
383