Seg Faults with XOR LL

This is a discussion on Seg Faults with XOR LL within the C Programming forums, part of the General Programming Boards category; I have an issue with the XOR Linked List I have created. It inserts and prints just fine. I can ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    4

    Seg Faults with XOR LL

    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

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    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.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    4
    so pretty much forget about using XOR LL's?

  4. #4
    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.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    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.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User
    Join Date
    Mar 2010
    Posts
    4
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Why does CppUnit give me seg faults?
    By cpjust in forum C++ Programming
    Replies: 3
    Last Post: 05-20-2010, 03:00 AM
  2. Replies: 4
    Last Post: 05-25-2009, 09:29 PM
  3. Seg faults. structs. pointers.
    By ominub in forum C Programming
    Replies: 12
    Last Post: 05-03-2009, 07:04 PM
  4. Help with arrays and seg faults
    By IdioticCreation in forum C++ Programming
    Replies: 7
    Last Post: 04-03-2008, 03:16 PM
  5. sorted linked list...why seg faults!
    By S15_88 in forum C Programming
    Replies: 4
    Last Post: 03-24-2008, 11:30 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21