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, 22 insertions, 7 deletions

diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3
index 2205f7e..493eff2 100644
--- a/lib/libc/stdlib/tsearch.3
+++ b/lib/libc/stdlib/tsearch.3
@@ -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 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 distinguishing between nodes and keys easier.