author | redestad |
Mon, 18 Nov 2019 16:10:32 +0100 | |
changeset 59121 | 7cbffba2156b |
parent 58962 | 2dcfc28a314d |
permissions | -rw-r--r-- |
1 | 1 |
/* |
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
47216
diff
changeset
|
2 |
* Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved. |
1 | 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 |
* |
|
5547
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1
diff
changeset
|
19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1
diff
changeset
|
20 |
* or visit www.oracle.com if you need additional information or have any |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1
diff
changeset
|
21 |
* questions. |
1 | 22 |
* |
23 |
*/ |
|
24 |
||
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
47216
diff
changeset
|
25 |
#ifndef SHARE_LIBADT_VECTSET_HPP |
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
47216
diff
changeset
|
26 |
#define SHARE_LIBADT_VECTSET_HPP |
7397 | 27 |
|
58962 | 28 |
#include "memory/allocation.hpp" |
59121 | 29 |
#include "utilities/copy.hpp" |
7397 | 30 |
|
58962 | 31 |
// Vector Sets |
1 | 32 |
|
33 |
// These sets can grow or shrink, based on the initial size and the largest |
|
58962 | 34 |
// element currently in them. |
1 | 35 |
|
36 |
//------------------------------VectorSet-------------------------------------- |
|
58962 | 37 |
class VectorSet : public ResourceObj { |
38 |
private: |
|
59121 | 39 |
|
40 |
static const uint word_bits = 5; |
|
41 |
static const uint bit_mask = 31; |
|
42 |
||
43 |
uint _size; // Size of data in 32-bit words |
|
44 |
uint32_t* _data; // The data, bit packed |
|
45 |
Arena* _set_arena; |
|
1 | 46 |
|
58962 | 47 |
void grow(uint newsize); // Grow vector to required bitsize |
59121 | 48 |
void reset_memory(); |
1 | 49 |
public: |
58962 | 50 |
VectorSet(Arena *arena); |
1 | 51 |
~VectorSet() {} |
59121 | 52 |
|
58962 | 53 |
void insert(uint elem); |
54 |
bool is_empty() const; |
|
55 |
void reset() { |
|
59121 | 56 |
Copy::zero_to_bytes(_data, _size * sizeof(uint32_t)); |
8319 | 57 |
} |
59121 | 58 |
void clear() { |
59 |
// Reclaim storage if huge |
|
60 |
if (_size > 100) { |
|
61 |
reset_memory(); |
|
62 |
} else { |
|
63 |
reset(); |
|
64 |
} |
|
65 |
} |
|
1 | 66 |
|
67 |
// Fast inlined "test and set". Replaces the idiom: |
|
58962 | 68 |
// if (visited.test(idx)) return; |
69 |
// visited.set(idx); |
|
1 | 70 |
// With: |
58962 | 71 |
// if (visited.test_set(idx)) return; |
1 | 72 |
// |
59121 | 73 |
bool test_set(uint elem) { |
74 |
uint32_t word = elem >> word_bits; |
|
75 |
if (word >= _size) { |
|
58962 | 76 |
// Then grow; set; return 0; |
77 |
this->insert(elem); |
|
59121 | 78 |
return false; |
58962 | 79 |
} |
59121 | 80 |
uint32_t mask = 1U << (elem & bit_mask); |
81 |
uint32_t data = _data[word]; |
|
82 |
_data[word] = data | mask; |
|
83 |
return (data & mask) != 0; |
|
1 | 84 |
} |
85 |
||
86 |
// Fast inlined test |
|
59121 | 87 |
bool test(uint elem) const { |
88 |
uint32_t word = elem >> word_bits; |
|
89 |
if (word >= _size) { |
|
90 |
return false; |
|
58962 | 91 |
} |
59121 | 92 |
uint32_t mask = 1U << (elem & bit_mask); |
93 |
return (_data[word] & mask) != 0; |
|
58962 | 94 |
} |
95 |
||
96 |
void remove(uint elem) { |
|
59121 | 97 |
uint32_t word = elem >> word_bits; |
98 |
if (word >= _size) { |
|
58962 | 99 |
return; |
100 |
} |
|
59121 | 101 |
uint32_t mask = 1U << (elem & bit_mask); |
102 |
_data[word] &= ~mask; // Clear bit |
|
1 | 103 |
} |
104 |
||
105 |
// Fast inlined set |
|
58962 | 106 |
void set(uint elem) { |
59121 | 107 |
uint32_t word = elem >> word_bits; |
108 |
if (word >= _size) { |
|
58962 | 109 |
this->insert(elem); |
1 | 110 |
} else { |
59121 | 111 |
uint32_t mask = 1U << (elem & bit_mask); |
112 |
_data[word] |= mask; |
|
1 | 113 |
} |
114 |
} |
|
115 |
}; |
|
116 |
||
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
47216
diff
changeset
|
117 |
#endif // SHARE_LIBADT_VECTSET_HPP |