1 /*
2 * Copyright (c) 1997, 2023, 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 friend VectorSet intersect(const VectorSet&, const VectorSet&);
39
40 private:
41
42 static const uint word_bits = 5;
43 static const uint bit_mask = 31;
44
45 // Used 32-bit words
46 uint _size;
47 // Allocated words
48 uint32_t* _data;
49 Arena* _set_arena;
50
51 void init(Arena* arena);
52 // Grow vector to required word capacity
53 void grow(uint new_word_capacity);
54 public:
55 VectorSet();
56 VectorSet(Arena* arena);
57 ~VectorSet() {}
58
59 NONCOPYABLE(VectorSet);
60 VectorSet& operator=(VectorSet&&) = delete;
61 // Allow move constructor for && (eg. capture return of function)
62 VectorSet(VectorSet&&) = default;
63
64 void insert(uint elem);
65 bool is_empty() const;
66 void reset() {
67 _size = 0;
68 }
69 void clear() {
70 reset();
71 }
72
73 // Fast inlined "test and set". Replaces the idiom:
74 // if (visited.test(idx)) return;
75 // visited.set(idx);
76 // With:
77 // if (visited.test_set(idx)) return;
78 //
79 bool test_set(uint elem) {
80 uint32_t word = elem >> word_bits;
81 if (word >= _size) {
82 // Then grow
83 grow(word);
84 }
85 uint32_t mask = 1U << (elem & bit_mask);
86 uint32_t data = _data[word];
87 _data[word] = data | mask;
88 return (data & mask) != 0;
89 }
90
91 // Fast inlined test
92 bool test(uint elem) const {
93 uint32_t word = elem >> word_bits;
94 if (word >= _size) {
95 return false;
96 }
97 uint32_t mask = 1U << (elem & bit_mask);
98 return (_data[word] & mask) != 0;
99 }
100
101 void remove(uint elem) {
102 uint32_t word = elem >> word_bits;
103 if (word >= _size) {
104 return;
105 }
106 uint32_t mask = 1U << (elem & bit_mask);
107 _data[word] &= ~mask; // Clear bit
108 }
109
110 // Fast inlined set
111 void set(uint elem) {
112 uint32_t word = elem >> word_bits;
113 if (word >= _size) {
114 grow(word);
115 }
116 uint32_t mask = 1U << (elem & bit_mask);
117 _data[word] |= mask;
118 }
119
120 #ifndef PRODUCT
121 void print_on(outputStream* st) const override;
122 #endif // PRODUCT
123 };
124
125 VectorSet intersect(const VectorSet& lhs, const VectorSet& rhs);
126 #endif // SHARE_LIBADT_VECTSET_HPP