94 class Stack: public StackBase<F> |
94 class Stack: public StackBase<F> |
95 { |
95 { |
96 public: |
96 public: |
97 friend class StackIterator<E, F>; |
97 friend class StackIterator<E, F>; |
98 |
98 |
|
99 // Number of elements that fit in 4K bytes minus the size of two pointers |
|
100 // (link field and malloc header). |
|
101 static const size_t _default_segment_size = (4096 - 2 * sizeof(E*)) / sizeof(E); |
|
102 static size_t default_segment_size() { return _default_segment_size; } |
|
103 |
99 // segment_size: number of items per segment |
104 // segment_size: number of items per segment |
100 // max_cache_size: maxmium number of *segments* to cache |
105 // max_cache_size: maxmium number of *segments* to cache |
101 // max_size: maximum number of items allowed, rounded to a multiple of |
106 // max_size: maximum number of items allowed, rounded to a multiple of |
102 // the segment size (0 == unlimited) |
107 // the segment size (0 == unlimited) |
103 inline Stack(size_t segment_size = default_segment_size(), |
108 inline Stack(size_t segment_size = _default_segment_size, |
104 size_t max_cache_size = 4, size_t max_size = 0); |
109 size_t max_cache_size = 4, size_t max_size = 0); |
105 inline ~Stack() { clear(true); } |
110 inline ~Stack() { clear(true); } |
106 |
111 |
107 inline bool is_empty() const { return this->_cur_seg == NULL; } |
112 inline bool is_empty() const { return this->_cur_seg == NULL; } |
108 inline bool is_full() const { return this->_full_seg_size >= this->max_size(); } |
113 inline bool is_full() const { return this->_full_seg_size >= this->max_size(); } |
119 inline E pop(); |
124 inline E pop(); |
120 |
125 |
121 // Clear everything from the stack, releasing the associated memory. If |
126 // Clear everything from the stack, releasing the associated memory. If |
122 // clear_cache is true, also release any cached segments. |
127 // clear_cache is true, also release any cached segments. |
123 void clear(bool clear_cache = false); |
128 void clear(bool clear_cache = false); |
124 |
|
125 static inline size_t default_segment_size(); |
|
126 |
129 |
127 protected: |
130 protected: |
128 // Each segment includes space for _seg_size elements followed by a link |
131 // Each segment includes space for _seg_size elements followed by a link |
129 // (pointer) to the previous segment; the space is allocated as a single block |
132 // (pointer) to the previous segment; the space is allocated as a single block |
130 // of size segment_bytes(). _seg_size is rounded up if necessary so the link |
133 // of size segment_bytes(). _seg_size is rounded up if necessary so the link |