1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/stack.hpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,212 @@
1.4 +/*
1.5 + * Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#ifndef SHARE_VM_UTILITIES_STACK_HPP
1.29 +#define SHARE_VM_UTILITIES_STACK_HPP
1.30 +
1.31 +#include "memory/allocation.hpp"
1.32 +#include "memory/allocation.inline.hpp"
1.33 +
1.34 +// Class Stack (below) grows and shrinks by linking together "segments" which
1.35 +// are allocated on demand. Segments are arrays of the element type (E) plus an
1.36 +// extra pointer-sized field to store the segment link. Recently emptied
1.37 +// segments are kept in a cache and reused.
1.38 +//
1.39 +// Notes/caveats:
1.40 +//
1.41 +// The size of an element must either evenly divide the size of a pointer or be
1.42 +// a multiple of the size of a pointer.
1.43 +//
1.44 +// Destructors are not called for elements popped off the stack, so element
1.45 +// types which rely on destructors for things like reference counting will not
1.46 +// work properly.
1.47 +//
1.48 +// Class Stack allocates segments from the C heap. However, two protected
1.49 +// virtual methods are used to alloc/free memory which subclasses can override:
1.50 +//
1.51 +// virtual void* alloc(size_t bytes);
1.52 +// virtual void free(void* addr, size_t bytes);
1.53 +//
1.54 +// The alloc() method must return storage aligned for any use. The
1.55 +// implementation in class Stack assumes that alloc() will terminate the process
1.56 +// if the allocation fails.
1.57 +
1.58 +template <class E, MEMFLAGS F> class StackIterator;
1.59 +
1.60 +// StackBase holds common data/methods that don't depend on the element type,
1.61 +// factored out to reduce template code duplication.
1.62 +template <MEMFLAGS F> class StackBase
1.63 +{
1.64 +public:
1.65 + size_t segment_size() const { return _seg_size; } // Elements per segment.
1.66 + size_t max_size() const { return _max_size; } // Max elements allowed.
1.67 + size_t max_cache_size() const { return _max_cache_size; } // Max segments
1.68 + // allowed in cache.
1.69 +
1.70 + size_t cache_size() const { return _cache_size; } // Segments in the cache.
1.71 +
1.72 +protected:
1.73 + // The ctor arguments correspond to the like-named functions above.
1.74 + // segment_size: number of items per segment
1.75 + // max_cache_size: maxmium number of *segments* to cache
1.76 + // max_size: maximum number of items allowed, rounded to a multiple of
1.77 + // the segment size (0 == unlimited)
1.78 + inline StackBase(size_t segment_size, size_t max_cache_size, size_t max_size);
1.79 +
1.80 + // Round max_size to a multiple of the segment size. Treat 0 as unlimited.
1.81 + static inline size_t adjust_max_size(size_t max_size, size_t seg_size);
1.82 +
1.83 +protected:
1.84 + const size_t _seg_size; // Number of items per segment.
1.85 + const size_t _max_size; // Maximum number of items allowed in the stack.
1.86 + const size_t _max_cache_size; // Maximum number of segments to cache.
1.87 + size_t _cur_seg_size; // Number of items in the current segment.
1.88 + size_t _full_seg_size; // Number of items in already-filled segments.
1.89 + size_t _cache_size; // Number of segments in the cache.
1.90 +};
1.91 +
1.92 +#ifdef __GNUC__
1.93 +#define inline
1.94 +#endif // __GNUC__
1.95 +
1.96 +template <class E, MEMFLAGS F>
1.97 +class Stack: public StackBase<F>
1.98 +{
1.99 +public:
1.100 + friend class StackIterator<E, F>;
1.101 +
1.102 + // segment_size: number of items per segment
1.103 + // max_cache_size: maxmium number of *segments* to cache
1.104 + // max_size: maximum number of items allowed, rounded to a multiple of
1.105 + // the segment size (0 == unlimited)
1.106 + inline Stack(size_t segment_size = default_segment_size(),
1.107 + size_t max_cache_size = 4, size_t max_size = 0);
1.108 + inline ~Stack() { clear(true); }
1.109 +
1.110 + inline bool is_empty() const { return this->_cur_seg == NULL; }
1.111 + inline bool is_full() const { return this->_full_seg_size >= this->max_size(); }
1.112 +
1.113 + // Performance sensitive code should use is_empty() instead of size() == 0 and
1.114 + // is_full() instead of size() == max_size(). Using a conditional here allows
1.115 + // just one var to be updated when pushing/popping elements instead of two;
1.116 + // _full_seg_size is updated only when pushing/popping segments.
1.117 + inline size_t size() const {
1.118 + return is_empty() ? 0 : this->_full_seg_size + this->_cur_seg_size;
1.119 + }
1.120 +
1.121 + inline void push(E elem);
1.122 + inline E pop();
1.123 +
1.124 + // Clear everything from the stack, releasing the associated memory. If
1.125 + // clear_cache is true, also release any cached segments.
1.126 + void clear(bool clear_cache = false);
1.127 +
1.128 + static inline size_t default_segment_size();
1.129 +
1.130 +protected:
1.131 + // Each segment includes space for _seg_size elements followed by a link
1.132 + // (pointer) to the previous segment; the space is allocated as a single block
1.133 + // of size segment_bytes(). _seg_size is rounded up if necessary so the link
1.134 + // is properly aligned. The C struct for the layout would be:
1.135 + //
1.136 + // struct segment {
1.137 + // E elements[_seg_size];
1.138 + // E* link;
1.139 + // };
1.140 +
1.141 + // Round up seg_size to keep the link field aligned.
1.142 + static inline size_t adjust_segment_size(size_t seg_size);
1.143 +
1.144 + // Methods for allocation size and getting/setting the link.
1.145 + inline size_t link_offset() const; // Byte offset of link field.
1.146 + inline size_t segment_bytes() const; // Segment size in bytes.
1.147 + inline E** link_addr(E* seg) const; // Address of the link field.
1.148 + inline E* get_link(E* seg) const; // Extract the link from seg.
1.149 + inline E* set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg.
1.150 +
1.151 + virtual E* alloc(size_t bytes);
1.152 + virtual void free(E* addr, size_t bytes);
1.153 +
1.154 + void push_segment();
1.155 + void pop_segment();
1.156 +
1.157 + void free_segments(E* seg); // Free all segments in the list.
1.158 + inline void reset(bool reset_cache); // Reset all data fields.
1.159 +
1.160 + DEBUG_ONLY(void verify(bool at_empty_transition) const;)
1.161 + DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;)
1.162 +
1.163 +private:
1.164 + E* _cur_seg; // Current segment.
1.165 + E* _cache; // Segment cache to avoid ping-ponging.
1.166 +};
1.167 +
1.168 +template <class E, MEMFLAGS F> class ResourceStack: public Stack<E, F>, public ResourceObj
1.169 +{
1.170 +public:
1.171 + // If this class becomes widely used, it may make sense to save the Thread
1.172 + // and use it when allocating segments.
1.173 +// ResourceStack(size_t segment_size = Stack<E, F>::default_segment_size()):
1.174 + ResourceStack(size_t segment_size): Stack<E, F>(segment_size, max_uintx)
1.175 + { }
1.176 +
1.177 + // Set the segment pointers to NULL so the parent dtor does not free them;
1.178 + // that must be done by the ResourceMark code.
1.179 + ~ResourceStack() { Stack<E, F>::reset(true); }
1.180 +
1.181 +protected:
1.182 + virtual E* alloc(size_t bytes);
1.183 + virtual void free(E* addr, size_t bytes);
1.184 +
1.185 +private:
1.186 + void clear(bool clear_cache = false);
1.187 +};
1.188 +
1.189 +template <class E, MEMFLAGS F>
1.190 +class StackIterator: public StackObj
1.191 +{
1.192 +public:
1.193 + StackIterator(Stack<E, F>& stack): _stack(stack) { sync(); }
1.194 +
1.195 + Stack<E, F>& stack() const { return _stack; }
1.196 +
1.197 + bool is_empty() const { return _cur_seg == NULL; }
1.198 +
1.199 + E next() { return *next_addr(); }
1.200 + E* next_addr();
1.201 +
1.202 + void sync(); // Sync the iterator's state to the stack's current state.
1.203 +
1.204 +private:
1.205 + Stack<E, F>& _stack;
1.206 + size_t _cur_seg_size;
1.207 + E* _cur_seg;
1.208 + size_t _full_seg_size;
1.209 +};
1.210 +
1.211 +#ifdef __GNUC__
1.212 +#undef inline
1.213 +#endif // __GNUC__
1.214 +
1.215 +#endif // SHARE_VM_UTILITIES_STACK_HPP
