libc/include/sys/tree.h: Re-add sys/tree.h

  Reverts 1339af44679aee0895fe311cfad89d38cfc2b919
---
 newlib/libc/include/sys/tree.h | 864 +++++++++++++++++++++++++++++++++
 1 file changed, 864 insertions(+)
 create mode 100644 newlib/libc/include/sys/tree.h
  

This file should not be added in a shared folder. It was a mistake to
put it there in the first place. The problem is that this file is not
a standard interface, it is de facto defined by the upstream (FreeBSD)
and they do not provide backward compatibility in this file as an API.
As a result, an application built with one version may not be upgraded
to a newer version.

It's a standalone include file that is not itself used inside of
newlib. If someone packaging newlib to distribute wants to provide a
specific version, they should do that in their own distribution. It
would be impossible to maintain a version of this file that would be
capable of making everyone happy, due to the above backward
compatibility problems.

We discovered this issue exactly when trying to use different versions
of libraries from freebsd together with newlib packaged in rtems.

Gedare

On Wed, Jul 17, 2024 at 7:51 AM Joel Sherrill <joel@rtems.org> wrote:
>
> Reverts 1339af44679aee0895fe311cfad89d38cfc2b919
> ---
>  newlib/libc/include/sys/tree.h | 864 +++++++++++++++++++++++++++++++++
>  1 file changed, 864 insertions(+)
>  create mode 100644 newlib/libc/include/sys/tree.h
>
> diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
> new file mode 100644
> index 000000000..2d3cec0ec
> --- /dev/null
> +++ b/newlib/libc/include/sys/tree.h
> @@ -0,0 +1,864 @@
> +/*     $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
> +/*     $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
> +/* $FreeBSD: head/sys/sys/tree.h 347360 2019-05-08 18:47:00Z trasz $ */
> +
> +/*-
> + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
> + *
> + * 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.
> + */
> +
> +#ifndef        _SYS_TREE_H_
> +#define        _SYS_TREE_H_
> +
> +#include <sys/cdefs.h>
> +
> +/*
> + * This file defines data structures for different types of trees:
> + * splay trees and red-black trees.
> + *
> + * A splay tree is a self-organizing data structure.  Every operation
> + * on the tree causes a splay to happen.  The splay moves the requested
> + * node to the root of the tree and partly rebalances it.
> + *
> + * This has the benefit that request locality causes faster lookups as
> + * the requested nodes move to the top of the tree.  On the other hand,
> + * every lookup causes memory writes.
> + *
> + * The Balance Theorem bounds the total access time for m operations
> + * and n inserts on an initially empty tree as O((m + n)lg n).  The
> + * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
> + *
> + * A red-black tree is a binary search tree with the node color as an
> + * extra attribute.  It fulfills a set of conditions:
> + *     - every search path from the root to a leaf consists of the
> + *       same number of black nodes,
> + *     - each red node (except for the root) has a black parent,
> + *     - each leaf node is black.
> + *
> + * Every operation on a red-black tree is bounded as O(lg n).
> + * The maximum height of a red-black tree is 2lg (n+1).
> + */
> +
> +#define SPLAY_HEAD(name, type)                                         \
> +struct name {                                                          \
> +       struct type *sph_root; /* root of the tree */                   \
> +}
> +
> +#define SPLAY_INITIALIZER(root)                                                \
> +       { NULL }
> +
> +#define SPLAY_INIT(root) do {                                          \
> +       (root)->sph_root = NULL;                                        \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define SPLAY_ENTRY(type)                                              \
> +struct {                                                               \
> +       struct type *spe_left; /* left element */                       \
> +       struct type *spe_right; /* right element */                     \
> +}
> +
> +#define SPLAY_LEFT(elm, field)         (elm)->field.spe_left
> +#define SPLAY_RIGHT(elm, field)                (elm)->field.spe_right
> +#define SPLAY_ROOT(head)               (head)->sph_root
> +#define SPLAY_EMPTY(head)              (SPLAY_ROOT(head) == NULL)
> +
> +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
> +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                      \
> +       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
> +       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
> +       (head)->sph_root = tmp;                                         \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define SPLAY_ROTATE_LEFT(head, tmp, field) do {                       \
> +       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
> +       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
> +       (head)->sph_root = tmp;                                         \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define SPLAY_LINKLEFT(head, tmp, field) do {                          \
> +       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
> +       tmp = (head)->sph_root;                                         \
> +       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define SPLAY_LINKRIGHT(head, tmp, field) do {                         \
> +       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
> +       tmp = (head)->sph_root;                                         \
> +       (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define SPLAY_ASSEMBLE(head, node, left, right, field) do {            \
> +       SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
> +       SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
> +       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
> +       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
> +} while (/*CONSTCOND*/ 0)
> +
> +/* Generates prototypes and inline functions */
> +
> +#define SPLAY_PROTOTYPE(name, type, field, cmp)                                \
> +void name##_SPLAY(struct name *, struct type *);                       \
> +void name##_SPLAY_MINMAX(struct name *, int);                          \
> +struct type *name##_SPLAY_INSERT(struct name *, struct type *);                \
> +struct type *name##_SPLAY_REMOVE(struct name *, struct type *);                \
> +                                                                       \
> +/* Finds the node with the same key as elm */                          \
> +static __unused __inline struct type *                                 \
> +name##_SPLAY_FIND(struct name *head, struct type *elm)                 \
> +{                                                                      \
> +       if (SPLAY_EMPTY(head))                                          \
> +               return(NULL);                                           \
> +       name##_SPLAY(head, elm);                                        \
> +       if ((cmp)(elm, (head)->sph_root) == 0)                          \
> +               return (head->sph_root);                                \
> +       return (NULL);                                                  \
> +}                                                                      \
> +                                                                       \
> +static __unused __inline struct type *                                 \
> +name##_SPLAY_NEXT(struct name *head, struct type *elm)                 \
> +{                                                                      \
> +       name##_SPLAY(head, elm);                                        \
> +       if (SPLAY_RIGHT(elm, field) != NULL) {                          \
> +               elm = SPLAY_RIGHT(elm, field);                          \
> +               while (SPLAY_LEFT(elm, field) != NULL) {                \
> +                       elm = SPLAY_LEFT(elm, field);                   \
> +               }                                                       \
> +       } else                                                          \
> +               elm = NULL;                                             \
> +       return (elm);                                                   \
> +}                                                                      \
> +                                                                       \
> +static __unused __inline struct type *                                 \
> +name##_SPLAY_MIN_MAX(struct name *head, int val)                       \
> +{                                                                      \
> +       name##_SPLAY_MINMAX(head, val);                                 \
> +        return (SPLAY_ROOT(head));                                     \
> +}
> +
> +/* Main splay operation.
> + * Moves node close to the key of elm to top
> + */
> +#define SPLAY_GENERATE(name, type, field, cmp)                         \
> +struct type *                                                          \
> +name##_SPLAY_INSERT(struct name *head, struct type *elm)               \
> +{                                                                      \
> +    if (SPLAY_EMPTY(head)) {                                           \
> +           SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
> +    } else {                                                           \
> +           int __comp;                                                 \
> +           name##_SPLAY(head, elm);                                    \
> +           __comp = (cmp)(elm, (head)->sph_root);                      \
> +           if(__comp < 0) {                                            \
> +                   SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
> +                   SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
> +                   SPLAY_LEFT((head)->sph_root, field) = NULL;         \
> +           } else if (__comp > 0) {                                    \
> +                   SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
> +                   SPLAY_LEFT(elm, field) = (head)->sph_root;          \
> +                   SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
> +           } else                                                      \
> +                   return ((head)->sph_root);                          \
> +    }                                                                  \
> +    (head)->sph_root = (elm);                                          \
> +    return (NULL);                                                     \
> +}                                                                      \
> +                                                                       \
> +struct type *                                                          \
> +name##_SPLAY_REMOVE(struct name *head, struct type *elm)               \
> +{                                                                      \
> +       struct type *__tmp;                                             \
> +       if (SPLAY_EMPTY(head))                                          \
> +               return (NULL);                                          \
> +       name##_SPLAY(head, elm);                                        \
> +       if ((cmp)(elm, (head)->sph_root) == 0) {                        \
> +               if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
> +                       (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
> +               } else {                                                \
> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
> +                       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
> +                       name##_SPLAY(head, elm);                        \
> +                       SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
> +               }                                                       \
> +               return (elm);                                           \
> +       }                                                               \
> +       return (NULL);                                                  \
> +}                                                                      \
> +                                                                       \
> +void                                                                   \
> +name##_SPLAY(struct name *head, struct type *elm)                      \
> +{                                                                      \
> +       struct type __node, *__left, *__right, *__tmp;                  \
> +       int __comp;                                                     \
> +\
> +       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
> +       __left = __right = &__node;                                     \
> +\
> +       while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
> +               if (__comp < 0) {                                       \
> +                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
> +                       if (__tmp == NULL)                              \
> +                               break;                                  \
> +                       if ((cmp)(elm, __tmp) < 0){                     \
> +                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
> +                               if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
> +                                       break;                          \
> +                       }                                               \
> +                       SPLAY_LINKLEFT(head, __right, field);           \
> +               } else if (__comp > 0) {                                \
> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
> +                       if (__tmp == NULL)                              \
> +                               break;                                  \
> +                       if ((cmp)(elm, __tmp) > 0){                     \
> +                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
> +                               if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
> +                                       break;                          \
> +                       }                                               \
> +                       SPLAY_LINKRIGHT(head, __left, field);           \
> +               }                                                       \
> +       }                                                               \
> +       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
> +}                                                                      \
> +                                                                       \
> +/* Splay with either the minimum or the maximum element                        \
> + * Used to find minimum or maximum element in tree.                    \
> + */                                                                    \
> +void name##_SPLAY_MINMAX(struct name *head, int __comp) \
> +{                                                                      \
> +       struct type __node, *__left, *__right, *__tmp;                  \
> +\
> +       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
> +       __left = __right = &__node;                                     \
> +\
> +       while (1) {                                                     \
> +               if (__comp < 0) {                                       \
> +                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
> +                       if (__tmp == NULL)                              \
> +                               break;                                  \
> +                       if (__comp < 0){                                \
> +                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
> +                               if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
> +                                       break;                          \
> +                       }                                               \
> +                       SPLAY_LINKLEFT(head, __right, field);           \
> +               } else if (__comp > 0) {                                \
> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
> +                       if (__tmp == NULL)                              \
> +                               break;                                  \
> +                       if (__comp > 0) {                               \
> +                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
> +                               if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
> +                                       break;                          \
> +                       }                                               \
> +                       SPLAY_LINKRIGHT(head, __left, field);           \
> +               }                                                       \
> +       }                                                               \
> +       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
> +}
> +
> +#define SPLAY_NEGINF   -1
> +#define SPLAY_INF      1
> +
> +#define SPLAY_INSERT(name, x, y)       name##_SPLAY_INSERT(x, y)
> +#define SPLAY_REMOVE(name, x, y)       name##_SPLAY_REMOVE(x, y)
> +#define SPLAY_FIND(name, x, y)         name##_SPLAY_FIND(x, y)
> +#define SPLAY_NEXT(name, x, y)         name##_SPLAY_NEXT(x, y)
> +#define SPLAY_MIN(name, x)             (SPLAY_EMPTY(x) ? NULL  \
> +                                       : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
> +#define SPLAY_MAX(name, x)             (SPLAY_EMPTY(x) ? NULL  \
> +                                       : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
> +
> +#define SPLAY_FOREACH(x, name, head)                                   \
> +       for ((x) = SPLAY_MIN(name, head);                               \
> +            (x) != NULL;                                               \
> +            (x) = SPLAY_NEXT(name, head, x))
> +
> +/* Macros that define a red-black tree */
> +#define RB_HEAD(name, type)                                            \
> +struct name {                                                          \
> +       struct type *rbh_root; /* root of the tree */                   \
> +}
> +
> +#define RB_INITIALIZER(root)                                           \
> +       { NULL }
> +
> +#define RB_INIT(root) do {                                             \
> +       (root)->rbh_root = NULL;                                        \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define RB_BLACK       0
> +#define RB_RED         1
> +#define RB_ENTRY(type)                                                 \
> +struct {                                                               \
> +       struct type *rbe_left;          /* left element */              \
> +       struct type *rbe_right;         /* right element */             \
> +       struct type *rbe_parent;        /* parent element */            \
> +       int rbe_color;                  /* node color */                \
> +}
> +
> +#define RB_LEFT(elm, field)            (elm)->field.rbe_left
> +#define RB_RIGHT(elm, field)           (elm)->field.rbe_right
> +#define RB_PARENT(elm, field)          (elm)->field.rbe_parent
> +#define RB_COLOR(elm, field)           (elm)->field.rbe_color
> +#define RB_ISRED(elm, field)           ((elm) != NULL && RB_COLOR(elm, field) == RB_RED)
> +#define RB_ROOT(head)                  (head)->rbh_root
> +#define RB_EMPTY(head)                 (RB_ROOT(head) == NULL)
> +
> +#define RB_SET_PARENT(dst, src, field) do {                            \
> +       RB_PARENT(dst, field) = src;                                    \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define RB_SET(elm, parent, field) do {                                        \
> +       RB_SET_PARENT(elm, parent, field);                              \
> +       RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
> +       RB_COLOR(elm, field) = RB_RED;                                  \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define RB_SET_BLACKRED(black, red, field) do {                                \
> +       RB_COLOR(black, field) = RB_BLACK;                              \
> +       RB_COLOR(red, field) = RB_RED;                                  \
> +} while (/*CONSTCOND*/ 0)
> +
> +/*
> + * Something to be invoked in a loop at the root of every modified subtree,
> + * from the bottom up to the root, to update augmented node data.
> + */
> +#ifndef RB_AUGMENT
> +#define RB_AUGMENT(x)  break
> +#endif
> +
> +#define RB_SWAP_CHILD(head, out, in, field) do {                       \
> +       if (RB_PARENT(out, field) == NULL)                              \
> +               RB_ROOT(head) = (in);                                   \
> +       else if ((out) == RB_LEFT(RB_PARENT(out, field), field))        \
> +               RB_LEFT(RB_PARENT(out, field), field) = (in);           \
> +       else                                                            \
> +               RB_RIGHT(RB_PARENT(out, field), field) = (in);          \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define RB_ROTATE_LEFT(head, elm, tmp, field) do {                     \
> +       (tmp) = RB_RIGHT(elm, field);                                   \
> +       if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
> +               RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);        \
> +       }                                                               \
> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> +       RB_LEFT(tmp, field) = (elm);                                    \
> +       RB_SET_PARENT(elm, tmp, field);                                 \
> +       RB_AUGMENT(elm);                                                \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                    \
> +       (tmp) = RB_LEFT(elm, field);                                    \
> +       if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
> +               RB_SET_PARENT(RB_LEFT(elm, field), elm, field);         \
> +       }                                                               \
> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> +       RB_RIGHT(tmp, field) = (elm);                                   \
> +       RB_SET_PARENT(elm, tmp, field);                                 \
> +       RB_AUGMENT(elm);                                                \
> +} while (/*CONSTCOND*/ 0)
> +
> +/*
> + * The RB_PARENT_ROTATE_LEFT() and RB_PARENT_ROTATE_RIGHT() rotations are
> + * specialized versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be
> + * used if the parent node exists and the direction of the child element is
> + * known.
> + */
> +
> +#define RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do {           \
> +       (tmp) = RB_RIGHT(left, field);                                  \
> +       if ((RB_RIGHT(left, field) = RB_LEFT(tmp, field)) != NULL) {    \
> +               RB_SET_PARENT(RB_RIGHT(left, field), left, field);      \
> +       }                                                               \
> +       RB_SET_PARENT(tmp, parent, field);                              \
> +       RB_LEFT(parent, field) = (tmp);                                 \
> +       RB_LEFT(tmp, field) = (left);                                   \
> +       RB_SET_PARENT(left, tmp, field);                                \
> +       RB_AUGMENT(left);                                               \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do {         \
> +       (tmp) = RB_LEFT(right, field);                                  \
> +       if ((RB_LEFT(right, field) = RB_RIGHT(tmp, field)) != NULL) {   \
> +               RB_SET_PARENT(RB_LEFT(right, field), right, field);     \
> +       }                                                               \
> +       RB_SET_PARENT(tmp, parent, field);                              \
> +       RB_RIGHT(parent, field) = (tmp);                                \
> +       RB_RIGHT(tmp, field) = (right);                                 \
> +       RB_SET_PARENT(right, tmp, field);                               \
> +       RB_AUGMENT(right);                                              \
> +} while (/*CONSTCOND*/ 0)
> +
> +/*
> + * The RB_RED_ROTATE_LEFT() and RB_RED_ROTATE_RIGHT() rotations are specialized
> + * versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be used if we
> + * rotate an element with a red child which has a black sibling.  Such a red
> + * node must have at least two child nodes so that the following red-black tree
> + * invariant is fulfilled:
> + *
> + *  Every path from a given node to any of its descendant NULL nodes goes
> + *  through the same number of black nodes.
> + *
> + *  elm (could be the root)
> + *    /      \
> + * BLACK   RED (left or right child)
> + *          /   \
> + *       BLACK  BLACK
> + */
> +
> +#define RB_RED_ROTATE_LEFT(head, elm, tmp, field) do {                 \
> +       (tmp) = RB_RIGHT(elm, field);                                   \
> +       RB_RIGHT(elm, field) = RB_LEFT(tmp, field);                     \
> +       RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);                \
> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> +       RB_LEFT(tmp, field) = (elm);                                    \
> +       RB_SET_PARENT(elm, tmp, field);                                 \
> +       RB_AUGMENT(elm);                                                \
> +} while (/*CONSTCOND*/ 0)
> +
> +#define RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do {                        \
> +       (tmp) = RB_LEFT(elm, field);                                    \
> +       RB_LEFT(elm, field) = RB_RIGHT(tmp, field);                     \
> +       RB_SET_PARENT(RB_LEFT(elm, field), elm, field);                 \
> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> +       RB_RIGHT(tmp, field) = (elm);                                   \
> +       RB_SET_PARENT(elm, tmp, field);                                 \
> +       RB_AUGMENT(elm);                                                \
> +} while (/*CONSTCOND*/ 0)
> +
> +/* Generates prototypes and inline functions */
> +#define        RB_PROTOTYPE(name, type, field, cmp)                            \
> +       RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
> +#define        RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
> +       RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
> +#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)            \
> +       RB_PROTOTYPE_INSERT_COLOR(name, type, attr);                    \
> +       RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);                    \
> +       RB_PROTOTYPE_INSERT(name, type, attr);                          \
> +       RB_PROTOTYPE_REMOVE(name, type, attr);                          \
> +       RB_PROTOTYPE_FIND(name, type, attr);                            \
> +       RB_PROTOTYPE_NFIND(name, type, attr);                           \
> +       RB_PROTOTYPE_NEXT(name, type, attr);                            \
> +       RB_PROTOTYPE_PREV(name, type, attr);                            \
> +       RB_PROTOTYPE_MINMAX(name, type, attr);                          \
> +       RB_PROTOTYPE_REINSERT(name, type, attr);
> +#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)                    \
> +       attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
> +#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)                    \
> +       attr void name##_RB_REMOVE_COLOR(struct name *, struct type *)
> +#define RB_PROTOTYPE_REMOVE(name, type, attr)                          \
> +       attr struct type *name##_RB_REMOVE(struct name *, struct type *)
> +#define RB_PROTOTYPE_INSERT(name, type, attr)                          \
> +       attr struct type *name##_RB_INSERT(struct name *, struct type *)
> +#define RB_PROTOTYPE_FIND(name, type, attr)                            \
> +       attr struct type *name##_RB_FIND(struct name *, struct type *)
> +#define RB_PROTOTYPE_NFIND(name, type, attr)                           \
> +       attr struct type *name##_RB_NFIND(struct name *, struct type *)
> +#define RB_PROTOTYPE_NEXT(name, type, attr)                            \
> +       attr struct type *name##_RB_NEXT(struct type *)
> +#define RB_PROTOTYPE_PREV(name, type, attr)                            \
> +       attr struct type *name##_RB_PREV(struct type *)
> +#define RB_PROTOTYPE_MINMAX(name, type, attr)                          \
> +       attr struct type *name##_RB_MINMAX(struct name *, int)
> +#define RB_PROTOTYPE_REINSERT(name, type, attr)                        \
> +       attr struct type *name##_RB_REINSERT(struct name *, struct type *)
> +
> +/* Main rb operation.
> + * Moves node close to the key of elm to top
> + */
> +#define        RB_GENERATE(name, type, field, cmp)                             \
> +       RB_GENERATE_INTERNAL(name, type, field, cmp,)
> +#define        RB_GENERATE_STATIC(name, type, field, cmp)                      \
> +       RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
> +#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)             \
> +       RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
> +       RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
> +       RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
> +       RB_GENERATE_REMOVE(name, type, field, attr)                     \
> +       RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
> +       RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
> +       RB_GENERATE_NEXT(name, type, field, attr)                       \
> +       RB_GENERATE_PREV(name, type, field, attr)                       \
> +       RB_GENERATE_MINMAX(name, type, field, attr)                     \
> +       RB_GENERATE_REINSERT(name, type, field, cmp, attr)
> +
> +
> +#define RB_GENERATE_INSERT_COLOR(name, type, field, attr)              \
> +attr void                                                              \
> +name##_RB_INSERT_COLOR(struct name *head, struct type *elm)            \
> +{                                                                      \
> +       struct type *parent, *gparent, *tmp;                            \
> +       while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) {     \
> +               gparent = RB_PARENT(parent, field);                     \
> +               if (parent == RB_LEFT(gparent, field)) {                \
> +                       tmp = RB_RIGHT(gparent, field);                 \
> +                       if (RB_ISRED(tmp, field)) {                     \
> +                               RB_COLOR(tmp, field) = RB_BLACK;        \
> +                               RB_SET_BLACKRED(parent, gparent, field);\
> +                               elm = gparent;                          \
> +                               continue;                               \
> +                       }                                               \
> +                       if (RB_RIGHT(parent, field) == elm) {           \
> +                               RB_PARENT_ROTATE_LEFT(gparent, parent,  \
> +                                   tmp, field);                        \
> +                               tmp = parent;                           \
> +                               parent = elm;                           \
> +                               elm = tmp;                              \
> +                       }                                               \
> +                       RB_SET_BLACKRED(parent, gparent, field);        \
> +                       RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
> +               } else {                                                \
> +                       tmp = RB_LEFT(gparent, field);                  \
> +                       if (RB_ISRED(tmp, field)) {                     \
> +                               RB_COLOR(tmp, field) = RB_BLACK;        \
> +                               RB_SET_BLACKRED(parent, gparent, field);\
> +                               elm = gparent;                          \
> +                               continue;                               \
> +                       }                                               \
> +                       if (RB_LEFT(parent, field) == elm) {            \
> +                               RB_PARENT_ROTATE_RIGHT(gparent, parent, \
> +                                   tmp, field);                        \
> +                               tmp = parent;                           \
> +                               parent = elm;                           \
> +                               elm = tmp;                              \
> +                       }                                               \
> +                       RB_SET_BLACKRED(parent, gparent, field);        \
> +                       RB_ROTATE_LEFT(head, gparent, tmp, field);      \
> +               }                                                       \
> +       }                                                               \
> +       RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
> +}
> +
> +#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)              \
> +attr void                                                              \
> +name##_RB_REMOVE_COLOR(struct name *head, struct type *parent)         \
> +{                                                                      \
> +       struct type *elm, *tmp;                                         \
> +       elm = NULL;                                                     \
> +       do {                                                            \
> +               if (RB_LEFT(parent, field) == elm) {                    \
> +                       tmp = RB_RIGHT(parent, field);                  \
> +                       if (RB_COLOR(tmp, field) == RB_RED) {           \
> +                               RB_SET_BLACKRED(tmp, parent, field);    \
> +                               RB_RED_ROTATE_LEFT(head, parent, tmp, field); \
> +                               tmp = RB_RIGHT(parent, field);          \
> +                       }                                               \
> +                       if (RB_ISRED(RB_RIGHT(tmp, field), field))      \
> +                               RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
> +                       else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \
> +                               struct type *oleft;                     \
> +                               RB_PARENT_ROTATE_RIGHT(parent, tmp,     \
> +                                   oleft, field);                      \
> +                               RB_COLOR(oleft, field) = RB_BLACK;      \
> +                               tmp = oleft;                            \
> +                       } else {                                        \
> +                               RB_COLOR(tmp, field) = RB_RED;          \
> +                               elm = parent;                           \
> +                               parent = RB_PARENT(elm, field);         \
> +                               continue;                               \
> +                       }                                               \
> +                       RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
> +                       RB_COLOR(parent, field) = RB_BLACK;             \
> +                       RB_ROTATE_LEFT(head, parent, tmp, field);       \
> +                       elm = RB_ROOT(head);                            \
> +                       break;                                          \
> +               } else {                                                \
> +                       tmp = RB_LEFT(parent, field);                   \
> +                       if (RB_COLOR(tmp, field) == RB_RED) {           \
> +                               RB_SET_BLACKRED(tmp, parent, field);    \
> +                               RB_RED_ROTATE_RIGHT(head, parent, tmp, field); \
> +                               tmp = RB_LEFT(parent, field);           \
> +                       }                                               \
> +                       if (RB_ISRED(RB_LEFT(tmp, field), field))       \
> +                               RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
> +                       else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \
> +                               struct type *oright;                    \
> +                               RB_PARENT_ROTATE_LEFT(parent, tmp,      \
> +                                   oright, field);                     \
> +                               RB_COLOR(oright, field) = RB_BLACK;     \
> +                               tmp = oright;                           \
> +                       } else {                                        \
> +                               RB_COLOR(tmp, field) = RB_RED;          \
> +                               elm = parent;                           \
> +                               parent = RB_PARENT(elm, field);         \
> +                               continue;                               \
> +                       }                                               \
> +                       RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
> +                       RB_COLOR(parent, field) = RB_BLACK;             \
> +                       RB_ROTATE_RIGHT(head, parent, tmp, field);      \
> +                       elm = RB_ROOT(head);                            \
> +                       break;                                          \
> +               }                                                       \
> +       } while (RB_COLOR(elm, field) == RB_BLACK && parent != NULL);   \
> +       RB_COLOR(elm, field) = RB_BLACK;                                \
> +}
> +
> +#define RB_GENERATE_REMOVE(name, type, field, attr)                    \
> +attr struct type *                                                     \
> +name##_RB_REMOVE(struct name *head, struct type *elm)                  \
> +{                                                                      \
> +       struct type *child, *old, *parent, *right;                      \
> +       int color;                                                      \
> +                                                                       \
> +       old = elm;                                                      \
> +       parent = RB_PARENT(elm, field);                                 \
> +       right = RB_RIGHT(elm, field);                                   \
> +       color = RB_COLOR(elm, field);                                   \
> +       if (RB_LEFT(elm, field) == NULL)                                \
> +               elm = child = right;                                    \
> +       else if (right == NULL)                                         \
> +               elm = child = RB_LEFT(elm, field);                      \
> +       else {                                                          \
> +               if ((child = RB_LEFT(right, field)) == NULL) {          \
> +                       child = RB_RIGHT(right, field);                 \
> +                       RB_RIGHT(old, field) = child;                   \
> +                       parent = elm = right;                           \
> +               } else {                                                \
> +                       do                                              \
> +                               elm = child;                            \
> +                       while ((child = RB_LEFT(elm, field)) != NULL);  \
> +                       child = RB_RIGHT(elm, field);                   \
> +                       parent = RB_PARENT(elm, field);                 \
> +                       RB_LEFT(parent, field) = child;                 \
> +                       RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \
> +               }                                                       \
> +               RB_SET_PARENT(RB_LEFT(old, field), elm, field);         \
> +               color = RB_COLOR(elm, field);                           \
> +               elm->field = old->field;                                \
> +       }                                                               \
> +       RB_SWAP_CHILD(head, old, elm, field);                           \
> +       if (child != NULL) {                                            \
> +               RB_SET_PARENT(child, parent, field);                    \
> +               RB_COLOR(child, field) = RB_BLACK;                      \
> +       } else if (color != RB_RED && parent != NULL)                   \
> +               name##_RB_REMOVE_COLOR(head, parent);                   \
> +       while (parent != NULL) {                                        \
> +               RB_AUGMENT(parent);                                     \
> +               parent = RB_PARENT(parent, field);                      \
> +       }                                                               \
> +       return (old);                                                   \
> +}
> +
> +#define RB_GENERATE_INSERT(name, type, field, cmp, attr)               \
> +/* Inserts a node into the RB tree */                                  \
> +attr struct type *                                                     \
> +name##_RB_INSERT(struct name *head, struct type *elm)                  \
> +{                                                                      \
> +       struct type *tmp;                                               \
> +       struct type *parent = NULL;                                     \
> +       int comp = 0;                                                   \
> +       tmp = RB_ROOT(head);                                            \
> +       while (tmp) {                                                   \
> +               parent = tmp;                                           \
> +               comp = (cmp)(elm, parent);                              \
> +               if (comp < 0)                                           \
> +                       tmp = RB_LEFT(tmp, field);                      \
> +               else if (comp > 0)                                      \
> +                       tmp = RB_RIGHT(tmp, field);                     \
> +               else                                                    \
> +                       return (tmp);                                   \
> +       }                                                               \
> +       RB_SET(elm, parent, field);                                     \
> +       if (parent != NULL) {                                           \
> +               if (comp < 0)                                           \
> +                       RB_LEFT(parent, field) = elm;                   \
> +               else                                                    \
> +                       RB_RIGHT(parent, field) = elm;                  \
> +       } else                                                          \
> +               RB_ROOT(head) = elm;                                    \
> +       name##_RB_INSERT_COLOR(head, elm);                              \
> +       while (elm != NULL) {                                           \
> +               RB_AUGMENT(elm);                                        \
> +               elm = RB_PARENT(elm, field);                            \
> +       }                                                               \
> +       return (NULL);                                                  \
> +}
> +
> +#define RB_GENERATE_FIND(name, type, field, cmp, attr)                 \
> +/* Finds the node with the same key as elm */                          \
> +attr struct type *                                                     \
> +name##_RB_FIND(struct name *head, struct type *elm)                    \
> +{                                                                      \
> +       struct type *tmp = RB_ROOT(head);                               \
> +       int comp;                                                       \
> +       while (tmp) {                                                   \
> +               comp = cmp(elm, tmp);                                   \
> +               if (comp < 0)                                           \
> +                       tmp = RB_LEFT(tmp, field);                      \
> +               else if (comp > 0)                                      \
> +                       tmp = RB_RIGHT(tmp, field);                     \
> +               else                                                    \
> +                       return (tmp);                                   \
> +       }                                                               \
> +       return (NULL);                                                  \
> +}
> +
> +#define RB_GENERATE_NFIND(name, type, field, cmp, attr)                        \
> +/* Finds the first node greater than or equal to the search key */     \
> +attr struct type *                                                     \
> +name##_RB_NFIND(struct name *head, struct type *elm)                   \
> +{                                                                      \
> +       struct type *tmp = RB_ROOT(head);                               \
> +       struct type *res = NULL;                                        \
> +       int comp;                                                       \
> +       while (tmp) {                                                   \
> +               comp = cmp(elm, tmp);                                   \
> +               if (comp < 0) {                                         \
> +                       res = tmp;                                      \
> +                       tmp = RB_LEFT(tmp, field);                      \
> +               }                                                       \
> +               else if (comp > 0)                                      \
> +                       tmp = RB_RIGHT(tmp, field);                     \
> +               else                                                    \
> +                       return (tmp);                                   \
> +       }                                                               \
> +       return (res);                                                   \
> +}
> +
> +#define RB_GENERATE_NEXT(name, type, field, attr)                      \
> +/* ARGSUSED */                                                         \
> +attr struct type *                                                     \
> +name##_RB_NEXT(struct type *elm)                                       \
> +{                                                                      \
> +       if (RB_RIGHT(elm, field)) {                                     \
> +               elm = RB_RIGHT(elm, field);                             \
> +               while (RB_LEFT(elm, field))                             \
> +                       elm = RB_LEFT(elm, field);                      \
> +       } else {                                                        \
> +               if (RB_PARENT(elm, field) &&                            \
> +                   (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
> +                       elm = RB_PARENT(elm, field);                    \
> +               else {                                                  \
> +                       while (RB_PARENT(elm, field) &&                 \
> +                           (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
> +                               elm = RB_PARENT(elm, field);            \
> +                       elm = RB_PARENT(elm, field);                    \
> +               }                                                       \
> +       }                                                               \
> +       return (elm);                                                   \
> +}
> +
> +#define RB_GENERATE_PREV(name, type, field, attr)                      \
> +/* ARGSUSED */                                                         \
> +attr struct type *                                                     \
> +name##_RB_PREV(struct type *elm)                                       \
> +{                                                                      \
> +       if (RB_LEFT(elm, field)) {                                      \
> +               elm = RB_LEFT(elm, field);                              \
> +               while (RB_RIGHT(elm, field))                            \
> +                       elm = RB_RIGHT(elm, field);                     \
> +       } else {                                                        \
> +               if (RB_PARENT(elm, field) &&                            \
> +                   (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
> +                       elm = RB_PARENT(elm, field);                    \
> +               else {                                                  \
> +                       while (RB_PARENT(elm, field) &&                 \
> +                           (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
> +                               elm = RB_PARENT(elm, field);            \
> +                       elm = RB_PARENT(elm, field);                    \
> +               }                                                       \
> +       }                                                               \
> +       return (elm);                                                   \
> +}
> +
> +#define RB_GENERATE_MINMAX(name, type, field, attr)                    \
> +attr struct type *                                                     \
> +name##_RB_MINMAX(struct name *head, int val)                           \
> +{                                                                      \
> +       struct type *tmp = RB_ROOT(head);                               \
> +       struct type *parent = NULL;                                     \
> +       while (tmp) {                                                   \
> +               parent = tmp;                                           \
> +               if (val < 0)                                            \
> +                       tmp = RB_LEFT(tmp, field);                      \
> +               else                                                    \
> +                       tmp = RB_RIGHT(tmp, field);                     \
> +       }                                                               \
> +       return (parent);                                                \
> +}
> +
> +#define        RB_GENERATE_REINSERT(name, type, field, cmp, attr)              \
> +attr struct type *                                                     \
> +name##_RB_REINSERT(struct name *head, struct type *elm)                        \
> +{                                                                      \
> +       struct type *cmpelm;                                            \
> +       if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&             \
> +           cmp(cmpelm, elm) >= 0) ||                                   \
> +           ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&             \
> +           cmp(elm, cmpelm) >= 0)) {                                   \
> +               /* XXXLAS: Remove/insert is heavy handed. */            \
> +               RB_REMOVE(name, head, elm);                             \
> +               return (RB_INSERT(name, head, elm));                    \
> +       }                                                               \
> +       return (NULL);                                                  \
> +}                                                                      \
> +
> +#define RB_NEGINF      -1
> +#define RB_INF 1
> +
> +#define RB_INSERT(name, x, y)  name##_RB_INSERT(x, y)
> +#define RB_REMOVE(name, x, y)  name##_RB_REMOVE(x, y)
> +#define RB_FIND(name, x, y)    name##_RB_FIND(x, y)
> +#define RB_NFIND(name, x, y)   name##_RB_NFIND(x, y)
> +#define RB_NEXT(name, x, y)    name##_RB_NEXT(y)
> +#define RB_PREV(name, x, y)    name##_RB_PREV(y)
> +#define RB_MIN(name, x)                name##_RB_MINMAX(x, RB_NEGINF)
> +#define RB_MAX(name, x)                name##_RB_MINMAX(x, RB_INF)
> +#define RB_REINSERT(name, x, y)        name##_RB_REINSERT(x, y)
> +
> +#define RB_FOREACH(x, name, head)                                      \
> +       for ((x) = RB_MIN(name, head);                                  \
> +            (x) != NULL;                                               \
> +            (x) = name##_RB_NEXT(x))
> +
> +#define RB_FOREACH_FROM(x, name, y)                                    \
> +       for ((x) = (y);                                                 \
> +           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
> +            (x) = (y))
> +
> +#define RB_FOREACH_SAFE(x, name, head, y)                              \
> +       for ((x) = RB_MIN(name, head);                                  \
> +           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
> +            (x) = (y))
> +
> +#define RB_FOREACH_REVERSE(x, name, head)                              \
> +       for ((x) = RB_MAX(name, head);                                  \
> +            (x) != NULL;                                               \
> +            (x) = name##_RB_PREV(x))
> +
> +#define RB_FOREACH_REVERSE_FROM(x, name, y)                            \
> +       for ((x) = (y);                                                 \
> +           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
> +            (x) = (y))
> +
> +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                      \
> +       for ((x) = RB_MAX(name, head);                                  \
> +           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
> +            (x) = (y))
> +
> +#endif /* _SYS_TREE_H_ */
> --
> 2.24.4
>
  

----- Am 17. Jul 2024 um 16:29 schrieb Gedare Bloom gedare@rtems.org:

> This file should not be added in a shared folder. It was a mistake to
> put it there in the first place. The problem is that this file is not
> a standard interface, it is de facto defined by the upstream (FreeBSD)
> and they do not provide backward compatibility in this file as an API.

The <sys/tree.h> is also present in other BSD systems, for example:

https://man.openbsd.org/tree

https://man.netbsd.org/tree.3

Which API incompatibility did you observe? FreeBSD releases may break the Application Binary Interface (ABI), but an Application Programming Interface (API) break would surprise me. If the API was extended, then it would be probably easy to add the new API elements to the Newlib version of <sys/tree.h>.

> As a result, an application built with one version may not be upgraded
> to a newer version.
> 
> It's a standalone include file that is not itself used inside of
> newlib. If someone packaging newlib to distribute wants to provide a
> specific version, they should do that in their own distribution. It
> would be impossible to maintain a version of this file that would be
> capable of making everyone happy, due to the above backward
> compatibility problems.
> 
> We discovered this issue exactly when trying to use different versions
> of libraries from freebsd together with newlib packaged in rtems.

From my point of view the problem is that libbsd uses its own version of <sys/tree.h>. I maintained this file in Newlib for quite a while and monitored the changes in FreeBSD. At the time when FreeBSD changed the implementation to use rank-balanced trees, I made a performance evaluation and didn't see benefits for the priority queue use case. FreeBSD fine tuned their new implementation in the meantime, so the situation may have changed. When you update libbsd to a newer version of FreeBSD you can't blindly accept everything. FreeBSD may optimize for certain use cases which are less important in the context of a supposed to be real-time operating system.

Independent of this, please move on with whatever agenda you have since I have the minority opinion in the RTEMS Project with respect to this topic.

> 
> Gedare
> 
> On Wed, Jul 17, 2024 at 7:51 AM Joel Sherrill <joel@rtems.org> wrote:
>>
>> Reverts 1339af44679aee0895fe311cfad89d38cfc2b919
>> ---
>>  newlib/libc/include/sys/tree.h | 864 +++++++++++++++++++++++++++++++++
>>  1 file changed, 864 insertions(+)
>>  create mode 100644 newlib/libc/include/sys/tree.h
>>
>> diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
>> new file mode 100644
>> index 000000000..2d3cec0ec
>> --- /dev/null
>> +++ b/newlib/libc/include/sys/tree.h
>> @@ -0,0 +1,864 @@
>> +/*     $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
>> +/*     $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
>> +/* $FreeBSD: head/sys/sys/tree.h 347360 2019-05-08 18:47:00Z trasz $ */
>> +
>> +/*-
>> + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
>> + *
>> + * 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.
>> + */
>> +
>> +#ifndef        _SYS_TREE_H_
>> +#define        _SYS_TREE_H_
>> +
>> +#include <sys/cdefs.h>
>> +
>> +/*
>> + * This file defines data structures for different types of trees:
>> + * splay trees and red-black trees.
>> + *
>> + * A splay tree is a self-organizing data structure.  Every operation
>> + * on the tree causes a splay to happen.  The splay moves the requested
>> + * node to the root of the tree and partly rebalances it.
>> + *
>> + * This has the benefit that request locality causes faster lookups as
>> + * the requested nodes move to the top of the tree.  On the other hand,
>> + * every lookup causes memory writes.
>> + *
>> + * The Balance Theorem bounds the total access time for m operations
>> + * and n inserts on an initially empty tree as O((m + n)lg n).  The
>> + * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
>> + *
>> + * A red-black tree is a binary search tree with the node color as an
>> + * extra attribute.  It fulfills a set of conditions:
>> + *     - every search path from the root to a leaf consists of the
>> + *       same number of black nodes,
>> + *     - each red node (except for the root) has a black parent,
>> + *     - each leaf node is black.
>> + *
>> + * Every operation on a red-black tree is bounded as O(lg n).
>> + * The maximum height of a red-black tree is 2lg (n+1).
>> + */
>> +
>> +#define SPLAY_HEAD(name, type)                                         \
>> +struct name {                                                          \
>> +       struct type *sph_root; /* root of the tree */                   \
>> +}
>> +
>> +#define SPLAY_INITIALIZER(root)
>> \
>> +       { NULL }
>> +
>> +#define SPLAY_INIT(root) do {                                          \
>> +       (root)->sph_root = NULL;                                        \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define SPLAY_ENTRY(type)                                              \
>> +struct {                                                               \
>> +       struct type *spe_left; /* left element */                       \
>> +       struct type *spe_right; /* right element */                     \
>> +}
>> +
>> +#define SPLAY_LEFT(elm, field)         (elm)->field.spe_left
>> +#define SPLAY_RIGHT(elm, field)                (elm)->field.spe_right
>> +#define SPLAY_ROOT(head)               (head)->sph_root
>> +#define SPLAY_EMPTY(head)              (SPLAY_ROOT(head) == NULL)
>> +
>> +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
>> +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                      \
>> +       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
>> +       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
>> +       (head)->sph_root = tmp;                                         \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define SPLAY_ROTATE_LEFT(head, tmp, field) do {                       \
>> +       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
>> +       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
>> +       (head)->sph_root = tmp;                                         \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define SPLAY_LINKLEFT(head, tmp, field) do {                          \
>> +       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
>> +       tmp = (head)->sph_root;                                         \
>> +       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define SPLAY_LINKRIGHT(head, tmp, field) do {                         \
>> +       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
>> +       tmp = (head)->sph_root;                                         \
>> +       (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define SPLAY_ASSEMBLE(head, node, left, right, field) do {            \
>> +       SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
>> +       SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
>> +       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
>> +       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +/* Generates prototypes and inline functions */
>> +
>> +#define SPLAY_PROTOTYPE(name, type, field, cmp)
>> \
>> +void name##_SPLAY(struct name *, struct type *);                       \
>> +void name##_SPLAY_MINMAX(struct name *, int);                          \
>> +struct type *name##_SPLAY_INSERT(struct name *, struct type *);
>> \
>> +struct type *name##_SPLAY_REMOVE(struct name *, struct type *);
>> \
>> +                                                                       \
>> +/* Finds the node with the same key as elm */                          \
>> +static __unused __inline struct type *                                 \
>> +name##_SPLAY_FIND(struct name *head, struct type *elm)                 \
>> +{                                                                      \
>> +       if (SPLAY_EMPTY(head))                                          \
>> +               return(NULL);                                           \
>> +       name##_SPLAY(head, elm);                                        \
>> +       if ((cmp)(elm, (head)->sph_root) == 0)                          \
>> +               return (head->sph_root);                                \
>> +       return (NULL);                                                  \
>> +}                                                                      \
>> +                                                                       \
>> +static __unused __inline struct type *                                 \
>> +name##_SPLAY_NEXT(struct name *head, struct type *elm)                 \
>> +{                                                                      \
>> +       name##_SPLAY(head, elm);                                        \
>> +       if (SPLAY_RIGHT(elm, field) != NULL) {                          \
>> +               elm = SPLAY_RIGHT(elm, field);                          \
>> +               while (SPLAY_LEFT(elm, field) != NULL) {                \
>> +                       elm = SPLAY_LEFT(elm, field);                   \
>> +               }                                                       \
>> +       } else                                                          \
>> +               elm = NULL;                                             \
>> +       return (elm);                                                   \
>> +}                                                                      \
>> +                                                                       \
>> +static __unused __inline struct type *                                 \
>> +name##_SPLAY_MIN_MAX(struct name *head, int val)                       \
>> +{                                                                      \
>> +       name##_SPLAY_MINMAX(head, val);                                 \
>> +        return (SPLAY_ROOT(head));                                     \
>> +}
>> +
>> +/* Main splay operation.
>> + * Moves node close to the key of elm to top
>> + */
>> +#define SPLAY_GENERATE(name, type, field, cmp)                         \
>> +struct type *                                                          \
>> +name##_SPLAY_INSERT(struct name *head, struct type *elm)               \
>> +{                                                                      \
>> +    if (SPLAY_EMPTY(head)) {                                           \
>> +           SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
>> +    } else {                                                           \
>> +           int __comp;                                                 \
>> +           name##_SPLAY(head, elm);                                    \
>> +           __comp = (cmp)(elm, (head)->sph_root);                      \
>> +           if(__comp < 0) {                                            \
>> +                   SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root,
>> field);\
>> +                   SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
>> +                   SPLAY_LEFT((head)->sph_root, field) = NULL;         \
>> +           } else if (__comp > 0) {                                    \
>> +                   SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root,
>> field);\
>> +                   SPLAY_LEFT(elm, field) = (head)->sph_root;          \
>> +                   SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
>> +           } else                                                      \
>> +                   return ((head)->sph_root);                          \
>> +    }                                                                  \
>> +    (head)->sph_root = (elm);                                          \
>> +    return (NULL);                                                     \
>> +}                                                                      \
>> +                                                                       \
>> +struct type *                                                          \
>> +name##_SPLAY_REMOVE(struct name *head, struct type *elm)               \
>> +{                                                                      \
>> +       struct type *__tmp;                                             \
>> +       if (SPLAY_EMPTY(head))                                          \
>> +               return (NULL);                                          \
>> +       name##_SPLAY(head, elm);                                        \
>> +       if ((cmp)(elm, (head)->sph_root) == 0) {                        \
>> +               if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
>> +                       (head)->sph_root = SPLAY_RIGHT((head)->sph_root,
>> field);\
>> +               } else {                                                \
>> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
>> +                       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
>> +                       name##_SPLAY(head, elm);                        \
>> +                       SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
>> +               }                                                       \
>> +               return (elm);                                           \
>> +       }                                                               \
>> +       return (NULL);                                                  \
>> +}                                                                      \
>> +                                                                       \
>> +void                                                                   \
>> +name##_SPLAY(struct name *head, struct type *elm)                      \
>> +{                                                                      \
>> +       struct type __node, *__left, *__right, *__tmp;                  \
>> +       int __comp;                                                     \
>> +\
>> +       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
>> +       __left = __right = &__node;                                     \
>> +\
>> +       while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
>> +               if (__comp < 0) {                                       \
>> +                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
>> +                       if (__tmp == NULL)                              \
>> +                               break;                                  \
>> +                       if ((cmp)(elm, __tmp) < 0){                     \
>> +                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
>> +                               if (SPLAY_LEFT((head)->sph_root, field) ==
>> NULL)\
>> +                                       break;                          \
>> +                       }                                               \
>> +                       SPLAY_LINKLEFT(head, __right, field);           \
>> +               } else if (__comp > 0) {                                \
>> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
>> +                       if (__tmp == NULL)                              \
>> +                               break;                                  \
>> +                       if ((cmp)(elm, __tmp) > 0){                     \
>> +                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
>> +                               if (SPLAY_RIGHT((head)->sph_root, field) ==
>> NULL)\
>> +                                       break;                          \
>> +                       }                                               \
>> +                       SPLAY_LINKRIGHT(head, __left, field);           \
>> +               }                                                       \
>> +       }                                                               \
>> +       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
>> +}                                                                      \
>> +                                                                       \
>> +/* Splay with either the minimum or the maximum element
>> \
>> + * Used to find minimum or maximum element in tree.                    \
>> + */                                                                    \
>> +void name##_SPLAY_MINMAX(struct name *head, int __comp) \
>> +{                                                                      \
>> +       struct type __node, *__left, *__right, *__tmp;                  \
>> +\
>> +       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
>> +       __left = __right = &__node;                                     \
>> +\
>> +       while (1) {                                                     \
>> +               if (__comp < 0) {                                       \
>> +                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
>> +                       if (__tmp == NULL)                              \
>> +                               break;                                  \
>> +                       if (__comp < 0){                                \
>> +                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
>> +                               if (SPLAY_LEFT((head)->sph_root, field) ==
>> NULL)\
>> +                                       break;                          \
>> +                       }                                               \
>> +                       SPLAY_LINKLEFT(head, __right, field);           \
>> +               } else if (__comp > 0) {                                \
>> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
>> +                       if (__tmp == NULL)                              \
>> +                               break;                                  \
>> +                       if (__comp > 0) {                               \
>> +                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
>> +                               if (SPLAY_RIGHT((head)->sph_root, field) ==
>> NULL)\
>> +                                       break;                          \
>> +                       }                                               \
>> +                       SPLAY_LINKRIGHT(head, __left, field);           \
>> +               }                                                       \
>> +       }                                                               \
>> +       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
>> +}
>> +
>> +#define SPLAY_NEGINF   -1
>> +#define SPLAY_INF      1
>> +
>> +#define SPLAY_INSERT(name, x, y)       name##_SPLAY_INSERT(x, y)
>> +#define SPLAY_REMOVE(name, x, y)       name##_SPLAY_REMOVE(x, y)
>> +#define SPLAY_FIND(name, x, y)         name##_SPLAY_FIND(x, y)
>> +#define SPLAY_NEXT(name, x, y)         name##_SPLAY_NEXT(x, y)
>> +#define SPLAY_MIN(name, x)             (SPLAY_EMPTY(x) ? NULL  \
>> +                                       : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
>> +#define SPLAY_MAX(name, x)             (SPLAY_EMPTY(x) ? NULL  \
>> +                                       : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
>> +
>> +#define SPLAY_FOREACH(x, name, head)                                   \
>> +       for ((x) = SPLAY_MIN(name, head);                               \
>> +            (x) != NULL;                                               \
>> +            (x) = SPLAY_NEXT(name, head, x))
>> +
>> +/* Macros that define a red-black tree */
>> +#define RB_HEAD(name, type)                                            \
>> +struct name {                                                          \
>> +       struct type *rbh_root; /* root of the tree */                   \
>> +}
>> +
>> +#define RB_INITIALIZER(root)                                           \
>> +       { NULL }
>> +
>> +#define RB_INIT(root) do {                                             \
>> +       (root)->rbh_root = NULL;                                        \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define RB_BLACK       0
>> +#define RB_RED         1
>> +#define RB_ENTRY(type)                                                 \
>> +struct {                                                               \
>> +       struct type *rbe_left;          /* left element */              \
>> +       struct type *rbe_right;         /* right element */             \
>> +       struct type *rbe_parent;        /* parent element */            \
>> +       int rbe_color;                  /* node color */                \
>> +}
>> +
>> +#define RB_LEFT(elm, field)            (elm)->field.rbe_left
>> +#define RB_RIGHT(elm, field)           (elm)->field.rbe_right
>> +#define RB_PARENT(elm, field)          (elm)->field.rbe_parent
>> +#define RB_COLOR(elm, field)           (elm)->field.rbe_color
>> +#define RB_ISRED(elm, field)           ((elm) != NULL && RB_COLOR(elm, field)
>> == RB_RED)
>> +#define RB_ROOT(head)                  (head)->rbh_root
>> +#define RB_EMPTY(head)                 (RB_ROOT(head) == NULL)
>> +
>> +#define RB_SET_PARENT(dst, src, field) do {                            \
>> +       RB_PARENT(dst, field) = src;                                    \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define RB_SET(elm, parent, field) do {
>> \
>> +       RB_SET_PARENT(elm, parent, field);                              \
>> +       RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
>> +       RB_COLOR(elm, field) = RB_RED;                                  \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define RB_SET_BLACKRED(black, red, field) do {
>> \
>> +       RB_COLOR(black, field) = RB_BLACK;                              \
>> +       RB_COLOR(red, field) = RB_RED;                                  \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +/*
>> + * Something to be invoked in a loop at the root of every modified subtree,
>> + * from the bottom up to the root, to update augmented node data.
>> + */
>> +#ifndef RB_AUGMENT
>> +#define RB_AUGMENT(x)  break
>> +#endif
>> +
>> +#define RB_SWAP_CHILD(head, out, in, field) do {                       \
>> +       if (RB_PARENT(out, field) == NULL)                              \
>> +               RB_ROOT(head) = (in);                                   \
>> +       else if ((out) == RB_LEFT(RB_PARENT(out, field), field))        \
>> +               RB_LEFT(RB_PARENT(out, field), field) = (in);           \
>> +       else                                                            \
>> +               RB_RIGHT(RB_PARENT(out, field), field) = (in);          \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define RB_ROTATE_LEFT(head, elm, tmp, field) do {                     \
>> +       (tmp) = RB_RIGHT(elm, field);                                   \
>> +       if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
>> +               RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);        \
>> +       }                                                               \
>> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
>> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
>> +       RB_LEFT(tmp, field) = (elm);                                    \
>> +       RB_SET_PARENT(elm, tmp, field);                                 \
>> +       RB_AUGMENT(elm);                                                \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                    \
>> +       (tmp) = RB_LEFT(elm, field);                                    \
>> +       if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
>> +               RB_SET_PARENT(RB_LEFT(elm, field), elm, field);         \
>> +       }                                                               \
>> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
>> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
>> +       RB_RIGHT(tmp, field) = (elm);                                   \
>> +       RB_SET_PARENT(elm, tmp, field);                                 \
>> +       RB_AUGMENT(elm);                                                \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +/*
>> + * The RB_PARENT_ROTATE_LEFT() and RB_PARENT_ROTATE_RIGHT() rotations are
>> + * specialized versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be
>> + * used if the parent node exists and the direction of the child element is
>> + * known.
>> + */
>> +
>> +#define RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do {           \
>> +       (tmp) = RB_RIGHT(left, field);                                  \
>> +       if ((RB_RIGHT(left, field) = RB_LEFT(tmp, field)) != NULL) {    \
>> +               RB_SET_PARENT(RB_RIGHT(left, field), left, field);      \
>> +       }                                                               \
>> +       RB_SET_PARENT(tmp, parent, field);                              \
>> +       RB_LEFT(parent, field) = (tmp);                                 \
>> +       RB_LEFT(tmp, field) = (left);                                   \
>> +       RB_SET_PARENT(left, tmp, field);                                \
>> +       RB_AUGMENT(left);                                               \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do {         \
>> +       (tmp) = RB_LEFT(right, field);                                  \
>> +       if ((RB_LEFT(right, field) = RB_RIGHT(tmp, field)) != NULL) {   \
>> +               RB_SET_PARENT(RB_LEFT(right, field), right, field);     \
>> +       }                                                               \
>> +       RB_SET_PARENT(tmp, parent, field);                              \
>> +       RB_RIGHT(parent, field) = (tmp);                                \
>> +       RB_RIGHT(tmp, field) = (right);                                 \
>> +       RB_SET_PARENT(right, tmp, field);                               \
>> +       RB_AUGMENT(right);                                              \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +/*
>> + * The RB_RED_ROTATE_LEFT() and RB_RED_ROTATE_RIGHT() rotations are specialized
>> + * versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be used if we
>> + * rotate an element with a red child which has a black sibling.  Such a red
>> + * node must have at least two child nodes so that the following red-black tree
>> + * invariant is fulfilled:
>> + *
>> + *  Every path from a given node to any of its descendant NULL nodes goes
>> + *  through the same number of black nodes.
>> + *
>> + *  elm (could be the root)
>> + *    /      \
>> + * BLACK   RED (left or right child)
>> + *          /   \
>> + *       BLACK  BLACK
>> + */
>> +
>> +#define RB_RED_ROTATE_LEFT(head, elm, tmp, field) do {                 \
>> +       (tmp) = RB_RIGHT(elm, field);                                   \
>> +       RB_RIGHT(elm, field) = RB_LEFT(tmp, field);                     \
>> +       RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);                \
>> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
>> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
>> +       RB_LEFT(tmp, field) = (elm);                                    \
>> +       RB_SET_PARENT(elm, tmp, field);                                 \
>> +       RB_AUGMENT(elm);                                                \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +#define RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do {
>> \
>> +       (tmp) = RB_LEFT(elm, field);                                    \
>> +       RB_LEFT(elm, field) = RB_RIGHT(tmp, field);                     \
>> +       RB_SET_PARENT(RB_LEFT(elm, field), elm, field);                 \
>> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
>> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
>> +       RB_RIGHT(tmp, field) = (elm);                                   \
>> +       RB_SET_PARENT(elm, tmp, field);                                 \
>> +       RB_AUGMENT(elm);                                                \
>> +} while (/*CONSTCOND*/ 0)
>> +
>> +/* Generates prototypes and inline functions */
>> +#define        RB_PROTOTYPE(name, type, field, cmp)
>> \
>> +       RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
>> +#define        RB_PROTOTYPE_STATIC(name, type, field, cmp)
>> \
>> +       RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
>> +#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)            \
>> +       RB_PROTOTYPE_INSERT_COLOR(name, type, attr);                    \
>> +       RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);                    \
>> +       RB_PROTOTYPE_INSERT(name, type, attr);                          \
>> +       RB_PROTOTYPE_REMOVE(name, type, attr);                          \
>> +       RB_PROTOTYPE_FIND(name, type, attr);                            \
>> +       RB_PROTOTYPE_NFIND(name, type, attr);                           \
>> +       RB_PROTOTYPE_NEXT(name, type, attr);                            \
>> +       RB_PROTOTYPE_PREV(name, type, attr);                            \
>> +       RB_PROTOTYPE_MINMAX(name, type, attr);                          \
>> +       RB_PROTOTYPE_REINSERT(name, type, attr);
>> +#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)                    \
>> +       attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
>> +#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)                    \
>> +       attr void name##_RB_REMOVE_COLOR(struct name *, struct type *)
>> +#define RB_PROTOTYPE_REMOVE(name, type, attr)                          \
>> +       attr struct type *name##_RB_REMOVE(struct name *, struct type *)
>> +#define RB_PROTOTYPE_INSERT(name, type, attr)                          \
>> +       attr struct type *name##_RB_INSERT(struct name *, struct type *)
>> +#define RB_PROTOTYPE_FIND(name, type, attr)                            \
>> +       attr struct type *name##_RB_FIND(struct name *, struct type *)
>> +#define RB_PROTOTYPE_NFIND(name, type, attr)                           \
>> +       attr struct type *name##_RB_NFIND(struct name *, struct type *)
>> +#define RB_PROTOTYPE_NEXT(name, type, attr)                            \
>> +       attr struct type *name##_RB_NEXT(struct type *)
>> +#define RB_PROTOTYPE_PREV(name, type, attr)                            \
>> +       attr struct type *name##_RB_PREV(struct type *)
>> +#define RB_PROTOTYPE_MINMAX(name, type, attr)                          \
>> +       attr struct type *name##_RB_MINMAX(struct name *, int)
>> +#define RB_PROTOTYPE_REINSERT(name, type, attr)                        \
>> +       attr struct type *name##_RB_REINSERT(struct name *, struct type *)
>> +
>> +/* Main rb operation.
>> + * Moves node close to the key of elm to top
>> + */
>> +#define        RB_GENERATE(name, type, field, cmp)
>> \
>> +       RB_GENERATE_INTERNAL(name, type, field, cmp,)
>> +#define        RB_GENERATE_STATIC(name, type, field, cmp)
>> \
>> +       RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
>> +#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)             \
>> +       RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
>> +       RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
>> +       RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
>> +       RB_GENERATE_REMOVE(name, type, field, attr)                     \
>> +       RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
>> +       RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
>> +       RB_GENERATE_NEXT(name, type, field, attr)                       \
>> +       RB_GENERATE_PREV(name, type, field, attr)                       \
>> +       RB_GENERATE_MINMAX(name, type, field, attr)                     \
>> +       RB_GENERATE_REINSERT(name, type, field, cmp, attr)
>> +
>> +
>> +#define RB_GENERATE_INSERT_COLOR(name, type, field, attr)              \
>> +attr void                                                              \
>> +name##_RB_INSERT_COLOR(struct name *head, struct type *elm)            \
>> +{                                                                      \
>> +       struct type *parent, *gparent, *tmp;                            \
>> +       while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) {     \
>> +               gparent = RB_PARENT(parent, field);                     \
>> +               if (parent == RB_LEFT(gparent, field)) {                \
>> +                       tmp = RB_RIGHT(gparent, field);                 \
>> +                       if (RB_ISRED(tmp, field)) {                     \
>> +                               RB_COLOR(tmp, field) = RB_BLACK;        \
>> +                               RB_SET_BLACKRED(parent, gparent, field);\
>> +                               elm = gparent;                          \
>> +                               continue;                               \
>> +                       }                                               \
>> +                       if (RB_RIGHT(parent, field) == elm) {           \
>> +                               RB_PARENT_ROTATE_LEFT(gparent, parent,  \
>> +                                   tmp, field);                        \
>> +                               tmp = parent;                           \
>> +                               parent = elm;                           \
>> +                               elm = tmp;                              \
>> +                       }                                               \
>> +                       RB_SET_BLACKRED(parent, gparent, field);        \
>> +                       RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
>> +               } else {                                                \
>> +                       tmp = RB_LEFT(gparent, field);                  \
>> +                       if (RB_ISRED(tmp, field)) {                     \
>> +                               RB_COLOR(tmp, field) = RB_BLACK;        \
>> +                               RB_SET_BLACKRED(parent, gparent, field);\
>> +                               elm = gparent;                          \
>> +                               continue;                               \
>> +                       }                                               \
>> +                       if (RB_LEFT(parent, field) == elm) {            \
>> +                               RB_PARENT_ROTATE_RIGHT(gparent, parent, \
>> +                                   tmp, field);                        \
>> +                               tmp = parent;                           \
>> +                               parent = elm;                           \
>> +                               elm = tmp;                              \
>> +                       }                                               \
>> +                       RB_SET_BLACKRED(parent, gparent, field);        \
>> +                       RB_ROTATE_LEFT(head, gparent, tmp, field);      \
>> +               }                                                       \
>> +       }                                                               \
>> +       RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
>> +}
>> +
>> +#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)              \
>> +attr void                                                              \
>> +name##_RB_REMOVE_COLOR(struct name *head, struct type *parent)         \
>> +{                                                                      \
>> +       struct type *elm, *tmp;                                         \
>> +       elm = NULL;                                                     \
>> +       do {                                                            \
>> +               if (RB_LEFT(parent, field) == elm) {                    \
>> +                       tmp = RB_RIGHT(parent, field);                  \
>> +                       if (RB_COLOR(tmp, field) == RB_RED) {           \
>> +                               RB_SET_BLACKRED(tmp, parent, field);    \
>> +                               RB_RED_ROTATE_LEFT(head, parent, tmp, field); \
>> +                               tmp = RB_RIGHT(parent, field);          \
>> +                       }                                               \
>> +                       if (RB_ISRED(RB_RIGHT(tmp, field), field))      \
>> +                               RB_COLOR(RB_RIGHT(tmp, field), field) =
>> RB_BLACK; \
>> +                       else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \
>> +                               struct type *oleft;                     \
>> +                               RB_PARENT_ROTATE_RIGHT(parent, tmp,     \
>> +                                   oleft, field);                      \
>> +                               RB_COLOR(oleft, field) = RB_BLACK;      \
>> +                               tmp = oleft;                            \
>> +                       } else {                                        \
>> +                               RB_COLOR(tmp, field) = RB_RED;          \
>> +                               elm = parent;                           \
>> +                               parent = RB_PARENT(elm, field);         \
>> +                               continue;                               \
>> +                       }                                               \
>> +                       RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
>> +                       RB_COLOR(parent, field) = RB_BLACK;             \
>> +                       RB_ROTATE_LEFT(head, parent, tmp, field);       \
>> +                       elm = RB_ROOT(head);                            \
>> +                       break;                                          \
>> +               } else {                                                \
>> +                       tmp = RB_LEFT(parent, field);                   \
>> +                       if (RB_COLOR(tmp, field) == RB_RED) {           \
>> +                               RB_SET_BLACKRED(tmp, parent, field);    \
>> +                               RB_RED_ROTATE_RIGHT(head, parent, tmp, field); \
>> +                               tmp = RB_LEFT(parent, field);           \
>> +                       }                                               \
>> +                       if (RB_ISRED(RB_LEFT(tmp, field), field))       \
>> +                               RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;
>> \
>> +                       else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \
>> +                               struct type *oright;                    \
>> +                               RB_PARENT_ROTATE_LEFT(parent, tmp,      \
>> +                                   oright, field);                     \
>> +                               RB_COLOR(oright, field) = RB_BLACK;     \
>> +                               tmp = oright;                           \
>> +                       } else {                                        \
>> +                               RB_COLOR(tmp, field) = RB_RED;          \
>> +                               elm = parent;                           \
>> +                               parent = RB_PARENT(elm, field);         \
>> +                               continue;                               \
>> +                       }                                               \
>> +                       RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
>> +                       RB_COLOR(parent, field) = RB_BLACK;             \
>> +                       RB_ROTATE_RIGHT(head, parent, tmp, field);      \
>> +                       elm = RB_ROOT(head);                            \
>> +                       break;                                          \
>> +               }                                                       \
>> +       } while (RB_COLOR(elm, field) == RB_BLACK && parent != NULL);   \
>> +       RB_COLOR(elm, field) = RB_BLACK;                                \
>> +}
>> +
>> +#define RB_GENERATE_REMOVE(name, type, field, attr)                    \
>> +attr struct type *                                                     \
>> +name##_RB_REMOVE(struct name *head, struct type *elm)                  \
>> +{                                                                      \
>> +       struct type *child, *old, *parent, *right;                      \
>> +       int color;                                                      \
>> +                                                                       \
>> +       old = elm;                                                      \
>> +       parent = RB_PARENT(elm, field);                                 \
>> +       right = RB_RIGHT(elm, field);                                   \
>> +       color = RB_COLOR(elm, field);                                   \
>> +       if (RB_LEFT(elm, field) == NULL)                                \
>> +               elm = child = right;                                    \
>> +       else if (right == NULL)                                         \
>> +               elm = child = RB_LEFT(elm, field);                      \
>> +       else {                                                          \
>> +               if ((child = RB_LEFT(right, field)) == NULL) {          \
>> +                       child = RB_RIGHT(right, field);                 \
>> +                       RB_RIGHT(old, field) = child;                   \
>> +                       parent = elm = right;                           \
>> +               } else {                                                \
>> +                       do                                              \
>> +                               elm = child;                            \
>> +                       while ((child = RB_LEFT(elm, field)) != NULL);  \
>> +                       child = RB_RIGHT(elm, field);                   \
>> +                       parent = RB_PARENT(elm, field);                 \
>> +                       RB_LEFT(parent, field) = child;                 \
>> +                       RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \
>> +               }                                                       \
>> +               RB_SET_PARENT(RB_LEFT(old, field), elm, field);         \
>> +               color = RB_COLOR(elm, field);                           \
>> +               elm->field = old->field;                                \
>> +       }                                                               \
>> +       RB_SWAP_CHILD(head, old, elm, field);                           \
>> +       if (child != NULL) {                                            \
>> +               RB_SET_PARENT(child, parent, field);                    \
>> +               RB_COLOR(child, field) = RB_BLACK;                      \
>> +       } else if (color != RB_RED && parent != NULL)                   \
>> +               name##_RB_REMOVE_COLOR(head, parent);                   \
>> +       while (parent != NULL) {                                        \
>> +               RB_AUGMENT(parent);                                     \
>> +               parent = RB_PARENT(parent, field);                      \
>> +       }                                                               \
>> +       return (old);                                                   \
>> +}
>> +
>> +#define RB_GENERATE_INSERT(name, type, field, cmp, attr)               \
>> +/* Inserts a node into the RB tree */                                  \
>> +attr struct type *                                                     \
>> +name##_RB_INSERT(struct name *head, struct type *elm)                  \
>> +{                                                                      \
>> +       struct type *tmp;                                               \
>> +       struct type *parent = NULL;                                     \
>> +       int comp = 0;                                                   \
>> +       tmp = RB_ROOT(head);                                            \
>> +       while (tmp) {                                                   \
>> +               parent = tmp;                                           \
>> +               comp = (cmp)(elm, parent);                              \
>> +               if (comp < 0)                                           \
>> +                       tmp = RB_LEFT(tmp, field);                      \
>> +               else if (comp > 0)                                      \
>> +                       tmp = RB_RIGHT(tmp, field);                     \
>> +               else                                                    \
>> +                       return (tmp);                                   \
>> +       }                                                               \
>> +       RB_SET(elm, parent, field);                                     \
>> +       if (parent != NULL) {                                           \
>> +               if (comp < 0)                                           \
>> +                       RB_LEFT(parent, field) = elm;                   \
>> +               else                                                    \
>> +                       RB_RIGHT(parent, field) = elm;                  \
>> +       } else                                                          \
>> +               RB_ROOT(head) = elm;                                    \
>> +       name##_RB_INSERT_COLOR(head, elm);                              \
>> +       while (elm != NULL) {                                           \
>> +               RB_AUGMENT(elm);                                        \
>> +               elm = RB_PARENT(elm, field);                            \
>> +       }                                                               \
>> +       return (NULL);                                                  \
>> +}
>> +
>> +#define RB_GENERATE_FIND(name, type, field, cmp, attr)                 \
>> +/* Finds the node with the same key as elm */                          \
>> +attr struct type *                                                     \
>> +name##_RB_FIND(struct name *head, struct type *elm)                    \
>> +{                                                                      \
>> +       struct type *tmp = RB_ROOT(head);                               \
>> +       int comp;                                                       \
>> +       while (tmp) {                                                   \
>> +               comp = cmp(elm, tmp);                                   \
>> +               if (comp < 0)                                           \
>> +                       tmp = RB_LEFT(tmp, field);                      \
>> +               else if (comp > 0)                                      \
>> +                       tmp = RB_RIGHT(tmp, field);                     \
>> +               else                                                    \
>> +                       return (tmp);                                   \
>> +       }                                                               \
>> +       return (NULL);                                                  \
>> +}
>> +
>> +#define RB_GENERATE_NFIND(name, type, field, cmp, attr)
>> \
>> +/* Finds the first node greater than or equal to the search key */     \
>> +attr struct type *                                                     \
>> +name##_RB_NFIND(struct name *head, struct type *elm)                   \
>> +{                                                                      \
>> +       struct type *tmp = RB_ROOT(head);                               \
>> +       struct type *res = NULL;                                        \
>> +       int comp;                                                       \
>> +       while (tmp) {                                                   \
>> +               comp = cmp(elm, tmp);                                   \
>> +               if (comp < 0) {                                         \
>> +                       res = tmp;                                      \
>> +                       tmp = RB_LEFT(tmp, field);                      \
>> +               }                                                       \
>> +               else if (comp > 0)                                      \
>> +                       tmp = RB_RIGHT(tmp, field);                     \
>> +               else                                                    \
>> +                       return (tmp);                                   \
>> +       }                                                               \
>> +       return (res);                                                   \
>> +}
>> +
>> +#define RB_GENERATE_NEXT(name, type, field, attr)                      \
>> +/* ARGSUSED */                                                         \
>> +attr struct type *                                                     \
>> +name##_RB_NEXT(struct type *elm)                                       \
>> +{                                                                      \
>> +       if (RB_RIGHT(elm, field)) {                                     \
>> +               elm = RB_RIGHT(elm, field);                             \
>> +               while (RB_LEFT(elm, field))                             \
>> +                       elm = RB_LEFT(elm, field);                      \
>> +       } else {                                                        \
>> +               if (RB_PARENT(elm, field) &&                            \
>> +                   (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
>> +                       elm = RB_PARENT(elm, field);                    \
>> +               else {                                                  \
>> +                       while (RB_PARENT(elm, field) &&                 \
>> +                           (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
>> +                               elm = RB_PARENT(elm, field);            \
>> +                       elm = RB_PARENT(elm, field);                    \
>> +               }                                                       \
>> +       }                                                               \
>> +       return (elm);                                                   \
>> +}
>> +
>> +#define RB_GENERATE_PREV(name, type, field, attr)                      \
>> +/* ARGSUSED */                                                         \
>> +attr struct type *                                                     \
>> +name##_RB_PREV(struct type *elm)                                       \
>> +{                                                                      \
>> +       if (RB_LEFT(elm, field)) {                                      \
>> +               elm = RB_LEFT(elm, field);                              \
>> +               while (RB_RIGHT(elm, field))                            \
>> +                       elm = RB_RIGHT(elm, field);                     \
>> +       } else {                                                        \
>> +               if (RB_PARENT(elm, field) &&                            \
>> +                   (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
>> +                       elm = RB_PARENT(elm, field);                    \
>> +               else {                                                  \
>> +                       while (RB_PARENT(elm, field) &&                 \
>> +                           (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
>> +                               elm = RB_PARENT(elm, field);            \
>> +                       elm = RB_PARENT(elm, field);                    \
>> +               }                                                       \
>> +       }                                                               \
>> +       return (elm);                                                   \
>> +}
>> +
>> +#define RB_GENERATE_MINMAX(name, type, field, attr)                    \
>> +attr struct type *                                                     \
>> +name##_RB_MINMAX(struct name *head, int val)                           \
>> +{                                                                      \
>> +       struct type *tmp = RB_ROOT(head);                               \
>> +       struct type *parent = NULL;                                     \
>> +       while (tmp) {                                                   \
>> +               parent = tmp;                                           \
>> +               if (val < 0)                                            \
>> +                       tmp = RB_LEFT(tmp, field);                      \
>> +               else                                                    \
>> +                       tmp = RB_RIGHT(tmp, field);                     \
>> +       }                                                               \
>> +       return (parent);                                                \
>> +}
>> +
>> +#define        RB_GENERATE_REINSERT(name, type, field, cmp, attr)
>> \
>> +attr struct type *                                                     \
>> +name##_RB_REINSERT(struct name *head, struct type *elm)
>> \
>> +{                                                                      \
>> +       struct type *cmpelm;                                            \
>> +       if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&             \
>> +           cmp(cmpelm, elm) >= 0) ||                                   \
>> +           ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&             \
>> +           cmp(elm, cmpelm) >= 0)) {                                   \
>> +               /* XXXLAS: Remove/insert is heavy handed. */            \
>> +               RB_REMOVE(name, head, elm);                             \
>> +               return (RB_INSERT(name, head, elm));                    \
>> +       }                                                               \
>> +       return (NULL);                                                  \
>> +}                                                                      \
>> +
>> +#define RB_NEGINF      -1
>> +#define RB_INF 1
>> +
>> +#define RB_INSERT(name, x, y)  name##_RB_INSERT(x, y)
>> +#define RB_REMOVE(name, x, y)  name##_RB_REMOVE(x, y)
>> +#define RB_FIND(name, x, y)    name##_RB_FIND(x, y)
>> +#define RB_NFIND(name, x, y)   name##_RB_NFIND(x, y)
>> +#define RB_NEXT(name, x, y)    name##_RB_NEXT(y)
>> +#define RB_PREV(name, x, y)    name##_RB_PREV(y)
>> +#define RB_MIN(name, x)                name##_RB_MINMAX(x, RB_NEGINF)
>> +#define RB_MAX(name, x)                name##_RB_MINMAX(x, RB_INF)
>> +#define RB_REINSERT(name, x, y)        name##_RB_REINSERT(x, y)
>> +
>> +#define RB_FOREACH(x, name, head)                                      \
>> +       for ((x) = RB_MIN(name, head);                                  \
>> +            (x) != NULL;                                               \
>> +            (x) = name##_RB_NEXT(x))
>> +
>> +#define RB_FOREACH_FROM(x, name, y)                                    \
>> +       for ((x) = (y);                                                 \
>> +           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
>> +            (x) = (y))
>> +
>> +#define RB_FOREACH_SAFE(x, name, head, y)                              \
>> +       for ((x) = RB_MIN(name, head);                                  \
>> +           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
>> +            (x) = (y))
>> +
>> +#define RB_FOREACH_REVERSE(x, name, head)                              \
>> +       for ((x) = RB_MAX(name, head);                                  \
>> +            (x) != NULL;                                               \
>> +            (x) = name##_RB_PREV(x))
>> +
>> +#define RB_FOREACH_REVERSE_FROM(x, name, y)                            \
>> +       for ((x) = (y);                                                 \
>> +           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
>> +            (x) = (y))
>> +
>> +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                      \
>> +       for ((x) = RB_MAX(name, head);                                  \
>> +           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
>> +            (x) = (y))
>> +
>> +#endif /* _SYS_TREE_H_ */
>> --
>> 2.24.4
  

On Wed, Jul 17, 2024 at 9:44 AM Sebastian Huber
<sebastian.huber@embedded-brains.de> wrote:
>
> ----- Am 17. Jul 2024 um 16:29 schrieb Gedare Bloom gedare@rtems.org:
>
> > This file should not be added in a shared folder. It was a mistake to
> > put it there in the first place. The problem is that this file is not
> > a standard interface, it is de facto defined by the upstream (FreeBSD)
> > and they do not provide backward compatibility in this file as an API.
>
> The <sys/tree.h> is also present in other BSD systems, for example:
>
> https://man.openbsd.org/tree
>
> https://man.netbsd.org/tree.3
>
For completeness:
https://man.freebsd.org/cgi/man.cgi?query=tree&apropos=0&sektion=0&manpath=FreeBSD+14.1-RELEASE+and+Ports&arch=default&format=html

> Which API incompatibility did you observe? FreeBSD releases may break the Application Binary Interface (ABI), but an Application Programming Interface (API) break would surprise me. If the API was extended, then it would be probably easy to add the new API elements to the Newlib version of <sys/tree.h>.
>
The problem is with how this header uses CPP macros to generate the
functional implementation. The functional implementation differs based
on which header file you include. This has the result that the
implementation is the API, already a questionable design choice, but
worse, if you have multiple versions of sys/tree.h, whichever one gets
included first will determine how the implementation is generated. If
you have inconsistency in the include order, you end up with different
functional implementations of the same names. This arises directly
when one has a tree.h generating rbtrees and a different tree.h
generating rank-balanced trees.

The problem is indicated by compile-time warnings about redefinitions
of CPP macros. These warnings are hiding the fact that completely
different functions can be instantiated depending on which tree.h gets
picked up.

> > As a result, an application built with one version may not be upgraded
> > to a newer version.
> >
> > It's a standalone include file that is not itself used inside of
> > newlib. If someone packaging newlib to distribute wants to provide a
> > specific version, they should do that in their own distribution. It
> > would be impossible to maintain a version of this file that would be
> > capable of making everyone happy, due to the above backward
> > compatibility problems.
> >
> > We discovered this issue exactly when trying to use different versions
> > of libraries from freebsd together with newlib packaged in rtems.
>
> From my point of view the problem is that libbsd uses its own version of <sys/tree.h>. I maintained this file in Newlib for quite a while and monitored the changes in FreeBSD. At the time when FreeBSD changed the implementation to use rank-balanced trees, I made a performance evaluation and didn't see benefits for the priority queue use case. FreeBSD fine tuned their new implementation in the meantime, so the situation may have changed. When you update libbsd to a newer version of FreeBSD you can't blindly accept everything. FreeBSD may optimize for certain use cases which are less important in the context of a supposed to be real-time operating system.
>
> Independent of this, please move on with whatever agenda you have since I have the minority opinion in the RTEMS Project with respect to this topic.
>
> >
> > Gedare
> >
> > On Wed, Jul 17, 2024 at 7:51 AM Joel Sherrill <joel@rtems.org> wrote:
> >>
> >> Reverts 1339af44679aee0895fe311cfad89d38cfc2b919
> >> ---
> >>  newlib/libc/include/sys/tree.h | 864 +++++++++++++++++++++++++++++++++
> >>  1 file changed, 864 insertions(+)
> >>  create mode 100644 newlib/libc/include/sys/tree.h
> >>
> >> diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
> >> new file mode 100644
> >> index 000000000..2d3cec0ec
> >> --- /dev/null
> >> +++ b/newlib/libc/include/sys/tree.h
> >> @@ -0,0 +1,864 @@
> >> +/*     $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
> >> +/*     $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
> >> +/* $FreeBSD: head/sys/sys/tree.h 347360 2019-05-08 18:47:00Z trasz $ */
> >> +
> >> +/*-
> >> + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
> >> + *
> >> + * 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.
> >> + */
> >> +
> >> +#ifndef        _SYS_TREE_H_
> >> +#define        _SYS_TREE_H_
> >> +
> >> +#include <sys/cdefs.h>
> >> +
> >> +/*
> >> + * This file defines data structures for different types of trees:
> >> + * splay trees and red-black trees.
> >> + *
> >> + * A splay tree is a self-organizing data structure.  Every operation
> >> + * on the tree causes a splay to happen.  The splay moves the requested
> >> + * node to the root of the tree and partly rebalances it.
> >> + *
> >> + * This has the benefit that request locality causes faster lookups as
> >> + * the requested nodes move to the top of the tree.  On the other hand,
> >> + * every lookup causes memory writes.
> >> + *
> >> + * The Balance Theorem bounds the total access time for m operations
> >> + * and n inserts on an initially empty tree as O((m + n)lg n).  The
> >> + * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
> >> + *
> >> + * A red-black tree is a binary search tree with the node color as an
> >> + * extra attribute.  It fulfills a set of conditions:
> >> + *     - every search path from the root to a leaf consists of the
> >> + *       same number of black nodes,
> >> + *     - each red node (except for the root) has a black parent,
> >> + *     - each leaf node is black.
> >> + *
> >> + * Every operation on a red-black tree is bounded as O(lg n).
> >> + * The maximum height of a red-black tree is 2lg (n+1).
> >> + */
> >> +
> >> +#define SPLAY_HEAD(name, type)                                         \
> >> +struct name {                                                          \
> >> +       struct type *sph_root; /* root of the tree */                   \
> >> +}
> >> +
> >> +#define SPLAY_INITIALIZER(root)
> >> \
> >> +       { NULL }
> >> +
> >> +#define SPLAY_INIT(root) do {                                          \
> >> +       (root)->sph_root = NULL;                                        \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define SPLAY_ENTRY(type)                                              \
> >> +struct {                                                               \
> >> +       struct type *spe_left; /* left element */                       \
> >> +       struct type *spe_right; /* right element */                     \
> >> +}
> >> +
> >> +#define SPLAY_LEFT(elm, field)         (elm)->field.spe_left
> >> +#define SPLAY_RIGHT(elm, field)                (elm)->field.spe_right
> >> +#define SPLAY_ROOT(head)               (head)->sph_root
> >> +#define SPLAY_EMPTY(head)              (SPLAY_ROOT(head) == NULL)
> >> +
> >> +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
> >> +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                      \
> >> +       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
> >> +       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
> >> +       (head)->sph_root = tmp;                                         \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define SPLAY_ROTATE_LEFT(head, tmp, field) do {                       \
> >> +       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
> >> +       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
> >> +       (head)->sph_root = tmp;                                         \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define SPLAY_LINKLEFT(head, tmp, field) do {                          \
> >> +       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
> >> +       tmp = (head)->sph_root;                                         \
> >> +       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define SPLAY_LINKRIGHT(head, tmp, field) do {                         \
> >> +       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
> >> +       tmp = (head)->sph_root;                                         \
> >> +       (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define SPLAY_ASSEMBLE(head, node, left, right, field) do {            \
> >> +       SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
> >> +       SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
> >> +       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
> >> +       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +/* Generates prototypes and inline functions */
> >> +
> >> +#define SPLAY_PROTOTYPE(name, type, field, cmp)
> >> \
> >> +void name##_SPLAY(struct name *, struct type *);                       \
> >> +void name##_SPLAY_MINMAX(struct name *, int);                          \
> >> +struct type *name##_SPLAY_INSERT(struct name *, struct type *);
> >> \
> >> +struct type *name##_SPLAY_REMOVE(struct name *, struct type *);
> >> \
> >> +                                                                       \
> >> +/* Finds the node with the same key as elm */                          \
> >> +static __unused __inline struct type *                                 \
> >> +name##_SPLAY_FIND(struct name *head, struct type *elm)                 \
> >> +{                                                                      \
> >> +       if (SPLAY_EMPTY(head))                                          \
> >> +               return(NULL);                                           \
> >> +       name##_SPLAY(head, elm);                                        \
> >> +       if ((cmp)(elm, (head)->sph_root) == 0)                          \
> >> +               return (head->sph_root);                                \
> >> +       return (NULL);                                                  \
> >> +}                                                                      \
> >> +                                                                       \
> >> +static __unused __inline struct type *                                 \
> >> +name##_SPLAY_NEXT(struct name *head, struct type *elm)                 \
> >> +{                                                                      \
> >> +       name##_SPLAY(head, elm);                                        \
> >> +       if (SPLAY_RIGHT(elm, field) != NULL) {                          \
> >> +               elm = SPLAY_RIGHT(elm, field);                          \
> >> +               while (SPLAY_LEFT(elm, field) != NULL) {                \
> >> +                       elm = SPLAY_LEFT(elm, field);                   \
> >> +               }                                                       \
> >> +       } else                                                          \
> >> +               elm = NULL;                                             \
> >> +       return (elm);                                                   \
> >> +}                                                                      \
> >> +                                                                       \
> >> +static __unused __inline struct type *                                 \
> >> +name##_SPLAY_MIN_MAX(struct name *head, int val)                       \
> >> +{                                                                      \
> >> +       name##_SPLAY_MINMAX(head, val);                                 \
> >> +        return (SPLAY_ROOT(head));                                     \
> >> +}
> >> +
> >> +/* Main splay operation.
> >> + * Moves node close to the key of elm to top
> >> + */
> >> +#define SPLAY_GENERATE(name, type, field, cmp)                         \
> >> +struct type *                                                          \
> >> +name##_SPLAY_INSERT(struct name *head, struct type *elm)               \
> >> +{                                                                      \
> >> +    if (SPLAY_EMPTY(head)) {                                           \
> >> +           SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
> >> +    } else {                                                           \
> >> +           int __comp;                                                 \
> >> +           name##_SPLAY(head, elm);                                    \
> >> +           __comp = (cmp)(elm, (head)->sph_root);                      \
> >> +           if(__comp < 0) {                                            \
> >> +                   SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root,
> >> field);\
> >> +                   SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
> >> +                   SPLAY_LEFT((head)->sph_root, field) = NULL;         \
> >> +           } else if (__comp > 0) {                                    \
> >> +                   SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root,
> >> field);\
> >> +                   SPLAY_LEFT(elm, field) = (head)->sph_root;          \
> >> +                   SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
> >> +           } else                                                      \
> >> +                   return ((head)->sph_root);                          \
> >> +    }                                                                  \
> >> +    (head)->sph_root = (elm);                                          \
> >> +    return (NULL);                                                     \
> >> +}                                                                      \
> >> +                                                                       \
> >> +struct type *                                                          \
> >> +name##_SPLAY_REMOVE(struct name *head, struct type *elm)               \
> >> +{                                                                      \
> >> +       struct type *__tmp;                                             \
> >> +       if (SPLAY_EMPTY(head))                                          \
> >> +               return (NULL);                                          \
> >> +       name##_SPLAY(head, elm);                                        \
> >> +       if ((cmp)(elm, (head)->sph_root) == 0) {                        \
> >> +               if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
> >> +                       (head)->sph_root = SPLAY_RIGHT((head)->sph_root,
> >> field);\
> >> +               } else {                                                \
> >> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
> >> +                       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
> >> +                       name##_SPLAY(head, elm);                        \
> >> +                       SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
> >> +               }                                                       \
> >> +               return (elm);                                           \
> >> +       }                                                               \
> >> +       return (NULL);                                                  \
> >> +}                                                                      \
> >> +                                                                       \
> >> +void                                                                   \
> >> +name##_SPLAY(struct name *head, struct type *elm)                      \
> >> +{                                                                      \
> >> +       struct type __node, *__left, *__right, *__tmp;                  \
> >> +       int __comp;                                                     \
> >> +\
> >> +       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
> >> +       __left = __right = &__node;                                     \
> >> +\
> >> +       while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
> >> +               if (__comp < 0) {                                       \
> >> +                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
> >> +                       if (__tmp == NULL)                              \
> >> +                               break;                                  \
> >> +                       if ((cmp)(elm, __tmp) < 0){                     \
> >> +                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
> >> +                               if (SPLAY_LEFT((head)->sph_root, field) ==
> >> NULL)\
> >> +                                       break;                          \
> >> +                       }                                               \
> >> +                       SPLAY_LINKLEFT(head, __right, field);           \
> >> +               } else if (__comp > 0) {                                \
> >> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
> >> +                       if (__tmp == NULL)                              \
> >> +                               break;                                  \
> >> +                       if ((cmp)(elm, __tmp) > 0){                     \
> >> +                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
> >> +                               if (SPLAY_RIGHT((head)->sph_root, field) ==
> >> NULL)\
> >> +                                       break;                          \
> >> +                       }                                               \
> >> +                       SPLAY_LINKRIGHT(head, __left, field);           \
> >> +               }                                                       \
> >> +       }                                                               \
> >> +       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
> >> +}                                                                      \
> >> +                                                                       \
> >> +/* Splay with either the minimum or the maximum element
> >> \
> >> + * Used to find minimum or maximum element in tree.                    \
> >> + */                                                                    \
> >> +void name##_SPLAY_MINMAX(struct name *head, int __comp) \
> >> +{                                                                      \
> >> +       struct type __node, *__left, *__right, *__tmp;                  \
> >> +\
> >> +       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
> >> +       __left = __right = &__node;                                     \
> >> +\
> >> +       while (1) {                                                     \
> >> +               if (__comp < 0) {                                       \
> >> +                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
> >> +                       if (__tmp == NULL)                              \
> >> +                               break;                                  \
> >> +                       if (__comp < 0){                                \
> >> +                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
> >> +                               if (SPLAY_LEFT((head)->sph_root, field) ==
> >> NULL)\
> >> +                                       break;                          \
> >> +                       }                                               \
> >> +                       SPLAY_LINKLEFT(head, __right, field);           \
> >> +               } else if (__comp > 0) {                                \
> >> +                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
> >> +                       if (__tmp == NULL)                              \
> >> +                               break;                                  \
> >> +                       if (__comp > 0) {                               \
> >> +                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
> >> +                               if (SPLAY_RIGHT((head)->sph_root, field) ==
> >> NULL)\
> >> +                                       break;                          \
> >> +                       }                                               \
> >> +                       SPLAY_LINKRIGHT(head, __left, field);           \
> >> +               }                                                       \
> >> +       }                                                               \
> >> +       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
> >> +}
> >> +
> >> +#define SPLAY_NEGINF   -1
> >> +#define SPLAY_INF      1
> >> +
> >> +#define SPLAY_INSERT(name, x, y)       name##_SPLAY_INSERT(x, y)
> >> +#define SPLAY_REMOVE(name, x, y)       name##_SPLAY_REMOVE(x, y)
> >> +#define SPLAY_FIND(name, x, y)         name##_SPLAY_FIND(x, y)
> >> +#define SPLAY_NEXT(name, x, y)         name##_SPLAY_NEXT(x, y)
> >> +#define SPLAY_MIN(name, x)             (SPLAY_EMPTY(x) ? NULL  \
> >> +                                       : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
> >> +#define SPLAY_MAX(name, x)             (SPLAY_EMPTY(x) ? NULL  \
> >> +                                       : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
> >> +
> >> +#define SPLAY_FOREACH(x, name, head)                                   \
> >> +       for ((x) = SPLAY_MIN(name, head);                               \
> >> +            (x) != NULL;                                               \
> >> +            (x) = SPLAY_NEXT(name, head, x))
> >> +
> >> +/* Macros that define a red-black tree */
> >> +#define RB_HEAD(name, type)                                            \
> >> +struct name {                                                          \
> >> +       struct type *rbh_root; /* root of the tree */                   \
> >> +}
> >> +
> >> +#define RB_INITIALIZER(root)                                           \
> >> +       { NULL }
> >> +
> >> +#define RB_INIT(root) do {                                             \
> >> +       (root)->rbh_root = NULL;                                        \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define RB_BLACK       0
> >> +#define RB_RED         1
> >> +#define RB_ENTRY(type)                                                 \
> >> +struct {                                                               \
> >> +       struct type *rbe_left;          /* left element */              \
> >> +       struct type *rbe_right;         /* right element */             \
> >> +       struct type *rbe_parent;        /* parent element */            \
> >> +       int rbe_color;                  /* node color */                \
> >> +}
> >> +
> >> +#define RB_LEFT(elm, field)            (elm)->field.rbe_left
> >> +#define RB_RIGHT(elm, field)           (elm)->field.rbe_right
> >> +#define RB_PARENT(elm, field)          (elm)->field.rbe_parent
> >> +#define RB_COLOR(elm, field)           (elm)->field.rbe_color
> >> +#define RB_ISRED(elm, field)           ((elm) != NULL && RB_COLOR(elm, field)
> >> == RB_RED)
> >> +#define RB_ROOT(head)                  (head)->rbh_root
> >> +#define RB_EMPTY(head)                 (RB_ROOT(head) == NULL)
> >> +
> >> +#define RB_SET_PARENT(dst, src, field) do {                            \
> >> +       RB_PARENT(dst, field) = src;                                    \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define RB_SET(elm, parent, field) do {
> >> \
> >> +       RB_SET_PARENT(elm, parent, field);                              \
> >> +       RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
> >> +       RB_COLOR(elm, field) = RB_RED;                                  \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define RB_SET_BLACKRED(black, red, field) do {
> >> \
> >> +       RB_COLOR(black, field) = RB_BLACK;                              \
> >> +       RB_COLOR(red, field) = RB_RED;                                  \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +/*
> >> + * Something to be invoked in a loop at the root of every modified subtree,
> >> + * from the bottom up to the root, to update augmented node data.
> >> + */
> >> +#ifndef RB_AUGMENT
> >> +#define RB_AUGMENT(x)  break
> >> +#endif
> >> +
> >> +#define RB_SWAP_CHILD(head, out, in, field) do {                       \
> >> +       if (RB_PARENT(out, field) == NULL)                              \
> >> +               RB_ROOT(head) = (in);                                   \
> >> +       else if ((out) == RB_LEFT(RB_PARENT(out, field), field))        \
> >> +               RB_LEFT(RB_PARENT(out, field), field) = (in);           \
> >> +       else                                                            \
> >> +               RB_RIGHT(RB_PARENT(out, field), field) = (in);          \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define RB_ROTATE_LEFT(head, elm, tmp, field) do {                     \
> >> +       (tmp) = RB_RIGHT(elm, field);                                   \
> >> +       if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
> >> +               RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);        \
> >> +       }                                                               \
> >> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> >> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> >> +       RB_LEFT(tmp, field) = (elm);                                    \
> >> +       RB_SET_PARENT(elm, tmp, field);                                 \
> >> +       RB_AUGMENT(elm);                                                \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                    \
> >> +       (tmp) = RB_LEFT(elm, field);                                    \
> >> +       if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
> >> +               RB_SET_PARENT(RB_LEFT(elm, field), elm, field);         \
> >> +       }                                                               \
> >> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> >> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> >> +       RB_RIGHT(tmp, field) = (elm);                                   \
> >> +       RB_SET_PARENT(elm, tmp, field);                                 \
> >> +       RB_AUGMENT(elm);                                                \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +/*
> >> + * The RB_PARENT_ROTATE_LEFT() and RB_PARENT_ROTATE_RIGHT() rotations are
> >> + * specialized versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be
> >> + * used if the parent node exists and the direction of the child element is
> >> + * known.
> >> + */
> >> +
> >> +#define RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do {           \
> >> +       (tmp) = RB_RIGHT(left, field);                                  \
> >> +       if ((RB_RIGHT(left, field) = RB_LEFT(tmp, field)) != NULL) {    \
> >> +               RB_SET_PARENT(RB_RIGHT(left, field), left, field);      \
> >> +       }                                                               \
> >> +       RB_SET_PARENT(tmp, parent, field);                              \
> >> +       RB_LEFT(parent, field) = (tmp);                                 \
> >> +       RB_LEFT(tmp, field) = (left);                                   \
> >> +       RB_SET_PARENT(left, tmp, field);                                \
> >> +       RB_AUGMENT(left);                                               \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do {         \
> >> +       (tmp) = RB_LEFT(right, field);                                  \
> >> +       if ((RB_LEFT(right, field) = RB_RIGHT(tmp, field)) != NULL) {   \
> >> +               RB_SET_PARENT(RB_LEFT(right, field), right, field);     \
> >> +       }                                                               \
> >> +       RB_SET_PARENT(tmp, parent, field);                              \
> >> +       RB_RIGHT(parent, field) = (tmp);                                \
> >> +       RB_RIGHT(tmp, field) = (right);                                 \
> >> +       RB_SET_PARENT(right, tmp, field);                               \
> >> +       RB_AUGMENT(right);                                              \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +/*
> >> + * The RB_RED_ROTATE_LEFT() and RB_RED_ROTATE_RIGHT() rotations are specialized
> >> + * versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be used if we
> >> + * rotate an element with a red child which has a black sibling.  Such a red
> >> + * node must have at least two child nodes so that the following red-black tree
> >> + * invariant is fulfilled:
> >> + *
> >> + *  Every path from a given node to any of its descendant NULL nodes goes
> >> + *  through the same number of black nodes.
> >> + *
> >> + *  elm (could be the root)
> >> + *    /      \
> >> + * BLACK   RED (left or right child)
> >> + *          /   \
> >> + *       BLACK  BLACK
> >> + */
> >> +
> >> +#define RB_RED_ROTATE_LEFT(head, elm, tmp, field) do {                 \
> >> +       (tmp) = RB_RIGHT(elm, field);                                   \
> >> +       RB_RIGHT(elm, field) = RB_LEFT(tmp, field);                     \
> >> +       RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);                \
> >> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> >> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> >> +       RB_LEFT(tmp, field) = (elm);                                    \
> >> +       RB_SET_PARENT(elm, tmp, field);                                 \
> >> +       RB_AUGMENT(elm);                                                \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +#define RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do {
> >> \
> >> +       (tmp) = RB_LEFT(elm, field);                                    \
> >> +       RB_LEFT(elm, field) = RB_RIGHT(tmp, field);                     \
> >> +       RB_SET_PARENT(RB_LEFT(elm, field), elm, field);                 \
> >> +       RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
> >> +       RB_SWAP_CHILD(head, elm, tmp, field);                           \
> >> +       RB_RIGHT(tmp, field) = (elm);                                   \
> >> +       RB_SET_PARENT(elm, tmp, field);                                 \
> >> +       RB_AUGMENT(elm);                                                \
> >> +} while (/*CONSTCOND*/ 0)
> >> +
> >> +/* Generates prototypes and inline functions */
> >> +#define        RB_PROTOTYPE(name, type, field, cmp)
> >> \
> >> +       RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
> >> +#define        RB_PROTOTYPE_STATIC(name, type, field, cmp)
> >> \
> >> +       RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
> >> +#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)            \
> >> +       RB_PROTOTYPE_INSERT_COLOR(name, type, attr);                    \
> >> +       RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);                    \
> >> +       RB_PROTOTYPE_INSERT(name, type, attr);                          \
> >> +       RB_PROTOTYPE_REMOVE(name, type, attr);                          \
> >> +       RB_PROTOTYPE_FIND(name, type, attr);                            \
> >> +       RB_PROTOTYPE_NFIND(name, type, attr);                           \
> >> +       RB_PROTOTYPE_NEXT(name, type, attr);                            \
> >> +       RB_PROTOTYPE_PREV(name, type, attr);                            \
> >> +       RB_PROTOTYPE_MINMAX(name, type, attr);                          \
> >> +       RB_PROTOTYPE_REINSERT(name, type, attr);
> >> +#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)                    \
> >> +       attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
> >> +#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)                    \
> >> +       attr void name##_RB_REMOVE_COLOR(struct name *, struct type *)
> >> +#define RB_PROTOTYPE_REMOVE(name, type, attr)                          \
> >> +       attr struct type *name##_RB_REMOVE(struct name *, struct type *)
> >> +#define RB_PROTOTYPE_INSERT(name, type, attr)                          \
> >> +       attr struct type *name##_RB_INSERT(struct name *, struct type *)
> >> +#define RB_PROTOTYPE_FIND(name, type, attr)                            \
> >> +       attr struct type *name##_RB_FIND(struct name *, struct type *)
> >> +#define RB_PROTOTYPE_NFIND(name, type, attr)                           \
> >> +       attr struct type *name##_RB_NFIND(struct name *, struct type *)
> >> +#define RB_PROTOTYPE_NEXT(name, type, attr)                            \
> >> +       attr struct type *name##_RB_NEXT(struct type *)
> >> +#define RB_PROTOTYPE_PREV(name, type, attr)                            \
> >> +       attr struct type *name##_RB_PREV(struct type *)
> >> +#define RB_PROTOTYPE_MINMAX(name, type, attr)                          \
> >> +       attr struct type *name##_RB_MINMAX(struct name *, int)
> >> +#define RB_PROTOTYPE_REINSERT(name, type, attr)                        \
> >> +       attr struct type *name##_RB_REINSERT(struct name *, struct type *)
> >> +
> >> +/* Main rb operation.
> >> + * Moves node close to the key of elm to top
> >> + */
> >> +#define        RB_GENERATE(name, type, field, cmp)
> >> \
> >> +       RB_GENERATE_INTERNAL(name, type, field, cmp,)
> >> +#define        RB_GENERATE_STATIC(name, type, field, cmp)
> >> \
> >> +       RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
> >> +#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)             \
> >> +       RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
> >> +       RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
> >> +       RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
> >> +       RB_GENERATE_REMOVE(name, type, field, attr)                     \
> >> +       RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
> >> +       RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
> >> +       RB_GENERATE_NEXT(name, type, field, attr)                       \
> >> +       RB_GENERATE_PREV(name, type, field, attr)                       \
> >> +       RB_GENERATE_MINMAX(name, type, field, attr)                     \
> >> +       RB_GENERATE_REINSERT(name, type, field, cmp, attr)
> >> +
> >> +
> >> +#define RB_GENERATE_INSERT_COLOR(name, type, field, attr)              \
> >> +attr void                                                              \
> >> +name##_RB_INSERT_COLOR(struct name *head, struct type *elm)            \
> >> +{                                                                      \
> >> +       struct type *parent, *gparent, *tmp;                            \
> >> +       while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) {     \
> >> +               gparent = RB_PARENT(parent, field);                     \
> >> +               if (parent == RB_LEFT(gparent, field)) {                \
> >> +                       tmp = RB_RIGHT(gparent, field);                 \
> >> +                       if (RB_ISRED(tmp, field)) {                     \
> >> +                               RB_COLOR(tmp, field) = RB_BLACK;        \
> >> +                               RB_SET_BLACKRED(parent, gparent, field);\
> >> +                               elm = gparent;                          \
> >> +                               continue;                               \
> >> +                       }                                               \
> >> +                       if (RB_RIGHT(parent, field) == elm) {           \
> >> +                               RB_PARENT_ROTATE_LEFT(gparent, parent,  \
> >> +                                   tmp, field);                        \
> >> +                               tmp = parent;                           \
> >> +                               parent = elm;                           \
> >> +                               elm = tmp;                              \
> >> +                       }                                               \
> >> +                       RB_SET_BLACKRED(parent, gparent, field);        \
> >> +                       RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
> >> +               } else {                                                \
> >> +                       tmp = RB_LEFT(gparent, field);                  \
> >> +                       if (RB_ISRED(tmp, field)) {                     \
> >> +                               RB_COLOR(tmp, field) = RB_BLACK;        \
> >> +                               RB_SET_BLACKRED(parent, gparent, field);\
> >> +                               elm = gparent;                          \
> >> +                               continue;                               \
> >> +                       }                                               \
> >> +                       if (RB_LEFT(parent, field) == elm) {            \
> >> +                               RB_PARENT_ROTATE_RIGHT(gparent, parent, \
> >> +                                   tmp, field);                        \
> >> +                               tmp = parent;                           \
> >> +                               parent = elm;                           \
> >> +                               elm = tmp;                              \
> >> +                       }                                               \
> >> +                       RB_SET_BLACKRED(parent, gparent, field);        \
> >> +                       RB_ROTATE_LEFT(head, gparent, tmp, field);      \
> >> +               }                                                       \
> >> +       }                                                               \
> >> +       RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
> >> +}
> >> +
> >> +#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)              \
> >> +attr void                                                              \
> >> +name##_RB_REMOVE_COLOR(struct name *head, struct type *parent)         \
> >> +{                                                                      \
> >> +       struct type *elm, *tmp;                                         \
> >> +       elm = NULL;                                                     \
> >> +       do {                                                            \
> >> +               if (RB_LEFT(parent, field) == elm) {                    \
> >> +                       tmp = RB_RIGHT(parent, field);                  \
> >> +                       if (RB_COLOR(tmp, field) == RB_RED) {           \
> >> +                               RB_SET_BLACKRED(tmp, parent, field);    \
> >> +                               RB_RED_ROTATE_LEFT(head, parent, tmp, field); \
> >> +                               tmp = RB_RIGHT(parent, field);          \
> >> +                       }                                               \
> >> +                       if (RB_ISRED(RB_RIGHT(tmp, field), field))      \
> >> +                               RB_COLOR(RB_RIGHT(tmp, field), field) =
> >> RB_BLACK; \
> >> +                       else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \
> >> +                               struct type *oleft;                     \
> >> +                               RB_PARENT_ROTATE_RIGHT(parent, tmp,     \
> >> +                                   oleft, field);                      \
> >> +                               RB_COLOR(oleft, field) = RB_BLACK;      \
> >> +                               tmp = oleft;                            \
> >> +                       } else {                                        \
> >> +                               RB_COLOR(tmp, field) = RB_RED;          \
> >> +                               elm = parent;                           \
> >> +                               parent = RB_PARENT(elm, field);         \
> >> +                               continue;                               \
> >> +                       }                                               \
> >> +                       RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
> >> +                       RB_COLOR(parent, field) = RB_BLACK;             \
> >> +                       RB_ROTATE_LEFT(head, parent, tmp, field);       \
> >> +                       elm = RB_ROOT(head);                            \
> >> +                       break;                                          \
> >> +               } else {                                                \
> >> +                       tmp = RB_LEFT(parent, field);                   \
> >> +                       if (RB_COLOR(tmp, field) == RB_RED) {           \
> >> +                               RB_SET_BLACKRED(tmp, parent, field);    \
> >> +                               RB_RED_ROTATE_RIGHT(head, parent, tmp, field); \
> >> +                               tmp = RB_LEFT(parent, field);           \
> >> +                       }                                               \
> >> +                       if (RB_ISRED(RB_LEFT(tmp, field), field))       \
> >> +                               RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;
> >> \
> >> +                       else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \
> >> +                               struct type *oright;                    \
> >> +                               RB_PARENT_ROTATE_LEFT(parent, tmp,      \
> >> +                                   oright, field);                     \
> >> +                               RB_COLOR(oright, field) = RB_BLACK;     \
> >> +                               tmp = oright;                           \
> >> +                       } else {                                        \
> >> +                               RB_COLOR(tmp, field) = RB_RED;          \
> >> +                               elm = parent;                           \
> >> +                               parent = RB_PARENT(elm, field);         \
> >> +                               continue;                               \
> >> +                       }                                               \
> >> +                       RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
> >> +                       RB_COLOR(parent, field) = RB_BLACK;             \
> >> +                       RB_ROTATE_RIGHT(head, parent, tmp, field);      \
> >> +                       elm = RB_ROOT(head);                            \
> >> +                       break;                                          \
> >> +               }                                                       \
> >> +       } while (RB_COLOR(elm, field) == RB_BLACK && parent != NULL);   \
> >> +       RB_COLOR(elm, field) = RB_BLACK;                                \
> >> +}
> >> +
> >> +#define RB_GENERATE_REMOVE(name, type, field, attr)                    \
> >> +attr struct type *                                                     \
> >> +name##_RB_REMOVE(struct name *head, struct type *elm)                  \
> >> +{                                                                      \
> >> +       struct type *child, *old, *parent, *right;                      \
> >> +       int color;                                                      \
> >> +                                                                       \
> >> +       old = elm;                                                      \
> >> +       parent = RB_PARENT(elm, field);                                 \
> >> +       right = RB_RIGHT(elm, field);                                   \
> >> +       color = RB_COLOR(elm, field);                                   \
> >> +       if (RB_LEFT(elm, field) == NULL)                                \
> >> +               elm = child = right;                                    \
> >> +       else if (right == NULL)                                         \
> >> +               elm = child = RB_LEFT(elm, field);                      \
> >> +       else {                                                          \
> >> +               if ((child = RB_LEFT(right, field)) == NULL) {          \
> >> +                       child = RB_RIGHT(right, field);                 \
> >> +                       RB_RIGHT(old, field) = child;                   \
> >> +                       parent = elm = right;                           \
> >> +               } else {                                                \
> >> +                       do                                              \
> >> +                               elm = child;                            \
> >> +                       while ((child = RB_LEFT(elm, field)) != NULL);  \
> >> +                       child = RB_RIGHT(elm, field);                   \
> >> +                       parent = RB_PARENT(elm, field);                 \
> >> +                       RB_LEFT(parent, field) = child;                 \
> >> +                       RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \
> >> +               }                                                       \
> >> +               RB_SET_PARENT(RB_LEFT(old, field), elm, field);         \
> >> +               color = RB_COLOR(elm, field);                           \
> >> +               elm->field = old->field;                                \
> >> +       }                                                               \
> >> +       RB_SWAP_CHILD(head, old, elm, field);                           \
> >> +       if (child != NULL) {                                            \
> >> +               RB_SET_PARENT(child, parent, field);                    \
> >> +               RB_COLOR(child, field) = RB_BLACK;                      \
> >> +       } else if (color != RB_RED && parent != NULL)                   \
> >> +               name##_RB_REMOVE_COLOR(head, parent);                   \
> >> +       while (parent != NULL) {                                        \
> >> +               RB_AUGMENT(parent);                                     \
> >> +               parent = RB_PARENT(parent, field);                      \
> >> +       }                                                               \
> >> +       return (old);                                                   \
> >> +}
> >> +
> >> +#define RB_GENERATE_INSERT(name, type, field, cmp, attr)               \
> >> +/* Inserts a node into the RB tree */                                  \
> >> +attr struct type *                                                     \
> >> +name##_RB_INSERT(struct name *head, struct type *elm)                  \
> >> +{                                                                      \
> >> +       struct type *tmp;                                               \
> >> +       struct type *parent = NULL;                                     \
> >> +       int comp = 0;                                                   \
> >> +       tmp = RB_ROOT(head);                                            \
> >> +       while (tmp) {                                                   \
> >> +               parent = tmp;                                           \
> >> +               comp = (cmp)(elm, parent);                              \
> >> +               if (comp < 0)                                           \
> >> +                       tmp = RB_LEFT(tmp, field);                      \
> >> +               else if (comp > 0)                                      \
> >> +                       tmp = RB_RIGHT(tmp, field);                     \
> >> +               else                                                    \
> >> +                       return (tmp);                                   \
> >> +       }                                                               \
> >> +       RB_SET(elm, parent, field);                                     \
> >> +       if (parent != NULL) {                                           \
> >> +               if (comp < 0)                                           \
> >> +                       RB_LEFT(parent, field) = elm;                   \
> >> +               else                                                    \
> >> +                       RB_RIGHT(parent, field) = elm;                  \
> >> +       } else                                                          \
> >> +               RB_ROOT(head) = elm;                                    \
> >> +       name##_RB_INSERT_COLOR(head, elm);                              \
> >> +       while (elm != NULL) {                                           \
> >> +               RB_AUGMENT(elm);                                        \
> >> +               elm = RB_PARENT(elm, field);                            \
> >> +       }                                                               \
> >> +       return (NULL);                                                  \
> >> +}
> >> +
> >> +#define RB_GENERATE_FIND(name, type, field, cmp, attr)                 \
> >> +/* Finds the node with the same key as elm */                          \
> >> +attr struct type *                                                     \
> >> +name##_RB_FIND(struct name *head, struct type *elm)                    \
> >> +{                                                                      \
> >> +       struct type *tmp = RB_ROOT(head);                               \
> >> +       int comp;                                                       \
> >> +       while (tmp) {                                                   \
> >> +               comp = cmp(elm, tmp);                                   \
> >> +               if (comp < 0)                                           \
> >> +                       tmp = RB_LEFT(tmp, field);                      \
> >> +               else if (comp > 0)                                      \
> >> +                       tmp = RB_RIGHT(tmp, field);                     \
> >> +               else                                                    \
> >> +                       return (tmp);                                   \
> >> +       }                                                               \
> >> +       return (NULL);                                                  \
> >> +}
> >> +
> >> +#define RB_GENERATE_NFIND(name, type, field, cmp, attr)
> >> \
> >> +/* Finds the first node greater than or equal to the search key */     \
> >> +attr struct type *                                                     \
> >> +name##_RB_NFIND(struct name *head, struct type *elm)                   \
> >> +{                                                                      \
> >> +       struct type *tmp = RB_ROOT(head);                               \
> >> +       struct type *res = NULL;                                        \
> >> +       int comp;                                                       \
> >> +       while (tmp) {                                                   \
> >> +               comp = cmp(elm, tmp);                                   \
> >> +               if (comp < 0) {                                         \
> >> +                       res = tmp;                                      \
> >> +                       tmp = RB_LEFT(tmp, field);                      \
> >> +               }                                                       \
> >> +               else if (comp > 0)                                      \
> >> +                       tmp = RB_RIGHT(tmp, field);                     \
> >> +               else                                                    \
> >> +                       return (tmp);                                   \
> >> +       }                                                               \
> >> +       return (res);                                                   \
> >> +}
> >> +
> >> +#define RB_GENERATE_NEXT(name, type, field, attr)                      \
> >> +/* ARGSUSED */                                                         \
> >> +attr struct type *                                                     \
> >> +name##_RB_NEXT(struct type *elm)                                       \
> >> +{                                                                      \
> >> +       if (RB_RIGHT(elm, field)) {                                     \
> >> +               elm = RB_RIGHT(elm, field);                             \
> >> +               while (RB_LEFT(elm, field))                             \
> >> +                       elm = RB_LEFT(elm, field);                      \
> >> +       } else {                                                        \
> >> +               if (RB_PARENT(elm, field) &&                            \
> >> +                   (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
> >> +                       elm = RB_PARENT(elm, field);                    \
> >> +               else {                                                  \
> >> +                       while (RB_PARENT(elm, field) &&                 \
> >> +                           (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
> >> +                               elm = RB_PARENT(elm, field);            \
> >> +                       elm = RB_PARENT(elm, field);                    \
> >> +               }                                                       \
> >> +       }                                                               \
> >> +       return (elm);                                                   \
> >> +}
> >> +
> >> +#define RB_GENERATE_PREV(name, type, field, attr)                      \
> >> +/* ARGSUSED */                                                         \
> >> +attr struct type *                                                     \
> >> +name##_RB_PREV(struct type *elm)                                       \
> >> +{                                                                      \
> >> +       if (RB_LEFT(elm, field)) {                                      \
> >> +               elm = RB_LEFT(elm, field);                              \
> >> +               while (RB_RIGHT(elm, field))                            \
> >> +                       elm = RB_RIGHT(elm, field);                     \
> >> +       } else {                                                        \
> >> +               if (RB_PARENT(elm, field) &&                            \
> >> +                   (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
> >> +                       elm = RB_PARENT(elm, field);                    \
> >> +               else {                                                  \
> >> +                       while (RB_PARENT(elm, field) &&                 \
> >> +                           (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
> >> +                               elm = RB_PARENT(elm, field);            \
> >> +                       elm = RB_PARENT(elm, field);                    \
> >> +               }                                                       \
> >> +       }                                                               \
> >> +       return (elm);                                                   \
> >> +}
> >> +
> >> +#define RB_GENERATE_MINMAX(name, type, field, attr)                    \
> >> +attr struct type *                                                     \
> >> +name##_RB_MINMAX(struct name *head, int val)                           \
> >> +{                                                                      \
> >> +       struct type *tmp = RB_ROOT(head);                               \
> >> +       struct type *parent = NULL;                                     \
> >> +       while (tmp) {                                                   \
> >> +               parent = tmp;                                           \
> >> +               if (val < 0)                                            \
> >> +                       tmp = RB_LEFT(tmp, field);                      \
> >> +               else                                                    \
> >> +                       tmp = RB_RIGHT(tmp, field);                     \
> >> +       }                                                               \
> >> +       return (parent);                                                \
> >> +}
> >> +
> >> +#define        RB_GENERATE_REINSERT(name, type, field, cmp, attr)
> >> \
> >> +attr struct type *                                                     \
> >> +name##_RB_REINSERT(struct name *head, struct type *elm)
> >> \
> >> +{                                                                      \
> >> +       struct type *cmpelm;                                            \
> >> +       if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&             \
> >> +           cmp(cmpelm, elm) >= 0) ||                                   \
> >> +           ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&             \
> >> +           cmp(elm, cmpelm) >= 0)) {                                   \
> >> +               /* XXXLAS: Remove/insert is heavy handed. */            \
> >> +               RB_REMOVE(name, head, elm);                             \
> >> +               return (RB_INSERT(name, head, elm));                    \
> >> +       }                                                               \
> >> +       return (NULL);                                                  \
> >> +}                                                                      \
> >> +
> >> +#define RB_NEGINF      -1
> >> +#define RB_INF 1
> >> +
> >> +#define RB_INSERT(name, x, y)  name##_RB_INSERT(x, y)
> >> +#define RB_REMOVE(name, x, y)  name##_RB_REMOVE(x, y)
> >> +#define RB_FIND(name, x, y)    name##_RB_FIND(x, y)
> >> +#define RB_NFIND(name, x, y)   name##_RB_NFIND(x, y)
> >> +#define RB_NEXT(name, x, y)    name##_RB_NEXT(y)
> >> +#define RB_PREV(name, x, y)    name##_RB_PREV(y)
> >> +#define RB_MIN(name, x)                name##_RB_MINMAX(x, RB_NEGINF)
> >> +#define RB_MAX(name, x)                name##_RB_MINMAX(x, RB_INF)
> >> +#define RB_REINSERT(name, x, y)        name##_RB_REINSERT(x, y)
> >> +
> >> +#define RB_FOREACH(x, name, head)                                      \
> >> +       for ((x) = RB_MIN(name, head);                                  \
> >> +            (x) != NULL;                                               \
> >> +            (x) = name##_RB_NEXT(x))
> >> +
> >> +#define RB_FOREACH_FROM(x, name, y)                                    \
> >> +       for ((x) = (y);                                                 \
> >> +           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
> >> +            (x) = (y))
> >> +
> >> +#define RB_FOREACH_SAFE(x, name, head, y)                              \
> >> +       for ((x) = RB_MIN(name, head);                                  \
> >> +           ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
> >> +            (x) = (y))
> >> +
> >> +#define RB_FOREACH_REVERSE(x, name, head)                              \
> >> +       for ((x) = RB_MAX(name, head);                                  \
> >> +            (x) != NULL;                                               \
> >> +            (x) = name##_RB_PREV(x))
> >> +
> >> +#define RB_FOREACH_REVERSE_FROM(x, name, y)                            \
> >> +       for ((x) = (y);                                                 \
> >> +           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
> >> +            (x) = (y))
> >> +
> >> +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                      \
> >> +       for ((x) = RB_MAX(name, head);                                  \
> >> +           ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
> >> +            (x) = (y))
> >> +
> >> +#endif /* _SYS_TREE_H_ */
> >> --
> >> 2.24.4
>
> --
> embedded brains GmbH & Co. KG
> Herr Sebastian HUBER
> Dornierstr. 4
> 82178 Puchheim
> Germany
> email: sebastian.huber@embedded-brains.de
> phone: +49-89-18 94 741 - 16
> fax:   +49-89-18 94 741 - 08
>
> Registergericht: Amtsgericht München
> Registernummer: HRB 157899
> Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
> Unsere Datenschutzerklärung finden Sie hier:
> https://embedded-brains.de/datenschutzerklaerung/
  

----- Am 17. Jul 2024 um 18:57 schrieb Gedare Bloom gedare@rtems.org:

> On Wed, Jul 17, 2024 at 9:44 AM Sebastian Huber
> <sebastian.huber@embedded-brains.de> wrote:
>>
>> ----- Am 17. Jul 2024 um 16:29 schrieb Gedare Bloom gedare@rtems.org:
>>
>> > This file should not be added in a shared folder. It was a mistake to
>> > put it there in the first place. The problem is that this file is not
>> > a standard interface, it is de facto defined by the upstream (FreeBSD)
>> > and they do not provide backward compatibility in this file as an API.
>>
>> The <sys/tree.h> is also present in other BSD systems, for example:
>>
>> https://man.openbsd.org/tree
>>
>> https://man.netbsd.org/tree.3
>>
> For completeness:
> https://man.freebsd.org/cgi/man.cgi?query=tree&apropos=0&sektion=0&manpath=FreeBSD+14.1-RELEASE+and+Ports&arch=default&format=html
> 
>> Which API incompatibility did you observe? FreeBSD releases may break the
>> Application Binary Interface (ABI), but an Application Programming Interface
>> (API) break would surprise me. If the API was extended, then it would be
>> probably easy to add the new API elements to the Newlib version of
>> <sys/tree.h>.
>>
> The problem is with how this header uses CPP macros to generate the
> functional implementation. The functional implementation differs based
> on which header file you include. This has the result that the
> implementation is the API, already a questionable design choice, but
> worse, if you have multiple versions of sys/tree.h, whichever one gets
> included first will determine how the implementation is generated. If
> you have inconsistency in the include order, you end up with different
> functional implementations of the same names. This arises directly
> when one has a tree.h generating rbtrees and a different tree.h
> generating rank-balanced trees.
> 
> The problem is indicated by compile-time warnings about redefinitions
> of CPP macros. These warnings are hiding the fact that completely
> different functions can be instantiated depending on which tree.h gets
> picked up.

Yes, this is true, however, these are Application Binary Interface issues and it happens only if you inconsitently mix differnt versions of <sys/tree.h>. Actually, you can only end up in this mess if the API is compatible.

Again, I would simply remove <sys/tree.h> from libbsd, monitor the FreeBSD changes, and after evaluation update the Newlib version if there are benefits.
  

On Wed, Jul 17, 2024 at 11:14 AM Sebastian Huber
<sebastian.huber@embedded-brains.de> wrote:
>
> ----- Am 17. Jul 2024 um 18:57 schrieb Gedare Bloom gedare@rtems.org:
>
> > On Wed, Jul 17, 2024 at 9:44 AM Sebastian Huber
> > <sebastian.huber@embedded-brains.de> wrote:
> >>
> >> ----- Am 17. Jul 2024 um 16:29 schrieb Gedare Bloom gedare@rtems.org:
> >>
> >> > This file should not be added in a shared folder. It was a mistake to
> >> > put it there in the first place. The problem is that this file is not
> >> > a standard interface, it is de facto defined by the upstream (FreeBSD)
> >> > and they do not provide backward compatibility in this file as an API.
> >>
> >> The <sys/tree.h> is also present in other BSD systems, for example:
> >>
> >> https://man.openbsd.org/tree
> >>
> >> https://man.netbsd.org/tree.3
> >>
> > For completeness:
> > https://man.freebsd.org/cgi/man.cgi?query=tree&apropos=0&sektion=0&manpath=FreeBSD+14.1-RELEASE+and+Ports&arch=default&format=html
> >
> >> Which API incompatibility did you observe? FreeBSD releases may break the
> >> Application Binary Interface (ABI), but an Application Programming Interface
> >> (API) break would surprise me. If the API was extended, then it would be
> >> probably easy to add the new API elements to the Newlib version of
> >> <sys/tree.h>.
> >>
> > The problem is with how this header uses CPP macros to generate the
> > functional implementation. The functional implementation differs based
> > on which header file you include. This has the result that the
> > implementation is the API, already a questionable design choice, but
> > worse, if you have multiple versions of sys/tree.h, whichever one gets
> > included first will determine how the implementation is generated. If
> > you have inconsistency in the include order, you end up with different
> > functional implementations of the same names. This arises directly
> > when one has a tree.h generating rbtrees and a different tree.h
> > generating rank-balanced trees.
> >
> > The problem is indicated by compile-time warnings about redefinitions
> > of CPP macros. These warnings are hiding the fact that completely
> > different functions can be instantiated depending on which tree.h gets
> > picked up.
>
> Yes, this is true, however, these are Application Binary Interface issues and it happens only if you inconsitently mix differnt versions of <sys/tree.h>. Actually, you can only end up in this mess if the API is compatible.
>
OK, that is fair.

> Again, I would simply remove <sys/tree.h> from libbsd, monitor the FreeBSD changes, and after evaluation update the Newlib version if there are benefits.
>
I'm not opposed to this route, but, we now wind up in the same problem
in newlib: cygwin would like to update tree.h, but rtems would like to
keep the rbtree version.

> --
> embedded brains GmbH & Co. KG
> Herr Sebastian HUBER
> Dornierstr. 4
> 82178 Puchheim
> Germany
> email: sebastian.huber@embedded-brains.de
> phone: +49-89-18 94 741 - 16
> fax:   +49-89-18 94 741 - 08
>
> Registergericht: Amtsgericht München
> Registernummer: HRB 157899
> Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
> Unsere Datenschutzerklärung finden Sie hier:
> https://embedded-brains.de/datenschutzerklaerung/
  

On Wed, Jul 17, 2024 at 11:15 AM Gedare Bloom <gedare@rtems.org> wrote:
>
> On Wed, Jul 17, 2024 at 11:14 AM Sebastian Huber
> <sebastian.huber@embedded-brains.de> wrote:
> >
> > ----- Am 17. Jul 2024 um 18:57 schrieb Gedare Bloom gedare@rtems.org:
> >
> > > On Wed, Jul 17, 2024 at 9:44 AM Sebastian Huber
> > > <sebastian.huber@embedded-brains.de> wrote:
> > >>
> > >> ----- Am 17. Jul 2024 um 16:29 schrieb Gedare Bloom gedare@rtems.org:
> > >>
> > >> > This file should not be added in a shared folder. It was a mistake to
> > >> > put it there in the first place. The problem is that this file is not
> > >> > a standard interface, it is de facto defined by the upstream (FreeBSD)
> > >> > and they do not provide backward compatibility in this file as an API.
> > >>
> > >> The <sys/tree.h> is also present in other BSD systems, for example:
> > >>
> > >> https://man.openbsd.org/tree
> > >>
> > >> https://man.netbsd.org/tree.3
> > >>
> > > For completeness:
> > > https://man.freebsd.org/cgi/man.cgi?query=tree&apropos=0&sektion=0&manpath=FreeBSD+14.1-RELEASE+and+Ports&arch=default&format=html
> > >
> > >> Which API incompatibility did you observe? FreeBSD releases may break the
> > >> Application Binary Interface (ABI), but an Application Programming Interface
> > >> (API) break would surprise me. If the API was extended, then it would be
> > >> probably easy to add the new API elements to the Newlib version of
> > >> <sys/tree.h>.
> > >>
> > > The problem is with how this header uses CPP macros to generate the
> > > functional implementation. The functional implementation differs based
> > > on which header file you include. This has the result that the
> > > implementation is the API, already a questionable design choice, but
> > > worse, if you have multiple versions of sys/tree.h, whichever one gets
> > > included first will determine how the implementation is generated. If
> > > you have inconsistency in the include order, you end up with different
> > > functional implementations of the same names. This arises directly
> > > when one has a tree.h generating rbtrees and a different tree.h
> > > generating rank-balanced trees.
> > >
> > > The problem is indicated by compile-time warnings about redefinitions
> > > of CPP macros. These warnings are hiding the fact that completely
> > > different functions can be instantiated depending on which tree.h gets
> > > picked up.
> >
> > Yes, this is true, however, these are Application Binary Interface issues and it happens only if you inconsitently mix differnt versions of <sys/tree.h>. Actually, you can only end up in this mess if the API is compatible.
> >
> OK, that is fair.
>
> > Again, I would simply remove <sys/tree.h> from libbsd, monitor the FreeBSD changes, and after evaluation update the Newlib version if there are benefits.
> >
> I'm not opposed to this route, but, we now wind up in the same problem
> in newlib: cygwin would like to update tree.h, but rtems would like to
> keep the rbtree version.
>
Nevermind, we fixed the RTEMS side. The only remaining problem is when
the application (or library such as libbsd) would prefer a different
version of tree.h. I think we can live with just restoring the tree.h
for now, or someone can provide an updated one also.

On the RTEMS side, someone needs to remove tree.h from our libbsd.

> > --
> > embedded brains GmbH & Co. KG
> > Herr Sebastian HUBER
> > Dornierstr. 4
> > 82178 Puchheim
> > Germany
> > email: sebastian.huber@embedded-brains.de
> > phone: +49-89-18 94 741 - 16
> > fax:   +49-89-18 94 741 - 08
> >
> > Registergericht: Amtsgericht München
> > Registernummer: HRB 157899
> > Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
> > Unsere Datenschutzerklärung finden Sie hier:
> > https://embedded-brains.de/datenschutzerklaerung/
  

On 18/7/2024 3:27 am, Gedare Bloom wrote:
> On Wed, Jul 17, 2024 at 11:15 AM Gedare Bloom <gedare@rtems.org> wrote:
>>
>> On Wed, Jul 17, 2024 at 11:14 AM Sebastian Huber
>> <sebastian.huber@embedded-brains.de> wrote:
>>>
>>> ----- Am 17. Jul 2024 um 18:57 schrieb Gedare Bloom gedare@rtems.org:
>>>
>>>> On Wed, Jul 17, 2024 at 9:44 AM Sebastian Huber
>>>> <sebastian.huber@embedded-brains.de> wrote:
>>>>>
>>>>> ----- Am 17. Jul 2024 um 16:29 schrieb Gedare Bloom gedare@rtems.org:
>>>>>
>>>>>> This file should not be added in a shared folder. It was a mistake to
>>>>>> put it there in the first place. The problem is that this file is not
>>>>>> a standard interface, it is de facto defined by the upstream (FreeBSD)
>>>>>> and they do not provide backward compatibility in this file as an API.
>>>>>
>>>>> The <sys/tree.h> is also present in other BSD systems, for example:
>>>>>
>>>>> https://man.openbsd.org/tree
>>>>>
>>>>> https://man.netbsd.org/tree.3
>>>>>
>>>> For completeness:
>>>> https://man.freebsd.org/cgi/man.cgi?query=tree&apropos=0&sektion=0&manpath=FreeBSD+14.1-RELEASE+and+Ports&arch=default&format=html
>>>>
>>>>> Which API incompatibility did you observe? FreeBSD releases may break the
>>>>> Application Binary Interface (ABI), but an Application Programming Interface
>>>>> (API) break would surprise me. If the API was extended, then it would be
>>>>> probably easy to add the new API elements to the Newlib version of
>>>>> <sys/tree.h>.
>>>>>
>>>> The problem is with how this header uses CPP macros to generate the
>>>> functional implementation. The functional implementation differs based
>>>> on which header file you include. This has the result that the
>>>> implementation is the API, already a questionable design choice, but
>>>> worse, if you have multiple versions of sys/tree.h, whichever one gets
>>>> included first will determine how the implementation is generated. If
>>>> you have inconsistency in the include order, you end up with different
>>>> functional implementations of the same names. This arises directly
>>>> when one has a tree.h generating rbtrees and a different tree.h
>>>> generating rank-balanced trees.
>>>>
>>>> The problem is indicated by compile-time warnings about redefinitions
>>>> of CPP macros. These warnings are hiding the fact that completely
>>>> different functions can be instantiated depending on which tree.h gets
>>>> picked up.
>>>
>>> Yes, this is true, however, these are Application Binary Interface issues and it happens only if you inconsitently mix differnt versions of <sys/tree.h>. Actually, you can only end up in this mess if the API is compatible.
>>>
>> OK, that is fair.
>>
>>> Again, I would simply remove <sys/tree.h> from libbsd, monitor the FreeBSD changes, and after evaluation update the Newlib version if there are benefits.
>>>
>> I'm not opposed to this route, but, we now wind up in the same problem
>> in newlib: cygwin would like to update tree.h, but rtems would like to
>> keep the rbtree version.
>>
> Nevermind, we fixed the RTEMS side. The only remaining problem is when
> the application (or library such as libbsd) would prefer a different
> version of tree.h. I think we can live with just restoring the tree.h
> for now, or someone can provide an updated one also.
> 
> On the RTEMS side, someone needs to remove tree.h from our libbsd.
> 

I am not comfortable with the return of this header to newlib and consider the
addition questionable. Corinna is right saying the removal of headers in the
shared area can break existing user code and continuing this path the addition
of headers like this can also break existing applications. We do not know if
users have headers like this in their code base. I feel users of newlib are in
the best position to know which version of the header they want to depend on. I
know of a couple of archived projects I worked on with imported FreeBSD code the
addition of this header would have caused problems.

Does newlib have a process for determining the addition of headers to the shared
area?

Chris
  

On Jul 17 11:15, Gedare Bloom wrote:
> On Wed, Jul 17, 2024 at 11:14 AM Sebastian Huber
> <sebastian.huber@embedded-brains.de> wrote:
> > Again, I would simply remove <sys/tree.h> from libbsd, monitor the FreeBSD changes, and after evaluation update the Newlib version if there are benefits.
> >
> I'm not opposed to this route, but, we now wind up in the same problem
> in newlib: cygwin would like to update tree.h, but rtems would like to
> keep the rbtree version.

Cygwin does not use sys/tree.h internally.  We don't have any specific
need for a specific internal implementation of the API.  Therefore, we
don't really care which impementation is used.

The concern here is to remove a header which has potentially been used
by a Cygwin package, and as I mentioned in my reply to Joel, there *are*
packages out there using this file, for instance tmux.  While tmux still
works if sys/tree.h is suddenly gone, I have no idea if it still works
as before, or if you get user-visible changes due to that.  That's what
I'd like to avoid.

Yes, it might or might not have been a questionable decision to put
sys/tree.h into newlib, but now it's there and removing it could have
unwelcome side-effects outside RTEMS, that's all I'm saying.

So, let's update it and live with it and next time such a file is
supposed to be added, let's be a bit more thorough in discussing its
need.

In terms of updating the file, I completely trust Sebastian to do the
right thing.


Thanks,
Corinna
  

On 18/07/2024 16:13, Corinna Vinschen wrote:
> On Jul 17 11:15, Gedare Bloom wrote:
>> On Wed, Jul 17, 2024 at 11:14 AM Sebastian Huber
>> <sebastian.huber@embedded-brains.de> wrote:
>>> Again, I would simply remove <sys/tree.h> from libbsd, monitor the FreeBSD changes, and after evaluation update the Newlib version if there are benefits.
>>>
>> I'm not opposed to this route, but, we now wind up in the same problem
>> in newlib: cygwin would like to update tree.h, but rtems would like to
>> keep the rbtree version.
> 
> Cygwin does not use sys/tree.h internally.  We don't have any specific
> need for a specific internal implementation of the API.  Therefore, we
> don't really care which impementation is used.
> 
> The concern here is to remove a header which has potentially been used
> by a Cygwin package, and as I mentioned in my reply to Joel, there *are*
> packages out there using this file, for instance tmux.  While tmux still
> works if sys/tree.h is suddenly gone, I have no idea if it still works
> as before, or if you get user-visible changes due to that.  That's what
> I'd like to avoid.
> 
> Yes, it might or might not have been a questionable decision to put
> sys/tree.h into newlib, but now it's there and removing it could have
> unwelcome side-effects outside RTEMS, that's all I'm saying.
> 
> So, let's update it and live with it and next time such a file is
> supposed to be added, let's be a bit more thorough in discussing its
> need.
> 
> In terms of updating the file, I completely trust Sebastian to do the
> right thing.
> 
> 
> Thanks,
> Corinna
> 

The usual way to deal with things like this is to follow a deprecation process.

first put #warning in the file so that it complains if users try to use it.
Then upgrade to #error, but allow something like -D__PERMIT_DEPRECATED_TREE_H to suppress this.
Finally remove the file, or move it somewhere well out of the way, like sys/obsolete/tree.h

R.
  

Hello,

updating the file will introduce an ABI incompatibility. The node structure of the removed header file was like this:

#define RB_ENTRY(type)                                                 \
struct {                                                               \
       struct type *rbe_left;          /* left element */              \
       struct type *rbe_right;         /* right element */             \
       struct type *rbe_parent;        /* parent element */            \
       int rbe_color;                  /* node color */                \
}

The current FreeBSD tree.h uses this:

#define RB_ENTRY(type)                                                  \
struct {                                                                \
        struct type *rbe_link[3];                                       \
}

/*
 * With the expectation that any object of struct type has an
 * address that is a multiple of 4, and that therefore the
 * 2 least significant bits of a pointer to struct type are
 * always zero, this implementation sets those bits to indicate
 * that the left or right child of the tree node is "red".
 */
#define _RB_LINK(elm, dir, field)       (elm)->field.rbe_link[dir]
#define _RB_UP(elm, field)              _RB_LINK(elm, 0, field)
#define _RB_L                           ((__uintptr_t)1)
#define _RB_R                           ((__uintptr_t)2)
#define _RB_LR                          ((__uintptr_t)3)
#define _RB_BITS(elm)                   (*(__uintptr_t *)&elm)
#define _RB_BITSUP(elm, field)          _RB_BITS(_RB_UP(elm, field))
#define _RB_PTR(elm)                    (__typeof(elm))                 \
                                        ((__uintptr_t)elm & ~_RB_LR)

They use now one of the pointers to store the colour. This reduces the data size of the nodes, however, it adds an alignment requirement. I haven't done any performance tests with the latest FreeBSD code yet. The version Newlib had was a pretty good general purpose red-black tree implementation without implementation constraints.
 
Kind regards, Sebastian
  

On Aug 13 11:59, Sebastian Huber wrote:
> Hello,
> 
> updating the file will introduce an ABI incompatibility. The node
> structure of the removed header file was like this:
> 
> #define RB_ENTRY(type)                                                 \
> struct {                                                               \
>        struct type *rbe_left;          /* left element */              \
>        struct type *rbe_right;         /* right element */             \
>        struct type *rbe_parent;        /* parent element */            \
>        int rbe_color;                  /* node color */                \
> }
> 
> The current FreeBSD tree.h uses this:
> 
> #define RB_ENTRY(type)                                                  \
> struct {                                                                \
>         struct type *rbe_link[3];                                       \
> }
> 
> /*
>  * With the expectation that any object of struct type has an
>  * address that is a multiple of 4, and that therefore the
>  * 2 least significant bits of a pointer to struct type are
>  * always zero, this implementation sets those bits to indicate
>  * that the left or right child of the tree node is "red".
>  */
> #define _RB_LINK(elm, dir, field)       (elm)->field.rbe_link[dir]
> #define _RB_UP(elm, field)              _RB_LINK(elm, 0, field)
> #define _RB_L                           ((__uintptr_t)1)
> #define _RB_R                           ((__uintptr_t)2)
> #define _RB_LR                          ((__uintptr_t)3)
> #define _RB_BITS(elm)                   (*(__uintptr_t *)&elm)
> #define _RB_BITSUP(elm, field)          _RB_BITS(_RB_UP(elm, field))
> #define _RB_PTR(elm)                    (__typeof(elm))                 \
>                                         ((__uintptr_t)elm & ~_RB_LR)
> 
> They use now one of the pointers to store the colour. This reduces the
> data size of the nodes, however, it adds an alignment requirement. I
> haven't done any performance tests with the latest FreeBSD code yet.
> The version Newlib had was a pretty good general purpose red-black
> tree implementation without implementation constraints.
>  
> Kind regards, Sebastian

Then please let's revert tree.h.

Thanks,
Corinna
  

On Aug 14 21:46, Corinna Vinschen wrote:
> On Aug 13 11:59, Sebastian Huber wrote:
> > Hello,
> > 
> > updating the file will introduce an ABI incompatibility. The node
> > structure of the removed header file was like this:
> > 
> > #define RB_ENTRY(type)                                                 \
> > struct {                                                               \
> >        struct type *rbe_left;          /* left element */              \
> >        struct type *rbe_right;         /* right element */             \
> >        struct type *rbe_parent;        /* parent element */            \
> >        int rbe_color;                  /* node color */                \
> > }
> > 
> > The current FreeBSD tree.h uses this:
> > 
> > #define RB_ENTRY(type)                                                  \
> > struct {                                                                \
> >         struct type *rbe_link[3];                                       \
> > }
> > 
> > /*
> >  * With the expectation that any object of struct type has an
> >  * address that is a multiple of 4, and that therefore the
> >  * 2 least significant bits of a pointer to struct type are
> >  * always zero, this implementation sets those bits to indicate
> >  * that the left or right child of the tree node is "red".
> >  */
> > #define _RB_LINK(elm, dir, field)       (elm)->field.rbe_link[dir]
> > #define _RB_UP(elm, field)              _RB_LINK(elm, 0, field)
> > #define _RB_L                           ((__uintptr_t)1)
> > #define _RB_R                           ((__uintptr_t)2)
> > #define _RB_LR                          ((__uintptr_t)3)
> > #define _RB_BITS(elm)                   (*(__uintptr_t *)&elm)
> > #define _RB_BITSUP(elm, field)          _RB_BITS(_RB_UP(elm, field))
> > #define _RB_PTR(elm)                    (__typeof(elm))                 \
> >                                         ((__uintptr_t)elm & ~_RB_LR)
> > 
> > They use now one of the pointers to store the colour. This reduces the
> > data size of the nodes, however, it adds an alignment requirement. I
> > haven't done any performance tests with the latest FreeBSD code yet.
> > The version Newlib had was a pretty good general purpose red-black
> > tree implementation without implementation constraints.
> >  
> > Kind regards, Sebastian
> 
> Then please let's revert tree.h.

Probably ideally with a deprecation following Richard's suggestion...


Thanks,
Corinna