From f13ac28347e28f5b6678e59b4e39da7d8daf3ad9 Mon Sep 17 00:00:00 2001 From: dlg Date: Thu, 8 Jun 2017 03:12:53 +0000 Subject: [PATCH] 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. --- share/man/man9/RBT_INIT.9 | 40 +++++++++++++++++++++++++++++++++++++-- sys/kern/subr_tree.c | 29 +++++++++++++++++++++++++++- sys/sys/tree.h | 26 ++++++++++++++++++++++++- 3 files changed, 91 insertions(+), 4 deletions(-) diff --git a/share/man/man9/RBT_INIT.9 b/share/man/man9/RBT_INIT.9 index 9bc87091882..9a59c6cd7ea 100644 --- a/share/man/man9/RBT_INIT.9 +++ b/share/man/man9/RBT_INIT.9 @@ -1,4 +1,4 @@ -.\" $OpenBSD: RBT_INIT.9,v 1.5 2016/09/15 06:07:22 dlg Exp $ +.\" $OpenBSD: RBT_INIT.9,v 1.6 2017/06/08 03:12:53 dlg Exp $ .\" .\" * Copyright 2002 Niels Provos .\" * All rights reserved. @@ -38,7 +38,7 @@ .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. .\" -.Dd $Mdocdate: September 15 2016 $ +.Dd $Mdocdate: June 8 2017 $ .Dt RBT_INIT 9 .Os .Sh NAME @@ -61,6 +61,9 @@ .Nm RBT_LEFT , .Nm RBT_RIGHT , .Nm RBT_PARENT , +.Nm RBT_SET_LEFT , +.Nm RBT_SET_RIGHT , +.Nm RBT_SET_PARENT , .Nm RBT_FOREACH , .Nm RBT_FOREACH_SAFE , .Nm RBT_FOREACH_REVERSE , @@ -114,6 +117,12 @@ .Fn RBT_RIGHT "NAME" "struct TYPE *elm" .Ft struct TYPE * .Fn RBT_PARENT "NAME" "struct TYPE *elm" +.Ft void +.Fn RBT_SET_LEFT "NAME" "struct TYPE *elm" "struct TYPE *left" +.Ft void +.Fn RBT_SET_RIGHT "NAME" "struct TYPE *elm" "struct TYPE *right" +.Ft void +.Fn RBT_SET_PARENT "NAME" "struct TYPE *elm" "struct TYPE *parent" .Fo RBT_FOREACH .Fa "VARNAME" .Fa "NAME" @@ -335,6 +344,30 @@ returns a pointer to the parent element of .Fa elm in a red-black tree of type .Fa NAME . +.Pp +.Fn RBT_SET_LEFT +sets the left child pointer of element +.Fa elm +to +.Fa left +in a red-black tree of type +.Fa NAME . +.Pp +.Fn RBT_SET_RIGHT +sets the right child pointer of element +.Fa elm +to +.Fa right +in a red-black tree of type +.Fa NAME . +.Pp +.Fn RBT_SET_PARENT +sets the parent pointer of element +.Fa elm +to +.Fa parent +in a red-black tree of type +.Fa NAME . .Ss Red-Black Tree Iterators The .Fn RBT_FOREACH @@ -418,6 +451,9 @@ value. .Fn RBT_LEFT , .Fn RBT_RIGHT , .Fn RBT_PARENT , +.Fn RBT_SET_LEFT , +.Fn RBT_SET_RIGHT , +.Fn RBT_SET_PARENT , .Fn RBT_FOREACH , .Fn RBT_FOREACH_REVERSE , .Fn RBT_FOREACH_SAFE , diff --git a/sys/kern/subr_tree.c b/sys/kern/subr_tree.c index 00f54f4d9fe..0f8d9eb5cc2 100644 --- a/sys/kern/subr_tree.c +++ b/sys/kern/subr_tree.c @@ -1,4 +1,4 @@ -/* $OpenBSD: subr_tree.c,v 1.6 2016/09/20 01:11:27 dlg Exp $ */ +/* $OpenBSD: subr_tree.c,v 1.7 2017/06/08 03:12:53 dlg Exp $ */ /* * Copyright 2002 Niels Provos @@ -592,6 +592,33 @@ _rb_parent(const struct rb_type *t, void *node) return (rbe == NULL ? NULL : rb_e2n(t, rbe)); } +void +_rb_set_left(const struct rb_type *t, void *node, void *left) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left); + + RBE_LEFT(rbe) = rbl; +} + +void +_rb_set_right(const struct rb_type *t, void *node, void *right) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right); + + RBE_RIGHT(rbe) = rbr; +} + +void +_rb_set_parent(const struct rb_type *t, void *node, void *parent) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent); + + RBE_PARENT(rbe) = rbp; +} + void _rb_poison(const struct rb_type *t, void *node, unsigned long poison) { diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 320060546b7..02c83e0365f 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -1,4 +1,4 @@ -/* $OpenBSD: tree.h,v 1.25 2016/09/26 08:08:51 kettenis Exp $ */ +/* $OpenBSD: tree.h,v 1.26 2017/06/08 03:12:53 dlg Exp $ */ /* * Copyright 2002 Niels Provos * All rights reserved. @@ -814,6 +814,9 @@ void *_rb_prev(const struct rb_type *, void *); void *_rb_left(const struct rb_type *, void *); void *_rb_right(const struct rb_type *, void *); void *_rb_parent(const struct rb_type *, void *); +void _rb_set_left(const struct rb_type *, void *, void *); +void _rb_set_right(const struct rb_type *, void *, void *); +void _rb_set_parent(const struct rb_type *, void *, void *); void *_rb_color(const struct rb_type *, void *); void _rb_poison(const struct rb_type *, void *, unsigned long); int _rb_check(const struct rb_type *, void *, unsigned long); @@ -908,6 +911,24 @@ _name##_RBT_PARENT(struct _type *elm) \ } \ \ __unused static inline void \ +_name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \ +{ \ + return _rb_set_left(_name##_RBT_TYPE, elm, left); \ +} \ + \ +__unused static inline void \ +_name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \ +{ \ + return _rb_set_right(_name##_RBT_TYPE, elm, right); \ +} \ + \ +__unused static inline void \ +_name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \ +{ \ + return _rb_set_parent(_name##_RBT_TYPE, elm, parent); \ +} \ + \ +__unused static inline void \ _name##_RBT_POISON(struct _type *elm, unsigned long poison) \ { \ return _rb_poison(_name##_RBT_TYPE, elm, poison); \ @@ -959,6 +980,9 @@ RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) #define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) #define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) #define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) +#define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l) +#define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r) +#define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p) #define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) #define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) -- 2.20.1