24 |
24 |
25 #ifndef SHARE_LIBADT_VECTSET_HPP |
25 #ifndef SHARE_LIBADT_VECTSET_HPP |
26 #define SHARE_LIBADT_VECTSET_HPP |
26 #define SHARE_LIBADT_VECTSET_HPP |
27 |
27 |
28 #include "memory/allocation.hpp" |
28 #include "memory/allocation.hpp" |
|
29 #include "utilities/copy.hpp" |
29 |
30 |
30 // Vector Sets |
31 // Vector Sets |
31 |
32 |
32 // These sets can grow or shrink, based on the initial size and the largest |
33 // These sets can grow or shrink, based on the initial size and the largest |
33 // element currently in them. |
34 // element currently in them. |
34 |
35 |
35 //------------------------------VectorSet-------------------------------------- |
36 //------------------------------VectorSet-------------------------------------- |
36 class VectorSet : public ResourceObj { |
37 class VectorSet : public ResourceObj { |
37 private: |
38 private: |
38 uint size; // Size of data IN LONGWORDS (32bits) |
39 |
39 uint32_t* data; // The data, bit packed |
40 static const uint word_bits = 5; |
40 Arena *_set_arena; |
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; |
41 |
46 |
42 void grow(uint newsize); // Grow vector to required bitsize |
47 void grow(uint newsize); // Grow vector to required bitsize |
43 |
48 void reset_memory(); |
44 public: |
49 public: |
45 VectorSet(Arena *arena); |
50 VectorSet(Arena *arena); |
46 ~VectorSet() {} |
51 ~VectorSet() {} |
|
52 |
47 void insert(uint elem); |
53 void insert(uint elem); |
48 |
|
49 void clear(); |
|
50 bool is_empty() const; |
54 bool is_empty() const; |
51 int hash() const; |
|
52 void reset() { |
55 void reset() { |
53 memset(data, 0, size*sizeof(uint32_t)); |
56 Copy::zero_to_bytes(_data, _size * sizeof(uint32_t)); |
54 } |
57 } |
55 |
58 void clear() { |
56 // Expose internals for speed-critical fast iterators |
59 // Reclaim storage if huge |
57 uint word_size() const { return size; } |
60 if (_size > 100) { |
|
61 reset_memory(); |
|
62 } else { |
|
63 reset(); |
|
64 } |
|
65 } |
58 |
66 |
59 // Fast inlined "test and set". Replaces the idiom: |
67 // Fast inlined "test and set". Replaces the idiom: |
60 // if (visited.test(idx)) return; |
68 // if (visited.test(idx)) return; |
61 // visited.set(idx); |
69 // visited.set(idx); |
62 // With: |
70 // With: |
63 // if (visited.test_set(idx)) return; |
71 // if (visited.test_set(idx)) return; |
64 // |
72 // |
65 int test_set(uint elem) { |
73 bool test_set(uint elem) { |
66 uint word = elem >> 5; // Get the longword offset |
74 uint32_t word = elem >> word_bits; |
67 if (word >= size) { |
75 if (word >= _size) { |
68 // Then grow; set; return 0; |
76 // Then grow; set; return 0; |
69 this->insert(elem); |
77 this->insert(elem); |
70 return 0; |
78 return false; |
71 } |
79 } |
72 uint32_t mask = 1L << (elem & 31); // Get bit mask |
80 uint32_t mask = 1U << (elem & bit_mask); |
73 uint32_t datum = data[word] & mask;// Get bit |
81 uint32_t data = _data[word]; |
74 data[word] |= mask; // Set bit |
82 _data[word] = data | mask; |
75 return datum; // Return bit |
83 return (data & mask) != 0; |
76 } |
84 } |
77 |
85 |
78 // Fast inlined test |
86 // Fast inlined test |
79 int test(uint elem) const { |
87 bool test(uint elem) const { |
80 uint word = elem >> 5; |
88 uint32_t word = elem >> word_bits; |
81 if (word >= size) { |
89 if (word >= _size) { |
82 return 0; |
90 return false; |
83 } |
91 } |
84 uint32_t mask = 1L << (elem & 31); |
92 uint32_t mask = 1U << (elem & bit_mask); |
85 return data[word] & mask; |
93 return (_data[word] & mask) != 0; |
86 } |
94 } |
87 |
95 |
88 void remove(uint elem) { |
96 void remove(uint elem) { |
89 uint word = elem >> 5; |
97 uint32_t word = elem >> word_bits; |
90 if (word >= size) { |
98 if (word >= _size) { |
91 return; |
99 return; |
92 } |
100 } |
93 uint32_t mask = 1L << (elem & 31); |
101 uint32_t mask = 1U << (elem & bit_mask); |
94 data[word] &= ~mask; // Clear bit |
102 _data[word] &= ~mask; // Clear bit |
95 } |
103 } |
96 |
104 |
97 // Fast inlined set |
105 // Fast inlined set |
98 void set(uint elem) { |
106 void set(uint elem) { |
99 uint word = elem >> 5; |
107 uint32_t word = elem >> word_bits; |
100 if (word >= size) { |
108 if (word >= _size) { |
101 this->insert(elem); |
109 this->insert(elem); |
102 } else { |
110 } else { |
103 uint32_t mask = 1L << (elem & 31); |
111 uint32_t mask = 1U << (elem & bit_mask); |
104 data[word] |= mask; |
112 _data[word] |= mask; |
105 } |
113 } |
106 } |
114 } |
107 }; |
115 }; |
108 |
116 |
109 #endif // SHARE_LIBADT_VECTSET_HPP |
117 #endif // SHARE_LIBADT_VECTSET_HPP |