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 

    25 // Class Stack (below) grows and shrinks by linking together "segments" which

    26 // are allocated on demand.  Segments are arrays of the element type (E) plus an

    27 // extra pointer-sized field to store the segment link.  Recently emptied

    28 // segments are kept in a cache and reused.

    29 //

    30 // Notes/caveats:

    31 //

    32 // The size of an element must either evenly divide the size of a pointer or be

    33 // a multiple of the size of a pointer.

    34 //

    35 // Destructors are not called for elements popped off the stack, so element

    36 // types which rely on destructors for things like reference counting will not

    37 // work properly.

    38 //

    39 // Class Stack allocates segments from the C heap.  However, two protected

    40 // virtual methods are used to alloc/free memory which subclasses can override:

    41 //

    42 //      virtual void* alloc(size_t bytes);

    43 //      virtual void  free(void* addr, size_t bytes);

    44 //

    45 // The alloc() method must return storage aligned for any use.  The

    46 // implementation in class Stack assumes that alloc() will terminate the process

    47 // if the allocation fails.

    48 

    49 template <class E> class StackIterator;

    50 

    51 // StackBase holds common data/methods that don't depend on the element type,

    52 // factored out to reduce template code duplication.

    53 class StackBase

    54 {

    55 public:

    56   size_t segment_size()   const { return _seg_size; } // Elements per segment.

    57   size_t max_size()       const { return _max_size; } // Max elements allowed.

    58   size_t max_cache_size() const { return _max_cache_size; } // Max segments

    59                                                             // allowed in cache.

    60 

    61   size_t cache_size() const { return _cache_size; }   // Segments in the cache.

    62 

    63 protected:

    64   // The ctor arguments correspond to the like-named functions above.

    65   // segment_size:    number of items per segment

    66   // max_cache_size:  maxmium number of *segments* to cache

    67   // max_size:        maximum number of items allowed, rounded to a multiple of

    68   //                  the segment size (0 == unlimited)

    69   inline StackBase(size_t segment_size, size_t max_cache_size, size_t max_size);

    70 

    71   // Round max_size to a multiple of the segment size.  Treat 0 as unlimited.

    72   static inline size_t adjust_max_size(size_t max_size, size_t seg_size);

    73 

    74 protected:

    75   const size_t _seg_size;       // Number of items per segment.

    76   const size_t _max_size;       // Maximum number of items allowed in the stack.

    77   const size_t _max_cache_size; // Maximum number of segments to cache.

    78   size_t       _cur_seg_size;   // Number of items in the current segment.

    79   size_t       _full_seg_size;  // Number of items in already-filled segments.

    80   size_t       _cache_size;     // Number of segments in the cache.

    81 };

    82 

    83 #ifdef __GNUC__

    84 #define inline

    85 #endif // __GNUC__

    86 

    87 template <class E>

    88 class Stack:  public StackBase

    89 {

    90 public:

    91   friend class StackIterator<E>;

    92 

    93   // segment_size:    number of items per segment

    94   // max_cache_size:  maxmium number of *segments* to cache

    95   // max_size:        maximum number of items allowed, rounded to a multiple of

    96   //                  the segment size (0 == unlimited)

    97   inline Stack(size_t segment_size = default_segment_size(),

    98                size_t max_cache_size = 4, size_t max_size = 0);

    99   inline ~Stack() { clear(true); }

   100 

   101   inline bool is_empty() const { return _cur_seg == NULL; }

   102   inline bool is_full()  const { return _full_seg_size >= max_size(); }

   103 

   104   // Performance sensitive code should use is_empty() instead of size() == 0 and

   105   // is_full() instead of size() == max_size().  Using a conditional here allows

   106   // just one var to be updated when pushing/popping elements instead of two;

   107   // _full_seg_size is updated only when pushing/popping segments.

   108   inline size_t size() const {

   109     return is_empty() ? 0 : _full_seg_size + _cur_seg_size;

   110   }

   111 

   112   inline void push(E elem);

   113   inline E    pop();

   114 

   115   // Clear everything from the stack, releasing the associated memory.  If

   116   // clear_cache is true, also release any cached segments.

   117   void clear(bool clear_cache = false);

   118 

   119   static inline size_t default_segment_size();

   120 

   121 protected:

   122   // Each segment includes space for _seg_size elements followed by a link

   123   // (pointer) to the previous segment; the space is allocated as a single block

   124   // of size segment_bytes().  _seg_size is rounded up if necessary so the link

   125   // is properly aligned.  The C struct for the layout would be:

   126   //

   127   // struct segment {

   128   //   E     elements[_seg_size];

   129   //   E*    link;

   130   // };

   131 

   132   // Round up seg_size to keep the link field aligned.

   133   static inline size_t adjust_segment_size(size_t seg_size);

   134 

   135   // Methods for allocation size and getting/setting the link.

   136   inline size_t link_offset() const;              // Byte offset of link field.

   137   inline size_t segment_bytes() const;            // Segment size in bytes.

   138   inline E**    link_addr(E* seg) const;          // Address of the link field.

   139   inline E*     get_link(E* seg) const;           // Extract the link from seg.

   140   inline E*     set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg.

   141 

   142   virtual E*    alloc(size_t bytes);

   143   virtual void  free(E* addr, size_t bytes);

   144 

   145   void push_segment();

   146   void pop_segment();

   147 

   148   void free_segments(E* seg);          // Free all segments in the list.

   149   inline void reset(bool reset_cache); // Reset all data fields.

   150 

   151   DEBUG_ONLY(void verify(bool at_empty_transition) const;)

   152   DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;)

   153 

   154 private:

   155   E* _cur_seg;    // Current segment.

   156   E* _cache;      // Segment cache to avoid ping-ponging.

   157 };

   158 

   159 template <class E> class ResourceStack:  public Stack<E>, public ResourceObj

   160 {

   161 public:

   162   // If this class becomes widely used, it may make sense to save the Thread

   163   // and use it when allocating segments.

   164   ResourceStack(size_t segment_size = Stack<E>::default_segment_size()):

   165     Stack<E>(segment_size, max_uintx)

   166     { }

   167 

   168   // Set the segment pointers to NULL so the parent dtor does not free them;

   169   // that must be done by the ResourceMark code.

   170   ~ResourceStack() { Stack<E>::reset(true); }

   171 

   172 protected:

   173   virtual E*   alloc(size_t bytes);

   174   virtual void free(E* addr, size_t bytes);

   175 

   176 private:

   177   void clear(bool clear_cache = false);

   178 };

   179 

   180 template <class E>

   181 class StackIterator: public StackObj

   182 {

   183 public:

   184   StackIterator(Stack<E>& stack): _stack(stack) { sync(); }

   185 

   186   Stack<E>& stack() const { return _stack; }

   187 

   188   bool is_empty() const { return _cur_seg == NULL; }

   189 

   190   E  next() { return *next_addr(); }

   191   E* next_addr();

   192 

   193   void sync(); // Sync the iterator's state to the stack's current state.

   194 

   195 private:

   196   Stack<E>& _stack;

   197   size_t    _cur_seg_size;

   198   E*        _cur_seg;

   199   size_t    _full_seg_size;

   200 };

   201 

   202 #ifdef __GNUC__

   203 #undef inline

   204 #endif // __GNUC__