C code for XOR linked list

Question

I have been trying to implement XOR linked list and its operations but I have not been able to do it properly.

Is it possible to implement it in C since XOR link list involves operations on addresses?

I would be very thankful if some actual working code is given.

Answer 1

That's an interesting idea that I have not seen before. With today's fairly abundant memory, it seems like a lot of complexity for little gain (although not all platforms are flush with memory). Edit While doing my real work, my mind kept drifting back to it, so I added the function to create the new node and put it on the given end. Prettier now. It's rather cool that both the addnode and traverse functions are symmetrical. Neither needs to know the direction. Just give it one end of the list and they operate correctly.

And based on Darron's comment (thanks), I changed the int to intptr_t for portability.

#include <stdio.h>
#include <malloc.h>
#include <stdint.h>  // gcc needs this for intptr_t.  

typedef struct xorll {
   int  value;
   struct xorll  *np;
}  xorll;


// traverse the list given either the head or the tail
void traverse( xorll *start )  // point to head or tail
{
   xorll *prev, *cur;

   cur = prev = start;
   while ( cur )
      {
      printf( "value = %d\n", cur->value );
      if ( cur->np == cur )
         // done
         break;
      if ( cur == prev )
         cur = cur->np;   // start of list
      else {
         xorll *save = cur;
         cur = (xorll*)((uintptr_t)prev ^ (uintptr_t)cur->np);
         prev = save;
         }
      }
}

// create a new node adding it to the given end and return it
xorll* newnode( xorll *prev, xorll *cur, int value )
{
   xorll *next;

   next = (xorll*)malloc( sizeof( xorll ));
   next->value = value;
   next->np = cur;  // end node points to previous one

   if ( cur == NULL )
      ; // very first node - we'll just return it
   else if ( prev == NULL ) {
      // this is the second node (they point at each other)
      cur->np = next;
      next->np = cur;
      }
   else {
      // do the xor magic
      cur->np = (xorll*)((uintptr_t)prev ^ (uintptr_t)next);
      }

   return next;
}



int main( int argc, char* argv[] )
{
   xorll *head, *tail;
   int   value = 1;

   // the first two nodes point at each other.  Weird param calls to
   // get the list started
   head = tail = newnode( NULL, NULL, value++ );
   tail = newnode( NULL, tail, value++ );

   // now add a couple to the end
   tail = newnode( tail->np, tail, value++ );
   tail = newnode( tail->np, tail, value++ );

   // this is cool - add a new head node
   head = newnode( head->np, head, 999 );


   printf( "Forwards:\n" );
   traverse( head );
   printf( "Backwards:\n" );
   traverse( tail );


}

Answer 2

Since you cannot perform xor operations on pointers, you will have to convert the addresses to an integer type to perform the xor and convert the result back to to right pointer type.

As far as I know C99 has only two integer types that guarantee conversion to and from pointers with defined behaviour (= getting your original pointer back): intptr_t and uintptr_t from <stdint.h>. Note that both types are optional, so your implementation might not have them.

Example of conversions, assuming a and b are valid pointers to struct node:

#include <stdint.h>

/* creating an xor field */
uintptr_t x = (uintptr_t) (void *) a ^ (uintptr_t) (void *) b;
/* reconstructing an address */
a = (void *) (x ^ (uintptr_t) (void *) b);

I'm not 100% sure the extra casts to void * are needed, somebody please correct me if they are not. See §7.18.1.4 of the C99 standard for more information on the (u)intptr_t types.

Answer 3

Is it possible to implement it in C since XOR link list involves operations on addresses??

Yes it is. Addresses are pointers, pointers are numbers* and numbers allow XOR (i.e. a ^ b).

Look up what is done, and you should be able to do the implementation.

*At least, you can think of them as numbers - explicit casts might be required though.