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; _______________________________________________ svn-src-head@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
