Two-way link list
I am trying to create an efficient double linked list. The list stores the XOR of the next and previous addresses, but I am running into an error in the function XOR
. Mistake:
[Error] cast from 'node*' to 'unsigned int' loses precision [-fpermissive]
My code:
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
node *next;
}*start,*temp;
node* XOR(node *a,node *b)
{
return (node *)((unsigned int)(a)^(unsigned int)(b));
}
void push(int data)
{
node *a=new node;
a->data=data;
a->next=XOR(start,NULL);
if(start!=NULL)
start->next=XOR(start->next,a);
start=a;
}
void disp()
{
temp=start;
node *prev,*cur;
while(temp)
{
cout<<temp->data<<" ";
if(temp==start)
{
prev=temp;
temp=temp->next;
}
else
{
cur=temp;
temp=XOR(temp->next,prev);
prev=cur;
}
}
}
main()
{
start=NULL;
push(1);
push(2);
push(3);
push(4);
push(5);
push(6);
push(7);
push(8);
}
source to share
An is unsigned int
not guaranteed to be as large as a pointer, in many cases a pointer is 64 bits and unsigned int
32 bits. Therefore, in this case, the upper 32 bits will be discarded, which will invalidate the pointer. You need uintptr_t
instead unsigned int
.
The corrected code should come first:
#include <cstdint>
Somewhere at the top to add a declaration for uintptr_t
, as well as many other useful types, and then change the line:
return (node *)((unsigned int)(a)^(unsigned int)(b));
To:
return (node *)((uintptr_t)(a)^(uintptr_t)(b));
Please take a look here for a much better explanation of how uintptr_t and other similar types work http://www.cplusplus.com/reference/cstdint/
Finally, I mentioned that on most modern machines, a xored linked list will actually be slower, not faster than a regular double linked list, as this method makes it much harder for the processor and compiler to predict what you are doing and optimize well this the effect is greater than accelerating speed while saving little space.
source to share
You must use the uintptr_t
one defined in #include <cstdint>
.
The very purpose uintptr_t
is to hold the pointer void*
and convert back without losing precision.
Using
uintptr_t XOR(node *a,node *b)
{
return reinterpret_cast<uintptr_t>(a)^reinterpret_cast<uintptr_t>(b);
}
I would not reverse it back to node*
until you return to uintptr_t
, which is a valid pointer.
I don't believe it clearly defined what happens when you create uintptr_t
that was not directly hidden from pointer to pointer.
source to share