1 files changed, 158 insertions, 0 deletions
diff --git a/src/common/util/Queue.h b/src/common/util/Queue.h
new file mode 100644
index 00000000..649cbcbe
--- /dev/null
+++ b/src/common/util/Queue.h
@@ -0,0 +1,158 @@
+/* This file is part of Om.  Copyright (C) 2005 Dave Robillard.
+ * 
+ * Om is free software; you can redistribute it and/or modify it under the
+ * terms of the GNU General Public License as published by the Free Software
+ * Foundation; either version 2 of the License, or (at your option) any later
+ * version.
+ * 
+ * Om is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for details.
+ * 
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef QUEUE_H
+#define QUEUE_H
+
+#include <cassert>
+#include <cstdlib>
+
+
+/** Realtime-safe single-reader single-writer queue (aka lock-free ringbuffer)
+ *
+ * Implemented as a dequeue in a fixed array.  This is read/write thread-safe, 
+ * pushing and popping may occur simultaneously by seperate threads, but
+ * the push and pop operations themselves are not thread-safe.
+ *
+ * FIXME: Verify atomicity of everything here.
+ */
+template <typename T>
+class Queue
+{
+public:
+	Queue(size_t size);
+	~Queue();
+	
+	inline bool is_empty() const;
+	inline bool is_full()  const;
+	
+	inline size_t capacity() const { return m_size-1; }
+	inline size_t fill() const;
+
+	inline T&   front() const;
+
+	inline bool push(T obj);
+	inline T&   pop();
+	
+private:
+	// Prevent copies (these are undefined)
+	Queue(const Queue& copy);
+	Queue& operator=(const Queue& copy);
+	
+	volatile size_t m_front;   ///< Index to front of queue (circular)
+	volatile size_t m_back;    ///< Index to back of queue (one past last element) (circular)
+	const    size_t m_size;    ///< Size of @ref m_objects (you can store m_size-1 objects)
+	T* const        m_objects; ///< Fixed array containing queued elements
+};
+
+
+template<typename T>
+Queue<T>::Queue(size_t size)
+: m_front(0),
+  m_back(0),
+  m_size(size+1),
+  m_objects((T*)calloc(m_size, sizeof(T)))
+{
+}
+
+
+template <typename T>
+Queue<T>::~Queue()
+{
+	free(m_objects);
+}
+
+
+/** Return whether or not the queue is empty.
+ */
+template <typename T>
+inline bool
+Queue<T>::is_empty() const
+{
+	return (m_back == m_front);
+}
+
+
+/** Return whether or not the queue is full.
+ */
+template <typename T>
+inline bool
+Queue<T>::is_full() const
+{
+	// FIXME: This can probably be faster
+	return (fill() == capacity());
+}
+
+
+/** Returns how many elements are currently in the queue.
+ */
+template <typename T>
+inline size_t
+Queue<T>::fill() const
+{
+	return (m_back + m_size - m_front) % m_size;
+}
+
+
+/** Return the element at the front of the queue without removing it
+ */
+template <typename T>
+inline T&
+Queue<T>::front() const
+{
+	return m_objects[m_front];
+}
+
+
+/** Push an item onto the back of the Queue - realtime-safe, not thread-safe.
+ *
+ * @returns true if @a elem was successfully pushed onto the queue,
+ * false otherwise (queue is full).
+ */
+template <typename T>
+inline bool
+Queue<T>::push(T elem)
+{
+	if (is_full()) {
+		return false;
+	} else {
+		m_objects[m_back] = elem;
+		m_back = (m_back + 1) % (m_size);
+		return true;
+	}
+}
+
+
+/** Pop an item off the front of the queue - realtime-safe, not thread-safe.
+ *
+ * It is a fatal error to call pop() when the queue is empty.
+ *
+ * @returns the element popped.
+ */
+template <typename T>
+inline T&
+Queue<T>::pop()
+{
+	assert(!is_empty());
+
+	T& r = m_objects[m_front];
+	m_front = (m_front + 1) % (m_size);
+	
+	return r;
+}
+
+
+#endif // QUEUE_H