>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
Received on Thu Apr 12 2018 - 23:21:38 UTC