1 /* 2 Scan Tailor - Interactive post-processing tool for scanned pages. 3 Copyright (C) Joseph Artsimovich <joseph.artsimovich@gmail.com> 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 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 this program. If not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #ifndef FAST_QUEUE_H_ 20 #define FAST_QUEUE_H_ 21 22 #include <boost/foreach.hpp> 23 #include <boost/intrusive/list.hpp> 24 #include <boost/type_traits/alignment_of.hpp> 25 #include <cassert> 26 #include <cstddef> 27 #include <cstdint> 28 #include "NonCopyable.h" 29 30 template <typename T> 31 class FastQueue { 32 public: FastQueue()33 FastQueue() : m_chunkCapacity(defaultChunkCapacity()) {} 34 35 FastQueue(const FastQueue& other); 36 ~FastQueue()37 ~FastQueue() { m_chunkList.clear_and_dispose(ChunkDisposer()); } 38 39 FastQueue& operator=(const FastQueue& other); 40 empty()41 const bool empty() const { return m_chunkList.empty(); } 42 front()43 T& front() { return *m_chunkList.front().pBegin; } 44 front()45 const T& front() const { return *m_chunkList.front().pBegin; } 46 47 void push(const T& t); 48 49 void pop(); 50 51 void swap(FastQueue& other); 52 53 private: 54 struct Chunk : public boost::intrusive::list_base_hook<> { DECLARE_NON_COPYABLEChunk55 DECLARE_NON_COPYABLE(Chunk) 56 57 public: 58 explicit Chunk(size_t capacity) { 59 const uintptr_t p = (uintptr_t)(this + 1); 60 const size_t alignment = boost::alignment_of<T>::value; 61 pBegin = (T*) (((p + alignment - 1) / alignment) * alignment); 62 pEnd = pBegin; 63 pBufferEnd = pBegin + capacity; 64 assert(size_t((char*) pBufferEnd - (char*) this) <= storageRequirement(capacity)); 65 } 66 ~ChunkChunk67 ~Chunk() { 68 for (; pBegin != pEnd; ++pBegin) { 69 pBegin->~T(); 70 } 71 } 72 storageRequirementChunk73 static size_t storageRequirement(size_t capacity) { 74 return sizeof(Chunk) + boost::alignment_of<T>::value - 1 + capacity * sizeof(T); 75 } 76 77 T* pBegin; 78 T* pEnd; 79 T* pBufferEnd; 80 // An implicit array of T follows. 81 }; 82 83 struct ChunkDisposer { operatorChunkDisposer84 void operator()(Chunk* chunk) { 85 chunk->~Chunk(); 86 delete[](char*) chunk; 87 } 88 }; 89 90 typedef boost::intrusive::list<Chunk, boost::intrusive::constant_time_size<false>> ChunkList; 91 defaultChunkCapacity()92 static size_t defaultChunkCapacity() { return (sizeof(T) >= 4096) ? 1 : 4096 / sizeof(T); } 93 94 ChunkList m_chunkList; 95 size_t m_chunkCapacity; 96 }; 97 98 99 template <typename T> FastQueue(const FastQueue & other)100FastQueue<T>::FastQueue(const FastQueue& other) : m_chunkCapacity(other.m_chunkCapacity) { 101 for (Chunk& chunk : other.m_chunkList) { 102 for (const T* obj = chunk->pBegin; obj != chunk->pEnd; ++obj) { 103 push(*obj); 104 } 105 } 106 } 107 108 template <typename T> 109 FastQueue<T>& FastQueue<T>::operator=(const FastQueue& other) { 110 FastQueue(other).swap(*this); 111 112 return *this; 113 } 114 115 template <typename T> push(const T & t)116void FastQueue<T>::push(const T& t) { 117 Chunk* chunk = 0; 118 119 if (!m_chunkList.empty()) { 120 chunk = &m_chunkList.back(); 121 if (chunk->pEnd == chunk->pBufferEnd) { 122 chunk = 0; 123 } 124 } 125 126 if (!chunk) { 127 // Create a new chunk. 128 char* buf = new char[Chunk::storageRequirement(m_chunkCapacity)]; 129 chunk = new (buf) Chunk(m_chunkCapacity); 130 m_chunkList.push_back(*chunk); 131 } 132 // Push to chunk. 133 new (chunk->pEnd) T(t); 134 ++chunk->pEnd; 135 } 136 137 template <typename T> pop()138void FastQueue<T>::pop() { 139 assert(!empty()); 140 141 Chunk* chunk = &m_chunkList.front(); 142 chunk->pBegin->~T(); 143 ++chunk->pBegin; 144 if (chunk->pBegin == chunk->pEnd) { 145 m_chunkList.pop_front(); 146 ChunkDisposer()(chunk); 147 } 148 } 149 150 template <typename T> swap(FastQueue & other)151void FastQueue<T>::swap(FastQueue& other) { 152 m_chunkList.swap(other.m_chunkList); 153 const size_t tmp = m_chunkCapacity; 154 m_chunkCapacity = other.m_chunkCapacity; 155 other.m_chunkCapacity = tmp; 156 } 157 158 template <typename T> swap(FastQueue<T> & o1,FastQueue<T> & o2)159inline void swap(FastQueue<T>& o1, FastQueue<T>& o2) { 160 o1.swap(o2); 161 } 162 163 #endif // ifndef FAST_QUEUE_H_ 164