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