diff options
| -rw-r--r-- | raul/Path.hpp | 5 | ||||
| -rw-r--r-- | raul/PathTable.hpp | 54 | ||||
| -rw-r--r-- | raul/Table.hpp | 122 | ||||
| -rw-r--r-- | raul/TableImpl.hpp | 398 | ||||
| -rw-r--r-- | test/path_test.cpp | 2 | ||||
| -rw-r--r-- | test/table_test.cpp | 402 | ||||
| -rw-r--r-- | wscript | 2 |
7 files changed, 4 insertions, 981 deletions
diff --git a/raul/Path.hpp b/raul/Path.hpp index 05fb029..867e2e3 100644 --- a/raul/Path.hpp +++ b/raul/Path.hpp @@ -198,10 +198,7 @@ public: /** Return true iff @p child is equal to, or a descendant of @p parent. */ static inline bool descendant_comparator(const Path& parent, const Path& child) { - return (child == parent || - (child.length() > parent.length() && - (!parent.compare(0, parent.length(), child, 0, parent.length()) - && (parent.is_root() || child[parent.length()] == '/')))); + return (child == parent || child.is_child_of(parent)); } }; diff --git a/raul/PathTable.hpp b/raul/PathTable.hpp deleted file mode 100644 index 6d41ece..0000000 --- a/raul/PathTable.hpp +++ /dev/null @@ -1,54 +0,0 @@ -/* - This file is part of Raul. - Copyright 2007-2012 David 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 3 of the License, or 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 more details. - - You should have received a copy of the GNU General Public License - along with Raul. If not, see <http://www.gnu.org/licenses/>. -*/ - -#ifndef RAUL_PATH_TABLE_HPP -#define RAUL_PATH_TABLE_HPP - -#include "raul/Path.hpp" -#include "raul/Table.hpp" - -namespace Raul { - -/** Table of Paths. - * \ingroup raul - */ -template <typename T> -class PathTable : public Table<Path, T> { -public: - /** Find all descendants of a Path key in the Table. - * It is guaranteed that (parent, parent+1, parent+2, ..., ret-1) are all - * descendants of parent. The return value is never a descendent of - * parent, and may be end(). - */ - typename Table<Path, T>::iterator find_descendants_end( - typename Table<Path, T>::iterator parent) - { - return Table<Path, T>::find_range_end(parent, - &Path::descendant_comparator); - } - - typename Table<Path, T>::const_iterator find_descendants_end( - typename Table<Path, T>::const_iterator parent) const - { - return Table<Path, T>::find_range_end(parent, - &Path::descendant_comparator); - } -}; - -} // namespace Raul - -#endif // RAUL_PATH_TABLE_HPP - diff --git a/raul/Table.hpp b/raul/Table.hpp deleted file mode 100644 index 9f9e01a..0000000 --- a/raul/Table.hpp +++ /dev/null @@ -1,122 +0,0 @@ -/* - This file is part of Raul. - Copyright 2007-2012 David 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 3 of the License, or 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 more details. - - You should have received a copy of the GNU General Public License - along with Raul. If not, see <http://www.gnu.org/licenses/>. -*/ - -#ifndef RAUL_TABLE_HPP -#define RAUL_TABLE_HPP - -#include <algorithm> -#include <utility> -#include <vector> - -#include "raul/Noncopyable.hpp" -#include "raul/SharedPtr.hpp" - -//#define TABLE_SORT_DEBUG - -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 fast and sorted. Possibly also faster in some situations due to all - * data being in a single chunk of memory, cache optimized, etc. - * \ingroup raul - */ -template <typename K, typename T> -class Table : public Noncopyable { -public: - Table<K, T>() : _entries() {} - Table<K, T>(size_t capacity) : _entries(capacity) {} - - void clear() { _entries.clear(); } - bool empty() const { return _entries.empty(); } - void reserve(size_t n) { _entries.reserve(n); } - - struct const_iterator { - const_iterator(const Table<K,T>& t, size_t i) : _table(&t), _index(i) {} - inline const std::pair<const K, T> operator*() const { return _table->_entries[_index]; } - inline const std::pair<const K, T>* operator->() const { return (std::pair<const K, T>*)&_table->_entries[_index]; } - inline const_iterator& operator++() { ++_index; return *this; } - 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; } - void operator=(const const_iterator& i) { _table = i._table; _index = i._index; } - private: - friend class Table<K,T>; - const Table<K,T>* _table; - size_t _index; - }; - - struct iterator { - iterator(Table<K,T>& t, size_t i) : _table(&t), _index(i) {} - inline std::pair<K, T>& operator*() const { return (std::pair<K, T>&)_table->_entries[_index]; } - inline std::pair<K, T>* operator->() const { return (std::pair<K, T>*)&_table->_entries[_index]; } - inline iterator& operator++() { ++_index; return *this; } - 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; } - iterator& operator=(const iterator& i) { _table = i._table; _index = i._index; return *this; } - private: - friend class Table<K,T>; - Table<K,T>* _table; - size_t _index; - }; - - inline size_t size() const { return _entries.size(); } - - std::pair<iterator,bool> insert(const std::pair<K, T>& entry); - - void erase(const K& key); - void erase(iterator i); - void erase(iterator start, iterator end); - void erase_by_index(size_t start, size_t end); - - SharedPtr< Table<K, T> > yank(iterator start, iterator end); - - std::pair<iterator, bool> cram(const Table<K, T>& range); - - const_iterator find(const_iterator start, const_iterator end, const K& key) const; - const_iterator find(const K& key) const; - - iterator find(const_iterator start, const_iterator end, const K& key); - iterator find(const K& key); - - const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const; - iterator find_range_end(iterator left, bool (*comp)(const K&,const K&)); - - T& operator[](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: -#ifdef TABLE_SORT_DEBUG - bool is_sorted() const; -#endif - - friend struct iterator; - - typedef std::pair<K, T> Entry; - - std::vector<Entry> _entries; -}; - -} // namespace Raul - -#endif // RAUL_TABLE_HPP diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp deleted file mode 100644 index 9b4bb6a..0000000 --- a/raul/TableImpl.hpp +++ /dev/null @@ -1,398 +0,0 @@ -/* - This file is part of Raul. - Copyright 2007-2012 David 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 3 of the License, or 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 more details. - - You should have received a copy of the GNU General Public License - along with Raul. If not, see <http://www.gnu.org/licenses/>. -*/ - -#ifndef RAUL_TABLE_IMPL_HPP -#define RAUL_TABLE_IMPL_HPP - -#include <algorithm> -#include <cassert> -#include <stdexcept> -#include <utility> -#include <vector> - -#include "raul/Table.hpp" - -namespace Raul { - -/* FIXME: This could be a lot less code... */ - -#ifdef TABLE_SORT_DEBUG -template <typename K, typename T> -bool -Table<K,T>::is_sorted() const -{ - if (size() <= 1) - return true; - - K prev_key = _entries[0].first; - - for (size_t i=1; i < size(); ++i) - if (_entries[i].first < prev_key) - return false; - else - prev_key = _entries[i].first; - - return true; -} -#endif - -/** Binary search (O(log(n))) */ -template <typename K, typename T> -typename Table<K,T>::const_iterator -Table<K,T>::find(const K& key) const -{ - return ((Table<K,T>*)this)->find(key); -} - -/** Binary search (O(log(n))) */ -template <typename K, typename T> -typename Table<K,T>::iterator -Table<K,T>::find(const K& key) -{ - return find(begin(), end(), key); -} - -/** Binary search (O(log(end - start))) */ -template <typename K, typename T> -typename Table<K,T>::const_iterator -Table<K,T>::find(const_iterator start, const_iterator finish, const K& key) const -{ - return ((Table<K,T>*)this)->find(start, finish, key); -} - -/** Binary search (O(log(end - start))) */ -template <typename K, typename T> -typename Table<K,T>::iterator -Table<K,T>::find(const_iterator start, const_iterator finish, const K& key) -{ - if (size() == 0) - return end(); - - size_t lower = start._index; - size_t upper = finish._index - 1; - size_t i; - - while (upper >= lower) { - i = lower + ((upper - lower) / 2); - const Entry& elem = _entries[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(); -} - -/** Find the end of a range using a custom comparator. - * Two entries a, b are considered in the range if comp(a, b) returns true. - * - * Returns an iterator exactly one entry past the end of the range (possibly end()). - * - * WARNING: The restrictions on \a comparator are very strict: ALL items - * considered equal by \a comparator must be stored in the Table consecutively - * i.e. there are no 3 values a, b, c S.T. comp(a) && ! comp(b) && comp(c). - * - * This is useful for very quickly finding all children of a Path, which - * obey the above rule with lexicographical order. - */ -template <typename K, typename T> -typename Table<K,T>::const_iterator -Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)) const -{ - return (const_cast<Table<K, T>&>(*this)).find_range_end(*((iterator*)&start), comp); -} - -/** Find the end of a range using a custom comparator. - * Two entries a, b are considered in the range if comp(a, b) returns true. - * - * Returns an iterator exactly one entry past the end of the range (possibly end()). - * - * WARNING: The restrictions on \a comparator are very strict: ALL items - * considered equal by \a comparator must be stored in the Table consecutively - * i.e. there are no 3 values a, b, c S.T. comp(a) && ! comp(b) && comp(c). - * - * This is useful for very quickly finding all children of a Path, which - * obey the above rule with lexicographical order. - */ -template <typename K, typename T> -typename Table<K,T>::iterator -Table<K,T>::find_range_end(iterator start, bool (*comp)(const K&,const K&)) -{ - if (size() == 0 || start == end()) - return this->end(); - - const K& key = start->first; - - size_t lower = start._index; - size_t upper = size() - 1; - - if (lower == upper) { - if (comp(key, _entries[lower].first)) - return iterator(*this, lower+1); - else - return this->end(); - } - - size_t i; - - while (upper > lower) { - - i = lower + ((upper - lower) / 2); - - if (upper - lower == 1) { - if (comp(key, _entries[upper].first) && upper < size()) - return iterator(*this, upper+1); - else if (lower < size()) - return iterator(*this, lower+1); - } - - const Entry& elem = _entries[i]; - - // Hit - if (comp(key, elem.first)) { - - if (i == size()-1 || !comp(key, _entries[i+1].first)) - return iterator(*this, i+1); - else - lower = i; - - // Miss - } else { - - upper = i; - - } - } - - assert(comp(start->first, _entries[lower].first)); - assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first)); - - return iterator(*this, lower+1); -} - -/** Erase and return a range of entries */ -template <typename K, typename T> -SharedPtr< Table<K, T> > -Table<K, T>::yank(iterator start, iterator end) -{ - SharedPtr< Table<K, T> > ret(new Table<K, T>(end._index - start._index)); - for (size_t i=start._index; i < end._index; ++i) - ret->_entries.at(i - start._index) = _entries[i]; - erase(start, end); - return ret; -} - -/** Cram a range of entries back in. - * Range MUST follow the same ordering guidelines as find_range_end. - * Return type is the same as insert, iterator points to first inserted entry */ -template <typename K, typename T> -std::pair<typename Table<K,T>::iterator, bool> -Table<K, T>::cram(const Table<K,T>& range) -{ - /* FIXME: _way_ too slow */ - - const size_t orig_size = size(); - - if (range.size() == 0) - return std::make_pair(end(), false); - - std::pair<iterator, bool> ret = insert(range._entries.front()); - if (range.size() == 1) - return ret; - - const size_t insert_index = ret.first._index; - - std::vector<Entry> new_entries(orig_size + range.size()); - - for (size_t i=0; i <= insert_index; ++i) - new_entries.at(i) = _entries.at(i); - - for (size_t i=0; i < size() - insert_index; ++i) - new_entries.at(new_entries.size() - 1 - i) = _entries.at(size() - 1 - i); - - for (size_t i=1; i < range.size(); ++i) - new_entries.at(insert_index + i) = range._entries.at(i); - - _entries = new_entries; - - assert(size() == orig_size + range.size()); -#ifdef TABLE_SORT_DEBUG - assert(is_sorted()); -#endif - - return std::make_pair(iterator(*this, insert_index), true); -} - -/** Add an item to the table, using \a entry.first as the search key. - * An iterator to the element where value was set is returned, and a bool which - * is true if an insertion took place, or false if an existing entry was updated. - * Matches std::map::insert interface. - * O(n) worst case - * O(log(n)) best case (capacity is large enough) - */ -template <typename K, typename T> -std::pair<typename Table<K,T>::iterator, bool> -Table<K,T>::insert(const std::pair<K, T>& entry) -{ - const K& key = entry.first; - const T& value = entry.second; - - if (size() == 0 || (size() == 1 && _entries[0].first < key)) { - _entries.push_back(entry); - return std::make_pair(iterator(*this, size()-1), true); - } else if (size() == 1) { - _entries.push_back(_entries[0]); - _entries[0] = entry; - return std::make_pair(begin(), true); - } - - 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(_entries[lower].first <= _entries[i].first); - assert(_entries[i].first <= _entries[upper].first); - - assert(i < size()); - Entry& elem = _entries[i]; - - if (elem.first == key) { - elem.second = value; - return std::make_pair(iterator(*this, i), false); - } else if (key < elem.first) { - if (i == 0 || _entries[i-1].first < key) - break; - upper = i - 1; - } else { - lower = i + 1; - } - } - - // Lil' off by one touchup :) - if (i < size() && _entries[i].first <= key) - ++i; - - _entries.push_back(_entries.back()); - - // Shift everything beyond i right - for (size_t j = size()-2; j > i; --j) - _entries[j] = _entries[j-1]; - - _entries[i] = entry; - -#ifdef TABLE_SORT_DEBUG - assert(is_sorted()); -#endif - - return std::make_pair(iterator(*this, i), true); -} - -/** Insert an item, and return a reference to it's value. - * - * This may be used to insert values with pretty syntax: - * - * table["gorilla"] = "killa"; - * - * T must have a default constructor for this to be possible. - */ -template <typename K, typename T> -T& -Table<K, T>::operator[](const K& key) -{ - iterator i = find(key); - if (i != end()) { - return i->second; - } else { - std::pair<iterator,bool> ret = insert(std::make_pair(key, T())); - return ret.first->second; - } -} - -template <typename K, typename T> -void -Table<K,T>::erase(const K& key) -{ - erase(find(key)); -} - -template <typename K, typename T> -void -Table<K,T>::erase(iterator i) -{ - if (i == end()) - return; - - const size_t index = i._index; - - // Shift left - for (size_t j=index; j < size()-1; ++j) - _entries[j] = _entries[j+1]; - - _entries.pop_back(); - -#ifdef TABLE_SORT_DEBUG - assert(is_sorted()); -#endif -} - -/** Erase a range of elements from \a first to \a last, including first but - * not including last. - */ -template <typename K, typename T> -void -Table<K,T>::erase(iterator first, iterator last) -{ - const size_t first_index = first._index; - const size_t last_index = last._index; - - Table<K,T>::erase_by_index(first_index, last_index); -} - -/** Erase a range of elements from \a first_index to \a last_index, including - * first_index but not including last_index. - */ -template <typename K, typename T> -void -Table<K,T>::erase_by_index(size_t first_index, size_t last_index) -{ - const size_t num_removed = last_index - first_index; - - // Shift left - for (size_t j=first_index; j < size() - num_removed; ++j) - _entries[j] = _entries[j + num_removed]; - - _entries.resize(size() - num_removed); - -#ifdef TABLE_SORT_DEBUG - assert(is_sorted()); -#endif -} - -} // namespace Raul - -#endif // RAUL_TABLE_IMLP_HPP - diff --git a/test/path_test.cpp b/test/path_test.cpp index 1bdd99e..d9d2b57 100644 --- a/test/path_test.cpp +++ b/test/path_test.cpp @@ -39,6 +39,7 @@ main() CHECK(Path("/").is_parent_of(Path("/foo"))); CHECK(Path("/foo").is_parent_of(Path("/foo/bar"))); CHECK(!(Path("/foo").is_parent_of(Path("/foo2")))); + CHECK(!(Path("/foo").is_parent_of(Path("/foo")))); CHECK(Path::lca(Path("/foo"), Path("/foo/bar/baz")) == Path("/")); CHECK(Path::lca(Path("/foo/bar"), Path("/foo/bar/baz")) == Path("/foo")); @@ -52,6 +53,7 @@ main() CHECK(Path::is_valid("/")); CHECK(!Path::is_valid("/foo/3foo/bar")); + CHECK(Path::descendant_comparator(Path("/"), Path("/"))); CHECK(Path::descendant_comparator(Path("/"), Path("/foo"))); CHECK(Path::descendant_comparator(Path("/foo"), Path("/foo/bar"))); CHECK(Path::descendant_comparator(Path("/foo"), Path("/foo"))); diff --git a/test/table_test.cpp b/test/table_test.cpp deleted file mode 100644 index f372d7c..0000000 --- a/test/table_test.cpp +++ /dev/null @@ -1,402 +0,0 @@ -/* - This file is part of Raul. - Copyright 2007-2012 David 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 3 of the License, or 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 more details. - - You should have received a copy of the GNU General Public License - along with Raul. If not, see <http://www.gnu.org/licenses/>. -*/ - -#include <cstring> -#include <iostream> -#include <map> -#include <set> -#include <string> -#include <sys/time.h> -#include <utility> - -#include "raul/log.hpp" -#include "raul/PathTable.hpp" -#include "raul/Table.hpp" -#include "raul/TableImpl.hpp" - -//#define WITH_TR1 1 - -#ifdef WITH_TR1 - #define BOOST_MULTI_INDEX_DISABLE_SERIALIZATION 1 - #include <boost/functional/hash.hpp> - #include <tr1/unordered_map> -#endif - -using namespace Raul; -using namespace std; - -int range_end_val; - -static bool -range_comparator(const int& a, const int& b) -{ - bool ret = (b >= a && b <= range_end_val); - //cout << "COMP: " << a << " . " << b << " = " << ret << endl; - return ret; -} - -static void benchmark(size_t n); - -int -main(int argc, char** argv) -{ - #define CHECK(cond) \ - do { if (!(cond)) { \ - error << "Test failed: " << (cond) << endl; \ - return 1; \ - } } while (0) - - if (argc == 3 && !strcmp(argv[1], "-b")) { - benchmark(atoi(argv[2])); - return 0; - } - - cout << "run with -b num_elems to benchmark" << endl; - srand(time(NULL)); - - range_end_val = rand()%10; - - Table<int, int> t; - for (size_t i=0; i < 20; ++i) { - int val = rand()%10; - t.insert(make_pair(val, val)); - } - - t[20] = 20; - t[21] = 21; - - cout << "Contents:" << endl; - for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) - cout << i->first << " "; - cout << endl; - - std::cout << "Range " << t.begin()->first << " .. " << range_end_val << std::endl; - - Table<int,int>::const_iterator range_begin = t.begin(); - ++range_begin; ++range_begin; - - Table<int,int>::iterator range_end = t.find_range_end(t.begin(), range_comparator); - - for (Table<int,int>::const_iterator i = t.begin(); i != range_end; ++i) - cout << i->first << " "; - cout << endl; - - Table<int, int>::iterator first = t.begin(); - ++first; - Table<int, int>::iterator last = first; - ++last; ++last; ++last; - - cout << "Erasing elements 1..3:" << endl; - t.erase(first, last); - - for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) - cout << i->first << " "; - cout << endl; - - cout << "Erasing elements 0..3" << endl; - first = t.begin(); - last = first; - ++last; ++last; ++last; - t.erase(first, last); - - for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) - cout << i->first << " "; - cout << endl; - - cout << "Erasing elements end()-2..end()" << endl; - last = t.end(); - first = last; - --first; --first; - t.erase(first, last); - - for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) - cout << i->first << " "; - cout << endl; - - cout << "Erasing everything" << endl; - first = t.begin(); - last = t.end(); - t.erase(first, last); - - for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) - cout << i->first << " "; - cout << endl; - - /* **** */ - - PathTable<char> pt; - pt.insert(make_pair("/foo", 'a')); - pt.insert(make_pair("/bar", 'a')); - pt.insert(make_pair("/bar/baz", 'b')); - pt.insert(make_pair("/bar/bazz/ME", 'c')); - pt.insert(make_pair("/bar/baz/YOU", 'c')); - pt.insert(make_pair("/bar/baz/US", 'c')); - pt.insert(make_pair("/bar/buzz", 'b')); - pt.insert(make_pair("/bar/buzz/THEM", 'c')); - pt.insert(make_pair("/bar/buzz/ONE", 'c')); - pt.insert(make_pair("/quux", 'a')); - - cout << "Paths: " << endl; - for (PathTable<char>::const_iterator i = pt.begin(); i != pt.end(); ++i) - cout << i->first << " "; - cout << endl; - - PathTable<char>::const_iterator descendants_begin = pt.begin(); - size_t begin_index = rand() % pt.size(); - for (size_t i=0; i < begin_index; ++i) - ++descendants_begin; - - cout << "\nDescendants of " << descendants_begin->first << endl; - PathTable<char>::const_iterator descendants_end = - pt.find_descendants_end(descendants_begin); - for (PathTable<char>::const_iterator i = descendants_begin; - i != descendants_end; ++i) { - cout << i->first << " "; - CHECK(Path::descendant_comparator(descendants_begin->first, i->first)); - } - cout << endl << endl; - - const Path yank_path("/bar"); - PathTable<char>::iterator quux = pt.find(yank_path); - assert(quux != pt.end()); - PathTable<char>::iterator quux_end = pt.find_descendants_end(quux ); - assert(quux_end != quux); - - SharedPtr< Table<Path,char> > yanked = pt.yank(quux, quux_end); - - cout << "Yanked " << yank_path << endl; - for (PathTable<char>::const_iterator i = pt.begin(); i != pt.end(); ++i) - cout << i->first << " "; - cout << endl; - - pt.cram(*yanked.get()); - - cout << "Crammed " << yank_path << endl; - for (PathTable<char>::const_iterator i = pt.begin(); i != pt.end(); ++i) - cout << i->first << " "; - cout << endl; - - /* **** */ - - Table<string, string> st; - - st.insert(make_pair("apple", "core")); - st.insert(make_pair("candy", "cane")); - st.insert(make_pair("banana", "peel")); - //st["alpha"] = "zero"; - //st["zeta"] = "one"; - - st.erase("banana"); - - for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) - cout << i->first << " "; - cout << endl; - - for (int i = 0; i < 500; ++i) { - Table<int, int> t; - - size_t table_size = (rand() % 500) + 1; - - for (size_t i = 0; i < table_size; ++i) { - int val = rand()%100; - t.insert(make_pair(val, ((val + 3) * 17))); - } - - for (size_t i = 0; i < table_size; ++i) { - int val = rand()%100; - Table<int, int>::iterator iter = t.find(val); - assert(iter == t.end() || iter->second == (val + 3) * 17); - } - - /*cout << "CONTENTS:" << endl; - - for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) { - cout << i->first << ": " << i->second << endl; - } - - Table<int,int>::iterator i = t.find(7); - if (i != t.end()) - cout << "Find: 7: " << i->second << endl;*/ - } - - return 0; -} - -static string -random_string() -{ - string ret(60, 'A' + (rand() % 26)); - return ret; -} - -static void -benchmark(size_t n) -{ - cout << "Benchmarking with n = " << n << endl; - - int useless_accumulator = 0; - - srand(time(NULL)); - - vector<string> values(n); - for (size_t i=0; i < n; ++i) - values.push_back(random_string()); - - timeval t1; - t1.tv_sec=0; - t1.tv_usec=0; - - timeval t2; - t2.tv_sec=0; - t2.tv_usec=0; - - /** std::map **/ - - std::map<string,int> m; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - m.insert(make_pair(values[i], i)); - - gettimeofday(&t2, NULL); - - float delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "std::map time to insert " << n << " values: \t" << delta_t << endl; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - useless_accumulator += m.find(values[i])->second; - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "std::map time to lookup " << n << " values: \t" << delta_t << endl; - - /** std::set **/ - - std::set<std::string> s; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - s.insert(values[i]); - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "std::set time to insert " << n << " values: \t" << delta_t << endl; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - useless_accumulator += static_cast<int>((*s.find(values[i]))[0]); - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "std::set time to lookup " << n << " values: \t" << delta_t << endl; - - /** sorted std::vector **/ - - /*std::vector<int> v; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - v.push_back(values[i]); - - sort(v.begin(), v.end()); - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "std::vector (sorted) time to insert " << n << " values: \t" << delta_t << endl; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - useless_accumulator += *lower_bound(v.begin(), v.end(), values[i]); - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "std::vector (sorted) time to lookup " << n << " values: \t" << delta_t << endl;*/ - - /** Raul::Table **/ - - Raul::Table<string,int> t(n); - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - t.insert(make_pair(values[i], i)); - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "Raul::Table time to insert " << n << " values: " << delta_t << endl; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - useless_accumulator += t.find(values[i])->second; - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "Raul::Table time to lookup " << n << " values: \t" << delta_t << endl; - -#ifdef WITH_TR1 - /** boost::hash && std::unordered_map **/ - - tr1::unordered_map<string, int, boost::hash<string> > um; - - gettimeofday(&t1, NULL); - - um.rehash(n); - - for (size_t i=0; i < n; ++i) - um.insert(make_pair(values[i], i)); - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "tr1::unordered_map + boost::hash time to insert " << n << " values: \t" << delta_t << endl; - - gettimeofday(&t1, NULL); - - for (size_t i=0; i < n; ++i) - useless_accumulator += um.find(values[i])->second; - - gettimeofday(&t2, NULL); - - delta_t = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) * 0.000001f; - - cout << "tr1::unordered_map + boost::hash time to lookup " << n << " values: \t" << delta_t << endl; -#endif -} - @@ -84,6 +84,7 @@ def configure(conf): tests = ''' test/atom_test test/atomic_test + test/double_buffer_test test/list_test test/path_test test/ptr_test @@ -91,7 +92,6 @@ tests = ''' test/ringbuffer_test test/sem_test test/symbol_test - test/table_test test/thread_test test/time_test test/uri_test |