Experimenting with XOR-linked lists

main.c

#include <stdio.h>
#include "xorlist.h"

int main(void) {
  struct Node *list = NULL;

  for (int i=1; i<=15; i++) {
    push(i, &list);
  }

  for (int i=0; i<4; i++) {
    printf("Pop! %d\n", pop(&list));
  }

  print_elems(list);

  kill_list(list);
  return 0;
}

xorlist.c

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

struct Node {
  int value;
  unsigned long prev_xor_next;
};

// Either connects or disconnects the chain [prev, node, next].  That is, if
// the chain is currently [prev, next], then the new chain is
// [prev, node, next].  If it is currently [prev, node, next], then the new
// chain is [prev, next].  *ONLY* alters `prev` and `next`!
void internal_dis_connect(struct Node *prev, struct Node *node, struct Node *next) {
  if (prev != NULL) { prev->prev_xor_next ^= REF(next) ^ REF(node); }
  if (next != NULL) { next->prev_xor_next ^= REF(prev) ^ REF(node); }
}

// Inserts a node with value `value` between `prev` and `next`, repointing the
// aforementioned nodes to include the newly-created one.  Returns the
// newly-created node (whose value is `value`).
//   `prev` and `next` *must* be adjacent.
struct Node *insert_between(int value, struct Node *prev, struct Node *next) {
  // Prepare the new node...
  struct Node *node = malloc(sizeof(struct Node));
  node->value = value;
  node->prev_xor_next = REF(prev) ^ REF(next);

  // Xor out old pointer (`prev` or `next`), xor in `new`.
  internal_dis_connect(prev, node, next);

  return node;
}

// Removes the node `node` that is assumed to be preceded by `prev`.
void remove_node(struct Node *node, struct Node *prev) {
  struct Node *next = NEXT_PTR(node, prev);

  // Xor out `node`, xor in new pointer (`prev` or `next`).
  internal_dis_connect(prev, node, next);

  free(node);
}

// Kills the whole list starting with the edge-node `node`.
void kill_list(struct Node *node) {
  struct Node *prev = NULL, *tmp;

  while (node != NULL) {
    tmp  = NEXT_PTR(node, prev);
    prev = node;

    free(node);
    node = tmp;
  }
}

// Prints each element of the list starting with the edge-node `node`.
void print_elems(struct Node *node) {
  struct Node *prev = NULL, *tmp;

  printf("\n"
         "    value         &node             xor            &next\n"
         "  ----------------------------------------------------------\n");

  while (node != NULL) {
    printf("  - %3d %16p %16p %16p\n",
           node->value, node, (void *)node->prev_xor_next, NEXT_PTR(node, prev));

    // (prev, node) = (node, NEXT(node, prev))
    tmp = NEXT_PTR(node, prev);
    prev = node;
    node = tmp;
  }
}

// Pushes a value to `*list`, updating `*list` to point to the new head of the
// list.
void push(int value, struct Node **list) {
  *list = insert_between(value, *list, NULL);
}

// Pops a value from `*list`, updating `*list` to point to the new head of the
// list and returning the value that was previously the head.
int pop(struct Node **list) {
  struct Node *old_head = *list;
  int res = old_head->value;

  *list = NEXT_PTR(old_head, NULL);

  remove_node(old_head, NULL);
  return res;
}

xorlist.h

#ifndef XORLIST_H
#define XORLIST_H

#define REF(ptr) \
        ((unsigned long) (ptr))
#define IS_LAST_PTR(node) \
        ((node)->prev_xor_next == REF(NULL))
#define NEXT_PTR(node, prev) \
        ((struct Node *) ((node)->prev_xor_next ^ REF(prev)))

struct Node;

// The main interface to the nodes.
struct Node *insert_between(int, struct Node *, struct Node *);
void remove_node(struct Node *, struct Node *);

// Helpers to act on all elements of a list.
void kill_list(struct Node *);
void print_elems(struct Node *);

// Helpers to provide a stack-like interface.
void push(int, struct Node **);
int pop(struct Node **);

#include "xorlist.c"
#endif