Reduce memory size of tsearch red-black tree.

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 add asserts for malloc alignment.
       (__twalk): Cast root to node in case CHECK_TREE is defined.

1 files changed, 14 insertions, 0 deletions

diff --git a/ChangeLog b/ChangeLog
index 4e172c467a..7205de46dc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2016-08-25  Mark Wielaard  <mark@klomp.org>
+
+	* 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 add asserts for malloc alignment.
+	(__twalk): Cast root to node in case CHECK_TREE is defined.
+
 2016-08-21  Samuel Thibault  <samuel.thibault@ens-lyon.org>
 
 	* scripts/check-local-headers.sh (exclude): Add mach_debug/.