roo_collections Namespace Reference

Data Structures
struct	DefaultHashFn
struct	DefaultHashFn< const char * >
struct	DefaultHashFn< SmallString< N > >
struct	DefaultHashFn< std::string >
struct	DefaultHashFn<::roo::string_view >
struct	DefaultKeyFn
class	FlatSmallHashMap
	Flat, memory-conscious hash map optimized for small collections. More...
class	FlatSmallHashtable
	Flat, memory-conscious hash table optimized for small collections. More...
struct	has_is_transparent
struct	has_is_transparent< _Func, _SfinaeType, std::void_t< typename _Func::is_transparent > >
struct	KeyCovert
struct	KeyCovert< std::string, ::roo::string_view >
struct	MapKeyFn
class	SmallString
	Fixed-capacity string stored inline (no heap allocation). More...
struct	TransparentEq
struct	TransparentStringHashFn

Typedefs
template<typename Value >
using	FlatSmallStringHashMap = FlatSmallHashMap< std::string, Value, TransparentStringHashFn, TransparentEq >
	String-specialized flat hash map with heterogeneous lookup support.
template<typename Key , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>
using	FlatSmallHashSet = FlatSmallHashtable< Key, Key, HashFn, DefaultKeyFn< Key >, KeyCmpFn >
	Flat, memory-conscious hash set optimized for small collections.
using	FlatSmallStringHashSet = FlatSmallHashtable< std::string, std::string, TransparentStringHashFn, TransparentEq, DefaultKeyFn< std::string > >
	String-specialized flat hash set with heterogeneous lookup support.
template<typename _Func , typename _SfinaeType >
using	has_is_transparent_t = typename has_is_transparent< _Func, _SfinaeType >::type

Functions
uint16_t	fastmod (uint32_t n, int idx)
int	initialCapacityIdx (uint16_t size_hint)
static uint32_t	murmur_32_scramble (uint32_t k)
uint32_t	murmur3_32 (const void *key, size_t len, uint32_t seed)
	Computes 32-bit MurmurHash3 of a binary buffer.

Variables
static constexpr float	kMaxFillRatio = 0.73
static constexpr uint16_t	kRadkePrimes []
static constexpr uint64_t	kRadkePrimeInverts []

Typedef Documentation

FlatSmallHashSet

template<typename Key , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashSet = typedef FlatSmallHashtable<Key, Key, HashFn, DefaultKeyFn<Key>, KeyCmpFn>

Flat, memory-conscious hash set optimized for small collections.

Stores keys in a single backing array and provides average constant-time lookup/insert/erase.

Template Parameters

Key	Stored key type.
HashFn	Hash function type.
KeyCmpFn	Equality predicate type.

Definition at line 23 of file flat_small_hash_set.h.

FlatSmallStringHashMap

template<typename Value >

using roo_collections::FlatSmallStringHashMap = typedef FlatSmallHashMap<std::string, Value, TransparentStringHashFn, TransparentEq>

String-specialized flat hash map with heterogeneous lookup support.

Accepts std::string, const char*, roo::string_view, and Arduino String (when available) for lookup operations.

Definition at line 191 of file flat_small_hash_map.h.

FlatSmallStringHashSet

using roo_collections::FlatSmallStringHashSet = typedef FlatSmallHashtable<std::string, std::string, TransparentStringHashFn, TransparentEq, DefaultKeyFn<std::string> >

String-specialized flat hash set with heterogeneous lookup support.

Accepts std::string, const char*, roo::string_view, and Arduino String (when available) for lookup operations.

Definition at line 30 of file flat_small_hash_set.h.

has_is_transparent_t

template<typename _Func , typename _SfinaeType >

using roo_collections::has_is_transparent_t = typedef typename has_is_transparent<_Func, _SfinaeType>::type

Definition at line 159 of file flat_small_hashtable.h.

Function Documentation

fastmod()

uint16_t roo_collections::fastmod ( uint32_t  n, int  idx  )

inline

Definition at line 57 of file flat_small_hashtable.h.

References kRadkePrimeInverts, and kRadkePrimes.

Referenced by roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::erase(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::erase(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::find(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::find(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::insert(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup(), and roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup().

initialCapacityIdx()

int roo_collections::initialCapacityIdx ( uint16_t  size_hint )

inline

Definition at line 62 of file flat_small_hashtable.h.

References kMaxFillRatio, and kRadkePrimes.

Referenced by roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::compact().

murmur3_32()

uint32_t roo_collections::murmur3_32	(	const void *	key,
		size_t	len,
		uint32_t	seed
	)

Computes 32-bit MurmurHash3 of a binary buffer.

Parameters

key	Pointer to the first byte of the buffer.
len	Number of bytes to hash.
seed	Hash seed.

Returns

32-bit hash value.

Definition at line 12 of file hash.cpp.

References murmur_32_scramble().

Referenced by roo_collections::DefaultHashFn<::roo::string_view >::operator()().

murmur_32_scramble()

static uint32_t roo_collections::murmur_32_scramble ( uint32_t  k )

inlinestatic

Definition at line 5 of file hash.cpp.

Referenced by murmur3_32().

Variable Documentation

kMaxFillRatio

constexpr float roo_collections::kMaxFillRatio = 0.73

staticconstexpr

Definition at line 36 of file flat_small_hashtable.h.

Referenced by initialCapacityIdx().

kRadkePrimeInverts

constexpr uint64_t roo_collections::kRadkePrimeInverts[]

staticconstexpr

Initial value:

= {
    0x281474976700001, 0xD5C26DD2255556, 0x5B9C78357DB6DC, 0x1745d1745d18,
    0x84210842109,     0x456c797dd4a,    0x20408102041,    0x105197f7d74,
    0x824a4e60b4,      0x4050647d9e,     0x202428adc4,     0x100501907e,
    0x800400201,       0x401506e65,      0x200c44b25,      0x100110122}

Definition at line 50 of file flat_small_hashtable.h.

Referenced by fastmod().

kRadkePrimes

constexpr uint16_t roo_collections::kRadkePrimes[]

staticconstexpr

Initial value:

= {
    0x1,   0x3,   0x7,   0xb,   0x1f,   0x3b,   0x7f,   0xfb,
    0x1f7, 0x3fb, 0x7f7, 0xffb, 0x1fff, 0x3feb, 0x7fcf, 0xffef}

Definition at line 43 of file flat_small_hashtable.h.

Referenced by roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::clear(), fastmod(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::FlatSmallHashtable(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::FlatSmallHashtable(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::ht_len(), initialCapacityIdx(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::insert(), and roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::operator=().