[fixed] Bug in core::map() - the root should never be red

[rogerborg]

Removing the root of an irr::core::map's red-black tree can lead to a crash if the new root is red. The root node should always be black.

Code: Select all

Index: include/irrMap.h
===================================================================
--- include/irrMap.h	(revision 1444)
+++ include/irrMap.h	(working copy)
@@ -830,7 +830,10 @@
 	{
 		Root = newRoot;
 		if (Root != 0)
+		{
 			Root->setParent(0);
+			Root->setBlack(); // The root must always be black
+		}
 	}
 
 	//! Insert a node into the tree without using any fancy balancing logic.

Test case that demonstrates the crash (when unpatched) and better behaviour after patching:

Code: Select all

#include <irrlicht.h>

#pragma comment(lib, "Irrlicht.lib")

int main()
{
    irr::core::map<int, int> myMap;

    (void)myMap.insert(2, 0);
    (void)myMap.insert(3, 0);
    myMap.remove(2); // removes the root
    (void)myMap.insert(0, 0); // crashes here

    // The following exercises the code after the patch
    myMap.remove(3); // remove the new root
    (void)myMap.insert(2, 0);
    (void)myMap.insert(4, 0);
    (void)myMap.insert(1, 0);
    (void)myMap.insert(3, 0);
    myMap.remove(2); // removes the root again
    (void)myMap.insert(0, 0);

    return 0;
}

[hybrid]

If only someone would provide a simpler, less buggy implementation of a map
Anyway, thanks for the patch.

[rogerborg]

Reading the current implementation scared me. I had to get a special hug from the missus afterwards.

[full.metal.coder]

if anyone would provide a decent implementation of a hash table...

Qt implementations of both just rock but are licensed under GPL so Irrlicht can not reuse them directly... there's also google dense_hash_map which is supposed to be good but has some limitations.

A temporary solution is to use two arrays, which is bug free and allows two-ways indexing but gives O(n) lookup instead of O(log n) for a classic map and O(1) for a hash table...