ИМЯ¶

hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - операции над ассоциативными массивами

БИБЛИОТЕКА¶

Стандартная библиотека языка C (libc, -lc)

СИНТАКСИС¶

#include <search.h>

int hcreate(size_t nel);
void hdestroy(void);

ENTRY *hsearch(ENTRY item, ACTION action);

#define _GNU_SOURCE         /* смотрите feature_test_macros(7) */
#include <search.h>

int hcreate_r(size_t nel, struct hsearch_data *htab);
void hdestroy_r(struct hsearch_data *htab);

int hsearch_r(ENTRY item, ACTION action, ENTRY **retval,
              struct hsearch_data *htab);

ОПИСАНИЕ¶

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

Функции hcreate_r(), hsearch_r() и hdestroy_r() являются реентерабильными версиями, позволяющими программе создавать более одного массива поиска одномоментно. Последний параметр, htab, указывает на структуру, описывающую массив, с которым работает функция. Программист должен считать, что не знает её формат (т. е., не должен пытаться напрямую читать и изменять её поля).

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

Функция hcreate_r() выполняет тоже, что и hcreate(), но для массива, описанного в структуре *htab. Перед вызовом hcreate_r() структура, на которую указывает htab, должна быть обнулена.

Функция hdestroy() освобождает память, занимаемую массивом, созданным hcreate(). После вызова hdestroy() функцией hcreate() можно создать новый массив. Функция hdestroy_r() выполняет аналогичную задачу для массива, описанного в *htab, который был ранее создан hcreate_r().

Функция hsearch() ищет в массиве элемент с ключом, равным item («равенство» определяется функцией strcmp(3)), и, в случае удачного завершения операции, возвращает указатель на него.

Аргумент item имеет тип ENTRY, который определён в <search.h> следующим образом:

typedef struct entry {


    char *key;


    void *data;
} ENTRY;

Поле key указывает на оканчивающуюся null строку, используемую в качестве ключа для поиска. Поле data указывает на данные, связанные с ключом.

Аргумент action определяет действие, выполняемое hsearch() после неудачного поиска. Его значением должно быть ENTER (указывает, что нужно вставить копию item и вернуть указатель на новый элемент массива) или FIND (нужно вернуть NULL). Если значение action равно FIND, то поле data игнорируется.

Функция hsearch_r() подобна hsearch(), но работает с массивом, указанным в *htab. Функция hsearch_r() отлична от hsearch() в том, что указатель найденного элемента возвращается в *retval, а не как результат работы функции.

ВОЗВРАЩАЕМОЕ ЗНАЧЕНИЕ¶

hcreate() and hcreate_r() return nonzero on success. They return 0 on error, with errno set to indicate the error.

On success, hsearch() returns a pointer to an entry in the hash table. hsearch() returns NULL on error, that is, if action is ENTER and the hash table is full, or action is FIND and item cannot be found in the hash table. hsearch_r() returns nonzero on success, and 0 on error. In the event of an error, these two functions set errno to indicate the error.

ОШИБКИ¶

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

EINVAL

Значение htab равно NULL.

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

ENOMEM

Значение action равно ENTER, значение key не найдено в массиве и в массиве нет места под новый элемент.

ESRCH

Значение action равно FIND и значение key не найдено в массиве.

В POSIX.1 определена только ошибка ENOMEM.

АТРИБУТЫ¶

Описание терминов данного раздела смотрите в attributes(7).

СТАНДАРТЫ¶

Функции hcreate(), hsearch() и hdestroy() взяты из SVr4 и описаны в POSIX.1-2001 и POSIX.1-2008.

Функции hcreate_r(), hsearch_r() и hdestroy_r() являются расширениями GNU.

ПРИМЕЧАНИЯ¶

Реализации ассоциативных массивов более эффективны, если массив содержит достаточно свободного места, чтобы не искать незанятое пространство. Это означает, что обычно, значение nel нужно увеличить на, как минимум, 25% от максимального количества элементов, ожидаемых в массиве.

Функции hdestroy() и hdestroy_r() не освобождают буферы, на которые указывают элементы key и data в массиве (это невозможно сделать, так как неизвестно, были ли выделены эти буферы динамически). Если эти буферы требуется освобождать (возможно, из-за того, что программа много раз создаёт и удаляет массивы, а не создаёт один массив на всё время работы), то программа должна предусмотреть хранилище под используемые структуры, которое позволило бы их освободить.

ОШИБКИ¶

SVr4 and POSIX.1-2001 specify that action is significant only for unsuccessful searches, so that an ENTER should not do anything for a successful search. In libc and glibc (before glibc 2.3), the implementation violates the specification, updating the data for the given key in this case.

Можно добавлять элементы массива, но не удалять.

ПРИМЕРЫ¶

Следующая программа вставляет в массив 24 элемента, а затем выводит на печать некоторые из них:

#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *data[] = { "alpha", "bravo", "charlie", "delta",


     "echo", "foxtrot", "golf", "hotel", "india", "juliet",


     "kilo", "lima", "mike", "november", "oscar", "papa",


     "quebec", "romeo", "sierra", "tango", "uniform",


     "victor", "whisky", "x-ray", "yankee", "zulu"
};
int
main(void)
{


    ENTRY e;


    ENTRY *ep;


    hcreate(30);


    for (size_t i = 0; i < 24; i++) {


        e.key = data[i];


        /* data is just an integer, instead of a


           pointer to something */


        e.data = (void *) i;


        ep = hsearch(e, ENTER);


        /* there should be no failures */


        if (ep == NULL) {


            fprintf(stderr, "entry failed\n");


            exit(EXIT_FAILURE);


        }


    }


    for (size_t i = 22; i < 26; i++) {


        /* print two entries from the table, and


           show that two are not in the table */


        e.key = data[i];


        ep = hsearch(e, FIND);


        printf("%9.9s -> %9.9s:%d\n", e.key,


               ep ? ep->key : "NULL", ep ? (int)(ep->data) : 0);


    }


    hdestroy();


    exit(EXIT_SUCCESS);
}

СМОТРИТЕ ТАКЖЕ¶

bsearch(3), lsearch(3), malloc(3), tsearch(3)

ПЕРЕВОД¶

Русский перевод этой страницы руководства разработал(и) Yuri Kozlov <yuray@komyakino.ru> и Иван Павлов <pavia00@gmail.com>

Этот перевод является свободной программной документацией; он распространяется на условиях общедоступной лицензии GNU (GNU General Public License - GPL, https://www.gnu.org/licenses/gpl-3.0.html версии 3 или более поздней) в отношении авторского права, но БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ.

Если вы обнаружите какие-либо ошибки в переводе этой страницы руководства, пожалуйста, сообщите об этом разработчику(ам) по его(их) адресу(ам) электронной почты или по адресу списка рассылки русских переводчиков.