PDStaticHash

A (very) simple hash table implementation. More...

Files
file	PDStaticHash.h

Macros
#define	static_hash_idx(mask, shift, key)   (((long)key ^ ((long)key >> shift)) & mask)
#define	PDStaticHashIdx(stha, key)   static_hash_idx(stha->mask, stha->shift, key)
#define	PDStaticHashValueForHash(stha, hash)   stha->table[hash]
#define	PDStaticHashValueForKey(stha, key)   stha->table[PDStaticHashIdx(stha, key)]
#define	PDStaticHashValueForHashAs(stha, hash, type)   as(type, PDStaticHashValueForHash(stha, hash))
#define	PDStaticHashValueForKeyAs(stha, key, type)   as(type, PDStaticHashValueForKey(stha, key))

Typedefs
typedef struct PDStaticHash *	PDStaticHashRef

Functions
PDStaticHashRef	PDStaticHashCreate (PDInteger entries, void **keys, void **values)
void	PDStaticHashDisownKeysValues (PDStaticHashRef sh, PDBool disownKeys, PDBool disownValues)

Detailed Description

A (very) simple hash table implementation.

Limited to predefined set of primitive keys on creation. \(O(1)\) but triggers false positives for undefined keys.

This is used as a pre-filter in the PDPipe implementation to reduce the misses for the more cumbersome pd_btree containing tasks. It is also used in the PDF spec implementation's PDStringFromComplex() function.

The static hash generates a hash table of \(2^n\) size, where \(n\) is the lowest possible number where the primitive value of the range of keys produces all unique indices based on the following formula, where \(K\), \(s\), and \(m\) are the key, shift and mask parameters

\((K \oplus (K \gg s)) \land m\)

The shifting is necessary because the range of keys tend to align, and in bad cases, the alignment happens in the low bits, resulting in redundancy. Unfortunately, determining the mask and shift values for a given instance is expensive and fairly unoptimized at the moment, with the excuse that creation does not occur repeatedly.

See also

PDPipe

Pajdeg PDF Implementation

Macro Definition Documentation

#define PDStaticHashIdx	(		stha,
			key
	)		static_hash_idx(stha->mask, stha->shift, key)

Generate a hash for the given key in the given static hash.

Parameters

stha	The PDStaticHashRef instance.
key	The key.

#define PDStaticHashValueForHash	(		stha,
			hash
	)		stha->table[hash]

Obtain value for given hash.

Parameters

stha	The PDStaticHashRef instance.
hash	The hash.

#define PDStaticHashValueForHashAs	(		stha,
			hash,
			type
	)		as(type, PDStaticHashValueForHash(stha, hash))

Obtain typecast value for hash.

Parameters

stha	The PDStaticHashRef instance.
hash	The hash.
type	The type.

#define PDStaticHashValueForKey	(		stha,
			key
	)		stha->table[PDStaticHashIdx(stha, key)]

Obtain value for given key.

Parameters

stha	The PDStaticHashRef instance.
key	The key.

#define PDStaticHashValueForKeyAs	(		stha,
			key,
			type
	)		as(type, PDStaticHashValueForKey(stha, key))

Obtain typecast value for key.

Parameters

stha	The PDStaticHashRef instance.
key	The key.
type	The type.

#define static_hash_idx	(		mask,
			shift,
			key
	)		(((long)key ^ ((long)key >> shift)) & mask)

Generate a hash for the given key based on provided mask and shift.

Note

Does not rely on a PDStaticHash instance.

Parameters

mask	The mask.
shift	The shift.
key	The key.

Typedef Documentation

typedef struct PDStaticHash* PDStaticHashRef

A (very) simple hash table implementation.

Limited to predefined set of primitive keys on creation. O(1) but triggers false positives in some instances.

Function Documentation

PDStaticHashRef PDStaticHashCreate	(	PDInteger	entries,
		void **	keys,
		void **	values
	)

Create a static hash with keys and values.

Sets up a static hash with given entries, where given keys are hashed as longs into indices inside the internal table, with guaranteed non-collision and O(1) mapping of keys to values.

Note

Setting up is expensive.

Warning

Triggers false-positives for non-complete input.

Parameters

entries	The number of entries.
keys	The array of keys. Note that keys are primitives.
values	The array of values corresponding to the array of keys.

Todo:

had 1 assert below; so this needs to be ripped out asap

void PDStaticHashDisownKeysValues	(	PDStaticHashRef	sh,
		PDBool	disownKeys,
		PDBool	disownValues
	)

Indicate that keys and/or values are not owned by the static hash and should not be freed on destruction; enabled flags are not disabled even if false is passed in (once disowned, always disowned)

Parameters

sh	The static hash
disownKeys	Whether keys should be disowned.
disownValues	Whether values should be disowned.