Java example source code file (stack.hpp)

This example Java source code file (stack.hpp) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

debug_only, max, maximum, memflags, null, number, resourcestack, segment, share_vm_utilities_stack_hpp, stack, stackbase, stackiterator

The stack.hpp Java example source code

/*
 * Copyright (c) 2009, 2012, 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.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, MEMFLAGS F> class StackIterator;

// StackBase holds common data/methods that don't depend on the element type,
// factored out to reduce template code duplication.
template <MEMFLAGS F> 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, MEMFLAGS F>
class Stack:  public StackBase<F>
{
public:
  friend class StackIterator<E, F>;

  // 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 this->_cur_seg == NULL; }
  inline bool is_full()  const { return this->_full_seg_size >= this->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 : this->_full_seg_size + this->_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, MEMFLAGS F> class ResourceStack:  public Stack, 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, F>::default_segment_size()):
  ResourceStack(size_t segment_size): Stack<E, F>(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, F>::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, MEMFLAGS F>
class StackIterator: public StackObj
{
public:
  StackIterator(Stack<E, F>& stack): _stack(stack) { sync(); }

  Stack<E, F>& 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, F>& _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