aboutsummaryrefslogtreecommitdiff
path: root/sys/sys/tree.h
Commit message (Collapse)AuthorAgeFilesLines
* sys: clean up empty lines in .c and .h filesMateusz Guzik2020-09-011-2/+1
| | | | Notes: svn path=/head/; revision=365223
* Rank balanced (RB) trees are a class of balanced trees that includesDoug Moore2020-07-231-138/+133
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=363450
* Eliminate the color field from the RB element struct. Identify theDoug Moore2020-06-251-102/+151
| | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=362617
* Define RB_SET_PARENT to do all assignments to rb parentDoug Moore2020-06-231-30/+28
| | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=362552
* In concluding RB_REMOVE_COLOR, in the case when the sibling of theDoug Moore2020-06-201-15/+11
| | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=362450
* Linuxkpi uses the rb-tree structures without using their interfaces,Doug Moore2020-06-131-148/+137
| | | | | | | | | | | | 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 Notes: svn path=/head/; revision=362139
* Fixup r361997 by balancing parens. Duh.Doug Moore2020-06-101-1/+1
| | | | Notes: svn path=/head/; revision=362000
* Restore an RB_COLOR macro, for the benefit of a bit of DIAGNOSTIC codeDoug Moore2020-06-101-0/+6
| | | | | | | | | | | that depends on it. Reported by: rpokala, mjguzik Reviewed by: markj Differential Revision: https://reviews.freebsd.org/D25204 Notes: svn path=/head/; revision=361997
* To reduce the size of an rb_node, drop the color field. Set the leastDoug Moore2020-06-091-138/+143
| | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=361984
* Remove from RB_REMOVE_COLOR some null checks where the pointer checkedDoug Moore2020-06-021-26/+20
| | | | | | | | | | | | 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 Notes: svn path=/head/; revision=361727
* RB_REMOVE invokes RB_REMOVE_COLOR either when child is red or child isDoug Moore2020-05-301-72/+65
| | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=361640
* For the case when RB_REMOVE requires a nontrivial search to find theDoug Moore2020-05-211-28/+24
| | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=361324
* Correct the use of RB_AUGMENT in the RB_TREE macros so that is invokedDoug Moore2020-01-271-50/+38
| | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=357173
* Add RB_REINSERT(3), a low overhead alternative to removing a nodeEdward Tomasz Napierala2019-09-281-2/+24
| | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=352837
* Mark inline functions with __unused; prevents compiler warningEdward Tomasz Napierala2019-05-081-3/+3
| | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=347360
* sys/sys: further adoption of SPDX licensing ID tags.Pedro F. Giffuni2017-11-271-0/+2
| | | | | | | | | | | | | | | 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. Notes: svn path=/head/; revision=326256
* Provide individual prototype and generate macros for the red-black tree.Konstantin Belousov2015-01-241-25/+61
| | | | | | | | | | This helps to reduce code size in statically linked applications. Submitted by: Sebastian Huber <sebastian.huber@embedded-brains.de> MFC after: 2 weeks Notes: svn path=/head/; revision=277642
* In sys/tree.h:Bruce M Simpson2009-03-011-1/+16
| | | | | | | | | | | | | | | | | | | * 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. Notes: svn path=/head/; revision=189204
* Add macro RB_FOREACH_SAFE(), which accepts an additional argumentBruce M Simpson2008-12-241-0/+5
| | | | | | | | specifying a temporary tree node pointer. It may be used in a similar way to the *_SAFE() macros in <sys/queue.h>. Notes: svn path=/head/; revision=186479
* Implement RB_PREV() AND RB_FOREACH_REVERSE().Jason Evans2007-12-281-0/+29
| | | | Notes: svn path=/head/; revision=174955
* Simplify/optimize RB_NFIND().Jason Evans2007-06-151-19/+11
| | | | | | | Submitted by: Andriy Gapon <avg@icyb.net.ua> Notes: svn path=/head/; revision=170779
* Add the RB_PROTOTYPE_STATIC and RB_GENERATE_STATIC macros.Jason Evans2006-01-191-18/+28
| | | | | | | Approved by: markm (mentor) Notes: svn path=/head/; revision=154548
* Add the RB_NFIND() macro, which is useful for red-black tree searchesJason Evans2006-01-111-0/+31
| | | | | | | | | | for which there may not be an exact match. Reviewed by: glebius, julian Approved by: markm (mentor) Notes: svn path=/head/; revision=154227
* Make the default RB_AUGMENT() produce a 'do {} while (0)' insteadHartmut Brandt2005-06-101-1/+1
| | | | | | | | of nothing. This prevents the compiler from complaining about empty if statements when compiled with higher WARN levels. Notes: svn path=/head/; revision=147245
* Add FreeBSD tagWarner Losh2005-01-071-1/+3
| | | | Notes: svn path=/head/; revision=139824
* Synch with NetBSD: avoid "unused parameter" warning.Dag-Erling Smørgrav2004-03-291-5/+5
| | | | Notes: svn path=/vendor/NetBSD/dist/; revision=127563
* Import the original directly from NetBSD instead of via OpenBSD.Dag-Erling Smørgrav2004-03-251-22/+26
| | | | Notes: svn path=/vendor/NetBSD/dist/; revision=127403
* Sync with OpenBSD (two-year old bug fix)Dag-Erling Smørgrav2004-03-191-3/+5
| | | | Notes: svn path=/vendor/NetBSD/dist/; revision=127208
* Import OpenBSD's <sys/tree.h>, needed by OpenSSH.Dag-Erling Smørgrav2002-06-231-0/+675
Obtained from: OpenBSD Notes: svn path=/vendor/NetBSD/dist/; revision=98679
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-16 09:15:32 +0000