![[BACK]](/icons/back.gif){kind=icon}
Up to [local] / src / sys / kern
Request diff between arbitrary revisions
Default branch: MAIN
Revision 1.10 / (download) - annotate - [select for diffs], Tue Oct 9 08:28:43 2018 UTC (5 years, 8 months ago) by dlg
Branch: MAIN
CVS Tags: OPENBSD_7_5_BASE,
OPENBSD_7_5,
OPENBSD_7_4_BASE,
OPENBSD_7_4,
OPENBSD_7_3_BASE,
OPENBSD_7_3,
OPENBSD_7_2_BASE,
OPENBSD_7_2,
OPENBSD_7_1_BASE,
OPENBSD_7_1,
OPENBSD_7_0_BASE,
OPENBSD_7_0,
OPENBSD_6_9_BASE,
OPENBSD_6_9,
OPENBSD_6_8_BASE,
OPENBSD_6_8,
OPENBSD_6_7_BASE,
OPENBSD_6_7,
OPENBSD_6_6_BASE,
OPENBSD_6_6,
OPENBSD_6_5_BASE,
OPENBSD_6_5,
OPENBSD_6_4_BASE,
OPENBSD_6_4,
HEAD
Changes since 1.9: +2 -2 lines
Diff to previous 1.9 (colored)
Fix a "copy-and-paste" error that Coverity picked up in the augment code This brings it back in line with the macros. via Paco A. and the FRRouting project. ok deraadt@ visa@ guenther@ tb@
Revision 1.9 / (download) - annotate - [select for diffs], Thu Jun 8 03:30:52 2017 UTC (7 years ago) by dlg
Branch: MAIN
CVS Tags: OPENBSD_6_3_BASE,
OPENBSD_6_3,
OPENBSD_6_2_BASE,
OPENBSD_6_2
Changes since 1.8: +3 -3 lines
Diff to previous 1.8 (colored)
make rb_n2e return a struct rb_entry *, not void * maybe this will help prevent misassignment in the future.
Revision 1.8 / (download) - annotate - [select for diffs], Thu Jun 8 03:22:56 2017 UTC (7 years ago) by dlg
Branch: MAIN
Changes since 1.7: +3 -4 lines
Diff to previous 1.7 (colored)
use unsigned long instead of caddr_t to move between nodes and entries. this removes the need for sys/param.h. this code can be built with only sys/tree.h, which in turn only needs sys/_null.h.
Revision 1.7 / (download) - annotate - [select for diffs], Thu Jun 8 03:12:53 2017 UTC (7 years ago) by dlg
Branch: MAIN
Changes since 1.6: +28 -1 lines
Diff to previous 1.6 (colored)
add RBT_SET_LEFT, RBT_SET_RIGHT, and RBT_SET_PARENT this are provided so an RBT and it's topology can be copied without having to reinsert the copied nodes into a new tree. there are two reasons RBT_LEFT/RIGHT/PARENT macros cant be used like RB_LEFT/RIGHT/PARENT for this. firstly, RBT_LEFT and co are functions that return a pointer value, they dont provide access to the pointer itself for use as an lvalue that you can assign to. secondly, RBT entries dont store pointers to other nodes, they point to the RBT_ENTRY structures inside other nodes. this means that RBT_SET_LEFT and co have to get an offset from the node to the RBT_ENTRY and store that.
Revision 1.6 / (download) - annotate - [select for diffs], Tue Sep 20 01:11:27 2016 UTC (7 years, 8 months ago) by dlg
Branch: MAIN
CVS Tags: OPENBSD_6_1_BASE,
OPENBSD_6_1
Changes since 1.5: +7 -7 lines
Diff to previous 1.5 (colored)
whitespace fixes, no functional change
Revision 1.5 / (download) - annotate - [select for diffs], Fri Sep 16 01:05:34 2016 UTC (7 years, 8 months ago) by dlg
Branch: MAIN
Changes since 1.4: +2 -2 lines
Diff to previous 1.4 (colored)
remove a trailing \ i mustnt have cleaned this up properly when i copied the tree.h code from Ilya Kaliman
Revision 1.4 / (download) - annotate - [select for diffs], Thu Sep 15 06:07:22 2016 UTC (7 years, 8 months ago) by dlg
Branch: MAIN
Changes since 1.3: +19 -1 lines
Diff to previous 1.3 (colored)
add RBT_POISON and RBT_CHECK so you can poison the pointers in RBT_ENTRYs this seems like a better way forward than simply removing the poisoning that uvm does.
Revision 1.3 / (download) - annotate - [select for diffs], Thu Sep 15 05:31:24 2016 UTC (7 years, 8 months ago) by dlg
Branch: MAIN
Changes since 1.2: +1 -1 lines
Diff to previous 1.2 (colored)
fix $OpenBSD$ tag
Revision 1.2 / (download) - annotate - [select for diffs], Thu Sep 15 05:21:09 2016 UTC (7 years, 8 months ago) by dlg
Branch: MAIN
Changes since 1.1: +4 -4 lines
Diff to previous 1.1 (colored)
rename the members of rb_entry so they dont keep working with RB macros
Revision 1.1 / (download) - annotate - [select for diffs], Fri Sep 2 11:17:14 2016 UTC (7 years, 9 months ago) by dlg
Branch: MAIN
provide an implementation of red black trees using functions the main goal of this change is to reduce the amount of code that is generated as a result of using the macro implementation (RB_FOO) of red black trees. on amd64 we should get a few dozen kilobytes of code space back, and make red black trees more icache friendly at the same time. the new (RBT_FOO) implementation is modelled on the existing one, but has some minor api variations. generally you can replace RB_ with RBT_ and get most of the way to converting code. internally the red black tree functions all take an rb_type struct that describes the layout of the object wired into a tree (ie, the offset of the RBT_ENTRY inside a node), the comparison function, and an optional augment function. because the functions are supposed to be used for all types, they end up taking void * for the node pointers instead of specific types. the tree is operated on as pointers between the RBT_ENTRY structs instead of the nodes, which gave me some type safety when implementing the code (cos casts to/from void * dont ever fail, and continually calculating the offset of the rb entry is annoying). RBT_ENTRYs are turned into node pointers by prepending the offset stored in the rb_type struct before theyre given to the comparison function or returned to the caller. to provide type safety on top of this, RBT_PROTOTYPE generates static inline function wrappers that only take arguments of the right type, and implicitly provide the rb_type struct argument to the actual RBT functions. therefore the actual functions should never be called directly, all calls should go through the RBT_ wrappers. RBT_GENERATE is responsible for creating the rb_type struct used by these wrappers. notably it also generates a wrapper around the compare function so the user provided one must take the right types instead of void *. in terms of speed, this code is comparable to the macro implementation. eg, insertion is very slightly slower in microbenchmarks, but deletion appears to be significantly faster. this is possibly because of the aggressive inlining ive done inside the delete codepaths. the code is not yet wired into the kernel build. it also needs to be said that there have been several attempts before this to provide functions for at least some parts of the kernels red black trees. that work made this a lot easier. ok deraadt@ jung@ tedu@