c++ skip list implementation?

[bob135]

I'm having trouble implementing a skip list. It's supposed to store rectangles and order them by a key which is a character array, using strcmp to order them correctly.

Obviously its screwed up somewhere but I'm not sure what's wrong. I step through and it breaks on the line right after the first if statement in the insert function, giving me an access violation.

This is what I have so far:

int randomH(){
	int h=1;//h must be at least 1
	while((rand() % 2) == 1){//with a coin flip, increase h
		h++;
	}
	return h;
}

node::node(char *myKey, int myX, int myY, int myH, int myW){
	key = myKey;
	x=myX;
	y=myY;
	h=myH;
	w=myW;

	height = randomH();
	forward = new node*[height];
}

skiplist::skiplist(){
	NIL = new node("THE_END",-1,-1,-1,-1);
	head = new node("THE_HEAD",-1,-1,-1,-1);
	listheight = head->height;
	for(int i=0;i<listheight;i++){
		head->forward[i] = NIL;
	}
}

void skiplist::insert(char *myKey, int myX, int myY, int myH, int myW){
	node *inserted = new node(myKey, myX, myY, myH, myW);//make the node to insert

	int i = inserted->height - 1;//track the height (start at the top)
	node *pos = head;//track the position (start at the head)

	while(i > -1){//until we try to drop "below" the tree
		if(pos->forward[i] == NIL || strcmp( pos->forward[i]->key, myKey) > 0){//if the node to the right is NIL or is bigger, add a pointer and go down a level
			inserted->forward[i] = pos->forward[i]; //the node being inserted points to the node pos pointed to
			pos->forward[i] = inserted; //the position prior to that node now points to it
			i--;
		}
		else if( strcmp( pos->forward[i]->key, myKey) < 0){//if the node to the right is smaller, go forward one
			pos = pos->forward[i];
		}
		else{//otherwise they're equal
			inserted->forward[i] = pos->forward[i]; //the node being inserted points to the node pos pointed to
			pos->forward[i] = inserted; //the position prior to that node now points to it			
		}
	}

	
	if(inserted->height > listheight){//and if the new node has a height in excess of the existing structure....
		node **tempForward = new node*[inserted->height]; //make a new array
		tempForward = head->forward; //store the existing head's forward array in it

		delete head->forward;//delete the old one
		head->forward = new node*[inserted->height];//remake it
		head->forward = tempForward;//copy old data to the new one

		for(int k = inserted->height - 1; k > listheight - 1; k--){
			head->forward[k] = inserted;
		}
	}

}

[Skizmo]

Please make your post readable with these.

What does the debugger tell you during the crash ?

[bob135]

Better?

It tells me....

Unhandled exception at 0x00414630 in SkipList.exe: 0xC0000005: Access violation reading location 0xfdfdfe15.

I look at the forward array in the debugger while stepping through the code. Here

		if(pos->forward[i] == NIL || strcmp( pos->forward[i]->key, myKey) > 0){//if the node to the right is NIL or is bigger, add a pointer and go down a level
			inserted->forward[i] = pos->forward[i]; //the node being inserted points to the node pos pointed to
			pos->forward[i] = inserted; //the position prior to that node now points to it
			i--;

And for some reason forward[i] is filled with garbage, even though I think it should always point to something, since the head's forward array initially points to NIL, and everything after that should be inserted before NIL.

[Lindley]

First thing: Since your classes use "new" in the constructor (and presumably "delete" in the destructor), you have to make sure they either have valid copy semantics, or else cannot be copied. The latter is easier in most cases. Simply add this to the class definition:

private:
    void operator=(const classname & rhs);
    classname(const classname & original);

If that produces any errors, then it signifies a problem with your usage: Either you'll need to stop trying to make whatever copy you're making, or you'll need to actually define both of those functions.