c++ skip list implementation?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: c++ skip list implementation?

  1. #1
    Join Date
    May 2009
    Posts
    2

    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;
    		}
    	}
    
    }
    Last edited by bob135; May 8th, 2009 at 11:55 AM. Reason: fixed formatting

  2. #2
    Join Date
    Sep 2004
    Location
    Holland (land of the dope)
    Posts
    4,123

    Re: c++ skip list implementation?

    Please make your post readable with these.

    What does the debugger tell you during the crash ?

  3. #3
    Join Date
    May 2009
    Posts
    2

    Re: c++ skip list implementation?

    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.

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: c++ skip list implementation?

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center