[gobject-introspection: 1/2] Replace linked lists with arrays in source scanner

[Christoph Reiter <creiter src gnome org>]

commit 51f7cb11a4f0a247381be9f69d432cc182d8ffda
Author: Tomasz Miąsko <tomasz miasko gmail com>
Date:   Sun Dec 9 00:00:00 2018 +0000

    Replace linked lists with arrays in source scanner
    
    Reduce total number of memory allocations and increase data locality.

 giscanner/giscannermodule.c | 41 +++++++++++++++-------------------
 giscanner/scannerlexer.l    |  2 +-
 giscanner/scannerparser.y   |  6 ++---
 giscanner/sourcescanner.c   | 54 +++++++++++++++++++++------------------------
 giscanner/sourcescanner.h   | 12 +++++-----
 5 files changed, 53 insertions(+), 62 deletions(-)
---
diff --git a/giscanner/giscannermodule.c b/giscanner/giscannermodule.c
index 24b84050..43f8bdea 100644
--- a/giscanner/giscannermodule.c
+++ b/giscanner/giscannermodule.c
@@ -489,57 +489,54 @@ pygi_source_scanner_set_macro_scan (PyGISourceScanner *self,
 static PyObject *
 pygi_source_scanner_get_symbols (PyGISourceScanner *self, G_GNUC_UNUSED PyObject *unused)
 {
-  GSList *l, *symbols;
+  GPtrArray *symbols;
   PyObject *list;
-  int i = 0;
+  guint i = 0;
 
   symbols = gi_source_scanner_get_symbols (self->scanner);
-  list = PyList_New (g_slist_length (symbols));
+  list = PyList_New (symbols->len);
 
-  for (l = symbols; l; l = l->next)
+  for (i = 0; i != symbols->len; ++i)
     {
-      PyObject *item = pygi_source_symbol_new (l->data);
-      PyList_SetItem (list, i++, item);
+      PyObject *item = pygi_source_symbol_new (g_ptr_array_index (symbols, i));
+      PyList_SetItem (list, i, item);
     }
 
-  g_slist_free (symbols);
-  Py_INCREF (list);
   return list;
 }
 
 static PyObject *
 pygi_source_scanner_get_errors (PyGISourceScanner *self, G_GNUC_UNUSED PyObject *unused)
 {
-  GSList *l, *errors;
+  GPtrArray *errors;
   PyObject *list;
-  int i = 0;
+  guint i = 0;
 
   errors = gi_source_scanner_get_errors (self->scanner);
-  list = PyList_New (g_slist_length (errors));
+  list = PyList_New (errors->len);
 
-  for (l = errors; l; l = l->next)
+  for (i = 0; i != errors->len; ++i)
     {
-      PyObject *item = PyUnicode_FromString (l->data);
-      PyList_SetItem (list, i++, item);
+      PyObject *item = PyUnicode_FromString (g_ptr_array_index (errors, i));
+      PyList_SetItem (list, i, item);
     }
 
-  g_slist_free (errors);
   return list;
 }
 
 static PyObject *
 pygi_source_scanner_get_comments (PyGISourceScanner *self, G_GNUC_UNUSED PyObject *unused)
 {
-  GSList *l, *comments;
+  GPtrArray *comments;
   PyObject *list;
-  int i = 0;
+  guint i = 0;
 
   comments = gi_source_scanner_get_comments (self->scanner);
-  list = PyList_New (g_slist_length (comments));
+  list = PyList_New (comments->len);
 
-  for (l = comments; l; l = l->next)
+  for (i = 0; i != comments->len; ++i)
     {
-      GISourceComment *comment = l->data;
+      GISourceComment *comment = g_ptr_array_index (comments, i);
       PyObject *comment_obj;
       PyObject *filename_obj;
       PyObject *item;
@@ -571,14 +568,12 @@ pygi_source_scanner_get_comments (PyGISourceScanner *self, G_GNUC_UNUSED PyObjec
         }
 
       item = Py_BuildValue ("(OOi)", comment_obj, filename_obj, comment->line);
-      PyList_SetItem (list, i++, item);
+      PyList_SetItem (list, i, item);
 
       Py_DECREF (comment_obj);
       Py_DECREF (filename_obj);
     }
 
-  g_slist_free (comments);
-  Py_INCREF (list);
   return list;
 }
 
diff --git a/giscanner/scannerlexer.l b/giscanner/scannerlexer.l
index 42e79d42..d3a6017e 100644
--- a/giscanner/scannerlexer.l
+++ b/giscanner/scannerlexer.l
@@ -515,7 +515,7 @@ print_error (GISourceScanner *scanner)
   if (yytext[0]) {
     char *filename = g_file_get_parse_name (scanner->current_file);
     gchar *error = g_strdup_printf ("%s:%d: unexpected character `%c'", filename, lineno, yytext[0]);
-    scanner->errors = g_slist_prepend (scanner->errors, error);
+    g_ptr_array_add (scanner->errors, error);
     g_free (filename);
   }
 }
diff --git a/giscanner/scannerparser.y b/giscanner/scannerparser.y
index 72c17ec3..182c69d3 100644
--- a/giscanner/scannerparser.y
+++ b/giscanner/scannerparser.y
@@ -166,7 +166,7 @@ pop_conditional (GISourceScanner *scanner)
     {
       gchar *filename = g_file_get_path (scanner->current_file);
       gchar *error = g_strdup_printf ("%s:%d: mismatched %s", filename, lineno, yytext);
-      scanner->errors = g_slist_prepend (scanner->errors, error);
+      g_ptr_array_add (scanner->errors, error);
       g_free (filename);
     }
 
@@ -183,7 +183,7 @@ warn_if_cond_has_gi_scanner (GISourceScanner *scanner,
       gchar *filename = g_file_get_path (scanner->current_file);
       gchar *error = g_strdup_printf ("%s:%d: the __GI_SCANNER__ constant should only be used with simple 
#ifdef or #endif: %s",
                filename, lineno, text);
-      scanner->errors = g_slist_prepend (scanner->errors, error);
+      g_ptr_array_add (scanner->errors, error);
       g_free (filename);
     }
 }
@@ -1571,7 +1571,7 @@ yyerror (GISourceScanner *scanner, const char *s)
     {
       gchar *error = g_strdup_printf ("%s:%d: %s in '%s' at '%s'",
           g_file_get_parse_name (scanner->current_file), lineno, s, linebuf, yytext);
-      scanner->errors = g_slist_prepend (scanner->errors, error);
+      g_ptr_array_add (scanner->errors, error);
     }
 }
 
diff --git a/giscanner/sourcescanner.c b/giscanner/sourcescanner.c
index 4d10c88b..27f82f77 100644
--- a/giscanner/sourcescanner.c
+++ b/giscanner/sourcescanner.c
@@ -210,6 +210,14 @@ gi_source_function_new (void)
   return func;
 }
 
+static void
+gi_source_comment_free (GISourceComment *comment)
+{
+  g_free (comment->comment);
+  g_free (comment->filename);
+  g_slice_free (GISourceComment, comment);
+}
+
 GISourceScanner *
 gi_source_scanner_new (void)
 {
@@ -222,18 +230,13 @@ gi_source_scanner_new (void)
                                                 (GDestroyNotify) gi_source_symbol_unref);
   scanner->files = g_hash_table_new_full (g_file_hash, (GEqualFunc)g_file_equal,
                                           g_object_unref, NULL);
+  scanner->symbols = g_ptr_array_new_with_free_func ((GDestroyNotify) gi_source_comment_free);
+  scanner->comments = g_ptr_array_new_with_free_func ((GDestroyNotify) gi_source_symbol_unref);
+  scanner->errors = g_ptr_array_new_with_free_func (g_free);
   g_queue_init (&scanner->conditionals);
   return scanner;
 }
 
-static void
-gi_source_comment_free (GISourceComment *comment)
-{
-  g_free (comment->comment);
-  g_free (comment->filename);
-  g_slice_free (GISourceComment, comment);
-}
-
 void
 gi_source_scanner_free (GISourceScanner *scanner)
 {
@@ -242,11 +245,9 @@ gi_source_scanner_free (GISourceScanner *scanner)
   g_hash_table_destroy (scanner->typedef_table);
   g_hash_table_destroy (scanner->const_table);
 
-  g_slist_foreach (scanner->comments, (GFunc)(void *)gi_source_comment_free, NULL);
-  g_slist_free (scanner->comments);
-  g_slist_foreach (scanner->symbols, (GFunc)(void *)gi_source_symbol_unref, NULL);
-  g_slist_free (scanner->symbols);
-  g_slist_free_full (scanner->errors, g_free);
+  g_ptr_array_free (scanner->symbols, TRUE);
+  g_ptr_array_free (scanner->comments, TRUE);
+  g_ptr_array_free (scanner->errors, TRUE);
 
   g_hash_table_unref (scanner->files);
 
@@ -281,8 +282,7 @@ gi_source_scanner_add_symbol (GISourceScanner  *scanner,
   g_assert (scanner->current_file);
 
   if (scanner->macro_scan || g_hash_table_contains (scanner->files, scanner->current_file))
-    scanner->symbols = g_slist_prepend (scanner->symbols,
-                                        gi_source_symbol_ref (symbol));
+    g_ptr_array_add (scanner->symbols, gi_source_symbol_ref (symbol));
 
   g_assert (symbol->source_filename != NULL);
 
@@ -309,45 +309,41 @@ gi_source_scanner_take_comment (GISourceScanner *scanner,
       return;
     }
 
-  scanner->comments = g_slist_prepend (scanner->comments,
-                                       comment);
+  g_ptr_array_add (scanner->comments, comment);
 }
 
 /**
  * gi_source_scanner_get_symbols:
  * @scanner: scanner instance
  *
- * Returns: (transfer container): List of GISourceSymbol.
- *   Free resulting list with g_slist_free().
+ * Returns: (transfer none): Array of GISourceSymbol.
  */
-GSList *
+GPtrArray *
 gi_source_scanner_get_symbols (GISourceScanner  *scanner)
 {
-  return g_slist_reverse (g_slist_copy (scanner->symbols));
+  return scanner->symbols;
 }
 
 /**
  * gi_source_scanner_get_errors:
  * @scanner: scanner instance
  *
- * Returns: (transfer container): List of strings.
- *   Free resulting list with g_slist_free().
+ * Returns: (transfer none): Array of strings.
  */
-GSList *
+GPtrArray *
 gi_source_scanner_get_errors (GISourceScanner  *scanner)
 {
-  return g_slist_reverse (g_slist_copy (scanner->errors));
+  return scanner->errors;
 }
 
 /**
  * gi_source_scanner_get_comments:
  * @scanner: scanner instance
  *
- * Returns: (transfer container): List of GISourceComment.
- *   Free resulting list with g_slist_free().
+ * Returns: (transfer none): Array of GISourceComment.
  */
-GSList *
+GPtrArray *
 gi_source_scanner_get_comments(GISourceScanner  *scanner)
 {
-  return g_slist_reverse (g_slist_copy (scanner->comments));
+  return scanner->comments;
 }
diff --git a/giscanner/sourcescanner.h b/giscanner/sourcescanner.h
index bcf1afc4..a788abe9 100644
--- a/giscanner/sourcescanner.h
+++ b/giscanner/sourcescanner.h
@@ -111,14 +111,14 @@ struct _GISourceScanner
   gboolean macro_scan;
   gboolean private; /* set by gtk-doc comment <private>/<public> */
   gboolean flags; /* set by gtk-doc comment <flags> */
-  GSList *symbols;
+  GPtrArray *symbols; /* GISourceSymbol */
   GHashTable *files;
-  GSList *comments; /* _GIComment */
+  GPtrArray *comments; /* GISourceComment */
   GHashTable *typedef_table;
   GHashTable *const_table;
   gboolean skipping;
   GQueue conditionals;
-  GSList *errors;
+  GPtrArray *errors;
 };
 
 struct _GISourceSymbol
@@ -161,9 +161,9 @@ void                gi_source_scanner_parse_macros     (GISourceScanner  *scanne
                                                        GList            *filenames);
 void                gi_source_scanner_set_macro_scan   (GISourceScanner  *scanner,
                                                        gboolean          macro_scan);
-GSList *            gi_source_scanner_get_symbols      (GISourceScanner  *scanner);
-GSList *            gi_source_scanner_get_comments     (GISourceScanner  *scanner);
-GSList *            gi_source_scanner_get_errors       (GISourceScanner  *scanner);
+GPtrArray *         gi_source_scanner_get_symbols      (GISourceScanner  *scanner);
+GPtrArray *         gi_source_scanner_get_comments     (GISourceScanner  *scanner);
+GPtrArray *         gi_source_scanner_get_errors       (GISourceScanner  *scanner);
 void                gi_source_scanner_free             (GISourceScanner  *scanner);
 
 GISourceSymbol *    gi_source_symbol_new               (GISourceSymbolType  type, GFile *file, int line);