Added Om aka Graph aka god knows what

git-svn-id: http://svn.drobilla.net/lad/grauph@9 a436a847-0d15-0410-975c-d299462d15a1

6 files changed, 528 insertions, 0 deletions

diff --git a/src/common/util/CountedPtr.h b/src/common/util/CountedPtr.h
new file mode 100644
index 00000000..f2079c7c
--- /dev/null
+++ b/src/common/util/CountedPtr.h
@@ -0,0 +1,185 @@
+/* A Reference Counting Smart Pointer.
+ * Copyright (C) 2006 Dave Robillard.
+ * 
+ * This 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.
+ * 
+ * This 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 COUNTED_PTR_H
+#define COUNTED_PTR_H
+
+#include <cassert>
+#include <cstddef>
+
+
+/** Simple reference counted pointer.
+ *
+ * Allocates one counter on the heap on initial construction.  You can safely
+ * cast a CountedPtr<X> to a CountedPtr<Y> iff Y is a base of X (eg the cast
+ * will only compile if it is a valid up-cast).
+ *
+ * It is possible for this to be a NULL pointer, and a boolean conversion
+ * operator is provided so you can test for this with "if (someCountedPtr)".
+ * Dereferencing a NULL CountedPtr will result in a failed assertion if
+ * debugging is enabled.
+ *
+ * FIXME: test this more thoroughly
+ */
+template <class T>
+class CountedPtr
+{
+public:
+	
+	// Declare some other type of CountedPtr as a friend (for casting)
+	template <class Y> friend class CountedPtr;
+
+
+	/** Allocate a new Counter (if p is non-NULL) */
+	CountedPtr(T* p)
+	: _counter(NULL)
+	{
+		if (p)
+			_counter = new Counter(p);
+	}
+
+	~CountedPtr()
+	{
+		release();
+	}
+
+	/** Copy a CountedPtr with the same type. */
+	CountedPtr(const CountedPtr& copy) 
+	: _counter(NULL)
+	{
+		assert(copy);
+		assert(this != &copy);
+		retain(copy._counter);
+	}
+	
+	/** Copy a CountedPtr to a valid base class.
+	 */
+	template <class Y>
+	CountedPtr(const CountedPtr<Y>& y)
+	: _counter(NULL)
+	{
+		assert(this != (CountedPtr*)&y);
+
+		// Fail if this is not a valid cast
+		if (y) {
+			T* const unused_variable = static_cast<Y* const>(y._counter->ptr);
+			assert(unused_variable == y._counter->ptr); // shuts up gcc
+		}
+		
+		//release();
+		retain((Counter*)y._counter);
+	}
+
+	/** Assign to the value of a CountedPtr of the same type. */
+	CountedPtr& operator=(const CountedPtr& copy)
+	{
+		if (this != &copy) {
+			release();
+			retain(copy._counter);
+		}
+		return *this;
+	}
+
+	/** Assign to the value of a CountedPtr of a different type. */
+	template <class Y>
+	CountedPtr& operator=(const CountedPtr<Y>& y)
+	{
+		if (this != (CountedPtr*)&y) {
+			release();
+			retain(y._counter);
+		}
+		return *this;
+	}
+
+	inline bool operator==(const CountedPtr& p) const
+	{
+		return (_counter == p._counter);
+	}
+
+	inline bool operator!=(const CountedPtr& p) const
+	{
+		return (_counter != p._counter);
+	}
+
+	/** Allow testing for NULL nicely like a real pointer */
+	operator bool() const
+	{
+		return (_counter && _counter->ptr);
+	}
+
+	inline T& operator*() const
+	{
+		assert(_counter);
+		assert(_counter->count > 0);
+		assert(_counter->ptr);
+		return *_counter->ptr;
+	}
+
+	inline T* operator->() const
+	{
+		assert(_counter);
+		assert(_counter->count > 0);
+		assert(_counter->ptr);
+		return _counter->ptr;
+	}
+
+	inline T* get() const { return _counter ? _counter->ptr : 0; }
+
+	bool unique() const { return (_counter ? _counter->count == 1 : true); }
+
+private:
+	/** Stored on the heap and referred to by all existing CountedPtr's to
+	 * the object */
+	struct Counter
+	{
+		Counter(T* p)
+		: ptr(p)
+		, count(1)
+		{
+			assert(p);
+		}
+		
+		T* const        ptr;
+		volatile size_t count;
+	};
+
+	/** Increment the count */
+	void retain(Counter* c) 
+	{	
+		assert(_counter == NULL || _counter == c);
+		_counter = c;
+		if (_counter)
+			++c->count;
+	}
+	
+	/** Decrement the count, delete if we're the last reference */
+	void release()
+	{	
+		if (_counter) {
+			if (--(_counter->count) == 0) {
+				delete _counter->ptr;
+				delete _counter;
+			}
+			_counter = NULL;
+		}
+	}
+	
+
+	Counter* _counter;
+};
+
+#endif // COUNTED_PTR_H
diff --git a/src/common/util/Makefile.am b/src/common/util/Makefile.am
new file mode 100644
index 00000000..b835dfde
--- /dev/null
+++ b/src/common/util/Makefile.am
@@ -0,0 +1,6 @@
+EXTRA_DIST = \
+	CountedPtr.h \
+	Path.h \
+	Queue.h \
+	Semaphore.h \
+	types.h
diff --git a/src/common/util/Path.h b/src/common/util/Path.h
new file mode 100644
index 00000000..126fe01d
--- /dev/null
+++ b/src/common/util/Path.h
@@ -0,0 +1,84 @@
+/* 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 PATH_H
+#define PATH_H
+
+#include <string>
+#include <cassert>
+using std::string;
+
+namespace Om {
+
+	
+/** Simple wrapper around standard string with useful path-specific methods.
+ */
+class Path : public std::basic_string<char> {
+public:
+	Path(const std::basic_string<char>& path)
+	: std::basic_string<char>(path)
+	{
+		assert(path.length() > 0);
+	}
+	
+	
+	inline bool is_valid() const
+	{
+		return (find_last_of("/") != string::npos);
+	}
+	
+	/** Return the name of this object (everything after the last '/').
+	 */
+	inline std::basic_string<char> name() const
+	{
+		assert(is_valid());
+
+		if ((*this) == "/")
+			return "";
+		else
+			return substr(find_last_of("/")+1);
+	}
+	
+	
+	/** Return the parent's path.
+	 *
+	 * Calling this on the path "/" will return "/".
+	 */
+	inline Path parent() const
+	{
+		assert(is_valid());
+		
+		std::basic_string<char> parent = substr(0, find_last_of("/"));
+		return (parent == "") ? "/" : parent;
+	}
+	
+	inline Path base_path() const
+	{
+		assert(is_valid());
+		
+		if ((*this) == "/")
+			return *this;
+		else
+			return (*this) + "/";
+	}
+
+	Path(const char* s) : std::basic_string<char>(s) {}
+};
+	
+
+} // namespace Om
+
+#endif // PATH_H
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
diff --git a/src/common/util/Semaphore.h b/src/common/util/Semaphore.h
new file mode 100644
index 00000000..c8abaf35
--- /dev/null
+++ b/src/common/util/Semaphore.h
@@ -0,0 +1,63 @@
+/* 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 SEMAPHORE_H
+#define SEMAPHORE_H
+
+#include <semaphore.h>
+
+
+/** Trivial wrapper around POSIX semaphores.
+ *
+ * This was created to provide an alternative debuggable implementation of
+ * semaphores based on a cond/mutex pair because semaphore's appeared not to
+ * work in GDB.  Turns out sem_wait can fail when run in GDB, and Debian
+ * really needs to update it's man pages.
+ *
+ * This class remains as a pretty wrapper/abstraction that does nothing.
+ */
+class Semaphore {
+public:
+	inline Semaphore(unsigned int initial) { sem_init(&m_sem, 0, initial); }
+	
+	inline ~Semaphore() { sem_destroy(&m_sem); }
+
+	/** Increment (and signal any waiters).
+	 * 
+	 * Realtime safe.
+	 */
+	inline void post() { sem_post(&m_sem); }
+
+	/** Wait until count is > 0, then decrement.
+	 *
+	 * Note that sem_wait always returns 0 in practise.  It returns nonzero
+	 * when run in GDB, so the while is necessary to allow debugging.
+	 *
+	 * Obviously not realtime safe.
+	 */
+	inline void wait() { while (sem_wait(&m_sem) != 0) ; }
+	
+	/** Non-blocking version of wait().
+	 *
+	 * Realtime safe?
+	 */
+	inline int  try_wait() { return sem_trywait(&m_sem); }
+private:
+	sem_t m_sem;
+};
+
+
+#endif // SEMAPHORE_H
diff --git a/src/common/util/types.h b/src/common/util/types.h
new file mode 100644
index 00000000..4c138292
--- /dev/null
+++ b/src/common/util/types.h
@@ -0,0 +1,32 @@
+/* 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 TYPES_H
+#define TYPES_H
+
+#include <cstddef> // for NULL, size_t, etc
+#include <jack/jack.h>
+
+typedef unsigned char uchar;
+typedef unsigned int uint;
+typedef unsigned long ulong;
+
+typedef jack_default_audio_sample_t sample;
+typedef jack_nframes_t samplecount;
+typedef jack_nframes_t samplerate;
+
+#endif // TYPES_H