Yes, that is exactly correct. Since you took the time, I'll offer a fuller explanation. It was for a spatial index where geometric objects were placed in an octtree. I also allowed each object to be inside more than one tree node for reasons (an objects position in the tree has nothing to do with other objects in the tree and I had to be able to straddle tree-node partitions).
This all lead to each octree node needing a list of things it contained, but I couldn't put the objects directly in the list because they needed to be contained by more than one node. Hence the linked list is actually made of:
struct Link {
struct Link** prev; //pointer to previous links next pointer (for delete)
struct Link* next; //Just a pointer, not an actual struct
struct Link* obj_next; //Pointer to the next link referencing this object
struct Treenode* node; //pointer to the containing tree node
struct Object* obj; //Pointer to an object in this tree node
};
You can start from an object and traverse a singly linked list of all the "Links" that reference it. This is used to delete an object. When querying the octree we come throught a doubly linked list using the first 2 pointers to find all object in the vicinity. That list is doubly linked to enable fast deletes of an object. The Link also contains a pointer to the tree node so after a deletion the node can be checked to see if it's empty (if so the tree is pruned). The Link obviously needs a pointer to the object since that's the entire goal - to find whats in the tree nodes.
I didn't want to include an instance of this whole structure within the tree nodes just to form a root for the list, so I modified the prev pointer into a pointer to a pointer which still allows quick deletes.
At some time I realized that 5 pointers isn't cache friendly so I XORed the pointers to the Treenode and the Object. Since we traverse these node starting from one of those 2 objects we can always recover the pointer to the other one is we store their XOR. This makes the links the size of 4 pointers at the expense of more ick, and did not impact performance at the time.
I'm not going to argue the merits of this approach to a spatial index, but I did find value in changing the prev pointer to a *ptr and that can be applied to any implementation.
This all lead to each octree node needing a list of things it contained, but I couldn't put the objects directly in the list because they needed to be contained by more than one node. Hence the linked list is actually made of:
You can start from an object and traverse a singly linked list of all the "Links" that reference it. This is used to delete an object. When querying the octree we come throught a doubly linked list using the first 2 pointers to find all object in the vicinity. That list is doubly linked to enable fast deletes of an object. The Link also contains a pointer to the tree node so after a deletion the node can be checked to see if it's empty (if so the tree is pruned). The Link obviously needs a pointer to the object since that's the entire goal - to find whats in the tree nodes.I didn't want to include an instance of this whole structure within the tree nodes just to form a root for the list, so I modified the prev pointer into a pointer to a pointer which still allows quick deletes.
At some time I realized that 5 pointers isn't cache friendly so I XORed the pointers to the Treenode and the Object. Since we traverse these node starting from one of those 2 objects we can always recover the pointer to the other one is we store their XOR. This makes the links the size of 4 pointers at the expense of more ick, and did not impact performance at the time.
I'm not going to argue the merits of this approach to a spatial index, but I did find value in changing the prev pointer to a *ptr and that can be applied to any implementation.