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)100 FastQueue<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)116 void 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()138 void 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)151 void 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)159 inline void swap(FastQueue<T>& o1, FastQueue<T>& o2) {
160   o1.swap(o2);
161 }
162 
163 #endif  // ifndef FAST_QUEUE_H_
164