Hello all
Currently we have some handling for hrefs (in the form of Inkscape::URIReference). It provides some signals and callbacks, but doesn't do everything that I would like it to. To be specific, there are several places when solving the following problems efficiently would be a great thing:
1. Given an object, iterate over all references to it. 2. Given an object, iterate over all objects it refers to.
Point 1 is useful for all sorts of things: marking objects for update, compensating clones, deletion, vacuum defs, etc. Point 2 would allow to remove 80% of clipboard code, and implement robust ID changing and clash prevention (which means, one that doesn't have to be updated whenever a new href-like attribute is added).
Here is my idea. We define a three-way smartpointer that looks like this:
class ObjectRefBase { ... SPObject *obj; ObjectRefBase *next; ObjectRefBase *next_ref; }; template <typename T> class ObjectRef : public ObjectRefBase { ... }; template <typename T> ObjectRef<T> const &getRef(T *obj) { return static_cast<ObjectRef<T> const &>(*obj); }
The 'next' and 'next_ref' pointers form a singly-linked cyclic lists. Each SPObject contains such a smartpointer (by protected inheritance: 'class SPObject: protected ObjectRefBase, ... {') that can be accessed using the getRef function, which is a templated friend of SPObject and returns an ObjectRef of correct type. The header of both lists is the pointer contained in the referenced object; it has 'obj' set to itself. 'next' allows us to iterate over references to this object, while 'next_ref' - over references contained in this object. The constructor might look like this:
ObjectRefBase(SPObject *owner) { if (owner == this) { obj = this; next = this; next_ref = this; } else { next_ref = owner->next_ref; owner->next_ref = this; obj = NULL; next = NULL; } }
If this is the embedded instance from protected inheritance, the the first test will be true and both lists will be initialized as empty (an empty cyclic list is represented by the header node having a next pointer pointing to itself). The assignment operator is as follows:
ObjectRefBase &operator=(ObjectRefBase const &other) { if (obj != NULL) { ObjectRefBase *cur = this; while (cur->next != this) cur = cur->next; cur->next = obj->next; } next = other.next; other.next = this; }
If the reference pointed to some object, the function walks the list and removes the reference from the linked list of the previous object; it then inserts itself into the linked list of the new object. The destructor works similarly:
~ObjectRefBase() { ObjectRefBase *cur = this; while (cur->next != this) cur = cur->next; cur->next = obj->next; cur = next_ref; while (cur->next_ref != this) cur = cur->next_ref; cur->next_ref = next_ref; }
Now we can iterate over the references to an object like this:
for (ObjectRefBase *cur = this->next; cur != this; cur = cur->next) { // do something with each reference to this object }
And over references contained in an object like this:
for (ObjectRefBase *cur = this->next_ref; cur != this; cur = cur->next_ref) { // do something with each reference stored in this object }
Testing whether the object has any indirect references is dead simple: this == next. Same for checking whether this object refers to anything: this == next_ref. The owner of a reference can be retrieved in linear time (by walking next_ref until we encounter next_ref == obj). All this of course can be encapsulated into a nice STL-like iterator interface which provides some extra type safety not present in ObjectRefBase (for example, we know that all ObjectRefs which we can reach via 'next' point to the same type). Handling CSS properties with URI references that are not members of the object is easy as well: ObjectRef doesn't need to be a member of the owner for all this to work. There are no boilerplate attach() / release() methods: the assignment operator of ObjectRef takes care of everything.
If walking the lists during reassignment and destruction turns out to be a performance problem, we can make both lists doubly-linked rather than singly-linked, where a node can be removed in constant time, at the price of 2 more pointers stored in each reference. Fast owner retrieval additionally requires storing the owner pointer. This gives 5 pointers of overhead, so for 10000 references on a 64-bit machine we get 390KB of overhead - should be manageable. I thought about a trick that can be used to implement constant-time erase on a cyclic single list (the iterator actually points one node before and we use cur->next->value to get the value), but it can't be applied here.
Why this is better than keeping pointers to the references in std::list or std::vector? - no memory allocations when adding a reference = better performance. - removing a reference is much simpler, because finding it in the list is not needed. - signals can be put in the ObjectRef class. - simple and elegant implementation.
What do you think? Improvements and discussion welcome.
Regards, Krzysztof