| /* | |
| * Copyright (c) 2024, 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_NMT_ARRAYWITHFREELIST_HPP | |
| #define SHARE_NMT_ARRAYWITHFREELIST_HPP | |
| #include "utilities/growableArray.hpp" | |
| #include <type_traits> | |
| // A flat array of elements E, backed by C-heap, growing on-demand. It allows for | |
| // returning arbitrary elements and keeps them in a freelist. Elements can be uniquely | |
| // identified via array index. | |
| template<typename E, MemTag MT> | |
| class ArrayWithFreeList { | |
| // An E must be trivially copyable and destructible, but it may be constructed | |
| // however it likes. | |
| constexpr void static_assert_E_satisfies_type_requirements() const { | |
| static_assert(std::is_trivially_copyable<E>::value && std::is_trivially_destructible<E>::value, "must be"); | |
| } | |
| public: | |
| using I = int32_t; | |
| static constexpr const I nil = -1; | |
| private: | |
| // A free list allocator element is either a link to the next free space | |
| // or an actual element. | |
| union BackingElement { | |
| I link; | |
| E e; | |
| }; | |
| GrowableArrayCHeap<BackingElement, MT> _backing_storage; | |
| I _free_start; | |
| bool is_in_bounds(I i) { | |
| return i >= 0 && i < _backing_storage.length(); | |
| } | |
| public: | |
| NONCOPYABLE(ArrayWithFreeList); | |
| ArrayWithFreeList(int initial_capacity = 8) | |
| : _backing_storage(initial_capacity), | |
| _free_start(nil) {} | |
| template<typename... Args> | |
| I allocate(Args... args) { | |
| static_assert_E_satisfies_type_requirements(); | |
| BackingElement* be; | |
| I i; | |
| if (_free_start != nil) { | |
| // Must point to already existing index | |
| be = &_backing_storage.at(_free_start); | |
| i = _free_start; | |
| _free_start = be->link; | |
| } else { | |
| // There are no free elements, allocate a new one. | |
| i = _backing_storage.append(BackingElement()); | |
| be = _backing_storage.adr_at(i); | |
| } | |
| ::new (be) E{args...}; | |
| return i; | |
| } | |
| void deallocate(I i) { | |
| static_assert_E_satisfies_type_requirements(); | |
| assert(i == nil || is_in_bounds(i), "out of bounds free"); | |
| if (i == nil) return; | |
| BackingElement& be_freed = _backing_storage.at(i); | |
| be_freed.link = _free_start; | |
| _free_start = i; | |
| } | |
| E& at(I i) { | |
| static_assert_E_satisfies_type_requirements(); | |
| assert(i != nil, "null pointer dereference"); | |
| assert(is_in_bounds(i), "out of bounds dereference"); | |
| return _backing_storage.at(i).e; | |
| } | |
| }; | |
| #endif // SHARE_NMT_ARRAYWITHFREELIST_HPP |