Working with XOR and linked list

[hartmannr76]

(Im doing this project in C and so using all structs in this program)

Ok so I understand how XOR works and all but what is confusing me:

-I have a node constructed that has a struct XORListNode *nextXORPrev; statement. Im trying to append a node to the beginning of the list with the following code...

int pointSize = sizeof(XORListNode);
	XORListNode *nodeToAdd = malloc(pointSize);
	nodeToAdd->data = dataToAdd;
	nodeToAdd->nextXORPrev ^= (XORListNode*)NULL ^ (XORListNode*)list->tail->nextXORPrev;

but im not sure if this is adding it right... would someone be able to explain how to add a node to a list like this in C...

- My next question... how would i traverse the list... i see code that shows like...

nodeToAdd->nextXORPrev ^= (XORListNode*)NULL ^ (XORListNode*)list->tail->nextXORPrev;

but i would have thought this adds to the list?? can someone help me out here??

Thank you for your time!!

[writetonsharma]

why are you xoring the next linked list pointer??
dont know if i am missing something!!


will this wont do?
list->tail->nextXORPrev = nodeToAdd;

[hartmannr76]

I just dont understand how you can setup 2 addresses in the XOR Node variable, like right now it doesnt make sense

[Duthomhas]

You shouldn't be XORing pointers. You'll smash your memory.

The best way to figure out linked lists is to get out a piece of paper and pencil and draw yourself little boxes (representing nodes) and arrows (representing pointers), then adjust the arrows to do what you want. Then make the code do the same thing.

Good luck!

[hartmannr76]

If i didnt have to use them I promise you i wouldnt lol, i have to do it for a school homework assignment, i know how linked lists work and i know the concept behind XOR i just dont know how to apply it...

[PanGalactic]

Never heard of this before, but Wikipedia has a good explanation. http://en.wikipedia.org/wiki/XOR_linked_list

An important note from the Wikipedia entry:

XOR of pointers is not defined in some contexts (e.g., the C language), although many languages provide some kind of type conversion between pointers and integers;

You probably need to define the nextXORPrev as a long rather than a pointer type.

[Duthomhas]

Ah, I never figured on doing something so, well, silly.

The way the addresses are stored is this:

1) nextXORPrev = next ^ prev;

In order to get one pointer out, you need to know both the other pointer and the XORed field. That is:

2) prev = nextXORPrev ^ next; // to get 'prev' I had to know everything on the right hand side

3) next = nextXORPrev ^ prev; // likewise, to get 'next' I had to know both 'prev' and 'nextXORPrev'


If you want to change one of the pointers, you must first obtain the pointer you wish to keep (using either equation 2 or 3) and then recombine the new pointer and the one you wish to keep using equation 1.

You will also have to do some casting between pointer and integer types. Here is an example to help you out:

#include <stdio.h>
#include <string.h>

/* XORPtr() ------------------------------------------------------------------
 *
 * This little function makes it convenient to XORs two char pointers.
 */
char* XORPtr( char* a, char* b )
  {
  return (char*)(
    (unsigned long)a ^ (unsigned long)b
    );
  }

/* printAB() -----------------------------------------------------------------
 *
 * This function prints the characters indexed by the XORed pointer.
 */
void printAB( char* ab, char* a )
  {
  char* b = XORPtr( ab, a );

  printf( "  *a = '%c'\n",   *XORPtr( ab, b ) );
  printf( "  *b = '%c'\n\n", *XORPtr( ab, a ) );
  }

/* main() --------------------------------------------------------------------
 */
int main()
  {
  /* Here's the stuff we will point to */
  char abc[] = "ABC";

  /* Here are our pointers */
  char* a = abc;
  char* b = abc + 1;
  char* c = abc + 2;

  /* And here is our combined pointer */
  char *ab = XORPtr( a, b );
  printf( "ab = a ^ b;\n\n" );

  printf( "printAB( ab, a );\n" );
  printAB( ab, a );

  /* Notice that it does not matter which pointer you call 'a' or 'b' */
  printf( "printAB( ab, b );\n" );
  printAB( ab, b );


  /* Now make ab = a ^ c.  Pay close attention here,
   * since we don't actually use 'a' in the calculation. */
  ab = XORPtr( ab, b );  /* first:  ab = a ^ NULL */
  ab = XORPtr( ab, c );  /* second: ab = a ^ c    */
  printf( "\nab == a ^ c;\n\n" );

  printf( "printAB( ab, a );\n" );
  printAB( ab, a );

  printf( "printAB( ab, c );\n" );
  printAB( ab, c );

  return 0;
  }

Make sure to compile and execute this program to see the outputs.

Hope this helps.

[edit] Oh yeah, two things:

1) You can have nextXORPrev stored as a pointer type without any problems, just as in my example above ab is stored as a char*.

2) Do not mix pointer types into the same field. When XORing pointers, make sure that both pointers are identical in type. While you won't have any trouble on a PC, there exists hardware where pointers significantly differ in structure for different types. Don't ask me why. (I don't know -- crazy hardware designers.) Also, you cannot rely on that actually being a NULL on line 53, for more of the same reason -- there exists architectures where a NULL pointer is not zero. Go figure. (Hence, don't try to extract a NULL, since it might not be.)

[edit 2] OK, one more thing.

Above I said that it does not matter which is a and which is b. I meant that in terms of using XOR. In your code, obviously, one must be prev and the other must be next. The point is that if you know one of the two, you can get the other out.

Phew. :-)

[hartmannr76]

Duoas,
Once again thank you soo much!! My professor said no one uses XOR lists in the industry but it doesn hurt to know them which is why he wants us to do them... Thank you again soo very much and I'll get on this code later tonight!! THANK YOU!!! :)!!!