Re: avltree / genalloc

From: Laurent Bercot <ska-skaware_at_skarnet.org>
Date: Thu, 12 Apr 2018 23:21:38 +0000

>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

This archive was generated by hypermail 2.3.0 : Sun May 09 2021 - 19:38:49 UTC