Map storing counters in a compact way. More...
#include <CountersMap.h>
Classes | |
class | const_iterator |
struct | CounterKey_t |
Structure with the index of the counter, split as needed. More... | |
Public Types | |
using | Key_t = KEY |
type of counter key in the map More... | |
using | Counter_t = COUNTER |
type of the single counter More... | |
using | Allocator_t = ALLOC |
type of the single counter More... | |
using | CounterMap_t = CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS > |
This class. More... | |
using | SubCounter_t = Counter_t |
Type of the subcounter (that is, the actual counter) More... | |
using | CounterBlock_t = typename Traits_t::CounterBlock_t |
using | BaseMap_t = typename Traits_t::template BaseMap_t< typename std::allocator_traits< Allocator_t >::template rebind_alloc< typename Traits_t::MapValue_t > > |
Type of the map used in the implementation. More... | |
using | value_type = std::pair< const Key_t, SubCounter_t > |
STL type definitions | |
using | mapped_type = SubCounter_t |
using | allocator_type = Allocator_t |
type of the single counter More... | |
Public Member Functions | |
CountersMap () | |
Default constructor (empty map) More... | |
CountersMap (Allocator_t alloc) | |
Constructor, specifies an allocator. More... | |
SubCounter_t | operator[] (Key_t key) const |
Read-only access to an element; returns 0 if no counter is present. More... | |
SubCounter_t | set (Key_t key, SubCounter_t value) |
Sets the specified counter to a count. More... | |
SubCounter_t | increment (Key_t key) |
Increments by 1 the specified counter. More... | |
SubCounter_t | decrement (Key_t key) |
Decrements by 1 the specified counter. More... | |
bool | empty () const |
Returns whether the map has no counters. More... | |
std::make_unsigned< Key_t >::type | n_counters () const |
Returns the number of allocated counters. More... | |
template<typename OALLOC > | |
bool | is_equal (const std::map< Key_t, SubCounter_t, std::less< Key_t >, OALLOC > &to, Key_t &first_difference) const |
Returns whether the counters in this map are equivalent to another. More... | |
template<typename OALLOC > | |
bool | is_equal (const std::map< Key_t, SubCounter_t, std::less< Key_t >, OALLOC > &to) const |
Returns whether the counters in this map are equivalent to another. More... | |
Iterators (experimental) | |
const_iterator | begin () const |
Returns an iterator to the begin of the counters. More... | |
const_iterator | end () const |
Returns an iterator past-the-end of the counters. More... | |
Static Public Attributes | |
static constexpr size_t | NCounters = Traits_t::NCounters |
Number of counters in one counter block. More... | |
static constexpr size_t | NSubcounters = NCounters * SUBCOUNTERS |
Number of subcounters in one counter block. More... | |
Protected Types | |
using | BlockKey_t = Key_t |
type of block key More... | |
using | CounterIndex_t = typename std::make_unsigned< Key_t >::type |
type of index in the block More... | |
Protected Member Functions | |
Counter_t | GetCounter (CounterKey_t key) const |
Returns the value of the counter at the specified split key. More... | |
SubCounter_t | GetSubCounter (CounterKey_t key) const |
Returns the value of the subcounter at the specified split key. More... | |
Counter_t & | GetOrCreateCounter (CounterKey_t key) |
Returns the counter at the specified split key. More... | |
Static Protected Member Functions | |
static CounterKey_t | SplitKey (Key_t key) |
Returns a split key corresponding to the specified key. More... | |
static const_iterator | make_const_iterator (typename BaseMap_t::const_iterator it, size_t ix) |
Creates a const_iterator (useful in derived classes) More... | |
Protected Attributes | |
BaseMap_t | counter_map |
the actual data structure for counters More... | |
Private Types | |
using | Traits_t = details::CountersMapTraits< KEY, COUNTER, SIZE > |
Set of data types pertaining this counter. More... | |
Private Member Functions | |
SubCounter_t | unchecked_set (CounterKey_t key, SubCounter_t delta) |
Sets the specified counter to a value (no check on value range) More... | |
SubCounter_t | unchecked_add (CounterKey_t key, SubCounter_t delta) |
Adds a delta to the specified counter (no check on underflow/overflow) More... | |
Map storing counters in a compact way.
KEY | the type of the key of the counters map |
COUNTER | the type of a basic counter (can be signed or unsigned) |
BLOCKSIZE | the number of counters in a cluster |
ALLOC | allocator for the underlying STL map |
SUBCOUNTERS | split each counter in subcounters (not implemented yet) |
This class is designed for the need of a vast number of counters with a integral numerical key, when the counter keys are usually clustered. This can be more or less efficient than a straight counters STL map according to how often the counters are clustered (if that does not happen often, CountersMap can have considerable memory overhead).
Counters are allocated in contiguous blocks of BLOCKSIZE counters. The selling point here is that a map node has some overhead (typically at least 3 pointers) and dynamically allocating it costs a lot (40 bytes have been observed). If you need a counter with a range of 100 (1 byte), that's far from optimal in many aspects (memory allocation also takes time).
The requirement of the key to be numerical is so that the concept of "next counter" is well defined and we can store contiguous counters in a fixed structure.
The idea behind subcounters is that you migt want to split a counter into subcounters to save memory if the maximum counter value is smaller than the range of the counter type. The implementation is delayed since in the end the same effect can be achieved by using a small counter type (e.g. signed char), unless the range is smaller that 16 (or 4, or 2), in which case the character can be split into bits. That will cause some overhead for increment and decrement instructions.
Definition at line 138 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::Allocator_t = ALLOC |
type of the single counter
Definition at line 149 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::allocator_type = Allocator_t |
type of the single counter
Definition at line 184 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::BaseMap_t = typename Traits_t::template BaseMap_t< typename std::allocator_traits<Allocator_t>::template rebind_alloc <typename Traits_t::MapValue_t> > |
Type of the map used in the implementation.
Definition at line 171 of file CountersMap.h.
|
protected |
type of block key
Definition at line 290 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::Counter_t = COUNTER |
type of the single counter
Definition at line 148 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::CounterBlock_t = typename Traits_t::CounterBlock_t |
Definition at line 165 of file CountersMap.h.
|
protected |
type of index in the block
Definition at line 292 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::CounterMap_t = CountersMap<KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS> |
This class.
Definition at line 152 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::Key_t = KEY |
type of counter key in the map
Definition at line 147 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::mapped_type = SubCounter_t |
Definition at line 183 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::SubCounter_t = Counter_t |
Type of the subcounter (that is, the actual counter)
Definition at line 162 of file CountersMap.h.
|
private |
Set of data types pertaining this counter.
Definition at line 144 of file CountersMap.h.
using lar::CountersMap< KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS >::value_type = std::pair<const Key_t, SubCounter_t> |
Definition at line 188 of file CountersMap.h.
|
inline |
|
inline |
Constructor, specifies an allocator.
Definition at line 198 of file CountersMap.h.
|
inline |
Returns an iterator to the begin of the counters.
Definition at line 511 of file CountersMap.h.
|
inline |
Decrements by 1 the specified counter.
key | key of the counter to be decreased |
Definition at line 505 of file CountersMap.h.
|
inline |
Returns whether the map has no counters.
Definition at line 245 of file CountersMap.h.
|
inline |
Returns an iterator past-the-end of the counters.
Definition at line 516 of file CountersMap.h.
|
inlineprotected |
Returns the value of the counter at the specified split key.
Definition at line 592 of file CountersMap.h.
|
inlineprotected |
Returns the counter at the specified split key.
Definition at line 601 of file CountersMap.h.
|
inlineprotected |
Returns the value of the subcounter at the specified split key.
Definition at line 367 of file CountersMap.h.
|
inline |
Increments by 1 the specified counter.
key | key of the counter to be increased |
Definition at line 500 of file CountersMap.h.
bool lar::CountersMap< K, C, S, A, SUB >::is_equal | ( | const std::map< Key_t, SubCounter_t, std::less< Key_t >, OALLOC > & | to, |
Key_t & | first_difference | ||
) | const |
Returns whether the counters in this map are equivalent to another.
to | a STL map |
first_difference | key of the first difference |
The maps are considered equal if all keys in each are present in the other, and their counters have the same value, with one exception: counters in CountersMap can not to exist in the other map, but only if their count is 0 (these should be plenty of them since counters are created in blocks).
If there is a key in one map but not in the other, first_difference stores that key; if a counter is present in both maps but with a different count, first_difference reports the key of that counter. If no difference is found, first_difference is left untouched.
Definition at line 522 of file CountersMap.h.
|
inline |
Returns whether the counters in this map are equivalent to another.
to | a STL map |
Definition at line 284 of file CountersMap.h.
|
inlinestaticprotected |
Creates a const_iterator (useful in derived classes)
Definition at line 379 of file CountersMap.h.
|
inline |
Returns the number of allocated counters.
Definition at line 249 of file CountersMap.h.
|
inline |
Read-only access to an element; returns 0 if no counter is present.
Definition at line 202 of file CountersMap.h.
|
inline |
Sets the specified counter to a count.
key | key of the counter to be increased |
value | count value to be set |
Given the complex underlying structure (especially when subcounters are involved), a special method is used to set the value of a counter. This is equivalent to map's operator[] in non-constant version, but the creation of a new counter is explicit.
Definition at line 495 of file CountersMap.h.
|
inlinestaticprotected |
Returns a split key corresponding to the specified key.
Definition at line 375 of file CountersMap.h.
|
private |
Adds a delta to the specified counter (no check on underflow/overflow)
Definition at line 631 of file CountersMap.h.
|
private |
Sets the specified counter to a value (no check on value range)
Definition at line 608 of file CountersMap.h.
|
protected |
the actual data structure for counters
Definition at line 359 of file CountersMap.h.
|
static |
Number of counters in one counter block.
Definition at line 156 of file CountersMap.h.
|
static |
Number of subcounters in one counter block.
Definition at line 159 of file CountersMap.h.