1 /* 2 Copyright (c) 2005-2023 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 // a hash table buffer that can expand, and can support as many deletions as 18 // additions, list-based, with elements of list held in array (for destruction 19 // management), multiplicative hashing (like ets). No synchronization built-in. 20 // 21 22 #ifndef __TBB__flow_graph_hash_buffer_impl_H 23 #define __TBB__flow_graph_hash_buffer_impl_H 24 25 #ifndef __TBB_flow_graph_H 26 #error Do not #include this internal file directly; use public TBB headers instead. 27 #endif 28 29 // included in namespace tbb::flow::interfaceX::internal 30 31 // elements in the table are a simple list; we need pointer to next element to 32 // traverse the chain 33 template<typename ValueType> 34 struct buffer_element_type { 35 // the second parameter below is void * because we can't forward-declare the type 36 // itself, so we just reinterpret_cast below. 37 typedef typename aligned_pair<ValueType, void *>::type type; 38 }; 39 40 template 41 < 42 typename Key, // type of key within ValueType 43 typename ValueType, 44 typename ValueToKey, // abstract method that returns "const Key" or "const Key&" given ValueType 45 typename HashCompare, // has hash and equal 46 typename Allocator=tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type > 47 > 48 class hash_buffer : public HashCompare { 49 public: 50 static const size_t INITIAL_SIZE = 8; // initial size of the hash pointer table 51 typedef ValueType value_type; 52 typedef typename buffer_element_type< value_type >::type element_type; 53 typedef value_type *pointer_type; 54 typedef element_type *list_array_type; // array we manage manually 55 typedef list_array_type *pointer_array_type; 56 typedef typename std::allocator_traits<Allocator>::template rebind_alloc<list_array_type> pointer_array_allocator_type; 57 typedef typename std::allocator_traits<Allocator>::template rebind_alloc<element_type> elements_array_allocator; 58 typedef typename std::decay<Key>::type Knoref; 59 60 private: 61 ValueToKey *my_key; 62 size_t my_size; 63 size_t nelements; 64 pointer_array_type pointer_array; // pointer_array[my_size] 65 list_array_type elements_array; // elements_array[my_size / 2] 66 element_type* free_list; 67 mask()68 size_t mask() { return my_size - 1; } 69 set_up_free_list(element_type ** p_free_list,list_array_type la,size_t sz)70 void set_up_free_list( element_type **p_free_list, list_array_type la, size_t sz) { 71 for(size_t i=0; i < sz - 1; ++i ) { // construct free list 72 la[i].second = &(la[i+1]); 73 } 74 la[sz-1].second = nullptr; 75 *p_free_list = (element_type *)&(la[0]); 76 } 77 78 // cleanup for exceptions 79 struct DoCleanup { 80 pointer_array_type *my_pa; 81 list_array_type *my_elements; 82 size_t my_size; 83 DoCleanupDoCleanup84 DoCleanup(pointer_array_type &pa, list_array_type &my_els, size_t sz) : 85 my_pa(&pa), my_elements(&my_els), my_size(sz) { } ~DoCleanupDoCleanup86 ~DoCleanup() { 87 if(my_pa) { 88 size_t dont_care = 0; 89 internal_free_buffer(*my_pa, *my_elements, my_size, dont_care); 90 } 91 } 92 }; 93 94 // exception-safety requires we do all the potentially-throwing operations first grow_array()95 void grow_array() { 96 size_t new_size = my_size*2; 97 size_t new_nelements = nelements; // internal_free_buffer zeroes this 98 list_array_type new_elements_array = nullptr; 99 pointer_array_type new_pointer_array = nullptr; 100 list_array_type new_free_list = nullptr; 101 { 102 DoCleanup my_cleanup(new_pointer_array, new_elements_array, new_size); 103 new_elements_array = elements_array_allocator().allocate(my_size); 104 new_pointer_array = pointer_array_allocator_type().allocate(new_size); 105 for(size_t i=0; i < new_size; ++i) new_pointer_array[i] = nullptr; 106 set_up_free_list(&new_free_list, new_elements_array, my_size ); 107 108 for(size_t i=0; i < my_size; ++i) { 109 for( element_type* op = pointer_array[i]; op; op = (element_type *)(op->second)) { 110 value_type *ov = reinterpret_cast<value_type *>(&(op->first)); 111 // could have std::move semantics 112 internal_insert_with_key(new_pointer_array, new_size, new_free_list, *ov); 113 } 114 } 115 my_cleanup.my_pa = nullptr; 116 my_cleanup.my_elements = nullptr; 117 } 118 119 internal_free_buffer(pointer_array, elements_array, my_size, nelements); 120 free_list = new_free_list; 121 pointer_array = new_pointer_array; 122 elements_array = new_elements_array; 123 my_size = new_size; 124 nelements = new_nelements; 125 } 126 127 // v should have perfect forwarding if std::move implemented. 128 // we use this method to move elements in grow_array, so can't use class fields internal_insert_with_key(element_type ** p_pointer_array,size_t p_sz,list_array_type & p_free_list,const value_type & v)129 void internal_insert_with_key( element_type **p_pointer_array, size_t p_sz, list_array_type &p_free_list, 130 const value_type &v) { 131 size_t l_mask = p_sz-1; 132 __TBB_ASSERT(my_key, "Error: value-to-key functor not provided"); 133 size_t h = this->hash(tbb::detail::invoke(*my_key, v)) & l_mask; 134 __TBB_ASSERT(p_free_list, "Error: free list not set up."); 135 element_type* my_elem = p_free_list; p_free_list = (element_type *)(p_free_list->second); 136 (void) new(&(my_elem->first)) value_type(v); 137 my_elem->second = p_pointer_array[h]; 138 p_pointer_array[h] = my_elem; 139 } 140 internal_initialize_buffer()141 void internal_initialize_buffer() { 142 pointer_array = pointer_array_allocator_type().allocate(my_size); 143 for(size_t i = 0; i < my_size; ++i) pointer_array[i] = nullptr; 144 elements_array = elements_array_allocator().allocate(my_size / 2); 145 set_up_free_list(&free_list, elements_array, my_size / 2); 146 } 147 148 // made static so an enclosed class can use to properly dispose of the internals internal_free_buffer(pointer_array_type & pa,list_array_type & el,size_t & sz,size_t & ne)149 static void internal_free_buffer( pointer_array_type &pa, list_array_type &el, size_t &sz, size_t &ne ) { 150 if(pa) { 151 for(size_t i = 0; i < sz; ++i ) { 152 element_type *p_next; 153 for( element_type *p = pa[i]; p; p = p_next) { 154 p_next = (element_type *)p->second; 155 // TODO revamp: make sure type casting is correct. 156 void* ptr = (void*)(p->first); 157 #if _MSC_VER && _MSC_VER <= 1900 && !__INTEL_COMPILER 158 suppress_unused_warning(ptr); 159 #endif 160 ((value_type*)ptr)->~value_type(); 161 } 162 } 163 pointer_array_allocator_type().deallocate(pa, sz); 164 pa = nullptr; 165 } 166 // Separate test (if allocation of pa throws, el may be allocated. 167 // but no elements will be constructed.) 168 if(el) { 169 elements_array_allocator().deallocate(el, sz / 2); 170 el = nullptr; 171 } 172 sz = INITIAL_SIZE; 173 ne = 0; 174 } 175 176 public: hash_buffer()177 hash_buffer() : my_key(nullptr), my_size(INITIAL_SIZE), nelements(0) { 178 internal_initialize_buffer(); 179 } 180 ~hash_buffer()181 ~hash_buffer() { 182 internal_free_buffer(pointer_array, elements_array, my_size, nelements); 183 delete my_key; 184 my_key = nullptr; 185 } 186 hash_buffer(const hash_buffer&) = delete; 187 hash_buffer& operator=(const hash_buffer&) = delete; 188 reset()189 void reset() { 190 internal_free_buffer(pointer_array, elements_array, my_size, nelements); 191 internal_initialize_buffer(); 192 } 193 194 // Take ownership of func object allocated with new. 195 // This method is only used internally, so can't be misused by user. set_key_func(ValueToKey * vtk)196 void set_key_func(ValueToKey *vtk) { my_key = vtk; } 197 // pointer is used to clone() get_key_func()198 ValueToKey* get_key_func() { return my_key; } 199 insert_with_key(const value_type & v)200 bool insert_with_key(const value_type &v) { 201 pointer_type p = nullptr; 202 __TBB_ASSERT(my_key, "Error: value-to-key functor not provided"); 203 if(find_ref_with_key(tbb::detail::invoke(*my_key, v), p)) { 204 p->~value_type(); 205 (void) new(p) value_type(v); // copy-construct into the space 206 return false; 207 } 208 ++nelements; 209 if(nelements*2 > my_size) grow_array(); 210 internal_insert_with_key(pointer_array, my_size, free_list, v); 211 return true; 212 } 213 214 // returns true and sets v to array element if found, else returns false. find_ref_with_key(const Knoref & k,pointer_type & v)215 bool find_ref_with_key(const Knoref& k, pointer_type &v) { 216 size_t i = this->hash(k) & mask(); 217 for(element_type* p = pointer_array[i]; p; p = (element_type *)(p->second)) { 218 pointer_type pv = reinterpret_cast<pointer_type>(&(p->first)); 219 __TBB_ASSERT(my_key, "Error: value-to-key functor not provided"); 220 if(this->equal(tbb::detail::invoke(*my_key, *pv), k)) { 221 v = pv; 222 return true; 223 } 224 } 225 return false; 226 } 227 find_with_key(const Knoref & k,value_type & v)228 bool find_with_key( const Knoref& k, value_type &v) { 229 value_type *p; 230 if(find_ref_with_key(k, p)) { 231 v = *p; 232 return true; 233 } 234 else 235 return false; 236 } 237 delete_with_key(const Knoref & k)238 void delete_with_key(const Knoref& k) { 239 size_t h = this->hash(k) & mask(); 240 element_type* prev = nullptr; 241 for(element_type* p = pointer_array[h]; p; prev = p, p = (element_type *)(p->second)) { 242 value_type *vp = reinterpret_cast<value_type *>(&(p->first)); 243 __TBB_ASSERT(my_key, "Error: value-to-key functor not provided"); 244 if(this->equal(tbb::detail::invoke(*my_key, *vp), k)) { 245 vp->~value_type(); 246 if(prev) prev->second = p->second; 247 else pointer_array[h] = (element_type *)(p->second); 248 p->second = free_list; 249 free_list = p; 250 --nelements; 251 return; 252 } 253 } 254 __TBB_ASSERT(false, "key not found for delete"); 255 } 256 }; 257 #endif // __TBB__flow_graph_hash_buffer_impl_H 258