MemoryBlockList.h
Go to the documentation of this file.
1 // cwchessboard -- A C++ chessboard tool set
2 //
3 //! @file MemoryBlockList.h This file contains the declaration of class MemoryBlockList.
4 //
5 // Copyright (C) 2010, by
6 //
7 // Carlo Wood, Run on IRC <carlo@alinoe.com>
8 // RSA-1024 0x624ACAD5 1997-01-26 Sign & Encrypt
9 // Fingerprint16 = 32 EC A7 B6 AC DB 65 A6 F6 F6 55 DD 1C DC FF 61
10 //
11 // This program is free software: you can redistribute it and/or modify
12 // it under the terms of the GNU General Public License as published by
13 // the Free Software Foundation, either version 2 of the License, or
14 // (at your option) any later version.
15 //
16 // This program is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 // GNU General Public License for more details.
20 //
21 // You should have received a copy of the GNU General Public License
22 // along with this program. If not, see <http://www.gnu.org/licenses/>.
23 
24 #ifndef MEMORYBLOCKLIST_H
25 #define MEMORYBLOCKLIST_H
26 
27 #ifndef USE_PCH
28 #include "debug.h"
29 #include <glibmm/refptr.h>
30 #include <glibmm/thread.h>
31 #include <glibmm/dispatcher.h>
32 #endif
33 
34 #include "Referenceable.h"
35 
36 namespace util {
37 
38 /** @brief A contiguous block in memory.
39 *
40  * The data block is allocated with malloc(3) and the
41  * object is placed at the beginning of that allocated memory block.
42 * /
43 struct MemoryBlock : public Referenceable {
44  private:
45  // Do not allow construction, copying or assignment of this class.
46  MemoryBlock(MemoryBlock const&) : Referenceable() { }
47  MemoryBlock& operator=(MemoryBlock const&) { return* this; }
48 
49  /** @name Construction and destruction* /
50  //@{
51 
52  protected:
53  // Except construction by MemoryBlockNode (which derives from this class).
54  //! Constructor.
55  MemoryBlock() { }
56 
57  public:
58  /** @brief Operator new.
59  *
60  * Construct object (derived from MemoryBlock) with:
61  * \code
62  * Object* obj = new (block_size) Object(params);
63  * /
64  void* operator new(size_t object_size, size_t block_size)
65  {
66  void* ptr = malloc(object_size + block_size);
67  AllocTag(reinterpret_cast<char*>(ptr), "MemoryBlockNode (" << object_size << " bytes) + buffer allocation");
68  return ptr;
69  }
70 
71  //! Operator delete.
72  void operator delete(void* ptr) { free(ptr); }
73 
74  //@}
75 };
76 
77 /** @brief A node in a linked list of memory blocks.
78 *
79  * This class is derived from MemoryBlock.
80  * The difference is that each node contains a reference to the next node.
81  * As a result is that the very existence of a node keeps the chain of
82  * following nodes alive.
83 * /
84 struct MemoryBlockNode : public MemoryBlock {
85  private:
86  size_t M_valid_bytes; //!< Number of valid bytes in this block.
87  Glib::RefPtr<MemoryBlockNode> M_next; //!< Reference to the next block, if any.
88 
89  //! The offset from the 'this' pointer of this object to the start of the data block.
90  static size_t const S_data_offset;
91 
92  private:
93  // Constructor. See MemoryBlockNode::create.
94  MemoryBlockNode(void) : M_valid_bytes(0) { }
95 
96  /** @name Creation and destruction* /
97  //@{
98 
99  public:
100  /** @brief Allocate a new MemoryBlock with room for \a size bytes of data.
101  *
102  * The actual number of bytes allocated are sizeof(MemoryBlockNode) + \a size.
103  * /
104  static Glib::RefPtr<MemoryBlockNode> create(size_t size)
105  {
106  return Glib::RefPtr<MemoryBlockNode>(new (size) MemoryBlockNode);
107  }
108 
109  //@}
110 
111  private:
112  friend class MemoryBlockList;
113  // This function may only be called by class MemoryBlockList.
114 
115  /** @brief Set how many bytes where just written to \a new_block and append it to the chain.
116  *
117  * This block must be the last node in the chain.
118  * /
119  void append(Glib::RefPtr<MemoryBlockNode>& new_block, size_t valid_bytes)
120  {
121  new_block->M_valid_bytes = valid_bytes;
122  M_next.swap(new_block);
123  }
124 
125  public:
126  /** @name Accessors* /
127  //@{
128 
129  //! Return a pointer to the first data byte.
130  char* block_begin(void) { return reinterpret_cast<char*>(this) + S_data_offset; }
131 
132  //! Return a const pointer to the first data byte.
133  char const* block_begin(void) const { return reinterpret_cast<char const*>(this) + S_data_offset; }
134 
135  //! Return a pointer to one byte past the last valid byte in this block.
136  char const* block_end(void) const { return reinterpret_cast<char const*>(this) + S_data_offset + M_valid_bytes; }
137 
138  //! Return the number of valid bytes in this block.
139  size_t valid_bytes(void) const { return M_valid_bytes; }
140 
141  //! Return true if this is the last block in the chain.
142  bool is_last_block(void) const { return !M_next; }
143 
144  //! Return a reference to the next block.
145  Glib::RefPtr<MemoryBlockNode> const& next(void) const { return M_next; }
146 
147  //@}
148 };
149 
150 struct MutexCondPair {
151  Glib::Mutex mutex;
152  Glib::Cond cond;
153 };
154 
155 class MemoryBlockList;
156 
157 /** @brief An immutable MemoryBlockList forward iterator for boost::spirit.
158 *
159  * However, this class is <em>not</em> Default Constructible.
160 *
161  * Also, this class also has no postincrement operator.
162  * This is a deliberate choice; a good algorithm should use preincrement only for efficiency reasons.
163 *
164  * It is
165 *
166  * - <a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a> (copy-constructor and <code>operator=</code>)
167  * - <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a> (<code>operator==</code> and <code>operator!=</code>)
168  * - Dereferenceable (<code>operator*</code> which returns an <em>immutable</em> reference)
169  * - Incrementable (preincrement <code>operator++</code>)
170 *
171  * A forward iterator is essentially an <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
172  * However, incrementing a forward iterator does not invalidate copies of the old value and it is guaranteed that,
173  * if i and j are dereferenceable and i == j, then ++i == ++j. As a consequence of these two facts, it is possible
174  * to pass through the same Forward Iterator twice. In other words, it is possible to use Forward Iterators (unlike
175  * Input Iterators) in multipass algorithms.
176 *
177  * Of course, the past-the-end iterator is singular, non-dereferencable and non-incrementable.
178 * /
179 class MemoryBlockListIterator {
180  public:
181  /** @name Required iterator types* /
182  //@{
183 
184  typedef std::input_iterator_tag iterator_category;
185  typedef char value_type;
186  typedef ptrdiff_t difference_type;
187  typedef char const* pointer;
188  typedef char const& reference;
189 
190  //@}
191 
192  private:
193  MemoryBlockList* const M_buffer; //!< The linked list of blocks that this iterator belongs to.
194  Glib::RefPtr<MemoryBlockNode const> M_block; //!< Reference to block that this iterator points into.
195  char const* M_ptr; //!< Pointer to the current character inside that block.
196  char const* M_block_end; //!< Cache of pointer to the end of the block (MemoryBlockNode::block_end()).
197  int M_processed_blocks; //!< The number of blocks this iterator consumed.
198 
199  public:
200  /** @name Assignable* /
201  //@{
202 
203  //! Copy-constructor.
204  MemoryBlockListIterator(MemoryBlockListIterator const& iter) :
205  M_buffer(iter.M_buffer),
206  M_block(iter.M_block),
207  M_ptr(iter.M_ptr),
208  M_block_end(iter.M_block_end),
209  M_processed_blocks(iter.M_processed_blocks)
210  { }
211 
212  //! Assignment operator (used for backtracking).
213  MemoryBlockListIterator& operator=(MemoryBlockListIterator const& iter)
214  {
215  assert(M_buffer == iter.M_buffer);
216  M_block = iter.M_block;
217  M_ptr = iter.M_ptr;
218  M_block_end = iter.M_block_end;
219  M_processed_blocks = iter.M_processed_blocks;
220  }
221 
222  //@}
223 
224  /** @name Equality Comparable* /
225  //@{
226 
227  friend bool operator==(MemoryBlockListIterator const& a, MemoryBlockListIterator const& b) { return a.M_ptr == b.M_ptr; }
228  friend bool operator!=(MemoryBlockListIterator const& a, MemoryBlockListIterator const& b) { return a.M_ptr != b.M_ptr; }
229 
230  //@}
231 
232  /** @name Dereferenceable* /
233  //@{
234 
235  value_type const& operator*(void) const { return* M_ptr; }
236 
237  //@}
238 
239  /** @name Incrementable* /
240  //@{
241 
242  //! Pre-increment operator.
243  // This function is only called from the DatabaseSeekable::read_thread thread.
244  MemoryBlockListIterator& operator++(void)
245  {
246  if (G_UNLIKELY(M_ptr == M_block_end))
247  advance_to_next_block();
248  else
249  ++M_ptr;
250  return* this;
251  }
252 
253  //@}
254 
255  //! Construct the past-the-end iterator.
256  MemoryBlockListIterator(MemoryBlockList* buffer) : M_buffer(buffer), M_ptr(NULL), M_processed_blocks(0) { }
257 
258  //! Make this iterator point to the beginning of \a node.
259  MemoryBlockListIterator& operator=(Glib::RefPtr<MemoryBlockNode const> const& node)
260  {
261  assert(M_buffer);
262  M_block = node;
263  M_ptr = node->block_begin();
264  M_block_end = node->block_end() - 1;
265  M_processed_blocks = 0;
266  }
267 
268  /** @name Accessors* /
269  //@{
270 
271  int processed_blocks(void) const { return M_processed_blocks; }
272 
273  MemoryBlockList* buffer(void) { return M_buffer; }
274 
275  //@}
276 
277  private:
278  void advance_to_next_block(void);
279 };
280 
281 /** A linked list of MemoryBlockNode objects.
282 *
283  * The idea of this linked list is as follows:
284 *
285  * A newly created list is entirely empty.
286  * When the first block is appended, then M_begin is set to point to this first block.
287 *
288  * A different thread should only start to process this block once the
289  * second block is appended: when
290 * /
291 class MemoryBlockList {
292  public:
293  typedef MemoryBlockListIterator iterator;
294  typedef sigc::slot<void> SlotNeedMoreData;
295 
296  // The the minimum buffer size in blocks is 4.
297  // We use 8 because that makes the inner loop use
298  // a little let overhead related to buffer full checks.
299  static int const S_max_blocks = 8;
300 
301  private:
302  Glib::RefPtr<MemoryBlockNode> M_last_node; //!< A pointer to the last node in the list.
303  iterator M_begin; //!< A pointer to the first node in the list. Read/write access by 'DatabaseSeekable::read_thread'.
304  int M_appended_blocks; //!< The number of blocks appended to this list. Read access by 'DatabaseSeekable::read_thread'.
305  bool M_closed; //!< False until the last block was appended and the read_thread is the only thread accessing this buffer.
306  bool M_buffer_full; //!< True while the main thread stops reading new blocks.
307  Glib::Dispatcher M_need_more_data; //!< Used to signal the main thread that more data can be appended to the buffer.
308  SlotNeedMoreData M_slot_need_more_data; //!< Pass the signal on the calling object.
309  MutexCondPair M_more_data; //!< Used for signaling that more data in the buffer is ready to be processed.
310 
311  public:
312  MemoryBlockList(SlotNeedMoreData const& slot) : M_begin(this), M_appended_blocks(0), M_closed(false), M_buffer_full(false), M_slot_need_more_data(slot)
313  { M_need_more_data.connect(sigc::mem_fun(*this,& MemoryBlockList::need_more_data_callback)); }
314 
315  void append(Glib::RefPtr<MemoryBlockNode>& new_block, size_t valid_bytes)
316  {
317  int blocks;
318  if (G_UNLIKELY(!M_last_node))
319  {
320  // If there is no last node, then this is the very first data block
321  // being appended. In that case the 'read thread' is not running:
322  // there wasn't any data yet in this buffer. Therefore, no locks
323  // are necessary.
324  new_block->M_valid_bytes = valid_bytes;
325  M_last_node.swap(new_block);
326  M_begin = M_last_node;
327  Dout(dc::notice, "Appending FIRST block to the list. Number of blocks is now 1");
328  assert(M_appended_blocks == 0);
329  M_appended_blocks = 1;
330  blocks = 1;
331  }
332  else
333  {
334  // The read thread is only running if there is more than one
335  // block available for processing (it won't touch the last
336  // block). Therefore, appending a new block doesn't need locking.
337  M_last_node->append(new_block, valid_bytes);
338  M_last_node = M_last_node->M_next;
339  // Increment block counter and signal the read thread if we have more than 1 block.
340  ++M_appended_blocks;
341  blocks = M_appended_blocks - M_begin.processed_blocks();
342  Dout(dc::notice, "Appending a new block to the list. Number of unread blocks: " << blocks);
343  // There should be always at least two blocks in the buffer now.
344  M_more_data.cond.signal();
345  }
346  // Stop reading if there are eight or more blocks already buffered and waiting.
347  if (blocks < S_max_blocks)
348  M_slot_need_more_data();
349  else
350  {
351  Dout(dc::notice, "The buffer is full!");
352  M_more_data.mutex.lock();
353  M_buffer_full = true;
354  // Wake up 'read thread' just in case (special case).
355  M_more_data.cond.signal();
356  M_more_data.mutex.unlock();
357  }
358  }
359 
360  void close(void)
361  {
362  M_more_data.mutex.lock();
363  M_closed = true;
364  // Wake up 'read thread' just in case (special case).
365  M_more_data.cond.signal();
366  M_more_data.mutex.unlock();
367  }
368 
369  bool closed(void) const { return M_closed; }
370  bool full(void) const { return M_buffer_full; }
371 
372  iterator& begin(void)
373  {
374  // Wait until there is another block, so we can start to process the first block.
375  while (!can_process_next_block(M_begin))
376  wait_for_more_data(M_begin);
377  return M_begin;
378  }
379  iterator end(void) const { return iterator(const_cast<MemoryBlockList*>(this)); }
380 
381  //! @brief Return the number of blocks that were appended to the linked list.
382  int appended_blocks(void) const { return M_appended_blocks; }
383 
384  //! Returns ok if the read_thread is allowed to process the block that M_begin is pointing at.
385  // This function is only called from DatabaseSeekable::read_thread.
386  bool can_process_next_block(iterator const& iter)
387  {
388  // Do not process the last block while we're still writing to the
389  // buffer because that would require using a mutex on a per character
390  // basis, while not processing the last block allows us to not us
391  // locking at all!
392  return M_closed || M_appended_blocks - iter.processed_blocks() >= 2;
393  }
394 
395  MutexCondPair& more_data(void) { return M_more_data; }
396 
397  Glib::Dispatcher& need_more_data(void) { return M_need_more_data; }
398 
399  void need_more_data_callback(void);
400 
401  void wait_for_more_data(iterator const& iter)
402  {
403  Dout(dc::notice, "Waiting for more data...");
404 continue_waiting:
405 #if 0
406  timespec start_sleep_time_real, stop_sleep_time_real;
407  timespec start_sleep_time_process, stop_sleep_time_process;
408  clock_gettime(CLOCK_PROCESS_CPUTIME_ID,& start_sleep_time_process);
409  clock_gettime(CLOCK_REALTIME,& start_sleep_time_real);
410 #endif
411  M_more_data.mutex.lock();
412  if (!M_buffer_full && !M_closed)
413  M_more_data.cond.wait(M_more_data.mutex);
414  M_more_data.mutex.unlock();
415 #if 0
416  clock_gettime(CLOCK_PROCESS_CPUTIME_ID,& stop_sleep_time_process);
417  clock_gettime(CLOCK_REALTIME,& stop_sleep_time_real);
418  stop_sleep_time_process -= start_sleep_time_process;
419  wait_time_thread_process += stop_sleep_time_process;
420  stop_sleep_time_real -= start_sleep_time_real;
421  wait_time_thread_real += stop_sleep_time_real;
422 #endif
423  // There is a small possibility that the main thread delayed
424  // setting M_buffer_full so that this thread already processed
425  // half of the buffer and got here even before M_buffer_full
426  // is set. Therefore, this thread is also woken up again
427  // when M_buffer_full is actually set.
428  if (M_buffer_full)
429  {
430  // Ok that is "weird". Now waste some cpu for this special case.
431  if (!can_process_next_block(iter))
432  {
433  M_need_more_data.emit();
434  goto continue_waiting;
435  }
436  }
437  Dout(dc::notice, "Got data!");
438  }
439 };
440 
441 } // namespace util
442 
443 #endif // MEMORYBLOCKLIST_H
This file contains the declaration of class Referenceable.

Copyright © 2006 - 2010 Carlo Wood.  All rights reserved.