A hash table is a data structure that associates some data with a unique key. More...
Data Structures | |
struct | t_hashtab_entry |
A hashtab entry. More... | |
struct | t_hashtab |
The hashtab object. More... | |
Macros | |
#define | HASH_DEFSLOTS |
Default number of slots in the hash table. More... | |
Functions | |
BEGIN_USING_C_LINKAGE t_hashtab * | hashtab_new (long slotcount) |
Create a new hashtab object. More... | |
t_max_err | hashtab_store (t_hashtab *x, t_symbol *key, t_object *val) |
Store an item in a hashtab with an associated key. More... | |
t_max_err | hashtab_storelong (t_hashtab *x, t_symbol *key, t_atom_long val) |
Store a t_atom_long value in a hashtab with an associated key. More... | |
t_max_err | hashtab_storesym (t_hashtab *x, t_symbol *key, t_symbol *val) |
Store a t_symbol value in a hashtab with an associated key. More... | |
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. More... | |
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. More... | |
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. More... | |
t_max_err | hashtab_lookuplong (t_hashtab *x, t_symbol *key, t_atom_long *val) |
Return a t_atom_long value stored in a hashtab with the specified key. More... | |
t_max_err | hashtab_lookupsym (t_hashtab *x, t_symbol *key, t_symbol **val) |
Return a t_symbol value stored in a hashtab with the specified key. More... | |
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. More... | |
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. More... | |
t_max_err | hashtab_clear (t_hashtab *x) |
Delete all items stored in a hashtab. More... | |
t_max_err | hashtab_chuckkey (t_hashtab *x, t_symbol *key) |
Remove an item from a hashtab associated with a given key. More... | |
t_max_err | hashtab_chuck (t_hashtab *x) |
Free a hashtab, but don't free the items it contains. More... | |
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. More... | |
t_max_err | hashtab_methodall (t_hashtab *x, t_symbol *s,...) |
Call the named message on every object in the hashtab. More... | |
t_max_err | hashtab_funall (t_hashtab *x, method fun, void *arg) |
Call the specified function for every item in the hashtab. More... | |
t_atom_long | hashtab_getsize (t_hashtab *x) |
Return the number of items stored in a hashtab. More... | |
void | hashtab_print (t_hashtab *x) |
Post a hashtab's statistics to the Max window. More... | |
void | hashtab_readonly (t_hashtab *x, long readonly) |
Set the hashtab's readonly bit. More... | |
void | hashtab_flags (t_hashtab *x, long flags) |
Set the hashtab's datastore flags. More... | |
t_atom_long | hashtab_getflags (t_hashtab *x) |
Get the hashtab's datastore flags. More... | |
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. More... | |
t_atom_long | hashtab_getkeyflags (t_hashtab *x, t_symbol *key) |
Retrieve the flags for an item stored in the hashtab with a given key. More... | |
t_max_err | hashtab_getkeys (t_hashtab *x, long *kc, t_symbol ***kv) |
Retrieve all of the keys stored in a hashtab. More... | |
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.
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.
#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.
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().
x | The hashtab object to be freed. |
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.
x | The hashtab instance. |
key | The key of the item to delete. |
Delete all items stored in a hashtab.
This is the equivalent of calling hashtab_delete() on every item in a hashtab.
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().
x | The hashtab instance. |
key | The key of the item to delete. |
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.
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. |
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.
x | The hashtab instance. |
flags | A valid value from the e_max_datastore_flags. The default is OBJ_FLAG_OBJ. |
Call the specified function for every item in the hashtab.
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. |
Referenced by jit_class_addinterface().
t_atom_long hashtab_getflags | ( | t_hashtab * | x | ) |
Get the hashtab's datastore flags.
x | The hashtab instance. |
t_atom_long hashtab_getkeyflags | ( | t_hashtab * | x, |
t_symbol * | key | ||
) |
Retrieve the flags for an item stored in the hashtab with a given key.
x | The hashtab instance. |
key | The key in the hashtab whose flags will be returned. |
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().
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. |
t_atom_long hashtab_getsize | ( | t_hashtab * | x | ) |
Return the number of items stored in a hashtab.
x | The hashtab instance. |
Change the flags for an item stored in the hashtab with a given key.
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. |
Return an item stored in a hashtab with the specified key.
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. |
Return an item stored in a hashtab with the specified key, also returning the items flags.
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. |
t_max_err hashtab_lookuplong | ( | t_hashtab * | x, |
t_symbol * | key, | ||
t_atom_long * | val | ||
) |
Return a t_atom_long value stored in a hashtab with the specified key.
x | The hashtab instance. |
key | The key in the hashtab to fetch. |
val | A pointer to a t_atom_long to which the fetched value will be assigned. |
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.
x | The hashtab instance. |
s | The name of the message to send to the objects. |
... | Any arguments to be sent with the message. |
BEGIN_USING_C_LINKAGE 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().
slotcount | The number of slots in the hash table. Prime numbers typically work well. Pass 0 to get the default size. |
Referenced by jit_class_addinterface().
void hashtab_print | ( | t_hashtab * | x | ) |
Post a hashtab's statistics to the Max window.
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.
x | The hashtab instance. |
readonly | A 1 or 0 for setting the readonly bit. |
Store an item in a hashtab with an associated key.
x | The hashtab instance. |
key | The key in the hashtab with which to associate the value. |
val | The value to store. |
Referenced by jit_class_addinterface().
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.
x | The hashtab instance. |
key | The key in the hashtab with which to associate the value. |
val | The value to store. |
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.
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. |
t_max_err hashtab_storelong | ( | t_hashtab * | x, |
t_symbol * | key, | ||
t_atom_long | val | ||
) |
Store a t_atom_long value in a hashtab with an associated key.
x | The hashtab instance. |
key | The key in the hashtab with which to associate the value. |
val | The t_atom_long value to store. |
Store a t_symbol value in a hashtab with an associated key.
x | The hashtab instance. |
key | The key in the hashtab with which to associate the value. |
val | The t_symbol pointer to store. |