Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
Loading...
Searching...
No Matches
hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator > Class Template Reference

#include <_flow_graph_tagged_buffer_impl.h>

Inheritance diagram for hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >:
Collaboration diagram for hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >:

Classes

struct  DoCleanup
 

Public Types

typedef ValueType value_type
 
typedef buffer_element_type< value_type >::type element_type
 
typedef value_typepointer_type
 
typedef element_typelist_array_type
 
typedef list_array_typepointer_array_type
 
typedef Allocator::template rebind< list_array_type >::other pointer_array_allocator_type
 
typedef Allocator::template rebind< element_type >::other elements_array_allocator
 
typedef tbb::internal::strip< Key >::type Knoref
 

Public Member Functions

 hash_buffer ()
 
 ~hash_buffer ()
 
void reset ()
 
void set_key_func (ValueToKey *vtk)
 
ValueToKey * get_key_func ()
 
bool insert_with_key (const value_type &v)
 
bool find_ref_with_key (const Knoref &k, pointer_type &v)
 
bool find_with_key (const Knoref &k, value_type &v)
 
void delete_with_key (const Knoref &k)
 

Static Public Attributes

static const size_t INITIAL_SIZE = 8
 

Private Member Functions

size_t mask ()
 
void set_up_free_list (element_type **p_free_list, list_array_type la, size_t sz)
 
void grow_array ()
 
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 internal_initialize_buffer ()
 

Static Private Member Functions

static void internal_free_buffer (pointer_array_type &pa, list_array_type &el, size_t &sz, size_t &ne)
 

Private Attributes

ValueToKey * my_key
 
size_t my_size
 
size_t nelements
 
pointer_array_type pointer_array
 
list_array_type elements_array
 
element_typefree_list
 

Detailed Description

template<typename Key, typename ValueType, typename ValueToKey, typename HashCompare, typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
class hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >

Definition at line 48 of file _flow_graph_tagged_buffer_impl.h.

Member Typedef Documentation

◆ element_type

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef buffer_element_type<value_type>::type hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::element_type

Definition at line 52 of file _flow_graph_tagged_buffer_impl.h.

◆ elements_array_allocator

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef Allocator::template rebind<element_type>::other hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::elements_array_allocator

Definition at line 57 of file _flow_graph_tagged_buffer_impl.h.

◆ Knoref

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef tbb::internal::strip<Key>::type hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::Knoref

Definition at line 58 of file _flow_graph_tagged_buffer_impl.h.

◆ list_array_type

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef element_type* hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::list_array_type

Definition at line 54 of file _flow_graph_tagged_buffer_impl.h.

◆ pointer_array_allocator_type

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef Allocator::template rebind<list_array_type>::other hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::pointer_array_allocator_type

Definition at line 56 of file _flow_graph_tagged_buffer_impl.h.

◆ pointer_array_type

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef list_array_type* hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::pointer_array_type

Definition at line 55 of file _flow_graph_tagged_buffer_impl.h.

◆ pointer_type

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef value_type* hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::pointer_type

Definition at line 53 of file _flow_graph_tagged_buffer_impl.h.

◆ value_type

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
typedef ValueType hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::value_type

Definition at line 51 of file _flow_graph_tagged_buffer_impl.h.

Constructor & Destructor Documentation

◆ hash_buffer()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::hash_buffer ( )
inline

Definition at line 172 of file _flow_graph_tagged_buffer_impl.h.

References hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::internal_initialize_buffer().

Here is the call graph for this function:

◆ ~hash_buffer()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::~hash_buffer ( )
inline

Member Function Documentation

◆ delete_with_key()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::delete_with_key ( const Knoref k)
inline

Definition at line 230 of file _flow_graph_tagged_buffer_impl.h.

230 {
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 }
#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 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
buffer_element_type< value_type >::type element_type

References __TBB_ASSERT, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::free_list, h, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::mask(), hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::my_key, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::nelements, p, and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::pointer_array.

Here is the call graph for this function:

◆ find_ref_with_key()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
bool hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::find_ref_with_key ( const Knoref k,
pointer_type v 
)
inline

Definition at line 207 of file _flow_graph_tagged_buffer_impl.h.

207 {
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 }

References __TBB_ASSERT, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::mask(), hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::my_key, p, and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::pointer_array.

Referenced by hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::find_with_key(), and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::insert_with_key().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ find_with_key()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
bool hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::find_with_key ( const Knoref k,
value_type v 
)
inline

Definition at line 220 of file _flow_graph_tagged_buffer_impl.h.

220 {
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 }
bool find_ref_with_key(const Knoref &k, pointer_type &v)

References hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::find_ref_with_key(), and p.

Here is the call graph for this function:

◆ get_key_func()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
ValueToKey * hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::get_key_func ( )
inline

◆ grow_array()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::grow_array ( )
inlineprivate

Definition at line 95 of file _flow_graph_tagged_buffer_impl.h.

95 {
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 }
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
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)
list_array_type * pointer_array_type
void set_up_free_list(element_type **p_free_list, list_array_type la, size_t sz)
element_type * list_array_type
Allocator::template rebind< element_type >::other elements_array_allocator

References hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::elements_array, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::free_list, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::internal_free_buffer(), hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::internal_insert_with_key(), hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::DoCleanup::my_elements, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::DoCleanup::my_pa, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::my_size, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::nelements, new_size, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::pointer_array, and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::set_up_free_list().

Referenced by hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::insert_with_key().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert_with_key()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
bool hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::insert_with_key ( const value_type v)
inline

◆ internal_free_buffer()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
static void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::internal_free_buffer ( pointer_array_type pa,
list_array_type el,
size_t &  sz,
size_t &  ne 
)
inlinestaticprivate

Definition at line 149 of file _flow_graph_tagged_buffer_impl.h.

149 {
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 }

References hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::INITIAL_SIZE, and p.

Referenced by hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::grow_array(), hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::reset(), hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::DoCleanup::~DoCleanup(), and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::~hash_buffer().

Here is the caller graph for this function:

◆ internal_initialize_buffer()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::internal_initialize_buffer ( )
inlineprivate

◆ internal_insert_with_key()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::internal_insert_with_key ( element_type **  p_pointer_array,
size_t  p_sz,
list_array_type p_free_list,
const value_type v 
)
inlineprivate

Definition at line 129 of file _flow_graph_tagged_buffer_impl.h.

130 {
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 }

References __TBB_ASSERT, h, hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::my_key, and void.

Referenced by hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::grow_array(), and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::insert_with_key().

Here is the caller graph for this function:

◆ mask()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
size_t hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::mask ( )
inlineprivate

Definition at line 68 of file _flow_graph_tagged_buffer_impl.h.

68{ return my_size - 1; }

References hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::my_size.

Referenced by hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::delete_with_key(), and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::find_ref_with_key().

Here is the caller graph for this function:

◆ reset()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::reset ( )
inline

◆ set_key_func()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::set_key_func ( ValueToKey *  vtk)
inline

◆ set_up_free_list()

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
void hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::set_up_free_list ( element_type **  p_free_list,
list_array_type  la,
size_t  sz 
)
inlineprivate

Definition at line 70 of file _flow_graph_tagged_buffer_impl.h.

70 {
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 }

Referenced by hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::grow_array(), and hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::internal_initialize_buffer().

Here is the caller graph for this function:

Member Data Documentation

◆ elements_array

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
list_array_type hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::elements_array
private

◆ free_list

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
element_type* hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::free_list
private

◆ INITIAL_SIZE

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
const size_t hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::INITIAL_SIZE = 8
static

◆ my_key

◆ my_size

◆ nelements

template<typename Key , typename ValueType , typename ValueToKey , typename HashCompare , typename Allocator = tbb::cache_aligned_allocator< typename aligned_pair<ValueType, void *>::type >>
size_t hash_buffer< Key, ValueType, ValueToKey, HashCompare, Allocator >::nelements
private

◆ pointer_array


The documentation for this class was generated from the following file:

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.