15 #ifndef _DATAT_BITS_INCLUDE_TAG
16 #error Must only be included from sag_connectivity_cpp.hpp, use that instead
36 class map_t:
protected sag_underlying_map_t
41 static size_t MIN_CAPACITY() {
return 8; }
43 typedef sag_underlying_map_table_entry_t item_t;
44 typedef int64_t hash_t;
47 template<
typename DATA>
61 template<
typename DATA,
typename UNDERLYING,
typename PAIR>
62 struct _iterator:
public std::iterator<std::bidirectional_iterator_tag, DATA>
66 typedef PAIR element_t;
68 _iterator(): tabledata(0), capacity(0), offs(0) {}
69 _iterator(
const UNDERLYING &tabledata,
size_t capacity, int64_t offs,
bool stepToItem=
false)
70 : tabledata(tabledata), capacity(capacity), offs(offs)
72 if (!valid() && stepToItem) {
77 iterator &operator--()
86 iterator operator--(
int)
92 iterator &operator++()
94 if (offs < capacity) {
101 iterator operator++(
int)
108 DATA &key()
const {
return static_cast<DATA&
>(tabledata[offs].key); }
109 DATA &value()
const {
return static_cast<DATA&
>(tabledata[offs].value); }
113 bool b = offs == other.offs;
121 element_t &operator*()
const
123 return reinterpret_cast<element_t &
>(tabledata[offs]);
125 element_t *operator->()
const
127 return reinterpret_cast<element_t *
>(tabledata + offs);
133 return offs >= capacity || offs < 0 || tabledata[offs].hash > 1 ||
SAG_DATA_EMPTY != tabledata[offs].key.tag;
135 UNDERLYING tabledata;
154 explicit map_t(
size_t n);
168 swap(std::move(tmp));
170 swap(std::move(other));
177 swap(std::move(other));
181 map_t(std::initializer_list<std::pair<data_t,data_t>> l)
184 for (
auto it = l.begin(); it != l.end(); ++it) {
185 insert(std::make_pair(it->first.copy(), it->second.copy()));
192 std::swap(table, other.table);
199 for (const_iterator it =
begin(); it !=
end(); ++it) {
200 newmap.
insert(std::make_pair(it->first.copy(), it->second.copy()));
215 if (
size() != other.
size())
return false;
216 for (const_iterator it =
begin(); it !=
end(); ++it) {
217 const_iterator jt = other.
find(it.key());
218 if (jt == other.
end())
return false;
219 if (it.value() != jt.value())
return false;
232 iterator
begin() {
return iterator(table?table->table:0, table?table->capacity:0, 0,
true); }
234 iterator
end() {
return iterator(table?table->table:0, table?table->capacity:0, table?table->capacity:0,
false); }
236 const_iterator
begin()
const {
return const_iterator(table?table->table:0, table?table->capacity:0, 0,
true); }
238 const_iterator
end()
const {
return const_iterator(table?table->table:0, table?table->capacity:0, table?table->capacity:0,
false); }
240 const_iterator
cbegin()
const {
return const_iterator(table?table->table:0, table?table->capacity:0, 0,
true); }
242 const_iterator
cend()
const {
return const_iterator(table?table->table:0, table?table->capacity:0, table?table->capacity:0,
false); }
245 size_t size()
const {
return table?table->count:0; }
254 return maybe_insert(std::pair<data_t&&,data_t&&>(std::move(k),
data_t())).first->second;
261 return maybe_insert(std::pair<const data_t&,const data_t&>(k,
data_t())).first->second;
267 const_iterator it =
find(k);
269 throw std::runtime_error(
"Element not in map");
293 std::pair<iterator, bool>
insert(
const std::pair<data_t&&, data_t&&> &v);
307 return insert(std::make_pair(std::move(k), std::move(v)));
312 std::pair<iterator, bool>
insert(
const std::pair<data_t&&, data_t&&> &v, hash_t hash);
323 void erase(iterator it);
336 void resize(
size_t newsize);
339 void really_insert(item_t &item,
const std::pair<data_t&&, data_t&&> &v, hash_t hash);
341 std::pair<iterator, bool> maybe_insert(
const std::pair<const data_t&, const data_t&> &v);
343 std::pair<iterator, bool> maybe_insert(
const std::pair<data_t&&, data_t&&> &v);
345 std::pair<map_t::const_iterator, map_t::const_iterator> find_for_insert(
const data_t &k, hash_t hash)
const;
348 bool empty(
const item_t &item)
const {
return 0 == item.hash &&
SAG_DATA_EMPTY == item.key.tag; }
350 bool empty(
const const_iterator::element_t &item)
const {
return 0 == item.hash &&
SAG_DATA_EMPTY == item.first.tag; }
352 bool hole(
const item_t &item)
const {
return 1 == item.hash &&
SAG_DATA_EMPTY == item.key.tag; }
354 bool hole(
const const_iterator::element_t &item)
const {
return 1 == item.hash &&
SAG_DATA_EMPTY == item.first.tag; }
356 bool live(
const item_t &item)
const {
return SAG_DATA_EMPTY != item.key.tag || item.hash > 1; }
358 bool live(
const const_iterator::element_t &item)
const {
return SAG_DATA_EMPTY != item.first.tag || item.hash > 1; }
361 size_t index(hash_t hash)
const
363 if (!table)
return 0;
364 return table->capacity ? hash % table->capacity : 0;
367 #ifdef _SAG_INTERNAL_UNSUPPORTED_DEBUG
369 SAG_CONNECTIVITY_API
static size_t clashes;
370 SAG_CONNECTIVITY_API
static size_t inserts;
371 SAG_CONNECTIVITY_API
static double resizeUsage;
372 SAG_CONNECTIVITY_API
static size_t resizes;
373 SAG_CONNECTIVITY_API
static size_t max_lookup_clash;
374 SAG_CONNECTIVITY_API
static size_t lookups;
375 SAG_CONNECTIVITY_API
static size_t lookup_clashes;
376 static double getInsertClashRatio() {
return (
double)clashes/(double)inserts; }
377 static double getAverageResizeRatio() {
return resizeUsage/(double)resizes; }
378 static void resetCounters() { clashes = inserts = resizeUsage = resizes = 0; }
379 static double getAverageLookupProbes() {
return 1.0+(double)lookup_clashes/(
double)lookups; }
380 static size_t getMaxLookupProbes() {
return 1+max_lookup_clash; }
iterator find(const data_t &k)
Searches the map for an item with the given key and returns an iterator to that position in the map...
std::pair< iterator, bool > insert(const std::pair< data_t &&, data_t && > &v)
Insert a new key/value pair into the map.
const data_t & operator[](const data_t &k) const
Return a reference to the item with the given key.
Definition: map_t.hpp:265
~map_t()
Free the underlying map contents.
Definition: map_t.hpp:157
A container for an payload and associated metadata.
Definition: message.hpp:27
A map class which implements many of the functions on std::map.
Definition: map_t.hpp:36
map_t(std::initializer_list< std::pair< data_t, data_t >> l)
Initialiser list construction.
Definition: map_t.hpp:181
iterator end()
Forward iterator end.
Definition: map_t.hpp:234
pair< const data_t > const_element
The type of an element in a const map.
Definition: map_t.hpp:146
data_t & operator[](data_t &&k)
Return a reference to the item with the given key.
Definition: map_t.hpp:252
const_iterator end() const
Forward const_iterator end.
Definition: map_t.hpp:238
_iterator< const data_t, sag_underlying_map_table_entry_t const *, const pair< const data_t > > const_iterator
The type of iterators on const maps.
Definition: map_t.hpp:142
std::pair< iterator, bool > insert(data_t &&k, data_t &&v)
Insert a new key/value pair into the map.
Definition: map_t.hpp:306
size_t size() const
Returns the number of key/value pairs in the map.
Definition: map_t.hpp:245
void swap(map_t &&other)
Swap the contents of this map and other.
Definition: map_t.hpp:190
const_iterator cbegin() const
Forward const_iterator begin.
Definition: map_t.hpp:240
map_t(map_t &&other)
Move constructor.
Definition: map_t.hpp:174
bool operator!=(const map_t &other) const
Returns false if this map deep-equals other.
Definition: map_t.hpp:225
Forward/reverse and const/non-const iterators are implemented using this class.
Definition: map_t.hpp:62
_iterator< data_t, sag_underlying_map_table_entry_t *, pair< data_t > > iterator
The type of iterators on mutable maps.
Definition: map_t.hpp:140
map_t copy() const
Return a deep copy of this map.
Definition: map_t.hpp:196
void clear()
Empty the map and free the underlying data.
iterator begin()
Forward iterator begin.
Definition: map_t.hpp:232
const_iterator cend() const
Forward const_iterator end.
Definition: map_t.hpp:242
pair< data_t > element
The type of an element in a mutable map.
Definition: map_t.hpp:144
bool empty() const
Returns true if the map is empty (size() == 0)
Definition: map_t.hpp:248
size_t erase(const data_t &k)
Remove the item with the specified key.
bool operator==(const map_t &other) const
Returns true if this map deep-equals other.
Definition: map_t.hpp:213
A variant type which can be one of the following:
Definition: data_t.hpp:42
const_iterator begin() const
Forward const_iterator begin.
Definition: map_t.hpp:236
map_t()
Construct an empty map.
Definition: map_t.hpp:149
data_t & operator[](const data_t &k)
Return a reference to the item with the given key.
Definition: map_t.hpp:259
Empty.
Definition: sag_connectivity_c.h:36
map_t & operator=(map_t &&other)
Move assignment.
Definition: map_t.hpp:164