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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
26 #define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
27
28 #include "memory/freeList.hpp"
29
30 /*
31 * A binary tree based search structure for free blocks.
32 * This is currently used in the Concurrent Mark&Sweep implementation, but
33 * will be used for free block management for metadata.
34 */
35
36 // A TreeList is a FreeList which can be used to maintain a
37 // binary tree of free lists.
38
39 template <class Chunk_t, class FreeList_t> class TreeChunk;
40 template <class Chunk_t, class FreeList_t> class BinaryTreeDictionary;
41 template <class Chunk_t, class FreeList_t> class AscendTreeCensusClosure;
42 template <class Chunk_t, class FreeList_t> class DescendTreeCensusClosure;
43 template <class Chunk_t, class FreeList_t> class DescendTreeSearchClosure;
44
45 template <class Chunk_t, class FreeList_t>
46 class TreeList : public FreeList_t {
47 friend class TreeChunk<Chunk_t, FreeList_t>;
48 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>;
259 Chunk_t* get_chunk(size_t size) {
260 verify_par_locked();
261 Chunk_t* res = get_chunk_from_tree(size);
262 assert(res == NULL || res->is_free(),
263 "Should be returning a free chunk");
264 return res;
265 }
266
267 void return_chunk(Chunk_t* chunk) {
268 verify_par_locked();
269 insert_chunk_in_tree(chunk);
270 }
271
272 void remove_chunk(Chunk_t* chunk) {
273 verify_par_locked();
274 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk);
275 assert(chunk->is_free(), "Should still be a free chunk");
276 }
277
278 size_t max_chunk_size() const;
279 size_t total_chunk_size(debug_only(const Mutex* lock)) const {
280 debug_only(
281 if (lock != NULL && lock->owned_by_self()) {
282 assert(total_size_in_tree(root()) == total_size(),
283 "_total_size inconsistency");
284 }
285 )
286 return total_size();
287 }
288
289 size_t min_size() const {
290 return TreeChunk<Chunk_t, FreeList_t>::min_size();
291 }
292
293 double sum_of_squared_block_sizes() const {
294 return sum_of_squared_block_sizes(root());
295 }
296
297 Chunk_t* find_chunk_ends_at(HeapWord* target) const;
298
299 // Return the largest free chunk in the tree.
300 Chunk_t* find_largest_dict() const;
301
302 void print_free_lists(outputStream* st) const;
303
304 // For debugging. Returns the sum of the _returned_bytes for
305 // all lists in the tree.
306 size_t sum_dict_returned_bytes() PRODUCT_RETURN0;
307 // Sets the _returned_bytes for all the lists in the tree to zero.
|
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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
26 #define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
27
28 #include "memory/freeList.hpp"
29 #include "memory/memRegion.hpp"
30
31 class Mutex;
32
33 /*
34 * A binary tree based search structure for free blocks.
35 * This is currently used in the Concurrent Mark&Sweep implementation, but
36 * will be used for free block management for metadata.
37 */
38
39 // A TreeList is a FreeList which can be used to maintain a
40 // binary tree of free lists.
41
42 template <class Chunk_t, class FreeList_t> class TreeChunk;
43 template <class Chunk_t, class FreeList_t> class BinaryTreeDictionary;
44 template <class Chunk_t, class FreeList_t> class AscendTreeCensusClosure;
45 template <class Chunk_t, class FreeList_t> class DescendTreeCensusClosure;
46 template <class Chunk_t, class FreeList_t> class DescendTreeSearchClosure;
47
48 template <class Chunk_t, class FreeList_t>
49 class TreeList : public FreeList_t {
50 friend class TreeChunk<Chunk_t, FreeList_t>;
51 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>;
262 Chunk_t* get_chunk(size_t size) {
263 verify_par_locked();
264 Chunk_t* res = get_chunk_from_tree(size);
265 assert(res == NULL || res->is_free(),
266 "Should be returning a free chunk");
267 return res;
268 }
269
270 void return_chunk(Chunk_t* chunk) {
271 verify_par_locked();
272 insert_chunk_in_tree(chunk);
273 }
274
275 void remove_chunk(Chunk_t* chunk) {
276 verify_par_locked();
277 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk);
278 assert(chunk->is_free(), "Should still be a free chunk");
279 }
280
281 size_t max_chunk_size() const;
282 inline size_t total_chunk_size(debug_only(const Mutex* lock)) const;
283
284 size_t min_size() const {
285 return TreeChunk<Chunk_t, FreeList_t>::min_size();
286 }
287
288 double sum_of_squared_block_sizes() const {
289 return sum_of_squared_block_sizes(root());
290 }
291
292 Chunk_t* find_chunk_ends_at(HeapWord* target) const;
293
294 // Return the largest free chunk in the tree.
295 Chunk_t* find_largest_dict() const;
296
297 void print_free_lists(outputStream* st) const;
298
299 // For debugging. Returns the sum of the _returned_bytes for
300 // all lists in the tree.
301 size_t sum_dict_returned_bytes() PRODUCT_RETURN0;
302 // Sets the _returned_bytes for all the lists in the tree to zero.
|