From adae91bf0400dead60dcfa3476fdbb234db14e18 Mon Sep 17 00:00:00 2001 From: ed Date: Sat, 29 Oct 2016 14:41:22 +0000 Subject: 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. --- lib/libc/stdlib/twalk.c | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-) (limited to 'lib/libc/stdlib/twalk.c') diff --git a/lib/libc/stdlib/twalk.c b/lib/libc/stdlib/twalk.c index 7acee41..4f999b4 100644 --- a/lib/libc/stdlib/twalk.c +++ b/lib/libc/stdlib/twalk.c @@ -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 #include -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 the tree to be walked */ /* 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); -- cgit v1.1