[GRASS-dev] Re: new version of lib/linkm (linked list memory manager)

[Rosen Matev]

Hi,

Here is my two-month-delay answer (sorry, very busy at school).

> We probably don't need (or want) to free individual chunks as they
> become empty; they can be retained for future allocations. We just
> need to free everything in link_dispose().

We don't actually free allocated fixed-sized blocks. However, we need
to mark when a block is empty (ready to be "allocated" again).

> OTOH, I don't even know if we really need *any* of this. Certainly,
> the code in lib/Vlib/poly.c could quite easily just use a realloc()ed
> array, with link pointers being replaced by array indices.

Let's assume that every time we call realloc() we double the size of
the array. If we need to allocate N elements, then we will make
log2(N) calls to realloc(). Moreover, in worst case scenario, the
realloc()s would have made a total of 2N element copies. We increase
the constant in the complexity of the algorithm, but my linkm also
increases it (probably even more).
Note: the results worsen if we don't use the "double the size of the
array" rule. For example adding a constant number of elements in every
realloc() is very bad asymptotically.
Having said that, I couldn't agree more to you that we don't need *any* of this.

> The bitmap code probably could as well, although it would need a bit
> more work. But then, AFAICT, nothing actually creates sparse bitmaps
> (which are the sole reason that the bitmap library uses the link
> library).

I'm not familiar with bitmap.c yet. I'll have a look

Regards,
Rosen Matev