possible bug in irr::core::map

aallison · Post by **aallison** » Sat May 31, 2008 7:21 am

I am not sure if this is a bug, but I am crashing from the following line in irrMap.h (line 593):

Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();

Is it guaranteed that the node in question has a grandparent? I am not familiar enough with Red/Black trees to know. I am getting a NULL pointer exception occasionally. Is it assumed that not very much rearranging of the tree is going on? Thanks.

-Abel

greenya · Post by **greenya** » Sat May 31, 2008 7:55 am

Instead of

Code: Select all

Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();

Try next

Code: Select all

Node* newNodesUncle1 = newNode->getParent();
Node* newNodesUncle2 = newNodesUncle1->getParent();
Node* newNodesUncle3 = newNodesUncle2->getLeftChild();

You will get again NULL exception but the line (in Debug mode) your IDE must show to you.

xDan · Post by **xDan** » Sat Jun 07, 2008 4:46 pm

I seem to have this same bug... I'm using irrlicht 1.4 but the lines @593 don't seem to be different in 1.4.1

Code: Select all

Program received signal SIGSEGV, Segmentation fault.
0x0040c2e4 in irr::core::map<int, modules::MaterialInteraction>::RBTree<int, mod
ules::MaterialInteraction>::getLeftChild() const (this=0x0)
    at libraries/irrlicht-1.4/irrMap.h:52
52                      RBTree* getLeftChild() const    { return LeftChild; }

Code: Select all

(gdb) backtrace
#0  0x0040c220 in irr::core::map<int, modules::MaterialInteraction>::RBTree<int,
 modules::MaterialInteraction>::getLeftChild() const (this=0x0)
    at libraries/irrlicht-1.4/irrMap.h:52
#1  0x00407117 in irr::core::map<int, modules::MaterialInteraction>::insert(int
const&, modules::MaterialInteraction const&) (this=0x3d43d0,
    keyNew=@0x4aa6fc0, v=@0x22f7cc) at libraries/irrlicht-1.4/irrMap.h:593
#2  0x00406c60 in irr::core::map<int, modules::MaterialInteraction>::set(int con
st&, modules::MaterialInteraction const&) (this=0x3d43d0, k=@0x4aa6fc0,
    v=@0x22f7cc) at libraries/irrlicht-1.4/irrMap.h:636

The crash only occurs after I have added and then removed several keys from the map.

piiichan · Post by **piiichan** » Tue Jun 17, 2008 6:34 am

I also have a bug with map:

Get the following error when calling insert()
Access violation reading location 0x00000000.
(looks like it is trying to dereference a NULL pointer)

Then the debugger brings me to line 52 of irrmap.h

Code: Select all

RBTree* getLeftChild() const	{ return LeftChild; }

It happens when I first insert at least 2 objects, then remove them, then try to insert them back again.

v1.4.1
VC++ 2005 Express SP1

xDan · Post by **xDan** » Wed Jul 02, 2008 12:04 pm

Well since I too have no knowledge of red black trees I made a simple replacement using core::array to use until some kind soul fixes it

It doesn't have all functionality but enough for my needs. Maybe someone elses too!

Code: Select all

#ifndef SLOWMAP_H
#define SLOWMAP_H

// This is just hacked up quickly as there seemed to be some bug with
// Irrlicht's map class. Hopefully that will get fixed then should
// change back to using map.
template <class KeyType, class ValueType>
class SlowMap
{
    struct KeyMap
    {
        KeyType key;
        ValueType value;
    };
    
    core::array<KeyMap> mappings;
    
public:
    void set(KeyType key, ValueType value)
    {
        for (u16 i = 0; i < mappings.size(); i ++)
        {
            if (mappings[i].key == key)
            {
                mappings[i].value = value;
                return;
            }
        }
        KeyMap mapping;
        mapping.key = key;
        mapping.value = value;
        mappings.push_back(mapping);
    }
    
    bool insert(KeyType key, ValueType value)
    {
        for (u16 i = 0; i < mappings.size(); i ++)
        {
            if (mappings[i].key == key)
                return false;
        }
        KeyMap mapping;
        mapping.key = key;
        mapping.value = value;
        mappings.push_back(mapping);
        return true;
    }
    
    void clear()
    {
        mappings.clear();
    }
    
    void remove(KeyType key)
    {
        for (u16 i = 0; i < mappings.size(); i ++)
        {
            if (mappings[i].key == key)
            {
                mappings.erase(i);
                return;
            }
        }
    }
    
    ValueType operator[](KeyType key)
    {
        for (u16 i = 0; i < mappings.size(); i ++)
        {
            if (mappings[i].key == key)
                return mappings[i].value;
        }
        throw (const char *)"SlowMap: key not found.";
    }
};

#endif