1 /*
 2  * Copyright (c) 1997, 2025, 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 #include "libadt/vectset.hpp"
26 #include "memory/arena.hpp"
27 #include "memory/resourceArea.hpp"
28 #include "utilities/count_leading_zeros.hpp"
29 #include "utilities/powerOfTwo.hpp"
30 
31 VectorSet::VectorSet() {
32   init(Thread::current()->resource_area());
33 }
34 
35 VectorSet::VectorSet(Arena* arena) {
36   init(arena);
37 }
38 
39 void VectorSet::init(Arena* arena) {
40   _size = 2;
41   _data = NEW_ARENA_ARRAY(arena, uint32_t, 2);
42   _data_size = 2;
43   _set_arena = arena;
44   _data[0] = 0;
45   _data[1] = 0;
46 }
47 
48 // Expand the existing set to a bigger size
49 void VectorSet::grow(uint new_word_capacity) {
50   assert(new_word_capacity >= _size, "Should have been checked before, use maybe_grow?");
51   assert(new_word_capacity < (1U << 30), "");
52   uint x = next_power_of_2(new_word_capacity);
53   if (x > _data_size) {
54     _data = REALLOC_ARENA_ARRAY(_set_arena, uint32_t, _data, _size, x);
55     _data_size = x;
56   }
57   Copy::zero_to_bytes(_data + _size, (x - _size) * sizeof(uint32_t));
58   _size = x;
59 }
60 
61 // Insert a member into an existing Set.
62 void VectorSet::insert(uint elem) {
63   uint32_t word = elem >> word_bits;
64   uint32_t mask = 1U << (elem & bit_mask);
65   maybe_grow(word);
66   _data[word] |= mask;
67 }
68 
69 // Return true if the set is empty
70 bool VectorSet::is_empty() const {
71   for (uint32_t i = 0; i < _size; i++) {
72     if (_data[i] != 0) {
73       return false;
74     }
75   }
76   return true;
77 }