1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/stack.hpp Tue Sep 28 15:56:15 2010 -0700
1.3 @@ -0,0 +1,204 @@
1.4 +/*
1.5 + * Copyright 2009 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// Class Stack (below) grows and shrinks by linking together "segments" which
1.29 +// are allocated on demand. Segments are arrays of the element type (E) plus an
1.30 +// extra pointer-sized field to store the segment link. Recently emptied
1.31 +// segments are kept in a cache and reused.
1.32 +//
1.33 +// Notes/caveats:
1.34 +//
1.35 +// The size of an element must either evenly divide the size of a pointer or be
1.36 +// a multiple of the size of a pointer.
1.37 +//
1.38 +// Destructors are not called for elements popped off the stack, so element
1.39 +// types which rely on destructors for things like reference counting will not
1.40 +// work properly.
1.41 +//
1.42 +// Class Stack allocates segments from the C heap. However, two protected
1.43 +// virtual methods are used to alloc/free memory which subclasses can override:
1.44 +//
1.45 +// virtual void* alloc(size_t bytes);
1.46 +// virtual void free(void* addr, size_t bytes);
1.47 +//
1.48 +// The alloc() method must return storage aligned for any use. The
1.49 +// implementation in class Stack assumes that alloc() will terminate the process
1.50 +// if the allocation fails.
1.51 +
1.52 +template <class E> class StackIterator;
1.53 +
1.54 +// StackBase holds common data/methods that don't depend on the element type,
1.55 +// factored out to reduce template code duplication.
1.56 +class StackBase
1.57 +{
1.58 +public:
1.59 + size_t segment_size() const { return _seg_size; } // Elements per segment.
1.60 + size_t max_size() const { return _max_size; } // Max elements allowed.
1.61 + size_t max_cache_size() const { return _max_cache_size; } // Max segments
1.62 + // allowed in cache.
1.63 +
1.64 + size_t cache_size() const { return _cache_size; } // Segments in the cache.
1.65 +
1.66 +protected:
1.67 + // The ctor arguments correspond to the like-named functions above.
1.68 + // segment_size: number of items per segment
1.69 + // max_cache_size: maxmium number of *segments* to cache
1.70 + // max_size: maximum number of items allowed, rounded to a multiple of
1.71 + // the segment size (0 == unlimited)
1.72 + inline StackBase(size_t segment_size, size_t max_cache_size, size_t max_size);
1.73 +
1.74 + // Round max_size to a multiple of the segment size. Treat 0 as unlimited.
1.75 + static inline size_t adjust_max_size(size_t max_size, size_t seg_size);
1.76 +
1.77 +protected:
1.78 + const size_t _seg_size; // Number of items per segment.
1.79 + const size_t _max_size; // Maximum number of items allowed in the stack.
1.80 + const size_t _max_cache_size; // Maximum number of segments to cache.
1.81 + size_t _cur_seg_size; // Number of items in the current segment.
1.82 + size_t _full_seg_size; // Number of items in already-filled segments.
1.83 + size_t _cache_size; // Number of segments in the cache.
1.84 +};
1.85 +
1.86 +#ifdef __GNUC__
1.87 +#define inline
1.88 +#endif // __GNUC__
1.89 +
1.90 +template <class E>
1.91 +class Stack: public StackBase
1.92 +{
1.93 +public:
1.94 + friend class StackIterator<E>;
1.95 +
1.96 + // segment_size: number of items per segment
1.97 + // max_cache_size: maxmium number of *segments* to cache
1.98 + // max_size: maximum number of items allowed, rounded to a multiple of
1.99 + // the segment size (0 == unlimited)
1.100 + inline Stack(size_t segment_size = default_segment_size(),
1.101 + size_t max_cache_size = 4, size_t max_size = 0);
1.102 + inline ~Stack() { clear(true); }
1.103 +
1.104 + inline bool is_empty() const { return _cur_seg == NULL; }
1.105 + inline bool is_full() const { return _full_seg_size >= max_size(); }
1.106 +
1.107 + // Performance sensitive code should use is_empty() instead of size() == 0 and
1.108 + // is_full() instead of size() == max_size(). Using a conditional here allows
1.109 + // just one var to be updated when pushing/popping elements instead of two;
1.110 + // _full_seg_size is updated only when pushing/popping segments.
1.111 + inline size_t size() const {
1.112 + return is_empty() ? 0 : _full_seg_size + _cur_seg_size;
1.113 + }
1.114 +
1.115 + inline void push(E elem);
1.116 + inline E pop();
1.117 +
1.118 + // Clear everything from the stack, releasing the associated memory. If
1.119 + // clear_cache is true, also release any cached segments.
1.120 + void clear(bool clear_cache = false);
1.121 +
1.122 + static inline size_t default_segment_size();
1.123 +
1.124 +protected:
1.125 + // Each segment includes space for _seg_size elements followed by a link
1.126 + // (pointer) to the previous segment; the space is allocated as a single block
1.127 + // of size segment_bytes(). _seg_size is rounded up if necessary so the link
1.128 + // is properly aligned. The C struct for the layout would be:
1.129 + //
1.130 + // struct segment {
1.131 + // E elements[_seg_size];
1.132 + // E* link;
1.133 + // };
1.134 +
1.135 + // Round up seg_size to keep the link field aligned.
1.136 + static inline size_t adjust_segment_size(size_t seg_size);
1.137 +
1.138 + // Methods for allocation size and getting/setting the link.
1.139 + inline size_t link_offset() const; // Byte offset of link field.
1.140 + inline size_t segment_bytes() const; // Segment size in bytes.
1.141 + inline E** link_addr(E* seg) const; // Address of the link field.
1.142 + inline E* get_link(E* seg) const; // Extract the link from seg.
1.143 + inline E* set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg.
1.144 +
1.145 + virtual E* alloc(size_t bytes);
1.146 + virtual void free(E* addr, size_t bytes);
1.147 +
1.148 + void push_segment();
1.149 + void pop_segment();
1.150 +
1.151 + void free_segments(E* seg); // Free all segments in the list.
1.152 + inline void reset(bool reset_cache); // Reset all data fields.
1.153 +
1.154 + DEBUG_ONLY(void verify(bool at_empty_transition) const;)
1.155 + DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;)
1.156 +
1.157 +private:
1.158 + E* _cur_seg; // Current segment.
1.159 + E* _cache; // Segment cache to avoid ping-ponging.
1.160 +};
1.161 +
1.162 +template <class E> class ResourceStack: public Stack<E>, public ResourceObj
1.163 +{
1.164 +public:
1.165 + // If this class becomes widely used, it may make sense to save the Thread
1.166 + // and use it when allocating segments.
1.167 + ResourceStack(size_t segment_size = Stack<E>::default_segment_size()):
1.168 + Stack<E>(segment_size, max_uintx)
1.169 + { }
1.170 +
1.171 + // Set the segment pointers to NULL so the parent dtor does not free them;
1.172 + // that must be done by the ResourceMark code.
1.173 + ~ResourceStack() { Stack<E>::reset(true); }
1.174 +
1.175 +protected:
1.176 + virtual E* alloc(size_t bytes);
1.177 + virtual void free(E* addr, size_t bytes);
1.178 +
1.179 +private:
1.180 + void clear(bool clear_cache = false);
1.181 +};
1.182 +
1.183 +template <class E>
1.184 +class StackIterator: public StackObj
1.185 +{
1.186 +public:
1.187 + StackIterator(Stack<E>& stack): _stack(stack) { sync(); }
1.188 +
1.189 + Stack<E>& stack() const { return _stack; }
1.190 +
1.191 + bool is_empty() const { return _cur_seg == NULL; }
1.192 +
1.193 + E next() { return *next_addr(); }
1.194 + E* next_addr();
1.195 +
1.196 + void sync(); // Sync the iterator's state to the stack's current state.
1.197 +
1.198 +private:
1.199 + Stack<E>& _stack;
1.200 + size_t _cur_seg_size;
1.201 + E* _cur_seg;
1.202 + size_t _full_seg_size;
1.203 +};
1.204 +
1.205 +#ifdef __GNUC__
1.206 +#undef inline
1.207 +#endif // __GNUC__
