Differential D11053 Diff 30746 head/lib/libc/stdlib/tsearch.3

Changeset View

Standalone View

head/lib/libc/stdlib/tsearch.3

	Show All 21 Lines
	.\" OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,			.\" OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
	.\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR			.\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
	.\" OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF			.\" OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
	.\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.			.\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	.\"			.\"
	.\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp			.\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp
	.\" $FreeBSD$			.\" $FreeBSD$
	.\"			.\"
	.Dd October 9, 2016			.Dd June 4, 2017
	.Dt TSEARCH 3			.Dt TSEARCH 3
	.Os			.Os
	.Sh NAME			.Sh NAME
	.Nm tsearch , tfind , tdelete , twalk			.Nm tsearch , tfind , tdelete , twalk
	.Nd manipulate binary search trees			.Nd manipulate binary search trees
	.Sh SYNOPSIS			.Sh SYNOPSIS
	.In search.h			.In search.h
	.Ft void *			.Ft void *
	▲ Show 20 Lines • Show All 86 Lines • ▼ Show 20 Lines
	functions			functions
	return NULL if			return NULL if
	.Fa rootp			.Fa rootp
	is NULL or the datum cannot be found.			is NULL or the datum cannot be found.
	.Pp			.Pp
	The			The
	.Fn twalk			.Fn twalk
	function returns no value.			function returns no value.
				.Sh EXAMPLES
				This example uses
				sevanUnsubmitted Done Inline Actions "each one of them against each other"? sevan: "each one of them against each other"?
				.Fn tsearch
				sevanUnsubmitted Done Inline Actions "by adding them to the tree and attempting"? sevan: "by adding them to the tree and attempting"?
				to search for four strings in
				bruefferUnsubmitted Done Inline Actions .Fn tfind (see the .Fn twalk just above the EXAMPLES section); same for tdelete. brueffer: .Fn tfind (see the .Fn twalk just above the EXAMPLES section); same for tdelete.
				sevanUnsubmitted Done Inline Actions s/uses/using? sevan: s/uses/using?
				.Dv root .
				bruefferUnsubmitted Done Inline Actions Please start a new sentence on a new line; ".Fn twalk" (same as above). brueffer: Please start a new sentence on a new line; ".Fn twalk" (same as above).
				Because the strings are not already present, they are added.
				.Fn tsearch
				is called twice on the fourth string to demonstrate that a string is not added when it is already present.
				sevanUnsubmitted Done Inline Actions I find the paragraph to be quite difficult to parse in one pass. Just a suggestion but It may be better to break it up rather than using more than one conjunction to say it as one. "The following example takes in four strings and compares each one of them against each other before adding them to the tree. The fourth string is added a second time. tfind is used to verify that a duplicate is not added and tdelete is used to remove it" question, is the it on the end of the sentence referring to a duplicate or any entry that's been added? sevan: I find the paragraph to be quite difficult to parse in one pass. Just a suggestion but It may…
				bruefferUnsubmitted Done Inline Actions I agree with sevan, I've had problems understanding that paragraph (refrained from commenting since he already had :-). The suggested re-wording sounds like an improvement. The rest looks good! brueffer: I agree with sevan, I've had problems understanding that paragraph (refrained from commenting…
				wblockUnsubmitted Done Inline Actions Hm. The example code is... not overly clear. But maybe this describes it? This example uses .Fn tsearch to search for four strings in .Dv root . Because the strings are not already present, they are added. .Fn tsearch is called twice on the fourth string to demonstrate that a string is not added when it is already present. .Fn tfind is used to find the single instance of the fourth string, and .Fn tdelete removes it. Finally, .Fn twalk is used to return and display the resulting binary search tree. wblock: Hm. The example code is... not overly clear. But maybe this describes it? ```This example…
				.Fn tfind
				is used to find the single instance of the fourth string, and
				.Fn tdelete
				removes it.
				Finally,
				.Fn twalk
				is used to return and display the resulting binary search tree.
				.Bd -literal
				#include <stdio.h>
				#include <search.h>
				#include <string.h>

				int
				comp(const void a, const void b)
				{

				return strcmp(a, b);
				}

				void
				printwalk(const posix_tnode * node, VISIT v, int __unused0)
				{

				if (v == postorder \|\| v == leaf) {
				printf("node: %s\n\\", (char *)node);
				}
				}

				int
				main(void)
				{
				posix_tnode *root = NULL;

				char one[] = "blah1";
				char two[] = "blah-2";
				char three[] = "blah-3";
				char four[] = "blah-4";

				tsearch(one, &root, comp);
				tsearch(two, &root, comp);
				tsearch(three, &root, comp);
				tsearch(four, &root, comp);
				tsearch(four, &root, comp);
				printf("four: %s\n", (char *)tfind(four, &root, comp));
				tdelete(four, &root, comp);

				twalk(root, printwalk);
				return 0;
				}
				.Ed
	.Sh SEE ALSO			.Sh SEE ALSO
	.Xr bsearch 3 ,			.Xr bsearch 3 ,
	.Xr hsearch 3 ,			.Xr hsearch 3 ,
	.Xr lsearch 3			.Xr lsearch 3
	.Sh STANDARDS			.Sh STANDARDS
	These functions conform to			These functions conform to
	.St -p1003.1-2008 .			.St -p1003.1-2008 .
	.Pp			.Pp
	Show All 11 Lines