Use a functional red-black tree for indexing the shapes

This is an experimental commit that uses a functional red-black tree to
create an index of the ancestor shapes.  It uses an Okasaki style
functional red black tree:

  https://www.cs.tufts.edu/comp/150FP/archive/chris-okasaki/redblack99.pdf

This tree is advantageous because:

* It offers O(n log n) insertions and O(n log n) lookups.
* It shares memory with previous "versions" of the tree

When we insert a node in the tree, only the parts of the tree that need
to be rebalanced are newly allocated.  Parts of the tree that don't need
to be rebalanced are not reallocated, so "new trees" are able to share
memory with old trees.  This is in contrast to a sorted set where we
would have to duplicate the set, and also resort the set on each
insertion.

I've added a new stat to RubyVM.stat so we can understand how the red
black tree increases.

1 files changed, 15 insertions, 0 deletions

diff --git a/shape.h b/shape.h
index 5689b48067..a3ab683c8f 100644
--- a/shape.h
+++ b/shape.h
@@ -17,10 +17,12 @@ typedef uint16_t attr_index_t;
 
 #if SIZEOF_SHAPE_T == 4
 typedef uint32_t shape_id_t;
+typedef uint32_t redblack_id_t;
 # define SHAPE_ID_NUM_BITS 32
 # define SHAPE_BUFFER_SIZE 0x80000
 #else
 typedef uint16_t shape_id_t;
+typedef uint16_t redblack_id_t;
 # define SHAPE_ID_NUM_BITS 16
 # define SHAPE_BUFFER_SIZE 0x8000
 #endif
@@ -40,6 +42,8 @@ typedef uint16_t shape_id_t;
 # define SPECIAL_CONST_SHAPE_ID (SIZE_POOL_COUNT * 2)
 # define OBJ_TOO_COMPLEX_SHAPE_ID (SPECIAL_CONST_SHAPE_ID + 1)
 
+typedef struct redblack_node redblack_node_t;
+
 struct rb_shape {
     struct rb_id_table * edges; // id_table from ID (ivar) to next shape
     ID edge_name; // ID (ivar) for transition from parent to rb_shape
@@ -48,10 +52,18 @@ struct rb_shape {
     uint8_t type;
     uint8_t size_pool_index;
     shape_id_t parent_id;
+    redblack_node_t * ancestor_index;
 };
 
 typedef struct rb_shape rb_shape_t;
 
+struct redblack_node {
+    ID key;
+    rb_shape_t * value;
+    redblack_id_t l;
+    redblack_id_t r;
+};
+
 enum shape_type {
     SHAPE_ROOT,
     SHAPE_IVAR,
@@ -67,6 +79,9 @@ typedef struct {
     rb_shape_t *shape_list;
     rb_shape_t *root_shape;
     shape_id_t next_shape_id;
+
+    redblack_node_t *shape_cache;
+    unsigned int cache_size;
 } rb_shape_tree_t;
 RUBY_EXTERN rb_shape_tree_t *rb_shape_tree_ptr;