Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
_flow_graph_tagged_buffer_impl.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 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 
18 
19 */
20 
21 // a hash table buffer that can expand, and can support as many deletions as
22 // additions, list-based, with elements of list held in array (for destruction
23 // management), multiplicative hashing (like ets). No synchronization built-in.
24 //
25 
26 #ifndef __TBB__flow_graph_hash_buffer_impl_H
27 #define __TBB__flow_graph_hash_buffer_impl_H
28 
29 #ifndef __TBB_flow_graph_H
30 #error Do not #include this internal file directly; use public TBB headers instead.
31 #endif
32 
33 // included in namespace tbb::flow::interfaceX::internal
34 
35 // elements in the table are a simple list; we need pointer to next element to
36 // traverse the chain
37 template<typename ValueType>
39  // the second parameter below is void * because we can't forward-declare the type
40  // itself, so we just reinterpret_cast below.
42 };
43 
44 template
45  <
46  typename Key, // type of key within ValueType
47  typename ValueType,
48  typename ValueToKey, // abstract method that returns "const Key" or "const Key&" given ValueType
49  typename HashCompare, // has hash and equal
51  >
52 class hash_buffer : public HashCompare {
53 public:
54  static const size_t INITIAL_SIZE = 8; // initial size of the hash pointer table
55  typedef ValueType value_type;
58  typedef element_type *list_array_type; // array we manage manually
60  typedef typename Allocator::template rebind<list_array_type>::other pointer_array_allocator_type;
61  typedef typename Allocator::template rebind<element_type>::other elements_array_allocator;
63 
64 private:
65  ValueToKey *my_key;
66  size_t my_size;
67  size_t nelements;
68  pointer_array_type pointer_array; // pointer_array[my_size]
69  list_array_type elements_array; // elements_array[my_size / 2]
71 
72  size_t mask() { return my_size - 1; }
73 
74  void set_up_free_list( element_type **p_free_list, list_array_type la, size_t sz) {
75  for(size_t i=0; i < sz - 1; ++i ) { // construct free list
76  la[i].second = &(la[i+1]);
77  }
78  la[sz-1].second = NULL;
79  *p_free_list = (element_type *)&(la[0]);
80  }
81 
82  // cleanup for exceptions
83  struct DoCleanup {
86  size_t my_size;
87 
88  DoCleanup(pointer_array_type &pa, list_array_type &my_els, size_t sz) :
89  my_pa(&pa), my_elements(&my_els), my_size(sz) { }
91  if(my_pa) {
92  size_t dont_care = 0;
94  }
95  }
96  };
97 
98  // exception-safety requires we do all the potentially-throwing operations first
99  void grow_array() {
100  size_t new_size = my_size*2;
101  size_t new_nelements = nelements; // internal_free_buffer zeroes this
102  list_array_type new_elements_array = NULL;
103  pointer_array_type new_pointer_array = NULL;
104  list_array_type new_free_list = NULL;
105  {
106  DoCleanup my_cleanup(new_pointer_array, new_elements_array, new_size);
107  new_elements_array = elements_array_allocator().allocate(my_size);
108  new_pointer_array = pointer_array_allocator_type().allocate(new_size);
109  for(size_t i=0; i < new_size; ++i) new_pointer_array[i] = NULL;
110  set_up_free_list(&new_free_list, new_elements_array, my_size );
111 
112  for(size_t i=0; i < my_size; ++i) {
113  for( element_type* op = pointer_array[i]; op; op = (element_type *)(op->second)) {
114  value_type *ov = reinterpret_cast<value_type *>(&(op->first));
115  // could have std::move semantics
116  internal_insert_with_key(new_pointer_array, new_size, new_free_list, *ov);
117  }
118  }
119  my_cleanup.my_pa = NULL;
120  my_cleanup.my_elements = NULL;
121  }
122 
124  free_list = new_free_list;
125  pointer_array = new_pointer_array;
126  elements_array = new_elements_array;
127  my_size = new_size;
128  nelements = new_nelements;
129  }
130 
131  // v should have perfect forwarding if std::move implemented.
132  // we use this method to move elements in grow_array, so can't use class fields
133  void internal_insert_with_key( element_type **p_pointer_array, size_t p_sz, list_array_type &p_free_list,
134  const value_type &v) {
135  size_t l_mask = p_sz-1;
136  __TBB_ASSERT(my_key, "Error: value-to-key functor not provided");
137  size_t h = this->hash((*my_key)(v)) & l_mask;
138  __TBB_ASSERT(p_free_list, "Error: free list not set up.");
139  element_type* my_elem = p_free_list; p_free_list = (element_type *)(p_free_list->second);
140  (void) new(&(my_elem->first)) value_type(v);
141  my_elem->second = p_pointer_array[h];
142  p_pointer_array[h] = my_elem;
143  }
144 
147  for(size_t i = 0; i < my_size; ++i) pointer_array[i] = NULL;
150  }
151 
152  // made static so an enclosed class can use to properly dispose of the internals
153  static void internal_free_buffer( pointer_array_type &pa, list_array_type &el, size_t &sz, size_t &ne ) {
154  if(pa) {
155  for(size_t i = 0; i < sz; ++i ) {
156  element_type *p_next;
157  for( element_type *p = pa[i]; p; p = p_next) {
158  p_next = (element_type *)p->second;
159  internal::punned_cast<value_type *>(&(p->first))->~value_type();
160  }
161  }
162  pointer_array_allocator_type().deallocate(pa, sz);
163  pa = NULL;
164  }
165  // Separate test (if allocation of pa throws, el may be allocated.
166  // but no elements will be constructed.)
167  if(el) {
168  elements_array_allocator().deallocate(el, sz / 2);
169  el = NULL;
170  }
171  sz = INITIAL_SIZE;
172  ne = 0;
173  }
174 
175 public:
178  }
179 
182  if(my_key) delete my_key;
183  }
184 
185  void reset() {
188  }
189 
190  // Take ownership of func object allocated with new.
191  // This method is only used internally, so can't be misused by user.
192  void set_key_func(ValueToKey *vtk) { my_key = vtk; }
193  // pointer is used to clone()
194  ValueToKey* get_key_func() { return my_key; }
195 
196  bool insert_with_key(const value_type &v) {
197  pointer_type p = NULL;
198  __TBB_ASSERT(my_key, "Error: value-to-key functor not provided");
199  if(find_ref_with_key((*my_key)(v), p)) {
200  p->~value_type();
201  (void) new(p) value_type(v); // copy-construct into the space
202  return false;
203  }
204  ++nelements;
205  if(nelements*2 > my_size) grow_array();
207  return true;
208  }
209 
210  // returns true and sets v to array element if found, else returns false.
211  bool find_ref_with_key(const Knoref& k, pointer_type &v) {
212  size_t i = this->hash(k) & mask();
213  for(element_type* p = pointer_array[i]; p; p = (element_type *)(p->second)) {
214  pointer_type pv = reinterpret_cast<pointer_type>(&(p->first));
215  __TBB_ASSERT(my_key, "Error: value-to-key functor not provided");
216  if(this->equal((*my_key)(*pv), k)) {
217  v = pv;
218  return true;
219  }
220  }
221  return false;
222  }
223 
224  bool find_with_key( const Knoref& k, value_type &v) {
225  value_type *p;
226  if(find_ref_with_key(k, p)) {
227  v = *p;
228  return true;
229  }
230  else
231  return false;
232  }
233 
234  void delete_with_key(const Knoref& k) {
235  size_t h = this->hash(k) & mask();
236  element_type* prev = NULL;
237  for(element_type* p = pointer_array[h]; p; prev = p, p = (element_type *)(p->second)) {
238  value_type *vp = reinterpret_cast<value_type *>(&(p->first));
239  __TBB_ASSERT(my_key, "Error: value-to-key functor not provided");
240  if(this->equal((*my_key)(*vp), k)) {
241  vp->~value_type();
242  if(prev) prev->second = p->second;
243  else pointer_array[h] = (element_type *)(p->second);
244  p->second = free_list;
245  free_list = p;
246  --nelements;
247  return;
248  }
249  }
250  __TBB_ASSERT(false, "key not found for delete");
251  }
252 };
253 #endif // __TBB__flow_graph_hash_buffer_impl_H
pointer_array_type pointer_array
bool insert_with_key(const value_type &v)
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.
tbb::internal::strip< Key >::type Knoref
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
Allocator::template rebind< list_array_type >::other pointer_array_allocator_type
void delete_with_key(const Knoref &k)
void set_key_func(ValueToKey *vtk)
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 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 int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
bool find_ref_with_key(const Knoref &k, pointer_type &v)
static const size_t INITIAL_SIZE
void const char const char int ITT_FORMAT __itt_group_sync p
static void internal_free_buffer(pointer_array_type &pa, list_array_type &el, size_t &sz, size_t &ne)
DoCleanup(pointer_array_type &pa, list_array_type &my_els, size_t sz)
aligned_pair< ValueType, void * >::type 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)
void set_up_free_list(element_type **p_free_list, list_array_type la, size_t sz)
list_array_type * pointer_array_type
list_array_type elements_array
buffer_element_type< value_type >::type element_type
Allocator::template rebind< element_type >::other elements_array_allocator
element_type * list_array_type
bool find_with_key(const Knoref &k, value_type &v)

Copyright © 2005-2019 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.