1 /*
2 * Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_UTILITIES_STACK_HPP
26 #define SHARE_VM_UTILITIES_STACK_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/allocation.inline.hpp"
30
31 // Class Stack (below) grows and shrinks by linking together "segments" which
32 // are allocated on demand. Segments are arrays of the element type (E) plus an
33 // extra pointer-sized field to store the segment link. Recently emptied
34 // segments are kept in a cache and reused.
35 //
36 // Notes/caveats:
37 //
38 // The size of an element must either evenly divide the size of a pointer or be
39 // a multiple of the size of a pointer.
40 //
41 // Destructors are not called for elements popped off the stack, so element
42 // types which rely on destructors for things like reference counting will not
43 // work properly.
44 //
45 // Class Stack allocates segments from the C heap. However, two protected
46 // virtual methods are used to alloc/free memory which subclasses can override:
47 //
48 // virtual void* alloc(size_t bytes);
49 // virtual void free(void* addr, size_t bytes);
50 //
51 // The alloc() method must return storage aligned for any use. The
52 // implementation in class Stack assumes that alloc() will terminate the process
53 // if the allocation fails.
54
55 template <class E, MEMFLAGS F> class StackIterator;
56
57 // StackBase holds common data/methods that don't depend on the element type,
58 // factored out to reduce template code duplication.
59 template <MEMFLAGS F> class StackBase
60 {
61 public:
62 size_t segment_size() const { return _seg_size; } // Elements per segment.
63 size_t max_size() const { return _max_size; } // Max elements allowed.
64 size_t max_cache_size() const { return _max_cache_size; } // Max segments
65 // allowed in cache.
66
67 size_t cache_size() const { return _cache_size; } // Segments in the cache.
68
69 protected:
70 // The ctor arguments correspond to the like-named functions above.
71 // segment_size: number of items per segment
72 // max_cache_size: maxmium number of *segments* to cache
73 // max_size: maximum number of items allowed, rounded to a multiple of
74 // the segment size (0 == unlimited)
75 inline StackBase(size_t segment_size, size_t max_cache_size, size_t max_size);
76
77 // Round max_size to a multiple of the segment size. Treat 0 as unlimited.
78 static inline size_t adjust_max_size(size_t max_size, size_t seg_size);
79
80 protected:
81 const size_t _seg_size; // Number of items per segment.
82 const size_t _max_size; // Maximum number of items allowed in the stack.
83 const size_t _max_cache_size; // Maximum number of segments to cache.
84 size_t _cur_seg_size; // Number of items in the current segment.
85 size_t _full_seg_size; // Number of items in already-filled segments.
86 size_t _cache_size; // Number of segments in the cache.
87 };
88
89 #ifdef __GNUC__
90 #define inline
91 #endif // __GNUC__
92
93 template <class E, MEMFLAGS F>
94 class Stack: public StackBase<F>
95 {
96 public:
97 friend class StackIterator<E, F>;
98
99 // segment_size: number of items per segment
100 // max_cache_size: maxmium number of *segments* to cache
101 // max_size: maximum number of items allowed, rounded to a multiple of
102 // the segment size (0 == unlimited)
103 inline Stack(size_t segment_size = default_segment_size(),
104 size_t max_cache_size = 4, size_t max_size = 0);
105 inline ~Stack() { clear(true); }
106
107 inline bool is_empty() const { return this->_cur_seg == NULL; }
108 inline bool is_full() const { return this->_full_seg_size >= this->max_size(); }
109
110 // Performance sensitive code should use is_empty() instead of size() == 0 and
111 // is_full() instead of size() == max_size(). Using a conditional here allows
112 // just one var to be updated when pushing/popping elements instead of two;
113 // _full_seg_size is updated only when pushing/popping segments.
114 inline size_t size() const {
115 return is_empty() ? 0 : this->_full_seg_size + this->_cur_seg_size;
116 }
117
118 inline void push(E elem);
119 inline E pop();
120
121 // Clear everything from the stack, releasing the associated memory. If
122 // clear_cache is true, also release any cached segments.
123 void clear(bool clear_cache = false);
124
125 static inline size_t default_segment_size();
126
127 protected:
128 // Each segment includes space for _seg_size elements followed by a link
129 // (pointer) to the previous segment; the space is allocated as a single block
130 // of size segment_bytes(). _seg_size is rounded up if necessary so the link
131 // is properly aligned. The C struct for the layout would be:
132 //
133 // struct segment {
134 // E elements[_seg_size];
135 // E* link;
136 // };
137
138 // Round up seg_size to keep the link field aligned.
139 static inline size_t adjust_segment_size(size_t seg_size);
140
141 // Methods for allocation size and getting/setting the link.
142 inline size_t link_offset() const; // Byte offset of link field.
143 inline size_t segment_bytes() const; // Segment size in bytes.
144 inline E** link_addr(E* seg) const; // Address of the link field.
145 inline E* get_link(E* seg) const; // Extract the link from seg.
146 inline E* set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg.
147
148 virtual E* alloc(size_t bytes);
149 virtual void free(E* addr, size_t bytes);
150
151 void push_segment();
152 void pop_segment();
153
154 void free_segments(E* seg); // Free all segments in the list.
155 inline void reset(bool reset_cache); // Reset all data fields.
156
157 DEBUG_ONLY(void verify(bool at_empty_transition) const;)
158 DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;)
159
160 private:
161 E* _cur_seg; // Current segment.
162 E* _cache; // Segment cache to avoid ping-ponging.
163 };
164
165 template <class E, MEMFLAGS F> class ResourceStack: public Stack<E, F>, public ResourceObj
166 {
167 public:
168 // If this class becomes widely used, it may make sense to save the Thread
169 // and use it when allocating segments.
170 // ResourceStack(size_t segment_size = Stack<E, F>::default_segment_size()):
171 ResourceStack(size_t segment_size): Stack<E, F>(segment_size, max_uintx)
172 { }
173
174 // Set the segment pointers to NULL so the parent dtor does not free them;
175 // that must be done by the ResourceMark code.
176 ~ResourceStack() { Stack<E, F>::reset(true); }
177
178 protected:
179 virtual E* alloc(size_t bytes);
180 virtual void free(E* addr, size_t bytes);
181
182 private:
183 void clear(bool clear_cache = false);
184 };
185
186 template <class E, MEMFLAGS F>
187 class StackIterator: public StackObj
188 {
189 public:
190 StackIterator(Stack<E, F>& stack): _stack(stack) { sync(); }
191
192 Stack<E, F>& stack() const { return _stack; }
193
194 bool is_empty() const { return _cur_seg == NULL; }
195
196 E next() { return *next_addr(); }
197 E* next_addr();
198
199 void sync(); // Sync the iterator's state to the stack's current state.
200
201 private:
202 Stack<E, F>& _stack;
203 size_t _cur_seg_size;
204 E* _cur_seg;
205 size_t _full_seg_size;
206 };
207
208 #ifdef __GNUC__
209 #undef inline
210 #endif // __GNUC__
211
212 #endif // SHARE_VM_UTILITIES_STACK_HPP