summaryrefslogtreecommitdiffstats
path: root/lib/libc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libc')
-rw-r--r--lib/libc/Symbols.list17
-rw-r--r--lib/libc/gen/Makefile.inc4
-rw-r--r--lib/libc/gen/tree.c655
-rw-r--r--lib/libc/hidden/sys/tree.h42
-rw-r--r--lib/libc/shlib_version2
-rw-r--r--lib/libc/stdlib/malloc.c21
6 files changed, 728 insertions, 13 deletions
diff --git a/lib/libc/Symbols.list b/lib/libc/Symbols.list
index c26e08624c5..bba27bc4d54 100644
--- a/lib/libc/Symbols.list
+++ b/lib/libc/Symbols.list
@@ -503,6 +503,23 @@ __signbitf
__signbitl
_ctype_
_longjmp
+_rb_check
+_rb_find
+_rb_insert
+_rb_left
+_rb_max
+_rb_min
+_rb_next
+_rb_nfind
+_rb_parent
+_rb_poison
+_rb_prev
+_rb_remove
+_rb_right
+_rb_root
+_rb_set_left
+_rb_set_parent
+_rb_set_right
_setjmp
_sys_errlist
_sys_nerr
diff --git a/lib/libc/gen/Makefile.inc b/lib/libc/gen/Makefile.inc
index 7b332cd407c..fdcd7007123 100644
--- a/lib/libc/gen/Makefile.inc
+++ b/lib/libc/gen/Makefile.inc
@@ -1,4 +1,4 @@
-# $OpenBSD: Makefile.inc,v 1.75 2017/05/29 09:40:02 deraadt Exp $
+# $OpenBSD: Makefile.inc,v 1.76 2017/06/19 03:06:26 dlg Exp $
# gen sources
.PATH: ${LIBCSRCDIR}/arch/${MACHINE_CPU}/gen ${LIBCSRCDIR}/gen
@@ -22,7 +22,7 @@ SRCS+= alarm.c assert.c auth_subr.c authenticate.c \
siginterrupt.c siglist.c signal.c signame.c \
sigsetops.c sleep.c statvfs.c strtofflags.c sysconf.c \
syslog.c syslog_r.c telldir.c time.c times.c \
- tolower_.c ttyname.c \
+ tolower_.c tree.c ttyname.c \
ttyslot.c toupper_.c ualarm.c uname.c unvis.c usleep.c \
utime.c valloc.c vis.c wait.c wait3.c waitpid.c warn.c \
warnc.c warnx.c vwarn.c vwarnc.c vwarnx.c verr.c verrc.c verrx.c
diff --git a/lib/libc/gen/tree.c b/lib/libc/gen/tree.c
new file mode 100644
index 00000000000..e647a795dd7
--- /dev/null
+++ b/lib/libc/gen/tree.c
@@ -0,0 +1,655 @@
+/* $OpenBSD: tree.c,v 1.1 2017/06/19 03:06:26 dlg Exp $ */
+
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * 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 <dlg@openbsd.org>
+ *
+ * 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.
+ */
+
+#include <sys/tree.h>
+
+static inline struct rb_entry *
+rb_n2e(const struct rb_type *t, void *node)
+{
+ unsigned long addr = (unsigned long)node;
+
+ return ((struct rb_entry *)(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_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) = RB_RED;
+}
+
+static inline void
+rbe_set_blackred(struct rb_entry *black, struct rb_entry *red)
+{
+ RBE_COLOR(black) = RB_BLACK;
+ RBE_COLOR(red) = RB_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) == RB_RED) {
+ gparent = RBE_PARENT(parent);
+
+ if (parent == RBE_LEFT(gparent)) {
+ tmp = RBE_RIGHT(gparent);
+ if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
+ RBE_COLOR(tmp) = RB_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) == RB_RED) {
+ RBE_COLOR(tmp) = RB_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)) = RB_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) == RB_BLACK) &&
+ rbe != RBH_ROOT(rbt)) {
+ if (RBE_LEFT(parent) == rbe) {
+ tmp = RBE_RIGHT(parent);
+ if (RBE_COLOR(tmp) == RB_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)) == RB_BLACK) &&
+ (RBE_RIGHT(tmp) == NULL ||
+ RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
+ RBE_COLOR(tmp) = RB_RED;
+ rbe = parent;
+ parent = RBE_PARENT(rbe);
+ } else {
+ if (RBE_RIGHT(tmp) == NULL ||
+ RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
+ struct rb_entry *oleft;
+
+ oleft = RBE_LEFT(tmp);
+ if (oleft != NULL)
+ RBE_COLOR(oleft) = RB_BLACK;
+
+ RBE_COLOR(tmp) = RB_RED;
+ rbe_rotate_right(t, rbt, tmp);
+ tmp = RBE_RIGHT(parent);
+ }
+
+ RBE_COLOR(tmp) = RBE_COLOR(parent);
+ RBE_COLOR(parent) = RB_BLACK;
+ if (RBE_RIGHT(tmp))
+ RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
+
+ rbe_rotate_left(t, rbt, parent);
+ rbe = RBH_ROOT(rbt);
+ break;
+ }
+ } else {
+ tmp = RBE_LEFT(parent);
+ if (RBE_COLOR(tmp) == RB_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)) == RB_BLACK) &&
+ (RBE_RIGHT(tmp) == NULL ||
+ RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
+ RBE_COLOR(tmp) = RB_RED;
+ rbe = parent;
+ parent = RBE_PARENT(rbe);
+ } else {
+ if (RBE_LEFT(tmp) == NULL ||
+ RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
+ struct rb_entry *oright;
+
+ oright = RBE_RIGHT(tmp);
+ if (oright != NULL)
+ RBE_COLOR(oright) = RB_BLACK;
+
+ RBE_COLOR(tmp) = RB_RED;
+ rbe_rotate_left(t, rbt, tmp);
+ tmp = RBE_LEFT(parent);
+ }
+
+ RBE_COLOR(tmp) = RBE_COLOR(parent);
+ RBE_COLOR(parent) = RB_BLACK;
+ if (RBE_LEFT(tmp) != NULL)
+ RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
+
+ rbe_rotate_right(t, rbt, parent);
+ rbe = RBH_ROOT(rbt);
+ break;
+ }
+ }
+ }
+
+ if (rbe != NULL)
+ RBE_COLOR(rbe) = RB_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 == RB_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));
+}
+DEF_STRONG(_rb_root);
+
+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_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;
+}
+DEF_STRONG(_rb_set_left);
+
+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;
+}
+DEF_STRONG(_rb_set_right);
+
+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;
+}
+DEF_STRONG(_rb_set_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);
diff --git a/lib/libc/hidden/sys/tree.h b/lib/libc/hidden/sys/tree.h
new file mode 100644
index 00000000000..91f2563a22b
--- /dev/null
+++ b/lib/libc/hidden/sys/tree.h
@@ -0,0 +1,42 @@
+/* $OpenBSD: tree.h,v 1.1 2017/06/19 03:06:26 dlg Exp $ */
+
+/*
+ * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
+ *
+ * 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_TREE
+#define _LIBC_TREE
+
+#include_next <sys/tree.h>
+
+PROTO_NORMAL(_rb_check);
+PROTO_NORMAL(_rb_find);
+PROTO_NORMAL(_rb_insert);
+PROTO_NORMAL(_rb_left);
+PROTO_NORMAL(_rb_max);
+PROTO_NORMAL(_rb_min);
+PROTO_NORMAL(_rb_next);
+PROTO_NORMAL(_rb_nfind);
+PROTO_NORMAL(_rb_parent);
+PROTO_NORMAL(_rb_poison);
+PROTO_NORMAL(_rb_prev);
+PROTO_NORMAL(_rb_remove);
+PROTO_NORMAL(_rb_right);
+PROTO_NORMAL(_rb_root);
+PROTO_NORMAL(_rb_set_left);
+PROTO_NORMAL(_rb_set_parent);
+PROTO_NORMAL(_rb_set_right);
+
+#endif /* !_LIBC_TREE */
diff --git a/lib/libc/shlib_version b/lib/libc/shlib_version
index 6793602e573..dba8c777a39 100644
--- a/lib/libc/shlib_version
+++ b/lib/libc/shlib_version
@@ -1,4 +1,4 @@
major=89
-minor=5
+minor=6
# note: If changes were made to include/thread_private.h or if system
# calls were added/changed then librthread/shlib_version also be updated.
diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index 999da6c1e9c..eaa97f88bbd 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: malloc.c,v 1.225 2017/05/13 07:11:29 otto Exp $ */
+/* $OpenBSD: malloc.c,v 1.226 2017/06/19 03:06:26 dlg Exp $ */
/*
* Copyright (c) 2008, 2010, 2011, 2016 Otto Moerbeek <otto@drijf.net>
* Copyright (c) 2012 Matthew Dempsky <matthew@openbsd.org>
@@ -2085,18 +2085,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)
@@ -2109,7 +2110,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)) {
@@ -2122,7 +2123,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;
@@ -2151,7 +2152,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));
@@ -2316,7 +2317,7 @@ malloc_dump(int fd, int poolno, struct dir_info *pool)
pool->delayed_chunks[i] = NULL;
}
/* XXX leak when run multiple times */
- RB_INIT(&leakhead);
+ RBT_INIT(leaktree, &leakhead);
malloc_dump1(fd, poolno, pool);
errno = saved_errno;
}
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.