Hash Tables

Hash Tables — Связь между ключами и значениями для быстрого поиска.

Краткое описание



#include <glib.h>


            GHashTable;
GHashTable* g_hash_table_new                (GHashFunc hash_func,
                                             GEqualFunc key_equal_func);
GHashTable* g_hash_table_new_full           (GHashFunc hash_func,
                                             GEqualFunc key_equal_func,
                                             GDestroyNotify key_destroy_func,
                                             GDestroyNotify value_destroy_func);
guint       (*GHashFunc)                    (gconstpointer key);
gboolean    (*GEqualFunc)                   (gconstpointer a,
                                             gconstpointer b);
void        g_hash_table_insert             (GHashTable *hash_table,
                                             gpointer key,
                                             gpointer value);
void        g_hash_table_replace            (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);
gpointer    g_hash_table_find               (GHashTable *hash_table,
                                             GHRFunc predicate,
                                             gpointer user_data);
void        (*GHFunc)                       (gpointer key,
                                             gpointer value,
                                             gpointer user_data);
gboolean    g_hash_table_remove             (GHashTable *hash_table,
                                             gconstpointer key);
gboolean    g_hash_table_steal              (GHashTable *hash_table,
                                             gconstpointer key);
guint       g_hash_table_foreach_remove     (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);
guint       g_hash_table_foreach_steal      (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);
void        g_hash_table_remove_all         (GHashTable *hash_table);
void        g_hash_table_steal_all          (GHashTable *hash_table);
gboolean    (*GHRFunc)                      (gpointer key,
                                             gpointer value,
                                             gpointer user_data);
#define     g_hash_table_freeze             (hash_table)
#define     g_hash_table_thaw               (hash_table)
void        g_hash_table_destroy            (GHashTable *hash_table);
GHashTable* g_hash_table_ref                (GHashTable *hash_table);
void        g_hash_table_unref              (GHashTable *hash_table);

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

Описание

GHashTable обеспечивает связь между ключами и значениями для наиболее быстрого поиска значения полученного ключа.

Помните что не ключи не их значения не копируются при помещении в GHashTable, поэтому они должны существовать для жизнеспособности GHashTable. Это значит использование статических строк допустимо, а временные строки (например создаваемые в буферах и возвращаемые GTK+ виджетами) должны быть скопированы с помощью g_strdup() перед вставкой в таблицу.

Если ключи и значения распределяются динамически, вы должны обязательно убедиться в их освобождении после удаления из GHashTable, а также когда они перезаписываются при новой вставке в GHashTable. Также не желательно смешивать статические строки и динамически-распределённые строки в GHashTable, потомучто тогда трудно определить должна ли строка освобождаться.

Для создания GHashTable, используйте g_hash_table_new().

Для вставки ключа и значения в GHashTable, используйте g_hash_table_insert().

Для поиска значения соответствующего полученному ключу используйте g_hash_table_lookup() и g_hash_table_lookup_extended().

Для удаления ключа и значения, используйте g_hash_table_remove().

Для вызова функции для каждой пары ключа и значения используйте g_hash_table_foreach().

Для уничтожения GHashTable используйте g_hash_table_destroy().

Детали

GHashTable

typedef struct _GHashTable GHashTable;

Структура GHashTable является непрозрачной структурой данных представляющей Hash Table. Доступ к ней может осуществляться только функциями описанными ниже.

g_hash_table_new ()

GHashTable* g_hash_table_new                (GHashFunc hash_func,
                                             GEqualFunc key_equal_func);

Создаёт новую GHashTable с количеством ссылок равным 1.

`hash_func` :	функция для создания хэш значения из ключа. Хеш значения используются для определения места хранения ключей внутри структуры данных GHashTable. Функции `g_direct_hash()`, `g_int_hash()` и `g_str_hash()` обеспечивают некоторые основные типы ключей. Если hash_func это `NULL`, то используется `g_direct_hash()`.
`key_equal_func` :	функция проверяющая эквивалентность двух ключей. Используется при поиске ключа в GHashTable. Функции `g_direct_equal()`, `g_int_equal()` и `g_str_equal()` обеспечивают основные типы ключей. Если `key_equal_func` это `NULL`, ключи сравниваются непосредственно в стиле `g_direct_equal()`, но без накладных расходов вызова функции.
Возвращает :	новая GHashTable.

g_hash_table_new_full ()

GHashTable* g_hash_table_new_full           (GHashFunc hash_func,
                                             GEqualFunc key_equal_func,
                                             GDestroyNotify key_destroy_func,
                                             GDestroyNotify value_destroy_func);

Создаёт новую GHashTable, похожа на g_hash_table_new() с количеством ссылок равным 1 и позволяет определять функции для освобождения памяти распределённой для ключа и значения которые получит вызов когда удалит элементы из GHashTable.

`hash_func` :	функция для создания хеш значения из ключа.
`key_equal_func` :	функция для проверки эквивалентности двух ключей.
`key_destroy_func` :	функция освобождающая распределённую память для ключа используемая при удалении элемента из GHashTable или `NULL` если вам не нужно выполнять такую функцию.
`value_destroy_func` :	функция освобождающая память, распределённую для значения, используемую при удалении элемента из GHashTable или `NULL` если вам не нужно выполнять такую функцию.
Возвращает :	новая GHashTable.

GHashFunc ()

guint (*GHashFunc) (gconstpointer key);

Специальный тип хеш функции которая помещается в g_hash_table_new() когда создаётся GHashTable.

В функцию помещается ключ и она должна вернуть хеш значение guint. Функции g_direct_hash(), g_int_hash() и g_str_hash() обеспечивают хеш-функции которые могут использоваться когда ключ gpointer, gint и gchar* соответственно.

ПОПРАВЬТЕ МЕНЯ: Здесь необходимо больше подробностей. Хеш-значения должны быть равномерно распределены по довольно большому диапазону? Модуль берётся с размером хеш таблицы (простое число) для поиска области памяти в которую помещается ключ. Функция должна быть очень быстрой, так как вызывается для каждого разыскиваемого ключа.

`key` :	ключ.
Возвращает :	хеш значение соответствующее ключу.

GEqualFunc ()

gboolean    (*GEqualFunc)                   (gconstpointer a,
                                             gconstpointer b);

Определяет тип функции используемой для проверки эквивалентности двух значений. Функция должна возвращать TRUE если оба значения эквивалентны или иначе FALSE.

`a` :	первое значение.
`b` :	значение для сравнения.
Возвращает :	`TRUE` если `a` = `b`; иначе `FALSE`.

g_hash_table_insert ()

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

Вставляет новый ключ и значение в GHashTable.

Если ключ уже существует в GHashTable его текущее значение переписывается новым. Если вы поместите value_destroy_func когда создаёте GHashTable, старое значение освобождается с помощью этой функции. Если вы поместите key_destroy_func когда создаёте GHashTable, помещаемый ключ освобождается с помощью этой функции.

`hash_table` :	GHashTable.
`key` :	вставляемый ключ.
`value` :	значение связанное с ключом.

g_hash_table_replace ()

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

Вставляет новый ключ и значение в GHashTable аналогично g_hash_table_insert(). Разница в том, что если ключ уже существует в GHashTable, он переписывается новым значением. Если вы поместили value_destroy_func когда создавали GHashTable, старое значение освобождается с помощью этой функции. Если вы поместили key_destroy_func когда создавали GHashTable, старый ключ освобождается с помощью этой функции.

`hash_table` :	GHashTable.
`key` :	ключ для вставки.
`value` :	значение связываемое с ключом.

g_hash_table_size ()

guint g_hash_table_size (GHashTable *hash_table);

Возвращает количество элементов находящихся в GHashTable.

`hash_table` :	GHashTable.
Возвращает :	количество пар ключ/значение в GHashTable.

g_hash_table_lookup ()

gpointer    g_hash_table_lookup             (GHashTable *hash_table,
                                             gconstpointer key);

Находит ключ в GHashTable. Помните что эта функция не может отличить ключ который не представлен от ключа который представлен но имеет значение NULL. Если вам нужно знать о таком различии, используйте g_hash_table_lookup_extended().

`hash_table` :	GHashTable.
`key` :	ключ для поиска.
Возвращает :	связанное значение, или `NULL` если ключ не найден.

g_hash_table_lookup_extended ()

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

Находит ключ в GHashTable, возвращает оригинальный ключ и связанное значение gboolean которое TRUE если ключ был найден. Это полезно если вам нужно освободить память распределённую для оригинального ключа, например перед вызовом g_hash_table_remove().

`hash_table` :	GHashTable.
`lookup_key` :	ключ для поиска.
`orig_key` :	возвращает оригинальный ключ.
`value` :	возвращает значение связанное с ключом.
Возвращает :	`TRUE` если ключ был найден в GHashTable.

g_hash_table_foreach ()

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

Вызывает полученную функцию для каждой пары ключ/значение в GHashTable. В функцию помещается ключ и значение каждой пары, а также параметр user_data. Хеш таблица не может меняться пока функция перемещается через неё (вы не можете добавлять/удалять элементы). Для удаления всех элементов соответствующих предикату, используйте g_hash_table_foreach_remove().

`hash_table` :	GHashTable.
`func` :	функция вызываемая для каждой пары ключ/значение.
`user_data` :	пользовательские данные помещаемые в функцию.

g_hash_table_find ()

gpointer    g_hash_table_find               (GHashTable *hash_table,
                                             GHRFunc predicate,
                                             gpointer user_data);

Вызывает полученную функцию для пар клю/значение в GHashTable, пока predicate не вернёт TRUE. В функцию помещается ключ и значение каждой пары, и полученный параметр user_data. Хеш таблица не может изменяться пока функция перемещается через неё (вы не можете добавлять/удалять элементы).

`hash_table` :	GHashTable.
`predicate` :	функция для проверки каждой пары ключ/значение на определённое свойство.
`user_data` :	пользовательские данные помещаемые в функцию.
Возвращает :	Значение первой возвращаемой пары ключ/значение, для которой функция вычислила `TRUE`. Если пара с требуемым свойством не найдена, возвращается `NULL`.

Начиная с версии 2.4

GHFunc ()

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

Определяет тип функции помещаемойв g_hash_table_foreach(). Она вызывается с каждой парой ключ/значение, вместе с параметром user_data который помещается в g_hash_table_foreach().

`key` :	ключ.
`value` :	значение соответствующее ключу.
`user_data` :	пользовательские данные помещаемые в `g_hash_table_foreach()`.

g_hash_table_remove ()

gboolean    g_hash_table_remove             (GHashTable *hash_table,
                                             gconstpointer key);

Удаляет ключ и связанное с ним значение из GHashTable.

Если GHashTable был создан используя g_hash_table_new_full(), ключ и значение освобождаются используя вставленную функцию уничтожения, иначе вы должны убедиться что освободили все динамически распределённые значения самостоятельно.

`hash_table` :	GHashTable.
`key` :	удаляемый ключ.
Возвращает :	`TRUE` если ключ был найден и удалён из GHashTable.

g_hash_table_steal ()

gboolean    g_hash_table_steal              (GHashTable *hash_table,
                                             gconstpointer key);

Удаляет ключ и связанное с ним значение из GHashTable, без вызова функции уничтожения ключа и значения.

`hash_table` :	GHashTable.
`key` :	ключ для удаления.
Возвращает :	`TRUE` если ключ был найден и удалён из GHashTable.

g_hash_table_foreach_remove ()

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

Вызывает полученную функцию для каждой пары ключ/значение в GHashTable. Если функция вернула TRUE, то ключ/значение удаляется из GHashTable. Если ключ или значение помещаются в функцию уничтожения при создании GHashTable, она используется для освобождения распределённой памяти удаляемых ключей и значений.

`hash_table` :	GHashTable.
`func` :	функция вызываемая для каждой пары ключ/значение.
`user_data` :	пользовательские данные помещаемые в функцию.
Возвращает :	количество удаляемых пар ключ/значение.

g_hash_table_foreach_steal ()

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

Вызывает полученную функцию для каждой пары ключ/значение в GHashTable. Если функция вернула TRUE, то пара ключ/значение удаляется из GHashTable, но функция уничтожения ключа или значения не вызывается.

`hash_table` :	GHashTable.
`func` :	функция вызываемая для каждой пары ключ/значение.
`user_data` :	пользовательские данные помещаемые в функцию.
Возвращает :	количество удаляемых пар ключ/значение.

g_hash_table_remove_all ()

void g_hash_table_remove_all (GHashTable *hash_table);

Удаляет все ключи и связанные с ними значения из GHashTable.

Если GHashTable была создана с использованием g_hash_table_new_full(), ключи и значения освобождаются используя помещённую функцию уничтожения, иначе вы должны убедиться что любые динамически распределённые значения освободили самостоятельно.

hash_table : GHashTable

Начиная с версии 2.12

g_hash_table_steal_all ()

void g_hash_table_steal_all (GHashTable *hash_table);

Удаляет все ключи и связанные с ними значения из GHashTable без вызова функции уничтожения ключа и значения.

hash_table : GHashTable.

Начиная с версии 2.12

GHRFunc ()

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

Определяет тип функции помещаемой в g_hash_table_foreach_remove(). Она вызывается с каждой парой ключ/значение, вместе с параметром user_data помещённым в g_hash_table_foreach_remove(). Она должна вернуть TRUE если пара ключ/значение должна быть удалена из GHashTable.

`key` :	ключ.
`value` :	значение связанное с ключом.
`user_data` :	пользовательские данные помещаемые в `g_hash_table_remove()`.
Возвращает :	`TRUE` если пара ключ/значение должна быть удалена из GHashTable.

g_hash_table_freeze()

#define g_hash_table_freeze(hash_table)

Внимание

g_hash_table_freeze устарела и не должна использоваться во вновь создаваемом коде.

Эта функция устарела и будет удалена в следующих релизах GLib. Она ничего не делает.

hash_table : GHashTable

g_hash_table_thaw()

#define g_hash_table_thaw(hash_table)

Внимание

g_hash_table_thaw устарела и не должна использоваться во вновь создаваемом коде.

Эта функция устарела и будет удалена в следующих релизах GLib. Она ничего не делает.

hash_table : GHashTable

g_hash_table_destroy ()

void g_hash_table_destroy (GHashTable *hash_table);

Уничтожает все ключи и значения в GHashTable и уменьшает количество её ссылок на 1. Если ключи и/или значения распределены динамически, вы должны либо освободить сначала их или создать GHashTable с уничтожающим уведомлением используя g_hash_table_new_full(). В последнем случае функция уничтожения, помещённая вами, будет вызвана для всех ключей и значений в течении фазы разрушения.

hash_table : GHashTable.

g_hash_table_ref ()

GHashTable* g_hash_table_ref (GHashTable *hash_table);

Автоматически увеличивает количество ссылок hash_table на одну. Эта функция MT-безопасна и может быть вызвана из любого потока.

`hash_table` :	правильная GHashTable.
Возвращает :	передачу в GHashTable.

Начиная с версии 2.10

g_hash_table_unref ()

void g_hash_table_unref (GHashTable *hash_table);

Автоматически уменьшает количество ссылок hash_table на одну. Если количество ссылок сброшено до 0, все ключи и значения будут уничтожены, а вся память, распределённая для хеш таблицы, освобождена. Эта функция MT-безопасна и может быть вызвана из любого потока.

hash_table : правильная GHashTable.

Начиная с версии 2.10

g_direct_equal ()

gboolean    g_direct_equal                  (gconstpointer v1,
                                             gconstpointer v2);

Сравнивает два аргумента gpointer и возвращает TRUE если они равны. Она может быть помещена в g_hash_table_new() как параметр key_equal_func, используя в качестве указателя ключ в GHashTable.

`v1` :	ключ.
`v2` :	ключ для сравнения с `v1`.
Возвращает :	`TRUE` если два ключа равны.

g_direct_hash ()

guint g_direct_hash (gconstpointer v);

Конвертирует gpointer в хеш значение. Она может быть помещена в g_hash_table_new() как параметр hash_func, используя в качестве указателя ключ в GHashTable.

`v` :	gpointer key
Возвращает :	хеш значение соответствующее ключу.

g_int_equal ()

gboolean    g_int_equal                     (gconstpointer v1,
                                             gconstpointer v2);

Сравнивает два значения gint и возвращает TRUE если они равны. Она может быть помещена в g_hash_table_new() как параметр key_equal_func, используя в качестве указателей на целочисленные ключи в GHashTable.

`v1` :	указатель на gint ключ.
`v2` :	указатель на gint ключ для сравнения с `v1`.
Возвращает :	`TRUE` если оба ключа равны.

g_int_hash ()

guint g_int_hash (gconstpointer v);

Конвертирует указатель на gint в хеш значение. Она может быть помещена в g_hash_table_new() как параметр hash_func, используя в качестве указателей на целочисленные значения ключи в GHashTable.

`v` :	указатель на gint ключ
Возвращает :	хеш значение соответствующее ключу.

g_str_equal ()

gboolean    g_str_equal                     (gconstpointer v1,
                                             gconstpointer v2);

Сравнивает две строки и возвращает TRUE если они равны. Она может быть помещена в g_hash_table_new() как параметр key_equal_func, используя в качестве строк ключи в GHashTable.

`v1` :	ключ.
`v2` :	ключ для сравнения с `v1`.
Возвращает :	`TRUE` если два ключа равны.

g_str_hash ()

guint g_str_hash (gconstpointer v);

Конвертирует строку в хеш значение. Она может помещаться в g_hash_table_new() как параметр hash_func, используя в качестве строки ключ в GHashTable.

`v` :	строка ключ.
Возвращает :	хеш значение соответствующее ключу.

			Справочное описание GLib
Начало \| Описание