1 /*
2 * Copyright (c) 1997, 2024, Oracle and/or its affiliates. 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 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_LIBADT_VECTSET_HPP
26 #define SHARE_LIBADT_VECTSET_HPP
27
28 #include "memory/allocation.hpp"
29 #include "utilities/copy.hpp"
30
31 // Vector Sets
32
33 // These sets can grow or shrink, based on the initial size and the largest
34 // element currently in them.
35
36 //------------------------------VectorSet--------------------------------------
37 class VectorSet : public AnyObj {
38 private:
39
40 static const uint word_bits = 5;
41 static const uint bit_mask = 31;
42
43 // Used 32-bit words
44 uint _size;
45 // Allocated words
46 uint _data_size;
47 uint32_t* _data;
48 Arena* _set_arena;
49 ReallocMark _nesting; // Safety checks for arena reallocation
50
51 void init(Arena* arena);
52
53 // Grow vector to required word capacity
54 void maybe_grow(uint new_word_capacity) {
55 _nesting.check(_set_arena); // Check if a potential reallocation in the arena is safe
56 if (new_word_capacity >= _size) {
57 grow(new_word_capacity);
58 }
59 }
60 void grow(uint new_word_capacity);
61
62 public:
63 VectorSet();
64 VectorSet(Arena* arena);
65 ~VectorSet() {}
66
67 NONCOPYABLE(VectorSet);
68 VectorSet& operator=(VectorSet&&) = delete;
69 // Allow move constructor for && (eg. capture return of function)
70 VectorSet(VectorSet&&) = default;
71
72 void insert(uint elem);
73 bool is_empty() const;
74 void reset() {
75 _size = 0;
76 }
77 void clear() {
78 reset();
79 }
80
81 // Fast inlined "test and set". Replaces the idiom:
82 // if (visited.test(idx)) return;
83 // visited.set(idx);
84 // With:
85 // if (visited.test_set(idx)) return;
86 //
87 bool test_set(uint elem) {
88 uint32_t word = elem >> word_bits;
89 maybe_grow(word);
90 uint32_t mask = 1U << (elem & bit_mask);
91 uint32_t data = _data[word];
92 _data[word] = data | mask;
93 return (data & mask) != 0;
94 }
95
96 // Fast inlined test
97 bool test(uint elem) const {
98 uint32_t word = elem >> word_bits;
99 if (word >= _size) {
100 return false;
101 }
102 uint32_t mask = 1U << (elem & bit_mask);
103 return (_data[word] & mask) != 0;
104 }
105
106 void remove(uint elem) {
107 uint32_t word = elem >> word_bits;
108 if (word >= _size) {
109 return;
110 }
111 uint32_t mask = 1U << (elem & bit_mask);
112 _data[word] &= ~mask; // Clear bit
113 }
114
115 // Fast inlined set
116 void set(uint elem) {
117 uint32_t word = elem >> word_bits;
118 maybe_grow(word);
119 uint32_t mask = 1U << (elem & bit_mask);
120 _data[word] |= mask;
121 }
122 };
123
124 #endif // SHARE_LIBADT_VECTSET_HPP