1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/stack.inline.hpp Tue Sep 28 15:56:15 2010 -0700
1.3 @@ -0,0 +1,273 @@
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 +StackBase::StackBase(size_t segment_size, size_t max_cache_size,
1.29 + size_t max_size):
1.30 + _seg_size(segment_size),
1.31 + _max_cache_size(max_cache_size),
1.32 + _max_size(adjust_max_size(max_size, segment_size))
1.33 +{
1.34 + assert(_max_size % _seg_size == 0, "not a multiple");
1.35 +}
1.36 +
1.37 +size_t StackBase::adjust_max_size(size_t max_size, size_t seg_size)
1.38 +{
1.39 + assert(seg_size > 0, "cannot be 0");
1.40 + assert(max_size >= seg_size || max_size == 0, "max_size too small");
1.41 + const size_t limit = max_uintx - (seg_size - 1);
1.42 + if (max_size == 0 || max_size > limit) {
1.43 + max_size = limit;
1.44 + }
1.45 + return (max_size + seg_size - 1) / seg_size * seg_size;
1.46 +}
1.47 +
1.48 +template <class E>
1.49 +Stack<E>::Stack(size_t segment_size, size_t max_cache_size, size_t max_size):
1.50 + StackBase(adjust_segment_size(segment_size), max_cache_size, max_size)
1.51 +{
1.52 + reset(true);
1.53 +}
1.54 +
1.55 +template <class E>
1.56 +void Stack<E>::push(E item)
1.57 +{
1.58 + assert(!is_full(), "pushing onto a full stack");
1.59 + if (_cur_seg_size == _seg_size) {
1.60 + push_segment();
1.61 + }
1.62 + _cur_seg[_cur_seg_size] = item;
1.63 + ++_cur_seg_size;
1.64 +}
1.65 +
1.66 +template <class E>
1.67 +E Stack<E>::pop()
1.68 +{
1.69 + assert(!is_empty(), "popping from an empty stack");
1.70 + if (_cur_seg_size == 1) {
1.71 + E tmp = _cur_seg[--_cur_seg_size];
1.72 + pop_segment();
1.73 + return tmp;
1.74 + }
1.75 + return _cur_seg[--_cur_seg_size];
1.76 +}
1.77 +
1.78 +template <class E>
1.79 +void Stack<E>::clear(bool clear_cache)
1.80 +{
1.81 + free_segments(_cur_seg);
1.82 + if (clear_cache) free_segments(_cache);
1.83 + reset(clear_cache);
1.84 +}
1.85 +
1.86 +template <class E>
1.87 +size_t Stack<E>::default_segment_size()
1.88 +{
1.89 + // Number of elements that fit in 4K bytes minus the size of two pointers
1.90 + // (link field and malloc header).
1.91 + return (4096 - 2 * sizeof(E*)) / sizeof(E);
1.92 +}
1.93 +
1.94 +template <class E>
1.95 +size_t Stack<E>::adjust_segment_size(size_t seg_size)
1.96 +{
1.97 + const size_t elem_sz = sizeof(E);
1.98 + const size_t ptr_sz = sizeof(E*);
1.99 + assert(elem_sz % ptr_sz == 0 || ptr_sz % elem_sz == 0, "bad element size");
1.100 + if (elem_sz < ptr_sz) {
1.101 + return align_size_up(seg_size * elem_sz, ptr_sz) / elem_sz;
1.102 + }
1.103 + return seg_size;
1.104 +}
1.105 +
1.106 +template <class E>
1.107 +size_t Stack<E>::link_offset() const
1.108 +{
1.109 + return align_size_up(_seg_size * sizeof(E), sizeof(E*));
1.110 +}
1.111 +
1.112 +template <class E>
1.113 +size_t Stack<E>::segment_bytes() const
1.114 +{
1.115 + return link_offset() + sizeof(E*);
1.116 +}
1.117 +
1.118 +template <class E>
1.119 +E** Stack<E>::link_addr(E* seg) const
1.120 +{
1.121 + return (E**) ((char*)seg + link_offset());
1.122 +}
1.123 +
1.124 +template <class E>
1.125 +E* Stack<E>::get_link(E* seg) const
1.126 +{
1.127 + return *link_addr(seg);
1.128 +}
1.129 +
1.130 +template <class E>
1.131 +E* Stack<E>::set_link(E* new_seg, E* old_seg)
1.132 +{
1.133 + *link_addr(new_seg) = old_seg;
1.134 + return new_seg;
1.135 +}
1.136 +
1.137 +template <class E>
1.138 +E* Stack<E>::alloc(size_t bytes)
1.139 +{
1.140 + return (E*) NEW_C_HEAP_ARRAY(char, bytes);
1.141 +}
1.142 +
1.143 +template <class E>
1.144 +void Stack<E>::free(E* addr, size_t bytes)
1.145 +{
1.146 + FREE_C_HEAP_ARRAY(char, (char*) addr);
1.147 +}
1.148 +
1.149 +template <class E>
1.150 +void Stack<E>::push_segment()
1.151 +{
1.152 + assert(_cur_seg_size == _seg_size, "current segment is not full");
1.153 + E* next;
1.154 + if (_cache_size > 0) {
1.155 + // Use a cached segment.
1.156 + next = _cache;
1.157 + _cache = get_link(_cache);
1.158 + --_cache_size;
1.159 + } else {
1.160 + next = alloc(segment_bytes());
1.161 + DEBUG_ONLY(zap_segment(next, true);)
1.162 + }
1.163 + const bool at_empty_transition = is_empty();
1.164 + _cur_seg = set_link(next, _cur_seg);
1.165 + _cur_seg_size = 0;
1.166 + _full_seg_size += at_empty_transition ? 0 : _seg_size;
1.167 + DEBUG_ONLY(verify(at_empty_transition);)
1.168 +}
1.169 +
1.170 +template <class E>
1.171 +void Stack<E>::pop_segment()
1.172 +{
1.173 + assert(_cur_seg_size == 0, "current segment is not empty");
1.174 + E* const prev = get_link(_cur_seg);
1.175 + if (_cache_size < _max_cache_size) {
1.176 + // Add the current segment to the cache.
1.177 + DEBUG_ONLY(zap_segment(_cur_seg, false);)
1.178 + _cache = set_link(_cur_seg, _cache);
1.179 + ++_cache_size;
1.180 + } else {
1.181 + DEBUG_ONLY(zap_segment(_cur_seg, true);)
1.182 + free(_cur_seg, segment_bytes());
1.183 + }
1.184 + const bool at_empty_transition = prev == NULL;
1.185 + _cur_seg = prev;
1.186 + _cur_seg_size = _seg_size;
1.187 + _full_seg_size -= at_empty_transition ? 0 : _seg_size;
1.188 + DEBUG_ONLY(verify(at_empty_transition);)
1.189 +}
1.190 +
1.191 +template <class E>
1.192 +void Stack<E>::free_segments(E* seg)
1.193 +{
1.194 + const size_t bytes = segment_bytes();
1.195 + while (seg != NULL) {
1.196 + E* const prev = get_link(seg);
1.197 + free(seg, bytes);
1.198 + seg = prev;
1.199 + }
1.200 +}
1.201 +
1.202 +template <class E>
1.203 +void Stack<E>::reset(bool reset_cache)
1.204 +{
1.205 + _cur_seg_size = _seg_size; // So push() will alloc a new segment.
1.206 + _full_seg_size = 0;
1.207 + _cur_seg = NULL;
1.208 + if (reset_cache) {
1.209 + _cache_size = 0;
1.210 + _cache = NULL;
1.211 + }
1.212 +}
1.213 +
1.214 +#ifdef ASSERT
1.215 +template <class E>
1.216 +void Stack<E>::verify(bool at_empty_transition) const
1.217 +{
1.218 + assert(size() <= max_size(), "stack exceeded bounds");
1.219 + assert(cache_size() <= max_cache_size(), "cache exceeded bounds");
1.220 + assert(_cur_seg_size <= segment_size(), "segment index exceeded bounds");
1.221 +
1.222 + assert(_full_seg_size % _seg_size == 0, "not a multiple");
1.223 + assert(at_empty_transition || is_empty() == (size() == 0), "mismatch");
1.224 + assert((_cache == NULL) == (cache_size() == 0), "mismatch");
1.225 +
1.226 + if (is_empty()) {
1.227 + assert(_cur_seg_size == segment_size(), "sanity");
1.228 + }
1.229 +}
1.230 +
1.231 +template <class E>
1.232 +void Stack<E>::zap_segment(E* seg, bool zap_link_field) const
1.233 +{
1.234 + if (!ZapStackSegments) return;
1.235 + const size_t zap_bytes = segment_bytes() - (zap_link_field ? 0 : sizeof(E*));
1.236 + uint32_t* cur = (uint32_t*)seg;
1.237 + const uint32_t* end = cur + zap_bytes / sizeof(uint32_t);
1.238 + while (cur < end) {
1.239 + *cur++ = 0xfadfaded;
1.240 + }
1.241 +}
1.242 +#endif
1.243 +
1.244 +template <class E>
1.245 +E* ResourceStack<E>::alloc(size_t bytes)
1.246 +{
1.247 + return (E*) resource_allocate_bytes(bytes);
1.248 +}
1.249 +
1.250 +template <class E>
1.251 +void ResourceStack<E>::free(E* addr, size_t bytes)
1.252 +{
1.253 + resource_free_bytes((char*) addr, bytes);
1.254 +}
1.255 +
1.256 +template <class E>
1.257 +void StackIterator<E>::sync()
1.258 +{
1.259 + _full_seg_size = _stack._full_seg_size;
1.260 + _cur_seg_size = _stack._cur_seg_size;
1.261 + _cur_seg = _stack._cur_seg;
1.262 +}
1.263 +
1.264 +template <class E>
1.265 +E* StackIterator<E>::next_addr()
1.266 +{
1.267 + assert(!is_empty(), "no items left");
1.268 + if (_cur_seg_size == 1) {
1.269 + E* addr = _cur_seg;
1.270 + _cur_seg = _stack.get_link(_cur_seg);
1.271 + _cur_seg_size = _stack.segment_size();
1.272 + _full_seg_size -= _stack.segment_size();
1.273 + return addr;
1.274 + }
1.275 + return _cur_seg + --_cur_seg_size;
1.276 +}
