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         void                                            clear                   (void);
  63
  64 private:
  65                                                                 AppendList              (const AppendList<ElementType>&);
  66         AppendList<ElementType>&        operator=               (const AppendList<ElementType>&);
  67
  68         struct Block
  69         {
  70                 const size_t            blockNdx;
  71                 ElementType*            elements;
  72                 Block* volatile         next;
  73
  74                 Block (size_t blockNdx_, size_t size)
  75                         : blockNdx      (blockNdx_)
  76                         , elements      (reinterpret_cast<ElementType*>(deAlignedMalloc(sizeof(ElementType)*size,
  77                                                                                                                                                 deAlign32((deUint32)alignOf<ElementType>(), (deUint32)sizeof(void*)))))
  78                         , next          (DE_NULL)
  79                 {
  80                 }
  81
  82                 ~Block (void)
  83                 {
  84                         deAlignedFree(reinterpret_cast<void*>(elements));
  85                 }
  86         };
  87
  88         const size_t                            m_blockSize;
  89         volatile size_t                         m_numElements;
  90         Block*                                          m_first;
  91         Block* volatile                         m_last;
  92
  93 public:
  94         template<typename CompatibleType>
  95         class Iterator
  96         {
  97         public:
  98                                                                         Iterator                                                (Block* curBlock_, size_t blockSize_, size_t slotNdx_)
  99                                                                                                                                                 : m_curBlock    (curBlock_)
 100                                                                                                                                                 , m_blockSize   (blockSize_)
 101                                                                                                                                                 , m_slotNdx             (slotNdx_)
 102                 {}
 103
 104                 bool                                            operator!=                                              (const Iterator<CompatibleType>& other) const
 105                 {
 106                         return m_curBlock != other.m_curBlock || m_slotNdx != other.m_slotNdx;
 107                 }
 108                 bool                                            operator==                                              (const Iterator<CompatibleType>& other) const
 109                 {
 110                         return m_curBlock == other.m_curBlock && m_slotNdx == other.m_slotNdx;
 111                 }
 112
 113                 Iterator<CompatibleType>&       operator++                                              (void)
 114                 {
 115                         ++m_slotNdx;
 116
 117                         if (m_slotNdx == m_blockSize)
 118                         {
 119                                 m_slotNdx = 0;
 120                                 m_curBlock = m_curBlock->next;
 121                         }
 122
 123                         return *this;
 124                 }
 125
 126                 Iterator<CompatibleType>        operator++                                              (int) const
 127                 {
 128                         Iterator<CompatibleType> copy(*this);
 129                         return ++copy;
 130                 }
 131
 132                 CompatibleType&                         operator*                                               (void) const
 133                 {
 134                         return m_curBlock->elements[m_slotNdx];
 135                 }
 136
 137                 CompatibleType*                         operator->                                              (void) const
 138                 {
 139                         return &m_curBlock->elements[m_slotNdx];
 140                 }
 141
 142                 operator                                        Iterator<const CompatibleType>  (void) const
 143                 {
 144                         return Iterator<const CompatibleType>(m_curBlock, m_blockSize, m_slotNdx);
 145                 }
 146
 147         private:
 148                 Block*                  m_curBlock;
 149                 size_t                  m_blockSize;
 150                 size_t                  m_slotNdx;
 151         };
 152
 153         typedef Iterator<const ElementType>     const_iterator;
 154         typedef Iterator<ElementType>           iterator;
 155
 156         const_iterator                          begin                   (void) const;
 157         iterator                                        begin                   (void);
 158
 159         const_iterator                          end                             (void) const;
 160         iterator                                        end                             (void);
 161 };
 162
 163 template<typename ElementType>
 164 AppendList<ElementType>::AppendList (size_t blockSize)
 165         : m_blockSize   (blockSize)
 166         , m_numElements (0)
 167         , m_first               (new Block(0, blockSize))
 168         , m_last                (m_first)
 169 {
 170 }
 171
 172 template<typename ElementType>
 173 AppendList<ElementType>::~AppendList (void)
 174 {
 175         size_t  elementNdx      = 0;
 176         Block*  curBlock        = m_first;
 177
 178         while (curBlock)
 179         {
 180                 Block* const    delBlock        = curBlock;
 181
 182                 curBlock = delBlock->next;
 183
 184                 // Call destructor for allocated elements
 185                 for (; elementNdx < min(m_numElements, delBlock->blockNdx*m_blockSize); ++elementNdx)
 186                         delBlock->elements[elementNdx%m_blockSize].~ElementType();
 187
 188                 delete delBlock;
 189         }
 190
 191         DE_ASSERT(elementNdx == m_numElements);
 192 }
 193
 194 template<typename ElementType>
 195 void AppendList<ElementType>::clear (void)
 196 {
 197         // \todo [2016-03-28 pyry] Make thread-safe, if possible
 198
 199         size_t  elementNdx      = 0;
 200         Block*  curBlock        = m_first;
 201
 202         while (curBlock)
 203         {
 204                 Block* const    delBlock        = curBlock;
 205
 206                 curBlock = delBlock->next;
 207
 208                 // Call destructor for allocated elements
 209                 for (; elementNdx < min(m_numElements, delBlock->blockNdx*m_blockSize); ++elementNdx)
 210                         delBlock->elements[elementNdx%m_blockSize].~ElementType();
 211
 212                 if (delBlock != m_first)
 213                         delete delBlock;
 214         }
 215
 216         DE_ASSERT(elementNdx == m_numElements);
 217
 218         m_numElements   = 0;
 219         m_last                  = m_first;
 220 }
 221
 222 template<typename ElementType>
 223 void AppendList<ElementType>::append (const ElementType& value)
 224 {
 225         // Fetch curBlock first before allocating slot. Otherwise m_last might get updated before
 226         // this thread gets chance of reading it, leading to curBlock->blockNdx > blockNdx.
 227         Block*                  curBlock        = m_last;
 228
 229         deMemoryReadWriteFence();
 230
 231         {
 232                 const size_t    elementNdx      = deAtomicIncrementUSize(&m_numElements) - 1;
 233                 const size_t    blockNdx        = elementNdx / m_blockSize;
 234                 const size_t    slotNdx         = elementNdx - (blockNdx * m_blockSize);
 235
 236                 while (curBlock->blockNdx != blockNdx)
 237                 {
 238                         if (curBlock->next)
 239                                 curBlock = curBlock->next;
 240                         else
 241                         {
 242                                 // Other thread(s) are currently allocating additional block(s)
 243                                 deYield();
 244                         }
 245                 }
 246
 247                 // Did we allocate last slot? If so, add a new block
 248                 if (slotNdx+1 == m_blockSize)
 249                 {
 250                         Block* const    newBlock        = new Block(blockNdx+1, m_blockSize);
 251
 252                         deMemoryReadWriteFence();
 253
 254                         // At this point if any other thread is trying to allocate more blocks
 255                         // they are being blocked by curBlock->next being null. This guarantees
 256                         // that this thread has exclusive modify access to m_last.
 257                         m_last = newBlock;
 258                         deMemoryReadWriteFence();
 259
 260                         // At this point other threads might have skipped to newBlock, but we
 261                         // still have exclusive modify access to curBlock->next.
 262                         curBlock->next = newBlock;
 263                         deMemoryReadWriteFence();
 264                 }
 265
 266                 new (&curBlock->elements[slotNdx]) ElementType(value);
 267         }
 268 }
 269
 270 template<typename ElementType>
 271 typename AppendList<ElementType>::const_iterator AppendList<ElementType>::begin (void) const
 272 {
 273         return const_iterator(m_first, m_blockSize, 0);
 274 }
 275
 276 template<typename ElementType>
 277 typename AppendList<ElementType>::iterator AppendList<ElementType>::begin (void)
 278 {
 279         return iterator(m_first, m_blockSize, 0);
 280 }
 281
 282 template<typename ElementType>
 283 typename AppendList<ElementType>::const_iterator AppendList<ElementType>::end (void) const
 284 {
 285         return const_iterator(m_last, m_blockSize, m_numElements%m_blockSize);
 286 }
 287
 288 template<typename ElementType>
 289 typename AppendList<ElementType>::iterator AppendList<ElementType>::end (void)
 290 {
 291         return iterator(m_last, m_blockSize, m_numElements%m_blockSize);
 292 }
 293
 294 void    AppendList_selfTest             (void);
 295
 296 } // de
 297
 298 #endif // _DEAPPENDLIST_HPP