[PATCH] libc/include/sys/tree.h: Re-add sys/tree.h

[Corinna Vinschen]

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