3 files changed, 265 insertions, 0 deletions
diff --git a/raul/Makefile.am b/raul/Makefile.am
index 77df449..7f47a50 100644
--- a/raul/Makefile.am
+++ b/raul/Makefile.am
@@ -29,6 +29,8 @@ raulinclude_HEADERS = \
 	Slave.hpp \
 	StampedChunkRingBuffer.hpp \
 	Stateful.hpp \
+	Table.hpp \
+	TableImpl.hpp \
 	Thread.hpp \
 	TimeSlice.hpp \
 	WeakPtr.hpp \
diff --git a/raul/Table.hpp b/raul/Table.hpp
new file mode 100644
index 0000000..b51bfe2
--- /dev/null
+++ b/raul/Table.hpp
@@ -0,0 +1,97 @@
+/* This file is part of Raul.
+ * Copyright (C) 2007 Dave Robillard <http://drobilla.net>
+ * 
+ * Raul 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.
+ * 
+ * Raul 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_TABLE_HPP
+#define RAUL_TABLE_HPP
+
+#include <vector>
+#include <algorithm>
+
+namespace Raul {
+
+
+/** Slow insertion, fast lookup, cache optimized, super fast sorted iteration.
+ *
+ * This has the advantage over std::map that iterating over the collection
+ * is super fast, and iteration is sorted.  Probably also faster due to all
+ * data being in a single chunk of memory, cache optimized, etc.
+ */
+template <typename K, typename T>
+class Table {
+public:
+	Table<K, T>() : _size(0), _array(NULL) {}
+	~Table<K, T>() { free(_array); }
+	
+	void clear() { free(_array); _array = NULL; _size = 0; }
+
+	typedef std::pair<K,T> Entry;
+
+	struct const_iterator {
+		const_iterator(const Table<K,T>& t, size_t i) : _table(t), _index(i) {}
+		inline const Entry& operator*() const { return _table._array[_index]; }
+		inline const Entry* operator->() const { return &_table._array[_index]; }
+		inline const_iterator& operator++() { ++_index; return *this; }
+		inline bool operator==(const const_iterator& i) const { return _index == i._index; }
+		inline bool operator!=(const const_iterator& i) const { return _index != i._index; }
+	private:
+		const Table<K,T>& _table;
+		size_t _index;
+	};
+	
+	struct iterator {
+		iterator(Table<K,T>& t, size_t i) : _table(t), _index(i) {}
+		inline Entry& operator*() const { return _table._array[_index]; }
+		inline Entry* operator->() const { return &_table._array[_index]; }
+		inline iterator& operator++() { ++_index; return *this; }
+		inline bool operator==(const iterator& i) const { return _index == i._index; }
+		inline bool operator!=(const iterator& i) const { return _index != i._index; }
+		operator const_iterator() { return *(const_iterator*)this; }
+	private:
+		Table<K,T>& _table;
+		size_t _index;
+	};
+
+	inline size_t size() const { return _size; }
+
+	void insert(K key, T value);
+	void remove(K& key);
+	void remove(iterator i);
+	
+	const_iterator find(const K& key) const;
+	iterator find(const K& key);
+
+	const_iterator begin() const { return const_iterator(*this, 0); }
+	const_iterator end()   const { return const_iterator(*this, size()); }
+	iterator       begin()       { return iterator(*this, 0); }
+	iterator       end()         { return iterator(*this, size()); }
+
+private:
+#ifndef NDEBUG
+	bool is_sorted() const;
+#endif
+
+	friend class iterator;
+	
+
+	size_t  _size;
+	Entry*  _array;
+};
+
+
+} // namespace Raul
+
+#endif // RAUL_TABLE_HPP
diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp
new file mode 100644
index 0000000..bac948e
--- /dev/null
+++ b/raul/TableImpl.hpp
@@ -0,0 +1,166 @@
+/* This file is part of Raul.
+ * Copyright (C) 2007 Dave Robillard <http://drobilla.net>
+ * 
+ * Raul 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.
+ * 
+ * Raul 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
+ */
+
+#include <cassert>
+#include <stdexcept>
+#include <algorithm>
+#include <iostream>
+#include <raul/Table.hpp>
+
+namespace Raul {
+
+#ifndef NDEBUG
+template <typename K, typename T>
+bool
+Table<K,T>::is_sorted() const
+{
+	if (_size <= 1)
+		return true;
+	
+	K prev_key = _array[0].first;
+
+	for (size_t i=1; i < _size; ++i)
+		if (_array[i].first < prev_key)
+			return false;
+		else
+			prev_key = _array[i].first;
+	
+	return true;
+}
+#endif
+
+
+/** Binary search (O(log(n))) */
+template <typename K, typename T>
+typename Table<K,T>::iterator
+Table<K,T>::find(const K& key)
+{
+	if (_size == 0)
+		return end();
+
+	size_t lower = 0;
+	size_t upper = _size - 1;
+	size_t i;
+	
+	while (upper >= lower) {
+		i = lower + ((upper - lower) / 2);
+		Entry& elem = _array[i];
+
+		if (elem.first == key)
+			return iterator(*this, i);
+		else if (i < _size-1 && elem.first < key)
+			lower = i + 1;
+		else if (i > 0)
+			upper = i - 1;
+		else
+			break;
+	}
+	
+	return end();
+}
+
+
+template <typename K, typename T>
+void
+Table<K,T>::insert(K key, T value)
+{
+	Entry new_entry = make_pair(key, value);
+
+	if (_size == 0) {
+		_array = (std::pair<K, T>*)malloc(sizeof(Entry) * 2);
+		_array[0] = new_entry;
+		++_size;
+		return;
+	} else if (_size == 1) {
+		if (key > _array[0].first) {
+			_array[1] = new_entry;
+		} else {
+			_array[1] = _array[0];
+			_array[0] = new_entry;
+		}
+		++_size;
+		return;
+	}
+
+	size_t lower = 0;
+	size_t upper = _size - 1;
+	size_t i;
+	
+	// Find the earliest element > key
+	while (upper >= lower) {
+		i = lower + ((upper - lower) / 2);
+		assert(i >= lower);
+		assert(i <= upper);
+		assert(_array[lower].first <= _array[i].first);
+		assert(_array[i].first <= _array[upper].first);
+
+		assert(i < _size);
+		Entry& elem = _array[i];
+
+		if (elem.first == key) {
+			break;
+		} else if (elem.first > key) {
+			if (i == 0 || _array[i-1].first < key)
+				break;
+			upper = i - 1;
+		} else {
+			lower = i + 1;
+		}
+	}
+
+	// Lil' off by one touchup :)
+	if (i < _size && _array[i].first <= key)
+		++i;
+	
+	_array = (Entry*)realloc(_array, (_size + 1) * sizeof(Entry));
+	
+	// FIXME: This could be faster using memmove etc...
+	for (size_t j=_size; j > i; --j)
+		_array[j] = _array[j-1];
+
+	_array[i] = new_entry;
+
+	++_size;
+
+	assert(is_sorted());
+}
+
+
+template <typename K, typename T>
+void
+Table<K,T>::remove(K& key)
+{
+	iterator i = find(key);
+	if (i != _array.end())
+		remove(i);
+}
+
+
+template <typename K, typename T>
+void
+Table<K,T>::remove(iterator i)
+{
+	_array.erase(i);
+
+#ifndef NDEBUG
+	assert(_array.is_sorted());
+#endif
+}
+
+
+} // namespace Raul
+