• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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