From fd31e21c548f278c463bb2dd130a4ec859db7e8a Mon Sep 17 00:00:00 2001 From: aisha Date: Sun, 1 Sep 2024 00:22:59 +0000 Subject: [PATCH] add tests for linux kpi for rbtree lots of cleanup and rewriting by jsg@ --- regress/sys/sys/tree/Makefile | 4 +- regress/sys/sys/tree/rb-linux/Makefile | 6 + regress/sys/sys/tree/rb-linux/rb-linux.c | 154 +++++++++++++++++++++++ 3 files changed, 162 insertions(+), 2 deletions(-) create mode 100644 regress/sys/sys/tree/rb-linux/Makefile create mode 100644 regress/sys/sys/tree/rb-linux/rb-linux.c diff --git a/regress/sys/sys/tree/Makefile b/regress/sys/sys/tree/Makefile index b1300d58eb6..60cb7263be9 100644 --- a/regress/sys/sys/tree/Makefile +++ b/regress/sys/sys/tree/Makefile @@ -1,6 +1,6 @@ -# $OpenBSD: Makefile,v 1.3 2002/08/21 15:10:06 miod Exp $ +# $OpenBSD: Makefile,v 1.4 2024/09/01 00:22:59 aisha Exp $ -SUBDIR= splay rb +SUBDIR= splay rb rb-linux install: diff --git a/regress/sys/sys/tree/rb-linux/Makefile b/regress/sys/sys/tree/rb-linux/Makefile new file mode 100644 index 00000000000..8b43e9eb716 --- /dev/null +++ b/regress/sys/sys/tree/rb-linux/Makefile @@ -0,0 +1,6 @@ +# $OpenBSD: Makefile,v 1.1 2024/09/01 00:22:59 aisha Exp $ + +CFLAGS= -I${BSDSRCDIR}/sys/dev/pci/drm/include +PROGS= rb-linux + +.include diff --git a/regress/sys/sys/tree/rb-linux/rb-linux.c b/regress/sys/sys/tree/rb-linux/rb-linux.c new file mode 100644 index 00000000000..c2cd9ef1100 --- /dev/null +++ b/regress/sys/sys/tree/rb-linux/rb-linux.c @@ -0,0 +1,154 @@ +/* $OpenBSD: rb-linux.c,v 1.1 2024/09/01 00:22:59 aisha 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. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * 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. + */ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +struct keynode { + struct rb_node node; + int key; +}; + +struct rb_root root; + +struct keynode * +rb_find(struct rb_root *head, struct keynode *elm) +{ + struct rb_node *tmp = head->rb_node; + + while (tmp) { + struct keynode *n = container_of(tmp, struct keynode, node); + if (elm->key < n->key) + tmp = tmp->rb_left; + else if (elm->key > n->key) + tmp = tmp->rb_right; + else + return n; + } + return NULL; +} + +struct keynode * +rb_insert(struct rb_root *head, struct keynode *elm) +{ + struct rb_node **tmp; + struct rb_node *parent = NULL; + tmp = &(head->rb_node); + + while (*tmp) { + struct keynode *n = container_of(*tmp, struct keynode, node); + parent = *tmp; + if (elm->key < n->key) + tmp = &((*tmp)->rb_left); + else if (elm->key > n->key) + tmp = &((*tmp)->rb_right); + else + return n; + } + + rb_link_node(&elm->node, parent, tmp); + rb_insert_color(&elm->node, head); + + return NULL; +} + +#define TESTS 10 +#define ITER 150 +#define MIN 5 +#define MAX 5000 + +int +main(int argc, char **argv) +{ + struct keynode *tmp, *ins; + int i, t, max, min; + struct rb_node *rb_node; + + root = RB_ROOT; + + for (t = 0; t < 10; t++) { + for (i = 0; i < ITER; i++) { + tmp = malloc(sizeof(struct keynode)); + if (tmp == NULL) err(1, "malloc"); + do { + tmp->key = arc4random_uniform(MAX-MIN); + tmp->key += MIN; + } while (rb_find(&root, tmp) != NULL); + if (i == 0) + max = min = tmp->key; + else { + if (tmp->key > max) + max = tmp->key; + if (tmp->key < min) + min = tmp->key; + } + if (rb_insert(&root, tmp) != NULL) + errx(1, "rb_insert failed"); + } + + rb_node = rb_first(&root); + ins = container_of(rb_node, struct keynode, node); + if (ins->key != min) + errx(1, "min does not match"); + tmp = ins; + rb_node = rb_last(&root); + ins = container_of(rb_node, struct keynode, node); + if (ins->key != max) + errx(1, "max does not match"); + + rb_erase(&tmp->node, &root); + + for (i = 0; i < ITER - 1; i++) { + rb_node = rb_first(&root); + if (rb_node == NULL) + errx(1, "rb_first error"); + tmp = container_of(rb_node, struct keynode, node); + rb_erase(&tmp->node, &root); + free(tmp); + } + } + + exit(0); +} + +#undef RB_ROOT +#define RB_ROOT(head) (head)->rbh_root + +RB_GENERATE(linux_root, rb_node, __entry, panic_cmp); + +int +panic_cmp(struct rb_node *a, struct rb_node *b) +{ + errx(1, "%s", __func__); +} -- 2.20.1