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
55template <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.
59template <MEMFLAGS F> class StackBase
60{
61public:
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
69protected:
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
80protected:
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
93template <class E, MEMFLAGS F>
94class Stack:  public StackBase<F>
95{
96public:
97  friend class StackIterator<E, F>;
98
99  // Number of elements that fit in 4K bytes minus the size of two pointers
100  // (link field and malloc header).
101  static const size_t _default_segment_size =  (4096 - 2 * sizeof(E*)) / sizeof(E);
102  static size_t default_segment_size() { return _default_segment_size; }
103
104  // segment_size:    number of items per segment
105  // max_cache_size:  maxmium number of *segments* to cache
106  // max_size:        maximum number of items allowed, rounded to a multiple of
107  //                  the segment size (0 == unlimited)
108  inline Stack(size_t segment_size = _default_segment_size,
109               size_t max_cache_size = 4, size_t max_size = 0);
110  inline ~Stack() { clear(true); }
111
112  inline bool is_empty() const { return this->_cur_seg == NULL; }
113  inline bool is_full()  const { return this->_full_seg_size >= this->max_size(); }
114
115  // Performance sensitive code should use is_empty() instead of size() == 0 and
116  // is_full() instead of size() == max_size().  Using a conditional here allows
117  // just one var to be updated when pushing/popping elements instead of two;
118  // _full_seg_size is updated only when pushing/popping segments.
119  inline size_t size() const {
120    return is_empty() ? 0 : this->_full_seg_size + this->_cur_seg_size;
121  }
122
123  inline void push(E elem);
124  inline E    pop();
125
126  // Clear everything from the stack, releasing the associated memory.  If
127  // clear_cache is true, also release any cached segments.
128  void clear(bool clear_cache = false);
129
130protected:
131  // Each segment includes space for _seg_size elements followed by a link
132  // (pointer) to the previous segment; the space is allocated as a single block
133  // of size segment_bytes().  _seg_size is rounded up if necessary so the link
134  // is properly aligned.  The C struct for the layout would be:
135  //
136  // struct segment {
137  //   E     elements[_seg_size];
138  //   E*    link;
139  // };
140
141  // Round up seg_size to keep the link field aligned.
142  static inline size_t adjust_segment_size(size_t seg_size);
143
144  // Methods for allocation size and getting/setting the link.
145  inline size_t link_offset() const;              // Byte offset of link field.
146  inline size_t segment_bytes() const;            // Segment size in bytes.
147  inline E**    link_addr(E* seg) const;          // Address of the link field.
148  inline E*     get_link(E* seg) const;           // Extract the link from seg.
149  inline E*     set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg.
150
151  virtual E*    alloc(size_t bytes);
152  virtual void  free(E* addr, size_t bytes);
153
154  void push_segment();
155  void pop_segment();
156
157  void free_segments(E* seg);          // Free all segments in the list.
158  inline void reset(bool reset_cache); // Reset all data fields.
159
160  DEBUG_ONLY(void verify(bool at_empty_transition) const;)
161  DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;)
162
163private:
164  E* _cur_seg;    // Current segment.
165  E* _cache;      // Segment cache to avoid ping-ponging.
166};
167
168template <class E, MEMFLAGS F> class ResourceStack:  public Stack<E, F>, public ResourceObj
169{
170public:
171  // If this class becomes widely used, it may make sense to save the Thread
172  // and use it when allocating segments.
173//  ResourceStack(size_t segment_size = Stack<E, F>::default_segment_size()):
174  ResourceStack(size_t segment_size): Stack<E, F>(segment_size, max_uintx)
175    { }
176
177  // Set the segment pointers to NULL so the parent dtor does not free them;
178  // that must be done by the ResourceMark code.
179  ~ResourceStack() { Stack<E, F>::reset(true); }
180
181protected:
182  virtual E*   alloc(size_t bytes);
183  virtual void free(E* addr, size_t bytes);
184
185private:
186  void clear(bool clear_cache = false);
187};
188
189template <class E, MEMFLAGS F>
190class StackIterator: public StackObj
191{
192public:
193  StackIterator(Stack<E, F>& stack): _stack(stack) { sync(); }
194
195  Stack<E, F>& stack() const { return _stack; }
196
197  bool is_empty() const { return _cur_seg == NULL; }
198
199  E  next() { return *next_addr(); }
200  E* next_addr();
201
202  void sync(); // Sync the iterator's state to the stack's current state.
203
204private:
205  Stack<E, F>& _stack;
206  size_t    _cur_seg_size;
207  E*        _cur_seg;
208  size_t    _full_seg_size;
209};
210
211#ifdef __GNUC__
212#undef inline
213#endif // __GNUC__
214
215#endif // SHARE_VM_UTILITIES_STACK_HPP
216