hcreate*(), hdestroy*(), hsearch*()

Управление ассоциативным массивом (хэш-таблицей)

Прототип:

#include <search.h>
        
int hcreate( size_t nel );
int hcreate_r( size_t nel, struct hsearch_data *table );
        
void hdestroy( void );
void hdestroy1( void (*freekey)( void * ), void (*freedata)( void * ) );
void hdestroy_r( struct hsearch_data *table );
void hdestroy1_r( struct hsearch_data *table, void (*freekey)( void * ), void (*freedata)( void * ) );
        
ENTRY * hsearch( ENTRY item, ACTION action );
int hsearch_r( ENTRY item, ACTION action, ENTRY **itemp, struct hsearch_data *table );

Аргументы:

nel
Оценка максимального количества записей в хэш-таблице.
table
Указатель на хэш-таблицу.
freekey
Функция освобождения ключа.
freedata
Функция освобождения значения.
item
Ключ данных, которые необходимо найти. Структура ENTRY содержит два указателя:
char *key
Ключ выполнения поиска и сравнения.
void *data
Указатель на данные, связанные с ключом.
action
Действие, выполняемое hsearch*() при неудачном поиске. Перечисление ACTION определяет следующие значения:
ENTER
Добавляет новую запись в хэш-таблицу. Если найдена существующая запись с таким же ключем, она не заменяется. Обратите внимание что ключ и данные элемента используются непосредственно новой записью в хэш-таблице. Хранилище для ключа не должно изменяться в течение всего времени существования хэш-таблицы.
FIND
Поиск в хэш-таблице без добавления новой записи.

Библиотека:

libc

Описание:

Функции hcreate*(), hdestroy*() и hsearch*() управляют хэш-таблицей.

Функция hcreate() выделяет память и инициализирует хэш-таблицу. Параметр nel указывает оценку максимального количества записей, которые должны хранится в хэш-таблице. Если дополнительное выделение памяти не приведет к сбою, задание недостаточного значения nel не приведет к нерабочему состоянию, однако может привести к снижению производительности. Инициализация с помощью функции hcreate() обязательна перед любыми операциями с использованием функции hsearch().

Функция hdestroy() уничтожает хэш-таблицу ранее созданную с помощью hcreate(). После вызова hdestroy() данные больше не могут быть доступны.

Функция hsearch() используется для поиска в хэш-таблице и возвращает указатель на запись в хэш-таблице. Параметр item имеет тип ENTRY, определенный в <search.h>. Для сравнения ключей в hsearch() используется strcmp().

Функции hdestroy() и hdestroy_r() не освобождают данные, связанные с ключем и значением каждой записи, так как они не выделяли их. Поскольку функция «итератор» не предусмотрена, функции hdestroy1() и hdestroy1_r() позволяют управлять освобождением ключа или значения с помощью предоставленных в параметрах функций freekey() и freedata().

Caution: Если freekey() и freedata() равны NULL, то ключ и значение не освобождаются, что может привести к утечкам памяти.

Функции hcreate_r(), hdestroy_r(), hdestroy1_r(), hsearch_r() являются реентерабельными версиями соответствующих функций, которые могут оперировать с хэш-таблицей, предоставленной пользователем. Функция hsearch_r() возвращает 0 если параметр action имеет значение ENTER и новая запись не может быть создана, иначе возвращается 1. Если запись уже существует или может быть создана, она помещается в itemp, иначе itemp устанавливается в NULL.

Функции hcreate_r(), hdestroy1(), hdestroy_r(), hdestroy1_r(), hsearch_r() поддерживаются, начиная с ЗОСРВ «Нейтрино» редакции 2021

Возвращаемое значение:

В случае успеха, функции hcreate() и hcreate_r() возвращают ненулевое значение. Иначе возвращается значение 0 и errno устанавливается для индикации ошибки.

Функции hdestroy() и hdestroy_r() не возвращают значение.

В случае успеха, функция hsearch() возвращает указатель на запись в хэш-таблице, соответствующую предоставленному ключу. Если параметр action имеет значение FIND и запись не была найдена, или если параметр action имеет значение ENTER и новая запись не может быть создана, возвращается NULL и errno устанавливается для индикации ошибки. Если параметр action имеет значение ENTER и в хэш-таблице уже существует запись, соответствующая предоставленному ключу, существующая запись возвращается.

Функция hsearch_r() возвращает 1 если хеш-таблица не заполнена, иначе возвращает 0. Если функция hsearch_r() возвращает 0 или запись не найдена, errno устанавливается для индикации ошибки.

Caution: По крайней мере, можно упомянуть следующие ограничения:
  • Оригинальный интерфейс позволяет использование только одну хэш-таблицу за раз.
  • Отдельные записи хэш-таблицы могут быть добавлены, но не удалены.
  • Нет итератора для сканирования всех записей в таблице.

Коды ошибок:

Функции hcreate(), hcreate_r(), hsearch() и hsearch_r() могут завершаться со следующей ошибкой:

ENOMEM
Недостаточно памяти.

Функции hsearch() и hsearch_r() могут также завершиться с ошибкой если параметр action имеет значение FIND и запись не была найдена:

ESRCH
Предоставленный элемент не найден.

Примеры:

Пример ниже читает строки, завершающиеся двумя числами, и помещает их в хэш таблицу, отбрасывая дубликаты. Затем он читает строки, находит соответствующую запись в таблице и выводит ее.

#include <stdio.h>
#include <search.h>
#include <string.h>
#include <stdlib.h>
        
struct info {               /* this is the info stored in table */
    int         age, room;  /* other than the key */
};
        
#define NUM_EMPL 5000 /* # of elements in search table */
int main( void )
{
    char        string_space[NUM_EMPL*20];  /* space to store strings */
    struct info info_space[NUM_EMPL];       /* space to store employee info */
    char        *str_ptr  = string_space;   /* next avail space in string_space */
    struct info *info_ptr = info_space;     /* next avail space in info_space */
    ENTRY       item, *found_item;
    char        name_to_find[30];           /* name to look for in table */
    int         i         = 0;
        
    /* create table */
    (void)hcreate( NUM_EMPL );
    while ( scanf( "%s%d%d", str_ptr, &info_ptr->age, &info_ptr->room ) != EOF && i++ < NUM_EMPL )
    {
        /* put info in structure, and structure in item */
        item.key   = str_ptr;
        item.data  = (void *)info_ptr;
        str_ptr   += strlen( str_ptr ) + 1;
        info_ptr++;
        /* put item into table */
        (void)hsearch( item, ENTER );
    }
        
    freopen( "/dev/tty", "r", stdin );
        
    /* access table */
    item.key = name_to_find;
    while ( scanf( "%s", item.key ) != EOF )
    {
        if ( (found_item = hsearch( item, FIND )) != NULL )
            /* if item is in the table */
            (void)printf( "found %s, age = %d, room = %d\n", found_item->key,
                          ((struct info *)found_item->data)->age,
                          ((struct info *)found_item->data)->room );
        else
            (void)printf( "no such employee %s\n", name_to_find );
    }
    hdestroy();
        
    return (0);
}

Классификация:

POSIX 1003.1 X/Open Systems Interfaces Extension

Безопасность использования
Точка остановки потока
Нет
Обработчик прерываний
Нет
Обработчик сигналов
Да
В потоке
Да

Тематические ссылки:

bsearch(), free() lsearch() malloc() strcmp()




Предыдущий раздел: Описание API системной библиотеки