4 ms·

I had a need for doubly linked list and realized you can make the prev-> pointer point to a pointer_to_object rather than to an object (a pointer to a pointer).

I had a need for doubly linked list and realized you can make the prev-> pointer point to a pointer_to_object rather than to an object (a pointer to a pointer). You point the prev pointer at the prior next-> pointer. In other words, the Nth objects prev pointer points at the (N-1)th objects next pointer. This was huge PITA but it allowed me to avoid putting an entire struct in the base object, just a single pointer initialized to NULL. So: BASE_OBJ->linked_obj1->linked_obj2->NULL Not showing the back links here, but BASE_OBJ only contains a pointer to linked_obj1 rather than an instance of its structure. You can add items to the list via that first pointer. Deletes work the same as usual too with the oddity of dealing with that *object.

jjnoakes 5y ago
Not sure I follow, can you explain with a code snippet?
- Akronymus 5y ago
  I think GP was referring to something like that https://www.youtube.com/watch?v=0ZEX_l0DFK0 https://www.youtube.com/watch?v=0ZEX_l0DFK0
kevin_thibedeau 5y ago
If you need cheap double linking you should consider an XOR linked list.
jmholla 5y ago
Wouldn't it need to be N-2? N-1's next is N, but prev should point to N-1.
- phkahler 5y ago
  The only reason we need to point to N-1 is to get access to its next pointer for doing deletes (in my case where I never scan the list backwards). So rather than point to N-1 it suffices to point directly at its next pointer.
dahfizz 5y ago
> Not showing the back links here, but BASE_OBJ only contains a pointer to linked_obj1 rather than an instance of its structure. I don't understand what you are after.... struct Foo { struct Foo* prev; //Just a pointer, not an actual struct struct Foo* next; //Just a pointer, not an actual struct }; That lets you "avoid putting an entire struct in the base object" without using a double pointer. It sounds like you did this: struct Foo { struct Foo** prev; //double pointer struct Foo* next; }; Which works, but is strange...
- phkahler 5y ago
  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.

jjnoakes 5y ago

Not sure I follow, can you explain with a code snippet?

Akronymus 5y ago
I think GP was referring to something like that https://www.youtube.com/watch?v=0ZEX_l0DFK0 https://www.youtube.com/watch?v=0ZEX_l0DFK0

kevin_thibedeau 5y ago

If you need cheap double linking you should consider an XOR linked list.

jmholla 5y ago

Wouldn't it need to be N-2? N-1's next is N, but prev should point to N-1.

phkahler 5y ago
The only reason we need to point to N-1 is to get access to its next pointer for doing deletes (in my case where I never scan the list backwards). So rather than point to N-1 it suffices to point directly at its next pointer.

dahfizz 5y ago

> Not showing the back links here, but BASE_OBJ only contains a pointer to linked_obj1 rather than an instance of its structure. I don't understand what you are after.... struct Foo { struct Foo* prev; //Just a pointer, not an actual struct struct Foo* next; //Just a pointer, not an actual struct }; That lets you "avoid putting an entire struct in the base object" without using a double pointer. It sounds like you did this: struct Foo { struct Foo** prev; //double pointer struct Foo* next; }; Which works, but is strange...

phkahler 5y ago
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.