Function vMemMgrInsertNode

libraries/asmjit/asmjit/base/vmem.cpp:312–387

}

static void vMemMgrInsertNode(VMemMgr* self, MemNode* node) noexcept {
  if (!self->_root) {
    // Empty tree case.
    self->_root = node;
  }
  else {
    // False tree root.
    RbNode head = { { nullptr, nullptr }, 0, 0 };

    // Grandparent & parent.
    RbNode* g = nullptr;
    RbNode* t = &head;

    // Iterator & parent.
    RbNode* p = nullptr;
    RbNode* q = t->node[1] = self->_root;

    int dir = 0;
    int last = 0; // Not needed to initialize, but makes some tools happy.

    // Search down the tree.
    for (;;) {
      if (!q) {
        // Insert new node at the bottom.
        q = node;
        p->node[dir] = node;
      }
      else if (rbIsRed(q->node[0]) && rbIsRed(q->node[1])) {
        // Color flip.
        q->red = 1;
        q->node[0]->red = 0;
        q->node[1]->red = 0;
      }

      // Fix red violation.
      if (rbIsRed(q) && rbIsRed(p)) {
        int dir2 = t->node[1] == g;
        t->node[dir2] = q == p->node[last] ? rbRotateSingle(g, !last) : rbRotateDouble(g, !last);
      }

      // Stop if found.
      if (q == node)
        break;

      last = dir;
      dir = q->mem < node->mem;

      // Update helpers.
      if (g) t = g;

      g = p;
      p = q;
      q = q->node[dir];
    }

    // Update root.
    self->_root = static_cast<MemNode*>(head.node[1]);
  }