Thread: xor linked list

i have a delema with my xor linked list program....now i keep getting the bottom error i will also get segmentation errors throughout the insert function!!!


i have the list commented out at all times....the only thing it will do right now is input numbers!!

and will output the number being passed in...and then what the head is afterwards...
this is the source code revised again:

Code:

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

#define MAX_NUMBERS 100

typedef struct _node{
        int data;
        unsigned long link;
} node;//end node

node *tmp, *head, *tail, *next, *prv, *cur;

void  insert(insertNum){
        printf("This is the random number passed in %d\n", insertNum);
        node *nekw = (node *)malloc(sizeof(node));
        nekw->data = insertNum;
        printf("this is the number inputed %d\n", nekw->data );
        cur = head;
        prv = NULL;
        while(cur != NULL && cur->data < insertNum){
                next = (node *)(cur->link ^ (unsigned long)prv);
                prv = cur;
                cur = next;
        }//end while loop
        if(prv == NULL){
                head = nekw;
        }//end if statement.
        else{
                nekw->link ^= (unsigned long) prv ^(unsigned long) cur;
                prv->link ^= (unsigned long) cur ^ (unsigned long) nekw;
                cur->link ^= (unsigned long) prv ^ (unsigned long) nekw;
        }//end else statement.
}//end insert.

void delete(int deleteNum){
        printf("I am in the delete function!\n");
        cur = head;
        printf("This is in cur before i start %2.1d\n", cur->data);
        prv = NULL;
        while(cur != NULL && (cur->data != deleteNum)){
                prv =(node *)(cur->link ^ (unsigned long)next);
                prv = cur;
                cur = next;
        }//end while loop
        if(cur != NULL && (cur->data == deleteNum)){
                printf("this is what was found %2.1d\n", cur->data);
                prv->link ^= (unsigned long) prv ^ (unsigned long) cur;
                next->link ^= (unsigned long) cur^ (unsigned long) next;
                free(cur);
        }//end if statement.
}//end delete.

 void list(int option){
        int cnt = 1;
        if(option == 1){
                cur = head;
                prv = NULL;
                printf("This is the list in acending order: \n");
                while(cnt <= MAX_NUMBERS){
                        printf("%3.1d", cur->data);
                        cnt++;
                        if(cnt % 10 == 0){
                                printf("\n");
                        }//end if statement
                        prv =(node *)(cur->link^(unsigned long)next);
                        prv = cur;
                        cur = next;
                }//end while loop
        }//end if
        else if(option == 2){
                cur = tail;
                next = NULL;
                printf("This is the list in decending order: \n");
                if(cnt % 10 == 0){
                        printf("\n");
                }//end if statement.
                while (cnt <= MAX_NUMBERS){
                        printf("%3.1d", prv->data);
                        cnt++;
                        if(cnt % 10 == 0){
                                printf("\n");
                        }//end if statement.
                        prv = (node *)(cur->link^(unsigned long) prv);
                        next = cur;
                        cur = prv;
                }//end while loop.
        }//end else if
}//end list.

int main(){
        head = NULL;
        tail = head;
        long inputZ;
        int num, option,cnt, beginning, end;
        int numDelete;
        printf("Please enter the seed: ");
        scanf("%l\n", &inputZ);
        init_seed(inputZ);

        printf("Please enter the range: ");
        scanf("%d%d\n", &beginning, &end);
        set_range(beginning, end);

        for(cnt=0; cnt <= MAX_NUMBERS; cnt++){
                insert(rndm());
        }//end for loop.
#if 0
        printf("For ascending press 1, or 2 for decending: ");
        scanf("%d\n", &num);
        list(num);

        numDelete = 7004;
        delete(numDelete);

        printf("For ascending press 1, or 2 for decending: ");
        scanf("%d\n", &num);
        list(num);
#endif
        return 0;
}//end main.

here is my output:

Code:

> gcc linkList.c rndm.o
>ls
a.out*  lab1/  lab2/  linkList.c  rndm.h  rndm.o
> a.out
Please enter the seed: 12345
Please enter the range: 1 9999
This is the random number passed in 3995
this is the number inputed 3995
This is the random number passed in 10463
this is the number inputed 10463
Segmentation fault
>

i don't understand what is going wrong....the only time the input should really brake down is the first one inserted and if a number inputed into a list of nodes is less than the first node then i have a problem....otherwise i should just be inserting nodes that have different numbers that are less than the next one!! but it seems to break down before i even insert a number!!!

well i was thinking because i am using dynamic variables that would be wanting to use malloc??

using the stdio.lib size of function...ohh and this is a homework assignment so i don't have much say in the matter of just not doing a xor linked list!!

i ran this gcc -W -Wall -ansi -pedantic -O2 linkList.c

what does it do it gave me hella errors!

Originally Posted by matsp

So fix those (and ask here if you don't understand what it means).

As to "you don't have a choice", Ok, fine - I just wanted to tell you that the "clever" trick is now so clever that the compiler/processor is getting confused and thus the code is actually worse than a straight/simple swap operation - it is not a good idea to use this in REAL CODE - and thus I doubt that it's a good idea for your teacher to teach you that sort of thing. You may get the impression that it's a good idea to do things this way.

--
Mats

Matsp made a similar comment that I copied and pasted off another website (I think it was a strrev() function or something). Even though the code wasn't mine and I wasn't disputing the merits of his claims, he did go through the trouble of proving that the xor technique does suffer a performance ding.

Originally Posted by adramalech

using the stdio.lib size of function

sizeof is not in stdlib.h. It's a compile-time operator.

I don't see you changing head anywhere. So that would appear to always and forever be NULL. (You set cur to nekw, but who cares?)

thanks...that was an eye opener it took me some time but i figured out that i forgot to set head and some of the others to what was made!!!

Why does your walk the list code look different in insert and print? Insert has

Code:

next = (node *)(cur->link ^ (unsigned long)prv);
prv = cur;
cur = next;

shouldn't that be where your trouble section is?

well see i am incrementing a pointer to next so i can traverse the list....those three lines are how i would traverse the list and i then output what is in cur->data until i get to the end...

it is very simple but it seems i am screwing something small up!!!

Originally Posted by adramalech

well see i am incrementing a pointer to next so i can traverse the list....those three lines are how i would traverse the list and i then output what is in cur->data until i get to the end...

Exactly: those three lines are how you traverse the list. Since that's not what you have in your "traverse the list' section where the error is, why do you not fix it?

well i don't know what i should have....i can just traverse it but without printing out at every time i increment cur i won't have a list function!!!

i thought that:

next = (node *)(cur->link ^ (unsigned long) prv);

was all i needed to make next pointer point to the next node!!

and then

prv = cur;

is just incrementing the prv pointer to where cur was...

then increments cur:

cur = next;


so what i am asking is how could i make the next pointer actually increment to the next node that is actually in the list???

should i do this???

next = (node *)(next->link ^ (unsigned long) cur);