git.sesse.net Git - casparcg/blob - dependencies64/tbb/include/tbb/internal/_flow_graph_tagged_buffer_impl.h

   1 /*
   2     Copyright 2005-2014 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks. Threading Building Blocks is free software;
   5     you can redistribute it and/or modify it under the terms of the GNU General Public License
   6     version 2  as  published  by  the  Free Software Foundation.  Threading Building Blocks is
   7     distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
   8     implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   9     See  the GNU General Public License for more details.   You should have received a copy of
  10     the  GNU General Public License along with Threading Building Blocks; if not, write to the
  11     Free Software Foundation, Inc.,  51 Franklin St,  Fifth Floor,  Boston,  MA 02110-1301 USA
  12
  13     As a special exception,  you may use this file  as part of a free software library without
  14     restriction.  Specifically,  if other files instantiate templates  or use macros or inline
  15     functions from this file, or you compile this file and link it with other files to produce
  16     an executable,  this file does not by itself cause the resulting executable to be covered
  17     by the GNU General Public License. This exception does not however invalidate any other
  18     reasons why the executable file might be covered by the GNU General Public License.
  19 */
  20
  21 // tagged buffer that can expand, and can support as many deletions as additions
  22 // list-based, with elements of list held in array (for destruction management),
  23 // multiplicative hashing (like ets).  No synchronization built-in.
  24 //
  25
  26 #ifndef __TBB__flow_graph_tagged_buffer_impl_H
  27 #define __TBB__flow_graph_tagged_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::interface7::internal
  34
  35 template<typename T, typename U, size_t NoTagMark>
  36 struct otherData {
  37     T t;
  38     U next;
  39     otherData() : t(NoTagMark), next(NULL) {}
  40 };
  41
  42 template<typename TagType, typename ValueType, size_t NoTagMark>
  43 struct buffer_element_type {
  44     // the second parameter below is void * because we can't forward-declare the type
  45     // itself, so we just reinterpret_cast below.
  46     typedef typename aligned_pair<ValueType, otherData<TagType, void *, NoTagMark> >::type type;
  47 };
  48
  49 template
  50     <
  51      typename TagType,
  52      typename ValueType,
  53      size_t   NoTagMark = 0,
  54      typename Allocator=tbb::cache_aligned_allocator< typename buffer_element_type<TagType, ValueType, NoTagMark>::type >
  55     >
  56 class tagged_buffer {
  57 public:
  58     static const size_t INITIAL_SIZE = 8;  // initial size of the hash pointer table
  59     static const TagType NO_TAG = TagType(NoTagMark);
  60     typedef ValueType value_type;
  61     typedef typename buffer_element_type<TagType, ValueType, NO_TAG>::type element_type;
  62     typedef value_type *pointer_type;
  63     typedef element_type *list_array_type;  // array we manage manually
  64     typedef list_array_type *pointer_array_type;
  65     typedef typename Allocator::template rebind<list_array_type>::other pointer_array_allocator_type;
  66     typedef typename Allocator::template rebind<element_type>::other elements_array_allocator;
  67 private:
  68     size_t my_size;
  69     size_t nelements;
  70     pointer_array_type pointer_array;    // pointer_array[my_size]
  71     list_array_type elements_array;      // elements_array[my_size / 2]
  72     element_type* free_list;
  73
  74     size_t mask() { return my_size - 1; }
  75
  76     static size_t hash(TagType t) {
  77         return uintptr_t(t)*tbb::internal::select_size_t_constant<0x9E3779B9,0x9E3779B97F4A7C15ULL>::value;
  78     }
  79
  80     void set_up_free_list( element_type **p_free_list, list_array_type la, size_t sz) {
  81         for(size_t i=0; i < sz - 1; ++i ) {  // construct free list
  82             la[i].second.next = &(la[i+1]);
  83             la[i].second.t = NO_TAG;
  84         }
  85         la[sz-1].second.next = NULL;
  86         *p_free_list = &(la[0]);
  87     }
  88
  89     // cleanup for exceptions
  90     struct DoCleanup {
  91         pointer_array_type *my_pa;
  92         list_array_type *my_elements;
  93         size_t my_size;
  94
  95         DoCleanup(pointer_array_type &pa, list_array_type &my_els, size_t sz) :
  96             my_pa(&pa), my_elements(&my_els), my_size(sz) {  }
  97         ~DoCleanup() {
  98             if(my_pa) {
  99                 size_t dont_care = 0;
 100                 internal_free_buffer(*my_pa, *my_elements, my_size, dont_care);
 101             }
 102         }
 103     };
 104
 105     // exception-safety requires we do all the potentially-throwing operations first
 106     void grow_array() {
 107         size_t new_size = my_size*2;
 108         size_t new_nelements = nelements;  // internal_free_buffer zeroes this
 109         list_array_type new_elements_array = NULL;
 110         pointer_array_type new_pointer_array = NULL;
 111         list_array_type new_free_list = NULL;
 112         {
 113             DoCleanup my_cleanup(new_pointer_array, new_elements_array, new_size);
 114             new_elements_array = elements_array_allocator().allocate(my_size);
 115             new_pointer_array = pointer_array_allocator_type().allocate(new_size);
 116             for(size_t i=0; i < new_size; ++i) new_pointer_array[i] = NULL;
 117             set_up_free_list(&new_free_list, new_elements_array, my_size );
 118
 119             for(size_t i=0; i < my_size; ++i) {
 120                 for( element_type* op = pointer_array[i]; op; op = (element_type *)(op->second.next)) {
 121                     value_type *ov = reinterpret_cast<value_type *>(&(op->first));
 122                     // could have std::move semantics
 123                     internal_tagged_insert(new_pointer_array, new_size, new_free_list, op->second.t, *ov);
 124                 }
 125             }
 126             my_cleanup.my_pa = NULL;
 127             my_cleanup.my_elements = NULL;
 128         }
 129
 130         internal_free_buffer(pointer_array, elements_array, my_size, nelements);
 131         free_list = new_free_list;
 132         pointer_array = new_pointer_array;
 133         elements_array = new_elements_array;
 134         my_size = new_size;
 135         nelements = new_nelements;
 136     }
 137
 138     // v should have perfect forwarding if std::move implemented.
 139     // we use this method to move elements in grow_array, so can't use class fields
 140     void internal_tagged_insert( element_type **p_pointer_array, size_t p_sz, list_array_type &p_free_list,
 141             const TagType t, const value_type &v) {
 142         size_t l_mask = p_sz-1;
 143         size_t h = hash(t) & l_mask;
 144         __TBB_ASSERT(p_free_list, "Error: free list not set up.");
 145         element_type* my_elem = p_free_list; p_free_list = (element_type *)(p_free_list->second.next);
 146         my_elem->second.t = t;
 147         (void) new(&(my_elem->first)) value_type(v);
 148         my_elem->second.next = p_pointer_array[h];
 149         p_pointer_array[h] = my_elem;
 150     }
 151
 152     void internal_initialize_buffer() {
 153         pointer_array = pointer_array_allocator_type().allocate(my_size);
 154         for(size_t i = 0; i < my_size; ++i) pointer_array[i] = NULL;
 155         elements_array = elements_array_allocator().allocate(my_size / 2);
 156         set_up_free_list(&free_list, elements_array, my_size / 2);
 157     }
 158
 159     // made static so an enclosed class can use to properly dispose of the internals
 160     static void internal_free_buffer( pointer_array_type &pa, list_array_type &el, size_t &sz, size_t &ne ) {
 161         if(pa) {
 162             for(size_t i = 0; i < sz; ++i ) {
 163                 element_type *p_next;
 164                 for( element_type *p = pa[i]; p; p = p_next) {
 165                     p_next = (element_type *)p->second.next;
 166                     value_type *vp = reinterpret_cast<value_type *>(&(p->first));
 167                     vp->~value_type();
 168                 }
 169             }
 170             pointer_array_allocator_type().deallocate(pa, sz);
 171             pa = NULL;
 172         }
 173         // Separate test (if allocation of pa throws, el may be allocated.
 174         // but no elements will be constructed.)
 175         if(el) {
 176             elements_array_allocator().deallocate(el, sz / 2);
 177             el = NULL;
 178         }
 179         sz = INITIAL_SIZE;
 180         ne = 0;
 181     }
 182
 183 public:
 184     tagged_buffer() : my_size(INITIAL_SIZE), nelements(0) {
 185         internal_initialize_buffer();
 186     }
 187
 188     ~tagged_buffer() {
 189         internal_free_buffer(pointer_array, elements_array, my_size, nelements);
 190     }
 191
 192     void reset() {
 193         internal_free_buffer(pointer_array, elements_array, my_size, nelements);
 194         internal_initialize_buffer();
 195     }
 196
 197     bool tagged_insert(const TagType t, const value_type &v) {
 198         pointer_type p;
 199         if(tagged_find_ref(t, 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();
 206         internal_tagged_insert(pointer_array, my_size, free_list, t, v);
 207         return true;
 208     }
 209
 210     // returns reference to array element.v
 211     bool tagged_find_ref(const TagType t, pointer_type &v) {
 212         size_t i = hash(t) & mask();
 213         for(element_type* p = pointer_array[i]; p; p = (element_type *)(p->second.next)) {
 214             if(p->second.t == t) {
 215                 v = reinterpret_cast<pointer_type>(&(p->first));
 216                 return true;
 217             }
 218         }
 219         return false;
 220     }
 221
 222     bool tagged_find( const TagType t, value_type &v) {
 223         value_type *p;
 224         if(tagged_find_ref(t, p)) {
 225             v = *p;
 226             return true;
 227         }
 228         else
 229             return false;
 230     }
 231
 232     void tagged_delete(const TagType t) {
 233         size_t h = hash(t) & mask();
 234         element_type* prev = NULL;
 235         for(element_type* p = pointer_array[h]; p; prev = p, p = (element_type *)(p->second.next)) {
 236             if(p->second.t == t) {
 237                 value_type *vp = reinterpret_cast<value_type *>(&(p->first));
 238                 vp->~value_type();
 239                 p->second.t = NO_TAG;
 240                 if(prev) prev->second.next = p->second.next;
 241                 else pointer_array[h] = (element_type *)(p->second.next);
 242                 p->second.next = free_list;
 243                 free_list = p;
 244                 --nelements;
 245                 return;
 246             }
 247         }
 248         __TBB_ASSERT(false, "tag not found for delete");
 249     }
 250 };
 251 #endif // __TBB__flow_graph_tagged_buffer_impl_H