20 ms·
> 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 ar
by 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 agoYes, 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.
- comex 5y agoThe advantage is that, supposing the a pointer to the head of the list is stored in some other container, like struct Container { struct Foo *first_foo; ...probably more stuff... }; then the first entry can have its `prev` field simply be `&container->first_foo`. (Each subsequent entry, as the OP said, has its `prev` field be `&previous_entry->next`.) That way, you can have a function that removes an entry from the list, given only a pointer to the entry: void foo_remove(struct Foo *foo) { *foo->prev = foo->next; if (foo->next != NULL) foo->next->prev = foo->prev; } No need to keep separate track of which container you belong to, and no need to special case the first entry of the list. The FreeBSD sys/queue.h macros use this pattern for the LIST type. (The disadvantage of this scheme is that despite it being a mostly doubly linked list, you can only iterate forwards.)
- phkahler 5y agoYou get it exactly. I gave a more detailed explanation of the specific use-case in response to a sibling comment. It's one piece of a very complex data structure that does exactly what was needed efficiently - a dynamically updatable spatial index for geometric primitives.
- Akronymus 5y agoRelated https://www.youtube.com/watch?v=0ZEX_l0DFK0 https://www.youtube.com/watch?v=0ZEX_l0DFK0