hsearch()

Искать ключ в ассоциативном массиве (хэш-таблице)

Прототип:

#include <search.h>
                                       
ENTRY * hsearch( ENTRY item, 
                 ACTION action );

Аргументы:

item

Структура типа ENTRY, объявленная в <search.h>, которая содержит:

char *key

указатель на ключ, используемый при сравнении записей.

void *data

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

action

Перечислитель типа ACTION, также объявленный в <search.h>, определяющий действие, которое применяется в случае отсуствия записи в таблице.

ENTER

добавляет новую запись в таблицу в соответствующем месте. Если новая запись дублирует существующую, добавления не происходит, и hsearch() возвращает указатель на существующую.

FIND

не добавляет новую запись в таблицу. Если запись не найдена, hsearch() возвращает NULL.

Библиотека:

libc

Описание:

Функция hsearch() ищет запись согласно алгоритму D (6.4) из монографии под авторством Д.Кнута (см. Тематические ссылки). Перед использованием функции необходимо вызвать hcreate() для создания хэш-таблицы.

Функция hsearch() возвращает указатель на место в хэш-таблице, где находится запись. Эта функция использует strcmp() в качестве функция сравнения.

Функции hsearch() и hcreate() используют malloc() для выделения памяти.

Единовременно может быть использована только одна хэш-таблица. Для удаления таблицы можно использовать hdestroy().

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

Найденный указатель или NULL в случаях, когда действие FIND не найдено, или когда передано действие ENTER, но таблица полностью занята.

Примеры:

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

#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 );
    }
                                       
    /* 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(), hcreate(), hdestroy(), malloc(), strcmp()

"The Art of Computer Programming, Volume 3, Sorting and Searching"/ Donald E. Knuth. — Addison-Wesley Publishing Company, 1973

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