Mercurial > hg > truffle
annotate src/share/vm/utilities/stack.hpp @ 15547:cab432461b8b
use NodeClass.Position when matching graphs, rearrange MatchableNode annotations, improve error reporting
author | Tom Rodriguez <tom.rodriguez@oracle.com> |
---|---|
date | Wed, 07 May 2014 10:58:26 -0700 |
parents | b9a9ed0f8eeb |
children |
rev | line source |
---|---|
1836 | 1 /* |
6842
b9a9ed0f8eeb
7197424: update copyright year to match last edit in jdk8 hotspot repository
mikael
parents:
6197
diff
changeset
|
2 * Copyright (c) 2009, 2012, 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 | |
6197 | 28 #include "memory/allocation.hpp" |
1972 | 29 #include "memory/allocation.inline.hpp" |
30 | |
1836 | 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 | |
6197 | 55 template <class E, MEMFLAGS F> class StackIterator; |
1836 | 56 |
57 // StackBase holds common data/methods that don't depend on the element type, | |
58 // factored out to reduce template code duplication. | |
6197 | 59 template <MEMFLAGS F> class StackBase |
1836 | 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 | |
6197 | 93 template <class E, MEMFLAGS F> |
94 class Stack: public StackBase<F> | |
1836 | 95 { |
96 public: | |
6197 | 97 friend class StackIterator<E, F>; |
1836 | 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 | |
6197 | 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(); } | |
1836 | 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 { | |
6197 | 115 return is_empty() ? 0 : this->_full_seg_size + this->_cur_seg_size; |
1836 | 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 | |
6197 | 165 template <class E, MEMFLAGS F> class ResourceStack: public Stack<E, F>, public ResourceObj |
1836 | 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. | |
6197 | 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) | |
1836 | 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. | |
6197 | 176 ~ResourceStack() { Stack<E, F>::reset(true); } |
1836 | 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 | |
6197 | 186 template <class E, MEMFLAGS F> |
1836 | 187 class StackIterator: public StackObj |
188 { | |
189 public: | |
6197 | 190 StackIterator(Stack<E, F>& stack): _stack(stack) { sync(); } |
1836 | 191 |
6197 | 192 Stack<E, F>& stack() const { return _stack; } |
1836 | 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: | |
6197 | 202 Stack<E, F>& _stack; |
1836 | 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__ | |
1972 | 211 |
212 #endif // SHARE_VM_UTILITIES_STACK_HPP |