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

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

-- 
embedded brains GmbH & Co. KG
Herr Sebastian HUBER
Dornierstr. 4
82178 Puchheim
Germany
email: [email protected]
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/