framework/delibs/decpp/deAppendList.hpp

   1 #ifndef _DEAPPENDLIST_HPP
   2 #define _DEAPPENDLIST_HPP
   3 /*-------------------------------------------------------------------------
   4  * drawElements C++ Base Library
   5  * -----------------------------
   6  *
   7  * Copyright 2015 The Android Open Source Project
   8  *
   9  * Licensed under the Apache License, Version 2.0 (the "License");
  10  * you may not use this file except in compliance with the License.
  11  * You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  *
  21  *//*!
  22  * \file
  23  * \brief Fast ordered append-only container
  24  *//*--------------------------------------------------------------------*/
  25
  26 #include "deDefs.hpp"
  27 #include "deAtomic.h"
  28 #include "deThread.h"
  29 #include "deMemory.h"
  30 #include "deInt32.h"
  31
  32 namespace de
  33 {
  34
  35 /*--------------------------------------------------------------------*//*!
  36  * \brief Fast ordered append-only container
  37  *
  38  * AppendList provides data structure for recording ordered list of elements
  39  * quickly, while still providing good sequential read access speed.
  40  * It is good for example logging.
  41  *
  42  * AppendList allocates memory in blocks of blockSize elements. Choosing
  43  * too small blockSize will affect performance.
  44  *
  45  * Elements can be appended from multiple threads simultaneously but if
  46  * current block runs out, allocation of next block will happen in a single
  47  * thread and block others from inserting further elements until completed.
  48  * For that reason shared AppendList should not be used if there is a lot
  49  * of contention and instead per-thread AppendList's are recommended.
  50  *//*--------------------------------------------------------------------*/
  51 template<typename ElementType>
  52 class AppendList
  53 {
  54 public:
  55                                                                 AppendList              (size_t blockSize);
  56                                                                 ~AppendList             (void);
  57
  58         void                                            append                  (const ElementType& value);
  59
  60         size_t                                          size                    (void) const { return m_numElements;    }
  61
  62 private:
  63                                                                 AppendList              (const AppendList<ElementType>&);
  64         AppendList<ElementType>&        operator=               (const AppendList<ElementType>&);
  65
  66         struct Block
  67         {
  68                 const size_t            blockNdx;
  69                 ElementType*            elements;
  70                 Block* volatile         next;
  71
  72                 Block (size_t blockNdx_, size_t size)
  73                         : blockNdx      (blockNdx_)
  74                         , elements      (reinterpret_cast<ElementType*>(deAlignedMalloc(sizeof(ElementType)*size,
  75                                                                                                                                                 deAlign32((deUint32)alignOf<ElementType>(), (deUint32)sizeof(void*)))))
  76                         , next          (DE_NULL)
  77                 {
  78                 }
  79
  80                 ~Block (void)
  81                 {
  82                         deAlignedFree(reinterpret_cast<void*>(elements));
  83                 }
  84         };
  85
  86         const size_t                            m_blockSize;
  87         volatile size_t                         m_numElements;
  88         Block*                                          m_first;
  89         Block* volatile                         m_last;
  90
  91 public:
  92         template<typename CompatibleType>
  93         class Iterator
  94         {
  95         public:
  96                                                                         Iterator                                                (Block* curBlock_, size_t blockSize_, size_t slotNdx_)
  97                                                                                                                                                 : m_curBlock    (curBlock_)
  98                                                                                                                                                 , m_blockSize   (blockSize_)
  99                                                                                                                                                 , m_slotNdx             (slotNdx_)
 100                 {}
 101
 102                 bool                                            operator!=                                              (const Iterator<CompatibleType>& other) const
 103                 {
 104                         return m_curBlock != other.m_curBlock || m_slotNdx != other.m_slotNdx;
 105                 }
 106                 bool                                            operator==                                              (const Iterator<CompatibleType>& other) const
 107                 {
 108                         return m_curBlock == other.m_curBlock && m_slotNdx == other.m_slotNdx;
 109                 }
 110
 111                 Iterator<CompatibleType>&       operator++                                              (void)
 112                 {
 113                         ++m_slotNdx;
 114
 115                         if (m_slotNdx == m_blockSize)
 116                         {
 117                                 m_slotNdx = 0;
 118                                 m_curBlock = m_curBlock->next;
 119                         }
 120
 121                         return *this;
 122                 }
 123
 124                 Iterator<CompatibleType>        operator++                                              (int) const
 125                 {
 126                         Iterator<CompatibleType> copy(*this);
 127                         return ++copy;
 128                 }
 129
 130                 CompatibleType&                         operator*                                               (void) const
 131                 {
 132                         return m_curBlock->elements[m_slotNdx];
 133                 }
 134
 135                 operator                                        Iterator<const CompatibleType>  (void) const
 136                 {
 137                         return Iterator<const CompatibleType>(m_curBlock, m_blockSize, m_slotNdx);
 138                 }
 139
 140         private:
 141                 Block*                  m_curBlock;
 142                 size_t                  m_blockSize;
 143                 size_t                  m_slotNdx;
 144         };
 145
 146         typedef Iterator<const ElementType>     const_iterator;
 147         typedef Iterator<ElementType>           iterator;
 148
 149         const_iterator                          begin                   (void) const;
 150         iterator                                        begin                   (void);
 151
 152         const_iterator                          end                             (void) const;
 153         iterator                                        end                             (void);
 154 };
 155
 156 template<typename ElementType>
 157 AppendList<ElementType>::AppendList (size_t blockSize)
 158         : m_blockSize   (blockSize)
 159         , m_numElements (0)
 160         , m_first               (new Block(0, blockSize))
 161         , m_last                (m_first)
 162 {
 163 }
 164
 165 template<typename ElementType>
 166 AppendList<ElementType>::~AppendList (void)
 167 {
 168         size_t  elementNdx      = 0;
 169         Block*  curBlock        = m_first;
 170
 171         while (curBlock)
 172         {
 173                 Block* const    delBlock        = curBlock;
 174
 175                 curBlock = delBlock->next;
 176
 177                 // Call destructor for allocated elements
 178                 for (; elementNdx < min(m_numElements, delBlock->blockNdx*m_blockSize); ++elementNdx)
 179                         delBlock->elements[elementNdx%m_blockSize].~ElementType();
 180
 181                 delete delBlock;
 182         }
 183 }
 184
 185 template<typename ElementType>
 186 void AppendList<ElementType>::append (const ElementType& value)
 187 {
 188         // Fetch curBlock first before allocating slot. Otherwise m_last might get updated before
 189         // this thread gets chance of reading it, leading to curBlock->blockNdx > blockNdx.
 190         Block*                  curBlock        = m_last;
 191
 192         deMemoryReadWriteFence();
 193
 194         {
 195                 const size_t    elementNdx      = deAtomicIncrementUSize(&m_numElements) - 1;
 196                 const size_t    blockNdx        = elementNdx / m_blockSize;
 197                 const size_t    slotNdx         = elementNdx - (blockNdx * m_blockSize);
 198
 199                 while (curBlock->blockNdx != blockNdx)
 200                 {
 201                         if (curBlock->next)
 202                                 curBlock = curBlock->next;
 203                         else
 204                         {
 205                                 // Other thread(s) are currently allocating additional block(s)
 206                                 deYield();
 207                         }
 208                 }
 209
 210                 // Did we allocate last slot? If so, add a new block
 211                 if (slotNdx+1 == m_blockSize)
 212                 {
 213                         Block* const    newBlock        = new Block(blockNdx+1, m_blockSize);
 214
 215                         deMemoryReadWriteFence();
 216
 217                         // At this point if any other thread is trying to allocate more blocks
 218                         // they are being blocked by curBlock->next being null. This guarantees
 219                         // that this thread has exclusive modify access to m_last.
 220                         m_last = newBlock;
 221                         deMemoryReadWriteFence();
 222
 223                         // At this point other threads might have skipped to newBlock, but we
 224                         // still have exclusive modify access to curBlock->next.
 225                         curBlock->next = newBlock;
 226                         deMemoryReadWriteFence();
 227                 }
 228
 229                 new (&curBlock->elements[slotNdx]) ElementType(value);
 230         }
 231 }
 232
 233 template<typename ElementType>
 234 typename AppendList<ElementType>::const_iterator AppendList<ElementType>::begin (void) const
 235 {
 236         return const_iterator(m_first, m_blockSize, 0);
 237 }
 238
 239 template<typename ElementType>
 240 typename AppendList<ElementType>::iterator AppendList<ElementType>::begin (void)
 241 {
 242         return iterator(m_first, m_blockSize, 0);
 243 }
 244
 245 template<typename ElementType>
 246 typename AppendList<ElementType>::const_iterator AppendList<ElementType>::end (void) const
 247 {
 248         return const_iterator(m_last, m_blockSize, m_numElements%m_blockSize);
 249 }
 250
 251 template<typename ElementType>
 252 typename AppendList<ElementType>::iterator AppendList<ElementType>::end (void)
 253 {
 254         return iterator(m_last, m_blockSize, m_numElements%m_blockSize);
 255 }
 256
 257 void    AppendList_selfTest             (void);
 258
 259 } // de
 260
 261 #endif // _DEAPPENDLIST_HPP