244   uint32_t parent = 0;  in InsertNode()  local
250   // Find the node which will become |node|'s parent after insertion  in InsertNode()
253     parent = iter;  in InsertNode()
259   assert(parent);  in InsertNode()
261   // Connect node and parent.  in InsertNode()
262   MutableParentOf(node) = parent;  in InsertNode()
264     MutableRightOf(parent) = node;  in InsertNode()
266     MutableLeftOf(parent) = node;  in InsertNode()
270   parent = ParentOf(node);  in InsertNode()
272   while (parent) {  in InsertNode()
273     UpdateNode(parent);  in InsertNode()
276       const int parent_balance = BalanceOf(parent);  in InsertNode()
278       if (RightOf(parent) == node) {  in InsertNode()
281           // Parent is right heavy, rotate left.  in InsertNode()
283           parent = RotateLeft(parent);  in InsertNode()
285           // Parent is balanced or left heavy, no need to balance further.  in InsertNode()
291           // Parent is left heavy, rotate right.  in InsertNode()
293           parent = RotateRight(parent);  in InsertNode()
295           // Parent is balanced or right heavy, no need to balance further.  in InsertNode()
301     assert(BalanceOf(parent) >= -1 && (BalanceOf(parent) <= 1));  in InsertNode()
303     node = parent;  in InsertNode()
304     parent = ParentOf(parent);  in InsertNode()
327   uint32_t parent = ParentOf(node);  in RemoveNode()  local
330   // Orphan |node| and reconnect parent and child.  in RemoveNode()
331   if (child) MutableParentOf(child) = parent;  in RemoveNode()
333   if (parent) {  in RemoveNode()
334     if (LeftOf(parent) == node)  in RemoveNode()
335       MutableLeftOf(parent) = child;  in RemoveNode()
337       MutableRightOf(parent) = child;  in RemoveNode()
352   while (parent) {  in RemoveNode()
353     UpdateNode(parent);  in RemoveNode()
356       const int parent_balance = BalanceOf(parent);  in RemoveNode()
362         if (RightOf(parent) == node) {  in RemoveNode()
365             // Parent is left heavy, rotate right.  in RemoveNode()
366             const uint32_t sibling = LeftOf(parent);  in RemoveNode()
368             parent = RotateRight(parent);  in RemoveNode()
373             // Parent is right heavy, rotate left.  in RemoveNode()
374             const uint32_t sibling = RightOf(parent);  in RemoveNode()
376             parent = RotateLeft(parent);  in RemoveNode()
382     assert(BalanceOf(parent) >= -1 && (BalanceOf(parent) <= 1));  in RemoveNode()
384     node = parent;  in RemoveNode()
385     parent = ParentOf(parent);  in RemoveNode()
412   // Update both node and pivot. Pivot is the new parent of node, so node should  in RotateLeft()
441   // Update both node and pivot. Pivot is the new parent of node, so node should  in RotateRight()