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

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