#include <IntrusiveHashMap.h>

Collaboration diagram for swoc::IntrusiveHashMap< H >:

Classes
struct	Bucket
	A bucket for the hash map. More...

struct	const_range
	A range of constant elements in the map. More...

struct	range

Public Types
enum	ExpansionPolicy { MANUAL , AVERAGE , MAXIMUM }
	When the hash table is expanded. More...

using	value_type = typename std::remove_pointer<typename std::remove_reference<decltype(H::next_ptr(nullptr))>::type>::type
	Type of elements in the map.

using	key_type = decltype(H::key_of(static_cast<value_type *>(nullptr)))
	Key type for the elements.

using	hash_id = decltype(H::hash_of(H::key_of(static_cast<value_type *>(nullptr))))
	The numeric hash ID computed from a key.

using	iterator = typename List::iterator

using	const_iterator = typename List::const_iterator

Public Member Functions
	IntrusiveHashMap (size_t n=DEFAULT_BUCKET_COUNT)

	IntrusiveHashMap (self_type &&that)=default
	Move constructor.

self_type &	clear ()

iterator	begin ()
	First element.

const_iterator	begin () const
	First element.

iterator	end ()
	Past last element.

const_iterator	end () const
	Past last element.

void	insert (value_type *v)

const_iterator	find (key_type key) const

iterator	find (key_type key)

const_iterator	find (value_type const *v) const

iterator	find (value_type *v)

const_range	equal_range (key_type key) const

range	equal_range (key_type key)

iterator	iterator_for (value_type *v)

const_iterator	iterator_for (const value_type *v) const

iterator	erase (iterator const &loc)

iterator	erase (range const &r)
	Remove all elements in the `range` r.

iterator	erase (iterator const &start, iterator const &limit)
	Remove all elements in the range (start, limit].

bool	erase (value_type *value)

template<typename F>
self_type &	apply (F &&f)

void	expand ()

size_t	count () const
	Number of elements in the map.

size_t	bucket_count () const
	Number of buckets in the array.

self_type &	set_expansion_policy (ExpansionPolicy policy)
	Set the expansion policy to policy.

ExpansionPolicy	get_expansion_policy () const
	Get the current expansion policy.

self_type &	set_expansion_limit (size_t n)
	Set the limit value for the expansion policy.

size_t	get_expansion_limit () const
	Set the limit value for the expansion policy.

template<typename F>
auto	apply (F &&f) -> self_type &

Static Public Attributes
static size_t constexpr	DEFAULT_BUCKET_COUNT = 7
	The default starting number of buckets.

static size_t constexpr	DEFAULT_EXPANSION_LIMIT = 4
	The default expansion policy limit.

static ExpansionPolicy constexpr	DEFAULT_EXPANSION_POLICY = AVERAGE
	Expansion policy if not specified in constructor.

Protected Types
using	List = IntrusiveDList<H>

using	Table = std::vector<Bucket>
	The type of storage for the buckets.

Protected Member Functions
Bucket *	bucket_for (key_type key)

	IntrusiveHashMap (const IntrusiveHashMap &)=delete

IntrusiveHashMap &	operator= (const IntrusiveHashMap &)=delete

Protected Attributes
List	_list
	Elements in the table.

Table	_table
	Array of buckets.

IntrusiveDList< typename Bucket::Linkage >	_active_buckets
	List of non-empty buckets.

ExpansionPolicy	_expansion_policy {DEFAULT_EXPANSION_POLICY}
	When to exand the table.

size_t	_expansion_limit {DEFAULT_EXPANSION_LIMIT}
	Limit value for expansion.

Static Protected Attributes
static constexpr std::array< size_t, 29 >	PRIME

Detailed Description

template<typename H>
class swoc::IntrusiveHashMap< H >

Intrusive Hash Table.

Values stored in this container are not destroyed when the container is destroyed or removed from the container. They must be released by the client.

Duplicate keys are allowed. Clients must walk the list for multiple entries.

See also: Location::operator++()

By default the table automatically expands to limit the average chain length. This can be tuned. If set to MANUAL then the table will expand only when explicitly requested to do so by the client.

See also: ExpansionPolicy; setExpansionPolicy(); setExpansionLimit(); expand()

The hash table is configured by a descriptor class. This must contain the following members

The static method key_type key_of(value_type *) which returns the key for an instance of value_type.
The static method bool equal(key_type lhs, key_type rhs) which checks if two instances of Key are the same.
The static method hash_id hash_of(key_type) which computes the hash value of the key. ID must a numeric type.
The static method value_type *& next_ptr(value_type *) which returns a reference to a forward pointer.
The static method value_type *& prev_ptr(value_type *) which returns a reference to a backwards pointer.

These are the required members, it is permitted to have other methods (if the descriptor is used for other purposes) or to provide overloads of the methods. Note this is compatible with IntrusiveDList.

Several internal types are deduced from these arguments.

Key is the return type of key_of and represents the key that distinguishes instances of value_type. Two instances of value_type are considered the same if their respective Key values are equal. Key is presumed cheap to copy. If the underlying key is not a simple type then Key should be a constant pointer or a constant reference. The hash table will never attempt to modify a key.

ID The numeric type that is the hash value for an instance of Key.

Example for HttpServerSession keyed by the origin server IP address.

struct Descriptor {
  static sockaddr const* key_of(HttpServerSession const* value) { return &value->ip.sa }
  static bool equal(sockaddr const* lhs, sockaddr const* rhs) { return ats_ip_eq(lhs, rhs); }
  static uint32_t hash_of(sockaddr const* key) { return ats_ip_hash(key); }
  static HttpServerSession *& next_ptr(HttpServerSession * ssn) { return ssn->_next; }
  static HttpServerSession *& prev_ptr(HttpServerSession * ssn) { return ssn->_prev; }
};
using Table = IntrusiveHashMap<Descriptor>;

Definition at line 74 of file IntrusiveHashMap.h.

Member Typedef Documentation

◆ const_iterator

template<typename H>

using swoc::IntrusiveHashMap< H >::const_iterator = typename List::const_iterator

Definition at line 138 of file IntrusiveHashMap.h.

◆ hash_id

template<typename H>

using swoc::IntrusiveHashMap< H >::hash_id = decltype(H::hash_of(H::key_of(static_cast<value_type *>(nullptr))))

The numeric hash ID computed from a key.

Definition at line 83 of file IntrusiveHashMap.h.

◆ iterator

template<typename H>

using swoc::IntrusiveHashMap< H >::iterator = typename List::iterator

Definition at line 137 of file IntrusiveHashMap.h.

◆ key_type

template<typename H>

using swoc::IntrusiveHashMap< H >::key_type = decltype(H::key_of(static_cast<value_type *>(nullptr)))

Key type for the elements.

Definition at line 81 of file IntrusiveHashMap.h.

◆ List

template<typename H>

using swoc::IntrusiveHashMap< H >::List = IntrusiveDList<H>

protected

List of elements. All table elements are in this list. The buckets reference their starting element in the list, or nothing if no elements are in that bucket.

Definition at line 97 of file IntrusiveHashMap.h.

◆ Table

template<typename H>

using swoc::IntrusiveHashMap< H >::Table = std::vector<Bucket>

protected

The type of storage for the buckets.

Definition at line 289 of file IntrusiveHashMap.h.

◆ value_type

template<typename H>

using swoc::IntrusiveHashMap< H >::value_type = typename std::remove_pointer<typename std::remove_reference<decltype(H::next_ptr(nullptr))>::type>::type

Type of elements in the map.

Definition at line 79 of file IntrusiveHashMap.h.

Member Enumeration Documentation

◆ ExpansionPolicy

template<typename H>

enum swoc::IntrusiveHashMap::ExpansionPolicy

When the hash table is expanded.

Enumerator
MANUAL	Client must explicitly expand the table.
AVERAGE	Table expands if average chain length exceeds limit. [default].
MAXIMUM	Table expands if any chain length exceeds limit.

Definition at line 86 of file IntrusiveHashMap.h.

Constructor & Destructor Documentation

◆ IntrusiveHashMap()

template<typename H>

swoc::IntrusiveHashMap< H >::IntrusiveHashMap ( size_t n = DEFAULT_BUCKET_COUNT )

Construct, starting with
buckets. This doubles as the default constructor.

Definition at line 384 of file IntrusiveHashMap.h.

Member Function Documentation

◆ apply() [1/2]

template<typename H>

template<typename F>

self_type & swoc::IntrusiveHashMap< H >::apply ( F && f )

Apply F(value_type&) to every element in the hash map.

This is similar to a range for loop except the iteration is done in a way where destruction or alternation of the element does not affect the iterator. Primarily this is useful for delete to clean up the elements but it can have other uses.

Template Parameters

F	A functional object of the form `void F(value_type&)`

Parameters

f	The function to apply.

Returns

◆ apply() [2/2]

template<typename H>

template<typename F>

auto swoc::IntrusiveHashMap< H >::apply ( F && f ) -> self_type &

Definition at line 631 of file IntrusiveHashMap.h.

◆ begin() [1/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::begin ( )

First element.

Definition at line 398 of file IntrusiveHashMap.h.

◆ begin() [2/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::begin ( ) const

First element.

Definition at line 404 of file IntrusiveHashMap.h.

◆ bucket_count()

template<typename H>

size_t swoc::IntrusiveHashMap< H >::bucket_count ( ) const

Number of buckets in the array.

Definition at line 664 of file IntrusiveHashMap.h.

◆ bucket_for()

template<typename H>

auto swoc::IntrusiveHashMap< H >::bucket_for ( key_type key )

protected

Definition at line 392 of file IntrusiveHashMap.h.

◆ clear()

template<typename H>

auto swoc::IntrusiveHashMap< H >::clear ( )

Remove all values from the table.

The values are not cleaned up. The values are not touched in this method, therefore it is safe to destroy them first and then clear this table.

Definition at line 422 of file IntrusiveHashMap.h.

◆ count()

template<typename H>

size_t swoc::IntrusiveHashMap< H >::count ( ) const

Number of elements in the map.

Definition at line 658 of file IntrusiveHashMap.h.

◆ end() [1/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::end ( )

Past last element.

Definition at line 410 of file IntrusiveHashMap.h.

◆ end() [2/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::end ( ) const

Past last element.

Definition at line 416 of file IntrusiveHashMap.h.

◆ equal_range() [1/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::equal_range ( key_type key )

Definition at line 452 of file IntrusiveHashMap.h.

◆ equal_range() [2/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::equal_range ( key_type key ) const

Find the range of objects with keys equal to key.

Returns: A iterator pair of [first, last) items with equal keys.

Definition at line 466 of file IntrusiveHashMap.h.

◆ erase() [1/4]

template<typename H>

auto swoc::IntrusiveHashMap< H >::erase ( iterator const & loc )

Remove the value at loc from the table.

Note: This does not clean up the removed elements. Use carefully to avoid leaks.

Returns: An iterator the next value past loc. [STL compatibility]

Definition at line 544 of file IntrusiveHashMap.h.

◆ erase() [2/4]

template<typename H>

auto swoc::IntrusiveHashMap< H >::erase	(	iterator const &	start,
		iterator const &	limit )

Remove all elements in the range (start, limit].

Definition at line 576 of file IntrusiveHashMap.h.

◆ erase() [3/4]

template<typename H>

auto swoc::IntrusiveHashMap< H >::erase ( range const & r )

Remove all elements in the range r.

Definition at line 597 of file IntrusiveHashMap.h.

◆ erase() [4/4]

template<typename H>

bool swoc::IntrusiveHashMap< H >::erase ( value_type * value )

Remove a value from the container. value is checked for being a member of the container.

Returns: true if value was in the container and removed, false if it was not in the container.

Definition at line 565 of file IntrusiveHashMap.h.

◆ expand()

template<typename H>

void swoc::IntrusiveHashMap< H >::expand ( )

Expand the hash if needed.

Useful primarily when the expansion policy is set to MANUAL.

Definition at line 637 of file IntrusiveHashMap.h.

◆ find() [1/4]

template<typename H>

auto swoc::IntrusiveHashMap< H >::find ( key_type key )

Definition at line 434 of file IntrusiveHashMap.h.

◆ find() [2/4]

template<typename H>

auto swoc::IntrusiveHashMap< H >::find ( key_type key ) const

Find an element with a key equal to key.

Returns: A element with a matching key, or the end iterator if not found.

Definition at line 446 of file IntrusiveHashMap.h.

◆ find() [3/4]

template<typename H>

auto swoc::IntrusiveHashMap< H >::find ( value_type * v )

Definition at line 484 of file IntrusiveHashMap.h.

◆ find() [4/4]

template<typename H>

auto swoc::IntrusiveHashMap< H >::find ( value_type const * v ) const

Get an iterator for an existing value v.

Returns: An iterator that references v, or the end iterator if v is not in the table.

Definition at line 491 of file IntrusiveHashMap.h.

◆ get_expansion_limit()

template<typename H>

size_t swoc::IntrusiveHashMap< H >::get_expansion_limit ( ) const

Set the limit value for the expansion policy.

Definition at line 690 of file IntrusiveHashMap.h.

◆ get_expansion_policy()

template<typename H>

auto swoc::IntrusiveHashMap< H >::get_expansion_policy ( ) const

Get the current expansion policy.

Definition at line 677 of file IntrusiveHashMap.h.

◆ insert()

template<typename H>

void swoc::IntrusiveHashMap< H >::insert ( value_type * v )

Insert a value in to the table. The value must NOT already be in a table of this type.

Note: The value itself is put in the table, not a copy.

Definition at line 497 of file IntrusiveHashMap.h.

◆ iterator_for() [1/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::iterator_for ( const value_type * v ) const

Definition at line 472 of file IntrusiveHashMap.h.

◆ iterator_for() [2/2]

template<typename H>

auto swoc::IntrusiveHashMap< H >::iterator_for ( value_type * v )

Get an iterator for the value v.

This is a bit obscure but needed in certain cases. Because the interface assumes iterators are always valid this avoid containment checks, which is useful if v is already known to be in the container.

Definition at line 478 of file IntrusiveHashMap.h.

◆ set_expansion_limit()

template<typename H>

auto swoc::IntrusiveHashMap< H >::set_expansion_limit ( size_t n )

Set the limit value for the expansion policy.

Definition at line 683 of file IntrusiveHashMap.h.

◆ set_expansion_policy()

template<typename H>

auto swoc::IntrusiveHashMap< H >::set_expansion_policy ( ExpansionPolicy policy )

Set the expansion policy to policy.

Definition at line 670 of file IntrusiveHashMap.h.

Member Data Documentation

◆ _active_buckets

template<typename H>

IntrusiveDList<typename Bucket::Linkage> swoc::IntrusiveHashMap< H >::_active_buckets

protected

List of non-empty buckets.

Definition at line 295 of file IntrusiveHashMap.h.

◆ _expansion_limit

template<typename H>

size_t swoc::IntrusiveHashMap< H >::_expansion_limit {DEFAULT_EXPANSION_LIMIT}

protected

Limit value for expansion.

Definition at line 300 of file IntrusiveHashMap.h.

◆ _expansion_policy

template<typename H>

ExpansionPolicy swoc::IntrusiveHashMap< H >::_expansion_policy {DEFAULT_EXPANSION_POLICY}

protected

When to exand the table.

Definition at line 299 of file IntrusiveHashMap.h.

◆ _list

template<typename H>

List swoc::IntrusiveHashMap< H >::_list

protected

Elements in the table.

Definition at line 291 of file IntrusiveHashMap.h.

◆ _table

template<typename H>

Table swoc::IntrusiveHashMap< H >::_table

protected

Array of buckets.

Definition at line 292 of file IntrusiveHashMap.h.

◆ DEFAULT_BUCKET_COUNT

template<typename H>

size_t constexpr swoc::IntrusiveHashMap< H >::DEFAULT_BUCKET_COUNT = 7

staticconstexpr

The default starting number of buckets.

POOMA.

Definition at line 131 of file IntrusiveHashMap.h.

◆ DEFAULT_EXPANSION_LIMIT

template<typename H>

size_t constexpr swoc::IntrusiveHashMap< H >::DEFAULT_EXPANSION_LIMIT = 4

staticconstexpr

The default expansion policy limit.

Value from previous version.

Definition at line 133 of file IntrusiveHashMap.h.

◆ DEFAULT_EXPANSION_POLICY

template<typename H>

ExpansionPolicy constexpr swoc::IntrusiveHashMap< H >::DEFAULT_EXPANSION_POLICY = AVERAGE

staticconstexpr

Expansion policy if not specified in constructor.

Definition at line 135 of file IntrusiveHashMap.h.

◆ PRIME

template<typename H>

std::array<size_t, 29> swoc::IntrusiveHashMap< H >::PRIME

staticconstexprprotected

Initial value:

= {
    {1, 3, 7, 13, 31, 61, 127, 251, 509, 1021,
     2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573,
     2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909}
  }

Definition at line 308 of file IntrusiveHashMap.h.

The documentation for this class was generated from the following file:

IntrusiveHashMap.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ hash_id

◆ iterator

◆ key_type

◆ List

◆ Table

◆ value_type

Member Enumeration Documentation

◆ ExpansionPolicy

Constructor & Destructor Documentation

◆ IntrusiveHashMap()

Member Function Documentation

◆ apply() [1/2]

◆ apply() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ bucket_count()

◆ bucket_for()

◆ clear()

◆ count()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/4]

◆ erase() [2/4]

◆ erase() [3/4]

◆ erase() [4/4]

◆ expand()

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ get_expansion_limit()

◆ get_expansion_policy()

◆ insert()

◆ iterator_for() [1/2]

◆ iterator_for() [2/2]

◆ set_expansion_limit()

◆ set_expansion_policy()

Member Data Documentation

◆ _active_buckets

◆ _expansion_limit

◆ _expansion_policy

◆ _list

◆ _table

◆ DEFAULT_BUCKET_COUNT

◆ DEFAULT_EXPANSION_LIMIT

◆ DEFAULT_EXPANSION_POLICY

◆ PRIME