HSEARCH - Linux手册页

时间:2019-08-20 18:00:35  来源:igfitidea点击:

Linux程序员手册 第3部分
更新日期: 2020-06-09

名称

hcreate,hdestroy,hsearch,hcreate_r,hdestroy_r,hsearch_r-哈希表管理

语法

#include <search.h>

int hcreate(size_t nel);

ENTRY *hsearch(ENTRY item, ACTION action);

void hdestroy(void);

#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include <search.h>

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

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

void hdestroy_r(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()函数在哈希表中搜索与该项目具有相同键(使用strcmp(3)确定"相同")的项目,如果成功,则返回指向该项目的指针。

参数项的类型为ENTRY,其定义如下:

typedef struct entry {
    char *key;
    void *data;
} ENTRY;

字段关键字指向一个以空值结尾的字符串,它是搜索关键字。字段数据指向与该键关联的数据。

参数操作确定搜索不成功后hsearch()的操作。此参数必须具有值ENTER(表示插入项的副本(并返回指向新哈希表条目的指针作为函数结果))或值FIND(表示应返回NULL)。 (如果操作为FIND,则将忽略数据。)

hsearch_r()函数类似于hsearch(),但对* htab描述的哈希表起作用。 hsearch_r()函数与hsearch()的不同之处在于,在* retval中而不是函数结果中返回指向找到的项的指针。

返回值

hcreate()和hcreate_r()成功返回非零值。错误时返回0,并设置errno以指示错误原因。

成功后,hsearch()将返回一个指向哈希表中条目的指针。如果出现错误,则hsearch()返回NULL,即操作为ENTER且哈希表已满,或者操作为FIND且在哈希表中找不到项目。 hsearch_r()成功返回非零,错误返回0。在发生错误的情况下,这两个函数将errno设置为指示错误原因。

错误说明

hcreate_r()和hdestroy_r()可能由于以下原因而失败:

EINVAL
htab为NULL。

hsearch()和hsearch_r()可能由于以下原因而失败:

ENOMEM
操作是ENTER,在表中找不到键,并且表中没有空间添加新条目。
ESRCH
操作是FIND,并且在表中找不到键。

POSIX.1仅指定ENOMEM错误。

属性

有关本节中使用的术语的说明,请参见attribute(7)。

InterfaceAttributeValue
hcreate(),hsearch(),
hdestroy()
Thread safetyMT-Unsafe race:hsearch
hcreate_r(),hsearch_r(),
hdestroy_r()
Thread safetyMT-Safe race:htab

遵循规范

函数hcreate(),hsearch()和hdestroy()来自SVr4,并在POSIX.1-2001和POSIX.1-2008中进行了描述。

函数hcreate_r(),hsearch_r()和hdestroy_r()是GNU扩展。

备注

当表包含足够的可用空间以最小化冲突时,哈希表的实现通常会更高效。通常,这意味着nel应至少比调用者希望在表中存储的最大元素数大25%。

hdestroy()和hdestroy_r()函数不会释放哈希表条目的键和数据元素所指向的缓冲区。 (它无法执行此操作,因为它不知道是否动态分配了这些缓冲区。)是否需要释放这些缓冲区(可能是因为程序反复创建和销毁哈希表,而不是创建其寿命匹配的单个表)程序),则该程序必须维护允许其释放它们的簿记数据结构。

BUGS

SVr4和POSIX.1-2001指定该操作仅对不成功的搜索有意义,因此ENTER不应对成功的搜索执行任何操作。在libc和glibc(2.3版之前)中,实现违反规范,在这种情况下,将更新给定键的数据。

可以添加单个哈希表条目,但不能删除。

示例

下面的程序将24个项目插入哈希表,然后打印其中的一些。

#include <stdio.h>
#include <stdlib.h>
#include <search.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, *ep;
    int i;

    hcreate(30);

    for (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 (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)

出版信息

这个页面是Linux手册页项目5.08版的一部分。有关项目的说明、有关报告错误的信息以及此页面的最新版本,请访问https://www.kernel.org/doc/man-pages/