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@xxxxxxxxxx> > > --- > > 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 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. Or alternatively even use 2 additional size variables, see VIR_RESIZE_N to avoid reallocations for maximum optimization.
