Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 13 Oct 2016 18:25:40 +0000 (UTC)
From:      Ed Schouten <ed@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r307227 - in head: include lib/libc/stdlib lib/libc/tests/stdlib
Message-ID:  <201610131825.u9DIPeXH066703@repo.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: ed
Date: Thu Oct 13 18:25:40 2016
New Revision: 307227
URL: https://svnweb.freebsd.org/changeset/base/307227

Log:
  Improve typing of POSIX search tree functions.
  
  Back in 2015 when I reimplemented these functions to use an AVL tree, I
  was annoyed by the weakness of the typing of these functions. Both tree
  nodes and keys are represented by 'void *', meaning that things like the
  documentation for these functions are an absolute train wreck.
  
  To make things worse, users of these functions need to cast the return
  value of tfind()/tsearch() from 'void *' to 'type_of_key **' in order to
  access the key. Technically speaking such casts violate aliasing rules.
  I've observed actual breakages as a result of this by enabling features
  like LTO.
  
  I've filed a bug report at the Austin Group. Looking at the way the bug
  got resolved, they made a pretty good step in the right direction. A new
  type 'posix_tnode' has been added to correspond to tree nodes. It is
  still defined as 'void' for source-level compatibility, but in the very
  far future it could be replaced by a proper structure type containing a
  key pointer.
  
  MFC after:	1 month
  Differential Revision:	https://reviews.freebsd.org/D8205

Modified:
  head/include/search.h
  head/lib/libc/stdlib/tdelete.c
  head/lib/libc/stdlib/tfind.c
  head/lib/libc/stdlib/tsearch.3
  head/lib/libc/stdlib/tsearch.c
  head/lib/libc/stdlib/twalk.c
  head/lib/libc/tests/stdlib/tsearch_test.c

Modified: head/include/search.h
==============================================================================
--- head/include/search.h	Thu Oct 13 18:02:29 2016	(r307226)
+++ head/include/search.h	Thu Oct 13 18:25:40 2016	(r307227)
@@ -34,16 +34,18 @@ typedef	enum {
 } VISIT;
 
 #ifdef _SEARCH_PRIVATE
-typedef	struct node {
-	void         *key;
-	struct node  *llink, *rlink;
-	signed char   balance;
-} node_t;
+typedef struct __posix_tnode {
+	void			*key;
+	struct __posix_tnode	*llink, *rlink;
+	signed char		 balance;
+} posix_tnode;
 
 struct que_elem {
 	struct que_elem *next;
 	struct que_elem *prev;
 };
+#else
+typedef void posix_tnode;
 #endif
 
 #if __BSD_VISIBLE
@@ -62,12 +64,15 @@ void	*lfind(const void *, const void *, 
 void	*lsearch(const void *, void *, size_t *, size_t,
 	    int (*)(const void *, const void *));
 void	 remque(void *);
-void	*tdelete(const void * __restrict, void ** __restrict,
+void	*tdelete(const void * __restrict, posix_tnode ** __restrict,
 	    int (*)(const void *, const void *));
-void	*tfind(const void *, void * const *,
+posix_tnode *
+	 tfind(const void *, posix_tnode * const *,
 	    int (*)(const void *, const void *));
-void	*tsearch(const void *, void **, int (*)(const void *, const void *));
-void	 twalk(const void *, void (*)(const void *, VISIT, int));
+posix_tnode *
+	 tsearch(const void *, posix_tnode **,
+	    int (*)(const void *, const void *));
+void	 twalk(const posix_tnode *, void (*)(const posix_tnode *, VISIT, int));
 
 #if __BSD_VISIBLE
 int	 hcreate_r(size_t, struct hsearch_data *);

Modified: head/lib/libc/stdlib/tdelete.c
==============================================================================
--- head/lib/libc/stdlib/tdelete.c	Thu Oct 13 18:02:29 2016	(r307226)
+++ head/lib/libc/stdlib/tdelete.c	Thu Oct 13 18:25:40 2016	(r307227)
@@ -46,9 +46,9 @@ __FBSDID("$FreeBSD$");
 		 * that we won't need to perform any rotations above	\
 		 * this point. In this case rotations are always	\
 		 * capable of keeping the subtree in balance. Make	\
-		 * this the base node and reset the path.		\
+		 * this the root node and reset the path.		\
 		 */							\
-		base = leaf;						\
+		rootp = leaf;						\
 		path_init(&path);					\
 	}								\
 	path_taking_left(&path);					\
@@ -59,7 +59,7 @@ __FBSDID("$FreeBSD$");
 #define	GO_RIGHT() do {							\
 	if ((*leaf)->balance == 0 ||					\
 	    ((*leaf)->balance > 0 && (*leaf)->llink->balance == 0)) {	\
-		base = leaf;						\
+		rootp = leaf;						\
 		path_init(&path);					\
 	}								\
 	path_taking_right(&path);					\
@@ -67,18 +67,16 @@ __FBSDID("$FreeBSD$");
 } while (0)
 
 void *
-tdelete(const void *restrict key, void **restrict rootp,
+tdelete(const void *restrict key, posix_tnode **restrict rootp,
     int (*compar)(const void *, const void *))
 {
 	struct path path;
-	node_t *root, **base, **leaf, *old, **n, *x, *y, *z;
-	void *result;
+	posix_tnode **leaf, *old, **n, *x, *y, *z, *result;
 	int cmp;
 
 	/* POSIX requires that tdelete() returns NULL if rootp is NULL. */
 	if (rootp == NULL)
 		return (NULL);
-	root = *rootp;
 
 	/*
 	 * Find the leaf that needs to be removed. Return if we cannot
@@ -86,19 +84,18 @@ tdelete(const void *restrict key, void *
 	 * to get to the node, as we will need it to adjust the
 	 * balances.
 	 */
-	result = (void *)1;
+	result = (posix_tnode *)1;
 	path_init(&path);
-	base = &root;
-	leaf = &root;
+	leaf = rootp;
 	for (;;) {
 		if (*leaf == NULL)
 			return (NULL);
 		cmp = compar(key, (*leaf)->key);
 		if (cmp < 0) {
-			result = &(*leaf)->key;
+			result = *leaf;
 			GO_LEFT();
 		} else if (cmp > 0) {
-			result = &(*leaf)->key;
+			result = *leaf;
 			GO_RIGHT();
 		} else {
 			break;
@@ -134,7 +131,7 @@ tdelete(const void *restrict key, void *
 	 * and left-left case that only exists when deleting. Hence the
 	 * duplication of code.
 	 */
-	for (n = base; n != leaf;) {
+	for (n = rootp; n != leaf;) {
 		if (path_took_left(&path)) {
 			x = *n;
 			if (x->balance < 0) {
@@ -207,6 +204,5 @@ tdelete(const void *restrict key, void *
 	}
 
 	/* Return the parent of the old entry. */
-	*rootp = root;
 	return (result);
 }

Modified: head/lib/libc/stdlib/tfind.c
==============================================================================
--- head/lib/libc/stdlib/tfind.c	Thu Oct 13 18:02:29 2016	(r307226)
+++ head/lib/libc/stdlib/tfind.c	Thu Oct 13 18:25:40 2016	(r307227)
@@ -4,8 +4,6 @@
  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  * the AT&T man page says.
  *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
  * Written by reading the System V Interface Definition, not the code.
  *
  * Totally public domain.
@@ -29,11 +27,10 @@ __FBSDID("$FreeBSD$");
  * vkey   - key to be found 
  * vrootp - address of the tree root 
  */
-void *
-tfind(const void *vkey, void * const *vrootp,
+posix_tnode *
+tfind(const void *vkey, posix_tnode * const *rootp,
     int (*compar)(const void *, const void *))
 {
-	node_t **rootp = (node_t **)vrootp;
 
 	if (rootp == NULL)
 		return NULL;

Modified: head/lib/libc/stdlib/tsearch.3
==============================================================================
--- head/lib/libc/stdlib/tsearch.3	Thu Oct 13 18:02:29 2016	(r307226)
+++ head/lib/libc/stdlib/tsearch.3	Thu Oct 13 18:25:40 2016	(r307227)
@@ -27,7 +27,7 @@
 .\"	OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp
 .\" $FreeBSD$
 .\"
-.Dd December 6, 2015
+.Dd October 9, 2016
 .Dt TSEARCH 3
 .Os
 .Sh NAME
@@ -36,13 +36,13 @@
 .Sh SYNOPSIS
 .In search.h
 .Ft void *
-.Fn tdelete "const void * restrict key" "void ** restrict rootp" "int (*compar) (const void *, const void *)"
-.Ft void *
-.Fn tfind "const void *key" "void * const *rootp" "int (*compar) (const void *, const void *)"
-.Ft void *
-.Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)"
+.Fn tdelete "const void * restrict key" "posix_tnode ** restrict rootp" "int (*compar) (const void *, const void *)"
+.Ft posix_tnode *
+.Fn tfind "const void *key" "posix_tnode * const *rootp" "int (*compar) (const void *, const void *)"
+.Ft posix_tnode *
+.Fn tsearch "const void *key" "posix_tnode **rootp" "int (*compar) (const void *, const void *)"
 .Ft void
-.Fn twalk "const void *root" "void (*action) (const void *, VISIT, int)"
+.Fn twalk "const posix_tnode *root" "void (*action) (const posix_tnode *, VISIT, int)"
 .Sh DESCRIPTION
 The
 .Fn tdelete ,
@@ -134,3 +134,18 @@ function returns no value.
 .Xr bsearch 3 ,
 .Xr hsearch 3 ,
 .Xr lsearch 3
+.Sh STANDARDS
+These functions conform to
+.St -p1003.1-2008 .
+.Pp
+The
+.Fa posix_tnode
+type is not part of
+.St -p1003.1-2008 ,
+but it is expected to be standardized by future versions of the standard.
+It is defined as
+.Fa void
+for source-level compatibility.
+Using
+.Fa posix_tnode
+makes it easier to distinguish between nodes and keys.

Modified: head/lib/libc/stdlib/tsearch.c
==============================================================================
--- head/lib/libc/stdlib/tsearch.c	Thu Oct 13 18:02:29 2016	(r307226)
+++ head/lib/libc/stdlib/tsearch.c	Thu Oct 13 18:25:40 2016	(r307227)
@@ -32,18 +32,17 @@ __FBSDID("$FreeBSD$");
 
 #include "tsearch_path.h"
 
-void *
-tsearch(const void *key, void **rootp,
+posix_tnode *
+tsearch(const void *key, posix_tnode **rootp,
     int (*compar)(const void *, const void *))
 {
 	struct path path;
-	node_t *root, **base, **leaf, *result, *n, *x, *y, *z;
+	posix_tnode **leaf, *result, *n, *x, *y, *z;
 	int cmp;
 
 	/* POSIX requires that tsearch() returns NULL if rootp is NULL. */
 	if (rootp == NULL)
-	return (NULL);
-		root = *rootp;
+		return (NULL);
 
 	/*
 	 * Find the leaf where the new key needs to be inserted. Return
@@ -52,8 +51,7 @@ tsearch(const void *key, void **rootp,
 	 * balances.
 	*/
 	path_init(&path);
-	base = &root;
-	leaf = &root;
+	leaf = rootp;
 	while (*leaf != NULL) {
 		if ((*leaf)->balance != 0) {
 			/*
@@ -62,9 +60,9 @@ tsearch(const void *key, void **rootp,
 			 * need to perform any rotations above this
 			 * point. In this case rotations are always
 			 * capable of keeping the subtree in balance.
-			 * Make this the base node and reset the path.
+			 * Make this the root node and reset the path.
 			 */
-			base = leaf;
+			rootp = leaf;
 			path_init(&path);
 		}
 		cmp = compar(key, (*leaf)->key);
@@ -75,7 +73,7 @@ tsearch(const void *key, void **rootp,
 			path_taking_right(&path);
 			leaf = &(*leaf)->rlink;
 		} else {
-			return (&(*leaf)->key);
+			return (*leaf);
 		}
 	}
 
@@ -94,7 +92,7 @@ tsearch(const void *key, void **rootp,
 	 * have a balance of zero, meaning that these nodes will not get
 	 * out of balance.
 	*/
-	for (n = *base; n != *leaf;) {
+	for (n = *rootp; n != *leaf;) {
 		if (path_took_left(&path)) {
 			n->balance += 1;
 			n = n->llink;
@@ -106,10 +104,10 @@ tsearch(const void *key, void **rootp,
 
 	/*
 	 * Adjusting the balances may have pushed the balance of the
-	 * base node out of range. Perform a rotation to bring the
+	 * root node out of range. Perform a rotation to bring the
 	 * balance back in range.
 	 */
-	x = *base;
+	x = *rootp;
 	if (x->balance > 1) {
 		y = x->llink;
 		if (y->balance < 0) {
@@ -129,7 +127,7 @@ tsearch(const void *key, void **rootp,
 			z->llink = y;
 			x->llink = z->rlink;
 			z->rlink = x;
-			*base = z;
+			*rootp = z;
 
 			x->balance = z->balance > 0 ? -1 : 0;
 			y->balance = z->balance < 0 ? 1 : 0;
@@ -146,7 +144,7 @@ tsearch(const void *key, void **rootp,
 			 */
 			x->llink = y->rlink;
 			y->rlink = x;
-			*base = y;
+			*rootp = y;
 
 			x->balance = 0;
 			y->balance = 0;
@@ -165,12 +163,12 @@ tsearch(const void *key, void **rootp,
 			 *      / \          A B   C D
 			 *     B   C
 			 */
-			node_t *z = y->llink;
+			posix_tnode *z = y->llink;
 			x->rlink = z->llink;
 			z->llink = x;
 			y->llink = z->rlink;
 			z->rlink = y;
-			*base = z;
+			*rootp = z;
 
 			x->balance = z->balance < 0 ? 1 : 0;
 			y->balance = z->balance > 0 ? -1 : 0;
@@ -187,7 +185,7 @@ tsearch(const void *key, void **rootp,
 			 */
 			x->rlink = y->llink;
 			y->llink = x;
-			*base = y;
+			*rootp = y;
 
 			x->balance = 0;
 			y->balance = 0;
@@ -195,6 +193,5 @@ tsearch(const void *key, void **rootp,
 	}
 
 	/* Return the new entry. */
-	*rootp = root;
-	return (&result->key);
+	return (result);
 }

Modified: head/lib/libc/stdlib/twalk.c
==============================================================================
--- head/lib/libc/stdlib/twalk.c	Thu Oct 13 18:02:29 2016	(r307226)
+++ head/lib/libc/stdlib/twalk.c	Thu Oct 13 18:25:40 2016	(r307227)
@@ -4,8 +4,6 @@
  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  * the AT&T man page says.
  *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
  * Written by reading the System V Interface Definition, not the code.
  *
  * Totally public domain.
@@ -23,12 +21,11 @@ __FBSDID("$FreeBSD$");
 #include <search.h>
 #include <stdlib.h>
 
-typedef void (*cmp_fn_t)(const void *, VISIT, int);
+typedef void (*cmp_fn_t)(const posix_tnode *, VISIT, int);
 
 /* Walk the nodes of a tree */
 static void
-trecurse(const node_t *root,	/* Root of the tree to be walked */
-	cmp_fn_t action, int level)
+trecurse(const posix_tnode *root, cmp_fn_t action, int level)
 {
 
 	if (root->llink == NULL && root->rlink == NULL)
@@ -46,7 +43,7 @@ trecurse(const node_t *root,	/* Root of 
 
 /* Walk the nodes of a tree */
 void
-twalk(const void *vroot, cmp_fn_t action) /* Root of the tree to be walked */
+twalk(const posix_tnode *vroot, cmp_fn_t action)
 {
 	if (vroot != NULL && action != NULL)
 		trecurse(vroot, action, 0);

Modified: head/lib/libc/tests/stdlib/tsearch_test.c
==============================================================================
--- head/lib/libc/tests/stdlib/tsearch_test.c	Thu Oct 13 18:02:29 2016	(r307226)
+++ head/lib/libc/tests/stdlib/tsearch_test.c	Thu Oct 13 18:25:40 2016	(r307227)
@@ -34,7 +34,7 @@ __FBSDID("$FreeBSD$");
 
 /* Validates the integrity of an AVL tree. */
 static inline unsigned int
-tnode_assert(const node_t *n)
+tnode_assert(const posix_tnode *n)
 {
 	unsigned int height_left, height_right;
 	int balance;
@@ -79,7 +79,7 @@ ATF_TC_BODY(tsearch_test, tc)
 		keys[i] = i;
 
 	/* Apply random operations on a binary tree and check the results. */
-	void *root = NULL;
+	posix_tnode *root = NULL;
 	bool present[NKEYS] = {};
 	for (int i = 0; i < NKEYS * 10; ++i) {
 		int key = nrand48(random_state) % NKEYS;



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201610131825.u9DIPeXH066703>