diff options
| author | David Gwynne <dlg@cvs.openbsd.org> | 2017-06-08 03:12:54 +0000 |
|---|---|---|
| committer | David Gwynne <dlg@cvs.openbsd.org> | 2017-06-08 03:12:54 +0000 |
| commit | 934692688a9e5c97e76775e1d57540d731e3dddb (patch) | |
| tree | ab6717794c9d98a23d7d1d929d71129d3133b540 /sys | |
| parent | 5d0bf25976815db76338471682651eb59e9a2ef9 (diff) | |
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.
Diffstat (limited to 'sys')
| -rw-r--r-- | sys/kern/subr_tree.c | 29 | ||||
| -rw-r--r-- | sys/sys/tree.h | 26 |
2 files changed, 53 insertions, 2 deletions
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 <provos@citi.umich.edu> @@ -593,6 +593,33 @@ _rb_parent(const struct rb_type *t, void *node) } 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) { struct rb_entry *rbe = rb_n2e(t, node); 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 <provos@citi.umich.edu> * 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) |