i#1114 JIT optimization: implement red-black tree

Commit log for first patchset:
---------------
i#1114 JIT optimization: implement red-black tree

Implements all red-black tree operations that were
stubbed out in the previous commit, and adds a
randomized unit test to cover corner cases.
---------------

[Byron, 2015-12-20 21:45:56]

This commit is quite large, though all the functionality is standard for a
red-black tree (plus a big test). I can break it into pieces if that would be
preferable (and this CL can be used for reference).

The unit test for the tree takes about 8 seconds on my Xeon E3 server. We could
make it shorter by reducing the data size, or by optimizing the list-based
cross-checks (which currently do a linear walk for every lookup).

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c
File core/jit_opt.c (right):

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c#newcode69
core/jit_opt.c:69: bb_node_t *nil;
Not using the CLRS implementation anymore, so nil's parent is never set.

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c#newcode484
core/jit_opt.c:484: if (deletion != node) {
This is ugly, but not sure what else we can do. Unless all use cases of the
future intervalx.h can allow the node instances to be completely tree-private?
But that seems like a problematic constraint.

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c#newcode588
core/jit_opt.c:588: #ifndef STANDALONE_UNIT_TEST
Is there a simpler way to avoid this? Can the unit_test set
DYNAMO_OPTION(opt_jit) internally?

[bruening, 2016-01-04 19:52:26]

LGTM

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c
File core/jit_opt.c (right):

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c#newcode588
core/jit_opt.c:588: #ifndef STANDALONE_UNIT_TEST
On 2015/12/20 21:45:56, Byron wrote:
> Is there a simpler way to avoid this? Can the unit_test set
> DYNAMO_OPTION(opt_jit) internally?

You can set it in your unit test init code below.

[Byron, 2016-01-06 01:06:17]

Committed as
https://github.com/DynamoRIO/dynamorio/commit/eb0a6d32ab8f89a53d6a8aee32426a4...

Final commit log: 
---------------
i#1114 JIT optimization: implement red-black tree

Implements all red-black tree operations that were
stubbed out in the previous commit, and adds a
randomized unit test to cover corner cases.

Review-URL: https://codereview.appspot.com/283920043
---------------

[Byron, 2016-01-06 01:07:18]

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c
File core/jit_opt.c (right):

https://codereview.appspot.com/283920043/diff/1/core/jit_opt.c#newcode588
core/jit_opt.c:588: #ifndef STANDALONE_UNIT_TEST
On 2016/01/04 19:52:26, bruening wrote:
> On 2015/12/20 21:45:56, Byron wrote:
> > Is there a simpler way to avoid this? Can the unit_test set
> > DYNAMO_OPTION(opt_jit) internally?
> 
> You can set it in your unit test init code below.

Done.