Better hrefs

12 Aug 2009


      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
-- 
View this message in context: http://www.nabble.com/Better-hrefs-tp24939304p24939304.html
Sent from the Inkscape - Dev mailing list archive at Nabble.com.

Krzysztof Kosiński

Jon A. Cruz

Krzysztof Kosiński

Jon A. Cruz

Jon A. Cruz

Jon A. Cruz

Jon A. Cruz

Krzysztof Kosiński

Jon A. Cruz

Krzysztof Kosiński

Jon A. Cruz

tags (0)

participants (2)