24 |
24 |
25 #include "precompiled.hpp" |
25 #include "precompiled.hpp" |
26 #include "libadt/vectset.hpp" |
26 #include "libadt/vectset.hpp" |
27 #include "memory/allocation.inline.hpp" |
27 #include "memory/allocation.inline.hpp" |
28 #include "memory/arena.hpp" |
28 #include "memory/arena.hpp" |
|
29 #include "utilities/count_leading_zeros.hpp" |
29 |
30 |
30 VectorSet::VectorSet(Arena *arena) { |
31 VectorSet::VectorSet(Arena *arena) : _size(2), |
31 _set_arena = arena; |
32 _data(NEW_ARENA_ARRAY(arena, uint32_t, 2)), |
32 size = 2; // Small initial size |
33 _set_arena(arena) { |
33 data = (uint32_t *)_set_arena->Amalloc(size*sizeof(uint32_t)); |
34 _data[0] = 0; |
34 data[0] = 0; // No elements |
35 _data[1] = 0; |
35 data[1] = 0; |
|
36 } |
36 } |
37 |
37 |
38 // Expand the existing set to a bigger size |
38 // Expand the existing set to a bigger size |
39 void VectorSet::grow(uint newsize) { |
39 void VectorSet::grow(uint new_size) { |
40 newsize = (newsize+31) >> 5; |
40 new_size = (new_size + bit_mask) >> word_bits; |
41 uint x = size; |
41 assert(new_size != 0 && new_size < (1U << 31), ""); |
42 while (x < newsize) { |
42 uint x = (1U << 31) >> (count_leading_zeros(new_size) - 1); |
43 x <<= 1; |
43 _data = REALLOC_ARENA_ARRAY(_set_arena, uint32_t, _data, _size, x); |
44 } |
44 Copy::zero_to_bytes(_data + _size, (x - _size) * sizeof(uint32_t)); |
45 data = (uint32_t *)_set_arena->Arealloc(data, size*sizeof(uint32_t), x*sizeof(uint32_t)); |
45 _size = x; |
46 memset((char*)(data + size), 0, (x - size) * sizeof(uint32_t)); |
|
47 size = x; |
|
48 } |
46 } |
49 |
47 |
50 // Insert a member into an existing Set. |
48 // Insert a member into an existing Set. |
51 void VectorSet::insert(uint elem) { |
49 void VectorSet::insert(uint elem) { |
52 uint word = elem >> 5; |
50 uint32_t word = elem >> word_bits; |
53 uint32_t mask = 1L << (elem & 31); |
51 uint32_t mask = 1U << (elem & bit_mask); |
54 if (word >= size) { |
52 if (word >= _size) { |
55 grow(elem + 1); |
53 grow(elem + 1); |
56 } |
54 } |
57 data[word] |= mask; |
55 _data[word] |= mask; |
58 } |
56 } |
59 |
57 |
60 // Clear a set |
58 // Resets the storage |
61 void VectorSet::clear() { |
59 void VectorSet::reset_memory() { |
62 if( size > 100 ) { // Reclaim storage only if huge |
60 assert(_size >= 2, "_size can never be less than 2"); |
63 FREE_RESOURCE_ARRAY(uint32_t,data,size); |
61 _data = REALLOC_ARENA_ARRAY(_set_arena, uint32_t, _data, _size, 2); |
64 size = 2; // Small initial size |
62 _size = 2; |
65 data = NEW_RESOURCE_ARRAY(uint32_t,size); |
63 _data[0] = 0; |
66 } |
64 _data[1] = 0; |
67 memset(data, 0, size*sizeof(uint32_t)); |
|
68 } |
65 } |
69 |
66 |
70 // Return true if the set is empty |
67 // Return true if the set is empty |
71 bool VectorSet::is_empty() const { |
68 bool VectorSet::is_empty() const { |
72 for (uint32_t i = 0; i < size; i++) { |
69 for (uint32_t i = 0; i < _size; i++) { |
73 if (data[i] != 0) { |
70 if (_data[i] != 0) { |
74 return false; |
71 return false; |
75 } |
72 } |
76 } |
73 } |
77 return true; |
74 return true; |
78 } |
75 } |
79 |
|
80 int VectorSet::hash() const { |
|
81 uint32_t _xor = 0; |
|
82 uint lim = ((size < 4) ? size : 4); |
|
83 for (uint i = 0; i < lim; i++) { |
|
84 _xor ^= data[i]; |
|
85 } |
|
86 return (int)_xor; |
|
87 } |
|