Re: avltree / genalloc
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
Re: avltree / genalloc
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,
Re: avltree / genalloc
- When using avltree_iter() we need to pass a avliterfunc_t_ref, which takes 3 arguments. If I understand correctly, first is the uint32_t index, then the tree's "internal" (unsigned int) index, and my pointer. "The uint32_t index" is confusing terminology, so to clarify, I call this number "the data contained in the node". An avlnode only stores an uint32_t of data, it doesn't know anything else; so that uint32_t is "the data". If you want to use the tree to index anything else than a set of uint32_t, you need to store your objects somewhere, for instance in a gensetdyn, and use the tree to store the indices of your objects into the gensetdyn. That is typically what the "external" field of the avltree is for: to store a pointer to your storage structure, so you can access the objects to extract keys from them (in dtok) and compare keys (in kcmp). But as far as avlnode/avltree is concerned, the uint32_t is "the data". So, the first argument is the data. The second argument is not the internal index, which user functions should basically never see because it's an implementation detail and totally irrelevant to them; the second argument is the height of the current node (root is 0, direct child of the root is 1, etc.) The third argument is the external pointer. So if I wanted, from there, to remove an item from the avltree, I could either use avltree_deletenode(tree, ARG2) or avltree_delete(tree, KEY) where KEY is the one from dtok(ARG1,p) -- would all that be correct, or did I miss/misunderstood something? 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. If you need to iterate over a tree-modifying function, I think you should write the loop yourself, because the complexity of writing the loop is much lesser than the complexity required to handle tree structure changes in the middle of a map. - So it means avltree_deletenode() needs the avltree's own/internal index, whereas gensetdyn_delete() needs "our" uint32_t index, correct? gensetdyn is totally irrelevant to the tree. (I mean, avltree uses a gensetdyn internally, to store the avlnodes, but it is an implementation detail you should not care about.) If you are using a gensetdyn to store your objects, then you will want to use the gensetdyn's indices as data in the tree. avltree_deletenode() is a bad API: it uses the internal index to the node, but the user should basically have no way to interact with that internal index. I wrote that "just in case", initially thinking it should, logically, be faster than avltree_delete() since it has internal information, but it's 1. a YAGNI violation, and 2. wrong anyway, because to delete a node you need to know the path from the root to that node, and just knowing the internal index doesn't give you that - you need to go on foot and make your key comparisons from the root down, which is exactly what avltree_delete() does. So: forget about avltree_deletenode() - thanks for the fix, I will apply the patch, but I will probably remove that macro altogether in a 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). My bad for creating confusion with a function that should not exist. I.e. if I have that uint32_t and want to remove things from both the avltree & gensetdyn (I'm using the later to store the actual data indexed via the former, btw) then for avltree I need to get the key (e.g. via t->dtok(u,p)) First, use avltree_delete(), with that uint32_t, to remove the node. Then, use gensetdyn_delete() to remove your object from your gensetdyn. (I ended up using avltree_delete directly, guessing you usually do that as well maybe?) Yes, that is the correct entry point for deletion. - And on a completely unrelated topic, is there really no way (macro/function) in skalibs to remove an item from a genalloc? I get it for stralloc, it's not really thought of as an array but a string, you rarely want to remove one char from somehere in the middle, whatever. But with a genalloc, I'd expect one to (often) be wanting to remove an item from the array, and not always/only the last one, yet I can't see how that's supposed to be done? (Again, as in via a macro or something, of course one can - as I do - handle the memmove oneself) 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
avltree / genalloc
Hey,
So I've been using avltree & gensetdyn (amongst others) lately in a
little project of mine, and I have some questions:
- When using avltree_iter() we need to pass a avliterfunc_t_ref, which
takes 3 arguments. If I understand correctly, first is the uint32_t
index, then the tree's "internal" (unsigned int) index, and my
pointer.
So if I wanted, from there, to remove an item from the avltree, I
could either use avltree_deletenode(tree, ARG2) or
avltree_delete(tree, KEY) where KEY is the one from dtok(ARG1,p) --
would all that be correct, or did I miss/misunderstood something?
- So it means avltree_deletenode() needs the avltree's own/internal
index, whereas gensetdyn_delete() needs "our" uint32_t index,
correct?
I.e. if I have that uint32_t and want to remove things from both the
avltree & gensetdyn (I'm using the later to store the actual data
indexed via the former, btw) then for avltree I need to get the key
(e.g. via t->dtok(u,p))
- I think there's a bug in skalibs right now, avltree_deletenode() is
broken and things don't even compile; I believe the attached patch is
a correct fix for it.
(I ended up using avltree_delete directly, guessing you usually do
that as well maybe?)
- And on a completely unrelated topic, is there really no way
(macro/function) in skalibs to remove an item from a genalloc? I get
it for stralloc, it's not really thought of as an array but a string,
you rarely want to remove one char from somehere in the middle, whatever.
But with a genalloc, I'd expect one to (often) be wanting to remove an
item from the array, and not always/only the last one, yet I can't see
how that's supposed to be done? (Again, as in via a macro or
something, of course one can - as I do - handle the memmove oneself)
Maybe I'm the odd one for wanting to do such a thing on a regular
basis, but something like in the (other) attached patch, I feel,
might be useful. I know it certainly wasn't the first time I have to
write that sort of things...
Thanks for the help!
Cheers,
>From c9d5bb194408f22db8ef859203f28c6748e78ab9 Mon Sep 17 00:00:00 2001
From: Olivier Brunel
Date: Thu, 12 Apr 2018 18:05:14 +0200
Subject: [PATCH] Fix avltree_deletenode
Signed-off-by: Olivier Brunel
---
src/include/skalibs/avltree.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/include/skalibs/avltree.h b/src/include/skalibs/avltree.h
index 1ce7385..8234d95 100644
--- a/src/include/skalibs/avltree.h
+++ b/src/include/skalibs/avltree.h
@@ -48,7 +48,7 @@ extern int avltree_newnode (avltree *, uint32_t, uint32_t *) ;
#define avltree_insertnode(t, i) avltree_setroot(t, avlnode_insertnode(avltree_nodes(t), avltree_totalsize(t), avltree_root(t), i, (t)->dtok, (t)->kcmp, (t)->external))
extern int avltree_insert (avltree *, uint32_t) ;
-#define avltree_deletenode(t, i) avltree_delete(t, (*(t)->dtok)(avltree_data(t, i)))
+#define avltree_deletenode(t, i) avltree_delete(t, (*(t)->dtok)(avltree_data(t, i),(t)->external))
extern int avltree_delete (avltree *, void const *) ;
#define avltree_iter(t, f, p) avlnode_iter(avltree_nodes(t), avltree_totalsize(t), avltree_root(t), f, p)
--
2.15.1
>From 0c8186bfedc2dfa6d1bd083dafc3ec9a7c46828d Mon Sep 17 00:00:00 2001
From: Olivier Brunel
Date: Thu, 12 Apr 2018 18:51:40 +0200
Subject: [PATCH] Add genalloc_delete
Signed-off-by: Olivier Brunel
---
src/include/skalibs/genalloc.h | 2 ++
src/libstddjb/genalloc_delete_size.c | 12
2 files changed, 14 insertions(+)
create mode 100644 src/libstddjb/genalloc_delete_size.c
diff --git a/src/include/skalibs/genalloc.h b/src/include/skalibs/genalloc.h
index da83c2f..acf2bec 100644
--- a/src/include/skalibs/genalloc.h
+++ b/src/include/skalibs/genalloc.h
@@ -28,6 +28,8 @@ typedef stralloc genalloc, *genalloc_ref ;
#define genalloc_reverse(type, g) stralloc_reverse_blocks((g), sizeof(type))
#define genalloc_insertb(type, g, offset, s, n) stralloc_insertb((g), (offset)*sizeof(type), (char const *)(s), (n)*sizeof(type))
#define genalloc_insert(type, g1, offset, g2) stralloc_insert((g1), (offset)*sizeof(type), (g2))
+#define genalloc_delete(type,g,i) genalloc_delete_size((g),sizeof(type),i)
+extern void genalloc_delete_size (genalloc *, size_t, size_t) ;
#define genalloc_deepfree(type, g, f) genalloc_deepfree_size(g, (freefunc_t_ref)(f), sizeof(type))
extern void genalloc_deepfree_size (genalloc *, freefunc_t_ref, size_t) ;
diff --git a/src/libstddjb/genalloc_delete_size.c b/src/libstddjb/genalloc_delete_size.c
new file mode 100644
index 000..a289000
--- /dev/null
+++ b/src/libstddjb/genalloc_delete_size.c
@@ -0,0 +1,12 @@
+/* ISC license. */
+
+#include
+#include
+#include
+
+void genalloc_delete_size (genalloc *g, size_t s, size_t i)
+{
+ size_t len = g->len / s;
+ if (len > i + 1) memmove (g->s + i * s, g->s + (i + 1) * s, (len - i - 1) * s) ;
+ g->len -= s ;
+}
--
2.15.1
Re: [s6-networking] silent option for s6-tcpclient
Hi all - I had a use-case where I needed s6-tcpclient to be completely silent, no matter the error (my existing system reads standard output and standard error, and tries to parse it). Sorry, not applying this patch. Parsing stderr is not supported: this would make error message format a public API, which it isn't (and depends on the libc anyway). That's the main difference between stdout and stderr: stdout messages are API, but stderr messages are not - they are ultimately made for human consumption, not machine consumption. Long-term, I'm going to change the system to log (but not parse) standard error from child processes. In the meantime, I figured this could be a useful feature for others. No. Don't help people mistakenly rely on whether stderr prints something or not. :P In the case of s6-tcpclient, verbosity 0 (-q) ensures it only writes to stderr if it dies, meaning that your application is not run anyway. So you can have a completely silent s6-tcpclient if your application runs. And of course, you can always redirect stderr to /dev/null, but that silences everything, including your application ^^ -- Laurent
[PATCH] [s6-networking] add silent option to s6-tcpclient
If the user passes "-s" to s6-tcpclient, all warning and
error messages will be supressed, making s6-tcpclient
completely transparent.
---
doc/s6-tcpclient.html | 3 +-
src/conn-tools/s6-tcpclient.c | 73 +++
2 files changed, 41 insertions(+), 35 deletions(-)
diff --git a/doc/s6-tcpclient.html b/doc/s6-tcpclient.html
index 79b66c7..842d659 100644
--- a/doc/s6-tcpclient.html
+++ b/doc/s6-tcpclient.html
@@ -28,7 +28,7 @@ then executes into a program.
Interface
- s6-tcpclient [ -q | -Q | -v ] [ -4 | -6 ] [ -d | -D ] [ -r | -R ] [ -h |
-H ] [ -n | -N ] [ -t timeout ] [ -l localname ] [ -T
timeoutconn ] [ -i localip ] [ -p localport ]
host port prog...
+ s6-tcpclient [ -q | -Q | -v | -s ] [ -4 | -6 ] [ -d | -D ] [ -r | -R ] [
-h | -H ] [ -n | -N ] [ -t timeout ] [ -l localname ] [ -T
timeoutconn ] [ -i localip ] [ -p localport ]
host port prog...
@@ -80,6 +80,7 @@ the current connection (very unreliable). Else unset.
-q : be quiet.
-Q : be normally verbose. This is the default.
-v : be verbose.
+ -s : be absolutely silent, even for system errors.
-4 : (only valid if the underlying skalibs has
IPv6 support) Interpret host as an IPv4 address or make A
queries to determine its addresses.
diff --git a/src/conn-tools/s6-tcpclient.c b/src/conn-tools/s6-tcpclient.c
index 5fdd7f0..53056b9 100644
--- a/src/conn-tools/s6-tcpclient.c
+++ b/src/conn-tools/s6-tcpclient.c
@@ -3,6 +3,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -18,17 +19,19 @@
#include
#ifdef SKALIBS_IPV6_ENABLED
-# define USAGE "s6-tcpclient [ -q | -Q | -v ] [ -4 | -6 ] [ -d | -D ] [ -r |
-R ] [ -h | -H ] [ -n | -N ] [ -t timeoutinfo ] [ -l localname ] [ -T
timeoutconn ] [ -i localip ] [ -p localport ] host port prog..."
-# define TFLAGS_DEFAULT { 0, 0, { 2, 58 }, IP46_ZERO, 0, 1, 0, 0, 1, 0, 1, 1 }
-# define OPTSTRING "qQv46dDrRhHnNt:l:T:i:p:"
+# define USAGE "s6-tcpclient [ -q | -Q | -v | -s ] [ -4 | -6 ] [ -d | -D ] [
-r | -R ] [ -h | -H ] [ -n | -N ] [ -t timeoutinfo ] [ -l localname ] [ -T
timeoutconn ] [ -i localip ] [ -p localport ] host port prog..."
+# define TFLAGS_DEFAULT { 0, 0, { 2, 58 }, IP46_ZERO, 0, 1, 0, 0, 0, 1, 0, 1,
1 }
+# define OPTSTRING "qQvs46dDrRhHnNt:l:T:i:p:"
#else
-# define USAGE "s6-tcpclient [ -q | -Q | -v ] [ -d | -D ] [ -r | -R ] [ -h |
-H ] [ -n | -N ] [ -t timeoutinfo ] [ -l localname ] [ -T timeoutconn ] [ -i
localip ] [ -p localport ] host port prog..."
-# define TFLAGS_DEFAULT { 0, 0, { 2, 58 }, IP46_ZERO, 0, 1, 1, 0, 1, 1 }
-# define OPTSTRING "qQvdDrRhHnNt:l:T:i:p:"
+# define USAGE "s6-tcpclient [ -q | -Q | -v | -s ] [ -d | -D ] [ -r | -R ] [
-h | -H ] [ -n | -N ] [ -t timeoutinfo ] [ -l localname ] [ -T timeoutconn ] [
-i localip ] [ -p localport ] host port prog..."
+# define TFLAGS_DEFAULT { 0, 0, { 2, 58 }, IP46_ZERO, 0, 1, 0, 1, 0, 1, 1 }
+# define OPTSTRING "qQvsdDrRhHnNt:l:T:i:p:"
#endif
#define usage() strerr_dieusage(100, USAGE)
+#define usagesilent() _exit(100)
#define dienomem() strerr_diefu1sys(111, "allocate")
+#define diesilent(e) _exit(e)
#define MAXIP 16
@@ -41,6 +44,7 @@ struct tflags_s
ip46_t localip ;
uint16_t localport ;
unsigned int verbosity : 2 ;
+ unsigned int silent : 1 ;
#ifdef SKALIBS_IPV6_ENABLED
unsigned int ip4 : 1 ;
unsigned int ip6 : 1 ;
@@ -71,6 +75,7 @@ int main (int argc, char const *const *argv)
case 'q' : if (flags.verbosity) flags.verbosity-- ; break ;
case 'Q' : flags.verbosity = 1 ; break ;
case 'v' : flags.verbosity++ ; break ;
+case 's' : flags.silent = 1 ; break ;
#ifdef SKALIBS_IPV6_ENABLED
case '4' : flags.ip4 = 1 ; break ;
case '6' : flags.ip6 = 1 ; break ;
@@ -100,7 +105,7 @@ int main (int argc, char const *const *argv)
}
case 'i' : if (!ip46_scan(l.arg, &flags.localip)) usage() ; localip =
1 ; break ;
case 'p' : if (!uint160_scan(l.arg, &flags.localport)) usage() ; break
;
-default : usage() ;
+default : flags.silent ? usagesilent() : usage() ;
}
}
argc -= l.ind ; argv += l.ind ;
@@ -110,11 +115,11 @@ int main (int argc, char const *const *argv)
if (!flags.ip6) flags.ip4 = 1 ;
#endif
if (!uint160_scan(argv[1], &remoteport))
-strerr_dief2x(100, "invalid port number: ", argv[1]) ;
+flags.silent ? diesilent(100) : strerr_dief2x(100, "invalid port number:
", argv[1]) ;
tain_now_g() ;
if (flags.timeout) tain_addsec_g(&deadline, flags.timeout) ;
else tain_add_g(&deadline, &tain_infinite_relative) ;
- if (!s6dns_init()) strerr_diefu1sys(111, "init DNS") ;
+ if (!s6dns_init()) flags.silent ? diesilent(111) : strerr_diefu1sys(111,
"init DNS") ;
{
ip46_t ip[2][MAXIP] ;
unsigned int j = 0 ;
@@ -159,7 +164,7 @@ int main (int argc, char const *const *argv)
genalloc ips = STRALLOC_ZERO ;
size_t i = 0 ;
if (s6dns_r
[s6-networking] silent option for s6-tcpclient
Hi all - I had a use-case where I needed s6-tcpclient to be completely silent, no matter the error (my existing system reads standard output and standard error, and tries to parse it). Long-term, I'm going to change the system to log (but not parse) standard error from child processes. In the meantime, I figured this could be a useful feature for others. doc/s6-tcpclient.html | 3 +- src/conn-tools/s6-tcpclient.c | 73 +++ 2 files changed, 41 insertions(+), 35 deletions(-)
