.\" $FreeBSD: src/lib/libc/stdlib/hcreate.3,v 1.2 2001/07/09 15:54:36 ru Exp $
|
.\" $FreeBSD: src/lib/libc/stdlib/hcreate.3,v 1.2 2001/07/09 15:54:36 ru Exp $
|
.\"
|
.\"
|
.Dd May 8, 2001
|
.Dd May 8, 2001
|
.Os
|
.Os
|
.Dt HCREATE 3
|
.Dt HCREATE 3
|
.Sh NAME
|
.Sh NAME
|
.Nm hcreate , hdestroy , hsearch
|
.Nm hcreate , hdestroy , hsearch
|
.Nd manage hash search table
|
.Nd manage hash search table
|
.Sh LIBRARY
|
.Sh LIBRARY
|
.Lb libc
|
.Lb libc
|
.Sh SYNOPSIS
|
.Sh SYNOPSIS
|
.In search.h
|
.In search.h
|
.Ft int
|
.Ft int
|
.Fn hcreate "size_t nel"
|
.Fn hcreate "size_t nel"
|
.Ft void
|
.Ft void
|
.Fn hdestroy void
|
.Fn hdestroy void
|
.Ft ENTRY *
|
.Ft ENTRY *
|
.Fn hsearch "ENTRY item" "ACTION action"
|
.Fn hsearch "ENTRY item" "ACTION action"
|
.Sh DESCRIPTION
|
.Sh DESCRIPTION
|
The
|
The
|
.Fn hcreate ,
|
.Fn hcreate ,
|
.Fn hdestroy ,
|
.Fn hdestroy ,
|
and
|
and
|
.Fn hsearch
|
.Fn hsearch
|
functions manage hash search tables.
|
functions manage hash search tables.
|
.Pp
|
.Pp
|
The
|
The
|
.Fn hcreate
|
.Fn hcreate
|
function allocates sufficient space for the table, and the application should
|
function allocates sufficient space for the table, and the application should
|
ensure it is called before
|
ensure it is called before
|
.Fn hsearch
|
.Fn hsearch
|
is used.
|
is used.
|
The
|
The
|
.Fa nel
|
.Fa nel
|
argument is an estimate of the maximum
|
argument is an estimate of the maximum
|
number of entries that the table should contain.
|
number of entries that the table should contain.
|
This number may be adjusted upward by the
|
This number may be adjusted upward by the
|
algorithm in order to obtain certain mathematically favorable circumstances.
|
algorithm in order to obtain certain mathematically favorable circumstances.
|
.Pp
|
.Pp
|
The
|
The
|
.Fn hdestroy
|
.Fn hdestroy
|
function disposes of the search table, and may be followed by another call to
|
function disposes of the search table, and may be followed by another call to
|
.Fn hcreate .
|
.Fn hcreate .
|
After the call to
|
After the call to
|
.Fn hdestroy ,
|
.Fn hdestroy ,
|
the data can no longer be considered accessible.
|
the data can no longer be considered accessible.
|
.Pp
|
.Pp
|
The
|
The
|
.Fn hsearch
|
.Fn hsearch
|
function is a hash-table search routine.
|
function is a hash-table search routine.
|
It returns a pointer into a hash table
|
It returns a pointer into a hash table
|
indicating the location at which an entry can be found.
|
indicating the location at which an entry can be found.
|
The
|
The
|
.Fa item
|
.Fa item
|
argument is a structure of type
|
argument is a structure of type
|
.Vt ENTRY
|
.Vt ENTRY
|
(defined in the
|
(defined in the
|
.Aq Pa search.h
|
.Aq Pa search.h
|
header) containing two pointers:
|
header) containing two pointers:
|
.Fa item.key
|
.Fa item.key
|
points to the comparison key (a
|
points to the comparison key (a
|
.Vt "char *" ) ,
|
.Vt "char *" ) ,
|
and
|
and
|
.Fa item.data
|
.Fa item.data
|
(a
|
(a
|
.Vt "void *" )
|
.Vt "void *" )
|
points to any other data to be associated with
|
points to any other data to be associated with
|
that key.
|
that key.
|
The comparison function used by
|
The comparison function used by
|
.Fn hsearch
|
.Fn hsearch
|
is
|
is
|
.Xr strcmp 3 .
|
.Xr strcmp 3 .
|
The
|
The
|
.Fa action
|
.Fa action
|
argument is a
|
argument is a
|
member of an enumeration type
|
member of an enumeration type
|
.Vt ACTION
|
.Vt ACTION
|
indicating the disposition of the entry if it cannot be
|
indicating the disposition of the entry if it cannot be
|
found in the table.
|
found in the table.
|
.Dv ENTER
|
.Dv ENTER
|
indicates that the
|
indicates that the
|
.Fa item
|
.Fa item
|
should be inserted in the table at an
|
should be inserted in the table at an
|
appropriate point.
|
appropriate point.
|
.Dv FIND
|
.Dv FIND
|
indicates that no entry should be made.
|
indicates that no entry should be made.
|
Unsuccessful resolution is
|
Unsuccessful resolution is
|
indicated by the return of a
|
indicated by the return of a
|
.Dv NULL
|
.Dv NULL
|
pointer.
|
pointer.
|
.Sh RETURN VALUES
|
.Sh RETURN VALUES
|
The
|
The
|
.Fn hcreate
|
.Fn hcreate
|
function returns 0 if it cannot allocate sufficient space for the table;
|
function returns 0 if it cannot allocate sufficient space for the table;
|
otherwise, it returns non-zero.
|
otherwise, it returns non-zero.
|
.Pp
|
.Pp
|
The
|
The
|
.Fn hdestroy
|
.Fn hdestroy
|
function does not return a value.
|
function does not return a value.
|
.Pp
|
.Pp
|
The
|
The
|
.Fn hsearch
|
.Fn hsearch
|
function returns a
|
function returns a
|
.Dv NULL
|
.Dv NULL
|
pointer if either the
|
pointer if either the
|
.Fa action
|
.Fa action
|
is
|
is
|
.Dv FIND
|
.Dv FIND
|
and the
|
and the
|
.Fa item
|
.Fa item
|
could not be found or the
|
could not be found or the
|
.Fa action
|
.Fa action
|
is
|
is
|
.Dv ENTER
|
.Dv ENTER
|
and the table is full.
|
and the table is full.
|
.Sh ERRORS
|
.Sh ERRORS
|
The
|
The
|
.Fn hcreate
|
.Fn hcreate
|
and
|
and
|
.Fn hsearch
|
.Fn hsearch
|
functions may fail if:
|
functions may fail if:
|
.Bl -tag -width Er
|
.Bl -tag -width Er
|
.It Bq Er ENOMEM
|
.It Bq Er ENOMEM
|
Insufficient storage space is available.
|
Insufficient storage space is available.
|
.El
|
.El
|
.Sh EXAMPLES
|
.Sh EXAMPLES
|
The following example reads in strings followed by two numbers
|
The following example reads in strings followed by two numbers
|
and stores them in a hash table, discarding duplicates.
|
and stores them in a hash table, discarding duplicates.
|
It then reads in strings and finds the matching entry in the hash
|
It then reads in strings and finds the matching entry in the hash
|
table and prints it out.
|
table and prints it out.
|
.Bd -literal
|
.Bd -literal
|
#include
|
#include
|
#include
|
#include
|
#include
|
#include
|
|
|
struct info { /* This is the info stored in the table */
|
struct info { /* This is the info stored in the table */
|
int age, room; /* other than the key. */
|
int age, room; /* other than the key. */
|
};
|
};
|
|
|
#define NUM_EMPL 5000 /* # of elements in search table. */
|
#define NUM_EMPL 5000 /* # of elements in search table. */
|
|
|
int
|
int
|
main(void)
|
main(void)
|
{
|
{
|
char string_space[NUM_EMPL*20]; /* Space to store strings. */
|
char string_space[NUM_EMPL*20]; /* Space to store strings. */
|
struct info info_space[NUM_EMPL]; /* Space to store employee info. */
|
struct info info_space[NUM_EMPL]; /* Space to store employee info. */
|
char *str_ptr = string_space; /* Next space in string_space. */
|
char *str_ptr = string_space; /* Next space in string_space. */
|
struct info *info_ptr = info_space; /* Next space in info_space. */
|
struct info *info_ptr = info_space; /* Next space in info_space. */
|
ENTRY item;
|
ENTRY item;
|
ENTRY *found_item; /* Name to look for in table. */
|
ENTRY *found_item; /* Name to look for in table. */
|
char name_to_find[30];
|
char name_to_find[30];
|
int i = 0;
|
int i = 0;
|
|
|
/* Create table; no error checking is performed. */
|
/* Create table; no error checking is performed. */
|
(void) hcreate(NUM_EMPL);
|
(void) hcreate(NUM_EMPL);
|
|
|
while (scanf("%s%d%d", str_ptr, &info_ptr->age,
|
while (scanf("%s%d%d", str_ptr, &info_ptr->age,
|
&info_ptr->room) != EOF && i++ < NUM_EMPL) {
|
&info_ptr->room) != EOF && i++ < NUM_EMPL) {
|
/* Put information in structure, and structure in item. */
|
/* Put information in structure, and structure in item. */
|
item.key = str_ptr;
|
item.key = str_ptr;
|
item.data = info_ptr;
|
item.data = info_ptr;
|
str_ptr += strlen(str_ptr) + 1;
|
str_ptr += strlen(str_ptr) + 1;
|
info_ptr++;
|
info_ptr++;
|
/* Put item into table. */
|
/* Put item into table. */
|
(void) hsearch(item, ENTER);
|
(void) hsearch(item, ENTER);
|
}
|
}
|
|
|
/* Access table. */
|
/* Access table. */
|
item.key = name_to_find;
|
item.key = name_to_find;
|
while (scanf("%s", item.key) != EOF) {
|
while (scanf("%s", item.key) != EOF) {
|
if ((found_item = hsearch(item, FIND)) != NULL) {
|
if ((found_item = hsearch(item, FIND)) != NULL) {
|
/* If item is in the table. */
|
/* If item is in the table. */
|
(void)printf("found %s, age = %d, room = %d\en",
|
(void)printf("found %s, age = %d, room = %d\en",
|
found_item->key,
|
found_item->key,
|
((struct info *)found_item->data)->age,
|
((struct info *)found_item->data)->age,
|
((struct info *)found_item->data)->room);
|
((struct info *)found_item->data)->room);
|
} else
|
} else
|
(void)printf("no such employee %s\en", name_to_find);
|
(void)printf("no such employee %s\en", name_to_find);
|
}
|
}
|
return 0;
|
return 0;
|
}
|
}
|
.Ed
|
.Ed
|
.Sh SEE ALSO
|
.Sh SEE ALSO
|
.Xr bsearch 3 ,
|
.Xr bsearch 3 ,
|
.Xr lsearch 3 ,
|
.Xr lsearch 3 ,
|
.Xr malloc 3 ,
|
.Xr malloc 3 ,
|
.Xr strcmp 3 ,
|
.Xr strcmp 3 ,
|
.Xr tsearch 3
|
.Xr tsearch 3
|
.Sh STANDARDS
|
.Sh STANDARDS
|
The
|
The
|
.Fn hcreate ,
|
.Fn hcreate ,
|
.Fn hdestroy ,
|
.Fn hdestroy ,
|
and
|
and
|
.Fn hsearch
|
.Fn hsearch
|
functions conform to
|
functions conform to
|
.St -xpg4.2 .
|
.St -xpg4.2 .
|
.Sh HISTORY
|
.Sh HISTORY
|
The
|
The
|
.Fn hcreate ,
|
.Fn hcreate ,
|
.Fn hdestroy ,
|
.Fn hdestroy ,
|
and
|
and
|
.Fn hsearch
|
.Fn hsearch
|
functions first appeared in
|
functions first appeared in
|
.At V .
|
.At V .
|
.Sh BUGS
|
.Sh BUGS
|
The interface permits the use of only one hash table at a time.
|
The interface permits the use of only one hash table at a time.
|
|
|
