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

[Glynn Clements]

Rosen Matev wrote:

> > 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).

In that case, it's probably easier to just keep blocks permanently
allocated. Free nodes live on a global free list, from where new nodes
are allocated. When the free list is empty, a new block is allocated
and its nodes are immediately placed on the free list.

If it wasn't for link_dispose(), you wouldn't even need to keep any
details of the actual blocks.

> > 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.

Ultimately, the time complexity is still only O(n), and anything which
processes the resulting polygon will be at least O(n), and probably
with a much larger constant.

-- 
Glynn Clements <glynn at gclements.plus.com>