git.sesse.net Git - casparcg/blob - tbb/include/tbb/internal/_flow_graph_item_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 #ifndef __TBB_item_buffer_H
  30 #define __TBB_item_buffer_H
  31
  32     //! Expandable buffer of items.  The possible operations are push, pop,
  33     //* tests for empty and so forth.  No mutual exclusion is built in.
  34     template <typename T, typename A=cache_aligned_allocator<T> >
  35     class item_buffer {
  36     public:
  37         typedef T input_type;
  38         typedef T output_type;
  39     protected:
  40         typedef size_t size_type;
  41         typedef std::pair< T, bool > item_type;
  42         typedef typename A::template rebind<item_type>::other allocator_type;
  43
  44         item_type *my_array;
  45         size_type my_array_size;
  46         static const size_type initial_buffer_size = 4;
  47         size_type my_head;
  48         size_type my_tail;
  49
  50         bool buffer_empty() { return my_head == my_tail; }
  51
  52         item_type &item(size_type i) { return my_array[i & (my_array_size - 1) ]; } // may not be marked valid
  53
  54         bool item_valid(size_type i) { return item(i).second; }
  55
  56         void fetch_front(T &v) { __TBB_ASSERT(item_valid(my_head), "front not valid"); v = item(my_head).first; }
  57         void fetch_back(T &v) { __TBB_ASSERT(item_valid(my_tail-1), "back not valid"); v = item(my_tail-1).first; }
  58
  59         void invalidate(size_type i) { __TBB_ASSERT(item_valid(i), "Item not valid"); item(i).second = false; }
  60         void validate(size_type i) { __TBB_ASSERT(!item_valid(i), "Item already valid"); item(i).second = true; }
  61
  62         void invalidate_front() { invalidate(my_head); }
  63         void validate_front() { validate(my_head); }
  64         void invalidate_back() { invalidate(my_tail-1); }
  65
  66         size_type size() { return my_tail - my_head; }
  67         size_type capacity() { return my_array_size; }
  68         bool buffer_full() { return size() == capacity(); }
  69
  70         //! Grows the internal array.
  71         void grow_my_array( size_t minimum_size ) {
  72             size_type old_size = my_array_size;
  73             size_type new_size = old_size ? 2*old_size : initial_buffer_size;
  74             while( new_size<minimum_size )
  75                 new_size*=2;
  76
  77             item_type* new_array = allocator_type().allocate(new_size);
  78             item_type* old_array = my_array;
  79
  80             for( size_type i=0; i<new_size; ++i ) {
  81                 new (&(new_array[i].first)) input_type;
  82                 new_array[i].second = false;
  83             }
  84
  85             size_t t=my_head;
  86             for( size_type i=0; i<old_size; ++i, ++t )
  87                 new_array[t&(new_size-1)] = old_array[t&(old_size-1)];
  88             my_array = new_array;
  89             my_array_size = new_size;
  90             if( old_array ) {
  91                 for( size_type i=0; i<old_size; ++i, ++t )
  92                     old_array[i].first.~input_type();
  93                 allocator_type().deallocate(old_array,old_size);
  94             }
  95         }
  96
  97         bool push_back(T &v) {
  98             if(buffer_full()) {
  99                 grow_my_array(size() + 1);
 100             }
 101             item(my_tail) = std::make_pair( v, true );
 102             ++my_tail;
 103             return true;
 104         }
 105
 106         bool pop_back(T &v) {
 107             if (!item_valid(my_tail-1)) {
 108                 return false;
 109             }
 110             fetch_back(v);
 111             invalidate_back();
 112             --my_tail;
 113             return true;
 114         }
 115
 116         bool pop_front(T &v) {
 117             if(!item_valid(my_head)) {
 118                 return false;
 119             }
 120             fetch_front(v);
 121             invalidate_front();
 122             ++my_head;
 123             return true;
 124         }
 125
 126     public:
 127         //! Constructor
 128         item_buffer( ) : my_array(NULL), my_array_size(0),
 129             my_head(0), my_tail(0) {
 130             grow_my_array(initial_buffer_size);
 131         }
 132
 133         ~item_buffer() {
 134             if (my_array) {
 135                 for( size_type i=0; i<my_array_size; ++i ) {
 136                     my_array[i].first.~input_type();
 137                 }
 138                 allocator_type().deallocate(my_array,my_array_size);
 139             }
 140         }
 141
 142     };
 143
 144     //! item_buffer with reservable front-end.  NOTE: if reserving, do not
 145     //* complete operation with pop_front(); use consume_front().
 146     //* No synchronization built-in.
 147     template<typename T, typename A=cache_aligned_allocator<T> >
 148     class reservable_item_buffer : public item_buffer<T, A> {
 149     protected:
 150         using item_buffer<T, A>::buffer_empty;
 151         using item_buffer<T, A>::fetch_front;
 152         using item_buffer<T, A>::invalidate_front;
 153         using item_buffer<T, A>::validate_front;
 154         using item_buffer<T, A>::item_valid;
 155         using item_buffer<T, A>::my_head;
 156
 157     public:
 158         reservable_item_buffer() : item_buffer<T, A>(), my_reserved(false) {}
 159     protected:
 160
 161         bool reserve_front(T &v) {
 162             if(my_reserved || !item_valid(my_head)) return false;
 163             my_reserved = true;
 164             // reserving the head
 165             fetch_front(v);
 166             // invalidate the head, but don't commit until consume is called
 167             invalidate_front();
 168             return true;
 169         }
 170
 171         void consume_front() {
 172             __TBB_ASSERT(my_reserved, "Attempt to consume a non-reserved item");
 173             ++my_head;
 174             my_reserved = false;
 175         }
 176
 177         void release_front() {
 178             __TBB_ASSERT(my_reserved, "Attempt to release a non-reserved item");
 179             validate_front();
 180             my_reserved = false;
 181         }
 182
 183         bool my_reserved;
 184     };
 185
 186 #endif // __TBB_item_buffer_H