Mercurial > hg > graal-compiler
view src/share/vm/utilities/stack.hpp @ 3536:c4f88f4ede54
Reflect API changes in JavaAccess.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 10 Aug 2011 02:13:41 +0200 |
parents | f95d63e2154a |
children | d2a62e0f25eb |
line wrap: on
line source
/* * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #ifndef SHARE_VM_UTILITIES_STACK_HPP #define SHARE_VM_UTILITIES_STACK_HPP #include "memory/allocation.inline.hpp" // Class Stack (below) grows and shrinks by linking together "segments" which // are allocated on demand. Segments are arrays of the element type (E) plus an // extra pointer-sized field to store the segment link. Recently emptied // segments are kept in a cache and reused. // // Notes/caveats: // // The size of an element must either evenly divide the size of a pointer or be // a multiple of the size of a pointer. // // Destructors are not called for elements popped off the stack, so element // types which rely on destructors for things like reference counting will not // work properly. // // Class Stack allocates segments from the C heap. However, two protected // virtual methods are used to alloc/free memory which subclasses can override: // // virtual void* alloc(size_t bytes); // virtual void free(void* addr, size_t bytes); // // The alloc() method must return storage aligned for any use. The // implementation in class Stack assumes that alloc() will terminate the process // if the allocation fails. template <class E> class StackIterator; // StackBase holds common data/methods that don't depend on the element type, // factored out to reduce template code duplication. class StackBase { public: size_t segment_size() const { return _seg_size; } // Elements per segment. size_t max_size() const { return _max_size; } // Max elements allowed. size_t max_cache_size() const { return _max_cache_size; } // Max segments // allowed in cache. size_t cache_size() const { return _cache_size; } // Segments in the cache. protected: // The ctor arguments correspond to the like-named functions above. // segment_size: number of items per segment // max_cache_size: maxmium number of *segments* to cache // max_size: maximum number of items allowed, rounded to a multiple of // the segment size (0 == unlimited) inline StackBase(size_t segment_size, size_t max_cache_size, size_t max_size); // Round max_size to a multiple of the segment size. Treat 0 as unlimited. static inline size_t adjust_max_size(size_t max_size, size_t seg_size); protected: const size_t _seg_size; // Number of items per segment. const size_t _max_size; // Maximum number of items allowed in the stack. const size_t _max_cache_size; // Maximum number of segments to cache. size_t _cur_seg_size; // Number of items in the current segment. size_t _full_seg_size; // Number of items in already-filled segments. size_t _cache_size; // Number of segments in the cache. }; #ifdef __GNUC__ #define inline #endif // __GNUC__ template <class E> class Stack: public StackBase { public: friend class StackIterator<E>; // segment_size: number of items per segment // max_cache_size: maxmium number of *segments* to cache // max_size: maximum number of items allowed, rounded to a multiple of // the segment size (0 == unlimited) inline Stack(size_t segment_size = default_segment_size(), size_t max_cache_size = 4, size_t max_size = 0); inline ~Stack() { clear(true); } inline bool is_empty() const { return _cur_seg == NULL; } inline bool is_full() const { return _full_seg_size >= max_size(); } // Performance sensitive code should use is_empty() instead of size() == 0 and // is_full() instead of size() == max_size(). Using a conditional here allows // just one var to be updated when pushing/popping elements instead of two; // _full_seg_size is updated only when pushing/popping segments. inline size_t size() const { return is_empty() ? 0 : _full_seg_size + _cur_seg_size; } inline void push(E elem); inline E pop(); // Clear everything from the stack, releasing the associated memory. If // clear_cache is true, also release any cached segments. void clear(bool clear_cache = false); static inline size_t default_segment_size(); protected: // Each segment includes space for _seg_size elements followed by a link // (pointer) to the previous segment; the space is allocated as a single block // of size segment_bytes(). _seg_size is rounded up if necessary so the link // is properly aligned. The C struct for the layout would be: // // struct segment { // E elements[_seg_size]; // E* link; // }; // Round up seg_size to keep the link field aligned. static inline size_t adjust_segment_size(size_t seg_size); // Methods for allocation size and getting/setting the link. inline size_t link_offset() const; // Byte offset of link field. inline size_t segment_bytes() const; // Segment size in bytes. inline E** link_addr(E* seg) const; // Address of the link field. inline E* get_link(E* seg) const; // Extract the link from seg. inline E* set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg. virtual E* alloc(size_t bytes); virtual void free(E* addr, size_t bytes); void push_segment(); void pop_segment(); void free_segments(E* seg); // Free all segments in the list. inline void reset(bool reset_cache); // Reset all data fields. DEBUG_ONLY(void verify(bool at_empty_transition) const;) DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;) private: E* _cur_seg; // Current segment. E* _cache; // Segment cache to avoid ping-ponging. }; template <class E> class ResourceStack: public Stack<E>, public ResourceObj { public: // If this class becomes widely used, it may make sense to save the Thread // and use it when allocating segments. ResourceStack(size_t segment_size = Stack<E>::default_segment_size()): Stack<E>(segment_size, max_uintx) { } // Set the segment pointers to NULL so the parent dtor does not free them; // that must be done by the ResourceMark code. ~ResourceStack() { Stack<E>::reset(true); } protected: virtual E* alloc(size_t bytes); virtual void free(E* addr, size_t bytes); private: void clear(bool clear_cache = false); }; template <class E> class StackIterator: public StackObj { public: StackIterator(Stack<E>& stack): _stack(stack) { sync(); } Stack<E>& stack() const { return _stack; } bool is_empty() const { return _cur_seg == NULL; } E next() { return *next_addr(); } E* next_addr(); void sync(); // Sync the iterator's state to the stack's current state. private: Stack<E>& _stack; size_t _cur_seg_size; E* _cur_seg; size_t _full_seg_size; }; #ifdef __GNUC__ #undef inline #endif // __GNUC__ #endif // SHARE_VM_UTILITIES_STACK_HPP