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