Some Interesting Pointer Tricks


I was browsing on Quora when I stumbled across some interesting answers on pointers. They were worth sharing, so here they are with the sources mentioned at the bottom.

 

Encoding information in the low-order bits of pointers.

The setup: The memory addresses of objects are aligned to specific boundaries—generally what we call natural alignment, which means objects are aligned to a memory address that is a multiple of their size. So a 64-bit integer is aligned to an eight-byte boundary;

0x7fff315470d8

is a proper

long

pointer on x86-64 but

0x7fff315470d9

is not. If a pointer is always aligned to an eight-byte boundary, then the low-order three bits are always zero.

The trick: You can stick whatever you want in those low-order bits, so long as you take them out before dereferencing the pointer. If your bottom three bits have to be zero, then you get three bits of “free” storage. To make this easy, you define a couple macros. One macro (called

POINTER()

in my example) masks out the low-order bits and returns a proper pointer. Another macro (

DATA()

in my example) masks out the high-order bits and returns the encoded data. To prevent the accidental dereferencing of the pointer before masking out the encoded data—which, aside from the pointer not pointing directly at your data, might be an alignment violation—the usual pattern is to store your pointers in

unsigned long

types, although a

uintptr_t

is a more portable alternative.

Example: Here’s an example, which defines three flags that you may OR into the pointer. Note this particular example requires a platform where pointers and longs are both 64-bits, but you could easily modify it for a 32-bit system.

 

</pre>
#include <stdio.h>

#define POINTER(p) (unsigned long*)(p & 0xffffffffffffff8UL)
#define DATA(p) (p & 7)

#define FLAG1 1
#define FLAG2 2
#define FLAG3 4

int main() {
unsigned long v = 0;
unsigned long p = (unsigned long) &v;

printf("p=%lu\n", p);
printf("POINTER(p)=%p\n", POINTER(p));
printf("DATA(p)=%lu\n", DATA(p));

p |= FLAG2;

printf("p=%lu\n", p);
printf("POINTER(p)=%p\n", POINTER(p));
printf("DATA(p)=%lu\n", DATA(p));

return 0;
}

Cool, but this seems like more work than it is worth? Often true! This sort of trick is useful when you have many, many pointers. For example, this is a common technique when implementing memory management systems where you might have a pointer to every active page in the system. Three bits with which to set read & write access flags are all you need.

Source: http://www.quora.com/C-programming-language/In-C-or-C++-what-are-your-favorite-pointer-tricks/answer/Robert-Love-1

 

 

Creating a doubly linked list with a single pointer

You can make a doubly linked list with a single pointer, which actually stores the XOR of its previous and next nodes’ addresses. For the head, this will just be the next element’s address.

Now, when traversing the list in the forward direction, instead of doing

n = n->next

, you do

n = n->next ^ prev

For the reverse direction, note that the tail’s next pointer will actually contain its previous node. So to traverse backwards, you just start with

n = tail
1
2
3
4
5
6
node *n = (forward ? head : tail), *prev = 0, *t;
while(/* some condition */) {
    t = n;
    n = n->next ^ prev;
    prev = t;
}

.

Insertion and deletion are similarly modified.

All of this is just a cute trick though- you should probably not use it unless writing code for some heavily memory constrained embedded system.

Source: http://www.quora.com/C-programming-language/In-C-or-C++-what-are-your-favorite-pointer-tricks/answer/Shrey-Banga

 

String Copy

while(*t++ = *s++) ;


Advertisements

3 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s