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?
Yes, avltree_free() is enough, because an avltree doesn't hold any
pointers to your data.
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.
Yes. Note that for that you can use gensetdyn_iter, the "f"
argument being a function that frees a cell. It will be called
on every allocated cell. The cells will still be marked as
allocated (it's not gensetdyn_delete()) but you don't care since
you're going to call gensetdyn_free() right afterwards.
I have such an iterator in genalloc: genalloc_deepfree(), which
calls the user-provided function to free every object. I don't
know why I haven't added the same for genset/dyn, I should
probably do it.
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?
Yes. Free your data, then free the container.
(Just to know, would the same be true with gensetdyn, and I shouldn't
add/remove during a gensetdyn_iter?)
Yes, and it's even trickier with a gensetdyn than with an avltree,
because the way a gensetdyn keeps track of what cells are allocated
is via a "freelist" stack, i.e. a genalloc of uint32_t containing the
indices of free cells. This makes gensetdyn_new() and gensetdyn_delete()
O(1) since they're just popping and pushing the stack. But for
gensetdyn_iter, the freelist is first converted to a bitarray, and
the bitarray is scanned, so the iterator is only called on allocated
cells. If you change the freelist while gensetdyn_iter() is running,
you will desync the freelist from the bitarray, and the iterator may
miss an allocated cell, or worse, call your function on an unallocated
one. So, don't do that. ^^'
Just to be clear, avltree_delete() actually takes the key (void *) for
that data, not the uint32_t itself, right?
Er, yes, sorry, it takes the key. So if you have the data, you need to
call your dtok function first. ("data to key")
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.
Then genalloc is indeed the right data structure from you, but
I don't have helpers to arbitrarily remove an object in the middle.
Note that if you don't need index stability, it's trivial, and O(1):
you can just overwrite the ith object with the (n-1)th, and decrement
the length. No need to copy len-i-1 objects, just copy one.
--
Laurent
