Hash Table

A hash table is a data structure that associates some data with a unique key. More...

Collaboration diagram for Hash Table:

Data Structures
struct	t_hashtab_entry
	A hashtab entry. More...
struct	t_hashtab
	The hashtab object. More...
Defines
#define	HASH_DEFSLOTS
	Default number of slots in the hash table.
Functions
t_hashtab *	hashtab_new (long slotcount)
	Create a new hashtab object.
t_max_err	hashtab_store (t_hashtab *x, t_symbol *key, t_object *val)
	Store an item in a hashtab with an associated key.
t_max_err	hashtab_store_safe (t_hashtab *x, t_symbol *key, t_object *val)
	Store an item in a hashtab with an associated key.
t_max_err	hashtab_storeflags (t_hashtab *x, t_symbol *key, t_object *val, long flags)
	Store an item in a hashtab with an associated key and also flags that define the behavior of the item.
t_max_err	hashtab_lookup (t_hashtab *x, t_symbol *key, t_object **val)
	Return an item stored in a hashtab with the specified key.
t_max_err	hashtab_lookupflags (t_hashtab *x, t_symbol *key, t_object **val, long *flags)
	Return an item stored in a hashtab with the specified key, also returning the items flags.
t_max_err	hashtab_delete (t_hashtab *x, t_symbol *key)
	Remove an item from a hashtab associated with the specified key and free it.
t_max_err	hashtab_clear (t_hashtab *x)
	Delete all items stored in a hashtab.
t_max_err	hashtab_chuckkey (t_hashtab *x, t_symbol *key)
	Remove an item from a hashtab associated with a given key.
t_max_err	hashtab_chuck (t_hashtab *x)
	Free a hashtab, but don't free the items it contains.
t_max_err	hashtab_findfirst (t_hashtab *x, void **o, long cmpfn(void *, void *), void *cmpdata)
	Search the hash table for the first item meeting defined criteria.
t_max_err	hashtab_methodall (t_hashtab *x, t_symbol *s,...)
	Call the named message on every object in the hashtab.
t_max_err	hashtab_funall (t_hashtab *x, method fun, void *arg)
	Call the specified function for every item in the hashtab.
long	hashtab_getsize (t_hashtab *x)
	Return the number of items stored in a hashtab.
void	hashtab_print (t_hashtab *x)
	Post a hashtab's statistics to the Max window.
void	hashtab_readonly (t_hashtab *x, long readonly)
	Set the hashtab's readonly bit.
void	hashtab_flags (t_hashtab *x, long flags)
	Set the hashtab's datastore flags.
long	hashtab_getflags (t_hashtab *x)
	Get the hashtab's datastore flags.
t_max_err	hashtab_keyflags (t_hashtab *x, t_symbol *key, long flags)
	Change the flags for an item stored in the hashtab with a given key.
long	hashtab_getkeyflags (t_hashtab *x, t_symbol *key)
	Retrieve the flags for an item stored in the hashtab with a given key.
t_max_err	hashtab_getkeys (t_hashtab *x, long *kc, t_symbol ***kv)
	Retrieve all of the keys stored in a hashtab.

---

Detailed Description

A hash table is a data structure that associates some data with a unique key.

If you know the key, you can get back the data much more quickly than with a linked list, particularly as the number of items stored grows larger. The Max hash table t_hashtab is optimized to work with symbol pointers as keys, but you can use any pointer or number, as long as it is unique.

To create a t_hashtab, you use hashtab_new(). To add items, use hashtab_store(). To find items that have been added, use hashtab_lookup().

By contrast with linked lists and arrays, hash tables do not have a strong sense of ordering. You can iterate through all items using hashtab_funall(), but the exact order is not under your control as items are added and removed. There is also no way to "sort" a hash table.

Example:

The following example creates a hashtab, shows how to add some data (in this case, just a number), look it up, and delete the hashtab.

    t_hashtab *tab = (t_hashtab *)hashtab_new(0);
    long result, value;

    hashtab_store(tab, gensym("a great number"), (t_object *)74);

    result = hashtab_lookup(tab, gensym("a great number"), (t_object **)value);

    if (!result)
        post("found the value and it is %ld",value);
    else
        post("did not find the value");

    hashtab_chuck(tab);

Note that the Max t_dictionary used for managing patcher data is implemented internally using both a t_hashtab and a t_linklist in parallel. The t_hashtab provides fast access, and the t_linklist provides sorting.

See also:

http://en.wikipedia.org/wiki/Hash_table

Linked List

---

Define Documentation

#define HASH_DEFSLOTS

Default number of slots in the hash table.

Creating a hashtab using hashtab_new() with an argument of 0 will use the default number of slots. Primes typically work well for the number of slots.

---

Function Documentation

t_max_err hashtab_chuck

(

t_hashtab *

x

)

Free a hashtab, but don't free the items it contains.

The hashtab can contain a variety of different types of data. By default, the hashtab assumes that all items are max objects with a valid t_object header.

You can alter the hashtab's notion of what it contains by using the hashtab_flags() method.

When you free the hashtab by calling object_free() it then tries to free all of the items it contains. If the hashtab is storing a custom type of data, or should otherwise not free the data it contains, then call hashtab_chuck() to free the object instead of object_free().

Parameters:

x	The hashtab object to be freed.

Returns:

A max error code.

See also:

object_free

t_max_err hashtab_chuckkey	(	t_hashtab *	x,
		t_symbol *	key
	)

Remove an item from a hashtab associated with a given key.

You are responsible for freeing any memory associated with the item that is removed from the hashtab.

Parameters:

x	The hashtab instance.
key	The key of the item to delete.

Returns:

A Max error code.

See also:

hashtab_delete

t_max_err hashtab_clear

(

t_hashtab *

x

)

Delete all items stored in a hashtab.

This is the equivalent of calling hashtab_delete() on every item in a hashtab.

Returns:

A max error code.

See also:

hashtab_flags()

hashtab_delete()

t_max_err hashtab_delete	(	t_hashtab *	x,
		t_symbol *	key
	)

Remove an item from a hashtab associated with the specified key and free it.

The hashtab can contain a variety of different types of data. By default, the hashtab assumes that all items are max objects with a valid t_object header. Thus by default, it frees items by calling object_free() on them.

You can alter the hashtab's notion of what it contains by using the hashtab_flags() method.

If you wish to remove an item from the hashtab and free it yourself, then you should use hashtab_chuckkey().

Parameters:

x	The hashtab instance.
key	The key of the item to delete.

Returns:

A Max error code.

See also:

hashtab_chuckkey()

hashtab_clear()

hashtab_flags()

t_max_err hashtab_findfirst	(	t_hashtab *	x,
		void **	o,
		long	cmpfnvoid *, void *,
		void *	cmpdata
	)

Search the hash table for the first item meeting defined criteria.

The items in the hashtab are iteratively processed, calling a specified comparison function on each until the comparison function returns true.

Parameters:

x	The hashtab instance.
o	The address to pointer that will be set with the matching item.
cmpfn	The function used to determine a match in the list.
cmpdata	An argument to be passed to the t_cmpfn. This will be passed as the second of the two args to the t_cmpfn. The first arg will be the hashtab item at each iteration in the list.

Returns:

A max error code.

See also:

linklist_findfirst()

t_cmpfn

void hashtab_flags	(	t_hashtab *	x,
		long	flags
	)

Set the hashtab's datastore flags.

The available flags are enumerated in e_max_datastore_flags. These flags control the behavior of the hashtab, particularly when removing items from the list using functions such as hashtab_clear(), hashtab_delete(), or when freeing the hashtab itself.

Parameters:

x	The hashtab instance.
flags	A valid value from the e_max_datastore_flags. The default is OBJ_FLAG_OBJ.

t_max_err hashtab_funall	(	t_hashtab *	x,
		method	fun,
		void *	arg
	)

Call the specified function for every item in the hashtab.

Parameters:

x	The hashtab instance.
fun	The function to call, specified as function pointer cast to a Max method.
arg	An argument that you would like to pass to the function being called.

Returns:

A max error code.

Remarks:

The hashtab_funall() method will call your function for every item in the list. It will pass both a pointer to the item in the list, and any argument that you provide. The following example shows a function that could be called by hashtab_funall().

    void myFun(t_hashtab_entry *e, void *myArg)
    {
        if (e->key && e->value) {
            // do something with e->key, e->value, and myArg here as appropriate
        }
    }

long hashtab_getflags

(

t_hashtab *

x

)

Get the hashtab's datastore flags.

Parameters:

x	The hashtab instance.

Returns:

The current state of the hashtab flags as enumerated in e_max_datastore_flags.

long hashtab_getkeyflags	(	t_hashtab *	x,
		t_symbol *	key
	)

Retrieve the flags for an item stored in the hashtab with a given key.

Parameters:

x	The hashtab instance.
key	The key in the hashtab whose flags will be returned.

Returns:

The flags for the given key.

See also:

hashtab_store_flags()

t_max_err hashtab_getkeys	(	t_hashtab *	x,
		long *	kc,
		t_symbol ***	kv
	)

Retrieve all of the keys stored in a hashtab.

If the kc and kv parameters are properly initialized to zero, then hashtab_getkeys() will allocate memory for the keys it returns. You are then responsible for freeing this memory using sysmem_freeptr().

Parameters:

x	The hashtab instance.
kc	The address of a long where the number of keys retrieved will be set.
kv	The address of the first of an array t_symbol pointers where the retrieved keys will be set.

Returns:

A max error code.

Remarks:

The following example demonstrates fetching all of the keys from a hashtab in order to iterate through each item stored in the hashtab.

    t_symbol    **keys = NULL;
    long        numKeys = 0;
    long        i;
    t_object    *anItem;

    hashtab_getkeys(aHashtab, &numKeys, &keys);
    for(i=0; i<numKeys; i++){
        hashtab_lookup(aHashtab, keys[i], &anItem);
        // Do something with anItem here...
    }
    if(keys)
        sysmem_freeptr(keys);

long hashtab_getsize

(

t_hashtab *

x

)

Return the number of items stored in a hashtab.

Parameters:

x	The hashtab instance.

Returns:

The number of items in the hash table.

t_max_err hashtab_keyflags	(	t_hashtab *	x,
		t_symbol *	key,
		long	flags
	)

Change the flags for an item stored in the hashtab with a given key.

Parameters:

x	The hashtab instance.
key	The key in the hashtab whose flags will be changed.
flags	One of the values listed in e_max_datastore_flags.

Returns:

A Max error code.

See also:

hashtab_store_flags()

t_max_err hashtab_lookup	(	t_hashtab *	x,
		t_symbol *	key,
		t_object **	val
	)

Return an item stored in a hashtab with the specified key.

Parameters:

x	The hashtab instance.
key	The key in the hashtab to fetch.
val	The address of a pointer to which the fetched value will be assigned.

Returns:

A Max error code.

See also:

hashtab_store()

t_max_err hashtab_lookupflags	(	t_hashtab *	x,
		t_symbol *	key,
		t_object **	val,
		long *	flags
	)

Return an item stored in a hashtab with the specified key, also returning the items flags.

Parameters:

x	The hashtab instance.
key	The key in the hashtab to fetch.
val	The address of a pointer to which the fetched value will be assigned.
flags	The address of a value to which the fetched flags will be assigned.

Returns:

A Max error code.

See also:

hashtab_lookup()

hashtab_store_flags()

t_max_err hashtab_methodall	(	t_hashtab *	x,
		t_symbol *	s,
			...
	)

Call the named message on every object in the hashtab.

The hashtab_methodall() function requires that all items in the hashtab are object instances with a valid t_object header.

Parameters:

x	The hashtab instance.
s	The name of the message to send to the objects.
...	Any arguments to be sent with the message.

Returns:

A max error code.

Remarks:

Internally, this function uses object_method(), meaning that no errors will be posted if the message name does not exist for the object. It also means that messages sent methods with A_GIMME definitions will need to be given a symbol argument prior to the argc and argv array information.

t_hashtab* hashtab_new

(

long

slotcount

)

Create a new hashtab object.

You can free the hashtab by calling object_free() on the hashtab's pointer, or by using hashtab_chuck().

Parameters:

slotcount

The number of slots in the hash table. Prime numbers typically work well. Pass 0 to get the default size.

Returns:

Pointer to the new hashtab object.

See also:

HASH_DEFSLOTS

object_free()

hashtab_chuck()

void hashtab_print

(

t_hashtab *

x

)

Post a hashtab's statistics to the Max window.

Parameters:

x	The hashtab instance.

void hashtab_readonly	(	t_hashtab *	x,
		long	readonly
	)

Set the hashtab's readonly bit.

By default the readonly bit is 0, indicating that it is threadsafe for both reading and writing. Setting the readonly bit to 1 will disable the hashtab's theadsafety mechanism, increasing performance but at the expense of threadsafe operation. Unless you can guarantee the threading context for a hashtab's use, you should leave this set to 0.

Parameters:

x	The hashtab instance.
readonly	A 1 or 0 for setting the readonly bit.

t_max_err hashtab_store	(	t_hashtab *	x,
		t_symbol *	key,
		t_object *	val
	)

Store an item in a hashtab with an associated key.

Parameters:

x	The hashtab instance.
key	The key in the hashtab with which to associate the value.
val	The value to store.

Returns:

A Max error code.

See also:

hashtab_lookup()

t_max_err hashtab_store_safe	(	t_hashtab *	x,
		t_symbol *	key,
		t_object *	val
	)

Store an item in a hashtab with an associated key.

The difference between hashtab_store_safe() and hashtab_store() is what happens in the event of a collision in the hash table. The normal hashtab_store() function will free the existing value at the collision location with sysmem_freeptr() and then replaces it. This version doesn't try to free the existing value at the collision location, but instead just over-writes it.

Parameters:

x	The hashtab instance.
key	The key in the hashtab with which to associate the value.
val	The value to store.

Returns:

A Max error code.

See also:

hashtab_store()

t_max_err hashtab_storeflags	(	t_hashtab *	x,
		t_symbol *	key,
		t_object *	val,
		long	flags
	)

Store an item in a hashtab with an associated key and also flags that define the behavior of the item.

The hashtab_store() method is the same as calling this method with the default (0) flags.

Parameters:

x	The hashtab instance.
key	The key in the hashtab with which to associate the value.
val	The value to store.
flags	One of the values listed in e_max_datastore_flags.

Returns:

A Max error code.

See also:

hashtab_store()