Generated content: counters and quotes

[Allan Sandfeld Jensen]

On Wednesday 16 February 2005 19:40, Waldo Bastian wrote:
> On Wednesday 16 February 2005 19:14, Leo Savernik wrote:
> > Am Dienstag, 15. Februar 2005 22:47 schrieb Allan Sandfeld Jensen:
> > > > additional member in RenderObject.
> > >
> > > Sounds interesting. Notice however that all lists and list-items now
> > > have a counter attached.
> >
> > Yeah, but only estimated 2% of all render objects will be actual list
> > items. That means, in a document containing 100000 render objects, we
> > incur a space overhead of 400000 bytes. With a hashmap, we only use space
> > for the purported 2% of counter-attached nodes, we only have 2000 bytes
> > over (+ overhead of the hashmap structures which we occur only once).
> >
> > > With a global structure we really just need a fast way to lookup:
> > > name*render-node -> counter-node
> >
> > QPtrDict is a hashmap, so it's O(1). There should be a convenience method
> > that allows accessing an associated counter node like
> >
> > xmlDocImpl()->attachedCounterNode(this)
>
> Assuming your hash map is big enough, if it's too small it becomes O(n)
> again.
>
> Also note that the overhead of doing a lookup in a QPtrDict is larger than
> doing a variable lookup, so I hope you don't want to do the lookup for each
> of the 100000 render objects in the above example. Maybe you have a bit
> free in RenderObject to record whether a node has a counter or not.
>
One bit is not enough. A node can have any number of counters with different 
names. In reality though, only siblings and parents to nodes with counters 
are scanned for counters. All nodes with children with counters, contain an 
empty counter-increment 0 for that counter, so that a sub-tree will always 
contain a subset of the counters of its parents.

Or in other words, it will not be a problem, since the nodes scanned are 
already minimal.

I am more interested in an elegant solution with a key-pair 
(RenderObject*,QString). Apparently QPtrDict uses pointers as keys and not 
values which makes QPair impractical.

`Allan