Page MenuHomeFreeBSD
Files F151911433

D8205.diff
No OneTemporary
Actions

D8205.diff
View Options

Index: head/include/search.h
===================================================================
--- head/include/search.h
+++ head/include/search.h
@@ -34,16 +34,18 @@
} 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 *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 *);
Index: head/lib/libc/stdlib/tdelete.c
===================================================================
--- head/lib/libc/stdlib/tdelete.c
+++ head/lib/libc/stdlib/tdelete.c
@@ -46,9 +46,9 @@
* 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 @@
#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 @@
} 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 @@
* 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 @@
* 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 @@
}
/* Return the parent of the old entry. */
- *rootp = root;
return (result);
}
Index: head/lib/libc/stdlib/tfind.c
===================================================================
--- head/lib/libc/stdlib/tfind.c
+++ head/lib/libc/stdlib/tfind.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.
@@ -29,11 +27,10 @@
* 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;
Index: head/lib/libc/stdlib/tsearch.3
===================================================================
--- head/lib/libc/stdlib/tsearch.3
+++ head/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 @@
.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.
Index: head/lib/libc/stdlib/tsearch.c
===================================================================
--- head/lib/libc/stdlib/tsearch.c
+++ head/lib/libc/stdlib/tsearch.c
@@ -32,18 +32,17 @@
#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 @@
* balances.
*/
path_init(&path);
- base = &root;
- leaf = &root;
+ leaf = rootp;
while (*leaf != NULL) {
if ((*leaf)->balance != 0) {
/*
@@ -62,9 +60,9 @@
* 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 @@
path_taking_right(&path);
leaf = &(*leaf)->rlink;
} else {
- return (&(*leaf)->key);
+ return (*leaf);
}
}
@@ -94,7 +92,7 @@
* 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 @@
/*
* 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 @@
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 @@
*/
x->llink = y->rlink;
y->rlink = x;
- *base = y;
+ *rootp = y;
x->balance = 0;
y->balance = 0;
@@ -165,12 +163,12 @@
* / \ 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 @@
*/
x->rlink = y->llink;
y->llink = x;
- *base = y;
+ *rootp = y;
x->balance = 0;
y->balance = 0;
@@ -195,6 +193,5 @@
}
/* Return the new entry. */
- *rootp = root;
- return (&result->key);
+ return (result);
}
Index: head/lib/libc/stdlib/twalk.c
===================================================================
--- head/lib/libc/stdlib/twalk.c
+++ head/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 @@
#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 @@
/* 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);
Index: head/lib/libc/tests/stdlib/tsearch_test.c
===================================================================
--- head/lib/libc/tests/stdlib/tsearch_test.c
+++ head/lib/libc/tests/stdlib/tsearch_test.c
@@ -34,7 +34,7 @@
/* 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 @@
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;

File Metadata

Mime Type
text/plain
Expires
Sun, Apr 12, 12:09 PM (5 h, 14 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31347242
Default Alt Text
D8205.diff (10 KB)

Event Timeline