# HG changeset patch # User redestad # Date 1574089832 -3600 # Node ID 7cbffba2156b57c30922b74bacf985b3e67f6361 # Parent fc68b2cdfeebe0ff243703a62bcbf935cf2afafa 8234248: More VectorSet cleanups Reviewed-by: neliasso, thartmann diff -r fc68b2cdfeeb -r 7cbffba2156b src/hotspot/share/libadt/vectset.cpp --- a/src/hotspot/share/libadt/vectset.cpp Wed Nov 06 18:06:36 2019 +0100 +++ b/src/hotspot/share/libadt/vectset.cpp Mon Nov 18 16:10:32 2019 +0100 @@ -26,62 +26,50 @@ #include "libadt/vectset.hpp" #include "memory/allocation.inline.hpp" #include "memory/arena.hpp" +#include "utilities/count_leading_zeros.hpp" -VectorSet::VectorSet(Arena *arena) { - _set_arena = arena; - size = 2; // Small initial size - data = (uint32_t *)_set_arena->Amalloc(size*sizeof(uint32_t)); - data[0] = 0; // No elements - data[1] = 0; +VectorSet::VectorSet(Arena *arena) : _size(2), + _data(NEW_ARENA_ARRAY(arena, uint32_t, 2)), + _set_arena(arena) { + _data[0] = 0; + _data[1] = 0; } // Expand the existing set to a bigger size -void VectorSet::grow(uint newsize) { - newsize = (newsize+31) >> 5; - uint x = size; - while (x < newsize) { - x <<= 1; - } - data = (uint32_t *)_set_arena->Arealloc(data, size*sizeof(uint32_t), x*sizeof(uint32_t)); - memset((char*)(data + size), 0, (x - size) * sizeof(uint32_t)); - size = x; +void VectorSet::grow(uint new_size) { + new_size = (new_size + bit_mask) >> word_bits; + assert(new_size != 0 && new_size < (1U << 31), ""); + uint x = (1U << 31) >> (count_leading_zeros(new_size) - 1); + _data = REALLOC_ARENA_ARRAY(_set_arena, uint32_t, _data, _size, x); + Copy::zero_to_bytes(_data + _size, (x - _size) * sizeof(uint32_t)); + _size = x; } // Insert a member into an existing Set. void VectorSet::insert(uint elem) { - uint word = elem >> 5; - uint32_t mask = 1L << (elem & 31); - if (word >= size) { + uint32_t word = elem >> word_bits; + uint32_t mask = 1U << (elem & bit_mask); + if (word >= _size) { grow(elem + 1); } - data[word] |= mask; + _data[word] |= mask; } -// Clear a set -void VectorSet::clear() { - if( size > 100 ) { // Reclaim storage only if huge - FREE_RESOURCE_ARRAY(uint32_t,data,size); - size = 2; // Small initial size - data = NEW_RESOURCE_ARRAY(uint32_t,size); - } - memset(data, 0, size*sizeof(uint32_t)); +// Resets the storage +void VectorSet::reset_memory() { + assert(_size >= 2, "_size can never be less than 2"); + _data = REALLOC_ARENA_ARRAY(_set_arena, uint32_t, _data, _size, 2); + _size = 2; + _data[0] = 0; + _data[1] = 0; } // Return true if the set is empty bool VectorSet::is_empty() const { - for (uint32_t i = 0; i < size; i++) { - if (data[i] != 0) { + for (uint32_t i = 0; i < _size; i++) { + if (_data[i] != 0) { return false; } } return true; } - -int VectorSet::hash() const { - uint32_t _xor = 0; - uint lim = ((size < 4) ? size : 4); - for (uint i = 0; i < lim; i++) { - _xor ^= data[i]; - } - return (int)_xor; -} diff -r fc68b2cdfeeb -r 7cbffba2156b src/hotspot/share/libadt/vectset.hpp --- a/src/hotspot/share/libadt/vectset.hpp Wed Nov 06 18:06:36 2019 +0100 +++ b/src/hotspot/share/libadt/vectset.hpp Mon Nov 18 16:10:32 2019 +0100 @@ -26,6 +26,7 @@ #define SHARE_LIBADT_VECTSET_HPP #include "memory/allocation.hpp" +#include "utilities/copy.hpp" // Vector Sets @@ -35,26 +36,33 @@ //------------------------------VectorSet-------------------------------------- class VectorSet : public ResourceObj { private: - uint size; // Size of data IN LONGWORDS (32bits) - uint32_t* data; // The data, bit packed - Arena *_set_arena; + + static const uint word_bits = 5; + static const uint bit_mask = 31; + + uint _size; // Size of data in 32-bit words + uint32_t* _data; // The data, bit packed + Arena* _set_arena; void grow(uint newsize); // Grow vector to required bitsize - + void reset_memory(); public: VectorSet(Arena *arena); ~VectorSet() {} + void insert(uint elem); - - void clear(); bool is_empty() const; - int hash() const; void reset() { - memset(data, 0, size*sizeof(uint32_t)); + Copy::zero_to_bytes(_data, _size * sizeof(uint32_t)); } - - // Expose internals for speed-critical fast iterators - uint word_size() const { return size; } + void clear() { + // Reclaim storage if huge + if (_size > 100) { + reset_memory(); + } else { + reset(); + } + } // Fast inlined "test and set". Replaces the idiom: // if (visited.test(idx)) return; @@ -62,46 +70,46 @@ // With: // if (visited.test_set(idx)) return; // - int test_set(uint elem) { - uint word = elem >> 5; // Get the longword offset - if (word >= size) { + bool test_set(uint elem) { + uint32_t word = elem >> word_bits; + if (word >= _size) { // Then grow; set; return 0; this->insert(elem); - return 0; + return false; } - uint32_t mask = 1L << (elem & 31); // Get bit mask - uint32_t datum = data[word] & mask;// Get bit - data[word] |= mask; // Set bit - return datum; // Return bit + uint32_t mask = 1U << (elem & bit_mask); + uint32_t data = _data[word]; + _data[word] = data | mask; + return (data & mask) != 0; } // Fast inlined test - int test(uint elem) const { - uint word = elem >> 5; - if (word >= size) { - return 0; + bool test(uint elem) const { + uint32_t word = elem >> word_bits; + if (word >= _size) { + return false; } - uint32_t mask = 1L << (elem & 31); - return data[word] & mask; + uint32_t mask = 1U << (elem & bit_mask); + return (_data[word] & mask) != 0; } void remove(uint elem) { - uint word = elem >> 5; - if (word >= size) { + uint32_t word = elem >> word_bits; + if (word >= _size) { return; } - uint32_t mask = 1L << (elem & 31); - data[word] &= ~mask; // Clear bit + uint32_t mask = 1U << (elem & bit_mask); + _data[word] &= ~mask; // Clear bit } // Fast inlined set void set(uint elem) { - uint word = elem >> 5; - if (word >= size) { + uint32_t word = elem >> word_bits; + if (word >= _size) { this->insert(elem); } else { - uint32_t mask = 1L << (elem & 31); - data[word] |= mask; + uint32_t mask = 1U << (elem & bit_mask); + _data[word] |= mask; } } };