Seg Faults with XOR LL

seePhor · 03-11-2010, 09:12 PM

I have an issue with the XOR Linked List I have created. It inserts and prints just fine. I can delete some numbers. When I try to delete 45, 4040, and 9769 from the list, I get segmentation faults and I am not sure what is causing it. I have not learned how to use a debugger yet and apparently I am not supposed to.

This is what I have so far

Note: I call delete in the list function. I want to display the list , then delete some values, and then display the list again. I would greatly appreciate any tips or suggestions. I am fairly new to C and using pointers gets a little confusing.

Code:

#include <stdio.h>
#include <stdlib.h>
#include "rndm.h"

struct node {
       int data;
       unsigned long link;
};
struct node *head, *tail, *currN, *prevN, *nextN, *tmp;

void insert(struct node **headN, struct node **tailN, int n);
void delete(struct node **headN, struct node **tailN, int n);
void list(struct node *head);
void nextNode();
void previNode();

//============================================================

void insert(struct node **headN, struct node **tailN, int numN) {
     struct node *newnode = malloc(sizeof(struct node));
     newnode->link =(unsigned long)(*headN);
     newnode->data = numN;
	 
     //if empty list
     if (*headN == NULL){
          *headN = newnode;
          currN = *headN;
          (*headN)->link = 0;
     } else if ((*headN)->link == (unsigned long)NULL){
           if (numN <= (*headN)->data){
                newnode->link = (unsigned long) *headN;
                (*headN)->link = (unsigned long) newnode;
                tail = *headN;
                *headN = newnode;
                nextN = tail;
                prevN = NULL;
            } else {
                newnode->link = (unsigned long) *headN;
                (*headN)->link = (unsigned long) newnode;
                tail = newnode;
                nextN = NULL;
                currN = tail;
                prevN = *headN;
              }
     } else { 
          currN = *headN;
          prevN = NULL;
          nextN = (struct node *)(currN->link ^ (unsigned long) prevN);
          if (numN > tail->data){
               while (currN!=tail){
                     nextNode();
               }
               newnode->link = (unsigned long) currN;
               currN->link = (unsigned long) newnode ^ (unsigned long) prevN;
               tail = newnode;
          } else if (numN < head->data){
               currN->link = (unsigned long) newnode ^ (unsigned long) nextN;
               newnode->link = (unsigned long) currN;
               *headN = newnode;
               nextN = currN;
               currN = *headN;
          } else {
               while (numN > currN->data){
                     nextNode();
               }
               newnode->link = (unsigned long) prevN ^ (unsigned long) currN;
               prevN->link ^= (unsigned long) currN ^ (unsigned long) newnode;
               currN->link ^= (unsigned long) prevN ^ (unsigned long) newnode;
          }
     }
}  

void delete(struct node **headN, struct node **tailN, int Del){
     prevN = NULL;
     currN = head;
     while(currN!=NULL && currN->data!=Del){
          nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
          nextNode();
     }
     nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
     prevN->link ^= (unsigned long) currN ^ (unsigned long) nextN;
     nextN->link ^= (unsigned long) currN ^ (unsigned long) prevN;
     free(currN);
}

void list(struct node *head){
     currN = head;
     prevN = NULL;
     int count = 1;
     nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
     printf("Linked List in ascending order\n");
     while(currN!=NULL){
          if(count <= 10){
               printf("%-5d", currN->data);
               nextNode();
               count++;
          } 
          else{
               printf("\n");
               count = 1;
          }
     }
     printf("\n\n"); 
	 	
	 delete( &head, &tail, 7004);

	 
     printf("Linked List in decending order\n");
     currN = tail;
     int count2 = 1;
     prevN = (struct node *) currN->link;
     nextN = NULL;
     while (currN!=NULL){
         if(count2 <= 10){
              printf("%-5d", currN->data);
              previNode();
              count2++;
          
          }else{
              printf("\n");
              count2 = 1;
          }
    }   
    printf("\n");         
}

void nextNode(){
    nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
    prevN = currN;
    currN = nextN;
}

void previNode(){
    prevN = (struct node *) (currN->link ^ (unsigned long) nextN);
    nextN = currN;
    currN = prevN;		
}

int main(){
    
    int i, num;
    float seed;
    head = NULL; tail = NULL; currN = NULL; prevN = NULL; nextN = NULL;
    
    init_seed(123456);
    set_range(1,9999);
    //inserting data into the linked list
    for ( i=0; i<100; ++i){
        num = rndm();
        insert( &head, &tail, num );
    }
    list(head); //print out list in both orders
    
    return 0;
}

This is the output I got when trying to delete other numbers:

Code:

Linked List in ascending order
107  127  271  297  546  677  720  753  958  1078
1107 1292 1345 1363 1485 1597 1683 1833 1861 1954
2120 2171 2194 2461 2510 2680 2951 2980 3069 3121
3130 3179 3337 3407 3725 3785 3793 3796 3856 3873
3968 4033 4107 4130 4173 4184 4327 4462 4637 4846
4900 4942 4995 5048 5084 5115 5184 5192 5203 5308
5375 5684 5712 6065 6166 6175 6212 6238 6325 6530
6578 6671 6805 6816 7004 7182 7251 7281 7624 7658
7790 8253 8331 8436 8521 8527 8771 8885 8988 9122
9211 9224 9376 9384 9401 9576 9625 9629 9662 9678

Linked List in decending order
9678 9662 9629 9625 9576 9401 9384 9376 9224 9211
9122 8988 8885 8771 8527 8521 8436 8331 8253 7790
7658 7624 7281 7251 7182 7004 6816 6805 6671 6578
6530 6325 6238 6212 6175 6166 6065 5712 5684 5375
5308 5203 5192 5184 5115 5084 5048 4995 4942 4900
4846 4637 4462 4327 4184 4173 4130 4107 4033 3968
3873 3856 3796 3793 3785 3725 3407 3337 3179 3130
3121 3069 2980 2951 2680 2510 2461 2194 2171 2120
1954 1861 1833 1683 1597 1485 1363 1345 1292 1107
1078 958  753  720  677  546  297  271  127  107
Segmentation fault

**Salem** · 03-11-2010, 11:35 PM

Maybe construct a proper LL with true next/prev pointers you can easily diagnose as being correct or broken.

Then leave it like that as the job is done.

seePhor · 03-11-2010, 11:43 PM

so pretty much forget about using XOR LL's?

seePhor · 03-11-2010, 11:47 PM

It is definitely narrowed down to my delete function. When I comment out the code for delete, it works fine.

**Salem** · 03-11-2010, 11:47 PM

XOR linked list - Wikipedia, the free encyclopedia
I find their disadvantages to be far too numerous.

One of which is affecting you, namely the debuggability of them.

Like I said, start with a regular DLL, and make sure it works.

Then (and only then), if you're still set on an XOR-LL, convert all the next/prev things into a single xor value.

Do the conversion by commenting out the real code, so you have a reminder of what it is you're actually doing.

seePhor · 03-12-2010, 12:20 AM

I feel really close though. I rewrote some of the code and rewrote some of my delete function:

Code:

#include <stdio.h>
#include <stdlib.h>
#include "rndm.h"

struct node {
       int data;
       unsigned long link;
};
struct node *head, *tail, *currN, *prevN, *nextN, *tmp;

void insert(struct node **headN, struct node **tailN, int n);
void delete(struct node **headN, struct node **tailN, int n);
void list(struct node *head, int i);
void nextNode();
void previNode();

//============================================================

void insert(struct node **headN, struct node **tailN, int numN) {
     struct node *newnode = malloc(sizeof(struct node));
     newnode->link =(unsigned long)(*headN);
     newnode->data = numN;
	 
     //if empty list
     if (*headN == NULL){
          *headN = newnode;
          currN = *headN;
          (*headN)->link = 0;
     } else if ((*headN)->link == (unsigned long)NULL){
           if (numN <= (*headN)->data){
                newnode->link = (unsigned long) *headN;
                (*headN)->link = (unsigned long) newnode;
                tail = *headN;
                *headN = newnode;
                nextN = tail;
                prevN = NULL;
            } else {
                newnode->link = (unsigned long) *headN;
                (*headN)->link = (unsigned long) newnode;
                tail = newnode;
                nextN = NULL;
                currN = tail;
                prevN = *headN;
              }
     } else { 
          currN = *headN;
          prevN = NULL;
          nextN = (struct node *)(currN->link ^ (unsigned long) prevN);
          if (numN > tail->data){
               while (currN!=tail){
                     nextNode();
               }
               newnode->link = (unsigned long) currN;
               currN->link = (unsigned long) newnode ^ (unsigned long) prevN;
               tail = newnode;
          } else if (numN < head->data){
               currN->link = (unsigned long) newnode ^ (unsigned long) nextN;
               newnode->link = (unsigned long) currN;
               *headN = newnode;
               nextN = currN;
               currN = *headN;
          } else {
               while (numN > currN->data){
                     nextNode();
               }
               newnode->link = (unsigned long) prevN ^ (unsigned long) currN;
               prevN->link ^= (unsigned long) currN ^ (unsigned long) newnode;
               currN->link ^= (unsigned long) prevN ^ (unsigned long) newnode;
          }
     }
}  

void delete(struct node **headN, struct node **tailN, int numD){
     
	 struct node *prevN = NULL;
     struct node *currN = *headN;
	 
	 while ( currN != NULL )
  	{
		struct node *nextN = (struct node *) (currN->link ^ (unsigned long)prevN);	
		//if the number is found, then delete it
		if (currN->data == numD)
		{
		  if(prevN) 
             	  {
                     prevN->link ^= (unsigned long)currN ^ (unsigned long)nextN;
           	  }
            	  else 
                     *headN = nextN;
	    	  if(nextN) 
            	  {
                     nextN->link ^= (unsigned long)currN ^ (unsigned long)prevN;
            	  }	
            	  else 
                     *tailN = prevN;
		  free(currN);
		  break;
		}
    		prevN = currN;
		currN = nextN;
	}
}

void list(struct node *head, int i){
     
	if(i == 0){ 
	 currN = head;
     prevN = NULL;
     int count = 1;
     nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
     printf("Linked List in ascending order\n");
     while(currN!=NULL){
          if(count <= 10){
               printf("%-5d", currN->data);
               nextNode();
               count++;
          } 
          else{
               printf("\n");
               count = 1;
          }
     }
	}
     printf("\n\n"); 

	if(i == 1){ 
     printf("Linked List in descending order\n");
     currN = tail;
     int count2 = 1;
     prevN = (struct node *) currN->link;
     nextN = NULL;
     while (currN!=NULL){
         if(count2 <= 10){
              printf("%-5d", currN->data);
              previNode();
              count2++;
          
          }else{
              printf("\n");
              count2 = 1;
          }
     } 
    } 	
    printf("\n");         
}

void nextNode(){
    nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
    prevN = currN;
    currN = nextN;
}

void previNode(){
    prevN = (struct node *) (currN->link ^ (unsigned long) nextN);
    nextN = currN;
    currN = prevN;		
}

int main(){
    
    int i, num;
    float seed;
    head = NULL; tail = NULL; currN = NULL; prevN = NULL; nextN = NULL;
    
    init_seed(1234567);
    set_range(1,9999);
    //inserting data into the linked list
    for ( i=0; i<100; ++i){
        num = rndm();
        insert( &head, &tail, num );
    }
	
    list((struct node*)head, 0);
	//delete((struct node**)head, (struct node**)tail, 45);
	//delete((struct node**)head, (struct node**)tail, 4040);
	//delete((struct node**)head, (struct node**)tail, 9769);
    list((struct node*)head, 1);
    
    
    return 0;
}

The delete calls i commented out cause segmentation faults.

03-11-2010, 11:35 PM	#2
Salem and the hat of Destiny Join Date: Aug 2001 Location: The edge of the known universe Posts: 22,495	Maybe construct a proper LL with true next/prev pointers you can easily diagnose as being correct or broken. Then leave it like that as the job is done. __________________ If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Salem is offline

03-11-2010, 11:43 PM	#3
seePhor Registered User Join Date: Mar 2010 Posts: 4	so pretty much forget about using XOR LL's?
seePhor is offline

03-11-2010, 11:47 PM	#4
seePhor Registered User Join Date: Mar 2010 Posts: 4	It is definitely narrowed down to my delete function. When I comment out the code for delete, it works fine.
seePhor is offline

03-11-2010, 11:47 PM	#5
Salem and the hat of Destiny Join Date: Aug 2001 Location: The edge of the known universe Posts: 22,495	XOR linked list - Wikipedia, the free encyclopedia I find their disadvantages to be far too numerous. One of which is affecting you, namely the debuggability of them. Like I said, start with a regular DLL, and make sure it works. Then (and only then), if you're still set on an XOR-LL, convert all the next/prev things into a single xor value. Do the conversion by commenting out the real code, so you have a reminder of what it is you're actually doing. __________________ If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Salem is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Why does CppUnit give me seg faults?	cpjust	C++ Programming	3	05-20-2010 03:00 AM
transpose of a 2D array seg faults on non-square arrays	zeebo17	C Programming	4	05-25-2009 09:29 PM
Seg faults. structs. pointers.	ominub	C Programming	12	05-03-2009 07:04 PM
Help with arrays and seg faults	IdioticCreation	C++ Programming	7	04-03-2008 03:16 PM
sorted linked list...why seg faults!	S15_88	C Programming	4	03-24-2008 11:30 AM