summaryrefslogtreecommitdiff
path: root/lib/openbsd-tree.c
AgeCommit message (Collapse)Author
2023-02-09*: manual SPDX License ID conversionsDavid Lamparter
The files converted in this commit either had some random misspelling or formatting weirdness that made them escape automated replacement, or have a particularly "weird" licensing setup (e.g. dual-licensed.) This also marks a bunch of "public domain" files as SPDX License "NONE". Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
2020-02-09*: Remove parenthesis on return for constantsDonatas Abraitis
Signed-off-by: Donatas Abraitis <donatas.abraitis@gmail.com>
2019-05-13lib: Add const to openbsd-tree functionsStephen Worley
A few of the functions in openbsd's RB tree implementation needed to have const in their parameters. Signed-off-by: Stephen Worley <sworley@cumulusnetworks.com>
2018-09-28lib: RB-tree copy-paste error (Coverity 1446184)F. Aragon
Overview: Coverity points a copy-paste error in the Red-Black tree implementation. The RB tree code is based on the OpenBSD implementation, so at first glance, it is a strong point for thinking twice before touching anything. Details: The code is an augmented RB tree implementation [1], which adds to RB trees the possibility of using a callback on every node update for updating per-node associated metainformation. The bug is clear once checking other places where the callback is called. Impact: - FRR: no impact, because the "augmented" capability is not being used. - OpenBSD [2]: it seems there is no impact, at least in the 'src' repository. Additional observations: - If the "augmented" capability is not used, the code could run faster (at every operation on a node the callback is checked for not being NULL). May be branch prediction could be enough for those extra operations being negligible on most processors in use. [1] http://kaba.hilvi.org/pastel-1.3.0/pastel/sys/redblacktree.htm [2] GH mirror: https://github.com/openbsd/src/blob/master/sys/kern/subr_tree.c Signed-off-by: F. Aragon <paco@voltanet.io>
2018-09-08*: fix config.h/zebra.h include orderDavid Lamparter
config.h (or, transitively, zebra.h) must be the first include file listed for autoconf things like _GNU_SOURCE and _POSIX_C_SOURCE to work correctly. Signed-off-by: David Lamparter <equinox@diac24.net>
2018-03-06*: conform with COMMUNITY.md formatting rules, via 'make indent'Lou Berger
Signed-off-by: Lou Berger <lberger@labn.net>
2017-07-24lib: fix corrupted RB treesRenato Westphal
Commit 8f942af90 introduced a bug while silencing a clang warning. Silence the warning in a different way to fix our red-black tree implementation. Fixes #841. Signed-off-by: Renato Westphal <renato@opensourcerouting.org>
2017-07-24lib: revert reindent of files imported from OpenBSDRenato Westphal
We should preserve the original indentation to make it easier to keep these files in sync with the upstream. Signed-off-by: Renato Westphal <renato@opensourcerouting.org>
2017-07-17*: reindentreindent-master-afterwhitespace / reindent
indent.py `git ls-files | pcregrep '\.[ch]$' | pcregrep -v '^(ldpd|babeld|nhrpd)/'` Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
2017-06-19lib: rename rb_tree to fix NetBSD compilationRafael Zalamena
Change rb_tree struct name to rbt_tree to avoid conflicts with NetBSD.
2017-06-16lib: fix a possible NULL deferenceRafael Zalamena
Silences a warning generated by clang.
2017-06-16lib: improve the RB implementationRafael Zalamena
Switch the RB tree implementation completely to the new dlg@'s version that uses pre-declared functions instead of macros for tree functions. Original e-mail/diff: https://marc.info/?l=openbsd-tech&m=147087487111068&w=2 Pros: * Reduces the amount of code that the usage of those macros generate * Allows the compiler to do a better compile-time check job * Might have better i-cache utilization since the tree code is shared Con: * dlg@ benchmarks shows it has 'very slightly slower' insertions * imported RB_* code must adapt the following calls: RB_INIT(), RB_GENERATE(), RB_ROOT(), RB_EMPTY(), make compare functions use 'const' (if not already) and maybe others.