[PATCH v2] Reduce memory size of tsearch red-black tree.

[Mark Wielaard]

On Wed, 2016-08-17 at 17:11 +0200, Mark Wielaard wrote:
> A tsearch red-black tree node contains 3 pointers (key, left, right)
> and 1 bit to hold the red-black flag. When allocating new nodes
> this 1 bit is expanded to a full word. Causing the overhead per node
> to be 3 times the key size.
> 
> We can reduce this overhead to just 2 times the key size.
> malloc returns naturally aligned memory. All nodes are internally
> allocated with malloc and the left/right node pointers are used
> as implementation details. So we can use the low bits of the
> left/right node pointers to store extra information.
> 
> Replace all direct accesses of the struct node_t node pointers and
> red-black value with defines that take care of the red-black flag in
> the low bit of the (left) node pointer. This reduces the size of the
> nodes on 32-bit systems from 16 to 12 bytes and on 64-bit systems
> from 32 to 24 bytes.
> 
> Also fix a call to CHECK_TREE so the code can be build (and tested)
> with DEBUGGING defined again.
> 
> V2 changes:
> 
> - Add assert after malloc to catch any odd pointers from bad
>   interposed mallocs.
> - Rename implementation flag to USE_MALLOC_LOW_BIT.
> 
> ChangeLog:
> 
>        * misc/tsearch.c (struct node_t): Reduce to 3 pointers if
>        USE_MALLOC_LOW_BIT.  Define pointer/value accessors.
>        (check_tree_recurse): Use newly defined accessors.
>        (check_tree): Likewise.
>        (maybe_split_for_insert): Likewise.
>        (__tfind): Likewise.
>        (__tdelete): Likewise.
>        (trecurse): Likewise.
>        (tdestroy_recurse): Likewise.
>        (__tsearch): Likewise. And assert malloc alignment.
>        (__twalk): Cast root to node in case CHECK_TREE is defined.

Ping. OK to commit?

Thanks,

Mark