summaryrefslogtreecommitdiffstats
path: root/raul/Queue.h
diff options
context:
space:
mode:
Diffstat (limited to 'raul/Queue.h')
-rw-r--r--raul/Queue.h160
1 files changed, 160 insertions, 0 deletions
diff --git a/raul/Queue.h b/raul/Queue.h
new file mode 100644
index 0000000..f400497
--- /dev/null
+++ b/raul/Queue.h
@@ -0,0 +1,160 @@
+/* This file is part of Ingen. Copyright (C) 2006 Dave Robillard.
+ *
+ * Ingen 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.
+ *
+ * Ingen 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.,
+ * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef RAUL_QUEUE_H
+#define RAUL_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)))
+{
+ assert(size > 1);
+}
+
+
+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());
+ assert(m_size > 0);
+
+ T& r = m_objects[m_front];
+ m_front = (m_front + 1) % (m_size);
+
+ return r;
+}
+
+
+#endif // RAUL_QUEUE_H