X-Git-Url: http://git.xonotic.org/?a=blobdiff_plain;ds=sidebyside;f=libs%2Fcontainer%2Fstack.h;h=10040a746b0a022e42c0867e25323917910f099e;hb=9c6a79a9f657a99b866c50816b2a129a316a05e9;hp=d83674c30adb5a429befd1932c33c9bff3698239;hpb=231225d6f97d0b926b2e896e5783cccfbc7c5619;p=xonotic%2Fnetradiant.git diff --git a/libs/container/stack.h b/libs/container/stack.h index d83674c3..10040a74 100644 --- a/libs/container/stack.h +++ b/libs/container/stack.h @@ -1,25 +1,25 @@ /* -Copyright (C) 2001-2006, William Joseph. -All Rights Reserved. + Copyright (C) 2001-2006, William Joseph. + All Rights Reserved. -This file is part of GtkRadiant. + This file is part of GtkRadiant. -GtkRadiant is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. + GtkRadiant is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. -GtkRadiant is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + GtkRadiant is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with GtkRadiant; if not, write to the Free Software -Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA -*/ + You should have received a copy of the GNU General Public License + along with GtkRadiant; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ -#if !defined(INCLUDED_CONTAINER_STACK_H) +#if !defined( INCLUDED_CONTAINER_STACK_H ) #define INCLUDED_CONTAINER_STACK_H #include "memory/allocator.h" @@ -36,204 +36,176 @@ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA template class Stack : public DefaultAllocator { - typedef DefaultAllocator Allocator; +typedef DefaultAllocator Allocator; - enum - { - DEFAULT_CAPACITY = 4, - }; +enum +{ + DEFAULT_CAPACITY = 4, +}; - typedef Type* pointer; - typedef const Type* const_pointer; +typedef Type* pointer; +typedef const Type* const_pointer; public: - typedef const_pointer const_iterator; +typedef const_pointer const_iterator; private: - pointer m_data; - pointer m_end; - std::size_t m_capacity; - - - void insert(const Type& value) - { - Allocator::construct(m_end++, value); - } - void insert_overflow(const Type& value) - { - const std::size_t new_capacity = (m_capacity) ? m_capacity + m_capacity : std::size_t(DEFAULT_CAPACITY); - const pointer new_data = Allocator::allocate(new_capacity); - const pointer new_end = std::copy(m_data, m_end, new_data); - - destroy(); - Allocator::deallocate(m_data, m_capacity); - - m_capacity = new_capacity; - m_data = new_data; - m_end = new_end; - insert(value); - } - void destroy() - { - for(pointer p = m_data; p != m_end; ++p) - { - Allocator::destroy(p); - } - } - void construct(const Stack& other) - { - pointer p = m_data; - for(const_iterator i = other.begin(); i != other.end(); ++i) - { - Allocator::construct(p++, *i); - } - } +pointer m_data; +pointer m_end; +std::size_t m_capacity; + + +void insert( const Type& value ){ + Allocator::construct( m_end++, value ); +} +void insert_overflow( const Type& value ){ + const std::size_t new_capacity = ( m_capacity ) ? m_capacity + m_capacity : std::size_t( DEFAULT_CAPACITY ); + const pointer new_data = Allocator::allocate( new_capacity ); + const pointer new_end = std::copy( m_data, m_end, new_data ); + + destroy(); + Allocator::deallocate( m_data, m_capacity ); + + m_capacity = new_capacity; + m_data = new_data; + m_end = new_end; + insert( value ); +} +void destroy(){ + for ( pointer p = m_data; p != m_end; ++p ) + { + Allocator::destroy( p ); + } +} +void construct( const Stack& other ){ + pointer p = m_data; + for ( const_iterator i = other.begin(); i != other.end(); ++i ) + { + Allocator::construct( p++, *i ); + } +} public: - Stack() : - m_data(0), - m_end(0), - m_capacity(0) - { - } - Stack(const Type& value) : - m_data(0), - m_end(0), - m_capacity(0) - { - push(value); - } - Stack(const Stack& other) : - DefaultAllocator(other) - { - m_capacity = other.m_capacity; - m_data = Allocator::allocate(m_capacity); - construct(other); - m_end = m_data + other.size(); - } - ~Stack() - { - destroy(); - Allocator::deallocate(m_data, m_capacity); - } - - const_iterator begin() const - { - return m_data; - } - const_iterator end() const - { - return m_end; - } - - bool empty() const - { - return end() == begin(); - } - void clear() - { - destroy(); - m_end = m_data; - } - - std::size_t size() const - { - return m_end - m_data; - } - Type operator[](const std::size_t i) const - { - return m_data[i]; - } - /// \brief Pushes \p value onto the stack at the top element. If reserved storage is insufficient for the new element, this will invalidate all iterators. - void push(const Type& value) - { - if(size() == m_capacity) - { - insert_overflow(value); - } - else - { - insert(value); - } - } - /// \brief Removes the top element of the stack. - void pop() - { - Allocator::destroy(--m_end); - } - /// \brief Returns the top element of the mutable stack. - Type& top() - { - return *(m_end-1); - } - /// \brief Returns the top element of the non-mutable stack. - const Type& top() const - { - return *(m_end-1); - } - /// \brief Returns the element below the top element of the mutable stack. - Type& parent() - { - return *(m_end-2); - } - /// \brief Returns the element below the top element of the non-mutable stack. - const Type& parent() const - { - return *(m_end-2); - } - /// \brief Swaps the values of this stack and \p other. - void swap(Stack& other) - { - std::swap(m_data, other.m_data); - std::swap(m_end, other.m_end); - std::swap(m_capacity, other.m_capacity); - } +Stack() : + m_data( 0 ), + m_end( 0 ), + m_capacity( 0 ){ +} +Stack( const Type& value ) : + m_data( 0 ), + m_end( 0 ), + m_capacity( 0 ){ + push( value ); +} +Stack( const Stack& other ) : + DefaultAllocator( other ){ + m_capacity = other.m_capacity; + m_data = Allocator::allocate( m_capacity ); + construct( other ); + m_end = m_data + other.size(); +} +~Stack(){ + destroy(); + Allocator::deallocate( m_data, m_capacity ); +} + +const_iterator begin() const { + return m_data; +} +const_iterator end() const { + return m_end; +} + +bool empty() const { + return end() == begin(); +} +void clear(){ + destroy(); + m_end = m_data; +} + +std::size_t size() const { + return m_end - m_data; +} +Type operator[]( const std::size_t i ) const { + return m_data[i]; +} +/// \brief Pushes \p value onto the stack at the top element. If reserved storage is insufficient for the new element, this will invalidate all iterators. +void push( const Type& value ){ + if ( size() == m_capacity ) { + insert_overflow( value ); + } + else + { + insert( value ); + } +} +/// \brief Removes the top element of the stack. +void pop(){ + Allocator::destroy( --m_end ); +} +/// \brief Returns the top element of the mutable stack. +Type& top(){ + return *( m_end - 1 ); +} +/// \brief Returns the top element of the non-mutable stack. +const Type& top() const { + return *( m_end - 1 ); +} +/// \brief Returns the element below the top element of the mutable stack. +Type& parent(){ + return *( m_end - 2 ); +} +/// \brief Returns the element below the top element of the non-mutable stack. +const Type& parent() const { + return *( m_end - 2 ); +} +/// \brief Swaps the values of this stack and \p other. +void swap( Stack& other ){ + std::swap( m_data, other.m_data ); + std::swap( m_end, other.m_end ); + std::swap( m_capacity, other.m_capacity ); +} #if 1 // use copy-swap technique - Stack& operator=(const Stack& other) - { - Stack temp(other); - temp.swap(*this); - return *this; - } +Stack& operator=( const Stack& other ){ + Stack temp( other ); + temp.swap( *this ); + return *this; +} #else // avoids memory allocation if capacity is already sufficient. - Stack& operator=(const Stack& other) - { - if(&other != this) - { - destroy(); - - if(other.size() > m_capacity) - { - Allocator::deallocate(m_data, m_capacity); - m_capacity = other.m_capacity; - m_data = Allocator::allocate(m_capacity); - } - m_end = m_data + other.size(); - - construct(other); - } - return *this; - } +Stack& operator=( const Stack& other ){ + if ( &other != this ) { + destroy(); + + if ( other.size() > m_capacity ) { + Allocator::deallocate( m_data, m_capacity ); + m_capacity = other.m_capacity; + m_data = Allocator::allocate( m_capacity ); + } + m_end = m_data + other.size(); + + construct( other ); + } + return *this; +} #endif }; /// \brief Returns true if \p self is lexicographically less than \p other. template -inline bool operator<(const Stack& self, const Stack& other) -{ - return std::lexicographical_compare(self.begin(), self.end(), other.begin(), other.end()); +inline bool operator<( const Stack& self, const Stack& other ){ + return std::lexicographical_compare( self.begin(), self.end(), other.begin(), other.end() ); } namespace std { - /// \brief Swaps the values of \p self and \p other. - /// Overloads std::swap(). - template - inline void swap(Stack& self, Stack& other) - { - self.swap(other); - } +/// \brief Swaps the values of \p self and \p other. +/// Overloads std::swap(). +template +inline void swap( Stack& self, Stack& other ){ + self.swap( other ); +} } #endif