void XSECXPathNodeList::addNode()

in xsec/utils/XSECXPathNodeList.cpp [300:400]

• 66 lines of code
• 17 McCabe index (conditional complexity)

void XSECXPathNodeList::addNode(const DOMNode *n) {

	btn * v;

	if (m_num == 0) {
		XSECnew(mp_tree, btn);
		mp_tree->l = mp_tree->r = NULL;
		mp_tree->v = n;
		mp_tree->p = NULL;
		mp_tree->h = 1;
		m_num = 1;
		return;
	}

	// Find the node
	btn * t = mp_tree;
	btn * last = NULL;

	while (t != NULL && t->v != n) {
		last = t;
		if (n > t->v)
			t = t->r;
		else
			t = t->l;
	}

	if (t != NULL)
		// Node already exists in tree!
		return;

	// Work out the insertion.
	XSECnew(v, btn);
	v->v = n;
	v->r = v->l = NULL;
	v->h = 1;
	v->p = last;

	// Determine on which leg to place the new value
	if (n > last->v)
		last->r = v;
	else
		last->l = v;

	// Recalculate heights
	t = last;
	long newh;
	while (t != NULL) {
		newh = calc_height(t);
		if (newh > t->h) {
			t->h = newh;
			t = t->p;
		}
		else
			// If the height is the same here, then nothing will have changed above
			t = NULL;
	}

	// Rebalance!
	
	t = last;
	while (t != NULL) {		
		long bal = balance_count(t);
		long balrc = balance_count(t->r);
		long ballc = balance_count(t->l);

		// Case 1 - Balance is OK
		if (bal <= 1 && bal >= -1) {
			// Do nothing!
		}

		// Case 2a - Balance is -2 and LC = -1
		else if (bal == -2 && ballc == -1) {

			// Rotate current node right
			rotate_right(t);
		}
		// Or balance is +2 and RC = +1
		else if (bal == 2 && balrc  == 1) {

			// Rotate current node left
			rotate_left(t);
		}
		// Case 2b = Balance is -2 and LC = +1
		else if (bal == -2 && ballc == 1) {

			// Double Right rotation
			rotate_left(t->l);
			rotate_right(t);
		}

		else {
			rotate_right(t->r);
			rotate_left(t);

		}

		t = t->p;

	}

}