GLib Reference Manual
<<< Previous PageHomeUpNext Page >>>

Hash Tables

Name

Hash Tables -- associations between keys and values so that given a key the value can be found quickly.

Synopsis


#include <glib.h>


struct      GHashTable;
GHashTable* g_hash_table_new                (GHashFunc hash_func,
                                             GCompareFunc key_compare_func);
guint       (*GHashFunc)                    (gconstpointer key);
gint        (*GCompareFunc)                 (gconstpointer a,
                                             gconstpointer b);
void        g_hash_table_insert             (GHashTable *hash_table,
                                             gpointer key,
                                             gpointer value);
guint       g_hash_table_size               (GHashTable *hash_table);
gpointer    g_hash_table_lookup             (GHashTable *hash_table,
                                             gconstpointer key);
gboolean    g_hash_table_lookup_extended    (GHashTable *hash_table,
                                             gconstpointer lookup_key,
                                             gpointer *orig_key,
                                             gpointer *value);
void        g_hash_table_foreach            (GHashTable *hash_table,
                                             GHFunc func,
                                             gpointer user_data);
void        (*GHFunc)                       (gpointer key,
                                             gpointer value,
                                             gpointer user_data);
void        g_hash_table_remove             (GHashTable *hash_table,
                                             gconstpointer key);
guint       g_hash_table_foreach_remove     (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);
gboolean    (*GHRFunc)                      (gpointer key,
                                             gpointer value,
                                             gpointer user_data);
void        g_hash_table_freeze             (GHashTable *hash_table);
void        g_hash_table_thaw               (GHashTable *hash_table);
void        g_hash_table_destroy            (GHashTable *hash_table);

gint        g_direct_equal                  (gconstpointer v,
                                             gconstpointer v2);
guint       g_direct_hash                   (gconstpointer v);
gint        g_int_equal                     (gconstpointer v,
                                             gconstpointer v2);
guint       g_int_hash                      (gconstpointer v);
gint        g_str_equal                     (gconstpointer v,
                                             gconstpointer v2);
guint       g_str_hash                      (gconstpointer v);

Description

A GHashTable provides associations between keys and values which is optimized so that given a key, the associated value can be found very quickly.

Note that neither keys nor values are copied when inserted into the GHashTable, so they must exist for the lifetime of the GHashTable. This means that the use of static strings is OK, but temporary strings (i.e. those created in buffers and those returned by GTK widgets) should be copied with g_strdup() before being inserted.

If keys or values are dynamically allocated, you must be careful to ensure that they are freed when they are removed from the GHashTable, and also when they are overwritten by new insertions into the GHashTable. It is also not advisable to mix static strings and dynamically-allocated strings in a GHashTable, because it then becomes difficult to determine whether the string should be freed.

To create a GHashTable, use g_hash_table_new().

To insert a key and value into a GHashTable, use g_hash_table_insert().

To lookup a value corresponding to a given key, use g_hash_table_lookup() and g_hash_table_lookup_extended().

To remove a key and value, use g_hash_table_remove().

To call a function for each key and value pair use g_hash_table_foreach().

To destroy a GHashTable use g_hash_table_destroy().

Details

struct GHashTable

struct GHashTable;

The GHashTable struct is an opaque data structure to represent a Hash Table. It should only be accessed via the following functions.

g_hash_table_new ()

GHashTable* g_hash_table_new                (GHashFunc hash_func,
                                             GCompareFunc key_compare_func);

Creates a new GHashTable.

hash_func :a function to create a hash value from a key. Hash values are used to determine where keys are stored within the GHashTable data structure. The g_direct_hash(), g_int_hash() and g_str_hash() functions are provided for some common types of keys. If hash_func is NULL, g_direct_hash() is used.
key_compare_func :a function to compare two keys to see if they are equal. This is used when looking up keys in the GHashTable. The g_direct_equal(), g_int_equal() and g_str_equal() functions are provided for the most common types of keys. If compare_func is NULL, keys are compared directly in a similar fashion to g_direct_equal(), but without the overhead of a function call.
Returns :a new GHashTable.

GHashFunc ()

guint       (*GHashFunc)                    (gconstpointer key);

Specifies the type of the hash function which is passed to g_hash_table_new() when a GHashTable is created.

The function is passed a key and should return a guint hash value. The functions g_direct_hash(), g_int_hash() and g_str_hash() provide hash functions which can be used when the key is a gpointer, gint, and gchar* respectively.

FIXME: Need more here. The hash values should be evenly distributed over a fairly large range? The modulus is taken with the hash table size (a prime number) to find the 'bucket' to place each key into. The function should also be very fast, since it is called for each key lookup.

key :a key.
Returns :the hash value corresponding to the key.

GCompareFunc ()

gint        (*GCompareFunc)                 (gconstpointer a,
                                             gconstpointer b);

Specifies the type of a comparison function used to compare two values. The value which should be returned depends on the context in which the GCompareFunc is used.

In g_hash_table_new(), g_cache_new(), and g_relation_index() the function should return TRUE if the two parameters are equal, or FALSE if they are not.

In g_list_find_custom() and g_slist_find_custom() the function should return 0 if the two parameters are equal.

In g_list_insert_sorted(), g_list_sort(), g_slist_insert_sorted(), g_slist_sort() and g_tree_new() the function should return a negative integer if the first value comes before the second, 0 if they are equal, or a positive integer if the first value comes after the second.

a :a value.
b :a value to compare with.
Returns :TRUE if the two values are equivalent.

g_hash_table_insert ()

void        g_hash_table_insert             (GHashTable *hash_table,
                                             gpointer key,
                                             gpointer value);

Inserts a new key and value into a GHashTable. If the key already exists in the GHashTable its current value is replaced with the new value.

Note: If the keys or values use dynamically allocated memory, then you should first check if the key already exists in the GHashTable. If it does, you should free the existing key and/or value before inserting the new key and value.

hash_table :a GHashTable.
key :a key to insert.
value :the value to associate with the key.

g_hash_table_size ()

guint       g_hash_table_size               (GHashTable *hash_table);

Returns the number of key/value pairs in a GHashTable.

hash_table :a GHashTable.
Returns :the number of key/value pairs in the GHashTable.

g_hash_table_lookup ()

gpointer    g_hash_table_lookup             (GHashTable *hash_table,
                                             gconstpointer key);

Looks up a key in the GHashTable, returning the associated value or NULL if the key is not found.

hash_table :a GHashTable.
key :the key to look up.
Returns :the associated value, or NULL if the key is not found.

g_hash_table_lookup_extended ()

gboolean    g_hash_table_lookup_extended    (GHashTable *hash_table,
                                             gconstpointer lookup_key,
                                             gpointer *orig_key,
                                             gpointer *value);

Looks up a key in the GHashTable, returning the original key and the associated value and a gboolean which is TRUE if the key was found. This is useful if you need to free the memory allocated for the original key, for example before calling g_hash_table_remove().

hash_table :a GHashTable.
lookup_key :the key to look up.
orig_key :returns the original key.
value :returns the value associated with the key.
Returns :TRUE if the key was found in the GHashTable.

g_hash_table_foreach ()

void        g_hash_table_foreach            (GHashTable *hash_table,
                                             GHFunc func,
                                             gpointer user_data);

Calls the given function for each of the key/value pairs in the GHashTable. The function is passed the key and value of each pair, and the given user_data parameter.

hash_table :a GHashTable.
func :the function to call for each key/value pair.
user_data :use data to pass to the function.

GHFunc ()

void        (*GHFunc)                       (gpointer key,
                                             gpointer value,
                                             gpointer user_data);

Specifies the type of the function passed to g_hash_table_foreach(). It is called with each key/value pair, together with the user_data parameter which is passed to g_hash_table_foreach().

key :a key.
value :the value corresponding to the key.
user_data :user data passed to g_hash_table_foreach().

g_hash_table_remove ()

void        g_hash_table_remove             (GHashTable *hash_table,
                                             gconstpointer key);

Removes a key and its associated value from a GHashTable.

Note: As with g_hash_table_insert(), you should make sure that any dynamically allocated values are freed yourself.

hash_table :a GHashTable.
key :the key to remove.

g_hash_table_foreach_remove ()

guint       g_hash_table_foreach_remove     (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);

Calls the given function for each key/value pair in the GHashTable. If the function returns TRUE, then the key/value pair is removed from the GHashTable.

hash_table :a GHashTable.
func :the function to call for each key/value pair.
user_data :user data to pass to the function.
Returns :the number of key/value paris removed.

GHRFunc ()

gboolean    (*GHRFunc)                      (gpointer key,
                                             gpointer value,
                                             gpointer user_data);

Specifies the type of the function passed to g_hash_table_foreach_remove(). It is called with each key/value pair, together with the user_data parameter passed to g_hash_table_foreach_remove(). It should return TRUE if the key/value pair should be removed from the GHashTable.

key :a key.
value :the value associated with the key.
user_data :user data passed to g_hash_table_remove().
Returns :TRUE if the key/value pair should be removed from the GHashTable.

g_hash_table_freeze ()

void        g_hash_table_freeze             (GHashTable *hash_table);

Disable resizing of a GHashTable.

This should be used if you need to make a lot of changes to a GHashTable at once, as it reduces the number of times that the GHashTable is rebuilt. You should call g_hash_table_thaw() after updating the GHashTable to enable resizing again.

hash_table :a GHashTable.

g_hash_table_thaw ()

void        g_hash_table_thaw               (GHashTable *hash_table);

Enables resizing of a GHashTable.

hash_table :a GHashTable.

g_hash_table_destroy ()

void        g_hash_table_destroy            (GHashTable *hash_table);

Destroys the GHashTable.

Note: If keys and/or values are dynamically allocated, you should free them first.

hash_table :a GHashTable.

g_direct_equal ()

gint        g_direct_equal                  (gconstpointer v,
                                             gconstpointer v2);

Compares two gpointer arguments and returns TRUE if they are equal. It can be passed to g_hash_table_new() as the key_compare_func parameter, when using pointers as keys in a GHashTable.

v :a key.
v2 :a key to compare with v.
Returns :TRUE if the two keys match.

g_direct_hash ()

guint       g_direct_hash                   (gconstpointer v);

Converts a gpointer to a hash value. It can be passed to g_hash_table_new() as the hash_func parameter, when using gpointer values as keys in a GHashTable.

v :a gpointer key.
Returns :a hash value corresponding to the key.

g_int_equal ()

gint        g_int_equal                     (gconstpointer v,
                                             gconstpointer v2);

Compares the two gint values being pointed to and returns TRUE if they are equal. It can be passed to g_hash_table_new() as the key_compare_func parameter, when using pointers to integers as keys in a GHashTable.

v :a pointer to a gint key.
v2 :a pointer to a gint key to compare with v.
Returns :TRUE if the two keys match.

g_int_hash ()

guint       g_int_hash                      (gconstpointer v);

Converts a pointer to a gint to a hash value. It can be passed to g_hash_table_new() as the hash_func parameter, when using pointers to gint values as keys in a GHashTable.

v :a pointer to a gint key.
Returns :a hash value corresponding to the key.

g_str_equal ()

gint        g_str_equal                     (gconstpointer v,
                                             gconstpointer v2);

Compares two strings and returns TRUE if they are equal. It can be passed to g_hash_table_new() as the key_compare_func parameter, when using strings as keys in a GHashTable.

v :a key.
v2 :a key to compare with v.
Returns :TRUE if the two keys match.

g_str_hash ()

guint       g_str_hash                      (gconstpointer v);

Converts a string to a hash value. It can be passed to g_hash_table_new() as the hash_func parameter, when using strings as keys in a GHashTable.

v :a string key.
Returns :a hash value corresponding to the key.



<<< Previous PageHomeUpNext Page >>>
Singly-Linked ListsStrings