2 Copyright 2005-2011 Intel Corporation. All Rights Reserved.
4 This file is part of Threading Building Blocks.
6 Threading Building Blocks is free software; you can redistribute it
7 and/or modify it under the terms of the GNU General Public License
8 version 2 as published by the Free Software Foundation.
10 Threading Building Blocks is distributed in the hope that it will be
11 useful, but WITHOUT ANY WARRANTY; without even the implied warranty
12 of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with Threading Building Blocks; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 As a special exception, you may use this file as part of a free software
20 library without restriction. Specifically, if other files instantiate
21 templates or use macros or inline functions from this file, or you compile
22 this file and link it with other files to produce an executable, this
23 file does not by itself cause the resulting executable to be covered by
24 the GNU General Public License. This exception does not however
25 invalidate any other reasons why the executable file might be covered by
26 the GNU General Public License.
29 // tagged buffer that can expand, and can support as many deletions as additions
30 // list-based, with elements of list held in std::vector (for destruction management),
31 // multiplicative hashing (like ets). No synchronization built-in.
34 template<typename TagType, typename ValueType, size_t NoTagMark>
35 struct buffer_element {
39 buffer_element() : t(NoTagMark), next(NULL) {}
47 typename Allocator=tbb::cache_aligned_allocator< buffer_element<TagType,ValueType,NoTagMark> >
51 static const size_t INITIAL_SIZE = 8; // initial size of the hash pointer table
52 static const TagType NO_TAG = TagType(NoTagMark);
53 typedef ValueType value_type;
54 typedef buffer_element<TagType,ValueType, NO_TAG> element_type;
55 typedef value_type *pointer_type;
56 typedef std::vector<element_type, Allocator> list_array_type;
57 typedef typename Allocator::template rebind<element_type*>::other pointer_array_allocator_type;
58 typedef typename Allocator::template rebind<list_array_type>::other list_array_allocator;
64 std::vector<element_type, Allocator> *lists;
65 element_type* free_list;
67 size_t mask() { return my_size - 1; }
70 static size_t hash(TagType t) {
74 #if __TBB_WORDSIZE == 4
75 return uintptr_t(t)*0x9E3779B9;
77 return uintptr_t(t)*0x9E3779B97F4A7C15;
82 void set_up_free_list( element_type **p_free_list, list_array_type *la, size_t sz) {
83 for(size_t i=0; i < sz - 1; ++i ) { // construct free list
84 (*la)[i].next = &((*la)[i+1]);
87 (*la)[sz-1].next = NULL;
88 *p_free_list = &((*la)[0]);
92 // make the pointer array larger
93 element_type **new_array;
94 element_type **old_array = array;
95 size_t old_size = my_size;
97 new_array = pointer_array_allocator_type().allocate(my_size);
98 for(size_t i=0; i < my_size; ++i) new_array[i] = NULL;
99 list_array_type *new_list_array = new list_array_type(old_size, element_type(), Allocator());
100 set_up_free_list(&free_list, new_list_array, old_size );
102 for(size_t i=0; i < old_size; ++i) {
103 for( element_type* op = old_array[i]; op; op = op->next) {
104 internal_tagged_insert(new_array, my_size, op->t, op->v);
107 pointer_array_allocator_type().deallocate(old_array, old_size);
109 delete lists; // destroy and deallocate instead
111 lists = new_list_array;
114 void internal_tagged_insert( element_type **ar, size_t sz, TagType t, value_type v) {
115 size_t l_mask = sz-1;
116 size_t h = hash(t) & l_mask;
117 __TBB_ASSERT(free_list, "Error: free list not set up.");
118 element_type* my_elem = free_list; free_list = free_list->next;
121 my_elem->next = ar[h];
126 tagged_buffer() : my_size(INITIAL_SIZE), nelements(0) {
127 array = pointer_array_allocator_type().allocate(my_size);
128 for(size_t i = 0; i < my_size; ++i) array[i] = NULL;
129 lists = new list_array_type(INITIAL_SIZE/2, element_type(), Allocator());
130 set_up_free_list(&free_list, lists, INITIAL_SIZE/2);
135 pointer_array_allocator_type().deallocate(array, my_size);
142 bool tagged_insert(TagType t, value_type v) {
144 if(tagged_find_ref(t, p)) {
145 *p = v; // replace the value
149 if(nelements*2 > my_size) grow_array();
150 internal_tagged_insert(array, my_size, t, v);
154 // returns reference to array element.v
155 bool tagged_find_ref(TagType t, pointer_type &v) {
156 size_t i = hash(t) & mask();
157 for(element_type* p = array[i]; p; p = p->next) {
166 bool tagged_find( TagType t, value_type &v) {
168 if(tagged_find_ref(t, p)) {
176 void tagged_delete(TagType t) {
177 size_t h = hash(t) & mask();
178 element_type* prev = NULL;
179 for(element_type* p = array[h]; p; prev = p, p = p->next) {
182 if(prev) prev->next = p->next;
183 else array[h] = p->next;
190 __TBB_ASSERT(false, "tag not found for delete");
193 // search for v in the array; if found {set t, return true} else return false
194 // we use this in join_node_FE to find if a tag's items are all available.
195 bool find_value_tag( TagType &t, value_type v) {
196 for(size_t i= 0; i < my_size / 2; ++i) { // remember the vector is half the size of the hash array
197 if( (*lists)[i].t != NO_TAG && (*lists)[i].v == v) {