3   Red Black Trees
16  * red-black trees properties:  https://en.wikipedia.org/wiki/Rbtree
18  *  1) A node is either red or black
21  *  4) Both children of every red node are black
26  *  consecutive red nodes in a path and every red node is therefore followed by
30  *  We shall indicate color with case, where black nodes are uppercase and red
31  *  nodes will be lowercase. Unknown color nodes shall be drawn as red within
64 static inline struct rb_node *rb_red_parent(struct rb_node *red)  in rb_red_parent()  argument
66 	return (struct rb_node *)red->__rb_parent_color;  in rb_red_parent()
92 		 * Loop invariant: node is red.  in __rb_insert()
107 		 * per 4), we don't want a red root or two  in __rb_insert()
108 		 * consecutive red nodes.  in __rb_insert()
119 				 * Case 1 - node's uncle is red (color flips).  in __rb_insert()
127 				 * However, since g's parent might be red, and  in __rb_insert()
277 					 * if it was red, or by recursing at p.  in ____rb_erase_color()
278 					 * p is red when coming from Case 1.  in ____rb_erase_color()
304 				 * Note: p might be red, and then both  in ____rb_erase_color()
305 				 * p and sl are red after rotation(which  in ____rb_erase_color()