Using XOR with pointers in C

Question

Last week, our teacher gave us an assignment to make a double linked list in C without using two pointers in the struct; we have to implement it just using one pointer to point to the next and previous node on the list. I'm convinced that the only way of doing so is using XOR to merge the next and previous direction, and then point to that "hybrid" memory allocation, and if I need the directions of prev or next, I can use XOR again to get one of the memory values I need.

I designed the algorithm and I thought it was going to work, but when I tried to implement the solution, I encountered with a problem. When I tried to compile the program, the compiler told me that I couldn't use XOR (^) to pointers:

invalid operands to binary ^ (have ‘void *’ and ‘node *’)

Here is the function to add a node at the front of the list:

typedef  struct node_list{
  int data;
  struct node_list *px;
}  node;

node* addfront ( node *root, int data ){ 
  node *new_node, *next;

  new_node = malloc ( sizeof ( node )); 
  new_node -> data = data;

  new_node -> px = (NULL ^ root);//this will be the new head of the list

  if ( root != NULL ){           // if the list isn't empty
    next = ( NULL ^ root -> px );  // "next" will be the following node of root, NULL^(NULL^next_element).
    root = ( new_node ^ next );    //now root isn't the head node, so it doesn't need to point null.
  }
}

I read that in C++, XOR to pointers is valid. Any ideas of how could implement this in C? I also read somewhere that I needed to use intptr_t, but I didn't understand what to do with it.

Answer 1

#include <stdint.h>

(void *)((uintptr_t)p1 ^ (uintptr_t)p2)

Technically, C does not mandate that void * be able to store any value of uintptr_t; since the value (uintptr_t)p1 ^ (uintptr_t)p2 (let's call it X) is not actually the conversion to uintptr_t of a valid pointer, the implementation-defined conversion of (void *)X back to uintptr_t may not produce the value X, breaking everything you want to do.

Fortunately, this is easily solved by using objects of type uintptr_t rather than void * to store your "xor pointers". Simply do:

uintptr_t xor_ptr = (uintptr_t)p1 ^ (uintptr_t)p2;

and then you can safely recover p1 from p2 (or vice versa) later via:

(void *)(xor_ptr ^ (uintptr_t)p2)

Since the value xor_ptr ^ (uintptr_t)p2 is equal to (uintptr_t)p1, C's definition of uintptr_t guarantees that this value, converted to void *, is equal (as a pointer) to p1 (per C11 7.20.1.4).