| // Copyright 2008, Google Inc. |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following disclaimer |
| // in the documentation and/or other materials provided with the |
| // distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived from |
| // this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #ifndef BASE_STACK_CONTAINER_H__ |
| #define BASE_STACK_CONTAINER_H__ |
| |
| #include <string> |
| #include <vector> |
| |
| #include "base/basictypes.h" |
| |
| // This allocator can be used with STL containers to provide a stack buffer |
| // from which to allocate memory and overflows onto the heap. This stack buffer |
| // would be allocated on the stack and allows us to avoid heap operations in |
| // some situations. |
| // |
| // STL likes to make copies of allocators, so the allocator itself can't hold |
| // the data. Instead, we make the creator responsible for creating a |
| // StackAllocator::Source which contains the data. Copying the allocator |
| // merely copies the pointer to this shared source, so all allocators created |
| // based on our allocator will share the same stack buffer. |
| // |
| // This stack buffer implementation is very simple. The first allocation that |
| // fits in the stack buffer will use the stack buffer. Any subsequent |
| // allocations will not use the stack buffer, even if there is unused room. |
| // This makes it appropriate for array-like containers, but the caller should |
| // be sure to reserve() in the container up to the stack buffer size. Otherwise |
| // the container will allocate a small array which will "use up" the stack |
| // buffer. |
| template<typename T, size_t stack_capacity> |
| class StackAllocator : public std::allocator<T> { |
| public: |
| typedef typename std::allocator<T>::pointer pointer; |
| typedef typename std::allocator<T>::size_type size_type; |
| |
| // Backing store for the allocator. The container owner is responsible for |
| // maintaining this for as long as any containers using this allocator are |
| // live. |
| struct Source { |
| Source() : used_stack_buffer_(false) { |
| } |
| |
| // Casts the buffer in its right type. |
| T* stack_buffer() { return reinterpret_cast<T*>(stack_buffer_); } |
| const T* stack_buffer() const { |
| return reinterpret_cast<const T*>(stack_buffer_); |
| } |
| |
| // |
| // IMPORTANT: Take care to ensure that stack_buffer_ is aligned |
| // since it is used to mimic an array of T. |
| // Be careful while declaring any unaligned types (like bool) |
| // before stack_buffer_. |
| // |
| |
| // The buffer itself. It is not of type T because we don't want the |
| // constructors and destructors to be automatically called. Define a POD |
| // buffer of the right size instead. |
| char stack_buffer_[sizeof(T[stack_capacity])]; |
| |
| // Set when the stack buffer is used for an allocation. We do not track |
| // how much of the buffer is used, only that somebody is using it. |
| bool used_stack_buffer_; |
| }; |
| |
| // Used by containers when they want to refer to an allocator of type U. |
| template<typename U> |
| struct rebind { |
| typedef StackAllocator<U, stack_capacity> other; |
| }; |
| |
| StackAllocator(Source* source) : source_(source) { |
| } |
| StackAllocator(const StackAllocator& other) : source_(other.source_) { |
| } |
| |
| // Actually do the allocation. Use the stack buffer if nobody has used it yet |
| // and the size requested fits. Otherwise, fall through to the standard |
| // allocator. |
| pointer allocate(size_type n, void* hint = 0) { |
| if (!source_->used_stack_buffer_ && n <= stack_capacity) { |
| source_->used_stack_buffer_ = true; |
| return source_->stack_buffer(); |
| } else { |
| return std::allocator<T>::allocate(n, hint); |
| } |
| } |
| |
| // Free: when trying to free the stack buffer, just mark it as free. For |
| // non-stack-buffer pointers, just fall though to the standard allocator. |
| void deallocate(pointer p, size_type n) { |
| if (p == source_->stack_buffer()) |
| source_->used_stack_buffer_ = false; |
| else |
| std::allocator<T>::deallocate(p, n); |
| } |
| |
| private: |
| Source* source_; |
| }; |
| |
| // A wrapper around STL containers that maintains a stack-sized buffer that the |
| // initial capacity of the vector is based on. Growing the container beyond the |
| // stack capacity will transparently overflow onto the heap. The container must |
| // support reserve(). |
| // |
| // WATCH OUT: the ContainerType MUST use the proper StackAllocator for this |
| // type. This object is really intended to be used only internally. You'll want |
| // to use the wrappers below for different types. |
| template<typename TContainerType, int stack_capacity> |
| class StackContainer { |
| public: |
| typedef TContainerType ContainerType; |
| typedef typename ContainerType::value_type ContainedType; |
| typedef StackAllocator<ContainedType, stack_capacity> Allocator; |
| |
| // Allocator must be constructed before the container! |
| StackContainer() : allocator_(&stack_data_), container_(allocator_) { |
| // Make the container use the stack allocation by reserving our buffer size |
| // before doing anything else. |
| container_.reserve(stack_capacity); |
| } |
| |
| // Getters for the actual container. |
| // |
| // Danger: any copies of this made using the copy constructor must have |
| // shorter lifetimes than the source. The copy will share the same allocator |
| // and therefore the same stack buffer as the original. Use std::copy to |
| // copy into a "real" container for longer-lived objects. |
| ContainerType& container() { return container_; } |
| const ContainerType& container() const { return container_; } |
| |
| // Support operator-> to get to the container. This allows nicer syntax like: |
| // StackContainer<...> foo; |
| // std::sort(foo->begin(), foo->end()); |
| ContainerType* operator->() { return &container_; } |
| const ContainerType* operator->() const { return &container_; } |
| |
| #ifdef UNIT_TEST |
| // Retrieves the stack source so that that unit tests can verify that the |
| // buffer is being used properly. |
| const typename Allocator::Source& stack_data() const { |
| return stack_data_; |
| } |
| #endif |
| |
| protected: |
| typename Allocator::Source stack_data_; |
| Allocator allocator_; |
| ContainerType container_; |
| |
| DISALLOW_EVIL_CONSTRUCTORS(StackContainer); |
| }; |
| |
| // StackString |
| template<size_t stack_capacity> |
| class StackString : public StackContainer< |
| std::basic_string<char, |
| std::char_traits<char>, |
| StackAllocator<char, stack_capacity> >, |
| stack_capacity> { |
| public: |
| StackString() : StackContainer< |
| std::basic_string<char, |
| std::char_traits<char>, |
| StackAllocator<char, stack_capacity> >, |
| stack_capacity>() { |
| } |
| |
| private: |
| DISALLOW_EVIL_CONSTRUCTORS(StackString); |
| }; |
| |
| // StackWString |
| template<size_t stack_capacity> |
| class StackWString : public StackContainer< |
| std::basic_string<wchar_t, |
| std::char_traits<wchar_t>, |
| StackAllocator<wchar_t, stack_capacity> >, |
| stack_capacity> { |
| public: |
| StackWString() : StackContainer< |
| std::basic_string<wchar_t, |
| std::char_traits<wchar_t>, |
| StackAllocator<wchar_t, stack_capacity> >, |
| stack_capacity>() { |
| } |
| |
| private: |
| DISALLOW_EVIL_CONSTRUCTORS(StackWString); |
| }; |
| |
| // StackVector |
| // |
| // Example: |
| // StackVector<int, 16> foo; |
| // foo->push_back(22); // we have overloaded operator-> |
| // foo[0] = 10; // as well as operator[] |
| template<typename T, size_t stack_capacity> |
| class StackVector : public StackContainer< |
| std::vector<T, StackAllocator<T, stack_capacity> >, |
| stack_capacity> { |
| public: |
| StackVector() : StackContainer< |
| std::vector<T, StackAllocator<T, stack_capacity> >, |
| stack_capacity>() { |
| } |
| |
| // We need to put this in STL containers sometimes, which requires a copy |
| // constructor. We can't call the regular copy constructor because that will |
| // take the stack buffer from the original. Here, we create an empty object |
| // and make a stack buffer of its own. |
| StackVector(const StackVector<T, stack_capacity>& other) |
| : StackContainer< |
| std::vector<T, StackAllocator<T, stack_capacity> >, |
| stack_capacity>() { |
| this->container().assign(other->begin(), other->end()); |
| } |
| |
| StackVector<T, stack_capacity>& operator=( |
| const StackVector<T, stack_capacity>& other) { |
| this->container().assign(other->begin(), other->end()); |
| return *this; |
| } |
| |
| // Vectors are commonly indexed, which isn't very convenient even with |
| // operator-> (using "->at()" does exception stuff we don't want). |
| T& operator[](size_t i) { return this->container().operator[](i); } |
| const T& operator[](size_t i) const { |
| return this->container().operator[](i); |
| } |
| }; |
| |
| #endif // BASE_STACK_CONTAINER_H__ |