summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--raul/Makefile.am2
-rw-r--r--raul/Table.hpp97
-rw-r--r--raul/TableImpl.hpp166
-rw-r--r--tests/Makefile.am5
-rw-r--r--tests/atomic_test.cpp4
-rw-r--r--tests/list_test.cpp2
-rw-r--r--tests/midi_ringbuffer_test.cpp2
-rw-r--r--tests/path_test.cpp2
-rw-r--r--tests/quantize_test.cpp2
-rw-r--r--tests/queue_test.cpp8
-rw-r--r--tests/rdf_test.cpp4
-rw-r--r--tests/ringbuffer_test.cpp2
-rw-r--r--tests/smf_test.cpp4
-rw-r--r--tests/thread_test.cpp2
-rw-r--r--tests/time_test.cpp2
15 files changed, 286 insertions, 18 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
+
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 27a8f1a..ae3db13 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -14,7 +14,8 @@ noinst_PROGRAMS = \
time_test \
quantize_test \
smf_test \
- rdf_test
+ rdf_test \
+ table_test
thread_test_LDADD = $(ALL_LIBS)
path_test_LDADD = $(ALL_LIBS)
@@ -27,6 +28,7 @@ time_test_LDADD = $(ALL_LIBS)
quantize_test_LDADD = $(ALL_LIBS)
smf_test_LDADD = $(ALL_LIBS)
rdf_test_LDADD = $(ALL_LIBS)
+table_test_LDADD = $(ALL_LIBS)
path_test_SOURCES = path_test.cpp
thread_test_SOURCES = thread_test.cpp
@@ -39,5 +41,6 @@ time_test_SOURCES = time_test.cpp
quantize_test_SOURCES = quantize_test.cpp
smf_test_SOURCES = smf_test.cpp
rdf_test_SOURCES = rdf_test.cpp
+table_test_SOURCES = table_test.cpp
endif
diff --git a/tests/atomic_test.cpp b/tests/atomic_test.cpp
index c10677a..caa6395 100644
--- a/tests/atomic_test.cpp
+++ b/tests/atomic_test.cpp
@@ -1,6 +1,6 @@
#include <iostream>
-#include <raul/AtomicInt.h>
-#include <raul/AtomicPtr.h>
+#include <raul/AtomicInt.hpp>
+#include <raul/AtomicPtr.hpp>
using namespace std;
using namespace Raul;
diff --git a/tests/list_test.cpp b/tests/list_test.cpp
index 133067b..d374b40 100644
--- a/tests/list_test.cpp
+++ b/tests/list_test.cpp
@@ -1,6 +1,6 @@
#include <iostream>
#include <cstddef>
-#include <raul/List.h>
+#include <raul/List.hpp>
using namespace std;
using namespace Raul;
diff --git a/tests/midi_ringbuffer_test.cpp b/tests/midi_ringbuffer_test.cpp
index 5f903d1..706aef1 100644
--- a/tests/midi_ringbuffer_test.cpp
+++ b/tests/midi_ringbuffer_test.cpp
@@ -1,5 +1,5 @@
#include <iostream>
-#include "raul/StampedChunkRingBuffer.h"
+#include "raul/StampedChunkRingBuffer.hpp"
#include "raul/midi_names.h"
using namespace std;
diff --git a/tests/path_test.cpp b/tests/path_test.cpp
index 280f968..cf62340 100644
--- a/tests/path_test.cpp
+++ b/tests/path_test.cpp
@@ -1,5 +1,5 @@
#include <iostream>
-#include <raul/Path.h>
+#include <raul/Path.hpp>
using namespace std;
using namespace Raul;
diff --git a/tests/quantize_test.cpp b/tests/quantize_test.cpp
index 434df2e..f79d279 100644
--- a/tests/quantize_test.cpp
+++ b/tests/quantize_test.cpp
@@ -1,5 +1,5 @@
#include <iostream>
-#include <raul/Quantizer.h>
+#include <raul/Quantizer.hpp>
using namespace std;
using namespace Raul;
diff --git a/tests/queue_test.cpp b/tests/queue_test.cpp
index 0b8bbd3..7a1d44b 100644
--- a/tests/queue_test.cpp
+++ b/tests/queue_test.cpp
@@ -6,10 +6,10 @@
#include <stdlib.h>
#include <fcntl.h>
#include <termios.h>
-#include "raul/SRSWQueue.h"
-#include "raul/SRMWQueue.h"
-#include "raul/Thread.h"
-#include "raul/AtomicInt.h"
+#include "raul/SRSWQueue.hpp"
+#include "raul/SRMWQueue.hpp"
+#include "raul/Thread.hpp"
+#include "raul/AtomicInt.hpp"
using namespace std;
using namespace Raul;
diff --git a/tests/rdf_test.cpp b/tests/rdf_test.cpp
index 6e224cf..afb1887 100644
--- a/tests/rdf_test.cpp
+++ b/tests/rdf_test.cpp
@@ -1,5 +1,5 @@
-#include <raul/RDFModel.h>
-#include <raul/RDFQuery.h>
+#include <raul/RDFModel.hpp>
+#include <raul/RDFQuery.hpp>
int
main()
diff --git a/tests/ringbuffer_test.cpp b/tests/ringbuffer_test.cpp
index 01f136f..851d7b9 100644
--- a/tests/ringbuffer_test.cpp
+++ b/tests/ringbuffer_test.cpp
@@ -1,5 +1,5 @@
#include <iostream>
-#include "raul/RingBuffer.h"
+#include "raul/RingBuffer.hpp"
using namespace std;
using namespace Raul;
diff --git a/tests/smf_test.cpp b/tests/smf_test.cpp
index 3396b90..3ca9715 100644
--- a/tests/smf_test.cpp
+++ b/tests/smf_test.cpp
@@ -1,7 +1,7 @@
#include <iostream>
#include <string>
-#include <raul/SMFReader.h>
-#include <raul/SMFWriter.h>
+#include <raul/SMFReader.hpp>
+#include <raul/SMFWriter.hpp>
using namespace std;
using namespace Raul;
diff --git a/tests/thread_test.cpp b/tests/thread_test.cpp
index ef3ad53..eb06701 100644
--- a/tests/thread_test.cpp
+++ b/tests/thread_test.cpp
@@ -1,5 +1,5 @@
#include <iostream>
-#include <raul/Thread.h>
+#include <raul/Thread.hpp>
using namespace std;
using namespace Raul;
diff --git a/tests/time_test.cpp b/tests/time_test.cpp
index 0ffdc61..c5c89b7 100644
--- a/tests/time_test.cpp
+++ b/tests/time_test.cpp
@@ -1,5 +1,5 @@
#include <iostream>
-#include <raul/TimeSlice.h>
+#include <raul/TimeSlice.hpp>
using namespace std;
using namespace Raul;
generated by cgit v1.2.1 (git 2.18.0) at 2024-09-29 23:08:31 +0000