diff options
author | ed <ed@FreeBSD.org> | 2016-10-29 14:41:22 +0000 |
---|---|---|
committer | ed <ed@FreeBSD.org> | 2016-10-29 14:41:22 +0000 |
commit | adae91bf0400dead60dcfa3476fdbb234db14e18 (patch) | |
tree | 96359a06310ef1f91c3a76c17d1cd738278f0e30 /include | |
parent | 9e5cbc784b00f68c9ca71fdabd4b7deacfc6b34e (diff) | |
download | FreeBSD-src-adae91bf0400dead60dcfa3476fdbb234db14e18.zip FreeBSD-src-adae91bf0400dead60dcfa3476fdbb234db14e18.tar.gz |
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.
Diffstat (limited to 'include')
-rw-r--r-- | include/search.h | 23 |
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 *); |