vectset.hpp

/*
 * Copyright (c) 1997, 2024, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
*/

#ifndef SHARE_LIBADT_VECTSET_HPP
#defineSHARE_LIBADT_VECTSET_HPP

#include"memory/allocation.hpp"
#include"utilities/copy.hpp"

// Vector Sets

// These sets can grow or shrink, based on the initial size and the largest
// element currently in them.

//------------------------------VectorSet--------------------------------------
classVectorSet : publicAnyObj {
private:

staticconstuint word_bits = 5;
staticconstuint bit_mask = 31;

// Used 32-bit words
uint _size;
// Allocated words
uint _data_size;
uint32_t* _data;
 Arena* _set_arena;
 ReallocMark _nesting; // Safety checks for arena reallocation

voidinit(Arena* arena);

// Grow vector to required word capacity
voidmaybe_grow(uint new_word_capacity) {
if (new_word_capacity >= _size) {
grow(new_word_capacity);
 }
 }
voidgrow(uint new_word_capacity);

public:
VectorSet();
VectorSet(Arena* arena);
~VectorSet() {}

NONCOPYABLE(VectorSet);
 VectorSet& operator=(VectorSet&&) = delete;
// Allow move constructor for && (eg. capture return of function)
VectorSet(VectorSet&&) = default;

voidinsert(uint elem);
boolis_empty() const;
voidreset() {
 _size = 0;
 }
voidclear() {
reset();
 }

// Fast inlined "test and set". Replaces the idiom:
// if (visited.test(idx)) return;
// visited.set(idx);
// With:
// if (visited.test_set(idx)) return;
//
booltest_set(uint elem) {
uint32_t word = elem >> word_bits;
maybe_grow(word);
uint32_t mask = 1U << (elem & bit_mask);
uint32_t data = _data[word];
 _data[word] = data | mask;
return (data & mask) != 0;
 }

// Fast inlined test
booltest(uint elem) const {
uint32_t word = elem >> word_bits;
if (word >= _size) {
returnfalse;
 }
uint32_t mask = 1U << (elem & bit_mask);
return (_data[word] & mask) != 0;
 }

voidremove(uint elem) {
uint32_t word = elem >> word_bits;
if (word >= _size) {
return;
 }
uint32_t mask = 1U << (elem & bit_mask);
 _data[word] &= ~mask; // Clear bit
 }

// Fast inlined set
voidset(uint elem) {
uint32_t word = elem >> word_bits;
maybe_grow(word);
uint32_t mask = 1U << (elem & bit_mask);
 _data[word] |= mask;
 }
};

#endif// SHARE_LIBADT_VECTSET_HPP