Tagging/Encoding Pointers

Question

I need a way to tag a pointer as being either part of set x or part of set y (ie: the tag has only 2 'states'), I'm that means one can assume untagged = x and tagged = y.

Currently I'm looking at using bitwise xor to do this:

ptr ^ magic = encoded_ptr
encoded_ptr ^ magic = ptr

but I'm stumped at how to determine if the pointer is tagged in the first place. I'm using this to mark what pools nodes in a linked list come from, so that when the are delinked, they can go back to the correct perants.

Update

Just to make it clear to all those people suggesting to store the flag in extra data members, I'm limited to sizeof(void*), so I can't add new members, else I would have. Also the pools aren't contiguous, they consist of many pages, tracking the ranges would add too much overhead (I'm after a fast & simple solution, if one can call it that).

Answer 1

Most solution will be platform specific. here a few of them:

1) A pointer returned by malloc or new will be aligned (4, 8, 16, 32 bytes, you name it). So, on most architectures, several LSB bits of the address will be always 0.

2) And a Win32 specific way: unless your program uses 3GB switch, values of all usermode pointers are less than 0x80000000, so the highest bit can be used as flag. As bonus, it will also crash when the flagged pointer is dereferenced without being repaired.