1 /*
2 * Copyright (c) 1997, 2019, 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 "precompiled.hpp"
26 #include "libadt/vectset.hpp"
27 #include "memory/arena.hpp"
28 #include "memory/resourceArea.hpp"
29 #include "utilities/count_leading_zeros.hpp"
30 #include "utilities/powerOfTwo.hpp"
31
32 VectorSet::VectorSet() {
33 init(Thread::current()->resource_area());
34 }
35
36 VectorSet::VectorSet(Arena* arena) {
37 init(arena);
38 }
39
40 void VectorSet::init(Arena* arena) {
41 _size = 2;
42 _data = NEW_ARENA_ARRAY(arena, uint32_t, 2);
43 _data_size = 2;
44 _set_arena = arena;
45 _data[0] = 0;
46 _data[1] = 0;
47 }
48
49 // Expand the existing set to a bigger size
50 void VectorSet::grow(uint new_word_capacity) {
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 if (word >= _size) {
66 grow(word);
67 }
68 _data[word] |= mask;
69 }
70
71 // Return true if the set is empty
72 bool VectorSet::is_empty() const {
73 for (uint32_t i = 0; i < _size; i++) {
74 if (_data[i] != 0) {
75 return false;
76 }
77 }
78 return true;
79 }
|
1 /*
2 * Copyright (c) 1997, 2022, 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 "precompiled.hpp"
26 #include "libadt/vectset.hpp"
27 #include "memory/arena.hpp"
28 #include "memory/resourceArea.hpp"
29 #include "utilities/count_leading_zeros.hpp"
30 #include "utilities/powerOfTwo.hpp"
31
32 VectorSet::VectorSet() {
33 init(Thread::current()->resource_area());
34 }
35
36 VectorSet::VectorSet(Arena* arena) {
37 init(arena);
38 }
39
40 void VectorSet::init(Arena* arena) {
41 _size = 2;
42 _data = NEW_ARENA_ARRAY(arena, uint32_t, 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 < (1U << 30), "");
51 uint x = next_power_of_2(new_word_capacity);
52 if (x > _size) {
53 _data = REALLOC_ARENA_ARRAY(_set_arena, uint32_t, _data, _size, x);
54 Copy::zero_to_bytes(_data + _size, (x - _size) * sizeof(uint32_t));
55 _size = x;
56 }
57 }
58
59 // Insert a member into an existing Set.
60 void VectorSet::insert(uint elem) {
61 uint32_t word = elem >> word_bits;
62 uint32_t mask = 1U << (elem & bit_mask);
63 if (word >= _size) {
64 grow(word);
65 }
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 }
78
79 #ifndef PRODUCT
80 void VectorSet::print_on(outputStream* st) const {
81 st->print("VectorSet(" PTR_FORMAT ")", p2i(this));
82 if (is_empty()) {
83 st->print_cr(" empty");
84 return;
85 }
86
87 bool first = false;
88 for (uint i = 0; i < (_size << word_bits); ++i) {
89 if (test(i)) {
90 if (!first) {
91 st->print(" [%u", i);
92 first = true;
93 } else {
94 st->print(",%u", i);
95 }
96 }
97 }
98 st->print_cr("]");
99 }
100 #endif
101
102 VectorSet intersect(const VectorSet& lhs, const VectorSet& rhs) {
103 VectorSet result;
104 uint min;
105 if (lhs._size > rhs._size) {
106 result.grow(lhs._size);
107 min = rhs._size;
108 } else {
109 result.grow(rhs._size);
110 min = lhs._size;
111 }
112 for (uint i = 0; i < min; ++i) {
113 result._data[i] = lhs._data[i] & rhs._data[i];
114 }
115 return result;
116 }
|