stl_util.h revision 88b2b80aed15bb1f931cddd40e44ca525ef10018
12faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes/* 22faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Copyright (C) 2011 The Android Open Source Project 32faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 42faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Licensed under the Apache License, Version 2.0 (the "License"); 52faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * you may not use this file except in compliance with the License. 62faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * You may obtain a copy of the License at 72faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 82faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 92faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * 102faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * Unless required by applicable law or agreed to in writing, software 112faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 122faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * See the License for the specific language governing permissions and 142faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes * limitations under the License. 152faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes */ 1658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_RUNTIME_BASE_STL_UTIL_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_RUNTIME_BASE_STL_UTIL_H_ 1958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 2008fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughes#include <algorithm> 211aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes#include <sstream> 2214134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes 23637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko#include "base/logging.h" 24637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 2558551df3c2646ed507feec9e9eb3768085a76059Carl Shapironamespace art { 2658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 2708fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughes// Sort and remove duplicates of an STL vector or deque. 2808fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughestemplate<class T> 2908fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughesvoid STLSortAndRemoveDuplicates(T* v) { 3008fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughes std::sort(v->begin(), v->end()); 3108fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughes v->erase(std::unique(v->begin(), v->end()), v->end()); 3208fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughes} 3308fc03ae5dded4adc9b45b7014a4b9dfedbe95a6Elliott Hughes 3458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// STLDeleteContainerPointers() 3558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// For a range within a container of pointers, calls delete 3658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// (non-array version) on these pointers. 3758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// NOTE: for these three functions, we could just implement a DeleteObject 3858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// functor and then call for_each() on the range and functor, but this 3958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// requires us to pull in all of algorithm.h, which seems expensive. 4058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// For hash_[multi]set, it is important that this deletes behind the iterator 4158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// because the hash_set may call the hash function on the iterator when it is 4258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// advanced, which could result in the hash function trying to deference a 4358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// stale pointer. 4458551df3c2646ed507feec9e9eb3768085a76059Carl Shapirotemplate <class ForwardIterator> 4558551df3c2646ed507feec9e9eb3768085a76059Carl Shapirovoid STLDeleteContainerPointers(ForwardIterator begin, 4658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro ForwardIterator end) { 4758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro while (begin != end) { 4858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro ForwardIterator temp = begin; 4958551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro ++begin; 5058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro delete *temp; 5158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro } 5258551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 5358551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 5458551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// STLDeleteElements() deletes all the elements in an STL container and clears 5558551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// the container. This function is suitable for use with a vector, set, 5658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// hash_set, or any other STL container which defines sensible begin(), end(), 5758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// and clear() methods. 5858551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// 592cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier// If container is null, this function is a no-op. 6058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// 6158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro// As an alternative to calling STLDeleteElements() directly, consider 623c43f8db38858cbe1e017731cbbb6859a8051162Richard Uhler// using a container of std::unique_ptr, which ensures that your container's 633c43f8db38858cbe1e017731cbbb6859a8051162Richard Uhler// elements are deleted when the container goes out of scope. 6458551df3c2646ed507feec9e9eb3768085a76059Carl Shapirotemplate <class T> 6558551df3c2646ed507feec9e9eb3768085a76059Carl Shapirovoid STLDeleteElements(T *container) { 662cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier if (container != nullptr) { 672cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier STLDeleteContainerPointers(container->begin(), container->end()); 682cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier container->clear(); 692cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier } 7058551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} 7158551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 72c31664f3d82e6cd68275a529a8a73f067a52e8beElliott Hughes// Given an STL container consisting of (key, value) pairs, STLDeleteValues 73c31664f3d82e6cd68275a529a8a73f067a52e8beElliott Hughes// deletes all the "value" components and clears the container. Does nothing 742cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier// in the case it's given a null pointer. 75c31664f3d82e6cd68275a529a8a73f067a52e8beElliott Hughestemplate <class T> 76c31664f3d82e6cd68275a529a8a73f067a52e8beElliott Hughesvoid STLDeleteValues(T *v) { 772cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier if (v != nullptr) { 782cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier for (typename T::iterator i = v->begin(); i != v->end(); ++i) { 792cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier delete i->second; 802cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier } 812cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier v->clear(); 82c31664f3d82e6cd68275a529a8a73f067a52e8beElliott Hughes } 83c31664f3d82e6cd68275a529a8a73f067a52e8beElliott Hughes} 84c31664f3d82e6cd68275a529a8a73f067a52e8beElliott Hughes 8514134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughestemplate <class T> 8614134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughesstd::string ToString(const T& v) { 873b6baaa203fa63f1522b2172a1645f90412afdaeElliott Hughes std::ostringstream os; 8814134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes os << "["; 8914134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes for (size_t i = 0; i < v.size(); ++i) { 9014134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes os << v[i]; 9114134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes if (i < v.size() - 1) { 9214134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes os << ", "; 9314134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes } 9414134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes } 9514134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes os << "]"; 9614134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes return os.str(); 9714134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes} 9814134a10e9bbaff0faf314dc00c1a1aeef8ef86bElliott Hughes 99637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below. 100637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markostruct FreeDelete { 101637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko // NOTE: Deleting a const object is valid but free() takes a non-const pointer. 102637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko void operator()(const void* ptr) const { 103637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko free(const_cast<void*>(ptr)); 104637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko } 105637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko}; 106637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 107637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// Alias for std::unique_ptr<> that uses the C function free() to delete objects. 108637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markotemplate <typename T> 109637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markousing UniqueCPtr = std::unique_ptr<T, FreeDelete>; 110637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 111637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// C++14 from-the-future import (std::make_unique) 112637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// Invoke the constructor of 'T' with the provided args, and wrap the result in a unique ptr. 113637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markotemplate <typename T, typename ... Args> 114637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markostd::unique_ptr<T> MakeUnique(Args&& ... args) { 115637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 116637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko} 117637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 118637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// Find index of the first element with the specified value known to be in the container. 119637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markotemplate <typename Container, typename T> 120637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markosize_t IndexOfElement(const Container& container, const T& value) { 121637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko auto it = std::find(container.begin(), container.end(), value); 122637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko DCHECK(it != container.end()); // Must exist. 123637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko return std::distance(container.begin(), it); 124637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko} 125637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 126637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// Remove the first element with the specified value known to be in the container. 127637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markotemplate <typename Container, typename T> 128637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markovoid RemoveElement(Container& container, const T& value) { 129637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko auto it = std::find(container.begin(), container.end(), value); 130637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko DCHECK(it != container.end()); // Must exist. 131637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko container.erase(it); 132637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko} 133637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 134637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// Replace the first element with the specified old_value known to be in the container. 135637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markotemplate <typename Container, typename T> 136637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markovoid ReplaceElement(Container& container, const T& old_value, const T& new_value) { 137637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko auto it = std::find(container.begin(), container.end(), old_value); 138637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko DCHECK(it != container.end()); // Must exist. 139637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko *it = new_value; 140637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko} 141637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 142637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko// Search for an element with the specified value and return true if it was found, false otherwise. 143637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markotemplate <typename Container, typename T> 144637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Markobool ContainsElement(const Container& container, const T& value, size_t start_pos = 0u) { 145637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko DCHECK_LE(start_pos, container.size()); 146637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko auto start = container.begin(); 147637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko std::advance(start, start_pos); 148637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko auto it = std::find(start, container.end(), value); 149637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko return it != container.end(); 150637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko} 151637ee0b9c10ab7732a7ee7b8335f3fff4ac1549cVladimir Marko 15204b0526d60de4e9979fc486d2ba655247d211d0bDavid Srbecky// const char* compare function suitable for std::map or std::set. 15304b0526d60de4e9979fc486d2ba655247d211d0bDavid Srbeckystruct CStringLess { 15404b0526d60de4e9979fc486d2ba655247d211d0bDavid Srbecky bool operator()(const char* lhs, const char* rhs) const { 15504b0526d60de4e9979fc486d2ba655247d211d0bDavid Srbecky return strcmp(lhs, rhs) < 0; 15604b0526d60de4e9979fc486d2ba655247d211d0bDavid Srbecky } 15704b0526d60de4e9979fc486d2ba655247d211d0bDavid Srbecky}; 15804b0526d60de4e9979fc486d2ba655247d211d0bDavid Srbecky 15988b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// Use to suppress type deduction for a function argument. 16088b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// See std::identity<> for more background: 16188b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1856.html#20.2.2 - move/forward helpers 16288b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// 16388b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// e.g. "template <typename X> void bar(identity<X>::type foo); 16488b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// bar(5); // compilation error 16588b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// bar<int>(5); // ok 16688b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// or "template <typename T> void foo(T* x, typename Identity<T*>::type y); 16788b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// Base b; 16888b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// Derived d; 16988b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// foo(&b, &d); // Use implicit Derived* -> Base* conversion. 17088b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// If T was deduced from both &b and &d, there would be a mismatch, i.e. deduction failure. 17188b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Markotemplate <typename T> 17288b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Markostruct Identity { 17388b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko using type = T; 17488b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko}; 17588b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko 17658551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro} // namespace art 17758551df3c2646ed507feec9e9eb3768085a76059Carl Shapiro 178fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_RUNTIME_BASE_STL_UTIL_H_ 179