Parent Directory
| 
Revision Log
| Links to HEAD: | (view) (download) (annotate) |
| Sticky Revision: |
sys: clean up empty lines in .c and .h files
Rank balanced (RB) trees are a class of balanced trees that includes AVL trees, red-black trees, and others. Weak AVL (wavl) trees are a recently discovered member of that class. This change replaces red-black rebalancing with weak AVL rebalancing in the RB tree macros. Wavl trees sit between AVL and red-black trees in terms of how strictly balance is enforced. They have the stricter balance of AVL trees as the tree is built - a wavl tree is an AVL tree until the first deletion. Once removals start, wavl trees are lazier about rebalancing than AVL trees, so that removals can be fast, but the balance of the tree can decay to that of a red-black tree. Subsequent insertions can push balance back toward the stricter AVL conditions. Removing a node from a wavl tree never requires more than two rotations, which is better than either red-black or AVL trees. Inserting a node into a wavl tree never requires more than two rotations, which matches red-black and AVL trees. The only disadvantage of wavl trees to red-black trees is that more insertions are likely to adjust the tree a bit. That's the cost of keeping the tree more balanced. Testing has shown that for the cases where red-black trees do worst, wavl trees better balance leads to faster lookups, so that if lookups outnumber insertions by a nontrivial amount, lookup time saved exceeds the extra cost of balancing. Reviewed by: alc, gbe, markj Tested by: pho Discussed with: emaste Differential Revision: https://reviews.freebsd.org/D25480
Eliminate the color field from the RB element struct. Identify the color of a node (or, really, the color of the link from the parent to the node) by using one of the last two bits of the parent pointer in that parent node. Adjust rebalancing methods to account for where colors are stored, and the fact that null children have a color too. Adjust RB_PARENT and RB_SET_PARENT to account for this change. Reviewed by: markj Tested by: pho, hselasky Differential Revision: https://reviews.freebsd.org/D25418
Define RB_SET_PARENT to do all assignments to rb parent pointers. Define RB_SWAP_CHILD to replace the child of a parent with its twin, and use it in 4 places. Use RB_SET in rb_link_node to remove the only linuxkpi reference to color, and then drop color- and parent-related definitions that are defined and used only in rbtree.h. This is intended to be entirely cosmetic, with no impact on program behavior, and leave RB_PARENT and RB_SET_PARENT as the only ways to read and write rb parent pointers. Reviewed by: markj, kib Tested by: pho Differential Revision: https://reviews.freebsd.org/D25264
In concluding RB_REMOVE_COLOR, in the case when the sibling of the root of the too-short tree is black and at least one of the children of that sibling is red, either one or two rotations finish the rebalancing. In the case when both of the children are red, the current implementation uses two rotations where only one is necessary. This change removes that extra rotation, and in that case also removes a needless black-to-red-to-black recoloring. Reviewed by: markj Differential Revision: https://reviews.freebsd.org/D25335
Linuxkpi uses the rb-tree structures without using their interfaces, making them break when the representation changes. Revert changes that eliminated the color field from rb-trees, leaving everything as it was before. Reviewed by: markj Differential Revision: https://reviews.freebsd.org/D25250
Fixup r361997 by balancing parens. Duh.
Restore an RB_COLOR macro, for the benefit of a bit of DIAGNOSTIC code that depends on it. Reported by: rpokala, mjguzik Reviewed by: markj Differential Revision: https://reviews.freebsd.org/D25204
To reduce the size of an rb_node, drop the color field. Set the least significant bit in the pointer to the node from its parent to indicate that the node is red. Have the tree rotation macros leave the old-parent/new-child node red and the new-parent/old-child node black. This change makes RB_LEFT and RB_RIGHT no longer assignable, and RB_COLOR no longer defined. Any code that modifies the tree or examines a node color would have to be modified after this change. Reviewed by: markj Tested by: pho Differential Revision: https://reviews.freebsd.org/D25105
Remove from RB_REMOVE_COLOR some null checks where the pointer checked is provably never null. Restructure the surrounding code just enough to make the non-nullness obvious. Reviewed by: markj Tested by: pho Differential Revision: https://reviews.freebsd.org/D25089
RB_REMOVE invokes RB_REMOVE_COLOR either when child is red or child is null. In the first case, RB_REMOVE_COLOR just changes the child to black and returns. With this change, RB_REMOVE handles that case, and drops the child argument to RB_REMOVE_COLOR, since that value is always null. RB_REMOVE_COLOR is changed to remove a couple of unneeded tests, and to eliminate some deep indentation. RB_ISRED is defined to combine a null check with a test for redness, to replace that combination in several places. Reviewed by: markj Tested by: pho Differential Revision: https://reviews.freebsd.org/D25032
For the case when RB_REMOVE requires a nontrivial search to find the node to replace the one being removed, restructure to first remove the replacement node and correct the parent pointers around it, and then let the all-cases code at the end deal with the parent of the deleted node, making it point to the replacement node. This removes one or two conditional branches. Reviewed by: markj Tested by: pho Differential Revision: https://reviews.freebsd.org/D24845
Correct the use of RB_AUGMENT in the RB_TREE macros so that is invoked at the root of every subtree that changes in an insert or delete, and only once, and ordered from the bottom of the tree to the top. For intel_gas.c, the only user of RB_AUGMENT I can find, change the augmenting routine so that it does not climb from entry to tree root on every call, and remove a 'tree correcting' function that can be supplanted by proper tree augmentation. Reviewed by: kib Tested by: pho Differential Revision: https://reviews.freebsd.org/D23189
Add RB_REINSERT(3), a low overhead alternative to removing a node and reinserting it back with an updated key. This is one of dependencies for the upcoming stats(3) code. Reviewed by: cem Obtained from: Netflix MFC after: 2 weeks Sponsored by: Klara Inc, Netflix Differential Revision: https://reviews.freebsd.org/D21786
Mark inline functions with __unused; prevents compiler warning when they end up being unused. Reviewed by: kib Obtained from: OpenBSD MFC after: 2 weeks Sponsored by: Klara Inc. Differential Revision: https://reviews.freebsd.org/D20185
sys/sys: further adoption of SPDX licensing ID tags. Mainly focus on files that use BSD 2-Clause license, however the tool I was using misidentified many licenses so this was mostly a manual - error prone - task. The Software Package Data Exchange (SPDX) group provides a specification to make it easier for automated tools to detect and summarize well known opensource licenses. We are gradually adopting the specification, noting that the tags are considered only advisory and do not, in any way, superceed or replace the license texts.
Provide individual prototype and generate macros for the red-black tree. This helps to reduce code size in statically linked applications. Submitted by: Sebastian Huber <sebastian.huber@embedded-brains.de> MFC after: 2 weeks
In sys/tree.h: * Add RB_FOREACH_FROM() which continues traversal *at* the y-node provided. There is no pre-increment. * Nuke RB_FOREACH_SAFE as it was buggy; it would omit the final node. * Replace RB_FOREACH_SAFE() with a working implementation derived from RB_FOREACH_FROM(). The key observation is that we now only check the loop-control variable, but still cache the next member pointer. * Add RB_FOREACH_REVERSE_FROM() which continues backwards traversal *at* the y-node provided. There is no pre-increment. Typically this is used to back out of allocations made whilst walking an RB-tree. * Add RB_FOREACH_REVERSE_SAFE() which performs insertion and deletion safe backwards traversal.
Add macro RB_FOREACH_SAFE(), which accepts an additional argument specifying a temporary tree node pointer. It may be used in a similar way to the *_SAFE() macros in <sys/queue.h>.
Implement RB_PREV() AND RB_FOREACH_REVERSE().
Simplify/optimize RB_NFIND(). Submitted by: Andriy Gapon <avg@icyb.net.ua>
Add the RB_PROTOTYPE_STATIC and RB_GENERATE_STATIC macros. Approved by: markm (mentor)
Add the RB_NFIND() macro, which is useful for red-black tree searches for which there may not be an exact match. Reviewed by: glebius, julian Approved by: markm (mentor)
Make the default RB_AUGMENT() produce a 'do {} while (0)' instead
of nothing. This prevents the compiler from complaining about empty
if statements when compiled with higher WARN levels.
Add FreeBSD tag
This commit was generated by cvs2svn to compensate for changes in r127563, which included commits to RCS files with non-trunk default branches.
Synch with NetBSD: avoid "unused parameter" warning.
Import the original directly from NetBSD instead of via OpenBSD.
Sync with OpenBSD (two-year old bug fix)
Import OpenBSD's <sys/tree.h>, needed by OpenSSH. Obtained from: OpenBSD
This form allows you to request diffs between any two revisions of this file. For each of the two "sides" of the diff, enter a numeric revision.
| ViewVC Help | |
| Powered by ViewVC 1.1.27 |