hashtables.h File Reference

#include <cstddef>
#include <unordered_map>
#include <wx/string.h>

Go to the source code of this file.

Classes
struct	iequal_to
	Equality test for "const char*" type used in very specialized KEYWORD_MAP below. More...
struct	fnv_1a
	Very fast and efficient hash function for "const char*" type, used in specialized KEYWORD_MAP below. More...

Typedefs
typedef std::unordered_map< const char *, int, fnv_1a, iequal_to >	KEYWORD_MAP
	A hashtable made of a const char* and an int.

Functions
std::size_t	KiHashCombine (std::size_t aSeed, std::size_t aValue)
	Fold aValue into the running hash aSeed using the well-known Boost hash_combine mixing step.

Typedef Documentation

KEYWORD_MAP

typedef std::unordered_map< const char*, int, fnv_1a, iequal_to > KEYWORD_MAP

A hashtable made of a const char* and an int.

Note

The use of this type outside very specific circumstances is foolish since there is no storage provided for the actual C string itself.

This type assumes use with type KEYWORD that is created by CMake and that table creates constant storage for C strings (and pointers to those C strings). Here we are only interested in the C strings themselves and only the pointers are duplicated within the hashtable. If the strings were not constant and fixed, this type would not work. Also note that normally a hashtable (i.e. unordered_map) using a const char* key would simply compare the 32 bit or 64 bit pointers themselves, rather than the C strings which they are known to point to in this context. I force the latter behavior by supplying both "hash" and "equality" overloads to the hashtable (unordered_map) template.

Author

Dick Hollenbeck

Definition at line 93 of file hashtables.h.

Function Documentation

KiHashCombine()

std::size_t KiHashCombine ( std::size_t aSeed, std::size_t aValue )

inline

Fold aValue into the running hash aSeed using the well-known Boost hash_combine mixing step.

The magic constant is the 32-bit fractional part of the golden ratio; the shifts spread bits so combining values is order- sensitive and collisions stay rare.

Used to build content hashes that must stay stable across runs (e.g. the diff-engine summary strings), so the mixing formula must not change once persisted output depends on it.

Definition at line 42 of file hashtables.h.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and KICAD_DIFF::PCB_DIFFER::Diff().