How to compress pointer ? eg. arbitrary bit pointer

Question

I'm coding a complex tree data structure, which stores lots of pointers. The pointers themselves occupy lots of space, and this is what I'm expecting to save.

So I'm here to ask whether there are examples on this. E.g.: For 64-bit data type, can I use a 32-bit or less pointer if the data it's pointing to is sure to be continuous?

I found a paper called Transparent Pointer Compression for Linked Data Structures, but I thought there could be a much simpler solution.

Update:

It is an octree. A paper here about this on GPU is GigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large And Detailed Scenes, they use 15-bit pointers on GPU

Answer 1

Instead of using pointers, use an index into an array. The index can be a short if the array is less than 65536 in length, or int32_t if it's less than 2147483648.

An arbitrary pointer can really be anywhere in memory, so there's no way to shorten it by more than a couple of bits.

Answer 2

If the utilization of pointers takes a lot of space:

use an array of pointers, and replaces pointers with indexes in that array. That adds just another indirection. With less than 64k pointers, you need a [short] array (Linux)

Simple implementation

#define   MAX_PTR  60000

void *aptr[MAX_PTR];
short nb = 0;

short ptr2index(void *ptr) {
  aptr[nb] = ptr;
  return (short)nb++;
}

void *index2ptr(short index) {
  return aptr[index];
}

... utilization ...

... short next; // in Class

Class *c = new Class();
mystruct->next = ptr2index((void *)c);

...

Class *x = (Class *)index2ptr(otherstruct->next);