core: refactor nm_settings_get_connections_sorted() to return array instead of GSList

We call these functions a lot. A GSList is just the wrong tool for the
job. Refactor the code to use instead a sorted array everywhere.

This means, we malloc() one array for all connections instead
slice-allocate a GSList item for each. Also, sorting an array
is faster then sorting a GSList.
Technically, the GSList implementation had the same big-O runtime
complexity, but using an array is still faster. That is, sorting
an array and a GSList is both O(n*log(n)).

Actually, nm_settings_get_connections_sorted() used
g_slist_insert_sorted() instead of g_slist_sort(). That results
in O(n^2). That could have been fixed to have O(n*log(n)), but
instead refactor the code to use an array.

5 files changed, 100 insertions, 85 deletions

diff --git a/src/nm-checkpoint.c b/src/nm-checkpoint.c
index 7d89e61ef8..08242ac60f 100644
--- a/src/nm-checkpoint.c
+++ b/src/nm-checkpoint.c
@@ -249,14 +249,14 @@ next_dev:
 
 	if (NM_FLAGS_HAS (priv->flags, NM_CHECKPOINT_CREATE_FLAG_DELETE_NEW_CONNECTIONS)) {
 		NMSettingsConnection *con;
-		gs_free_slist GSList *list = NULL;
-		GSList *item;
+		gs_free NMSettingsConnection **list = NULL;
+		guint i;
 
 		g_return_val_if_fail (priv->connection_uuids, NULL);
-		list = nm_settings_get_connections_sorted (nm_settings_get ());
+		list = nm_settings_get_connections_sorted (nm_settings_get (), NULL);
 
-		for (item = list; item; item = g_slist_next (item)) {
-			con = item->data;
+		for (i = 0; list[i]; i++) {
+			con = list[i];
 			if (!g_hash_table_contains (priv->connection_uuids,
 			                            nm_settings_connection_get_uuid (con))) {
 				_LOGD ("rollback: deleting new connection %s (%s)",
diff --git a/src/nm-manager.c b/src/nm-manager.c
index 3cb158e082..fef1f6b2d9 100644
--- a/src/nm-manager.c
+++ b/src/nm-manager.c
@@ -433,18 +433,17 @@ GSList *
 nm_manager_get_activatable_connections (NMManager *manager)
 {
 	NMManagerPrivate *priv = NM_MANAGER_GET_PRIVATE (manager);
-	GSList *all_connections = nm_settings_get_connections_sorted (priv->settings);
-	GSList *connections = NULL, *iter;
+	gs_free NMSettingsConnection **all_connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	GSList *connections = NULL;
 	NMSettingsConnection *connection;
+	guint i;
 
-	for (iter = all_connections; iter; iter = iter->next) {
-		connection = iter->data;
-
+	for (i = 0; all_connections[i]; i++) {
+		connection = all_connections[i];
 		if (!find_ac_for_connection (manager, NM_CONNECTION (connection)))
 			connections = g_slist_prepend (connections, connection);
 	}
 
-	g_slist_free (all_connections);
 	return g_slist_reverse (connections);
 }
 
@@ -1205,7 +1204,8 @@ system_create_virtual_device (NMManager *self, NMConnection *connection)
 {
 	NMManagerPrivate *priv = NM_MANAGER_GET_PRIVATE (self);
 	NMDeviceFactory *factory;
-	gs_free_slist GSList *connections = NULL;
+	gs_free NMSettingsConnection **connections = NULL;
+	guint i;
 	GSList *iter;
 	gs_free char *iface = NULL;
 	NMDevice *device = NULL, *parent = NULL;
@@ -1276,9 +1276,9 @@ system_create_virtual_device (NMManager *self, NMConnection *connection)
 	}
 
 	/* Create backing resources if the device has any autoconnect connections */
-	connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = connections; iter; iter = g_slist_next (iter)) {
-		NMConnection *candidate = iter->data;
+	connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; connections[i]; i++) {
+		NMConnection *candidate = NM_CONNECTION (connections[i]);
 		NMSettingConnection *s_con;
 
 		if (!nm_device_check_connection_compatible (device, candidate))
@@ -1307,13 +1307,14 @@ static void
 retry_connections_for_parent_device (NMManager *self, NMDevice *device)
 {
 	NMManagerPrivate *priv = NM_MANAGER_GET_PRIVATE (self);
-	GSList *connections, *iter;
+	gs_free NMSettingsConnection **connections = NULL;
+	guint i;
 
 	g_return_if_fail (device);
 
-	connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = connections; iter; iter = g_slist_next (iter)) {
-		NMConnection *candidate = iter->data;
+	connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; connections[i]; i++) {
+		NMConnection *candidate = NM_CONNECTION (connections[i]);
 		gs_free_error GError *error = NULL;
 		gs_free char *ifname = NULL;
 		NMDevice *parent;
@@ -1328,8 +1329,6 @@ retry_connections_for_parent_device (NMManager *self, NMDevice *device)
 			}
 		}
 	}
-
-	g_slist_free (connections);
 }
 
 static void
@@ -2775,7 +2774,8 @@ find_slaves (NMManager *manager,
              NMDevice *device)
 {
 	NMManagerPrivate *priv = NM_MANAGER_GET_PRIVATE (manager);
-	GSList *all_connections, *iter;
+	gs_free NMSettingsConnection **all_connections = NULL;
+	guint i;
 	GSList *slaves = NULL;
 	NMSettingConnection *s_con;
 
@@ -2786,11 +2786,11 @@ find_slaves (NMManager *manager,
 	 * even if a slave was already active, it might be deactivated during
 	 * master reactivation.
 	 */
-	all_connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = all_connections; iter; iter = iter->next) {
+	all_connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; all_connections[i]; i++) {
 		NMSettingsConnection *master_connection = NULL;
 		NMDevice *master_device = NULL;
-		NMConnection *candidate = iter->data;
+		NMConnection *candidate = NM_CONNECTION (all_connections[i]);
 
 		find_master (manager, candidate, NULL, &master_connection, &master_device, NULL, NULL);
 		if (   (master_connection && master_connection == connection)
@@ -2798,7 +2798,6 @@ find_slaves (NMManager *manager,
 			slaves = g_slist_prepend (slaves, candidate);
 		}
 	}
-	g_slist_free (all_connections);
 
 	return g_slist_reverse (slaves);
 }
@@ -3813,7 +3812,17 @@ impl_manager_add_and_activate_connection (NMManager *self,
 	if (!subject)
 		goto error;
 
-	all_connections = nm_settings_get_connections_sorted (priv->settings);
+	{
+		gs_free NMSettingsConnection **connections = NULL;
+		guint i, len;
+
+		connections = nm_settings_get_connections_sorted (priv->settings, &len);
+		all_connections = NULL;
+		for (i = len; i > 0; ) {
+			i--;
+			all_connections = g_slist_prepend (all_connections, connections[i]);
+		}
+	}
 	if (vpn) {
 		/* Try to fill the VPN's connection setting and name at least */
 		if (!nm_connection_get_setting_vpn (connection)) {
@@ -4770,7 +4779,7 @@ gboolean
 nm_manager_start (NMManager *self, GError **error)
 {
 	NMManagerPrivate *priv = NM_MANAGER_GET_PRIVATE (self);
-	GSList *iter, *connections;
+	gs_free NMSettingsConnection **connections = NULL;
 	guint i;
 
 	if (!nm_settings_start (priv->settings, error))
@@ -4822,10 +4831,9 @@ nm_manager_start (NMManager *self, GError **error)
 	 * connection-added signals thus devices have to be created manually.
 	 */
 	_LOGD (LOGD_CORE, "creating virtual devices...");
-	connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = connections; iter; iter = iter->next)
-		connection_changed (self, NM_CONNECTION (iter->data));
-	g_slist_free (connections);
+	connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; connections[i]; i++)
+		connection_changed (self, NM_CONNECTION (connections[i]));
 
 	priv->devices_inited = TRUE;
 
diff --git a/src/nm-policy.c b/src/nm-policy.c
index aebd843e3e..92de1e38ec 100644
--- a/src/nm-policy.c
+++ b/src/nm-policy.c
@@ -1149,7 +1149,8 @@ static void
 reset_autoconnect_all (NMPolicy *self, NMDevice *device)
 {
 	NMPolicyPrivate *priv = NM_POLICY_GET_PRIVATE (self);
-	GSList *connections, *iter;
+	gs_free NMSettingsConnection **connections = NULL;
+	guint i;
 
 	if (device) {
 		_LOGD (LOGD_DEVICE, "re-enabling autoconnect for all connections on %s",
@@ -1157,41 +1158,43 @@ reset_autoconnect_all (NMPolicy *self, NMDevice *device)
 	} else
 		_LOGD (LOGD_DEVICE, "re-enabling autoconnect for all connections");
 
-	connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = connections; iter; iter = g_slist_next (iter)) {
-		if (!device || nm_device_check_connection_compatible (device, iter->data)) {
-			nm_settings_connection_reset_autoconnect_retries (iter->data);
-			nm_settings_connection_set_autoconnect_blocked_reason (iter->data, NM_DEVICE_STATE_REASON_NONE);
+	connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; connections[i]; i++) {
+		NMSettingsConnection *connection = connections[i];
+
+		if (!device || nm_device_check_connection_compatible (device, NM_CONNECTION (connection))) {
+			nm_settings_connection_reset_autoconnect_retries (connection);
+			nm_settings_connection_set_autoconnect_blocked_reason (connection, NM_DEVICE_STATE_REASON_NONE);
 		}
 	}
-	g_slist_free (connections);
 }
 
 static void
 reset_autoconnect_for_failed_secrets (NMPolicy *self)
 {
 	NMPolicyPrivate *priv = NM_POLICY_GET_PRIVATE (self);
-	GSList *connections, *iter;
+	gs_free NMSettingsConnection **connections = NULL;
+	guint i;
 
 	_LOGD (LOGD_DEVICE, "re-enabling autoconnect for all connections with failed secrets");
 
-	connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = connections; iter; iter = g_slist_next (iter)) {
-		NMSettingsConnection *connection = NM_SETTINGS_CONNECTION (iter->data);
+	connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; connections[i]; i++) {
+		NMSettingsConnection *connection = connections[i];
 
 		if (nm_settings_connection_get_autoconnect_blocked_reason (connection) == NM_DEVICE_STATE_REASON_NO_SECRETS) {
 			nm_settings_connection_reset_autoconnect_retries (connection);
 			nm_settings_connection_set_autoconnect_blocked_reason (connection, NM_DEVICE_STATE_REASON_NONE);
 		}
 	}
-	g_slist_free (connections);
 }
 
 static void
 block_autoconnect_for_device (NMPolicy *self, NMDevice *device)
 {
 	NMPolicyPrivate *priv = NM_POLICY_GET_PRIVATE (self);
-	GSList *connections, *iter;
+	gs_free NMSettingsConnection **connections = NULL;
+	guint i;
 
 	_LOGD (LOGD_DEVICE, "blocking autoconnect for all connections on %s",
 	       nm_device_get_iface (device));
@@ -1203,14 +1206,15 @@ block_autoconnect_for_device (NMPolicy *self, NMDevice *device)
 	if (!nm_device_is_software (device))
 		return;
 
-	connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = connections; iter; iter = g_slist_next (iter)) {
-		if (nm_device_check_connection_compatible (device, iter->data)) {
-			nm_settings_connection_set_autoconnect_blocked_reason (NM_SETTINGS_CONNECTION (iter->data),
+	connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; connections[i]; i++) {
+		NMSettingsConnection *connection = connections[i];
+
+		if (nm_device_check_connection_compatible (device, NM_CONNECTION (connection))) {
+			nm_settings_connection_set_autoconnect_blocked_reason (connection,
 			                                                       NM_DEVICE_STATE_REASON_USER_REQUESTED);
 		}
 	}
-	g_slist_free (connections);
 }
 
 static void
@@ -1278,7 +1282,8 @@ reset_connections_retries (gpointer user_data)
 {
 	NMPolicy *self = (NMPolicy *) user_data;
 	NMPolicyPrivate *priv = NM_POLICY_GET_PRIVATE (self);
-	GSList *connections, *iter;
+	gs_free NMSettingsConnection **connections = NULL;
+	guint i;
 	gint32 con_stamp, min_stamp, now;
 	gboolean changed = FALSE;
 
@@ -1286,9 +1291,9 @@ reset_connections_retries (gpointer user_data)
 
 	min_stamp = 0;
 	now = nm_utils_get_monotonic_timestamp_s ();
-	connections = nm_settings_get_connections_sorted (priv->settings);
-	for (iter = connections; iter; iter = g_slist_next (iter)) {
-		NMSettingsConnection *connection = NM_SETTINGS_CONNECTION (iter->data);
+	connections = nm_settings_get_connections_sorted (priv->settings, NULL);
+	for (i = 0; connections[i]; i++) {
+		NMSettingsConnection *connection = connections[i];
 
 		con_stamp = nm_settings_connection_get_autoconnect_retry_time (connection);
 		if (con_stamp == 0)
@@ -1300,7 +1305,6 @@ reset_connections_retries (gpointer user_data)
 		} else if (min_stamp == 0 || min_stamp > con_stamp)
 			min_stamp = con_stamp;
 	}
-	g_slist_free (connections);
 
 	/* Schedule the handler again if there are some stamps left */
 	if (min_stamp != 0)
@@ -1318,8 +1322,7 @@ activate_slave_connections (NMPolicy *self, NMDevice *device)
 {
 	NMPolicyPrivate *priv = NM_POLICY_GET_PRIVATE (self);
 	const char *master_device, *master_uuid_settings = NULL, *master_uuid_applied = NULL;
-	gs_free_slist GSList *connections = NULL;
-	GSList *iter;
+	guint i;
 	NMActRequest *req;
 	gboolean internal_activation = FALSE;
 
@@ -1345,27 +1348,29 @@ activate_slave_connections (NMPolicy *self, NMDevice *device)
 		internal_activation = subject && nm_auth_subject_is_internal (subject);
 	}
 
-	if (!internal_activation)
-		connections = nm_settings_get_connections_sorted (priv->settings);
+	if (!internal_activation) {
+		gs_free NMSettingsConnection **connections = NULL;
 
-	for (iter = connections; iter; iter = g_slist_next (iter)) {
-		NMConnection *slave;
-		NMSettingConnection *s_slave_con;
-		const char *slave_master;
+		connections = nm_settings_get_connections_sorted (priv->settings, NULL);
 
-		slave = NM_CONNECTION (iter->data);
-		g_assert (slave);
+		for (i = 0; connections[i]; i++) {
+			NMConnection *slave;
+			NMSettingConnection *s_slave_con;
+			const char *slave_master;
 
-		s_slave_con = nm_connection_get_setting_connection (slave);
-		g_assert (s_slave_con);
-		slave_master = nm_setting_connection_get_master (s_slave_con);
-		if (!slave_master)
-			continue;
+			slave = NM_CONNECTION (connections[i]);
+
+			s_slave_con = nm_connection_get_setting_connection (slave);
+			g_assert (s_slave_con);
+			slave_master = nm_setting_connection_get_master (s_slave_con);
+			if (!slave_master)
+				continue;
 
-		if (   !g_strcmp0 (slave_master, master_device)
-		    || !g_strcmp0 (slave_master, master_uuid_applied)
-		    || !g_strcmp0 (slave_master, master_uuid_settings))
-			nm_settings_connection_reset_autoconnect_retries (NM_SETTINGS_CONNECTION (slave));
+			if (   !g_strcmp0 (slave_master, master_device)
+			    || !g_strcmp0 (slave_master, master_uuid_applied)
+			    || !g_strcmp0 (slave_master, master_uuid_settings))
+				nm_settings_connection_reset_autoconnect_retries (NM_SETTINGS_CONNECTION (slave));
+		}
 	}
 
 	schedule_activate_all (self);
diff --git a/src/settings/nm-settings.c b/src/settings/nm-settings.c
index 057d341d4b..1739a32fef 100644
--- a/src/settings/nm-settings.c
+++ b/src/settings/nm-settings.c
@@ -494,21 +494,22 @@ nm_settings_get_connections_clone (NMSettings *self,
 /* Returns a list of NMSettingsConnections.
  * The list is sorted in the order suitable for auto-connecting, i.e.
  * first go connections with autoconnect=yes and most recent timestamp.
- * Caller must free the list with g_slist_free().
+ * Caller must free the list with g_free(), but not the list items.
  */
-GSList *
-nm_settings_get_connections_sorted (NMSettings *self)
+NMSettingsConnection **
+nm_settings_get_connections_sorted (NMSettings *self, guint *out_len)
 {
-	GHashTableIter iter;
-	gpointer data = NULL;
-	GSList *list = NULL;
+	NMSettingsConnection **connections;
+	guint len;
 
 	g_return_val_if_fail (NM_IS_SETTINGS (self), NULL);
 
-	g_hash_table_iter_init (&iter, NM_SETTINGS_GET_PRIVATE (self)->connections);
-	while (g_hash_table_iter_next (&iter, NULL, &data))
-		list = g_slist_insert_sorted (list, data, (GCompareFunc) nm_settings_connection_cmp_default);
-	return list;
+	connections = nm_settings_get_connections_clone (self, &len, NULL, NULL);
+	if (len > 1)
+		g_qsort_with_data (connections, len, sizeof (NMSettingsConnection *), nm_settings_connection_cmp_default_p_with_data, NULL);
+
+	NM_SET_OUT (out_len, len);
+	return connections;
 }
 
 NMSettingsConnection *
diff --git a/src/settings/nm-settings.h b/src/settings/nm-settings.h
index 09fe2d137e..0771edee13 100644
--- a/src/settings/nm-settings.h
+++ b/src/settings/nm-settings.h
@@ -102,7 +102,8 @@ NMSettingsConnection **nm_settings_get_connections_clone (NMSettings *self,
                                                           NMSettingsConnectionFilterFunc func,
                                                           gpointer func_data);
 
-GSList *nm_settings_get_connections_sorted (NMSettings *settings);
+NMSettingsConnection **nm_settings_get_connections_sorted (NMSettings *self,
+                                                           guint *out_len);
 
 NMSettingsConnection *nm_settings_add_connection (NMSettings *settings,
                                                   NMConnection *connection,