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

   1 /*
   2     Copyright 2005-2011 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   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.
   9
  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.
  14
  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
  18
  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.
  27 */
  28
  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.
  32 //
  33
  34 #ifndef __TBB__flow_graph_tagged_buffer_impl_H
  35 #define __TBB__flow_graph_tagged_buffer_impl_H
  36
  37 #ifndef __TBB_flow_graph_H
  38 #error Do not #include this internal file directly; use public TBB headers instead.
  39 #endif
  40
  41 template<typename TagType, typename ValueType, size_t NoTagMark>
  42 struct buffer_element {
  43     TagType t;
  44     ValueType v;
  45     buffer_element *next;
  46     buffer_element() : t(NoTagMark), next(NULL) {}
  47 };
  48
  49 template
  50     <
  51      typename TagType,
  52      typename ValueType,
  53      size_t   NoTagMark = 0,
  54      typename Allocator=tbb::cache_aligned_allocator< buffer_element<TagType,ValueType,NoTagMark> >
  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 buffer_element<TagType,ValueType, NO_TAG> element_type;
  62     typedef value_type *pointer_type;
  63     typedef std::vector<element_type, Allocator> list_array_type;
  64     typedef typename Allocator::template rebind<element_type*>::other pointer_array_allocator_type;
  65     typedef typename Allocator::template rebind<list_array_type>::other list_array_allocator;
  66 private:
  67
  68     size_t my_size;
  69     size_t nelements;
  70     element_type** array;
  71     std::vector<element_type, Allocator> *lists;
  72     element_type* free_list;
  73
  74     size_t mask() { return my_size - 1; }
  75
  76 // #define ABYSMAL 1
  77     static size_t hash(TagType t) {
  78 #if ABYSMAL
  79         return (size_t)1;
  80 #else
  81 #if __TBB_WORDSIZE == 4
  82         return uintptr_t(t)*0x9E3779B9;
  83 #else
  84         return uintptr_t(t)*0x9E3779B97F4A7C15;
  85 #endif
  86 #endif
  87     }
  88
  89     void set_up_free_list( element_type **p_free_list, list_array_type *la, size_t sz) {
  90         for(size_t i=0; i < sz - 1; ++i ) {  // construct free list
  91             (*la)[i].next = &((*la)[i+1]);
  92             (*la)[i].t = NO_TAG;
  93         }
  94         (*la)[sz-1].next = NULL;
  95         *p_free_list = &((*la)[0]);
  96     }
  97
  98     void grow_array() {
  99         // make the pointer array larger
 100         element_type **new_array;
 101         element_type **old_array = array;
 102         size_t old_size = my_size;
 103         my_size *=2;
 104         new_array = pointer_array_allocator_type().allocate(my_size);
 105         for(size_t i=0; i < my_size; ++i) new_array[i] = NULL;
 106         list_array_type *new_list_array = new list_array_type(old_size, element_type(), Allocator());
 107         set_up_free_list(&free_list, new_list_array, old_size );
 108
 109         for(size_t i=0; i < old_size; ++i) {
 110             for( element_type* op = old_array[i]; op; op = op->next) {
 111                 internal_tagged_insert(new_array, my_size, op->t, op->v);
 112             }
 113         }
 114         pointer_array_allocator_type().deallocate(old_array, old_size);
 115
 116         delete lists;  // destroy and deallocate instead
 117         array = new_array;
 118         lists = new_list_array;
 119     }
 120
 121     void internal_tagged_insert( element_type **ar, size_t sz, TagType t, value_type v) {
 122         size_t l_mask = sz-1;
 123         size_t h = hash(t) & l_mask;
 124         __TBB_ASSERT(free_list, "Error: free list not set up.");
 125         element_type* my_elem = free_list; free_list = free_list->next;
 126         my_elem->t = t;
 127         my_elem->v = v;
 128         my_elem->next = ar[h];
 129         ar[h] = my_elem;
 130     }
 131
 132 public:
 133     tagged_buffer() : my_size(INITIAL_SIZE), nelements(0) {
 134         array = pointer_array_allocator_type().allocate(my_size);
 135         for(size_t i = 0; i < my_size; ++i) array[i] = NULL;
 136         lists = new list_array_type(INITIAL_SIZE/2, element_type(), Allocator());
 137         set_up_free_list(&free_list, lists, INITIAL_SIZE/2);
 138     }
 139
 140     ~tagged_buffer() {
 141         if(array) {
 142             pointer_array_allocator_type().deallocate(array, my_size);
 143         }
 144         if(lists) {
 145             delete lists;
 146         }
 147     }
 148
 149     bool tagged_insert(TagType t, value_type v) {
 150         pointer_type p;
 151         if(tagged_find_ref(t, p)) {
 152             *p = v;  // replace the value
 153             return false;
 154         }
 155         ++nelements;
 156         if(nelements*2 > my_size) grow_array();
 157         internal_tagged_insert(array, my_size, t, v);
 158         return true;
 159     }
 160
 161     // returns reference to array element.v
 162     bool tagged_find_ref(TagType t, pointer_type &v) {
 163         size_t i = hash(t) & mask();
 164         for(element_type* p = array[i]; p; p = p->next) {
 165             if(p->t == t) {
 166                 v = &(p->v);
 167                 return true;
 168             }
 169         }
 170         return false;
 171     }
 172
 173     bool tagged_find( TagType t, value_type &v) {
 174         value_type *p;
 175         if(tagged_find_ref(t, p)) {
 176             v = *p;
 177             return true;
 178         }
 179         else
 180             return false;
 181     }
 182
 183     void tagged_delete(TagType t) {
 184         size_t h = hash(t) & mask();
 185         element_type* prev = NULL;
 186         for(element_type* p = array[h]; p; prev = p, p = p->next) {
 187             if(p->t == t) {
 188                 p->t = NO_TAG;
 189                 if(prev) prev->next = p->next;
 190                 else array[h] = p->next;
 191                 p->next = free_list;
 192                 free_list = p;
 193                 --nelements;
 194                 return;
 195             }
 196         }
 197         __TBB_ASSERT(false, "tag not found for delete");
 198     }
 199
 200     // search for v in the array; if found {set t, return true} else return false
 201     // we use this in join_node_FE to find if a tag's items are all available.
 202     bool find_value_tag( TagType &t, value_type v) {
 203         for(size_t i= 0; i < my_size / 2; ++i) {  // remember the vector is half the size of the hash array
 204             if( (*lists)[i].t != NO_TAG && (*lists)[i].v == v) {
 205                 t = (*lists)[i].t;
 206                 return true;
 207             }
 208         }
 209         return false;
 210     }
 211 };
 212 #endif // __TBB__flow_graph_tagged_buffer_impl_H