XOR Doubly Linked List

Question

So I am trying to create a XOR Doubly Linked List as part of an exercise, but I keep getting a Segmentation fault on my removeFirst() function. I cannot figure out what is going wrong, does anybody have a clue?

This is what a node looks like:

class Node{

public:
    int data;
    Node *XOR;

};

I am using this function to calculate the XOR:

Node* returnXOR(Node *a, Node *b){
    return (Node*)((uintptr_t) (a) ^ (uintptr_t) (b));
}

This is my XOR Doubly Linked List class:

class XORDLL{

public:
Node *head;

XORDLL(){
    head = NULL;
}

void addFirst(int data){
    // Make a newNode pointer
    Node *newNode = new Node;

    // Set the variables
    newNode->data = data;
    newNode->XOR = returnXOR(head, NULL);   

    // If the head is not empty set the XOR of the head to the next XOR the newNode
    if(head != NULL){
        head->XOR = returnXOR(newNode, returnXOR(head->XOR, NULL));
    }   

    // Set the newNode to the head 
    head = newNode;
}

void removeFirst(){
    // If head is equal to NULL, do nothing
    if(head == NULL){
        return;
    }
    // Store current head
    Node *tmp = head;

    // Set head equal to the next address
    head = returnXOR(tmp->XOR, NULL);
    head->XOR = returnXOR(tmp->XOR, tmp);


    // Delete tmp variable
    delete tmp;
}

void printList(){
    Node *current = head;
    Node *prev = NULL;
    Node *next;
    while(current != NULL){
        printf("%d ", current->data);
        next = returnXOR(current->XOR, prev);
        prev = current;
        current = next;           
    }
    printf("\n");
}
};

When I run this piece of code:

int main(){
    XORDLL l;
    l.addFirst(1);
    l.addFirst(2);
    l.addFirst(3);
    l.printList();
    l.removeFirst();
    l.printList();
    return 0;
}

This is the output:

3 2 1 Segmentation fault (core dumped)

You `returnXOR` function takes the raw memory address of two existing `Node`s, XORs the two raw memory addresses, and casts the result to a pointer to another `Node`. Unfortunately, the actual chance of the resulting memory address being a valid pointer to a `Node` are slim to none. Hence your crash. This is like taking the geographic longtitude and lattitude of two oasis in the African desert, exclusive-or the numeric longtitude/lattitude, travel to the new set of coordinates, and expecting to find a third oasis, there. — Sam Varshavchik, Jan 08 '19 at 13:24
That was what I was thinking as well, but why does my printList() function work correctly, when using the same method. — Jorn van der Maat, Jan 08 '19 at 13:25
Because, if you work out the math, that code always ends up visiting two valid nodes, then computing a NULL value (first XOR with null, XOR with 0, does nothing; and the next iteration XORs a memory address with itself, producing a NULL). You got very lucky there. BTW, `delete current, prev, next;` does not do what you think it does. It does not, I repeat, does not, delete three pointers. It seems that it would be a good idea to [spend a little bit more time reading a good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Jan 08 '19 at 13:29
Thanks for the information, I will have to sort that out for myself. — Jorn van der Maat, Jan 08 '19 at 13:37
@JornvanderMaat `Node *newNode = (Node*) malloc (sizeof(Node));` -- Why are you using `malloc` in a C++ program? The code exhibits undefined behavior, since `Node` is not a POD type. Your code does not construct `Node` objects -- in C++, `operator new` is used to dynamically construct types. All `malloc` does is allocate bytes -- it does not construct objects. — PaulMcKenzie, Jan 08 '19 at 13:48

grungegurunge · Accepted Answer · 2019-01-08T13:47:58.940

0

You delete the malloc'ed data. You need to free it instead, or use new instead of malloc. Another bug is that you miss this line:

          void removeFirst(){
          // If head is equal to NULL, do nothing
          if(head == NULL){
              return;
          }
          // Store current head
          Node *tmp = head;

          // Set head equal to the next address
          head = returnXOR(tmp->XOR, NULL);
          head->XOR = returnXOR(head->XOR, tmp); <<<<<<<<<<<<<<<<<< Here

          // Free tmp variable
          free(tmp);
      }

edited Jan 08 '19 at 13:47

answered Jan 08 '19 at 13:29

grungegurunge

841
7
13

Although this is also true, this is the least of the many, many problems with the shown code. – Sam Varshavchik Jan 08 '19 at 13:30
So I changed my code to get rid of the delete statements and used free, but I still get the same output. – Jorn van der Maat Jan 08 '19 at 13:40
Fixed another bug : ) – grungegurunge Jan 08 '19 at 13:48
There should be no call to `malloc` to begin with as it is totally wrong for the `Node` data type. Thus you should not encourage usage of `free`. – PaulMcKenzie Jan 08 '19 at 13:51
I would say that there should be no calls to ```new``` either. But when you work on low level XORing pointers, I think ```malloc``` is not a big problem, as it's not really C++, it's just C. – grungegurunge Jan 08 '19 at 13:53
The code exhibits undefined behavior, as `malloc` cannot be used on the `Node` type, as it is not a POD type. So there is no `node->XOR` or `node->data` that properly exists that makes sense. – PaulMcKenzie Jan 08 '19 at 13:56
Changed my code again using new instead of malloc, makes no difference. – Jorn van der Maat Jan 08 '19 at 13:58
Hey, did you add the line from the code above? It works for me now. And if you switched to ```new```, did you change ```free``` to ```delete``` also? – grungegurunge Jan 08 '19 at 14:02
@JornvanderMaat -- The point is that the code was wrong to begin with. You cannot use `malloc` to instantiate or create non-POD types. – PaulMcKenzie Jan 08 '19 at 14:11
@grungegurunge I edited my code again to match yours and changed free to delete, but it is still not working. Am I missing something? – Jorn van der Maat Jan 08 '19 at 14:15
@PaulMcKenzie Ah I see, thanks for pointing that out, learned something new today :). – Jorn van der Maat Jan 08 '19 at 14:16
Yes, that works for me as well, must be a small error in my old code. Big thanks man :) – Jorn van der Maat Jan 08 '19 at 14:39

XOR Doubly Linked List

1 Answers1

Linked