From 2a85dc3fd5af5c33601cf04ead06c7545fa46d75 Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 14 Dec 2016 22:58:54 +0100 Subject: Split in hash_xxx, array, lru, cache ++ in hpp files. To reduce clinon build --- .../src/vespa/vespalib/data/memorydatastore.cpp | 1 + .../vespa/vespalib/data/slime/binary_format.cpp | 1 + .../src/vespa/vespalib/data/slime/symbol_table.cpp | 21 ++ .../src/vespa/vespalib/data/slime/symbol_table.h | 23 +- .../src/vespa/vespalib/eval/llvm/llvm_wrapper.cpp | 1 - vespalib/src/vespa/vespalib/stllike/CMakeLists.txt | 3 + vespalib/src/vespa/vespalib/stllike/hash_map.cpp | 16 ++ vespalib/src/vespa/vespalib/stllike/hash_map.h | 54 ++-- vespalib/src/vespa/vespalib/stllike/hash_map.hpp | 90 +++++++ vespalib/src/vespa/vespalib/stllike/hash_set.cpp | 14 + vespalib/src/vespa/vespalib/stllike/hash_set.h | 57 ++-- vespalib/src/vespa/vespalib/stllike/hash_set.hpp | 106 ++++++++ vespalib/src/vespa/vespalib/stllike/hashtable.cpp | 2 +- vespalib/src/vespa/vespalib/stllike/hashtable.h | 265 +------------------ vespalib/src/vespa/vespalib/stllike/hashtable.hpp | 289 +++++++++++++++++++++ .../vespalib/tensor/dense/dense_tensor_builder.cpp | 4 +- .../tensor/dense/dense_tensor_cells_iterator.h | 1 + .../vespa/vespalib/tensor/sparse/sparse_tensor.cpp | 5 +- .../vespa/vespalib/tensor/sparse/sparse_tensor.h | 2 +- .../sparse/sparse_tensor_address_reducer.cpp | 2 +- .../tensor/sparse/sparse_tensor_builder.cpp | 1 + .../vespalib/tensor/sparse/sparse_tensor_match.cpp | 2 +- .../src/vespa/vespalib/tensor/tensor_apply.cpp | 2 +- .../src/vespa/vespalib/tensor/tensor_mapper.cpp | 3 +- vespalib/src/vespa/vespalib/tensor/types.h | 1 - vespalib/src/vespa/vespalib/util/CMakeLists.txt | 1 + vespalib/src/vespa/vespalib/util/array.cpp | 18 ++ vespalib/src/vespa/vespalib/util/array.h | 249 +----------------- vespalib/src/vespa/vespalib/util/array.hpp | 208 +++++++++++++++ vespalib/src/vespa/vespalib/util/arrayref.h | 47 ++++ .../src/vespa/vespalib/util/generationholder.h | 4 +- vespalib/src/vespa/vespalib/util/stash.h | 3 +- 32 files changed, 889 insertions(+), 607 deletions(-) create mode 100644 vespalib/src/vespa/vespalib/stllike/hash_map.cpp create mode 100644 vespalib/src/vespa/vespalib/stllike/hash_map.hpp create mode 100644 vespalib/src/vespa/vespalib/stllike/hash_set.cpp create mode 100644 vespalib/src/vespa/vespalib/stllike/hash_set.hpp create mode 100644 vespalib/src/vespa/vespalib/stllike/hashtable.hpp create mode 100644 vespalib/src/vespa/vespalib/util/array.cpp create mode 100644 vespalib/src/vespa/vespalib/util/array.hpp create mode 100644 vespalib/src/vespa/vespalib/util/arrayref.h (limited to 'vespalib') diff --git a/vespalib/src/vespa/vespalib/data/memorydatastore.cpp b/vespalib/src/vespa/vespalib/data/memorydatastore.cpp index 824a8adf1d6..73b0d559a15 100644 --- a/vespalib/src/vespa/vespalib/data/memorydatastore.cpp +++ b/vespalib/src/vespa/vespalib/data/memorydatastore.cpp @@ -1,5 +1,6 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #include +#include namespace vespalib { diff --git a/vespalib/src/vespa/vespalib/data/slime/binary_format.cpp b/vespalib/src/vespa/vespalib/data/slime/binary_format.cpp index d3026211c61..be2089b4076 100644 --- a/vespalib/src/vespa/vespalib/data/slime/binary_format.cpp +++ b/vespalib/src/vespa/vespalib/data/slime/binary_format.cpp @@ -3,6 +3,7 @@ #include "binary_format.h" #include "inserter.h" #include "slime.h" +#include namespace vespalib { namespace slime { diff --git a/vespalib/src/vespa/vespalib/data/slime/symbol_table.cpp b/vespalib/src/vespa/vespalib/data/slime/symbol_table.cpp index 57b0b2e843a..fe1d0a1a78b 100644 --- a/vespalib/src/vespa/vespalib/data/slime/symbol_table.cpp +++ b/vespalib/src/vespa/vespalib/data/slime/symbol_table.cpp @@ -1,6 +1,7 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #include "symbol_table.h" +#include namespace vespalib { namespace slime { @@ -18,5 +19,25 @@ SymbolTable::clear() { _symbols.clear(); } +Symbol +SymbolTable::insert(const Memory &name) { + SymbolMap::const_iterator pos = _symbols.find(name); + if (pos == _symbols.end()) { + Symbol symbol(_names.size()); + SymbolVector::Reference r(_names.push_back(name.data, name.size)); + _symbols.insert(std::make_pair(Memory(r.c_str(), r.size()), symbol)); + return symbol; + } + return pos->second; +} +Symbol +SymbolTable::lookup(const Memory &name) const { + SymbolMap::const_iterator pos = _symbols.find(name); + if (pos == _symbols.end()) { + return Symbol(); + } + return pos->second; +} + } // namespace vespalib::slime } // namespace vespalib diff --git a/vespalib/src/vespa/vespalib/data/slime/symbol_table.h b/vespalib/src/vespa/vespalib/data/slime/symbol_table.h index 23cdbecdb5e..e4cafa2b9d6 100644 --- a/vespalib/src/vespa/vespalib/data/slime/symbol_table.h +++ b/vespalib/src/vespa/vespalib/data/slime/symbol_table.h @@ -21,8 +21,8 @@ private: return lcm.hash(); } }; - typedef hash_map SymbolMap; - typedef VariableSizeVector SymbolVector; + using SymbolMap = hash_map; + using SymbolVector = VariableSizeVector; SymbolMap _symbols; SymbolVector _names; @@ -38,23 +38,8 @@ public: SymbolVector::Reference r(_names[symbol.getValue()]); return Memory(r.c_str(), r.size()); } - Symbol insert(const Memory &name) { - SymbolMap::const_iterator pos = _symbols.find(name); - if (pos == _symbols.end()) { - Symbol symbol(_names.size()); - SymbolVector::Reference r(_names.push_back(name.data, name.size)); - _symbols.insert(std::make_pair(Memory(r.c_str(), r.size()), symbol)); - return symbol; - } - return pos->second; - } - Symbol lookup(const Memory &name) const { - SymbolMap::const_iterator pos = _symbols.find(name); - if (pos == _symbols.end()) { - return Symbol(); - } - return pos->second; - } + Symbol insert(const Memory &name); + Symbol lookup(const Memory &name) const; void clear(); }; diff --git a/vespalib/src/vespa/vespalib/eval/llvm/llvm_wrapper.cpp b/vespalib/src/vespa/vespalib/eval/llvm/llvm_wrapper.cpp index c5ceacb3a5a..1222eeae837 100644 --- a/vespalib/src/vespa/vespalib/eval/llvm/llvm_wrapper.cpp +++ b/vespalib/src/vespa/vespalib/eval/llvm/llvm_wrapper.cpp @@ -1,6 +1,5 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include #include #include "llvm_wrapper.h" #include diff --git a/vespalib/src/vespa/vespalib/stllike/CMakeLists.txt b/vespalib/src/vespa/vespalib/stllike/CMakeLists.txt index c03dc4d1703..3900c6210d4 100644 --- a/vespalib/src/vespa/vespalib/stllike/CMakeLists.txt +++ b/vespalib/src/vespa/vespalib/stllike/CMakeLists.txt @@ -3,6 +3,9 @@ vespa_add_library(vespalib_vespalib_stllike OBJECT SOURCES asciistream.cpp hashtable.cpp + hashtable.cpp + hash_set.cpp + hash_map.cpp string.cpp DEPENDS ) diff --git a/vespalib/src/vespa/vespalib/stllike/hash_map.cpp b/vespalib/src/vespa/vespalib/stllike/hash_map.cpp new file mode 100644 index 00000000000..bbc8ea17991 --- /dev/null +++ b/vespalib/src/vespa/vespalib/stllike/hash_map.cpp @@ -0,0 +1,16 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "hash_map.hpp" + +namespace vespalib { +} + +VESPALIB_HASH_MAP_INSTANTIATE(vespalib::string, vespalib::string); +VESPALIB_HASH_MAP_INSTANTIATE(vespalib::string, int32_t); +VESPALIB_HASH_MAP_INSTANTIATE(vespalib::string, uint32_t); +VESPALIB_HASH_MAP_INSTANTIATE(vespalib::string, uint64_t); +VESPALIB_HASH_MAP_INSTANTIATE(vespalib::string, double); +VESPALIB_HASH_MAP_INSTANTIATE(int64_t, int32_t); +VESPALIB_HASH_MAP_INSTANTIATE(uint32_t, uint32_t); +VESPALIB_HASH_MAP_INSTANTIATE(uint64_t, uint32_t); +VESPALIB_HASH_MAP_INSTANTIATE(double, uint32_t); \ No newline at end of file diff --git a/vespalib/src/vespa/vespalib/stllike/hash_map.h b/vespalib/src/vespa/vespalib/stllike/hash_map.h index 22f352fcd99..12c6d3574e4 100644 --- a/vespalib/src/vespa/vespalib/stllike/hash_map.h +++ b/vespalib/src/vespa/vespalib/stllike/hash_map.h @@ -1,7 +1,8 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #pragma once -#include +#include "hashtable.h" +#include "hash_fun.h" namespace vespalib { @@ -12,15 +13,20 @@ public: typedef std::pair value_type; typedef K key_type; typedef V mapped_type; + using HashTable = hashtable< K, value_type, H, EQ, std::_Select1st< value_type >, M >; private: - typedef hashtable< K, value_type, H, EQ, std::_Select1st< value_type >, M > HashTable; HashTable _ht; public: typedef typename HashTable::iterator iterator; typedef typename HashTable::const_iterator const_iterator; typedef typename HashTable::insert_result insert_result; public: - hash_map(size_t reserveSize=0) : _ht(reserveSize) { } + hash_map(hash_map &&) = default; + hash_map & operator = (hash_map &&) = default; + hash_map(const hash_map &) = default; + hash_map & operator = (const hash_map &) = default; + hash_map(size_t reserveSize=0); + ~hash_map(); iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } const_iterator begin() const { return _ht.begin(); } @@ -28,52 +34,28 @@ public: size_t capacity() const { return _ht.capacity(); } size_t size() const { return _ht.size(); } bool empty() const { return _ht.empty(); } - insert_result insert(const value_type & value) { return _ht.insert(value); } + insert_result insert(const value_type & value); template void insert(InputIt first, InputIt last); const V & operator [] (const K & key) const { return _ht.find(key)->second; } V & operator [] (const K & key) { return _ht.insert(value_type(key, V())).first->second; } - void erase(const K & key) { return _ht.erase(key); } - void erase(iterator it) { return _ht.erase(it->first); } - void erase(const_iterator it) { return _ht.erase(it->first); } + void erase(const K & key); + void erase(iterator it) { return erase(it->first); } + void erase(const_iterator it) { return erase(it->first); } iterator find(const K & key) { return _ht.find(key); } const_iterator find(const K & key) const { return _ht.find(key); } - void clear() { _ht.clear(); } - void resize(size_t newSize) { _ht.resize(newSize); } - void swap(hash_map & rhs) { _ht.swap(rhs._ht); } + void clear(); + void resize(size_t newSize); + void swap(hash_map & rhs); bool operator == (const hash_map & rhs) const; - size_t getMemoryConsumption() const { return _ht.getMemoryConsumption(); } - size_t getMemoryUsed() const { return _ht.getMemoryUsed(); } + size_t getMemoryConsumption() const; + size_t getMemoryUsed() const; }; -template -bool hash_map::operator ==(const hash_map & rhs) const { - bool identical(rhs.size() == size()); - if (identical) { - for(const_iterator at(begin()), mat(end()); identical && at != mat; at++) { - const_iterator bt = rhs.find(at->first); - identical = (bt != rhs.end()) && (*at == *bt); - } - } - return identical; -} - -template -template -void hash_map::insert(InputIt first, InputIt last) { - while (first != last) { - _ht.insert(*first); - ++first; - } -} - template< typename K, typename V, typename H, typename EQ, typename M > void swap(hash_map & a, hash_map & b) { a.swap(b); } - } - - diff --git a/vespalib/src/vespa/vespalib/stllike/hash_map.hpp b/vespalib/src/vespa/vespalib/stllike/hash_map.hpp new file mode 100644 index 00000000000..0a97a1f17f1 --- /dev/null +++ b/vespalib/src/vespa/vespalib/stllike/hash_map.hpp @@ -0,0 +1,90 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#pragma once + +#include "hash_map.h" +#include "hashtable.hpp" + +namespace vespalib { + +template +hash_map::hash_map(size_t reserveSize) : + _ht(reserveSize) +{ } + +template +hash_map::~hash_map() { } + +template +bool +hash_map::operator ==(const hash_map & rhs) const { + bool identical(rhs.size() == size()); + if (identical) { + for(const_iterator at(begin()), mat(end()); identical && at != mat; at++) { + const_iterator bt = rhs.find(at->first); + identical = (bt != rhs.end()) && (*at == *bt); + } + } + return identical; +} + +template +typename hash_map::insert_result +hash_map::insert(const value_type & value) { + return _ht.insert(value); +} + +template +void +hash_map::erase(const K & key) { + return _ht.erase(key); +} + +template +template +void +hash_map::insert(InputIt first, InputIt last) { + while (first != last) { + _ht.insert(*first); + ++first; + } +} + +template +void +hash_map::clear() { + _ht.clear(); +} + +template +void +hash_map::resize(size_t newSize) { + _ht.resize(newSize); +} + +template +void +hash_map::swap(hash_map & rhs) { + _ht.swap(rhs._ht); +} + +template +size_t +hash_map::getMemoryConsumption() const { + return _ht.getMemoryConsumption(); +} + +template +size_t +hash_map::getMemoryUsed() const +{ + return _ht.getMemoryUsed(); +} + +} + +#define VESPALIB_HASH_MAP_INSTANTIATE(K, V) \ + template class vespalib::hash_map; \ + template class vespalib::hashtable, vespalib::hash, std::equal_to, std::_Select1st>>; \ + template vespalib::hashtable, vespalib::hash, std::equal_to, std::_Select1st>>::insert_result \ + vespalib::hashtable, vespalib::hash, std::equal_to, std::_Select1st>>::insert(std::pair &&); \ + template class vespalib::Array>>; diff --git a/vespalib/src/vespa/vespalib/stllike/hash_set.cpp b/vespalib/src/vespa/vespalib/stllike/hash_set.cpp new file mode 100644 index 00000000000..ef0c0e6188e --- /dev/null +++ b/vespalib/src/vespa/vespalib/stllike/hash_set.cpp @@ -0,0 +1,14 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "hash_set.hpp" + +namespace vespalib { +} + +VESPALIB_HASH_SET_INSTANTIATE(int32_t); +VESPALIB_HASH_SET_INSTANTIATE(uint32_t); +VESPALIB_HASH_SET_INSTANTIATE(uint64_t); +VESPALIB_HASH_SET_INSTANTIATE(double); +VESPALIB_HASH_SET_INSTANTIATE(vespalib::string); +VESPALIB_HASH_SET_INSTANTIATE(std::string); +VESPALIB_HASH_SET_INSTANTIATE(const void *); \ No newline at end of file diff --git a/vespalib/src/vespa/vespalib/stllike/hash_set.h b/vespalib/src/vespa/vespalib/stllike/hash_set.h index ff7049b7784..c74a377cc18 100644 --- a/vespalib/src/vespa/vespalib/stllike/hash_set.h +++ b/vespalib/src/vespa/vespalib/stllike/hash_set.h @@ -1,7 +1,8 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #pragma once -#include +#include "hashtable.h" +#include "hash_fun.h" #include namespace vespalib { @@ -10,26 +11,24 @@ template< typename K, typename H = vespalib::hash, typename EQ = std::equal_t class hash_set { private: - typedef hashtable< K, K, H, EQ, std::_Identity, M> HashTable; + using HashTable = hashtable< K, K, H, EQ, std::_Identity, M>; HashTable _ht; public: typedef typename HashTable::iterator iterator; typedef typename HashTable::const_iterator const_iterator; typedef typename HashTable::insert_result insert_result; public: - hash_set(size_t reserveSize=0) : _ht(reserveSize) { } - hash_set(size_t reserveSize, const H & hasher, const EQ & equal) : _ht(reserveSize, hasher, equal) { } + hash_set(hash_set &&) = default; + hash_set & operator = (hash_set &&) = default; + hash_set(const hash_set &) = default; + hash_set & operator = (const hash_set &) = default; + hash_set(size_t reserveSize=0); + hash_set(size_t reserveSize, const H & hasher, const EQ & equal); template - hash_set(InputIterator first, InputIterator last) - : _ht(0) - { - insert(first, last); - } - hash_set(std::initializer_list input) - : _ht(0) - { - insert(input.begin(), input.end()); - } + hash_set(InputIterator first, InputIterator last); + + hash_set(std::initializer_list input); + ~hash_set(); iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } const_iterator begin() const { return _ht.begin(); } @@ -37,16 +36,10 @@ public: size_t capacity() const { return _ht.capacity(); } size_t size() const { return _ht.size(); } bool empty() const { return _ht.empty(); } - insert_result insert(const K & value) { return _ht.insert(value); } + insert_result insert(const K & value); template - void insert(InputIt first, InputIt last) { - _ht.resize(last-first + capacity()); - for(;first < last; first++) { - _ht.insert(*first); - } - } - void erase(const K & key) { return _ht.erase(key); } - void erase(const iterator & it) { return _ht.erase(it); } + void insert(InputIt first, InputIt last); + void erase(const K & key); iterator find(const K & key) { return _ht.find(key); } const_iterator find(const K & key) const { return _ht.find(key); } @@ -66,25 +59,17 @@ public: return _ht.template find(key, altExtract); } - void clear() { _ht.clear(); } - void resize(size_t newSize) { _ht.resize(newSize); } - void swap(hash_set & rhs) { _ht.swap(rhs._ht); } + void clear(); + void resize(size_t newSize); + void swap(hash_set & rhs); - bool operator==(const hash_set &rhs) const { - bool equal = (size() == rhs.size()); - if (equal) { - for (auto itr = begin(), endItr = end(); equal && itr != endItr; ++itr) { - equal = (rhs.find(*itr) != rhs.end()); - } - } - return equal; - } + bool operator==(const hash_set &rhs) const; /** * Get an approximate number of memory consumed by hash set. Not including * any data K would store outside of sizeof(K) of course. */ - size_t getMemoryConsumption() const { return _ht.getMemoryConsumption(); } + size_t getMemoryConsumption() const; }; template< typename K, typename H, typename EQ, typename M > diff --git a/vespalib/src/vespa/vespalib/stllike/hash_set.hpp b/vespalib/src/vespa/vespalib/stllike/hash_set.hpp new file mode 100644 index 00000000000..98c57a76358 --- /dev/null +++ b/vespalib/src/vespa/vespalib/stllike/hash_set.hpp @@ -0,0 +1,106 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#pragma once + +#include "hash_set.h" +#include "hashtable.hpp" + +namespace vespalib { + +template +hash_set::hash_set(size_t reserveSize) + : _ht(reserveSize) +{ } + +template +hash_set::hash_set(size_t reserveSize, const H &hasher, const EQ &equal) + : _ht(reserveSize, hasher, equal) +{ } + +template +template +hash_set::hash_set(InputIterator first, InputIterator last) + : _ht(0) +{ + insert(first, last); +} + +template +hash_set::hash_set(std::initializer_list input) + : _ht(0) +{ + insert(input.begin(), input.end()); +} + +template +hash_set::~hash_set() {} + +template +bool +hash_set::operator==(const hash_set &rhs) const { + bool equal = (size() == rhs.size()); + if (equal) { + for (auto itr = begin(), endItr = end(); equal && itr != endItr; ++itr) { + equal = (rhs.find(*itr) != rhs.end()); + } + } + return equal; +} + +template +void +hash_set::clear() { + _ht.clear(); +} + +template +void +hash_set::resize(size_t newSize) { + _ht.resize(newSize); +} + +template +void +hash_set::swap(hash_set &rhs) { + _ht.swap(rhs._ht); +} + +template +size_t +hash_set::getMemoryConsumption() const { + return _ht.getMemoryConsumption(); +} + +template +template +void +hash_set::insert(InputIt first, InputIt last) { + _ht.resize(last - first + capacity()); + for (; first < last; first++) { + _ht.insert(*first); + } +} + +template +void +hash_set::erase(const K &key) { + return _ht.erase(key); +} + +template +typename hash_set::insert_result +hash_set::insert(const K & value) { + return _ht.insert(value); +} + +} + +#define VESPALIB_HASH_SET_INSTANTIATE(K) \ + template class vespalib::hash_set; \ + template class vespalib::hashtable, std::equal_to, std::_Identity>; \ + template class vespalib::Array>; + +#define VESPALIB_HASH_SET_INSTANTIATE_H(K, H) \ + template class vespalib::hash_set; \ + template class vespalib::hashtable, std::_Identity>; \ + template class vespalib::Array>; + diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.cpp b/vespalib/src/vespa/vespalib/stllike/hashtable.cpp index e2da6b255af..28423e5263e 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.cpp +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.cpp @@ -1,5 +1,5 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include +#include namespace { diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.h b/vespalib/src/vespa/vespalib/stllike/hashtable.h index a1eeb289c31..ae30f04d1d1 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.h +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.h @@ -1,15 +1,9 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #pragma once -#include #include -#include -#include -#include #include -#include "hash_fun.h" - namespace vespalib { /** @@ -113,6 +107,9 @@ public: hash_node &operator=(hash_node &&) = default; hash_node(const hash_node &) = default; // These will not be created hash_node &operator=(const hash_node &) = default; // if V is non-copyable. + bool operator == (const hash_node & rhs) const { + return (_next == rhs._next) && (_node == rhs._node); + } V & getValue() { return _node; } const V & getValue() const { return _node; } next_t getNext() const { return _next; } @@ -227,6 +224,10 @@ public: typedef std::pair insert_result; public: + hashtable(hashtable &&) = default; + hashtable & operator = (hashtable &&) = default; + hashtable(const hashtable &); + hashtable & operator = (const hashtable &); hashtable(size_t reservedSpace); hashtable(size_t reservedSpace, const Hash & hasher, const Equal & equal); virtual ~hashtable(); @@ -248,20 +249,14 @@ public: const_iterator find(const AltKey & key) const { return find(key, AltExtract()); } const_iterator find(const Key & key) const; template - insert_result insert(V && node) { return insertInternal(std::forward(node)); } - void erase(const Key & key) { - const_iterator found(find(key)); - if (found != end()) { - DefaultMoveHandler moveHandler; - erase(moveHandler, found); - } - } + insert_result insert(V && node); + void erase(const Key & key); void reserve(size_t sz) { if (sz > _nodes.capacity()) { resize(sz); } } - void clear() { _nodes.clear(); resize(getTableSize()); } + void clear(); void resize(size_t newSize); void swap(hashtable & rhs); @@ -307,244 +302,4 @@ private: void reclaim(MoveHandler & moveHandler, next_t node); }; -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -void hashtable::swap(hashtable & rhs) -{ - std::swap(_modulator, rhs._modulator); - std::swap(_count, rhs._count); - _nodes.swap(rhs._nodes); - std::swap(_hasher, rhs._hasher); - std::swap(_equal, rhs._equal); - std::swap(_keyExtractor, rhs._keyExtractor); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -hashtable::hashtable(size_t reservedSpace) : - _modulator(1), - _count(0), - _nodes(1) -{ - if (reservedSpace > 0) { - resize(reservedSpace); - } } - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -hashtable::hashtable(size_t reservedSpace, const Hash & hasher, const Equal & equal) : - _modulator(1), - _count(0), - _nodes(1), - _hasher(hasher), - _equal(equal) -{ - if (reservedSpace > 0) { - resize(reservedSpace); - } -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -hashtable::~hashtable() -{ -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -typename hashtable::iterator -hashtable::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); - } - h = _nodes[h].getNext(); - } while (h != Node::npos); - } - return end(); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -typename hashtable::const_iterator -hashtable::find(const Key & key) const -{ - 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); - } - h = _nodes[h].getNext(); - } while (h != Node::npos); - } - return end(); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -template< typename AltKey, typename AltExtract, typename AltHash, typename AltEqual> -typename hashtable::const_iterator -hashtable::find(const AltKey & key, const AltExtract & altExtract) const -{ - 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); - } - h = _nodes[h].getNext(); - } while (h != Node::npos); - } - return end(); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -template< typename AltKey, typename AltExtract, typename AltHash, typename AltEqual> -typename hashtable::iterator -hashtable::find(const AltKey & key, const AltExtract & altExtract) -{ - 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); - } - h = _nodes[h].getNext(); - } while (h != Node::npos); - } - return end(); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -template< typename V > -typename hashtable::insert_result -hashtable::insertInternal(V && node) -{ - const next_t h = hash(_keyExtractor(node)); - if ( ! _nodes[h].valid() ) { - _nodes[h] = std::forward(node); - _count++; - return insert_result(iterator(this, h, 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); - } - } - if (_nodes.size() < _nodes.capacity()) { - const next_t p(_nodes[h].getNext()); - const next_t newIdx(_nodes.size()); - _nodes[h].setNext(newIdx); - new (_nodes.push_back_fast()) Node(std::forward(node), p); - _count++; - return insert_result(iterator(this, h, newIdx), true); - } else { - resize(_nodes.capacity()*2); - return insertInternal(std::forward(node)); - } - } else { - resize(_nodes.capacity()*2); - return insertInternal(std::forward(node)); - } -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -template -void hashtable::reclaim(MoveHandler & moveHandler, next_t node) -{ - size_t last(_nodes.size()-1); - if (last >= getTableSize()) { - if (last != node) { - next_t h = hash(_keyExtractor(_nodes[last].getValue())); - for (next_t n(_nodes[h].getNext()); n != last; n=_nodes[h].getNext()) { - h = n; - } - move(moveHandler, last, node); - _nodes[h].setNext(node); - } - _nodes.resize(last); - } -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -template -void -hashtable::erase(MoveHandler & moveHandler, const const_iterator & it) -{ - next_t h = it.getHash(); - next_t prev = Node::npos; - do { - if (h == it.getInternalIndex()) { - if (prev != Node::npos) { - _nodes[prev].setNext(_nodes[h].getNext()); - reclaim(moveHandler, h); - } else { - if (_nodes[h].hasNext()) { - next_t next = _nodes[h].getNext(); - move(moveHandler, next, h); - reclaim(moveHandler, next); - } else { - _nodes[h].invalidate(); - } - } - _count--; - return; - } - prev = h; - h = _nodes[h].getNext(); - } while (h != Node::npos); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -void -hashtable::resize(size_t newSize) -{ - newSize = roundUp2inN(newSize); - next_t newModulo = Modulator::selectHashTableSize(newSize/3); - if (newModulo > newSize) { - newSize = newModulo; - } - NodeStore newStore; - newStore.reserve(roundUp2inN(newSize)); - newStore.resize(newModulo); - _modulator = Modulator(newModulo); - _count = 0; - _nodes.swap(newStore); - move(std::move(newStore)); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -void -hashtable::move(NodeStore && oldStore) -{ - for(typename NodeStore::iterator it(oldStore.begin()), mt(oldStore.end()); it != mt; it++) { - if (it->valid()) { - insert(std::move(it->getValue())); - } - } -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -size_t -hashtable::getMemoryConsumption() const -{ - return sizeof(hashtable) - + _nodes.capacity() * sizeof(Node); -} - -template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > -size_t -hashtable::getMemoryUsed() const -{ - return sizeof(hashtable) - + _nodes.size() * sizeof(Node); -} - -} - diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp new file mode 100644 index 00000000000..76454ff7fff --- /dev/null +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp @@ -0,0 +1,289 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#pragma once + +#include "hashtable.h" +#include + +namespace vespalib { + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +void hashtable::swap(hashtable & rhs) +{ + std::swap(_modulator, rhs._modulator); + std::swap(_count, rhs._count); + _nodes.swap(rhs._nodes); + std::swap(_hasher, rhs._hasher); + std::swap(_equal, rhs._equal); + std::swap(_keyExtractor, rhs._keyExtractor); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +hashtable::hashtable(size_t reservedSpace) : + _modulator(1), + _count(0), + _nodes(1) +{ + if (reservedSpace > 0) { + resize(reservedSpace); + } +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +hashtable::hashtable(size_t reservedSpace, const Hash & hasher, const Equal & equal) : + _modulator(1), + _count(0), + _nodes(1), + _hasher(hasher), + _equal(equal) +{ + if (reservedSpace > 0) { + resize(reservedSpace); + } +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +hashtable::hashtable(const hashtable & rhs) + : _modulator(rhs._modulator), + _count(rhs._count), + _nodes(rhs._nodes), + _hasher(rhs._hasher), + _equal(rhs._equal) +{ } + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +hashtable & +hashtable::operator = (const hashtable & rhs) { + hashtable(rhs).swap(*this); + return *this; +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +hashtable::~hashtable() +{ +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +typename hashtable::iterator +hashtable::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); + } + h = _nodes[h].getNext(); + } while (h != Node::npos); + } + return end(); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +typename hashtable::const_iterator +hashtable::find(const Key & key) const +{ + 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); + } + h = _nodes[h].getNext(); + } while (h != Node::npos); + } + return end(); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +template< typename AltKey, typename AltExtract, typename AltHash, typename AltEqual> +typename hashtable::const_iterator +hashtable::find(const AltKey & key, const AltExtract & altExtract) const +{ + 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); + } + h = _nodes[h].getNext(); + } while (h != Node::npos); + } + return end(); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +template< typename AltKey, typename AltExtract, typename AltHash, typename AltEqual> +typename hashtable::iterator +hashtable::find(const AltKey & key, const AltExtract & altExtract) +{ + 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); + } + h = _nodes[h].getNext(); + } while (h != Node::npos); + } + return end(); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +template +typename hashtable::insert_result +hashtable::insert(V && node) { + return insertInternal(std::forward(node)); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +void +hashtable::erase(const Key & key) { + const_iterator found(find(key)); + if (found != end()) { + DefaultMoveHandler moveHandler; + erase(moveHandler, found); + } +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +void +hashtable::clear() { + _nodes.clear(); + resize(getTableSize()); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +template< typename V > +typename hashtable::insert_result +hashtable::insertInternal(V && node) +{ + const next_t h = hash(_keyExtractor(node)); + if ( ! _nodes[h].valid() ) { + _nodes[h] = std::forward(node); + _count++; + return insert_result(iterator(this, h, 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); + } + } + if (_nodes.size() < _nodes.capacity()) { + const next_t p(_nodes[h].getNext()); + const next_t newIdx(_nodes.size()); + _nodes[h].setNext(newIdx); + new (_nodes.push_back_fast()) Node(std::forward(node), p); + _count++; + return insert_result(iterator(this, h, newIdx), true); + } else { + resize(_nodes.capacity()*2); + return insertInternal(std::forward(node)); + } + } else { + resize(_nodes.capacity()*2); + return insertInternal(std::forward(node)); + } +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +template +void hashtable::reclaim(MoveHandler & moveHandler, next_t node) +{ + size_t last(_nodes.size()-1); + if (last >= getTableSize()) { + if (last != node) { + next_t h = hash(_keyExtractor(_nodes[last].getValue())); + for (next_t n(_nodes[h].getNext()); n != last; n=_nodes[h].getNext()) { + h = n; + } + move(moveHandler, last, node); + _nodes[h].setNext(node); + } + _nodes.resize(last); + } +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +template +void +hashtable::erase(MoveHandler & moveHandler, const const_iterator & it) +{ + next_t h = it.getHash(); + next_t prev = Node::npos; + do { + if (h == it.getInternalIndex()) { + if (prev != Node::npos) { + _nodes[prev].setNext(_nodes[h].getNext()); + reclaim(moveHandler, h); + } else { + if (_nodes[h].hasNext()) { + next_t next = _nodes[h].getNext(); + move(moveHandler, next, h); + reclaim(moveHandler, next); + } else { + _nodes[h].invalidate(); + } + } + _count--; + return; + } + prev = h; + h = _nodes[h].getNext(); + } while (h != Node::npos); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +void +hashtable::resize(size_t newSize) +{ + newSize = roundUp2inN(newSize); + next_t newModulo = Modulator::selectHashTableSize(newSize/3); + if (newModulo > newSize) { + newSize = newModulo; + } + NodeStore newStore; + newStore.reserve(roundUp2inN(newSize)); + newStore.resize(newModulo); + _modulator = Modulator(newModulo); + _count = 0; + _nodes.swap(newStore); + move(std::move(newStore)); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +void +hashtable::move(NodeStore && oldStore) +{ + for(typename NodeStore::iterator it(oldStore.begin()), mt(oldStore.end()); it != mt; it++) { + if (it->valid()) { + insert(std::move(it->getValue())); + } + } +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +size_t +hashtable::getMemoryConsumption() const +{ + return sizeof(hashtable) + + _nodes.capacity() * sizeof(Node); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +size_t +hashtable::getMemoryUsed() const +{ + return sizeof(hashtable) + + _nodes.size() * sizeof(Node); +} + +} + diff --git a/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_builder.cpp b/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_builder.cpp index fe626e626cc..8b41d349d43 100644 --- a/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_builder.cpp +++ b/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_builder.cpp @@ -1,11 +1,9 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include #include "dense_tensor_builder.h" #include #include -#include -#include +#include using vespalib::IllegalArgumentException; using vespalib::make_string; diff --git a/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_cells_iterator.h b/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_cells_iterator.h index 446db249e02..c3d00fdb28d 100644 --- a/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_cells_iterator.h +++ b/vespalib/src/vespa/vespalib/tensor/dense/dense_tensor_cells_iterator.h @@ -6,6 +6,7 @@ #include #include #include +#include namespace vespalib { namespace tensor { diff --git a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.cpp b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.cpp index 24c48bfb92c..7a0214e2ca1 100644 --- a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.cpp +++ b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.cpp @@ -1,6 +1,5 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include #include "sparse_tensor.h" #include "sparse_tensor_address_builder.h" #include "sparse_tensor_match.h" @@ -10,6 +9,7 @@ #include #include #include +#include #include using vespalib::eval::TensorSpec; @@ -306,4 +306,7 @@ SparseTensor::reduce(const eval::BinaryOperation &op, } } // namespace vespalib::tensor + +template class hash_map; + } // namespace vespalib diff --git a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.h b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.h index 5ed3d16b29c..e6682011ba2 100644 --- a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.h +++ b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor.h @@ -22,7 +22,7 @@ namespace tensor { class SparseTensor : public Tensor { public: - typedef vespalib::hash_map Cells; + using Cells = vespalib::hash_map; static constexpr size_t STASH_CHUNK_SIZE = 16384u; diff --git a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_address_reducer.cpp b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_address_reducer.cpp index 6073acc4669..277bf7963e0 100644 --- a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_address_reducer.cpp +++ b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_address_reducer.cpp @@ -1,8 +1,8 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include #include "sparse_tensor_address_reducer.h" #include +#include namespace vespalib { namespace tensor { diff --git a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_builder.cpp b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_builder.cpp index 537da7d8085..4092499bf44 100644 --- a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_builder.cpp +++ b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_builder.cpp @@ -2,6 +2,7 @@ #include "sparse_tensor_builder.h" #include +#include namespace vespalib { namespace tensor { diff --git a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_match.cpp b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_match.cpp index 30cbad770a3..4b4378796d0 100644 --- a/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_match.cpp +++ b/vespalib/src/vespa/vespalib/tensor/sparse/sparse_tensor_match.cpp @@ -1,8 +1,8 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include #include "sparse_tensor_match.h" #include "sparse_tensor_address_decoder.h" +#include namespace vespalib { namespace tensor { diff --git a/vespalib/src/vespa/vespalib/tensor/tensor_apply.cpp b/vespalib/src/vespa/vespalib/tensor/tensor_apply.cpp index 23edf418c0b..ab8c1534a39 100644 --- a/vespalib/src/vespa/vespalib/tensor/tensor_apply.cpp +++ b/vespalib/src/vespa/vespalib/tensor/tensor_apply.cpp @@ -1,7 +1,7 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include #include "tensor_apply.h" +#include namespace vespalib { namespace tensor { diff --git a/vespalib/src/vespa/vespalib/tensor/tensor_mapper.cpp b/vespalib/src/vespa/vespalib/tensor/tensor_mapper.cpp index 9c263fb3ffa..646377c1d1a 100644 --- a/vespalib/src/vespa/vespalib/tensor/tensor_mapper.cpp +++ b/vespalib/src/vespa/vespalib/tensor/tensor_mapper.cpp @@ -1,7 +1,5 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include - #include "tensor_mapper.h" #include "tensor.h" #include "tensor_visitor.h" @@ -9,6 +7,7 @@ #include #include "tensor_address_element_iterator.h" #include "default_tensor.h" +#include using vespalib::eval::ValueType; diff --git a/vespalib/src/vespa/vespalib/tensor/types.h b/vespalib/src/vespa/vespalib/tensor/types.h index 6dcdfb5f0d8..7bdb37b8ac2 100644 --- a/vespalib/src/vespa/vespalib/tensor/types.h +++ b/vespalib/src/vespa/vespalib/tensor/types.h @@ -4,7 +4,6 @@ #include #include -#include #include namespace vespalib { diff --git a/vespalib/src/vespa/vespalib/util/CMakeLists.txt b/vespalib/src/vespa/vespalib/util/CMakeLists.txt index 261c33c8135..6fb3626a3a1 100644 --- a/vespalib/src/vespa/vespalib/util/CMakeLists.txt +++ b/vespalib/src/vespa/vespalib/util/CMakeLists.txt @@ -5,6 +5,7 @@ vespa_add_library(vespalib_vespalib_util OBJECT alignedmemory.cpp alloc.cpp approx.cpp + array.cpp atomic.cpp backtrace.cpp barrier.cpp diff --git a/vespalib/src/vespa/vespalib/util/array.cpp b/vespalib/src/vespa/vespalib/util/array.cpp new file mode 100644 index 00000000000..364e87d8a66 --- /dev/null +++ b/vespalib/src/vespa/vespalib/util/array.cpp @@ -0,0 +1,18 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "array.hpp" + +namespace vespalib { + +template class Array; +template class Array; +template class Array; +template class Array; +template class Array; +template class Array; +template class Array; +template class Array; +template class Array; +template class Array; + +} diff --git a/vespalib/src/vespa/vespalib/util/array.h b/vespalib/src/vespa/vespalib/util/array.h index 4016a1dbf3c..4d0699c7886 100644 --- a/vespalib/src/vespa/vespalib/util/array.h +++ b/vespalib/src/vespa/vespalib/util/array.h @@ -2,59 +2,14 @@ #pragma once #include -#include -#include #include #include -#include #include #include #include namespace vespalib { -template class Array; - -/** - * This is a simple wrapper class for a typed array with no memory ownership. - * It is similar to vespalib::stringref - **/ -template -class ArrayRef { -public: - ArrayRef(T * v, size_t sz) : _v(v), _sz(sz) { } - ArrayRef(std::vector & v) : _v(&v[0]), _sz(v.size()) { } - inline ArrayRef(Array &v); - ArrayRef() : _v(nullptr), _sz(0) {} - T & operator [] (size_t i) { return _v[i]; } - const T & operator [] (size_t i) const { return _v[i]; } - size_t size() const { return _sz; } - T *begin() { return _v; } - T *end() { return _v + _sz; } -private: - T * _v; - size_t _sz; -}; - -template -class ConstArrayRef { -public: - ConstArrayRef(const T *v, size_t sz) : _v(v), _sz(sz) { } - ConstArrayRef(const std::vector & v) : _v(&v[0]), _sz(v.size()) { } - ConstArrayRef(const ArrayRef & v) : _v(&v[0]), _sz(v.size()) { } - inline ConstArrayRef(const Array &v); - ConstArrayRef() : _v(nullptr), _sz(0) {} - const T & operator [] (size_t i) const { return _v[i]; } - size_t size() const { return _sz; } - const T *cbegin() const { return _v; } - const T *cend() const { return _v + _sz; } - const T *begin() const { return _v; } - const T *end() const { return _v + _sz; } -private: - const T *_v; - size_t _sz; -}; - /** * This is a small and compact implementation of a resizeable array. * It has a smaller footprint than std::vector and most important, @@ -134,42 +89,23 @@ public: typedef T value_type; typedef size_t size_type; - Array(const Alloc & initial=Alloc::alloc()) : _array(initial.create(0)), _sz(0) { } + Array(const Alloc & initial=Alloc::alloc()); Array(size_t sz, const Alloc & initial=Alloc::alloc()); Array(Alloc && buf, size_t sz); Array(Array &&rhs); Array(size_t sz, T value, const Alloc & initial=Alloc::alloc()); Array(const_iterator begin, const_iterator end, const Alloc & initial=Alloc::alloc()); Array(const Array & rhs); - Array & operator =(const Array & rhs) { - if (&rhs != this) { - Array t(rhs); - swap(t); - } - return *this; - } - Array & operator =(Array && rhs) { - if (&rhs != this) { - Array t(std::move(rhs)); - swap(t); - } - return *this; - } + Array & operator =(const Array & rhs); + Array & operator =(Array && rhs); ~Array(); void swap(Array & rhs) { _array.swap(rhs._array); std::swap(_sz, rhs._sz); } void resize(size_t n); - void assign(const_iterator begin_, const_iterator end_) { - Array tmp(begin_, end_); - swap(tmp); - } - void reserve(size_t n) { - if (capacity() < n) { - increase(n); - } - } + void assign(const_iterator begin_, const_iterator end_); + void reserve(size_t n); void push_back(const T & v) { std::_Construct(push_back(), v); } iterator push_back() { extend(size()+1); return array(_sz++); } iterator push_back_fast() { return array(_sz++); } @@ -216,179 +152,4 @@ private: size_t _sz; }; -template -ArrayRef::ArrayRef(Array &v) - : _v(&v[0]), - _sz(v.size()) -{ -} - -template -ConstArrayRef::ConstArrayRef(const Array &v) - : _v(&v[0]), - _sz(v.size()) -{ -} - -template -void construct(T * dest, const T * source, size_t sz, std::tr1::false_type) -{ - for (size_t i(0); i < sz; i++) { - std::_Construct(dest + i, *(source + i)); - } -} - -template -void construct(T * dest, const T * source, size_t sz, std::tr1::true_type) -{ - memcpy(dest, source, sz*sizeof(T)); -} - -template -void construct(T * dest, size_t sz, std::tr1::false_type) -{ - for (size_t i(0); i < sz; i++) { - void *ptr = &dest[i]; - new(ptr) T(); - } -} - -template -void construct(T * dest, size_t sz, std::tr1::true_type) -{ - (void) dest; - (void) sz; -} - -template -void construct(T * dest, size_t sz, T val, std::tr1::false_type) -{ - for (size_t i(0); i < sz; i++) { - void *ptr = &dest[i]; - new(ptr) T(val); - } -} - -template -void construct(T * dest, size_t sz, T val, std::tr1::true_type) -{ - for (size_t i(0); i < sz; i++) { - dest[i] = val; - } -} - -template -Array::Array(const Array & rhs) - : _array(rhs._array.create(rhs.size() * sizeof(T))), - _sz(rhs.size()) -{ - construct(array(0), rhs.array(0), _sz, std::tr1::has_trivial_destructor()); -} - -template -bool Array::operator ==(const Array & rhs) const -{ - bool retval(size() == rhs.size()); - for (size_t i(0); retval && (i < _sz); i++) { - if (*array(i) != rhs[i]) { - retval = false; - } - } - return retval; -} - -template -void Array::resize(size_t n) -{ - if (n > capacity()) { - reserve(n); - } - if (n > _sz) { - construct(array(_sz), n-_sz, std::tr1::has_trivial_destructor()); - } else if (n < _sz) { - std::_Destroy(array(n), array(_sz)); - } - _sz = n; -} - -template -void move(T * dest, T * source, size_t sz, std::tr1::false_type) -{ - for (size_t i(0); i < sz; i++) { - std::_Construct(dest + i, std::move(*(source + i))); - std::_Destroy(source + i); - } -} - -template -void move(T * dest, const T * source, size_t sz, std::tr1::true_type) -{ - memcpy(dest, source, sz*sizeof(T)); -} - -template -void Array::increase(size_t n) -{ - Alloc newArray(_array.create(sizeof(T)*n)); - if (capacity() > 0) { - move(static_cast(newArray.get()), array(0), _sz, std::tr1::has_trivial_destructor()); - } - _array.swap(newArray); -} - -template -Array::Array(Alloc && buf, size_t sz) : - _array(std::move(buf)), - _sz(sz) -{ -} - - -template -Array::Array(Array &&rhs) - : _array(std::move(rhs._array)), - _sz(rhs._sz) -{ - rhs._sz = 0; -} - -template -Array::Array(size_t sz, const Alloc & initial) : - _array(initial.create(sz * sizeof(T))), - _sz(sz) -{ - construct(array(0), _sz, std::tr1::has_trivial_destructor()); -} - -template -Array::Array(size_t sz, T value, const Alloc & initial) : - _array(initial.create(sz * sizeof(T))), - _sz(sz) -{ - construct(array(0), _sz, value, std::tr1::has_trivial_destructor()); -} - -template -Array::Array(const_iterator begin_, const_iterator end_, const Alloc & initial) : - _array(initial.create(begin_ != end_ ? sizeof(T) * (end_-begin_) : 0)), - _sz(end_-begin_) -{ - construct(array(0), begin_, _sz, std::tr1::has_trivial_destructor()); -} - -template -Array::~Array() -{ - cleanup(); -} - -template -void Array::cleanup() -{ - std::_Destroy(array(0), array(_sz)); - _sz = 0; - Alloc().swap(_array); -} - } - diff --git a/vespalib/src/vespa/vespalib/util/array.hpp b/vespalib/src/vespa/vespalib/util/array.hpp new file mode 100644 index 00000000000..a7194c95014 --- /dev/null +++ b/vespalib/src/vespa/vespalib/util/array.hpp @@ -0,0 +1,208 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#pragma once + +#include "array.h" +#include +#include + +namespace vespalib { + +template +void construct(T * dest, const T * source, size_t sz, std::tr1::false_type) +{ + for (size_t i(0); i < sz; i++) { + std::_Construct(dest + i, *(source + i)); + } +} + +template +void construct(T * dest, const T * source, size_t sz, std::tr1::true_type) +{ + memcpy(dest, source, sz*sizeof(T)); +} + +template +void construct(T * dest, size_t sz, std::tr1::false_type) +{ + for (size_t i(0); i < sz; i++) { + void *ptr = &dest[i]; + new(ptr) T(); + } +} + +template +void construct(T * dest, size_t sz, std::tr1::true_type) +{ + (void) dest; + (void) sz; +} + +template +void construct(T * dest, size_t sz, T val, std::tr1::false_type) +{ + for (size_t i(0); i < sz; i++) { + void *ptr = &dest[i]; + new(ptr) T(val); + } +} + +template +void construct(T * dest, size_t sz, T val, std::tr1::true_type) +{ + for (size_t i(0); i < sz; i++) { + dest[i] = val; + } +} + +template +Array::Array(const Array & rhs) + : _array(rhs._array.create(rhs.size() * sizeof(T))), + _sz(rhs.size()) +{ + construct(array(0), rhs.array(0), _sz, std::tr1::has_trivial_destructor()); +} + +template +Array & Array::operator =(const Array & rhs) +{ + if (&rhs != this) { + Array t(rhs); + swap(t); + } + return *this; +} + +template +Array & Array::operator =(Array && rhs) { + if (&rhs != this) { + Array t(std::move(rhs)); + swap(t); + } + return *this; +} + +template +void Array::assign(const_iterator begin_, const_iterator end_) { + Array tmp(begin_, end_); + swap(tmp); +} +template +void Array::reserve(size_t n) { + if (capacity() < n) { + increase(n); + } +} + +template +bool Array::operator ==(const Array & rhs) const +{ + bool retval(size() == rhs.size()); + for (size_t i(0); retval && (i < _sz); i++) { + if ( ! (*array(i) == rhs[i]) ) { + retval = false; + } + } + return retval; +} + +template +void Array::resize(size_t n) +{ + if (n > capacity()) { + reserve(n); + } + if (n > _sz) { + construct(array(_sz), n-_sz, std::tr1::has_trivial_destructor()); + } else if (n < _sz) { + std::_Destroy(array(n), array(_sz)); + } + _sz = n; +} + +template +void move(T * dest, T * source, size_t sz, std::tr1::false_type) +{ + for (size_t i(0); i < sz; i++) { + std::_Construct(dest + i, std::move(*(source + i))); + std::_Destroy(source + i); + } +} + +template +void move(T * dest, const T * source, size_t sz, std::tr1::true_type) +{ + memcpy(dest, source, sz*sizeof(T)); +} + +template +void Array::increase(size_t n) +{ + Alloc newArray(_array.create(sizeof(T)*n)); + if (capacity() > 0) { + move(static_cast(newArray.get()), array(0), _sz, std::tr1::has_trivial_destructor()); + } + _array.swap(newArray); +} + +template +Array::Array(const Alloc & initial) + : _array(initial.create(0)), + _sz(0) +{ } + +template +Array::Array(Alloc && buf, size_t sz) : + _array(std::move(buf)), + _sz(sz) +{ +} + + +template +Array::Array(Array &&rhs) + : _array(std::move(rhs._array)), + _sz(rhs._sz) +{ + rhs._sz = 0; +} + +template +Array::Array(size_t sz, const Alloc & initial) : + _array(initial.create(sz * sizeof(T))), + _sz(sz) +{ + construct(array(0), _sz, std::tr1::has_trivial_destructor()); +} + +template +Array::Array(size_t sz, T value, const Alloc & initial) : + _array(initial.create(sz * sizeof(T))), + _sz(sz) +{ + construct(array(0), _sz, value, std::tr1::has_trivial_destructor()); +} + +template +Array::Array(const_iterator begin_, const_iterator end_, const Alloc & initial) : + _array(initial.create(begin_ != end_ ? sizeof(T) * (end_-begin_) : 0)), + _sz(end_-begin_) +{ + construct(array(0), begin_, _sz, std::tr1::has_trivial_destructor()); +} + +template +Array::~Array() +{ + cleanup(); +} + +template +void Array::cleanup() +{ + std::_Destroy(array(0), array(_sz)); + _sz = 0; + Alloc().swap(_array); +} + +} + diff --git a/vespalib/src/vespa/vespalib/util/arrayref.h b/vespalib/src/vespa/vespalib/util/arrayref.h new file mode 100644 index 00000000000..1e93fa36576 --- /dev/null +++ b/vespalib/src/vespa/vespalib/util/arrayref.h @@ -0,0 +1,47 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#pragma once + +#include "array.h" + +namespace vespalib { + +/** + * This is a simple wrapper class for a typed array with no memory ownership. + * It is similar to vespalib::stringref + **/ +template +class ArrayRef { +public: + ArrayRef(T * v, size_t sz) : _v(v), _sz(sz) { } + ArrayRef(std::vector & v) : _v(&v[0]), _sz(v.size()) { } + ArrayRef(Array &v) : _v(&v[0]), _sz(v.size()) { } + T & operator [] (size_t i) { return _v[i]; } + const T & operator [] (size_t i) const { return _v[i]; } + size_t size() const { return _sz; } + T *begin() { return _v; } + T *end() { return _v + _sz; } +private: + T * _v; + size_t _sz; +}; + +template +class ConstArrayRef { +public: + ConstArrayRef(const T *v, size_t sz) : _v(v), _sz(sz) { } + ConstArrayRef(const std::vector & v) : _v(&v[0]), _sz(v.size()) { } + ConstArrayRef(const ArrayRef & v) : _v(&v[0]), _sz(v.size()) { } + ConstArrayRef(const Array &v) : _v(&v[0]), _sz(v.size()) { } + ConstArrayRef() : _v(nullptr), _sz(0) {} + const T & operator [] (size_t i) const { return _v[i]; } + size_t size() const { return _sz; } + const T *cbegin() const { return _v; } + const T *cend() const { return _v + _sz; } + const T *begin() const { return _v; } + const T *end() const { return _v + _sz; } +private: + const T *_v; + size_t _sz; +}; + +} diff --git a/vespalib/src/vespa/vespalib/util/generationholder.h b/vespalib/src/vespa/vespalib/util/generationholder.h index d178fc7f4e5..557104e2687 100644 --- a/vespalib/src/vespa/vespalib/util/generationholder.h +++ b/vespalib/src/vespa/vespalib/util/generationholder.h @@ -3,6 +3,7 @@ #pragma once #include +#include #include "generationhandler.h" namespace vespalib { @@ -22,8 +23,7 @@ public: GenerationHeldBase(size_t size) : _generation(0u), _size(size) - { - } + { } virtual ~GenerationHeldBase(void); size_t getSize(void) const { return _size; } diff --git a/vespalib/src/vespa/vespalib/util/stash.h b/vespalib/src/vespa/vespalib/util/stash.h index 1ec0f7b0056..4daccc22d0b 100644 --- a/vespalib/src/vespa/vespalib/util/stash.h +++ b/vespalib/src/vespa/vespalib/util/stash.h @@ -2,9 +2,8 @@ #pragma once -#include #include "traits.h" -#include "array.h" +#include "arrayref.h" namespace vespalib { namespace stash { -- cgit v1.2.3