Module Name: src
Committed By: christos
Date: Sun Jul 20 13:34:17 UTC 2014
Modified Files:
src/include: search.h
src/lib/libc/stdlib: Makefile.inc hcreate.3 hcreate.c
Log Message:
Our hdestroy implementation was non-conformant because it freed the key of
each entry. Add a new function hdestroy1 that allows the user to control
what gets freed. Pointed out by Pedro Giffuni at FreeBSD.
To generate a diff of this commit:
cvs rdiff -u -r1.20 -r1.21 src/include/search.h
cvs rdiff -u -r1.81 -r1.82 src/lib/libc/stdlib/Makefile.inc
cvs rdiff -u -r1.10 -r1.11 src/lib/libc/stdlib/hcreate.3
cvs rdiff -u -r1.8 -r1.9 src/lib/libc/stdlib/hcreate.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/include/search.h
diff -u src/include/search.h:1.20 src/include/search.h:1.21
--- src/include/search.h:1.20 Sat Apr 27 17:35:25 2013
+++ src/include/search.h Sun Jul 20 09:34:17 2014
@@ -1,4 +1,4 @@
-/* $NetBSD: search.h,v 1.20 2013/04/27 21:35:25 joerg Exp $ */
+/* $NetBSD: search.h,v 1.21 2014/07/20 13:34:17 christos Exp $ */
/*
* Written by J.T. Conklin <j...@netbsd.org>
@@ -62,8 +62,12 @@ void hdestroy(void);
ENTRY *hsearch(ENTRY, ACTION);
#ifdef _NETBSD_SOURCE
+#define FREE_KEY 1
+#define FREE_DATA 2
+void hdestroy1(int);
int hcreate_r(size_t, struct hsearch_data *);
void hdestroy_r(struct hsearch_data *);
+void hdestroy1_r(struct hsearch_data *, int);
int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
#endif /* _NETBSD_SOURCE */
Index: src/lib/libc/stdlib/Makefile.inc
diff -u src/lib/libc/stdlib/Makefile.inc:1.81 src/lib/libc/stdlib/Makefile.inc:1.82
--- src/lib/libc/stdlib/Makefile.inc:1.81 Tue Jan 7 21:15:42 2014
+++ src/lib/libc/stdlib/Makefile.inc Sun Jul 20 09:34:17 2014
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.81 2014/01/08 02:15:42 christos Exp $
+# $NetBSD: Makefile.inc,v 1.82 2014/07/20 13:34:17 christos Exp $
# from: @(#)Makefile.inc 8.3 (Berkeley) 2/4/95
# stdlib sources
@@ -66,6 +66,7 @@ MLINKS+=getenv.3 setenv.3 getenv.3 unset
MLINKS+=getenv.3 getenv_r.3
MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3
MLINKS+=hcreate.3 hcreate_r.3 hcreate.3 hdestroy_r.3 hcreate.3 hsearch_r.3
+MLINKS+=hcreate.3 hdestroy1.3 hcreate.3 hdestroy1_r.3
MLINKS+=insque.3 remque.3
MLINKS+=lsearch.3 lfind.3
MLINKS+=malloc.3 calloc.3 malloc.3 realloc.3 malloc.3 free.3
Index: src/lib/libc/stdlib/hcreate.3
diff -u src/lib/libc/stdlib/hcreate.3:1.10 src/lib/libc/stdlib/hcreate.3:1.11
--- src/lib/libc/stdlib/hcreate.3:1.10 Thu Sep 15 05:14:54 2011
+++ src/lib/libc/stdlib/hcreate.3 Sun Jul 20 09:34:17 2014
@@ -1,4 +1,4 @@
-.\" $NetBSD: hcreate.3,v 1.10 2011/09/15 09:14:54 wiz Exp $
+.\" $NetBSD: hcreate.3,v 1.11 2014/07/20 13:34:17 christos Exp $
.\"
.\" Copyright (c) 1999 The NetBSD Foundation, Inc.
.\" All rights reserved.
@@ -27,14 +27,16 @@
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
-.Dd September 14, 2011
+.Dd July 20, 2014
.Dt HCREATE 3
.Os
.Sh NAME
.Nm hcreate ,
.Nm hcreate_r ,
.Nm hdestroy ,
+.Nm hdestroy1 ,
.Nm hdestroy_r ,
+.Nm hdestroy1_r ,
.Nm hsearch ,
.Nm hsearch_r
.Nd manage hash search table
@@ -49,7 +51,11 @@
.Ft void
.Fn hdestroy "void"
.Ft void
+.Fn hdestroy1 "int flags"
+.Ft void
.Fn hdestroy_r "struct hsearch_data *table"
+.Ft void
+.Fn hdestroy1_r "struct hsearch_data *table" "int flags"
.Ft ENTRY *
.Fn hsearch "ENTRY item" "ACTION action"
.Ft int
@@ -60,6 +66,8 @@ The
.Fn hcreate_r ,
.Fn hdestroy ,
.Fn hdestroy_r
+.Fn hdestroy1 ,
+.Fn hdestroy1_r
.Fn hsearch ,
and
.Fn hsearch_r
@@ -141,33 +149,49 @@ Search the hash table without inserting
.Fa item .
.El
.Pp
-Note that the comparison
-.Fa key
-must be allocated using
-.Xr malloc 3
-or
-.Xr calloc 3
-if action is
-.Dv ENTER
-and
-.Fn hdestroy
-will be called.
-This is because
+The traditional
.Fn hdestroy
-will call
+and
+.Fn hdestroy_r
+functions don't
.Xr free 3
-for each comparison
+the data associated with the
+.Fa key
+and
+.Fa value
+of each entry, because they did not allocate them.
+Since there is no
+.Dq iterator
+function provided, the
+.Fn hdestroy1
+and
+.Fn hdestroy1_r
+allow controlling if the
.Fa key
-(but not
-.Fa data ) .
-Typically the comparison
+or
+.Fa value
+will be freed using the
+.Fa flags
+argument.
+If the bit
+.Dv FREE_KEY
+is set, then the
.Fa key
-is allocated by using
-.Xr strdup 3 .
+of each entry will be
+passed to
+.Xr free 3 .
+If the bit
+.Dv FREE_VALUE
+is set, then the
+.Fa value
+of each entry will be
+passed to
+.Xr free 3 .
.Pp
The
.Fn hcreate_r ,
.Fn hdestroy_r ,
+.Fn hdestroy1_r ,
and
.Fn hsearch_r
functions are re-entrant versions of the above functions that can
@@ -266,6 +290,7 @@ given is not found.
.Xr bsearch 3 ,
.Xr lsearch 3 ,
.Xr malloc 3 ,
+.Xr free 3 ,
.Xr strcmp 3
.Sh STANDARDS
The
@@ -291,6 +316,13 @@ and
functions are
.Tn GNU
extensions.
+The
+.Fn hdestroy1
+and
+.Fn hdestroy1_r
+are
+.Nx
+extensions.
.Sh CAVEATS
At least the following limitations can be mentioned:
.Bl -bullet
@@ -301,20 +333,5 @@ interface permits the use of only one ha
.It
Individual hash table entries can be added, but not deleted.
.It
-The standard is indecipherable about the
-internal memory usage of the functions,
-mentioning only that
-.Do
-.Fn hcreate
-and
-.Fn hsearch
-functions may use
-.Fn malloc
-to allocate space
-.Dc .
-This limits the portability of the functions,
-given that other implementations may not
-.Xr free 3
-the buffer pointed by
-.Fa key .
+There is no iterator to scan for all entries in the table.
.El
Index: src/lib/libc/stdlib/hcreate.c
diff -u src/lib/libc/stdlib/hcreate.c:1.8 src/lib/libc/stdlib/hcreate.c:1.9
--- src/lib/libc/stdlib/hcreate.c:1.8 Sat Sep 17 12:54:39 2011
+++ src/lib/libc/stdlib/hcreate.c Sun Jul 20 09:34:17 2014
@@ -1,4 +1,4 @@
-/* $NetBSD: hcreate.c,v 1.8 2011/09/17 16:54:39 christos Exp $ */
+/* $NetBSD: hcreate.c,v 1.9 2014/07/20 13:34:17 christos Exp $ */
/*
* Copyright (c) 2001 Christopher G. Demetriou
@@ -43,7 +43,7 @@
#include <sys/cdefs.h>
#if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: hcreate.c,v 1.8 2011/09/17 16:54:39 christos Exp $");
+__RCSID("$NetBSD: hcreate.c,v 1.9 2014/07/20 13:34:17 christos Exp $");
#endif /* LIBC_SCCS and not lint */
#if !defined(lint)
@@ -141,14 +141,20 @@ hcreate_r(size_t nel, struct hsearch_dat
}
void
-hdestroy(void)
+hdestroy1(int flags)
{
_DIAGASSERT(htable.table != NULL);
- hdestroy_r(&htable);
+ hdestroy1_r(&htable, flags);
}
void
-hdestroy_r(struct hsearch_data *head)
+hdestroy(void)
+{
+ hdestroy1(0);
+}
+
+void
+hdestroy1_r(struct hsearch_data *head, int flags)
{
struct internal_entry *ie;
size_t idx;
@@ -166,13 +172,22 @@ hdestroy_r(struct hsearch_data *head)
while (!SLIST_EMPTY(&table[idx])) {
ie = SLIST_FIRST(&table[idx]);
SLIST_REMOVE_HEAD(&table[idx], link);
- free(ie->ent.key);
+ if (flags & FREE_KEY)
+ free(ie->ent.key);
+ if (flags & FREE_DATA)
+ free(ie->ent.data);
free(ie);
}
}
free(table);
}
+void
+hdestroy_r(struct hsearch_data *head)
+{
+ hdestroy1_r(head, 0);
+}
+
ENTRY *
hsearch(ENTRY item, ACTION action)
{
