Re: RFC: partial symbol table address range generalization

[Jim Blandy <jimb at zwingli dot cygnus dot com>]

Andrew Cagney <ac131313@cygnus.com> writes:
> > The question is, how can you represent this in an obstack-friendly
> > way?  The obvious representation of an addrmap is a sorted array, with
> > a gap for insertion, but obstacks don't like arrays that expand
> > occasionally.  A doubling algorithm can guarantee that the waste is
> > merely proportional to the final size, but that's kind of crummy.  A
> > binary tree works better, but you spend a lot of memory on child
> > links; we wouldn't want to use an addrmap to store line number info if
> > it took twenty bytes per line (currently it takes only twelve) (both
> > assuming a 64-bit CORE_ADDR and 32-bit pointers and ints).
> 
> You mean a b-tree?

You mean something balanced?  Yes, of course.

My real point is: I think our effort is best spent on structures with
simple interfaces and acceptable performance under a broad range of
usage patterns, that can be reused in different contexts.  I'd like to
see us gradually replace the dozens of ad-hoc structures we've got now
with applications of generic structures.

That's why I was excited about addrsets and addrmaps; my code isn't
surprising, but I hoped the interfaces were smooth enough to allow
them to be used for lots of different purposes.