Re: avltree / genalloc

From: Olivier Brunel <jjk_at_jjacky.com>
Date: Thu, 12 Apr 2018 23:37:21 +0200

Many thanks for the explaination/clarifications!


> avltree_iter isn't meant to perform operations that modify the
> structure
> of the tree. It *may* work, but there's no guarantee it will - and
> typically, if you modify the tree, later values for node height will
> certainly be incorrect. I wrote avltree_iter as a shortcut to perform
> simple operations such as printing the tree or calling a function on
> the data contained in every node; it should not be used with a
> tree-modifying function.

Ok, so let me ask you this: I want to delete my avltree. That is, I'd
like to remove all its nodes and be done with it, i.e. I need to free
all memory associated with it. I guess avltree_free() is enough, no
need to delete each node individually?

Obviously I want to do the same with my data, stored in a gensetdyn,
but there gensetdyn_free isn't enough, because I have extra memory
allocated (on a per-item basis) that I need to free as well, hence I
need to iterate over the items to perform my own freeing.

So yeah, that should in fact be done over the gensetdyn not the
avltree, that was my mistake, and then I simply not delete anything
either, just free my memory and call gensetdyn_free is enough, correct?

(Just to know, would the same be true with gensetdyn, and I shouldn't
add/remove during a gensetdyn_iter?)


> future major release - and use avltree_delete(), which is the right
> API. And the argument to avltree_delete() is the data in the node,
> i.e. your uint32_t (that is probably the index of your object in your
> gensetdyn).

Just to be clear, avltree_delete() actually takes the key (void *) for
that data, not the uint32_t itself, right?


> Well, genalloc is really "stralloc for larger objects", and I try
> not to implement for genalloc what I would not implement for stralloc.
> If you often need to remove items from a genalloc that are not the
> last one, then genalloc may not be the appropriate data structure,
> and you may want a gensetdyn instead.

hmm... I've been thinking about this, but I feel like what I need is
just a (dynamic) array, that I can add to and remove from. Maybe I'm
not seeing a genalloc exactly same as you; I feel gensetdyn might be
good for that, but I don't actually need indices to be stable (I'm
storing pointers), which is why a genalloc seems right to me: it's an
array, that can grow (or shrink) as needed. No need for more complexity
or anything. genalloc is pretty simple & straightforward, it's good,
but I do need to remove items from time to time, and that means I need
the memory moving bit.


Cheers,
Received on Thu Apr 12 2018 - 21:37:21 UTC