uncommitted - ordered-map
Ready changes
Summary
Import uploads missing from VCS:Diff
diff --git a/.codecov.yml b/.codecov.yml
index db24720..92a0a4a 100644
--- a/.codecov.yml
+++ b/.codecov.yml
@@ -1 +1,5 @@
comment: off
+coverage:
+ status:
+ project: off
+ patch: off
diff --git a/.pc/.quilt_patches b/.pc/.quilt_patches
new file mode 100644
index 0000000..6857a8d
--- /dev/null
+++ b/.pc/.quilt_patches
@@ -0,0 +1 @@
+debian/patches
diff --git a/.pc/.quilt_series b/.pc/.quilt_series
new file mode 100644
index 0000000..c206706
--- /dev/null
+++ b/.pc/.quilt_series
@@ -0,0 +1 @@
+series
diff --git a/.pc/.version b/.pc/.version
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/.pc/.version
@@ -0,0 +1 @@
+2
diff --git a/.pc/applied-patches b/.pc/applied-patches
new file mode 100644
index 0000000..e69de29
diff --git a/.travis.yml b/.travis.yml
index 0eac4db..afc8b6a 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -29,7 +29,6 @@ matrix:
dist: xenial
env:
- CBUILD_TYPE="Release"
- - TYPE="sanitize"
- CXXFLAGS="-fsanitize=address,undefined"
- os: linux
@@ -37,6 +36,12 @@ matrix:
env:
- TYPE="coverage"
- CXXFLAGS="--coverage"
+
+ - os: linux
+ compiler: gcc
+ env:
+ - CBUILD_TYPE="Release"
+ - CXXFLAGS="-fno-exceptions"
addons:
apt:
diff --git a/CMakeLists.txt b/CMakeLists.txt
index cf2e114..947ac9a 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -2,7 +2,7 @@ cmake_minimum_required(VERSION 3.1)
include(GNUInstallDirs)
-project(tsl-ordered-map VERSION 0.8.1)
+project(tsl-ordered-map VERSION 1.0.0)
add_library(ordered_map INTERFACE)
# Use tsl::ordered_map as target, more consistent with other libraries conventions (Boost, Qt, ...)
diff --git a/LICENSE b/LICENSE
index af99670..e9c5ae9 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,6 +1,6 @@
MIT License
-Copyright (c) 2017 Tessil
+Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
diff --git a/README.md b/README.md
index 5dfd141..107b650 100644
--- a/README.md
+++ b/README.md
@@ -4,7 +4,7 @@
The ordered-map library provides a hash map and a hash set which preserve the order of insertion in a way similar to Python's [OrderedDict](https://docs.python.org/3/library/collections.html#collections.OrderedDict). When iterating over the map, the values will be returned in the same order as they were inserted.
-The values are stored contiguously in an underlying structure, no holes in-between values even after an erase operation. By default a `std::deque` is used for this structure, but it's also possible to use a `std::vector`. This structure is directly accessible through the `values_container()` method and if the structure is a `std::vector`, a `data()` method is also provided to easily interact with C APIs.
+The values are stored contiguously in an underlying structure, no holes in-between values even after an erase operation. By default a `std::deque` is used for this structure, but it's also possible to use a `std::vector`. This structure is directly accessible through the `values_container()` method and if the structure is a `std::vector`, a `data()` method is also provided to easily interact with C APIs. This provides fast iteration but with the drawback of an O(n) erase operation. An O(1) `pop_back()` and an O(1) `unordered_erase()` functions are available.
To resolve collisions on hashes, the library uses linear robin hood probing with backward shift deletion.
@@ -22,15 +22,16 @@ Two classes are provided: `tsl::ordered_map` and `tsl::ordered_set`.
- Provide random access iterators and also reverse iterators.
- Support for heterogeneous lookups allowing the usage of `find` with a type different than `Key` (e.g. if you have a map that uses `std::unique_ptr<foo>` as key, you can use a `foo*` or a `std::uintptr_t` as key parameter to `find` without constructing a `std::unique_ptr<foo>`, see [example](#heterogeneous-lookups)).
- If the hash is known before a lookup, it is possible to pass it as parameter to speed-up the lookup (see `precalculated_hash` parameter in [API](https://tessil.github.io/ordered-map/classtsl_1_1ordered__map.html#a7fcde27edc6697a0b127f4b1aefa8a7d)).
+- Support for efficient serialization and deserialization (see [example](#serialization) and the `serialize/deserialize` methods in the [API](https://tessil.github.io/ordered-map/classtsl_1_1ordered__map.html) for details).
- The library can be used with exceptions disabled (through `-fno-exceptions` option on Clang and GCC, without an `/EH` option on MSVC or simply by defining `TSL_NO_EXCEPTIONS`). `std::terminate` is used in replacement of the `throw` instruction when exceptions are disabled.
- API closely similar to `std::unordered_map` and `std::unordered_set`.
-### Differences compare to `std::unordered_map`
+### Differences compared to `std::unordered_map`
`tsl::ordered_map` tries to have an interface similar to `std::unordered_map`, but some differences exist.
- The iterators are `RandomAccessIterator`.
- Iterator invalidation behaves in a way closer to `std::vector` and `std::deque` (see [API](https://tessil.github.io/ordered-map/classtsl_1_1ordered__map.html#details) for details). If you use `std::vector` as `ValueTypeContainer`, you can use `reserve()` to preallocate some space and avoid the invalidation of the iterators on insert.
- Slow `erase()` operation, it has a complexity of O(n). A faster O(1) version `unordered_erase()` exists, but it breaks the insertion order (see [API](https://tessil.github.io/ordered-map/classtsl_1_1ordered__map.html#a9f94a7889fa7fa92eea41ca63b3f98a4) for details). An O(1) `pop_back()` is also available.
-- The equality oprators `operator==` and `operator!=` are order dependent. Two `tsl::ordered_map` with the same values but inserted in a different order don't compare equal.
+- The equality operators `operator==` and `operator!=` are order dependent. Two `tsl::ordered_map` with the same values but inserted in a different order don't compare equal.
- For iterators, `operator*()` and `operator->()` return a reference and a pointer to `const std::pair<Key, T>` instead of `std::pair<const Key, T>` making the value `T` not modifiable. To modify the value you have to call the `value()` method of the iterator to get a mutable reference. Example:
```c++
tsl::ordered_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};
@@ -239,6 +240,206 @@ int main() {
}
```
+#### Serialization
+
+The library provides an efficient way to serialize and deserialize a map or a set so that it can be saved to a file or send through the network.
+To do so, it requires the user to provide a function object for both serialization and deserialization.
+
+```c++
+struct serializer {
+ // Must support the following types for U: std::uint64_t, float
+ // and std::pair<Key, T> if a map is used or Key for a set.
+ template<typename U>
+ void operator()(const U& value);
+};
+```
+
+```c++
+struct deserializer {
+ // Must support the following types for U: std::uint64_t, float
+ // and std::pair<Key, T> if a map is used or Key for a set.
+ template<typename U>
+ U operator()();
+};
+```
+
+Note that the implementation leaves binary compatibility (endianness, float binary representation, size of int, ...) of the types it serializes/deserializes in the hands of the provided function objects if compatibility is required.
+
+More details regarding the `serialize` and `deserialize` methods can be found in the [API](https://tessil.github.io/ordered-map/classtsl_1_1ordered__map.html).
+
+```c++
+#include <cassert>
+#include <cstdint>
+#include <fstream>
+#include <type_traits>
+#include <tsl/ordered_map.h>
+
+
+class serializer {
+public:
+ explicit serializer(const char* file_name) {
+ m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
+ m_ostream.open(file_name, std::ios::binary);
+ }
+
+ template<class T,
+ typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
+ void operator()(const T& value) {
+ m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
+ }
+
+ void operator()(const std::pair<std::int64_t, std::int64_t>& value) {
+ (*this)(value.first);
+ (*this)(value.second);
+ }
+
+private:
+ std::ofstream m_ostream;
+};
+
+class deserializer {
+public:
+ explicit deserializer(const char* file_name) {
+ m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
+ m_istream.open(file_name, std::ios::binary);
+ }
+
+ template<class T>
+ T operator()() {
+ T value;
+ deserialize(value);
+
+ return value;
+ }
+
+private:
+ template<class T,
+ typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
+ void deserialize(T& value) {
+ m_istream.read(reinterpret_cast<char*>(&value), sizeof(T));
+ }
+
+ void deserialize(std::pair<std::int64_t, std::int64_t>& value) {
+ deserialize(value.first);
+ deserialize(value.second);
+ }
+
+private:
+ std::ifstream m_istream;
+};
+
+
+int main() {
+ const tsl::ordered_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
+
+
+ const char* file_name = "ordered_map.data";
+ {
+ serializer serial(file_name);
+ map.serialize(serial);
+ }
+
+ {
+ deserializer dserial(file_name);
+ auto map_deserialized = tsl::ordered_map<std::int64_t, std::int64_t>::deserialize(dserial);
+
+ assert(map == map_deserialized);
+ }
+
+ {
+ deserializer dserial(file_name);
+
+ /**
+ * If the serialized and deserialized map are hash compatibles (see conditions in API),
+ * setting the argument to true speed-up the deserialization process as we don't have
+ * to recalculate the hash of each key. We also know how much space each bucket needs.
+ */
+ const bool hash_compatible = true;
+ auto map_deserialized =
+ tsl::ordered_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_compatible);
+
+ assert(map == map_deserialized);
+ }
+}
+```
+
+##### Serialization with Boost Serialization and compression with zlib
+
+It's possible to use a serialization library to avoid the boilerplate.
+
+The following example uses Boost Serialization with the Boost zlib compression stream to reduce the size of the resulting serialized file. The example requires C++20 due to the usage of the template parameter list syntax in lambdas, but it can be adapted to less recent versions.
+
+```c++
+#include <boost/archive/binary_iarchive.hpp>
+#include <boost/archive/binary_oarchive.hpp>
+#include <boost/iostreams/filter/zlib.hpp>
+#include <boost/iostreams/filtering_stream.hpp>
+#include <boost/serialization/split_free.hpp>
+#include <boost/serialization/utility.hpp>
+#include <cassert>
+#include <cstdint>
+#include <fstream>
+#include <tsl/ordered_map.h>
+
+
+namespace boost { namespace serialization {
+ template<class Archive, class Key, class T>
+ void serialize(Archive & ar, tsl::ordered_map<Key, T>& map, const unsigned int version) {
+ split_free(ar, map, version);
+ }
+
+ template<class Archive, class Key, class T>
+ void save(Archive & ar, const tsl::ordered_map<Key, T>& map, const unsigned int /*version*/) {
+ auto serializer = [&ar](const auto& v) { ar & v; };
+ map.serialize(serializer);
+ }
+
+ template<class Archive, class Key, class T>
+ void load(Archive & ar, tsl::ordered_map<Key, T>& map, const unsigned int /*version*/) {
+ auto deserializer = [&ar]<typename U>() { U u; ar & u; return u; };
+ map = tsl::ordered_map<Key, T>::deserialize(deserializer);
+ }
+}}
+
+
+int main() {
+ tsl::ordered_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
+
+
+ const char* file_name = "ordered_map.data";
+ {
+ std::ofstream ofs;
+ ofs.exceptions(ofs.badbit | ofs.failbit);
+ ofs.open(file_name, std::ios::binary);
+
+ boost::iostreams::filtering_ostream fo;
+ fo.push(boost::iostreams::zlib_compressor());
+ fo.push(ofs);
+
+ boost::archive::binary_oarchive oa(fo);
+
+ oa << map;
+ }
+
+ {
+ std::ifstream ifs;
+ ifs.exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
+ ifs.open(file_name, std::ios::binary);
+
+ boost::iostreams::filtering_istream fi;
+ fi.push(boost::iostreams::zlib_decompressor());
+ fi.push(ifs);
+
+ boost::archive::binary_iarchive ia(fi);
+
+ tsl::ordered_map<std::int64_t, std::int64_t> map_deserialized;
+ ia >> map_deserialized;
+
+ assert(map == map_deserialized);
+ }
+}
+```
+
### License
The code is licensed under the MIT license, see the [LICENSE file](LICENSE) for details.
diff --git a/debian/changelog b/debian/changelog
index 61b8c8e..7797c39 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,16 @@
+ordered-map (1.0.0-1) unstable; urgency=medium
+
+ * New upstream version 1.0.0
+ * Update upstream author's name in debian/copyiright
+
+ -- Hilko Bengen <bengen@debian.org> Sun, 13 Sep 2020 12:33:45 +0200
+
+ordered-map (0.8.1-2) unstable; urgency=medium
+
+ * Add git-buildpackage configuration
+
+ -- Hilko Bengen <bengen@debian.org> Sun, 31 May 2020 22:10:50 +0200
+
ordered-map (0.8.1-1) experimental; urgency=medium
* Initial release (Closes: #951373)
diff --git a/debian/copyright b/debian/copyright
index eeac1a5..c71c0f4 100644
--- a/debian/copyright
+++ b/debian/copyright
@@ -3,7 +3,7 @@ Upstream-Name: ordered-map
Source: https://github.com/Tessil/ordered-map/releases
Files: *
-Copyright: 2007 Tessil
+Copyright: 2007 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
License: MIT
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
diff --git a/debian/gbp.conf b/debian/gbp.conf
new file mode 100644
index 0000000..e73ec50
--- /dev/null
+++ b/debian/gbp.conf
@@ -0,0 +1,4 @@
+[DEFAULT]
+debian-branch=debian/master
+upstream-branch=upstream
+pristine-tar=True
diff --git a/include/tsl/ordered_hash.h b/include/tsl/ordered_hash.h
index a0b9088..5fbbfcb 100644
--- a/include/tsl/ordered_hash.h
+++ b/include/tsl/ordered_hash.h
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
@@ -68,11 +68,12 @@
#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || (defined (_MSC_VER) && defined (_CPPUNWIND))) && !defined(TSL_NO_EXCEPTIONS)
# define TSL_OH_THROW_OR_TERMINATE(ex, msg) throw ex(msg)
#else
+# define TSL_OH_NO_EXCEPTIONS
# ifdef NDEBUG
# define TSL_OH_THROW_OR_TERMINATE(ex, msg) std::terminate()
# else
-# include <cstdio>
-# define TSL_OH_THROW_OR_TERMINATE(ex, msg) do { std::fprintf(stderr, msg); std::terminate(); } while(0)
+# include <iostream>
+# define TSL_OH_THROW_OR_TERMINATE(ex, msg) do { std::cerr << msg << std::endl; std::terminate(); } while(0)
# endif
#endif
@@ -105,6 +106,47 @@ struct is_vector<T, typename std::enable_if<
>::type>: std::true_type {
};
+// Only available in C++17, we need to be compatible with C++11
+template<class T>
+const T& clamp( const T& v, const T& lo, const T& hi) {
+ return std::min(hi, std::max(lo, v));
+}
+
+template<typename T, typename U>
+static T numeric_cast(U value, const char* error_message = "numeric_cast() failed.") {
+ T ret = static_cast<T>(value);
+ if(static_cast<U>(ret) != value) {
+ TSL_OH_THROW_OR_TERMINATE(std::runtime_error, error_message);
+ }
+
+ const bool is_same_signedness = (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
+ (std::is_signed<T>::value && std::is_signed<U>::value);
+ if(!is_same_signedness && (ret < T{}) != (value < U{})) {
+ TSL_OH_THROW_OR_TERMINATE(std::runtime_error, error_message);
+ }
+
+ return ret;
+}
+
+
+/**
+ * Fixed size type used to represent size_type values on serialization. Need to be big enough
+ * to represent a std::size_t on 32 and 64 bits platforms, and must be the same size on both platforms.
+ */
+using slz_size_type = std::uint64_t;
+static_assert(std::numeric_limits<slz_size_type>::max() >= std::numeric_limits<std::size_t>::max(),
+ "slz_size_type must be >= std::size_t");
+
+template<class T, class Deserializer>
+static T deserialize_value(Deserializer& deserializer) {
+ // MSVC < 2017 is not conformant, circumvent the problem by removing the template keyword
+#if defined (_MSC_VER) && _MSC_VER < 1910
+ return deserializer.Deserializer::operator()<T>();
+#else
+ return deserializer.Deserializer::template operator()<T>();
+#endif
+}
+
/**
* Each bucket entry stores an index which is the index in m_values corresponding to the bucket's value
@@ -167,6 +209,27 @@ public:
m_hash = truncate_hash(hash);
}
+ template<class Serializer>
+ void serialize(Serializer& serializer) const {
+ const slz_size_type index = m_index;
+ serializer(index);
+
+ const slz_size_type hash = m_hash;
+ serializer(hash);
+ }
+
+ template<class Deserializer>
+ static bucket_entry deserialize(Deserializer& deserializer) {
+ const slz_size_type index = deserialize_value<slz_size_type>(deserializer);
+ const slz_size_type hash = deserialize_value<slz_size_type>(deserializer);
+
+ bucket_entry bentry;
+ bentry.m_index = numeric_cast<index_type>(index, "Deserialized index is too big.");
+ bentry.m_hash = numeric_cast<truncated_hash_type>(hash, "Deserialized hash is too big.");
+
+ return bentry;
+ }
+
static truncated_hash_type truncate_hash(std::size_t hash) noexcept {
@@ -202,7 +265,7 @@ private:
*
*
*
- * The orderd_hash structure is a hash table which preserves the order of insertion of the elements.
+ * The ordered_hash structure is a hash table which preserves the order of insertion of the elements.
* To do so, it stores the values in the ValueTypeContainer (m_values) using emplace_back at each
* insertion of a new element. Another structure (m_buckets of type std::vector<bucket_entry>) will
* serve as buckets array for the hash table part. Each bucket stores an index which corresponds to
@@ -384,12 +447,12 @@ public:
KeyEqual(equal),
m_buckets_data(alloc),
m_buckets(static_empty_bucket_ptr()),
- m_mask(0),
+ m_hash_mask(0),
m_values(alloc),
m_grow_on_next_insert(false)
{
if(bucket_count > max_bucket_count()) {
- TSL_OH_THROW_OR_TERMINATE(std::length_error, "The map exceeds its maxmimum size.");
+ TSL_OH_THROW_OR_TERMINATE(std::length_error, "The map exceeds its maximum size.");
}
if(bucket_count > 0) {
@@ -397,7 +460,7 @@ public:
m_buckets_data.resize(bucket_count);
m_buckets = m_buckets_data.data(),
- m_mask = bucket_count - 1;
+ m_hash_mask = bucket_count - 1;
}
this->max_load_factor(max_load_factor);
@@ -408,11 +471,11 @@ public:
m_buckets_data(other.m_buckets_data),
m_buckets(m_buckets_data.empty()?static_empty_bucket_ptr():
m_buckets_data.data()),
- m_mask(other.m_mask),
+ m_hash_mask(other.m_hash_mask),
m_values(other.m_values),
- m_grow_on_next_insert(other.m_grow_on_next_insert),
+ m_load_threshold(other.m_load_threshold),
m_max_load_factor(other.m_max_load_factor),
- m_load_threshold(other.m_load_threshold)
+ m_grow_on_next_insert(other.m_grow_on_next_insert)
{
}
@@ -425,18 +488,18 @@ public:
m_buckets_data(std::move(other.m_buckets_data)),
m_buckets(m_buckets_data.empty()?static_empty_bucket_ptr():
m_buckets_data.data()),
- m_mask(other.m_mask),
+ m_hash_mask(other.m_hash_mask),
m_values(std::move(other.m_values)),
- m_grow_on_next_insert(other.m_grow_on_next_insert),
+ m_load_threshold(other.m_load_threshold),
m_max_load_factor(other.m_max_load_factor),
- m_load_threshold(other.m_load_threshold)
+ m_grow_on_next_insert(other.m_grow_on_next_insert)
{
other.m_buckets_data.clear();
other.m_buckets = static_empty_bucket_ptr();
- other.m_mask = 0;
+ other.m_hash_mask = 0;
other.m_values.clear();
- other.m_grow_on_next_insert = false;
other.m_load_threshold = 0;
+ other.m_grow_on_next_insert = false;
}
ordered_hash& operator=(const ordered_hash& other) {
@@ -448,11 +511,11 @@ public:
m_buckets = m_buckets_data.empty()?static_empty_bucket_ptr():
m_buckets_data.data();
- m_mask = other.m_mask;
+ m_hash_mask = other.m_hash_mask;
m_values = other.m_values;
- m_grow_on_next_insert = other.m_grow_on_next_insert;
- m_max_load_factor = other.m_max_load_factor;
m_load_threshold = other.m_load_threshold;
+ m_max_load_factor = other.m_max_load_factor;
+ m_grow_on_next_insert = other.m_grow_on_next_insert;
}
return *this;
@@ -728,11 +791,11 @@ public:
swap(static_cast<KeyEqual&>(*this), static_cast<KeyEqual&>(other));
swap(m_buckets_data, other.m_buckets_data);
swap(m_buckets, other.m_buckets);
- swap(m_mask, other.m_mask);
+ swap(m_hash_mask, other.m_hash_mask);
swap(m_values, other.m_values);
- swap(m_grow_on_next_insert, other.m_grow_on_next_insert);
- swap(m_max_load_factor, other.m_max_load_factor);
swap(m_load_threshold, other.m_load_threshold);
+ swap(m_max_load_factor, other.m_max_load_factor);
+ swap(m_grow_on_next_insert, other.m_grow_on_next_insert);
}
@@ -811,6 +874,17 @@ public:
return (it_bucket != m_buckets_data.cend())?const_iterator(m_values.begin() + it_bucket->index()):end();
}
+
+ template<class K>
+ bool contains(const K& key) const {
+ return contains(key, hash_key(key));
+ }
+
+ template<class K>
+ bool contains(const K& key, std::size_t hash) const {
+ return find(key, hash) != cend();
+ }
+
template<class K>
std::pair<iterator, iterator> equal_range(const K& key) {
@@ -862,7 +936,10 @@ public:
}
void max_load_factor(float ml) {
- m_max_load_factor = std::max(0.1f, std::min(ml, 0.95f));
+ m_max_load_factor = clamp(ml, float(MAX_LOAD_FACTOR__MINIMUM),
+ float(MAX_LOAD_FACTOR__MAXIMUM));
+
+ m_max_load_factor = ml;
m_load_threshold = size_type(float(bucket_count())*m_max_load_factor);
}
@@ -1013,6 +1090,16 @@ public:
return 1;
}
+ template<class Serializer>
+ void serialize(Serializer& serializer) const {
+ serialize_impl(serializer);
+ }
+
+ template<class Deserializer>
+ void deserialize(Deserializer& deserializer, bool hash_compatible) {
+ deserialize_impl(deserializer, hash_compatible);
+ }
+
friend bool operator==(const ordered_hash& lhs, const ordered_hash& rhs) {
return lhs.m_values == rhs.m_values;
}
@@ -1085,7 +1172,7 @@ private:
tsl_oh_assert(bucket_count >= size_type(std::ceil(float(size())/max_load_factor())));
if(bucket_count > max_bucket_count()) {
- TSL_OH_THROW_OR_TERMINATE(std::length_error, "The map exceeds its maxmimum size.");
+ TSL_OH_THROW_OR_TERMINATE(std::length_error, "The map exceeds its maximum size.");
}
if(bucket_count > 0) {
@@ -1103,7 +1190,7 @@ private:
m_buckets_data.data();
// Everything should be noexcept from here.
- m_mask = (bucket_count > 0)?(bucket_count - 1):0;
+ m_hash_mask = (bucket_count > 0)?(bucket_count - 1):0;
this->max_load_factor(m_max_load_factor);
m_grow_on_next_insert = false;
@@ -1363,7 +1450,7 @@ private:
}
std::size_t bucket_for_hash(std::size_t hash) const noexcept {
- return hash & m_mask;
+ return hash & m_hash_mask;
}
std::size_t iterator_to_index(const_iterator it) const noexcept {
@@ -1388,6 +1475,83 @@ private:
}
}
+ template<class Serializer>
+ void serialize_impl(Serializer& serializer) const {
+ const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
+ serializer(version);
+
+ const slz_size_type nb_elements = m_values.size();
+ serializer(nb_elements);
+
+ const slz_size_type bucket_count = m_buckets_data.size();
+ serializer(bucket_count);
+
+ const float max_load_factor = m_max_load_factor;
+ serializer(max_load_factor);
+
+
+ for(const value_type& value: m_values) {
+ serializer(value);
+ }
+
+ for(const bucket_entry& bucket: m_buckets_data) {
+ bucket.serialize(serializer);
+ }
+ }
+
+ template<class Deserializer>
+ void deserialize_impl(Deserializer& deserializer, bool hash_compatible) {
+ tsl_oh_assert(m_buckets_data.empty()); // Current hash table must be empty
+
+ const slz_size_type version = deserialize_value<slz_size_type>(deserializer);
+ // For now we only have one version of the serialization protocol.
+ // If it doesn't match there is a problem with the file.
+ if(version != SERIALIZATION_PROTOCOL_VERSION) {
+ TSL_OH_THROW_OR_TERMINATE(std::runtime_error, "Can't deserialize the ordered_map/set. "
+ "The protocol version header is invalid.");
+ }
+
+ const slz_size_type nb_elements = deserialize_value<slz_size_type>(deserializer);
+ const slz_size_type bucket_count_ds = deserialize_value<slz_size_type>(deserializer);
+ const float max_load_factor = deserialize_value<float>(deserializer);
+
+ if(max_load_factor < MAX_LOAD_FACTOR__MINIMUM || max_load_factor > MAX_LOAD_FACTOR__MAXIMUM) {
+ TSL_OH_THROW_OR_TERMINATE(std::runtime_error, "Invalid max_load_factor. Check that the serializer "
+ "and deserializer support floats correctly as they "
+ "can be converted implicitly to ints.");
+ }
+
+
+ this->max_load_factor(max_load_factor);
+
+ if(bucket_count_ds == 0) {
+ tsl_oh_assert(nb_elements == 0);
+ return;
+ }
+
+
+ if(!hash_compatible) {
+ reserve(numeric_cast<size_type>(nb_elements, "Deserialized nb_elements is too big."));
+ for(slz_size_type el = 0; el < nb_elements; el++) {
+ insert(deserialize_value<value_type>(deserializer));
+ }
+ }
+ else {
+ m_buckets_data.reserve(numeric_cast<size_type>(bucket_count_ds, "Deserialized bucket_count is too big."));
+ m_buckets = m_buckets_data.data(),
+ m_hash_mask = m_buckets_data.capacity() - 1;
+
+ reserve_space_for_values(numeric_cast<size_type>(nb_elements, "Deserialized nb_elements is too big."));
+ for(slz_size_type el = 0; el < nb_elements; el++) {
+ m_values.push_back(deserialize_value<value_type>(deserializer));
+ }
+
+ for(slz_size_type b = 0; b < bucket_count_ds; b++) {
+ m_buckets_data.push_back(bucket_entry::deserialize(deserializer));
+ }
+ }
+ }
+
static std::size_t round_up_to_power_of_two(std::size_t value) {
if(is_power_of_two(value)) {
return value;
@@ -1415,9 +1579,16 @@ public:
static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
private:
+ static constexpr float MAX_LOAD_FACTOR__MINIMUM = 0.1f;
+ static constexpr float MAX_LOAD_FACTOR__MAXIMUM = 0.95f;
+
static const size_type REHASH_ON_HIGH_NB_PROBES__NPROBES = 128;
static constexpr float REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR = 0.15f;
+ /**
+ * Protocol version currenlty used for serialization.
+ */
+ static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
/**
* Return an always valid pointer to an static empty bucket_entry with last_bucket() == true.
@@ -1439,13 +1610,14 @@ private:
*/
bucket_entry* m_buckets;
- size_type m_mask;
+ size_type m_hash_mask;
values_container_type m_values;
- bool m_grow_on_next_insert;
- float m_max_load_factor;
size_type m_load_threshold;
+ float m_max_load_factor;
+
+ bool m_grow_on_next_insert;
};
diff --git a/include/tsl/ordered_map.h b/include/tsl/ordered_map.h
index 6b90992..1a20cca 100644
--- a/include/tsl/ordered_map.h
+++ b/include/tsl/ordered_map.h
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
@@ -41,18 +41,18 @@ namespace tsl {
/**
- * Implementation of an hash map using open adressing with robin hood with backshift delete to resolve collisions.
+ * Implementation of an hash map using open addressing with robin hood with backshift delete to resolve collisions.
*
* The particularity of this hash map is that it remembers the order in which the elements were added and
* provide a way to access the structure which stores these values through the 'values_container()' method.
* The used container is defined by ValueTypeContainer, by default a std::deque is used (grows faster) but
* a std::vector may be used. In this case the map provides a 'data()' method which give a direct access
- * to the memory used to store the values (which can be usefull to communicate with C API's).
+ * to the memory used to store the values (which can be useful to communicate with C API's).
*
* The Key and T must be copy constructible and/or move constructible. To use `unordered_erase` they both
* must be swappable.
*
- * The behaviour of the hash map is undefinded if the destructor of Key or T throws an exception.
+ * The behaviour of the hash map is undefined if the destructor of Key or T throws an exception.
*
* By default the maximum size of a map is limited to 2^32 - 1 values, if needed this can be changed through
* the IndexType template parameter. Using an `uint64_t` will raise this limit to 2^64 - 1 values but each
@@ -378,7 +378,7 @@ public:
* @copydoc erase(iterator pos)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash.
*/
size_type erase(const key_type& key, std::size_t precalculated_hash) {
return m_ht.erase(key, precalculated_hash);
@@ -415,7 +415,7 @@ public:
/**
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
T& at(const Key& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); }
@@ -439,7 +439,7 @@ public:
* @copydoc at(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
T& at(const K& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); }
@@ -467,7 +467,7 @@ public:
/**
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
size_type count(const Key& key, std::size_t precalculated_hash) const {
return m_ht.count(key, precalculated_hash);
@@ -484,7 +484,7 @@ public:
* @copydoc count(const K& key) const
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
size_type count(const K& key, std::size_t precalculated_hash) const {
@@ -497,7 +497,7 @@ public:
/**
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
iterator find(const Key& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
@@ -521,7 +521,7 @@ public:
* @copydoc find(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
iterator find(const K& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
@@ -536,7 +536,7 @@ public:
* @copydoc find(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
const_iterator find(const K& key, std::size_t precalculated_hash) const {
@@ -545,11 +545,41 @@ public:
+ bool contains(const Key& key) const { return m_ht.contains(key); }
+
+ /**
+ * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
+ */
+ bool contains(const Key& key, std::size_t precalculated_hash) const {
+ return m_ht.contains(key, precalculated_hash);
+ }
+
+ /**
+ * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
+ * If so, K must be hashable and comparable to Key.
+ */
+ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
+ bool contains(const K& key) const { return m_ht.contains(key); }
+
+ /**
+ * @copydoc contains(const K& key) const
+ *
+ * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
+ */
+ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
+ bool contains(const K& key, std::size_t precalculated_hash) const {
+ return m_ht.contains(key, precalculated_hash);
+ }
+
+
+
std::pair<iterator, iterator> equal_range(const Key& key) { return m_ht.equal_range(key); }
/**
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash) {
return m_ht.equal_range(key, precalculated_hash);
@@ -575,7 +605,7 @@ public:
* @copydoc equal_range(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
std::pair<iterator, iterator> equal_range(const K& key, std::size_t precalculated_hash) {
@@ -747,7 +777,7 @@ public:
* @copydoc unordered_erase(iterator pos)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
size_type unordered_erase(const key_type& key, std::size_t precalculated_hash) {
return m_ht.unordered_erase(key, precalculated_hash);
@@ -766,13 +796,53 @@ public:
* @copydoc unordered_erase(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
size_type unordered_erase(const K& key, std::size_t precalculated_hash) {
return m_ht.unordered_erase(key, precalculated_hash);
}
+ /**
+ * Serialize the map through the `serializer` parameter.
+ *
+ * The `serializer` parameter must be a function object that supports the following call:
+ * - `template<typename U> void operator()(const U& value);` where the types `std::uint64_t`, `float` and `std::pair<Key, T>` must be supported for U.
+ *
+ * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, ...) of the types it serializes
+ * in the hands of the `Serializer` function object if compatibility is required.
+ */
+ template<class Serializer>
+ void serialize(Serializer& serializer) const {
+ m_ht.serialize(serializer);
+ }
+
+ /**
+ * Deserialize a previously serialized map through the `deserializer` parameter.
+ *
+ * The `deserializer` parameter must be a function object that supports the following calls:
+ * - `template<typename U> U operator()();` where the types `std::uint64_t`, `float` and `std::pair<Key, T>` must be supported for U.
+ *
+ * If the deserialized hash map type is hash compatible with the serialized map, the deserialization process can be
+ * sped up by setting `hash_compatible` to true. To be hash compatible, the Hash and KeyEqual must behave the same way
+ * than the ones used on the serialized map. The `std::size_t` must also be of the same size as the one on the platform used
+ * to serialize the map, the same apply for `IndexType`. If these criteria are not met, the behaviour is undefined with
+ * `hash_compatible` sets to true.
+ *
+ * The behaviour is undefined if the type `Key` and `T` of the `ordered_map` are not the same as the
+ * types used during serialization.
+ *
+ * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, size of int, ...) of the types it
+ * deserializes in the hands of the `Deserializer` function object if compatibility is required.
+ */
+ template<class Deserializer>
+ static ordered_map deserialize(Deserializer& deserializer, bool hash_compatible = false) {
+ ordered_map map(0);
+ map.m_ht.deserialize(deserializer, hash_compatible);
+
+ return map;
+ }
+
friend bool operator==(const ordered_map& lhs, const ordered_map& rhs) { return lhs.m_ht == rhs.m_ht; }
diff --git a/include/tsl/ordered_set.h b/include/tsl/ordered_set.h
index 6fdb938..90a99ee 100644
--- a/include/tsl/ordered_set.h
+++ b/include/tsl/ordered_set.h
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
@@ -41,17 +41,17 @@ namespace tsl {
/**
- * Implementation of an hash set using open adressing with robin hood with backshift delete to resolve collisions.
+ * Implementation of an hash set using open addressing with robin hood with backshift delete to resolve collisions.
*
* The particularity of this hash set is that it remembers the order in which the elements were added and
* provide a way to access the structure which stores these values through the 'values_container()' method.
* The used container is defined by ValueTypeContainer, by default a std::deque is used (grows faster) but
* a std::vector may be used. In this case the set provides a 'data()' method which give a direct access
- * to the memory used to store the values (which can be usefull to communicate with C API's).
+ * to the memory used to store the values (which can be useful to communicate with C API's).
*
* The Key must be copy constructible and/or move constructible. To use `unordered_erase` it also must be swappable.
*
- * The behaviour of the hash set is undefinded if the destructor of Key throws an exception.
+ * The behaviour of the hash set is undefined if the destructor of Key throws an exception.
*
* By default the maximum size of a set is limited to 2^32 - 1 values, if needed this can be changed through
* the IndexType template parameter. Using an `uint64_t` will raise this limit to 2^64 - 1 values but each
@@ -302,7 +302,7 @@ public:
* @copydoc erase(iterator pos)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash.
*/
size_type erase(const key_type& key, std::size_t precalculated_hash) {
return m_ht.erase(key, precalculated_hash);
@@ -339,7 +339,7 @@ public:
/**
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
size_type count(const Key& key, std::size_t precalculated_hash) const {
return m_ht.count(key, precalculated_hash);
@@ -356,7 +356,7 @@ public:
* @copydoc count(const K& key) const
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
size_type count(const K& key, std::size_t precalculated_hash) const {
@@ -370,7 +370,7 @@ public:
/**
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
iterator find(const Key& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
@@ -394,7 +394,7 @@ public:
* @copydoc find(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
iterator find(const K& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); }
@@ -409,7 +409,7 @@ public:
* @copydoc find(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
const_iterator find(const K& key, std::size_t precalculated_hash) const {
@@ -418,11 +418,41 @@ public:
+ bool contains(const Key& key) const { return m_ht.contains(key); }
+
+ /**
+ * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
+ */
+ bool contains(const Key& key, std::size_t precalculated_hash) const {
+ return m_ht.contains(key, precalculated_hash);
+ }
+
+ /**
+ * This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists.
+ * If so, K must be hashable and comparable to Key.
+ */
+ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
+ bool contains(const K& key) const { return m_ht.contains(key); }
+
+ /**
+ * @copydoc contains(const K& key) const
+ *
+ * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
+ */
+ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
+ bool contains(const K& key, std::size_t precalculated_hash) const {
+ return m_ht.contains(key, precalculated_hash);
+ }
+
+
+
std::pair<iterator, iterator> equal_range(const Key& key) { return m_ht.equal_range(key); }
/**
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash) {
return m_ht.equal_range(key, precalculated_hash);
@@ -448,7 +478,7 @@ public:
* @copydoc equal_range(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
std::pair<iterator, iterator> equal_range(const K& key, std::size_t precalculated_hash) {
@@ -602,7 +632,7 @@ public:
* @copydoc unordered_erase(iterator pos)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
size_type unordered_erase(const key_type& key, std::size_t precalculated_hash) {
return m_ht.unordered_erase(key, precalculated_hash);
@@ -621,13 +651,53 @@ public:
* @copydoc unordered_erase(const K& key)
*
* Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
- * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash.
+ * as hash_function()(key). Useful to speed-up the lookup if you already have the hash.
*/
template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
size_type unordered_erase(const K& key, std::size_t precalculated_hash) {
return m_ht.unordered_erase(key, precalculated_hash);
}
+ /**
+ * Serialize the set through the `serializer` parameter.
+ *
+ * The `serializer` parameter must be a function object that supports the following call:
+ * - `void operator()(const U& value);` where the types `std::uint64_t`, `float` and `Key` must be supported for U.
+ *
+ * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, ...) of the types it serializes
+ * in the hands of the `Serializer` function object if compatibility is required.
+ */
+ template<class Serializer>
+ void serialize(Serializer& serializer) const {
+ m_ht.serialize(serializer);
+ }
+
+ /**
+ * Deserialize a previously serialized set through the `deserializer` parameter.
+ *
+ * The `deserializer` parameter must be a function object that supports the following calls:
+ * - `template<typename U> U operator()();` where the types `std::uint64_t`, `float` and `Key` must be supported for U.
+ *
+ * If the deserialized hash set type is hash compatible with the serialized set, the deserialization process can be
+ * sped up by setting `hash_compatible` to true. To be hash compatible, the Hash and KeyEqual must behave the same way
+ * than the ones used on the serialized map. The `std::size_t` must also be of the same size as the one on the platform used
+ * to serialize the map, the same apply for `IndexType`. If these criteria are not met, the behaviour is undefined with
+ * `hash_compatible` sets to true.
+ *
+ * The behaviour is undefined if the type `Key` of the `ordered_set` is not the same as the
+ * type used during serialization.
+ *
+ * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, size of int, ...) of the types it
+ * deserializes in the hands of the `Deserializer` function object if compatibility is required.
+ */
+ template<class Deserializer>
+ static ordered_set deserialize(Deserializer& deserializer, bool hash_compatible = false) {
+ ordered_set set(0);
+ set.m_ht.deserialize(deserializer, hash_compatible);
+
+ return set;
+ }
+
friend bool operator==(const ordered_set& lhs, const ordered_set& rhs) { return lhs.m_ht == rhs.m_ht; }
diff --git a/tests/custom_allocator_tests.cpp b/tests/custom_allocator_tests.cpp
index a8ebc28..9090d75 100644
--- a/tests/custom_allocator_tests.cpp
+++ b/tests/custom_allocator_tests.cpp
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
@@ -75,7 +75,11 @@ public:
pointer ptr = static_cast<pointer>(std::malloc(n * sizeof(T)));
if(ptr == nullptr) {
+#ifdef TSL_OH_NO_EXCEPTIONS
+ std::abort();
+#else
throw std::bad_alloc();
+#endif
}
return ptr;
diff --git a/tests/main.cpp b/tests/main.cpp
index 50443b6..9c2c8b8 100644
--- a/tests/main.cpp
+++ b/tests/main.cpp
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
diff --git a/tests/ordered_map_tests.cpp b/tests/ordered_map_tests.cpp
index a7a7935..5d5a9df 100644
--- a/tests/ordered_map_tests.cpp
+++ b/tests/ordered_map_tests.cpp
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
@@ -874,7 +874,7 @@ BOOST_AUTO_TEST_CASE(test_max_size) {
* constructor
*/
BOOST_AUTO_TEST_CASE(test_extreme_bucket_count_value_construction) {
- BOOST_CHECK_THROW((tsl::ordered_map<int, int>(std::numeric_limits<std::size_t>::max())), std::length_error);
+ TSL_OH_CHECK_THROW((tsl::ordered_map<int, int>(std::numeric_limits<std::size_t>::max())), std::length_error);
}
BOOST_AUTO_TEST_CASE(test_range_construct) {
@@ -1064,6 +1064,29 @@ BOOST_AUTO_TEST_CASE(test_copy_constructor_and_operator) {
BOOST_CHECK(map_copy == map_copy3);
}
+BOOST_AUTO_TEST_CASE(test_copy_constructor_empty) {
+ tsl::ordered_map<std::string, int> map(0);
+ tsl::ordered_map<std::string, int> map_copy(map);
+
+ BOOST_CHECK(map.empty());
+ BOOST_CHECK(map_copy.empty());
+
+ BOOST_CHECK(map.find("") == map.end());
+ BOOST_CHECK(map_copy.find("") == map_copy.end());
+}
+
+BOOST_AUTO_TEST_CASE(test_copy_operator_empty) {
+ tsl::ordered_map<std::string, int> map(0);
+ tsl::ordered_map<std::string, int> map_copy(16);
+ map_copy = map;
+
+ BOOST_CHECK(map.empty());
+ BOOST_CHECK(map_copy.empty());
+
+ BOOST_CHECK(map.find("") == map.end());
+ BOOST_CHECK(map_copy.find("") == map_copy.end());
+}
+
/**
* at
@@ -1074,7 +1097,19 @@ BOOST_AUTO_TEST_CASE(test_at) {
BOOST_CHECK_EQUAL(map.at(0), 10);
BOOST_CHECK_EQUAL(map.at(-2), 20);
- BOOST_CHECK_THROW(map.at(1), std::out_of_range);
+ TSL_OH_CHECK_THROW(map.at(1), std::out_of_range);
+}
+
+
+/**
+ * contains
+ */
+BOOST_AUTO_TEST_CASE(test_contains) {
+ tsl::ordered_map<std::int64_t, std::int64_t> map = {{0, 10}, {-2, 20}};
+
+ BOOST_CHECK(map.contains(0));
+ BOOST_CHECK(map.contains(-2));
+ BOOST_CHECK(!map.contains(-3));
}
@@ -1155,6 +1190,89 @@ BOOST_AUTO_TEST_CASE(test_swap_empty) {
BOOST_CHECK(map2 == (tsl::ordered_map<std::int64_t, std::int64_t>{{1, 10}, {8, 80}, {3, 30}, {4, 40}}));
}
+/**
+ * serialize and deserialize
+ */
+BOOST_AUTO_TEST_CASE(test_serialize_deserialize_empty) {
+ // serialize empty map; deserialize in new map; check equal.
+ // for deserialization, test it with and without hash compatibility.
+ const tsl::ordered_map<std::string, move_only_test> empty_map(0);
+
+
+ serializer serial;
+ empty_map.serialize(serial);
+
+ deserializer dserial(serial.str());
+ auto empty_map_deserialized = decltype(empty_map)::deserialize(dserial, true);
+ BOOST_CHECK(empty_map_deserialized == empty_map);
+
+ deserializer dserial2(serial.str());
+ empty_map_deserialized = decltype(empty_map)::deserialize(dserial2, false);
+ BOOST_CHECK(empty_map_deserialized == empty_map);
+}
+
+BOOST_AUTO_TEST_CASE(test_serialize_deserialize) {
+ // insert x values; delete some values; serialize map; deserialize in new map; check equal.
+ // for deserialization, test it with and without hash compatibility.
+ const std::size_t nb_values = 1000;
+
+
+ tsl::ordered_map<std::string, move_only_test> map;
+ for(std::size_t i = 0; i < nb_values + 40; i++) {
+ map.insert({utils::get_key<std::string>(i), utils::get_value<move_only_test>(i)});
+ }
+
+ for(std::size_t i = nb_values; i < nb_values + 40; i++) {
+ map.erase(utils::get_key<std::string>(i));
+ }
+ BOOST_CHECK_EQUAL(map.size(), nb_values);
+
+
+
+ serializer serial;
+ map.serialize(serial);
+
+ deserializer dserial(serial.str());
+ auto map_deserialized = decltype(map)::deserialize(dserial, true);
+ BOOST_CHECK(map == map_deserialized);
+
+ deserializer dserial2(serial.str());
+ map_deserialized = decltype(map)::deserialize(dserial2, false);
+ BOOST_CHECK(map_deserialized == map);
+}
+
+BOOST_AUTO_TEST_CASE(test_serialize_deserialize_with_different_hash) {
+ // insert x values; serialize map; deserialize in new map which has a different hash; check equal
+ struct hash_str_diff {
+ std::size_t operator()(const std::string& str) const {
+ return std::hash<std::string>()(str) + 123;
+ }
+ };
+
+
+ const std::size_t nb_values = 1000;
+
+
+ tsl::ordered_map<std::string, move_only_test> map;
+ for(std::size_t i = 0; i < nb_values; i++) {
+ map.insert({utils::get_key<std::string>(i), utils::get_value<move_only_test>(i)});
+ }
+ BOOST_CHECK_EQUAL(map.size(), nb_values);
+
+
+
+ serializer serial;
+ map.serialize(serial);
+
+ deserializer dserial(serial.str());
+ auto map_deserialized = tsl::ordered_map<std::string, move_only_test, hash_str_diff>::deserialize(dserial, false);
+
+ BOOST_CHECK_EQUAL(map_deserialized.size(), map.size());
+ for(const auto& val: map) {
+ BOOST_CHECK(map_deserialized.find(val.first) != map_deserialized.end());
+ }
+}
+
/**
* front(), back()
*/
@@ -1296,7 +1414,7 @@ BOOST_AUTO_TEST_CASE(test_heterogeneous_lookups) {
BOOST_CHECK_EQUAL(map.at(addr1), 4);
BOOST_CHECK_EQUAL(map.at(addr2), 5);
- BOOST_CHECK_THROW(map.at(addr_unknown), std::out_of_range);
+ TSL_OH_CHECK_THROW(map.at(addr_unknown), std::out_of_range);
@@ -1347,8 +1465,11 @@ BOOST_AUTO_TEST_CASE(test_empty_map) {
BOOST_CHECK_EQUAL(map.count(""), 0);
BOOST_CHECK_EQUAL(map.count("test"), 0);
- BOOST_CHECK_THROW(map.at(""), std::out_of_range);
- BOOST_CHECK_THROW(map.at("test"), std::out_of_range);
+ BOOST_CHECK(!map.contains(""));
+ BOOST_CHECK(!map.contains("test"));
+
+ TSL_OH_CHECK_THROW(map.at(""), std::out_of_range);
+ TSL_OH_CHECK_THROW(map.at("test"), std::out_of_range);
auto range = map.equal_range("test");
BOOST_CHECK(range.first == range.second);
@@ -1385,7 +1506,16 @@ BOOST_AUTO_TEST_CASE(test_precalculated_hash) {
BOOST_CHECK_EQUAL(map_const.at(3, map_const.hash_function()(3)), -3);
BOOST_REQUIRE_NE(map.hash_function()(2), map.hash_function()(3));
- BOOST_CHECK_THROW(map.at(3, map.hash_function()(2)), std::out_of_range);
+ TSL_OH_CHECK_THROW(map.at(3, map.hash_function()(2)), std::out_of_range);
+
+ /**
+ * count
+ */
+ BOOST_CHECK(map.contains(3, map.hash_function()(3)));
+ BOOST_CHECK(map_const.contains(3, map_const.hash_function()(3)));
+
+ BOOST_REQUIRE_NE(map.hash_function()(2), map.hash_function()(3));
+ BOOST_CHECK(!map.contains(3, map.hash_function()(2)));
/**
* count
diff --git a/tests/ordered_set_tests.cpp b/tests/ordered_set_tests.cpp
index e30ae26..6675734 100644
--- a/tests/ordered_set_tests.cpp
+++ b/tests/ordered_set_tests.cpp
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
@@ -127,5 +127,38 @@ BOOST_AUTO_TEST_CASE(test_insert_pointer) {
BOOST_CHECK_EQUAL(set.size(), 1);
BOOST_CHECK_EQUAL(**set.begin(), value);
}
+
+/**
+ * serialize and deserialize
+ */
+BOOST_AUTO_TEST_CASE(test_serialize_deserialize) {
+ // insert x values; delete some values; serialize set; deserialize in new set; check equal.
+ // for deserialization, test it with and without hash compatibility.
+ const std::size_t nb_values = 1000;
+
+
+ tsl::ordered_set<move_only_test> set;
+ for(std::size_t i = 0; i < nb_values + 40; i++) {
+ set.insert(utils::get_key<move_only_test>(i));
+ }
+
+ for(std::size_t i = nb_values; i < nb_values + 40; i++) {
+ set.erase(utils::get_key<move_only_test>(i));
+ }
+ BOOST_CHECK_EQUAL(set.size(), nb_values);
+
+
+
+ serializer serial;
+ set.serialize(serial);
+
+ deserializer dserial(serial.str());
+ auto set_deserialized = decltype(set)::deserialize(dserial, true);
+ BOOST_CHECK(set == set_deserialized);
+
+ deserializer dserial2(serial.str());
+ set_deserialized = decltype(set)::deserialize(dserial2, false);
+ BOOST_CHECK(set_deserialized == set);
+}
BOOST_AUTO_TEST_SUITE_END()
diff --git a/tests/utils.h b/tests/utils.h
index a57282f..dcc790c 100644
--- a/tests/utils.h
+++ b/tests/utils.h
@@ -1,7 +1,7 @@
/**
* MIT License
*
- * Copyright (c) 2017 Tessil
+ * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
@@ -24,7 +24,6 @@
#ifndef TSL_UTILS_H
#define TSL_UTILS_H
-#include <boost/numeric/conversion/cast.hpp>
#include <cstddef>
#include <cstdint>
#include <functional>
@@ -33,6 +32,13 @@
#include <string>
#include <utility>
+#include "tsl/ordered_hash.h"
+
+#ifdef TSL_OH_NO_EXCEPTIONS
+#define TSL_OH_CHECK_THROW(S, E)
+#else
+#define TSL_OH_CHECK_THROW(S, E) BOOST_CHECK_THROW(S, E)
+#endif
template<typename T>
class identity_hash {
@@ -160,7 +166,7 @@ public:
template<>
inline std::int64_t utils::get_key<std::int64_t>(std::size_t counter) {
- return boost::numeric_cast<std::int64_t>(counter);
+ return tsl::detail_ordered_hash::numeric_cast<std::int64_t>(counter);
}
template<>
@@ -170,7 +176,7 @@ inline std::string utils::get_key<std::string>(std::size_t counter) {
template<>
inline move_only_test utils::get_key<move_only_test>(std::size_t counter) {
- return move_only_test(boost::numeric_cast<std::int64_t>(counter));
+ return move_only_test(tsl::detail_ordered_hash::numeric_cast<std::int64_t>(counter));
}
@@ -178,7 +184,7 @@ inline move_only_test utils::get_key<move_only_test>(std::size_t counter) {
template<>
inline std::int64_t utils::get_value<std::int64_t>(std::size_t counter) {
- return boost::numeric_cast<std::int64_t>(counter*2);
+ return tsl::detail_ordered_hash::numeric_cast<std::int64_t>(counter*2);
}
template<>
@@ -188,7 +194,7 @@ inline std::string utils::get_value<std::string>(std::size_t counter) {
template<>
inline move_only_test utils::get_value<move_only_test>(std::size_t counter) {
- return move_only_test(boost::numeric_cast<std::int64_t>(counter*2));
+ return move_only_test(tsl::detail_ordered_hash::numeric_cast<std::int64_t>(counter*2));
}
@@ -207,4 +213,107 @@ inline HMap utils::get_filled_hash_map(std::size_t nb_elements) {
return map;
}
+
+template<class T>
+struct is_pair: std::false_type {
+};
+
+template <class T1, class T2>
+struct is_pair<std::pair<T1, T2>>: std::true_type {
+};
+
+/**
+ * serializer helper to test serialize(...) and deserialize(...) functions
+ */
+class serializer {
+public:
+ serializer() {
+ m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
+ }
+
+ template<class T>
+ void operator()(const T& val) {
+ serialize_impl(val);
+ }
+
+ std::string str() const {
+ return m_ostream.str();
+ }
+
+private:
+ template<typename T, typename U>
+ void serialize_impl(const std::pair<T, U>& val) {
+ serialize_impl(val.first);
+ serialize_impl(val.second);
+ }
+
+ void serialize_impl(const std::string& val) {
+ serialize_impl(tsl::detail_ordered_hash::numeric_cast<std::uint64_t>(val.size()));
+ m_ostream.write(val.data(), val.size());
+ }
+
+ void serialize_impl(const move_only_test& val) {
+ serialize_impl(val.value());
+ }
+
+ template<class T,
+ typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
+ void serialize_impl(const T& val) {
+ m_ostream.write(reinterpret_cast<const char*>(&val), sizeof(val));
+ }
+
+private:
+ std::stringstream m_ostream;
+};
+
+class deserializer {
+public:
+ explicit deserializer(const std::string& init_str = ""): m_istream(init_str) {
+ m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
+ }
+
+ template<class T>
+ T operator()() {
+ return deserialize_impl<T>();
+ }
+
+private:
+ template<class T,
+ typename std::enable_if<is_pair<T>::value>::type* = nullptr>
+ T deserialize_impl() {
+ auto first = deserialize_impl<typename T::first_type>();
+ return std::make_pair(std::move(first), deserialize_impl<typename T::second_type>());
+ }
+
+ template<class T,
+ typename std::enable_if<std::is_same<std::string, T>::value>::type* = nullptr>
+ T deserialize_impl() {
+ const std::size_t str_size = tsl::detail_ordered_hash::numeric_cast<std::size_t>(deserialize_impl<std::uint64_t>());
+
+ // TODO std::string::data() return a const pointer pre-C++17. Avoid the inefficient double allocation.
+ std::vector<char> chars(str_size);
+ m_istream.read(chars.data(), str_size);
+
+ return std::string(chars.data(), chars.size());
+ }
+
+ template<class T,
+ typename std::enable_if<std::is_same<move_only_test, T>::value>::type* = nullptr>
+ move_only_test deserialize_impl() {
+ return move_only_test(deserialize_impl<std::int64_t>());
+ }
+
+ template<class T,
+ typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
+ T deserialize_impl() {
+ T val;
+ m_istream.read(reinterpret_cast<char*>(&val), sizeof(val));
+
+ return val;
+ }
+
+private:
+ std::stringstream m_istream;
+};
+
#endif
Debdiff
File lists identical (after any substitutions)
No differences were encountered in the control files