c++ skip list implementation?

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:

Code:

---

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

---

Code:

---

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];
}

---

Code:

---

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;
        }
}

---

Code:

---

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;
                }
        }

}

---

Please make your post readable with these.

What does the debugger tell you during the crash ?

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

Code:

---

                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.

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:

Code:

---

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.