Doubly link list

Question

I am trying to make a memory efficient doubly linked list. The list stores the XOR of the next and the previous addresses, but I am facing an error in the function XOR. The error is:

[Error] cast from 'node*' to 'unsigned int' loses precision [-fpermissive]

My code is:

#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);
}

some criticism: ... you should really use the usual standard headers. In your case that would be for now. also main() is C. the implicit int is not a C++ feature and thus your main should atleast be `int main()`. now your error: you are compiling for 64 bits but unsigned int is 32. to make it portable include and use std::uintptr_t. — Felix Bytow, Jul 22 '15 at 09:54
Also, see: [question 1](http://stackoverflow.com/questions/25489286/error-cast-from-void-to-int-loses-precision-fpermissive-in-makefile), [question 2](http://stackoverflow.com/questions/1640423/error-cast-from-void-to-int-loses-precision), [question 3](http://stackoverflow.com/questions/2024895/how-should-i-handle-cast-from-void-to-int-loses-precision-when-compiling) — stgatilov, Jul 22 '15 at 09:54

Vality · Accepted Answer · 2015-07-22T09:59:02.083

An unsigned int is not guaranteed to be as large as a a pointer, in many cases a pointer is 64 bits and an unsigned int 32 bits. Therefore in this case the upper 32 bits are discarded, invalidating the pointer. You need a uintptr_t instead of an unsigned int.

The corrected code must first:

#include <cstdint>

Somewhere at the top in order to add a declaration for uintptr_t as well as a variety of other useful types and second 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 shall mention that in most modern machines a xored linked list will actually be slower, not faster than a normal doubly linked list as the technique makes it much harder for the CPU and compiler to predict what you are doing and optimise well and this effect is greater than the speed boost from small space saving.

Persixty · Answer 2 · 2015-07-22T09:57:11.943

You should use uintptr_t defined in #include <cstdint>.

The very purpose of uintptr_t is to be capable of holding a void* pointer and being converted back without loss of precision.

Use

uintptr_t XOR(node *a,node *b)
{
    return reinterpret_cast<uintptr_t>(a)^reinterpret_cast<uintptr_t>(b);   
}

I wouldn't then cast that back to node* until you eventually return to a uintptr_t that is the valid pointer.

I don't believe it's well defined what happens when you cast a uintptr_t that wasn't directly cast from a pointer to a pointer.

Doubly link list

2 Answers2