Using XOR to implement doubly linked list with one pointer per node

Question

I'm having trouble with XOR doubly link list that has one pointer that must be contain NEXT and PREV pointers of nodes. I must xor address of pointers to do so, but I can't. I can allocate a memory address that XORed from two address but I can't get value to its address (this has segmentation fault error):

int main(){
    int* ptr = new int;
    int *ptr2 = new int;
    ptr2 = (int*)((unsigned long)ptr ^ (unsigned long)ptr2);
    *ptr2= 5;        /here has segmentation fault
    cout <<*ptr2;    
    return 0;

Why does this code have an error? How can I fix it?

thanks for your response but I cant transfer my idea I say my question in other words: normally we have a pointer that allocate the space of memory to it by "new" (in c++) keyword. this address that reserve for our pointer is determine by the os,correct? for example the address that pointer points to it is 0x8f3400b (this is where the memory is free that can reserve) I want to do that manually by addressing not with new keyword like this code:

int* ptr1 = (int*) 0x2355;
int* ptr2 = (int*) 0x23ff;

now i dont know the address 0x2355 and 0x23ff can be reserved or not ? then i decide that "new" these pointers and then XORing them, like below:

int* ptr1 = new int     //ptr1 is now manage by OS
int* ptr2 = new int     //like ptr1 ...

then I want XORing these pointers and make a new space to append a node that is the third node but i cant the addressing of it is correct but when i want to valuing it segmentation fault occured:

int* ptr1 = new int;    // for example the address is X
int* ptr2 = new int;    // for example the address is Y
int* ptr3 = (int*)((unsigned long)ptr1 ^ (unsigned long)ptr2);    //the final address is X^Y

how can i correct this? i dont know how use intptr_t and other please help me thanks

I assume you're attempting to do this? en.wikipedia.org/wiki/XOR_linked_list — Greg Hewgill
– Greg Hewgill, Commented Dec 29, 2011 at 22:08
Do not laugh at it: there is such a thing as a XOR linked list, which does actually involve XORing pointers together. This guy is probably trying to work with such a list. I wish I could understand what he is trying to say, it could have been interesting. If only it was in English. — Mike Nakis
– Mike Nakis, Commented Dec 29, 2011 at 22:10
@GregHewgill: Even that article has <quote> This form of linked list may be inadvisable: </quote> — Loki Astari
– Loki Astari, Commented Dec 29, 2011 at 22:29

Keith Thompson · Accepted Answer · 2011-12-29 22:14:24Z

9

There's a really ugly trick that (if it works) lets you implement a doubly linked list with only one pointer per node. As you say, it requires xor'ing pointer values.

This Wikipedia article discusses it.

It's almost always a really really bad idea. The language does not guarantee that it will work at all.

If you must do this, cast the pointer values to uintptr_t or intptr_t (those types aren't even guaranteed to exist, but they probably will), declared in <stdint.h> or <cstdint>.

The result of xor'ing two pointer values will not be a valid pointer, and any attempt to use it as one will blow up in your face (if you're lucky). The only way to get a valid pointer back from such an operation is to reverse it, getting back the original pointer value. It's not surprising that your *ptr2 = 5; causes a segmentation fault.

If you're doing this as an exercise, just to see if you can get it to work, by all means go ahead and have fun.

If you think you have some practical requirement for this, you don't. If you want a doubly linked list, just have two pointers per node. Or, better yet, since you're programming in C++, use one of the standard library container classes.

answered Dec 29, 2011 at 22:14

Keith Thompson

266k46 gold badges447 silver badges668 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

marcinj Over a year ago

"The language does not guarantee that it will work at all." can you elaborate on that? if pointers are reinterpret_cast then later you only have to do mathematics on integers? this should be safe and on embeded systems can save some memory

Keith Thompson Over a year ago

@luskan: If you store the xor'ed pointer value into a pointer object, it could be a trap representation, or the act of storing it could change its representation by normalizing it. If you only store the xor'ed value in an object of type uintptr_t or intptr_t, you're ok, as long as the only uintptr_t values you ever convert back to pointer type are identical to values derived by converting valid pointer values to [u]intptr_t. But I think the technique actually requires storing the xor'ed values as pointers.

David Rodríguez - dribeas Over a year ago

@KeithThompson: The technique does not require storing the values as pointers, it only tries to reach a compromise where less memory is used at the cost of more processing. The datum to be stored can be a pointer or an integral type (which might require more processing in some platforms --if data/addresses have to be stored in different registers) but the idea is that if you care more about the memory footprint you can reduce it a bit.

Basile Starynkevitch · Accepted Answer · 2011-12-29 22:02:32Z

0

Never do that

If you absolutely want to cast pointers to some integer type, use intptr_t at least (provided by <cstdint> or <stdint.h> header file).

Why do you want to xor pointers? It is an ugly trick! It sort-of disable compiler optimizations.

answered Dec 29, 2011 at 22:02

Basile Starynkevitch

231k18 gold badges323 silver badges578 bronze badges

1 Comment

Bohdan Mart Over a year ago

It won't disable compiler optimizations in itself. But indeed it could cause slowdown. How big? Need to measure. But it would allow to save memory. Useful in some cases.

Prabhakaran · Accepted Answer · 2013-04-25 09:28:04Z

using turbo C version 3.0, we have implemented Doubly linked list with one pointer taking advantage of XOR. Pass your comments.... 'C' the Change Team of FINDMIND.

/* Code developed by 'C' The Change Team of FINDMIND
   Prabhakaran D, Vaishnavi N K, N N Priya, guided by
   Mr.Sridhar Arumugaswamy */

#include <stdio.h>
#include <conio.h>

struct Node {
   int data;
   unsigned int next;
}*start, *end, *newNode;

typedef struct Node NODE;

int menu(){
   int choice;
   clrscr();
   printf("1.Add\n2.Display\n3.Exit\n");
   scanf("%d", &choice );
   fflush(stdin);
   return choice;
}

void add() {
   clrscr();
   newNode = ( NODE * ) malloc ( sizeof( NODE ) );
   newNode -> next = 0;
   printf("Enter the data to enter :");
   scanf("%d", &(newNode -> data) );
   fflush(stdin);
   if( start == NULL ) {
      start = end = newNode;
   } else {
      newNode -> next = (unsigned int)end ^ 0;
      end -> next = ( end -> next ^ 0 ) ^ ( unsigned int)newNode;
      end = newNode;
   }
}

void display() {
   NODE *temp, *curr, *prev;
   prev = curr = temp = NULL;
   clrscr();
   for ( curr = start; curr != end ; temp = prev ,\
   prev = curr , curr = ( NODE * ) ( curr -> next ^ (unsigned int)temp ) )
      printf("%d\n", curr -> data );
   printf("%d\n", curr -> data );
   getch();
}

void main() {
   int choice;
   choice = menu();
   do {
      switch( choice ) {
     case 1: add();
         break;
     case 2: display();
         break;
     case 3: printf("\n\nBye!!!");
         break;
     default: printf("Bug dude!!!");
      }
      choice = menu();
   } while(choice != 3);
}

Collectives™ on Stack Overflow

Using XOR to implement doubly linked list with one pointer per node

3 Answers 3

3 Comments

Never do that

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Never do that

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related