diff options
4 files changed, 57 insertions, 64 deletions
diff --git a/config/src/tests/file_subscription/my.cfg b/config/src/tests/file_subscription/my.cfg index 6172609bdff..4b0bbd13c83 100644 --- a/config/src/tests/file_subscription/my.cfg +++ b/config/src/tests/file_subscription/my.cfg @@ -1 +1 @@ -myField "foobar" +myField "bar" diff --git a/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp b/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp index fe57de093dd..dfa21e12137 100644 --- a/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp +++ b/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp @@ -122,7 +122,7 @@ lrucache_map<P>::erase(const K & key) { } else { _tail = v._prev; } - HashTable::erase(*this, it); + HashTable::erase(*this, HashTable::hash(key), it); } } @@ -202,7 +202,7 @@ lrucache_map<P>::removeOld() { { _tail = last->second._prev; HashTable::getByInternalIndex(_tail).second._next = LinkedValueBase::npos; - HashTable::erase(*this, HashTable::find(last->first)); + HashTable::erase(*this, HashTable::hash(last->first), HashTable::find(last->first)); } } } diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.h b/vespalib/src/vespa/vespalib/stllike/hashtable.h index 263ee952c2e..55db2f6d384 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.h +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.h @@ -141,19 +141,18 @@ public: typedef Value* pointer; typedef std::forward_iterator_tag iterator_category; - iterator(hashtable * hash, next_t start) : _hash(start), _subNode(start), _hashTable(hash) { - advanceToNextValidHash(); - } - iterator(hashtable * hash, next_t start, next_t subNode) : _hash(start), _subNode(subNode), _hashTable(hash) { } - Value & operator * () const { return _hashTable->get(_subNode); } - Value * operator -> () const { return & _hashTable->get(_subNode); } - iterator & operator ++ () { - if (_hashTable->_nodes[_subNode].hasNext()) { - _subNode = _hashTable->_nodes[_subNode].getNext(); - } else { - _hash++; + iterator(hashtable * hash) : _current(0), _hashTable(hash) { + if ((_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid()) { advanceToNextValidHash(); } + } + iterator(hashtable * hash, next_t pos) : _current(pos), _hashTable(hash) { } + static iterator end(hashtable *hash) { return iterator(hash, Node::npos); } + + Value & operator * () const { return _hashTable->get(_current); } + Value * operator -> () const { return & _hashTable->get(_current); } + iterator & operator ++ () { + advanceToNextValidHash(); return *this; } iterator operator ++ (int) { @@ -161,19 +160,19 @@ public: ++(*this); return prev; } - bool operator==(const iterator& rhs) const { return (_subNode == rhs._subNode); } - bool operator!=(const iterator& rhs) const { return (_subNode != rhs._subNode); } + bool operator==(const iterator& rhs) const { return (_current == rhs._current); } + bool operator!=(const iterator& rhs) const { return (_current != rhs._current); } /// Carefull about this one. Only used by lrucache. - next_t getInternalIndex() const { return _subNode; } - void setInternalIndex(next_t n) { _subNode = n; } - next_t getHash() const { return _hash; } + next_t getInternalIndex() const { return _current; } + void setInternalIndex(next_t n) { _current = n; } private: void advanceToNextValidHash() { - for (;(_hash < _hashTable->getTableSize()) && ! _hashTable->_nodes[_hash].valid(); _hash++) { } - _subNode = (_hash < _hashTable->getTableSize()) ? _hash : Node::npos; + for (_current++;(_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid(); _current++) { } + if (_current >= _hashTable->initializedSize()) { + _current = Node::npos; + } } - next_t _hash; - next_t _subNode; + next_t _current; hashtable * _hashTable; friend class hashtable::const_iterator; @@ -186,21 +185,19 @@ public: typedef const Value* pointer; typedef std::forward_iterator_tag iterator_category; - const_iterator(const hashtable * hash, next_t start) : _hash(start), _subNode(start), _hashTable(hash) { - advanceToNextValidHash(); - } - const_iterator(const hashtable * hash, next_t start, next_t subNode) : _hash(start), _subNode(subNode), _hashTable(hash) { } - const_iterator(const iterator &i) - : _hash(i._hash), _subNode(i._subNode), _hashTable(i._hashTable) {} - const Value & operator * () const { return _hashTable->get(_subNode); } - const Value * operator -> () const { return & _hashTable->get(_subNode); } - const_iterator & operator ++ () { - if (_hashTable->_nodes[_subNode].hasNext()) { - _subNode = _hashTable->_nodes[_subNode].getNext(); - } else { - _hash++; + const_iterator(const hashtable * hash) : _current(0), _hashTable(hash) { + if ((_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid()) { advanceToNextValidHash(); } + } + const_iterator(const hashtable * hash, next_t pos) : _current(pos), _hashTable(hash) { } + const_iterator(const iterator &i) : _current(i._current), _hashTable(i._hashTable) {} + static const_iterator end(const hashtable *hash) { return const_iterator(hash, Node::npos); } + + const Value & operator * () const { return _hashTable->get(_current); } + const Value * operator -> () const { return & _hashTable->get(_current); } + const_iterator & operator ++ () { + advanceToNextValidHash(); return *this; } const_iterator operator ++ (int) { @@ -208,17 +205,17 @@ public: ++(*this); return prev; } - bool operator==(const const_iterator& rhs) const { return (_subNode == rhs._subNode); } - bool operator!=(const const_iterator& rhs) const { return (_subNode != rhs._subNode); } - next_t getInternalIndex() const { return _subNode; } - next_t getHash() const { return _hash; } + bool operator==(const const_iterator& rhs) const { return (_current == rhs._current); } + bool operator!=(const const_iterator& rhs) const { return (_current != rhs._current); } + next_t getInternalIndex() const { return _current; } private: void advanceToNextValidHash() { - for (;(_hash < _hashTable->getTableSize()) && ! _hashTable->_nodes[_hash].valid(); _hash++) { } - _subNode = (_hash < _hashTable->getTableSize()) ? _hash : Node::npos; + for (_current++;(_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid(); _current++) { } + if (_current >= _hashTable->initializedSize()) { + _current = Node::npos; + } } - next_t _hash; - next_t _subNode; + next_t _current; const hashtable * _hashTable; }; typedef std::pair<iterator, bool> insert_result; @@ -231,10 +228,10 @@ public: hashtable(size_t reservedSpace); hashtable(size_t reservedSpace, const Hash & hasher, const Equal & equal); virtual ~hashtable(); - iterator begin() { return iterator(this, 0); } - iterator end() { return iterator(this, Node::npos); } - const_iterator begin() const { return const_iterator(this, 0); } - const_iterator end() const { return const_iterator(this, Node::npos); } + iterator begin() { return iterator(this); } + iterator end() { return iterator::end(this); } + const_iterator begin() const { return const_iterator(this); } + const_iterator end() const { return const_iterator::end(this); } size_t capacity() const { return _nodes.capacity(); } size_t size() const { return _count; } bool empty() const { return _count == 0; } @@ -280,7 +277,8 @@ protected: Value & getByInternalIndex(size_t index) { return _nodes[index].getValue(); } const Value & getByInternalIndex(size_t index) const { return _nodes[index].getValue(); } template <typename MoveHandler> - void erase(MoveHandler & moveHandler, const const_iterator & key); + void erase(MoveHandler & moveHandler, next_t h, const const_iterator & key); + next_t hash(const Key & key) const { return modulator(_hasher(key)); } private: Modulator _modulator; size_t _count; @@ -292,7 +290,7 @@ private: const Value & get(size_t index) const { return _nodes[index].getValue(); } next_t modulator(next_t key) const { return _modulator.modulo(key); } next_t getTableSize() const { return _modulator.getTableSize(); } - next_t hash(const Key & key) const { return modulator(_hasher(key)); } + size_t initializedSize() const { return _nodes.size(); } template <typename MoveHandler> void move(MoveHandler & moveHandler, next_t from, next_t to) { _nodes[to] = std::move(_nodes[from]); diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp index 359e71aa0d2..ada3f455017 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp @@ -68,10 +68,9 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const Key & key) { next_t h = hash(key); if (_nodes[h].valid()) { - next_t start(h); do { if (_equal(_keyExtractor(_nodes[h].getValue()), key)) { - return iterator(this, start, h); + return iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -85,10 +84,9 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const Key & key) { next_t h = hash(key); if (_nodes[h].valid()) { - next_t start(h); do { if (_equal(_keyExtractor(_nodes[h].getValue()), key)) { - return const_iterator(this, start, h); + return const_iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -104,11 +102,10 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const AltKey & k AltHash altHasher; next_t h = modulator(altHasher(key)); if (_nodes[h].valid()) { - next_t start(h); AltEqual altEqual; do { if (altEqual(altExtract(_keyExtractor(_nodes[h].getValue())), key)) { - return const_iterator(this, start, h); + return const_iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -124,11 +121,10 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const AltKey & k AltHash altHasher; next_t h = modulator(altHasher(key)); if (_nodes[h].valid()) { - next_t start(h); AltEqual altEqual; do { if (altEqual(altExtract(_keyExtractor(_nodes[h].getValue())), key)) { - return iterator(this, start, h); + return iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -149,7 +145,7 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::erase(const Key & key const_iterator found(find(key)); if (found != end()) { DefaultMoveHandler moveHandler; - erase(moveHandler, found); + erase(moveHandler, hash(key), found); } } @@ -169,11 +165,11 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insertInternal(V && n if ( ! _nodes[h].valid() ) { _nodes[h] = std::forward<V>(node); _count++; - return insert_result(iterator(this, h, h), true); + return insert_result(iterator(this, h), true); } else if (_nodes.size() <= _nodes.capacity()) { for (next_t c(h); c != Node::npos; c = _nodes[c].getNext()) { if (_equal(_keyExtractor(_nodes[c].getValue()), _keyExtractor(node))) { - return insert_result(iterator(this, h, c), false); + return insert_result(iterator(this, c), false); } } if (_nodes.size() < _nodes.capacity()) { @@ -182,7 +178,7 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insertInternal(V && n _nodes[h].setNext(newIdx); new (_nodes.push_back_fast()) Node(std::forward<V>(node), p); _count++; - return insert_result(iterator(this, h, newIdx), true); + return insert_result(iterator(this, newIdx), true); } else { resize(_nodes.capacity()*2); return insertInternal(std::forward<V>(node)); @@ -214,9 +210,8 @@ void hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::reclaim(MoveHand template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > template <typename MoveHandler> void -hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::erase(MoveHandler & moveHandler, const const_iterator & it) +hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::erase(MoveHandler & moveHandler, next_t h, const const_iterator & it) { - next_t h = it.getHash(); next_t prev = Node::npos; do { if (h == it.getInternalIndex()) { |