Page MenuHomeFreeBSD

Add RB_NUMNODES in tree(3)
AbandonedPublic

Authored by bapt on Aug 12 2015, 7:08 PM.
Tags
None
Referenced Files
Unknown Object (File)
Dec 28 2023, 3:03 PM
Unknown Object (File)
Dec 28 2023, 3:02 PM
Unknown Object (File)
Dec 20 2023, 12:32 AM
Unknown Object (File)
Dec 9 2023, 12:13 PM
Unknown Object (File)
Nov 23 2023, 3:56 PM
Unknown Object (File)
Nov 23 2023, 11:43 AM
Unknown Object (File)
Nov 19 2023, 1:02 PM
Unknown Object (File)
Nov 19 2023, 3:36 AM
Subscribers

Details

Reviewers
davide
imp
Group Reviewers
manpages

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 74
Build 74: arc lint + arc unit

Event Timeline

bapt retitled this revision from to Add RB_NUMNODES in tree(3).
bapt updated this object.
bapt edited the test plan for this revision. (Show Details)
bapt added a reviewer: davide.
imp added a reviewer: imp.

Please consider renaming to RB_COUNT(), and please do not change the memory layout or semantics of basic containers which are already used in-kernel (discussed on src-committers@)

bapt edited edge metadata.

Rename RB_COUNT

wblock added inline comments.
share/man/man3/tree.3
566

s/traverse/traverses/

567

Reads a little better with a comma here:

.Ar head ,
570

s/nodes/node/

bapt edited edge metadata.

Update following @wblock comments on this review, and some of the bde's arguments

bapt edited edge metadata.

Pet mode of bde@ arguments

I dislike macros like these.

If I would write code against this header, I would expect that this macro has a time complexity that is as efficient as possible. A red-black tree could be augmented to keep track of the count and have an RB_COUNT() that runs in O(1) time. This macro runs in linear time.

For the same reason, I completely dislike SLIST_REMOVE(). We use it all over the place, but it actually has an O(n) running time. Code that uses SLIST_REMOVE() should just be changed to use a LIST instead of an SLIST. SLIST_REMOVE() shouldn't have been added in the first place.

Additional remark: if such a macro is added, it would make more sense to return the count -- not have it passed in by reference.

In D3371#68718, @ed wrote:

I dislike macros like these.

If I would write code against this header, I would expect that this macro has a time complexity that is as efficient as possible. A red-black tree could be augmented to keep track of the count and have an RB_COUNT() that runs in O(1) time. This macro runs in linear time.

I was trying to avoid doing that because it means I would have way more code to do :)

But yes in theory this is better. Actually the initial RB_NUMNODES I wrote was just to minimize conversion from Illumos libavl which has a avl_numnodes (but O(1)) I felt changing the whole tree.h was wrong)

For the same reason, I completely dislike SLIST_REMOVE(). We use it all over the place, but it actually has an O(n) running time. Code that uses SLIST_REMOVE() should just be changed to use a LIST instead of an SLIST. SLIST_REMOVE() shouldn't have been added in the first place.

share/man/man3/tree.3
570

Still needs to be changed to singular "node".