tdestroy: don't visit one-child node twice
ClosedPublic
Actions

Authored by dougm on Jan 14 2026, 6:06 AM.

Tags

None

Referenced Files

	Unknown Object (File)
	Tue, Feb 10, 4:24 AM

	Unknown Object (File)
	Fri, Feb 6, 4:39 PM

	Unknown Object (File)
	Thu, Jan 29, 8:35 PM

	Unknown Object (File)
	Thu, Jan 29, 2:41 AM

	Unknown Object (File)
	Wed, Jan 28, 3:25 PM

	Unknown Object (File)
	Tue, Jan 27, 8:33 PM

	Unknown Object (File)
	Mon, Jan 26, 1:09 PM

	Unknown Object (File)
	Mon, Jan 19, 10:07 PM

View All 19 Files

Subscribers

imp

Details

Reviewers

alc
kib

Commits

rG988555e329d0: tdestroy: don't visit one-child node twice

Summary

Change tdestroy() to immediately free a node with no right child as soon as it is encountered. Currently, such nodes are visited twice before deletion.

Diff Detail

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

dougm requested review of this revision.Jan 14 2026, 6:06 AM

dougm created this revision.

Remove a redundant NULL check.

Did you tested this with lib/libc/tests/stdlib/tsearch_test.c?
If it works, I am fine with it.

$ kyua test -k /usr/tests/Kyuafile lib/libc/stdlib/tsearch_test
lib/libc/stdlib/tsearch_test:tdestroy_test -> passed [0.001s]
lib/libc/stdlib/tsearch_test:tsearch_test -> passed [0.030s]

kib accepted this revision.Thu, Jan 15, 4:22 AM

This revision is now accepted and ready to land.Thu, Jan 15, 4:22 AM

Closed by commit rG988555e329d0: tdestroy: don't visit one-child node twice (authored by dougm). · Explain WhyFri, Jan 16, 10:28 PM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rG988555e329d0: tdestroy: don't visit one-child node twice.

Herald added a subscriber: imp. · View Herald TranscriptFri, Jan 16, 10:28 PM