[PATCH 07/40] util: Add helpers for auto-freeing GSList filled with strings

[Michal Privoznik]

On 2/9/21 3:48 PM, Peter Krempa wrote:
> On Tue, Feb 09, 2021 at 15:22:40 +0100, Michal Privoznik wrote:
>> On 2/6/21 9:32 AM, Peter Krempa wrote:
>>> glib's 'g_autoslist()' doesn't support lists of 'char *' strings. Add a
>>> type alias 'virGSListString' so that we can register an 'autoptr'
>>> function for it for simple usage of GSList with strings.
>>>
>>> Signed-off-by: Peter Krempa <pkrempa at redhat.com>
>>> ---
>>>    src/libvirt_private.syms |  4 ++++
>>>    src/util/meson.build     |  1 +
>>>    src/util/virglibutil.c   | 27 +++++++++++++++++++++++++++
>>>    src/util/virglibutil.h   | 28 ++++++++++++++++++++++++++++
>>>    4 files changed, 60 insertions(+)
>>>    create mode 100644 src/util/virglibutil.c
>>>    create mode 100644 src/util/virglibutil.h
>>>
>>
>>
>>> diff --git a/src/util/virglibutil.h b/src/util/virglibutil.h
>>> new file mode 100644
>>> index 0000000000..2bff69f22f
>>> --- /dev/null
>>> +++ b/src/util/virglibutil.h
>>> @@ -0,0 +1,28 @@
>>> +/*
>>> + * virglibutil.h: Utilities helping with glib usage
>>> + *
>>> + * This library is free software; you can redistribute it and/or
>>> + * modify it under the terms of the GNU Lesser General Public
>>> + * License as published by the Free Software Foundation; either
>>> + * version 2.1 of the License, or (at your option) any later version.
>>> + *
>>> + * This library is distributed in the hope that it will be useful,
>>> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
>>> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
>>> + * Lesser General Public License for more details.
>>> + *
>>> + * You should have received a copy of the GNU Lesser General Public
>>> + * License along with this library.  If not, see
>>> + * <http://www.gnu.org/licenses/>.
>>> + */
>>> +
>>> +#pragma once
>>> +
>>> +#include "internal.h"
>>> +
>>> +void
>>> +virGSListStringFree(GSList *l);
>>> +
>>> +typedef GSList virGSListString;
>>
>> So, GSList is a singly linked list. This doubles memory usage because for
>> every string we have to also store pointer to next. Is O(n^2) that bad so
>> that we have to sacrifice memory complexity?
> 
> Firstly, for any cases where we know the number of elements or at least
> a sane upper bound before inserting, we still keep using a char **.
> 
> This leaves us with places that don't know how many elements there will
> be which insert:
> 1) a lot of elements -> definitely worth the overhead
> 2) a few elements -> the overhead is comparatively small

Yeah, this is my assumption (based in my experience with small 
machines), that we usually have very few items on string lists (thinking 
of namespace code, cgroup code and likes).

> 
> In places we might want to care about memory complexity, the code can
> use a char ** list with a counter variable instead of the GSList to
> avoid both memory and computational complexity, but not memory
> fragmentation issues where a (singly) linked list prevents memory copy
> when enlarging.

Yeah. I guess I'm more fan of arrays then lists because arrays are more 
cache friendly than linked lists.

> 
> Or alternatively even use 2 additional size variables, see VIR_RESIZE_N
> to avoid reallocations for maximum optimization.
> 

Hopefully we don't care about performance that much.

<rant>I am also not fan of glib. That may be another reason that I 
prefer our own implementation. It suits our needs better.</rant>

Michal