stack.inline.hpp revision 1756:894b1d7c7e01
1/* 2 * Copyright 2009 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 20 * CA 95054 USA or visit www.sun.com if you need additional information or 21 * have any questions. 22 * 23 */ 24 25StackBase::StackBase(size_t segment_size, size_t max_cache_size, 26 size_t max_size): 27 _seg_size(segment_size), 28 _max_cache_size(max_cache_size), 29 _max_size(adjust_max_size(max_size, segment_size)) 30{ 31 assert(_max_size % _seg_size == 0, "not a multiple"); 32} 33 34size_t StackBase::adjust_max_size(size_t max_size, size_t seg_size) 35{ 36 assert(seg_size > 0, "cannot be 0"); 37 assert(max_size >= seg_size || max_size == 0, "max_size too small"); 38 const size_t limit = max_uintx - (seg_size - 1); 39 if (max_size == 0 || max_size > limit) { 40 max_size = limit; 41 } 42 return (max_size + seg_size - 1) / seg_size * seg_size; 43} 44 45template <class E> 46Stack<E>::Stack(size_t segment_size, size_t max_cache_size, size_t max_size): 47 StackBase(adjust_segment_size(segment_size), max_cache_size, max_size) 48{ 49 reset(true); 50} 51 52template <class E> 53void Stack<E>::push(E item) 54{ 55 assert(!is_full(), "pushing onto a full stack"); 56 if (_cur_seg_size == _seg_size) { 57 push_segment(); 58 } 59 _cur_seg[_cur_seg_size] = item; 60 ++_cur_seg_size; 61} 62 63template <class E> 64E Stack<E>::pop() 65{ 66 assert(!is_empty(), "popping from an empty stack"); 67 if (_cur_seg_size == 1) { 68 E tmp = _cur_seg[--_cur_seg_size]; 69 pop_segment(); 70 return tmp; 71 } 72 return _cur_seg[--_cur_seg_size]; 73} 74 75template <class E> 76void Stack<E>::clear(bool clear_cache) 77{ 78 free_segments(_cur_seg); 79 if (clear_cache) free_segments(_cache); 80 reset(clear_cache); 81} 82 83template <class E> 84size_t Stack<E>::default_segment_size() 85{ 86 // Number of elements that fit in 4K bytes minus the size of two pointers 87 // (link field and malloc header). 88 return (4096 - 2 * sizeof(E*)) / sizeof(E); 89} 90 91template <class E> 92size_t Stack<E>::adjust_segment_size(size_t seg_size) 93{ 94 const size_t elem_sz = sizeof(E); 95 const size_t ptr_sz = sizeof(E*); 96 assert(elem_sz % ptr_sz == 0 || ptr_sz % elem_sz == 0, "bad element size"); 97 if (elem_sz < ptr_sz) { 98 return align_size_up(seg_size * elem_sz, ptr_sz) / elem_sz; 99 } 100 return seg_size; 101} 102 103template <class E> 104size_t Stack<E>::link_offset() const 105{ 106 return align_size_up(_seg_size * sizeof(E), sizeof(E*)); 107} 108 109template <class E> 110size_t Stack<E>::segment_bytes() const 111{ 112 return link_offset() + sizeof(E*); 113} 114 115template <class E> 116E** Stack<E>::link_addr(E* seg) const 117{ 118 return (E**) ((char*)seg + link_offset()); 119} 120 121template <class E> 122E* Stack<E>::get_link(E* seg) const 123{ 124 return *link_addr(seg); 125} 126 127template <class E> 128E* Stack<E>::set_link(E* new_seg, E* old_seg) 129{ 130 *link_addr(new_seg) = old_seg; 131 return new_seg; 132} 133 134template <class E> 135E* Stack<E>::alloc(size_t bytes) 136{ 137 return (E*) NEW_C_HEAP_ARRAY(char, bytes); 138} 139 140template <class E> 141void Stack<E>::free(E* addr, size_t bytes) 142{ 143 FREE_C_HEAP_ARRAY(char, (char*) addr); 144} 145 146template <class E> 147void Stack<E>::push_segment() 148{ 149 assert(_cur_seg_size == _seg_size, "current segment is not full"); 150 E* next; 151 if (_cache_size > 0) { 152 // Use a cached segment. 153 next = _cache; 154 _cache = get_link(_cache); 155 --_cache_size; 156 } else { 157 next = alloc(segment_bytes()); 158 DEBUG_ONLY(zap_segment(next, true);) 159 } 160 const bool at_empty_transition = is_empty(); 161 _cur_seg = set_link(next, _cur_seg); 162 _cur_seg_size = 0; 163 _full_seg_size += at_empty_transition ? 0 : _seg_size; 164 DEBUG_ONLY(verify(at_empty_transition);) 165} 166 167template <class E> 168void Stack<E>::pop_segment() 169{ 170 assert(_cur_seg_size == 0, "current segment is not empty"); 171 E* const prev = get_link(_cur_seg); 172 if (_cache_size < _max_cache_size) { 173 // Add the current segment to the cache. 174 DEBUG_ONLY(zap_segment(_cur_seg, false);) 175 _cache = set_link(_cur_seg, _cache); 176 ++_cache_size; 177 } else { 178 DEBUG_ONLY(zap_segment(_cur_seg, true);) 179 free(_cur_seg, segment_bytes()); 180 } 181 const bool at_empty_transition = prev == NULL; 182 _cur_seg = prev; 183 _cur_seg_size = _seg_size; 184 _full_seg_size -= at_empty_transition ? 0 : _seg_size; 185 DEBUG_ONLY(verify(at_empty_transition);) 186} 187 188template <class E> 189void Stack<E>::free_segments(E* seg) 190{ 191 const size_t bytes = segment_bytes(); 192 while (seg != NULL) { 193 E* const prev = get_link(seg); 194 free(seg, bytes); 195 seg = prev; 196 } 197} 198 199template <class E> 200void Stack<E>::reset(bool reset_cache) 201{ 202 _cur_seg_size = _seg_size; // So push() will alloc a new segment. 203 _full_seg_size = 0; 204 _cur_seg = NULL; 205 if (reset_cache) { 206 _cache_size = 0; 207 _cache = NULL; 208 } 209} 210 211#ifdef ASSERT 212template <class E> 213void Stack<E>::verify(bool at_empty_transition) const 214{ 215 assert(size() <= max_size(), "stack exceeded bounds"); 216 assert(cache_size() <= max_cache_size(), "cache exceeded bounds"); 217 assert(_cur_seg_size <= segment_size(), "segment index exceeded bounds"); 218 219 assert(_full_seg_size % _seg_size == 0, "not a multiple"); 220 assert(at_empty_transition || is_empty() == (size() == 0), "mismatch"); 221 assert((_cache == NULL) == (cache_size() == 0), "mismatch"); 222 223 if (is_empty()) { 224 assert(_cur_seg_size == segment_size(), "sanity"); 225 } 226} 227 228template <class E> 229void Stack<E>::zap_segment(E* seg, bool zap_link_field) const 230{ 231 if (!ZapStackSegments) return; 232 const size_t zap_bytes = segment_bytes() - (zap_link_field ? 0 : sizeof(E*)); 233 uint32_t* cur = (uint32_t*)seg; 234 const uint32_t* end = cur + zap_bytes / sizeof(uint32_t); 235 while (cur < end) { 236 *cur++ = 0xfadfaded; 237 } 238} 239#endif 240 241template <class E> 242E* ResourceStack<E>::alloc(size_t bytes) 243{ 244 return (E*) resource_allocate_bytes(bytes); 245} 246 247template <class E> 248void ResourceStack<E>::free(E* addr, size_t bytes) 249{ 250 resource_free_bytes((char*) addr, bytes); 251} 252 253template <class E> 254void StackIterator<E>::sync() 255{ 256 _full_seg_size = _stack._full_seg_size; 257 _cur_seg_size = _stack._cur_seg_size; 258 _cur_seg = _stack._cur_seg; 259} 260 261template <class E> 262E* StackIterator<E>::next_addr() 263{ 264 assert(!is_empty(), "no items left"); 265 if (_cur_seg_size == 1) { 266 E* addr = _cur_seg; 267 _cur_seg = _stack.get_link(_cur_seg); 268 _cur_seg_size = _stack.segment_size(); 269 _full_seg_size -= _stack.segment_size(); 270 return addr; 271 } 272 return _cur_seg + --_cur_seg_size; 273} 274