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