aoqi@0: /* aoqi@0: * Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved. aoqi@0: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. aoqi@0: * aoqi@0: * This code is free software; you can redistribute it and/or modify it aoqi@0: * under the terms of the GNU General Public License version 2 only, as aoqi@0: * published by the Free Software Foundation. aoqi@0: * aoqi@0: * This code is distributed in the hope that it will be useful, but WITHOUT aoqi@0: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or aoqi@0: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License aoqi@0: * version 2 for more details (a copy is included in the LICENSE file that aoqi@0: * accompanied this code). aoqi@0: * aoqi@0: * You should have received a copy of the GNU General Public License version aoqi@0: * 2 along with this work; if not, write to the Free Software Foundation, aoqi@0: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. aoqi@0: * aoqi@0: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA aoqi@0: * or visit www.oracle.com if you need additional information or have any aoqi@0: * questions. aoqi@0: * aoqi@0: */ aoqi@0: aoqi@0: #ifndef SHARE_VM_UTILITIES_STACK_HPP aoqi@0: #define SHARE_VM_UTILITIES_STACK_HPP aoqi@0: aoqi@0: #include "memory/allocation.hpp" aoqi@0: #include "memory/allocation.inline.hpp" aoqi@0: aoqi@0: // Class Stack (below) grows and shrinks by linking together "segments" which aoqi@0: // are allocated on demand. Segments are arrays of the element type (E) plus an aoqi@0: // extra pointer-sized field to store the segment link. Recently emptied aoqi@0: // segments are kept in a cache and reused. aoqi@0: // aoqi@0: // Notes/caveats: aoqi@0: // aoqi@0: // The size of an element must either evenly divide the size of a pointer or be aoqi@0: // a multiple of the size of a pointer. aoqi@0: // aoqi@0: // Destructors are not called for elements popped off the stack, so element aoqi@0: // types which rely on destructors for things like reference counting will not aoqi@0: // work properly. aoqi@0: // aoqi@0: // Class Stack allocates segments from the C heap. However, two protected aoqi@0: // virtual methods are used to alloc/free memory which subclasses can override: aoqi@0: // aoqi@0: // virtual void* alloc(size_t bytes); aoqi@0: // virtual void free(void* addr, size_t bytes); aoqi@0: // aoqi@0: // The alloc() method must return storage aligned for any use. The aoqi@0: // implementation in class Stack assumes that alloc() will terminate the process aoqi@0: // if the allocation fails. aoqi@0: aoqi@0: template class StackIterator; aoqi@0: aoqi@0: // StackBase holds common data/methods that don't depend on the element type, aoqi@0: // factored out to reduce template code duplication. aoqi@0: template class StackBase aoqi@0: { aoqi@0: public: aoqi@0: size_t segment_size() const { return _seg_size; } // Elements per segment. aoqi@0: size_t max_size() const { return _max_size; } // Max elements allowed. aoqi@0: size_t max_cache_size() const { return _max_cache_size; } // Max segments aoqi@0: // allowed in cache. aoqi@0: aoqi@0: size_t cache_size() const { return _cache_size; } // Segments in the cache. aoqi@0: aoqi@0: protected: aoqi@0: // The ctor arguments correspond to the like-named functions above. aoqi@0: // segment_size: number of items per segment aoqi@0: // max_cache_size: maxmium number of *segments* to cache aoqi@0: // max_size: maximum number of items allowed, rounded to a multiple of aoqi@0: // the segment size (0 == unlimited) aoqi@0: inline StackBase(size_t segment_size, size_t max_cache_size, size_t max_size); aoqi@0: aoqi@0: // Round max_size to a multiple of the segment size. Treat 0 as unlimited. aoqi@0: static inline size_t adjust_max_size(size_t max_size, size_t seg_size); aoqi@0: aoqi@0: protected: aoqi@0: const size_t _seg_size; // Number of items per segment. aoqi@0: const size_t _max_size; // Maximum number of items allowed in the stack. aoqi@0: const size_t _max_cache_size; // Maximum number of segments to cache. aoqi@0: size_t _cur_seg_size; // Number of items in the current segment. aoqi@0: size_t _full_seg_size; // Number of items in already-filled segments. aoqi@0: size_t _cache_size; // Number of segments in the cache. aoqi@0: }; aoqi@0: aoqi@0: #ifdef __GNUC__ aoqi@0: #define inline aoqi@0: #endif // __GNUC__ aoqi@0: aoqi@0: template aoqi@0: class Stack: public StackBase aoqi@0: { aoqi@0: public: aoqi@0: friend class StackIterator; aoqi@0: aoqi@0: // segment_size: number of items per segment aoqi@0: // max_cache_size: maxmium number of *segments* to cache aoqi@0: // max_size: maximum number of items allowed, rounded to a multiple of aoqi@0: // the segment size (0 == unlimited) aoqi@0: inline Stack(size_t segment_size = default_segment_size(), aoqi@0: size_t max_cache_size = 4, size_t max_size = 0); aoqi@0: inline ~Stack() { clear(true); } aoqi@0: aoqi@0: inline bool is_empty() const { return this->_cur_seg == NULL; } aoqi@0: inline bool is_full() const { return this->_full_seg_size >= this->max_size(); } aoqi@0: aoqi@0: // Performance sensitive code should use is_empty() instead of size() == 0 and aoqi@0: // is_full() instead of size() == max_size(). Using a conditional here allows aoqi@0: // just one var to be updated when pushing/popping elements instead of two; aoqi@0: // _full_seg_size is updated only when pushing/popping segments. aoqi@0: inline size_t size() const { aoqi@0: return is_empty() ? 0 : this->_full_seg_size + this->_cur_seg_size; aoqi@0: } aoqi@0: aoqi@0: inline void push(E elem); aoqi@0: inline E pop(); aoqi@0: aoqi@0: // Clear everything from the stack, releasing the associated memory. If aoqi@0: // clear_cache is true, also release any cached segments. aoqi@0: void clear(bool clear_cache = false); aoqi@0: aoqi@0: static inline size_t default_segment_size(); aoqi@0: aoqi@0: protected: aoqi@0: // Each segment includes space for _seg_size elements followed by a link aoqi@0: // (pointer) to the previous segment; the space is allocated as a single block aoqi@0: // of size segment_bytes(). _seg_size is rounded up if necessary so the link aoqi@0: // is properly aligned. The C struct for the layout would be: aoqi@0: // aoqi@0: // struct segment { aoqi@0: // E elements[_seg_size]; aoqi@0: // E* link; aoqi@0: // }; aoqi@0: aoqi@0: // Round up seg_size to keep the link field aligned. aoqi@0: static inline size_t adjust_segment_size(size_t seg_size); aoqi@0: aoqi@0: // Methods for allocation size and getting/setting the link. aoqi@0: inline size_t link_offset() const; // Byte offset of link field. aoqi@0: inline size_t segment_bytes() const; // Segment size in bytes. aoqi@0: inline E** link_addr(E* seg) const; // Address of the link field. aoqi@0: inline E* get_link(E* seg) const; // Extract the link from seg. aoqi@0: inline E* set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg. aoqi@0: aoqi@0: virtual E* alloc(size_t bytes); aoqi@0: virtual void free(E* addr, size_t bytes); aoqi@0: aoqi@0: void push_segment(); aoqi@0: void pop_segment(); aoqi@0: aoqi@0: void free_segments(E* seg); // Free all segments in the list. aoqi@0: inline void reset(bool reset_cache); // Reset all data fields. aoqi@0: aoqi@0: DEBUG_ONLY(void verify(bool at_empty_transition) const;) aoqi@0: DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;) aoqi@0: aoqi@0: private: aoqi@0: E* _cur_seg; // Current segment. aoqi@0: E* _cache; // Segment cache to avoid ping-ponging. aoqi@0: }; aoqi@0: aoqi@0: template class ResourceStack: public Stack, public ResourceObj aoqi@0: { aoqi@0: public: aoqi@0: // If this class becomes widely used, it may make sense to save the Thread aoqi@0: // and use it when allocating segments. aoqi@0: // ResourceStack(size_t segment_size = Stack::default_segment_size()): aoqi@0: ResourceStack(size_t segment_size): Stack(segment_size, max_uintx) aoqi@0: { } aoqi@0: aoqi@0: // Set the segment pointers to NULL so the parent dtor does not free them; aoqi@0: // that must be done by the ResourceMark code. aoqi@0: ~ResourceStack() { Stack::reset(true); } aoqi@0: aoqi@0: protected: aoqi@0: virtual E* alloc(size_t bytes); aoqi@0: virtual void free(E* addr, size_t bytes); aoqi@0: aoqi@0: private: aoqi@0: void clear(bool clear_cache = false); aoqi@0: }; aoqi@0: aoqi@0: template aoqi@0: class StackIterator: public StackObj aoqi@0: { aoqi@0: public: aoqi@0: StackIterator(Stack& stack): _stack(stack) { sync(); } aoqi@0: aoqi@0: Stack& stack() const { return _stack; } aoqi@0: aoqi@0: bool is_empty() const { return _cur_seg == NULL; } aoqi@0: aoqi@0: E next() { return *next_addr(); } aoqi@0: E* next_addr(); aoqi@0: aoqi@0: void sync(); // Sync the iterator's state to the stack's current state. aoqi@0: aoqi@0: private: aoqi@0: Stack& _stack; aoqi@0: size_t _cur_seg_size; aoqi@0: E* _cur_seg; aoqi@0: size_t _full_seg_size; aoqi@0: }; aoqi@0: aoqi@0: #ifdef __GNUC__ aoqi@0: #undef inline aoqi@0: #endif // __GNUC__ aoqi@0: aoqi@0: #endif // SHARE_VM_UTILITIES_STACK_HPP