[PATCH 07/40] util: Add helpers for auto-freeing GSList filled with strings
Peter Krempa
pkrempa at redhat.com
Tue Feb 9 14:48:31 UTC 2021
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
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.
More information about the libvir-list
mailing list