MFC r307227 and r307343:

  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.

1 files changed, 14 insertions, 9 deletions

diff --git a/include/search.h b/include/search.h
index 4c1f534..068446f 100644
--- a/include/search.h
+++ b/include/search.h
@@ -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 *, size_t *, size_t,
 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 *);