crash in std::_Rb_tree_increment(std::_Rb_tree_node_base const *)

[ashishkumar]

Hi,
I got a crash stacktrace which is...
------------------------------------------------------------------
............
...............
leafNodeArray::elementAt(int) const
leafNodeArray::sort() const
std::_Rb_tree_increment(std::_Rb_tree_node_base const*)
------------------------------------------------------------------

I have tried to put the actual useful code snippet below (by slightly modifiing the names...). In run time, the map table has lot of entries. I do not have the testcase to reproduce the issue for the crash. I just have to statically analyze the code and see if the root cause can be found.
(i) from std::_Rb_tre_increment , does it mean that ++p is the culprit..
(ii) The crash happens on 64 bit machines. Can it be the case that the index which is being typecasted from int to unsigned int is creating some problem.

Any help is welcome.?

--------------------------sample similar code...-------------------------------------
#include <stdlib.h>
#include <stdio.h>
#include <map>
class leafNode {
};

typedef std::map<const char *, leafNode *> leafNodeMap;

class leafNodeArray {
public:
leafNodeArray();
~leafNodeArray();
int getLength() const;
const leafNode * elementAt(int index) const;
void addLeafNode(leafNode *obj);
private:
void deleteSortedArray() const;
void sort() const;
leafNodeMap _map;
mutable bool _isSorted;
mutable leafNode** _sortedArray;
};

leafNodeArray::leafNodeArray() {
_sortedArray = NULL;
}

leafNodeArray::~leafNodeArray() {
deleteSortedArray();
}

void
leafNodeArray::deleteSortedArray() const {
if (_sortedArray) {
delete[] _sortedArray;
}
_sortedArray = NULL;
}

int
leafNodeArray::getLength() const {
return _map.size();
}

void
leafNodeArray::sort() const {
if (!_isSorted) {
deleteSortedArray();
_sortedArray = new leafNode*[_map.size()];
leafNodeMap::const_iterator p;
int index=0;
for( p = _map.begin(); p != _map.end(); ++p ) {
_sortedArray[index++] = (leafNode *)p->second;
}
_isSorted = TRUE;
}
}

const leafNode *
leafNodeArray::elementAt(int index) const {
sort();
if ((unsigned int)index >= _map.size()) {
return NULL;
}
return ((const leafNode *)_sortedArray[index]);
}

main() {
//const leafNodeArray * leaves = root->getLeafNodes();
// In actual scenario the leaves are not empty and do have... proper length.
const leafNodeArray * leaves = new leafNodeArray();
if (leaves) {
int count = leaves->getLength();
for(int i=0;i < count; i++) {
const leafNode * tempLeaf = leaves->elementAt(i);
//.... do some read only operation with leafNode
}
}
}
-----------------------------------------------

[cire]

sort isn't called before elementAt. elementAt doesn't check to see if _isSorted == true or whether _sortedArray is non-Null.

I would guess the problem is you're dereferencing a null pointer.

[ashishkumar]

Sorry,
I missed one line, the sort function sets the _isSorted = TRUE after the for loop. Hence next sort() function will not go through the loop.
Next you are hinting at the NULL check for _sortedArray. That means you are saying that the new() function has failed and may be we can have a try-catch which catches a bad_alloc. Are you pointing towards a memory allocation failure??

[cire]

What I'm saying is that sort isn't called before elementAt.

That means no attempt at allocating memory for _sortedArray has occurred.

That means elementAt will be dereferencing a null pointer.