Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
Loading...
Searching...
No Matches
_flow_graph_tagged_buffer_impl.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2005-2020 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
33template<typename ValueType>
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
40template
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
47 >
48class hash_buffer : public HashCompare {
49public:
50 static const size_t INITIAL_SIZE = 8; // initial size of the hash pointer table
51 typedef ValueType value_type;
54 typedef element_type *list_array_type; // array we manage manually
56 typedef typename Allocator::template rebind<list_array_type>::other pointer_array_allocator_type;
57 typedef typename Allocator::template rebind<element_type>::other elements_array_allocator;
59
60private:
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]
67
68 size_t mask() { return my_size - 1; }
69
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 = NULL;
75 *p_free_list = (element_type *)&(la[0]);
76 }
77
78 // cleanup for exceptions
79 struct DoCleanup {
82 size_t my_size;
83
84 DoCleanup(pointer_array_type &pa, list_array_type &my_els, size_t sz) :
85 my_pa(&pa), my_elements(&my_els), my_size(sz) { }
87 if(my_pa) {
88 size_t dont_care = 0;
90 }
91 }
92 };
93
94 // exception-safety requires we do all the potentially-throwing operations first
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 = NULL;
99 pointer_array_type new_pointer_array = NULL;
100 list_array_type new_free_list = NULL;
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] = NULL;
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 = NULL;
116 my_cleanup.my_elements = NULL;
117 }
118
120 free_list = new_free_list;
121 pointer_array = new_pointer_array;
122 elements_array = new_elements_array;
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
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((*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
143 for(size_t i = 0; i < my_size; ++i) pointer_array[i] = NULL;
146 }
147
148 // made static so an enclosed class can use to properly dispose of the internals
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 internal::punned_cast<value_type *>(&(p->first))->~value_type();
156 }
157 }
158 pointer_array_allocator_type().deallocate(pa, sz);
159 pa = NULL;
160 }
161 // Separate test (if allocation of pa throws, el may be allocated.
162 // but no elements will be constructed.)
163 if(el) {
164 elements_array_allocator().deallocate(el, sz / 2);
165 el = NULL;
166 }
167 sz = INITIAL_SIZE;
168 ne = 0;
169 }
170
171public:
174 }
175
178 if(my_key) delete my_key;
179 }
180
181 void reset() {
184 }
185
186 // Take ownership of func object allocated with new.
187 // This method is only used internally, so can't be misused by user.
188 void set_key_func(ValueToKey *vtk) { my_key = vtk; }
189 // pointer is used to clone()
190 ValueToKey* get_key_func() { return my_key; }
191
193 pointer_type p = NULL;
194 __TBB_ASSERT(my_key, "Error: value-to-key functor not provided");
195 if(find_ref_with_key((*my_key)(v), p)) {
196 p->~value_type();
197 (void) new(p) value_type(v); // copy-construct into the space
198 return false;
199 }
200 ++nelements;
201 if(nelements*2 > my_size) grow_array();
203 return true;
204 }
205
206 // returns true and sets v to array element if found, else returns false.
208 size_t i = this->hash(k) & mask();
209 for(element_type* p = pointer_array[i]; p; p = (element_type *)(p->second)) {
210 pointer_type pv = reinterpret_cast<pointer_type>(&(p->first));
211 __TBB_ASSERT(my_key, "Error: value-to-key functor not provided");
212 if(this->equal((*my_key)(*pv), k)) {
213 v = pv;
214 return true;
215 }
216 }
217 return false;
218 }
219
220 bool find_with_key( const Knoref& k, value_type &v) {
221 value_type *p;
222 if(find_ref_with_key(k, p)) {
223 v = *p;
224 return true;
225 }
226 else
227 return false;
228 }
229
230 void delete_with_key(const Knoref& k) {
231 size_t h = this->hash(k) & mask();
232 element_type* prev = NULL;
233 for(element_type* p = pointer_array[h]; p; prev = p, p = (element_type *)(p->second)) {
234 value_type *vp = reinterpret_cast<value_type *>(&(p->first));
235 __TBB_ASSERT(my_key, "Error: value-to-key functor not provided");
236 if(this->equal((*my_key)(*vp), k)) {
237 vp->~value_type();
238 if(prev) prev->second = p->second;
239 else pointer_array[h] = (element_type *)(p->second);
240 p->second = free_list;
241 free_list = p;
242 --nelements;
243 return;
244 }
245 }
246 __TBB_ASSERT(false, "key not found for delete");
247 }
248};
249#endif // __TBB__flow_graph_hash_buffer_impl_H
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition tbb_stddef.h:165
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t new_size
void const char const char int ITT_FORMAT __itt_group_sync p
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function h
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
aligned_pair< ValueType, void * >::type type
static void internal_free_buffer(pointer_array_type &pa, list_array_type &el, size_t &sz, size_t &ne)
void delete_with_key(const Knoref &k)
buffer_element_type< value_type >::type element_type
bool find_with_key(const Knoref &k, value_type &v)
Allocator::template rebind< list_array_type >::other pointer_array_allocator_type
void internal_insert_with_key(element_type **p_pointer_array, size_t p_sz, list_array_type &p_free_list, const value_type &v)
tbb::internal::strip< Key >::type Knoref
bool find_ref_with_key(const Knoref &k, pointer_type &v)
pointer_array_type pointer_array
static const size_t INITIAL_SIZE
list_array_type * pointer_array_type
void set_up_free_list(element_type **p_free_list, list_array_type la, size_t sz)
bool insert_with_key(const value_type &v)
Allocator::template rebind< element_type >::other elements_array_allocator
void set_key_func(ValueToKey *vtk)
DoCleanup(pointer_array_type &pa, list_array_type &my_els, size_t sz)

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.