CODEWITHSUNDEEP
pointersgobit-manipulationxor
dannyBoy
dannyBoy

Reputation: 67

Bitwise XOR on address in GoLang

I was trying to implement the XOR Linked List in Go where I had to store the XORed address. In C/C++ it's quite simple

(*struct_type)(([unsigned] int)nodeA ^ ([unsigned] int)nodeB)

I tried a similar approach in Go. I had a struct named Node with two nodes nodeA and nodeB. To get this I tried the following ways:

*Node(uint(nodeA) ^ uint(nodeB))

Which gave me an error saying, can't convert type Node to uint. Another way I tried, which I was sure woundn't work, was

nodeA ^ nodeB

Is there a way to parse the address to int type, XOR them and then re-parse them into Node address? Or does Go provide a simple solution to this that I'm not aware of?

Upvotes: 2

Views: 1788

Answers (3)

Thundercat
Thundercat

Reputation: 121119

Use unsafe.Pointer for pointer arithmetic:

a := &T{}
b := &T{}
x := uintptr(unsafe.Pointer(a)) ^ uintptr(unsafe.Pointer(b))
y := (*T)(unsafe.Pointer(uintptr(unsafe.Pointer(a)) ^ x))
fmt.Println(b == y)  // prints true

The GC uses pointers to track memory. If the code is rewritten to 

a := &T{}
b := &T{}
x := uintptr(unsafe.Pointer(a)) ^ uintptr(unsafe.Pointer(b))
b = nil // clear all pointers to struct
b = (*T)(unsafe.Pointer(uintptr(unsafe.Pointer(a)) ^ x))

then it's possible for the GC to collect the struct pointed to by b before the last assignment to b.

It's not possible to implement a safe XOR list in Go because the GC can collect the elements.

Don't do this.

Upvotes: 4

dannyBoy
dannyBoy

Reputation: 67

Thank you for pointing out that Go doesn't support pointer arithmetic. I did a quick research and, found and used the usafe package Go provides just in case "unsafe" work in needed. I solved the problem with the following lines of code:

a := unsafe.Pointer(nodeA)
b := unsafe.Pointer(nodeB)
return (*Node)(unsafe.Pointer(uintptr(a) ^ uintptr(b)))

The docs to unsafe package.

Upvotes: 1

peterSO
peterSO

Reputation: 166815

You can't implement an XOR Linked List in Go. The Go garbage collector (GC) uses pointer values to keep track of in-use memory. If you mangle a pointer value, the GC will not work.

Upvotes: 3

Related Questions