Re: [PATCH 02/10] string-list.h: add string_list_pop function.

Martin Ågren [off-list ref] writes:

On 9 August 2018 at 00:17, Stefan Beller [off-list ref] wrote:

quoted

A string list can be used as a stack, but should we? A later patch shows
how useful this will be.

Signed-off-by: Stefan Beller <redacted>
---
 string-list.c | 8 ++++++++
 string-list.h | 6 ++++++
 2 files changed, 14 insertions(+)

diff --git a/string-list.c b/string-list.c
index 9f651bb4294..ea80afc8a0c 100644
--- a/string-list.c
+++ b/string-list.c

@@ -80,6 +80,14 @@ void string_list_remove(struct string_list *list, const char *string,
        }
 }

+struct string_list_item *string_list_pop(struct string_list *list)
+{
+       if (list->nr == 0)
+               return 0;

return NULL, not 0.

It is OK to return NULL, which may make the caller a bit simpler,
i.e.

	while (item = list_pop(list))
		work_on(item);

but if we consider it a good discipline for the caller to see if
there are still things on the stack before attempting to pop, then
instead of returning NULL, we can have BUG("") there, which requires
the caller to be more like this:

	while (list->nr)
		work_on(list_pop(list));

which is not so bad.

quoted

+/**
+ * Returns the last item inserted and removes it from the list.
+ * If the list is empty, return NULL.
+ */
+struct string_list_item *string_list_pop(struct string_list *list);
+

The memory ownership is now with the caller. That is, the caller needs
to check/know `list->strdup_strings` and know `free_util` to be able to
properly free all memory.

OTOH, the pointer returned by this function is only guaranteed to be
valid until you start inserting into the list (well, you can do one
insertion per pop without worrying, but that's quite detailed
implementation knowledge).

Yes, it is a more grave limitation when using string_list as a
stack.  A single realloc() and you are dead X-<.

On Thu, Aug 09, 2018 at 02:29:32PM -0700, Junio C Hamano wrote:

quoted

quoted

+struct string_list_item *string_list_pop(struct string_list *list)
+{
+       if (list->nr == 0)
+               return 0;

return NULL, not 0.

It is OK to return NULL, which may make the caller a bit simpler,
i.e.

	while (item = list_pop(list))
		work_on(item);

but if we consider it a good discipline for the caller to see if
there are still things on the stack before attempting to pop, then
instead of returning NULL, we can have BUG("") there, which requires
the caller to be more like this:

	while (list->nr)
		work_on(list_pop(list));

which is not so bad.

In many cases you can just do:

  while (list->nr) {
	work_on(list->items[list->nr - 1]);
	list_remove(list, list->nr - 1);
  }

and then all of those memory ownership issues like:

quoted

The memory ownership is now with the caller. That is, the caller needs
to check/know `list->strdup_strings` and know `free_util` to be able to
properly free all memory.

quoted

OTOH, the pointer returned by this function is only guaranteed to be
valid until you start inserting into the list (well, you can do one
insertion per pop without worrying, but that's quite detailed
implementation knowledge).

Yes, it is a more grave limitation when using string_list as a
stack.  A single realloc() and you are dead X-<.

just go away. :)

Where that falls down is if you really need work_on() to put more items
on the stack, but only after you've removed the current top. But then
writing it out may still be nicer, because it makes it clear you have to
do:

  const char *cur_string = xstrdup(list->items[list->nr-1].string);

if you want the data to live past the removal.

-Peff

On Thu, Aug 9, 2018 at 2:41 PM Jeff King [off-list ref] wrote:

quoted

      while (list->nr)
              work_on(list_pop(list));

which is not so bad.

In many cases you can just do:

  while (list->nr) {
        work_on(list->items[list->nr - 1]);
        list_remove(list, list->nr - 1);
  }

and then all of those memory ownership issues like:

[...]

just go away. :)

The only complication here is the lack of list_remove(index),
we do have list_remove(string), which internally searches the
item and removes it. Hence I did not want to use it.

Another idea I had was to keep the list immutable (except amending,
just like a constitution ;-) and store an index of how far we got in that
list already. That wastes memory for keeping entries around, but is safe
for memory due to its nature.

Where that falls down is if you really need work_on() to put more items
on the stack, but only after you've removed the current top. But then
writing it out may still be nicer, because it makes it clear you have to
do:

  const char *cur_string = xstrdup(list->items[list->nr-1].string);

Another way would be to use

  string_list_pop(&list, &string_dst, &util_dst);
i.e.
  /* Returns 0 if the dst was filled */
  int (struct string_list *, char **, void**)

as then we do not expose the internals and would not have issues
with reallocs.

if you want the data to live past the removal.

In the code proposed there are no additions (hence no reallocs)
and the need for the data is short lived.

But I can see how the design was just fitting my purpose and
we could come up with some better API.

Thanks,
Stefan

On Thu, Aug 09, 2018 at 02:52:29PM -0700, Stefan Beller wrote:

quoted

In many cases you can just do:

  while (list->nr) {
        work_on(list->items[list->nr - 1]);
        list_remove(list, list->nr - 1);
  }

and then all of those memory ownership issues like:

[...]

quoted

just go away. :)

The only complication here is the lack of list_remove(index),
we do have list_remove(string), which internally searches the
item and removes it. Hence I did not want to use it.

Heh, I almost dug into that more.

I think you could have helpers to spell the two lines above even more
nicely:

  while (list->nr) {
        work_on(list_top(list));
	list_pop(list); /* note this doesn't return anything! */
  }

But yes, it's not possible with the current functions.

Another idea I had was to keep the list immutable (except amending,
just like a constitution ;-) and store an index of how far we got in that
list already. That wastes memory for keeping entries around, but is safe
for memory due to its nature.

You can also use a list.h linked-list. Then removal from the list and
freeing are two separate operations (but it exercises your malloc a lot
more if you're constantly pushing and popping).

quoted

Where that falls down is if you really need work_on() to put more items
on the stack, but only after you've removed the current top. But then
writing it out may still be nicer, because it makes it clear you have to
do:

  const char *cur_string = xstrdup(list->items[list->nr-1].string);

Another way would be to use

  string_list_pop(&list, &string_dst, &util_dst);
i.e.
  /* Returns 0 if the dst was filled */
  int (struct string_list *, char **, void**)

as then we do not expose the internals and would not have issues
with reallocs.

Yes, I almost suggested that, but there's the question of memory
ownership of string_dst. Does it need freed or not? Is that answer
dependent on the strdup_strings flag?

quoted

if you want the data to live past the removal.

In the code proposed there are no additions (hence no reallocs)
and the need for the data is short lived.

But I can see how the design was just fitting my purpose and
we could come up with some better API.

Yeah, I didn't actually dig into your use case. I just want to make sure
we don't add a crappy function to our API. ;)

-Peff

On Thu, Aug 9, 2018 at 2:56 PM Jeff King [off-list ref] wrote:

I think you could have helpers to spell the two lines above even more
nicely:

  while (list->nr) {
        work_on(list_top(list));
        list_pop(list); /* note this doesn't return anything! */
  }

But yes, it's not possible with the current functions.

I like this one most, and as we manage our own memory via the
alloc variable we also would not see a lot of memory churn for constant
push/pop traffic.

You can also use a list.h linked-list. Then removal from the list and
freeing are two separate operations (but it exercises your malloc a lot
more if you're constantly pushing and popping).

For that I'd have to define my own type derived from list.h to carry
the string and the util pointer, which looks very similar to the string_list
we already have from a users POV.

quoted

quoted

Where that falls down is if you really need work_on() to put more items
on the stack, but only after you've removed the current top. But then
writing it out may still be nicer, because it makes it clear you have to
do:

  const char *cur_string = xstrdup(list->items[list->nr-1].string);

Another way would be to use

  string_list_pop(&list, &string_dst, &util_dst);
i.e.
  /* Returns 0 if the dst was filled */
  int (struct string_list *, char **, void**)

as then we do not expose the internals and would not have issues
with reallocs.

Yes, I almost suggested that, but there's the question of memory
ownership of string_dst. Does it need freed or not? Is that answer
dependent on the strdup_strings flag?

Sure. But as the caller, you should know?
You constructed that string_list.