? sys/sys/refcnt_t.h ? sys/sys/rwlock_t.h ? sys/sys/srp_t.h ? sys/sys/task_t.h ? sys/sys/timeout_t.h Index: sys/sys/cdefs.h =================================================================== RCS file: /cvs/src/sys/sys/cdefs.h,v retrieving revision 1.39 diff -u -p -r1.39 cdefs.h --- sys/sys/cdefs.h 18 Apr 2014 11:51:17 -0000 1.39 +++ sys/sys/cdefs.h 5 Oct 2016 10:49:40 -0000 @@ -87,6 +87,15 @@ #endif /* !__GNUC__ */ #endif /* !(__STDC__ || __cplusplus) */ +/* Macros for calculating the offset of a field */ +#ifndef __offsetof +#if __GNUC_PREREQ__(4, 0) +#define __offsetof(s, e) __builtin_offsetof(s, e) +#else +#define __offsetof(s, e) ((size_t)&((s *)0)->e) +#endif +#endif + /* * GCC1 and some versions of GCC2 declare dead (non-returning) and * pure (no side effects) functions using "volatile" and "const"; Index: sys/sys/rbt.h =================================================================== RCS file: sys/sys/rbt.h diff -N sys/sys/rbt.h --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ sys/sys/rbt.h 5 Oct 2016 10:49:40 -0000 @@ -0,0 +1,219 @@ +/* $OpenBSD: tree.h,v 1.24 2016/09/15 06:07:22 dlg Exp $ */ + +/* + * Copyright (c) 2016 David Gwynne + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _SYS_RBT_H_ +#define _SYS_RBT_H_ + +#include +#include /* for __offsetof */ + +#include + +static inline void +_rb_init(struct rb_tree *rbt) +{ + rbt->rbt_root = NULL; +} + +static inline int +_rb_empty(struct rb_tree *rbt) +{ + return (rbt->rbt_root == NULL); +} + +void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); +void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); +void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); +void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); +void *_rb_root(const struct rb_type *, struct rb_tree *); +void *_rb_min(const struct rb_type *, struct rb_tree *); +void *_rb_max(const struct rb_type *, struct rb_tree *); +void *_rb_next(const struct rb_type *, void *); +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_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); + +#define RBT_INITIALIZER(_head) { { NULL } } + +#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ +extern const struct rb_type *const _name##_RBT_TYPE; \ + \ +static inline void \ +_name##_RBT_INIT(struct _name *head) \ +{ \ + _rb_init(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ +{ \ + return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_FIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_ROOT(struct _name *head) \ +{ \ + return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline int \ +_name##_RBT_EMPTY(struct _name *head) \ +{ \ + return _rb_empty(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MIN(struct _name *head) \ +{ \ + return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MAX(struct _name *head) \ +{ \ + return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline void \ +_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_poison(_name##_RBT_TYPE, elm, poison); \ +} \ + \ +static inline int \ +_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_check(_name##_RBT_TYPE, elm, poison); \ +} + +#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ +static int \ +_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct rb_type _name##_RBT_INFO = { \ + _name##_RBT_COMPARE, \ + _aug, \ + __offsetof(struct _type, _field), \ +}; \ +const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO + +#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ +static void \ +_name##_RBT_AUGMENT(void *ptr) \ +{ \ + struct _type *p = ptr; \ + return _aug(p); \ +} \ +RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) + +#define RBT_GENERATE(_name, _type, _field, _cmp) \ + RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) + +#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) +#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) +#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) +#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) +#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) +#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) +#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) +#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) +#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) +#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) +#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) +#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_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) +#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) + +#define RBT_FOREACH(_e, _name, _head) \ + for ((_e) = RBT_MIN(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RBT_NEXT(_name, (_e))) + +#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ + for ((_e) = RBT_MIN(_name, (_head)); \ + (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ + (_e) = (_n)) + +#define RBT_FOREACH_REVERSE(_e, _name, _head) \ + for ((_e) = RBT_MAX(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RBT_PREV(_name, (_e))) + +#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ + for ((_e) = RBT_MAX(_name, (_head)); \ + (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ + (_e) = (_n)) + +#endif /* _SYS_RBT_H_ */ Index: sys/sys/rbtvar.h =================================================================== RCS file: sys/sys/rbtvar.h diff -N sys/sys/rbtvar.h --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ sys/sys/rbtvar.h 5 Oct 2016 10:49:40 -0000 @@ -0,0 +1,46 @@ +/* $OpenBSD: tree.h,v 1.24 2016/09/15 06:07:22 dlg Exp $ */ + +/* + * Copyright (c) 2016 David Gwynne + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _SYS_RBTVAR_H_ +#define _SYS_RBTVAR_H_ + +struct rb_type { + int (*t_compare)(const void *, const void *); + void (*t_augment)(void *); + unsigned int t_offset; /* offset of rb_entry in type */ +}; + +struct rb_tree { + struct rb_entry *rbt_root; +}; + +struct rb_entry { + struct rb_entry *rbt_parent; + struct rb_entry *rbt_left; + struct rb_entry *rbt_right; + unsigned int rbt_color; +}; + +#define RBT_HEAD(_name, _type) \ +struct _name { \ + struct rb_tree rbh_root; \ +} + +#define RBT_ENTRY(_type) struct rb_entry + +#endif /* _SYS_RBTVAR_H_ */ Index: sys/sys/tree.h =================================================================== RCS file: /cvs/src/sys/sys/tree.h,v retrieving revision 1.25 diff -u -p -r1.25 tree.h --- sys/sys/tree.h 26 Sep 2016 08:08:51 -0000 1.25 +++ sys/sys/tree.h 5 Oct 2016 10:49:40 -0000 @@ -747,241 +747,16 @@ name##_RB_MINMAX(struct name *head, int ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ (x) = (y)) - /* - * Copyright (c) 2016 David Gwynne - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. + * provide compat access to the function version of red-black trees * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * the types are included first so theyre always visible, and the api is + * included for use immediate use in the kernel. */ -struct rb_type { - int (*t_compare)(const void *, const void *); - void (*t_augment)(void *); - unsigned int t_offset; /* offset of rb_entry in type */ -}; - -struct rb_tree { - struct rb_entry *rbt_root; -}; - -struct rb_entry { - struct rb_entry *rbt_parent; - struct rb_entry *rbt_left; - struct rb_entry *rbt_right; - unsigned int rbt_color; -}; - -#define RBT_HEAD(_name, _type) \ -struct _name { \ - struct rb_tree rbh_root; \ -} - -#define RBT_ENTRY(_type) struct rb_entry - +#include #ifdef _KERNEL - -static inline void -_rb_init(struct rb_tree *rbt) -{ - rbt->rbt_root = NULL; -} - -static inline int -_rb_empty(struct rb_tree *rbt) -{ - return (rbt->rbt_root == NULL); -} - -void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); -void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); -void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); -void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); -void *_rb_root(const struct rb_type *, struct rb_tree *); -void *_rb_min(const struct rb_type *, struct rb_tree *); -void *_rb_max(const struct rb_type *, struct rb_tree *); -void *_rb_next(const struct rb_type *, void *); -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_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); - -#define RBT_INITIALIZER(_head) { { NULL } } - -#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ -extern const struct rb_type *const _name##_RBT_TYPE; \ - \ -__unused static inline void \ -_name##_RBT_INIT(struct _name *head) \ -{ \ - _rb_init(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ -{ \ - return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ -{ \ - return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_FIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_ROOT(struct _name *head) \ -{ \ - return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline int \ -_name##_RBT_EMPTY(struct _name *head) \ -{ \ - return _rb_empty(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MIN(struct _name *head) \ -{ \ - return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MAX(struct _name *head) \ -{ \ - return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NEXT(struct _type *elm) \ -{ \ - return _rb_next(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PREV(struct _type *elm) \ -{ \ - return _rb_prev(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_LEFT(struct _type *elm) \ -{ \ - return _rb_left(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_RIGHT(struct _type *elm) \ -{ \ - return _rb_right(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PARENT(struct _type *elm) \ -{ \ - return _rb_parent(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline void \ -_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_poison(_name##_RBT_TYPE, elm, poison); \ -} \ - \ -__unused static inline int \ -_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_check(_name##_RBT_TYPE, elm, poison); \ -} - -#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ -static int \ -_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ -{ \ - const struct _type *l = lptr, *r = rptr; \ - return _cmp(l, r); \ -} \ -static const struct rb_type _name##_RBT_INFO = { \ - _name##_RBT_COMPARE, \ - _aug, \ - offsetof(struct _type, _field), \ -}; \ -const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO - -#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ -static void \ -_name##_RBT_AUGMENT(void *ptr) \ -{ \ - struct _type *p = ptr; \ - return _aug(p); \ -} \ -RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) - -#define RBT_GENERATE(_name, _type, _field, _cmp) \ - RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) - -#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) -#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) -#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) -#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) -#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) -#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) -#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) -#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) -#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) -#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) -#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) -#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_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) -#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) - -#define RBT_FOREACH(_e, _name, _head) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_NEXT(_name, (_e))) - -#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ - (_e) = (_n)) - -#define RBT_FOREACH_REVERSE(_e, _name, _head) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_PREV(_name, (_e))) - -#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ - (_e) = (_n)) - +#include #endif /* _KERNEL */ #endif /* _SYS_TREE_H_ */ Index: lib/libc/Makefile.inc =================================================================== RCS file: /cvs/src/lib/libc/Makefile.inc,v retrieving revision 1.29 diff -u -p -r1.29 Makefile.inc --- lib/libc/Makefile.inc 7 May 2016 19:05:21 -0000 1.29 +++ lib/libc/Makefile.inc 5 Oct 2016 10:49:41 -0000 @@ -63,6 +63,7 @@ AINC+= -nostdinc -idirafter ${DESTDIR}/ .include "${LIBCSRCDIR}/termios/Makefile.inc" .include "${LIBCSRCDIR}/thread/Makefile.inc" .include "${LIBCSRCDIR}/time/Makefile.inc" +.include "${LIBCSRCDIR}/tree/Makefile.inc" .include "${LIBCSRCDIR}/uuid/Makefile.inc" .include "${LIBCSRCDIR}/sys/Makefile.inc" .if (${YP:L} == "yes") Index: lib/libc/Symbols.list =================================================================== RCS file: /cvs/src/lib/libc/Symbols.list,v retrieving revision 1.50 diff -u -p -r1.50 Symbols.list --- lib/libc/Symbols.list 3 Sep 2016 16:25:03 -0000 1.50 +++ lib/libc/Symbols.list 5 Oct 2016 10:49:41 -0000 @@ -1621,6 +1621,22 @@ tzset tzsetwall wcsftime +/* tree */ +_rb_insert +_rb_remove +_rb_find +_rb_nfind +_rb_root +_rb_min +_rb_max +_rb_next +_rb_prev +_rb_left +_rb_right +_rb_parent +_rb_poison +_rb_check + /* uuid */ uuid_compare uuid_create Index: lib/libc/shlib_version =================================================================== RCS file: /cvs/src/lib/libc/shlib_version,v retrieving revision 1.187 diff -u -p -r1.187 shlib_version --- lib/libc/shlib_version 17 Sep 2016 20:13:48 -0000 1.187 +++ lib/libc/shlib_version 5 Oct 2016 10:49:41 -0000 @@ -1,4 +1,4 @@ major=89 -minor=2 +minor=3 # note: If changes were made to include/thread_private.h or if system # calls were added/changed then librthread/shlib_version also be updated. Index: lib/libc/hidden/rbt.h =================================================================== RCS file: lib/libc/hidden/rbt.h diff -N lib/libc/hidden/rbt.h --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ lib/libc/hidden/rbt.h 5 Oct 2016 10:49:41 -0000 @@ -0,0 +1,38 @@ +/* $OpenBSD$ +/* + * Copyright (c) 2016 David Gwynne + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _LIBC_RBT +#define _LIBC_RBT + +#include_next + +PROTO_NORMAL(_rb_insert); +PROTO_NORMAL(_rb_remove); +PROTO_NORMAL(_rb_find); +PROTO_NORMAL(_rb_nfind); +PROTO_NORMAL(_rb_root); +PROTO_NORMAL(_rb_min); +PROTO_NORMAL(_rb_max); +PROTO_NORMAL(_rb_next); +PROTO_NORMAL(_rb_prev); +PROTO_NORMAL(_rb_left); +PROTO_NORMAL(_rb_right); +PROTO_NORMAL(_rb_parent); +PROTO_NORMAL(_rb_poison); +PROTO_NORMAL(_rb_check); + +#endif /* !_LIBC_RBT */ Index: lib/libc/stdlib/Makefile.inc =================================================================== RCS file: /cvs/src/lib/libc/stdlib/Makefile.inc,v retrieving revision 1.61 diff -u -p -r1.61 Makefile.inc --- lib/libc/stdlib/Makefile.inc 14 Aug 2016 23:18:03 -0000 1.61 +++ lib/libc/stdlib/Makefile.inc 5 Oct 2016 10:49:42 -0000 @@ -2,6 +2,7 @@ # stdlib sources .PATH: ${LIBCSRCDIR}/arch/${MACHINE_CPU}/stdlib ${LIBCSRCDIR}/stdlib +CFLAGS+=-DMALLOC_STATS SRCS+= a64l.c abort.c atexit.c atoi.c atof.c atol.c atoll.c bsearch.c \ exit.c ecvt.c gcvt.c getenv.c getopt_long.c \ Index: lib/libc/stdlib/malloc.c =================================================================== RCS file: /cvs/src/lib/libc/stdlib/malloc.c,v retrieving revision 1.197 diff -u -p -r1.197 malloc.c --- lib/libc/stdlib/malloc.c 21 Sep 2016 04:38:56 -0000 1.197 +++ lib/libc/stdlib/malloc.c 5 Oct 2016 10:49:42 -0000 @@ -38,7 +38,7 @@ #include #ifdef MALLOC_STATS -#include +#include #include #endif @@ -1776,18 +1776,19 @@ struct malloc_leak { }; struct leaknode { - RB_ENTRY(leaknode) entry; + RBT_ENTRY(leaknode) entry; struct malloc_leak d; }; -static int -leakcmp(struct leaknode *e1, struct leaknode *e2) +static inline int +leakcmp(const struct leaknode *e1, const struct leaknode *e2) { return e1->d.f < e2->d.f ? -1 : e1->d.f > e2->d.f; } -static RB_HEAD(leaktree, leaknode) leakhead; -RB_GENERATE_STATIC(leaktree, leaknode, entry, leakcmp) +static RBT_HEAD(leaktree, leaknode) leakhead; +RBT_PROTOTYPE(leaktree, leaknode, entry, leakcmp); +RBT_GENERATE(leaktree, leaknode, entry, leakcmp); static void putleakinfo(void *f, size_t sz, int cnt) @@ -1800,7 +1801,7 @@ putleakinfo(void *f, size_t sz, int cnt) return; key.d.f = f; - p = RB_FIND(leaktree, &leakhead, &key); + p = RBT_FIND(leaktree, &leakhead, &key); if (p == NULL) { if (page == NULL || used >= MALLOC_PAGESIZE / sizeof(struct leaknode)) { @@ -1813,7 +1814,7 @@ putleakinfo(void *f, size_t sz, int cnt) p->d.f = f; p->d.total_size = sz * cnt; p->d.count = cnt; - RB_INSERT(leaktree, &leakhead, p); + RBT_INSERT(leaktree, &leakhead, p); } else { p->d.total_size += sz * cnt; p->d.count += cnt; @@ -1842,7 +1843,7 @@ dump_leaks(int fd) malloc_leaks = MMAP(MALLOC_PAGESIZE); if (malloc_leaks != MAP_FAILED) memset(malloc_leaks, 0, MALLOC_PAGESIZE); - RB_FOREACH(p, leaktree, &leakhead) { + RBT_FOREACH(p, leaktree, &leakhead) { snprintf(buf, sizeof(buf), "%18p %7zu %6u %6zu\n", p->d.f, p->d.total_size, p->d.count, p->d.total_size / p->d.count); write(fd, buf, strlen(buf)); @@ -2007,7 +2008,7 @@ malloc_dump(int fd, struct dir_info *poo pool->delayed_chunks[i] = NULL; } /* XXX leak when run multiple times */ - RB_INIT(&leakhead); + RBT_INIT(leaktree, &leakhead); malloc_dump1(fd, pool); errno = saved_errno; } Index: lib/libc/tree/Makefile.inc =================================================================== RCS file: lib/libc/tree/Makefile.inc diff -N lib/libc/tree/Makefile.inc --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ lib/libc/tree/Makefile.inc 5 Oct 2016 10:49:42 -0000 @@ -0,0 +1,8 @@ +# $OpenBSD: Makefile.inc,v 1.146 2016/07/04 18:01:44 guenther Exp $ +# $NetBSD: Makefile.inc,v 1.35 1995/10/16 23:49:07 jtc Exp $ +# @(#)Makefile.inc 8.1 (Berkeley) 6/17/93 + +# sources +.PATH: ${LIBCSRCDIR}/tree + +SRCS+= rbt.c Index: lib/libc/tree/rbt.c =================================================================== RCS file: lib/libc/tree/rbt.c diff -N lib/libc/tree/rbt.c --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ lib/libc/tree/rbt.c 5 Oct 2016 10:49:42 -0000 @@ -0,0 +1,631 @@ +/* $OpenBSD: subr_tree.c,v 1.6 2016/09/20 01:11:27 dlg Exp $ */ + +/* + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright (c) 2016 David Gwynne + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef DEF_STRONG +#define DEF_STRONG(sym) __asm("") +#endif + +#include + +static inline void * +rb_n2e(const struct rb_type *t, void *node) +{ + unsigned long addr = (unsigned long)node; + + return ((void *)(addr + t->t_offset)); +} + +static inline void * +rb_e2n(const struct rb_type *t, struct rb_entry *rbe) +{ + unsigned long addr = (unsigned long)rbe; + + return ((void *)(addr - t->t_offset)); +} + +#define RBE_BLACK 0 +#define RBE_RED 1 + +#define RBE_LEFT(_rbe) (_rbe)->rbt_left +#define RBE_RIGHT(_rbe) (_rbe)->rbt_right +#define RBE_PARENT(_rbe) (_rbe)->rbt_parent +#define RBE_COLOR(_rbe) (_rbe)->rbt_color + +#define RBH_ROOT(_rbt) (_rbt)->rbt_root + +static inline void +rbe_set(struct rb_entry *rbe, struct rb_entry *parent) +{ + RBE_PARENT(rbe) = parent; + RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; + RBE_COLOR(rbe) = RBE_RED; +} + +static inline void +rbe_set_blackred(struct rb_entry *black, struct rb_entry *red) +{ + RBE_COLOR(black) = RBE_BLACK; + RBE_COLOR(red) = RBE_RED; +} + +static inline void +rbe_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + (*t->t_augment)(rb_e2n(t, rbe)); +} + +static inline void +rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + if (t->t_augment != NULL) + rbe_augment(t, rbe); +} + +static inline void +rbe_rotate_left(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_RIGHT(rbe); + RBE_RIGHT(rbe) = RBE_LEFT(tmp); + if (RBE_RIGHT(rbe) != NULL) + RBE_PARENT(RBE_LEFT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_LEFT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_rotate_right(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_LEFT(rbe); + RBE_LEFT(rbe) = RBE_RIGHT(tmp); + if (RBE_LEFT(rbe) != NULL) + RBE_PARENT(RBE_RIGHT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_RIGHT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_insert_color(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent, *gparent, *tmp; + + while ((parent = RBE_PARENT(rbe)) != NULL && + RBE_COLOR(parent) == RBE_RED) { + gparent = RBE_PARENT(parent); + + if (parent == RBE_LEFT(gparent)) { + tmp = RBE_RIGHT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) { + RBE_COLOR(tmp) = RBE_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_RIGHT(parent) == rbe) { + rbe_rotate_left(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_right(t, rbt, gparent); + } else { + tmp = RBE_LEFT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) { + RBE_COLOR(tmp) = RBE_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_LEFT(parent) == rbe) { + rbe_rotate_right(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_left(t, rbt, gparent); + } + } + + RBE_COLOR(RBH_ROOT(rbt)) = RBE_BLACK; +} + +static inline void +rbe_remove_color(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *parent, struct rb_entry *rbe) +{ + struct rb_entry *tmp; + + while ((rbe == NULL || RBE_COLOR(rbe) == RBE_BLACK) && + rbe != RBH_ROOT(rbt)) { + if (RBE_LEFT(parent) == rbe) { + tmp = RBE_RIGHT(parent); + if (RBE_COLOR(tmp) == RBE_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_left(t, rbt, parent); + tmp = RBE_RIGHT(parent); + } + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) { + RBE_COLOR(tmp) = RBE_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK) { + struct rb_entry *oleft; + + oleft = RBE_LEFT(tmp); + if (oleft != NULL) + RBE_COLOR(oleft) = RBE_BLACK; + + RBE_COLOR(tmp) = RBE_RED; + rbe_rotate_right(t, rbt, tmp); + tmp = RBE_RIGHT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RBE_BLACK; + if (RBE_RIGHT(tmp)) + RBE_COLOR(RBE_RIGHT(tmp)) = RBE_BLACK; + + rbe_rotate_left(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } else { + tmp = RBE_LEFT(parent); + if (RBE_COLOR(tmp) == RBE_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_right(t, rbt, parent); + tmp = RBE_LEFT(parent); + } + + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) { + RBE_COLOR(tmp) = RBE_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) { + struct rb_entry *oright; + + oright = RBE_RIGHT(tmp); + if (oright != NULL) + RBE_COLOR(oright) = RBE_BLACK; + + RBE_COLOR(tmp) = RBE_RED; + rbe_rotate_left(t, rbt, tmp); + tmp = RBE_LEFT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RBE_BLACK; + if (RBE_LEFT(tmp) != NULL) + RBE_COLOR(RBE_LEFT(tmp)) = RBE_BLACK; + + rbe_rotate_right(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } + } + + if (rbe != NULL) + RBE_COLOR(rbe) = RBE_BLACK; +} + +static inline struct rb_entry * +rbe_remove(const struct rb_type *t, struct rb_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *child, *parent, *old = rbe; + unsigned int color; + + if (RBE_LEFT(rbe) == NULL) + child = RBE_RIGHT(rbe); + else if (RBE_RIGHT(rbe) == NULL) + child = RBE_LEFT(rbe); + else { + struct rb_entry *tmp; + + rbe = RBE_RIGHT(rbe); + while ((tmp = RBE_LEFT(rbe)) != NULL) + rbe = tmp; + + child = RBE_RIGHT(rbe); + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; + if (RBE_PARENT(rbe) == old) + parent = rbe; + *rbe = *old; + + tmp = RBE_PARENT(old); + if (tmp != NULL) { + if (RBE_LEFT(tmp) == old) + RBE_LEFT(tmp) = rbe; + else + RBE_RIGHT(tmp) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + RBE_PARENT(RBE_LEFT(old)) = rbe; + if (RBE_RIGHT(old)) + RBE_PARENT(RBE_RIGHT(old)) = rbe; + + if (t->t_augment != NULL && parent != NULL) { + tmp = parent; + do { + rbe_augment(t, tmp); + tmp = RBE_PARENT(tmp); + } while (tmp != NULL); + } + + goto color; + } + + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; +color: + if (color == RBE_BLACK) + rbe_remove_color(t, rbt, parent, child); + + return (old); +} + +void * +_rb_remove(const struct rb_type *t, struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *old; + + old = rbe_remove(t, rbt, rbe); + + return (old == NULL ? NULL : rb_e2n(t, old)); +} +DEF_STRONG(_rb_remove); + +void * +_rb_insert(const struct rb_type *t, struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *tmp; + struct rb_entry *parent = NULL; + void *node; + int comp = 0; + + tmp = RBH_ROOT(rbt); + while (tmp != NULL) { + parent = tmp; + + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(elm, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + rbe_set(rbe, parent); + + if (parent != NULL) { + if (comp < 0) + RBE_LEFT(parent) = rbe; + else + RBE_RIGHT(parent) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + rbe_insert_color(t, rbt, rbe); + + return (NULL); +} +DEF_STRONG(_rb_insert); + +/* Finds the node with the same key as elm */ +void * +_rb_find(const struct rb_type *t, struct rb_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (NULL); +} +DEF_STRONG(_rb_find); + +/* Finds the first node greater than or equal to the search key */ +void * +_rb_nfind(const struct rb_type *t, struct rb_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + void *res = NULL; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) { + res = node; + tmp = RBE_LEFT(tmp); + } else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (res); +} +DEF_STRONG(_rb_nfind); + +void * +_rb_next(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_RIGHT(rbe) != NULL) { + rbe = RBE_RIGHT(rbe); + while (RBE_LEFT(rbe) != NULL) + rbe = RBE_LEFT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} +DEF_STRONG(_rb_next); + +void * +_rb_prev(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_LEFT(rbe)) { + rbe = RBE_LEFT(rbe); + while (RBE_RIGHT(rbe)) + rbe = RBE_RIGHT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} +DEF_STRONG(_rb_prev); + +void * +_rb_root(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + + return (rbe == NULL ? rbe : rb_e2n(t, rbe)); +} + +void * +_rb_min(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_LEFT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} +DEF_STRONG(_rb_min); + +void * +_rb_max(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_RIGHT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} +DEF_STRONG(_rb_max); + +void * +_rb_left(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_LEFT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} +DEF_STRONG(_rb_left); + +void * +_rb_right(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_RIGHT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} +DEF_STRONG(_rb_right); + +void * +_rb_parent(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_PARENT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} +DEF_STRONG(_rb_parent); + +void +_rb_poison(const struct rb_type *t, void *node, unsigned long poison) +{ + struct rb_entry *rbe = rb_n2e(t, node); + + RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) = + (struct rb_entry *)poison; +} +DEF_STRONG(_rb_poison); + +int +_rb_check(const struct rb_type *t, void *node, unsigned long poison) +{ + struct rb_entry *rbe = rb_n2e(t, node); + + return ((unsigned long)RBE_PARENT(rbe) == poison && + (unsigned long)RBE_LEFT(rbe) == poison && + (unsigned long)RBE_RIGHT(rbe) == poison); +} +DEF_STRONG(_rb_check);