git.sesse.net Git - casparcg/blob - 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 template<typename TagType, typename ValueType, size_t NoTagMark>
  35 struct buffer_element {
  36     TagType t;
  37     ValueType v;
  38     buffer_element *next;
  39     buffer_element() : t(NoTagMark), next(NULL) {}
  40 };
  41
  42 template
  43     <
  44      typename TagType,
  45      typename ValueType,
  46      size_t   NoTagMark = 0,
  47      typename Allocator=tbb::cache_aligned_allocator< buffer_element<TagType,ValueType,NoTagMark> >
  48     >
  49 class tagged_buffer {
  50 public:
  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;
  59 private:
  60
  61     size_t my_size;
  62     size_t nelements;
  63     element_type** array;
  64     std::vector<element_type, Allocator> *lists;
  65     element_type* free_list;
  66
  67     size_t mask() { return my_size - 1; }
  68
  69 // #define ABYSMAL 1
  70     static size_t hash(TagType t) {
  71 #if ABYSMAL
  72         return (size_t)1;
  73 #else
  74 #if __TBB_WORDSIZE == 4
  75         return uintptr_t(t)*0x9E3779B9;
  76 #else
  77         return uintptr_t(t)*0x9E3779B97F4A7C15;
  78 #endif
  79 #endif
  80     }
  81
  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]);
  85             (*la)[i].t = NO_TAG;
  86         }
  87         (*la)[sz-1].next = NULL;
  88         *p_free_list = &((*la)[0]);
  89     }
  90
  91     void grow_array() {
  92         // make the pointer array larger
  93         element_type **new_array;
  94         element_type **old_array = array;
  95         size_t old_size = my_size;
  96         my_size *=2;
  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 );
 101
 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);
 105             }
 106         }
 107         pointer_array_allocator_type().deallocate(old_array, old_size);
 108
 109         delete lists;  // destroy and deallocate instead
 110         array = new_array;
 111         lists = new_list_array;
 112     }
 113
 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;
 119         my_elem->t = t;
 120         my_elem->v = v;
 121         my_elem->next = ar[h];
 122         ar[h] = my_elem;
 123     }
 124
 125 public:
 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);
 131     }
 132
 133     ~tagged_buffer() {
 134         if(array) {
 135             pointer_array_allocator_type().deallocate(array, my_size);
 136         }
 137         if(lists) {
 138             delete lists;
 139         }
 140     }
 141
 142     bool tagged_insert(TagType t, value_type v) {
 143         pointer_type p;
 144         if(tagged_find_ref(t, p)) {
 145             *p = v;  // replace the value
 146             return false;
 147         }
 148         ++nelements;
 149         if(nelements*2 > my_size) grow_array();
 150         internal_tagged_insert(array, my_size, t, v);
 151         return true;
 152     }
 153
 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) {
 158             if(p->t == t) {
 159                 v = &(p->v);
 160                 return true;
 161             }
 162         }
 163         return false;
 164     }
 165
 166     bool tagged_find( TagType t, value_type &v) {
 167         value_type *p;
 168         if(tagged_find_ref(t, p)) {
 169             v = *p;
 170             return true;
 171         }
 172         else
 173             return false;
 174     }
 175
 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) {
 180             if(p->t == t) {
 181                 p->t = NO_TAG;
 182                 if(prev) prev->next = p->next;
 183                 else array[h] = p->next;
 184                 p->next = free_list;
 185                 free_list = p;
 186                 --nelements;
 187                 return;
 188             }
 189         }
 190         __TBB_ASSERT(false, "tag not found for delete");
 191     }
 192
 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) {
 198                 t = (*lists)[i].t;
 199                 return true;
 200             }
 201         }
 202         return false;
 203     }
 204 };