Add new, from scratch implementation of hsearch() et al that actually works.

Obtained from:	NetBSD
MFC after:	1 month

1 files changed, 206 insertions, 0 deletions

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