obmap Method Implementation More...

#include "../../include/obmap.h"
#include "../../include/private/obmap_private.h"

Functions
obmap *	obmap_new (void)
	Constructor, creates a new, empty, obmap instance with a small initial capacity. More...

obmap *	obmap_new_with_capacity (uint32_t capacity)
	Constructor, creates a new, empty obmap instance with capacity given. More...

obmap *	obmap_copy (const obmap *to_copy)
	Copy constructor, creates a new obmap with the exact same contents of another obmap. More...

void	obmap_insert (obmap m, obj key, obj *value)
	Add a key-value pair to an obmap. More...

obj *	obmap_lookup (const obmap m, const obj key)
	Lookup the value stored at key in an obmap. More...

void	obmap_remove (obmap m, obj key)
	Removes a key-value pair from an obmap. More...

void	obmap_rehash (obmap *m)
	Rehashes all elements contained in an obmap. More...

void	obmap_clear (obmap *m)
	Clears an obmap of all key-value pairs, essentially restoring it to the initial empty state that existed after creation. More...

obmap_pair *	obmap_new_pair (obj key, obj value)
	Default constructor for an obmap_pair. More...

obmap_pair *	obmap_copy_pair (obmap_pair *mp)
	Copy constructor, creates a new obmap_pair with the same key-value of an existing obmap_pair. More...

void	obmap_replace_pair_value (obmap_pair mp, obj value)
	Replaces existing value in an obmap_pair with the supplied value. More...

ob_hash_t	obmap_hash_pair (const obj *to_hash)
	Hash function for obmap_pair. More...

void	obmap_display_pair (const obj *to_print)
	Displays an instance of obmap_pair to stderr. More...

void	obmap_destroy_pair (obj *to_dealloc)
	Destructor for obmap_pair. More...

obmap *	obmap_create_default (void)
	Default constructor for obmap. More...

ob_hash_t	obmap_hash (const obj *to_hash)
	Hash function for obmap. More...

int8_t	obmap_compare (const obj a, const obj b)
	Compares two instances of obmap. More...

void	obmap_display (const obj *to_print)
	Displays an instance of obmap to stderr. More...

void	obmap_destroy (obj *to_dealloc)
	Destructor for obmap. More...

void	obmap_increase_size (obmap *to_size)
	Increases the size of the map to the next capacity within MAP_CAPACITIES array. More...

void	obmap_add_to_table (obmap m, obdeque_iterator it)
	Adds an obdeque_iterator to the proper location within the obmap. More...

ob_hash_t	obmap_find_key (const obmap m, const obj key)
	Finds a key within the hash table, it exists. More...

ob_hash_t	obmap_offset_collision (ob_hash_t prev_offset)
	Generates an offset from the hash value to rectify collisions. More...

Variables
const uint32_t	MAP_CAPACITIES []

const uint32_t	NUM_CAPACITIES

const double	MAX_LOAD_FACTOR = 0.75

Detailed Description

obmap Method Implementation

Author: theck

Function Documentation

void obmap_add_to_table	(	obmap *	m,
		obdeque_iterator *	it
	)

Adds an obdeque_iterator to the proper location within the obmap.

Parameters

m	The obmap to add the iterator to
it	The obdeque_iterator to add to the hash table

void obmap_clear ( obmap * m)

Clears an obmap of all key-value pairs, essentially restoring it to the initial empty state that existed after creation.

Parameters

m	Pointer to an instance of obmap

int8_t obmap_compare	(	const obj *	a,
		const obj *	b
	)

Compares two instances of obmap.

Parameters

a	A non-NULL obj pointer to type obmap
b	A non-NULL obj pointer to type obmap

Return values

OB_LESS_THAN	obj a is less than b
OB_GREATER_THAN	obj a is equivalent to b
OB_EQUAL_TO	obj a is greater than b

obmap* obmap_copy ( const obmap * to_copy)

Copy constructor, creates a new obmap with the exact same contents of another obmap.

Parameters

to_copy Pointer to an instance of obmap to copy

Returns: A copy of the provided obmap

obmap_pair* obmap_copy_pair ( obmap_pair * mp)

Copy constructor, creates a new obmap_pair with the same key-value of an existing obmap_pair.

Parameters

mp	The obmap instance to copy

Returns: An instance of class obmap_pair that contains the same key-value as mp

obmap* obmap_create_default ( void )

Default constructor for obmap.

Returns: An instance of class obmap

Warning: All public constructors should call this constructor and intialize individual members as needed, so that all base data is initialized properly.

void obmap_destroy ( obj * to_dealloc)

Destructor for obmap.

Parameters

to_dealloc An obj pointer to an instance of obmap with reference count of 0

Warning: Do not call manually, release will call automatically when the instances reference count drops to 0!

void obmap_destroy_pair ( obj * to_dealloc)

Destructor for obmap_pair.

Parameters

to_dealloc An obj pointer to an instance of obmap with reference count of 0

Warning: Do not call manually, release will call automatically when the instances reference count drops to 0!

void obmap_display ( const obj * to_print)

Displays an instance of obmap to stderr.

Parameters

to_print A non-NULL obj pointer to type obmap

void obmap_display_pair ( const obj * to_print)

Displays an instance of obmap_pair to stderr.

Parameters

to_print A non-NULL obj pointer to type obmap_pair

ob_hash_t obmap_find_key	(	const obmap *	m,
		const obj *	key
	)

Finds a key within the hash table, it exists.

Parameters

m	The obmap in which to search for the key
key	The key to serach for within the obmap

Returns: Index in the hash_table where a result can be found or where a NULL value resides if key was not found

ob_hash_t obmap_hash ( const obj * to_hash)

Hash function for obmap.

Parameters

to_hash An obj pointer to an instance of obmap

Returns: Key value (hash) for the given obj pointer to a obmap

ob_hash_t obmap_hash_pair ( const obj * to_hash)

Hash function for obmap_pair.

Parameters

to_hash An obj pointer to an instance of obmap_pair

Returns: Key value (hash) for the given obj pointer to a obmap_pair

void obmap_increase_size ( obmap * to_size)

Increases the size of the map to the next capacity within MAP_CAPACITIES array.

Parameters

to_size obmap to resize

void obmap_insert	(	obmap *	m,
		obj *	key,
		obj *	value
	)

Add a key-value pair to an obmap.

Parameters

m	Pointer to an instance of obmap
key	Pointer to any Offbrand compatible class to use as a lookup key
value	Pointer to any Offbrand compatible class

If the key is already contained within the m then the old value stored at that key is replaced with the new value

obj* obmap_lookup	(	const obmap *	m,
		const obj *	key
	)

Lookup the value stored at key in an obmap.

Parameters

m	Pointer to an instance of obmap
key	Pointer to any Offbrand compatible class to use as a lookup key

Return values

NULL	Key not found in obmap instance or key bound to NULL value
non-NULL	Value found at key in obmap

obmap* obmap_new ( void )

Constructor, creates a new, empty, obmap instance with a small initial capacity.

Returns: Pointer to the newly created obmap instance

obmap_pair* obmap_new_pair	(	obj *	key,
		obj *	value
	)

Default constructor for an obmap_pair.

Parameters

key	Offbrand compatible class instance used to lookup value within hash table
value	Offbrand compatible class stored within the obmap at a position denoted by key

Returns: An instance of class obmap_pair

Warning: All public constructors should call this constructor and intialize individual members as needed, so that all base data is initialized properly.

obmap* obmap_new_with_capacity ( uint32_t capacity)

Constructor, creates a new, empty obmap instance with capacity given.

Parameters

capacity Capacity required for obmap instance

Returns: Pointer to the newly created obmap instance

ob_hash_t obmap_offset_collision ( ob_hash_t prev_offset)

Generates an offset from the hash value to rectify collisions.

Parameters

prev_offset Last offset provided (0 if initiating call for the first time)

Returns: New offset to the next possible location to insert within table

void obmap_rehash ( obmap * m)

Rehashes all elements contained in an obmap.

Parameters

m	Pointer to an instance of obmap

This method is useful for ensuring that mutable keys will still lead to valid lookups of the associated values even after key(s) have been altered

void obmap_remove	(	obmap *	m,
		obj *	key
	)

Removes a key-value pair from an obmap.

Parameters

m	Pointer to an instance of obmap
key	Pointer to any Offbrand compatible class to use as a lookup key

If no key exists then the funciton will silently do nothing

Warning: This function runs in O(n), and is inherently more expensive than an add or lookup.

void obmap_replace_pair_value	(	obmap_pair *	mp,
		obj *	value
	)

Replaces existing value in an obmap_pair with the supplied value.

Parameters

mp	An instance of obmap_pair
value	The new value to replace the existing value

Variable Documentation

const uint32_t MAP_CAPACITIES[]

Initial value:

= {
  (1<<7)-1,
  (1<<8)-5,
  (1<<9)-3,
  (1<<10)-3,
  (1<<11)-9,
  (1<<12)-3,
  (1<<13)-1,
  (1<<14)-3,
  (1<<15)-19,
  (1<<16)-15,
  (1<<17)-1,
  (1<<18)-5,
  (1<<19)-1,
  (1<<20)-3,
  (1<<21)-9,
  (1<<22)-3,
  (1<<23)-15,
  (1<<24)-3,
  (1<<25)-39,
  (1<<26)-5,
  (1<<27)-39,
  (1<<28)-57,
  (1<<29)-3,
  (1<<30)-35,
  ((uint64_t)1<<31)-1,
  (((uint64_t)1)<<32)-5
}

Map capacity table, where capacities are the nearest prime numbers less than powers of 2.

const double MAX_LOAD_FACTOR = 0.75

Maximum load factor of an obmap before the map will be resized.

const uint32_t NUM_CAPACITIES

Initial value:

=

sizeof(MAP_CAPACITIES)/sizeof(MAP_CAPACITIES[0])

Number of elements in the map capacity table.

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation