| /* | |
| * Copyright (c) 1997, 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_LIBADT_VECTSET_HPP | |
| #define SHARE_LIBADT_VECTSET_HPP | |
| #include "memory/allocation.hpp" | |
| #include "utilities/copy.hpp" | |
| // Vector Sets | |
| // These sets can grow or shrink, based on the initial size and the largest | |
| // element currently in them. | |
| //------------------------------VectorSet-------------------------------------- | |
| class VectorSet : public AnyObj { | |
| private: | |
| static const uint word_bits = 5; | |
| static const uint bit_mask = 31; | |
| // Used 32-bit words | |
| uint _size; | |
| // Allocated words | |
| uint _data_size; | |
| uint32_t* _data; | |
| Arena* _set_arena; | |
| ReallocMark _nesting; // Safety checks for arena reallocation | |
| void init(Arena* arena); | |
| // Grow vector to required word capacity | |
| void maybe_grow(uint new_word_capacity) { | |
| _nesting.check(_set_arena); // Check if a potential reallocation in the arena is safe | |
| if (new_word_capacity >= _size) { | |
| grow(new_word_capacity); | |
| } | |
| } | |
| void grow(uint new_word_capacity); | |
| public: | |
| VectorSet(); | |
| VectorSet(Arena* arena); | |
| ~VectorSet() {} | |
| NONCOPYABLE(VectorSet); | |
| VectorSet& operator=(VectorSet&&) = delete; | |
| // Allow move constructor for && (eg. capture return of function) | |
| VectorSet(VectorSet&&) = default; | |
| void insert(uint elem); | |
| bool is_empty() const; | |
| void reset() { | |
| _size = 0; | |
| } | |
| void clear() { | |
| reset(); | |
| } | |
| // Fast inlined "test and set". Replaces the idiom: | |
| // if (visited.test(idx)) return; | |
| // visited.set(idx); | |
| // With: | |
| // if (visited.test_set(idx)) return; | |
| // | |
| bool test_set(uint elem) { | |
| uint32_t word = elem >> word_bits; | |
| maybe_grow(word); | |
| uint32_t mask = 1U << (elem & bit_mask); | |
| uint32_t data = _data[word]; | |
| _data[word] = data | mask; | |
| return (data & mask) != 0; | |
| } | |
| // Fast inlined test | |
| bool test(uint elem) const { | |
| uint32_t word = elem >> word_bits; | |
| if (word >= _size) { | |
| return false; | |
| } | |
| uint32_t mask = 1U << (elem & bit_mask); | |
| return (_data[word] & mask) != 0; | |
| } | |
| void remove(uint elem) { | |
| uint32_t word = elem >> word_bits; | |
| if (word >= _size) { | |
| return; | |
| } | |
| uint32_t mask = 1U << (elem & bit_mask); | |
| _data[word] &= ~mask; // Clear bit | |
| } | |
| // Fast inlined set | |
| void set(uint elem) { | |
| uint32_t word = elem >> word_bits; | |
| maybe_grow(word); | |
| uint32_t mask = 1U << (elem & bit_mask); | |
| _data[word] |= mask; | |
| } | |
| }; | |
| #endif // SHARE_LIBADT_VECTSET_HPP |