From ca1c84d3d3df15ed62588c77bbbae537a83c016f Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 26 Jul 2007 07:36:20 +0000 Subject: Use C++ey memory via std::vector instead of malloc and friends for Table, since containing std::string etc. was dying horribly. Fixed semantics of erase range method to match std::vector. Fix valgrind errors. git-svn-id: http://svn.drobilla.net/lad/raul@630 a436a847-0d15-0410-975c-d299462d15a1 --- raul/TableImpl.hpp | 119 +++++++++++++++++++++++++++++++++-------------------- 1 file changed, 75 insertions(+), 44 deletions(-) (limited to 'raul/TableImpl.hpp') diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp index bac948e..ab79b7f 100644 --- a/raul/TableImpl.hpp +++ b/raul/TableImpl.hpp @@ -28,16 +28,16 @@ template bool Table::is_sorted() const { - if (_size <= 1) + if (size() <= 1) return true; - K prev_key = _array[0].first; + K prev_key = _entries[0].first; - for (size_t i=1; i < _size; ++i) - if (_array[i].first < prev_key) + for (size_t i=1; i < size(); ++i) + if (_entries[i].first < prev_key) return false; else - prev_key = _array[i].first; + prev_key = _entries[i].first; return true; } @@ -49,20 +49,20 @@ template typename Table::iterator Table::find(const K& key) { - if (_size == 0) + if (size() == 0) return end(); size_t lower = 0; - size_t upper = _size - 1; + size_t upper = size() - 1; size_t i; while (upper >= lower) { i = lower + ((upper - lower) / 2); - Entry& elem = _array[i]; + const Entry& elem = _entries[i]; if (elem.first == key) return iterator(*this, i); - else if (i < _size-1 && elem.first < key) + else if (i < size()-1 && elem.first < key) lower = i + 1; else if (i > 0) upper = i - 1; @@ -76,28 +76,19 @@ Table::find(const K& key) template void -Table::insert(K key, T value) +Table::insert(const K& key, const T& value) { - Entry new_entry = make_pair(key, value); - - if (_size == 0) { - _array = (std::pair*)malloc(sizeof(Entry) * 2); - _array[0] = new_entry; - ++_size; + if (size() == 0 || size() == 1 && key > _entries[0].first) { + _entries.push_back(make_pair(key, value)); return; - } else if (_size == 1) { - if (key > _array[0].first) { - _array[1] = new_entry; - } else { - _array[1] = _array[0]; - _array[0] = new_entry; - } - ++_size; + } else if (size() == 1) { + _entries.push_back(_entries[0]); + _entries[0] = make_pair(key, value); return; } size_t lower = 0; - size_t upper = _size - 1; + size_t upper = size() - 1; size_t i; // Find the earliest element > key @@ -105,16 +96,16 @@ Table::insert(K key, T value) 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(_entries[lower].first <= _entries[i].first); + assert(_entries[i].first <= _entries[upper].first); - assert(i < _size); - Entry& elem = _array[i]; + assert(i < size()); + Entry& elem = _entries[i]; if (elem.first == key) { break; } else if (elem.first > key) { - if (i == 0 || _array[i-1].first < key) + if (i == 0 || _entries[i-1].first < key) break; upper = i - 1; } else { @@ -123,41 +114,81 @@ Table::insert(K key, T value) } // Lil' off by one touchup :) - if (i < _size && _array[i].first <= key) + if (i < size() && _entries[i].first <= key) ++i; - _array = (Entry*)realloc(_array, (_size + 1) * sizeof(Entry)); + _entries.resize(size() + 1); + + // Shift everything beyond i right + for (size_t j = size()-1; j > i; --j) + _entries[j] = _entries[j-1]; - // FIXME: This could be faster using memmove etc... - for (size_t j=_size; j > i; --j) - _array[j] = _array[j-1]; + _entries[i] = make_pair(key, value); + + assert(is_sorted()); +} + + +template +void +Table::erase(const K& key) +{ + erase(find(key)); +} + - _array[i] = new_entry; +template +void +Table::erase(iterator i) +{ + if (i == end()) + return; - ++_size; + 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(); + +#ifndef NDEBUG assert(is_sorted()); +#endif } +/** Erase a range of elements from \a first to \a last, including first but + * not including last. + */ template void -Table::remove(K& key) +Table::erase(iterator first, iterator last) { - iterator i = find(key); - if (i != _array.end()) - remove(i); + const size_t first_index = first._index; + const size_t last_index = last._index; + + erase(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 void -Table::remove(iterator i) +Table::erase(size_t first_index, size_t last_index) { - _array.erase(i); + 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); #ifndef NDEBUG - assert(_array.is_sorted()); + assert(is_sorted()); #endif } -- cgit v1.2.1