[glib/wip/tingping/happy-eyeballs] gnetworkaddress: Interleave ipv4 and ipv6 addresses

[Patrick Griffis <pgriffis src gnome org>]

commit 1b029bd1c6f082f845ad9252a580ce3eb30a1e86
Author: Patrick Griffis <pgriffis igalia com>
Date:   Mon Oct 29 14:36:31 2018 -0400

    gnetworkaddress: Interleave ipv4 and ipv6 addresses

 gio/gnetworkaddress.c       | 146 +++++++++++++++++++++++++++++++++++++++-----
 gio/tests/network-address.c |  25 +++++++-
 2 files changed, 156 insertions(+), 15 deletions(-)
---
diff --git a/gio/gnetworkaddress.c b/gio/gnetworkaddress.c
index fe7629853..86cf11592 100644
--- a/gio/gnetworkaddress.c
+++ b/gio/gnetworkaddress.c
@@ -875,6 +875,7 @@ typedef struct {
 
   GNetworkAddress *addr;
   GList *addresses;
+  GList *last_tail;
   GList *current_item;
   GTask *queued_task;
   GError *last_error;
@@ -899,10 +900,118 @@ g_network_address_address_enumerator_finalize (GObject *object)
   g_clear_object (&addr_enum->queued_task);
   g_clear_error (&addr_enum->last_error);
   g_object_unref (addr_enum->addr);
+  g_clear_pointer (&addr_enum->addresses, g_list_free);
 
   G_OBJECT_CLASS (_g_network_address_address_enumerator_parent_class)->finalize (object);
 }
 
+static inline GSocketFamily
+get_address_family (GInetSocketAddress *address)
+{
+  return g_inet_address_get_family (g_inet_socket_address_get_address (address));
+}
+
+static void
+list_split_families (GList  *list,
+                     GList **out_ipv4,
+                     GList **out_ipv6)
+{
+  g_assert (out_ipv4);
+  g_assert (out_ipv6);
+
+  while (list)
+    {
+      GSocketFamily family = get_address_family (list->data);
+      if (family == G_SOCKET_FAMILY_IPV4)
+        *out_ipv4 = g_list_prepend (*out_ipv4, list->data);
+      else if (family == G_SOCKET_FAMILY_IPV6)
+        *out_ipv6 = g_list_prepend (*out_ipv6, list->data);
+      else
+        g_assert_not_reached ();
+
+      list = g_list_next (list);
+    }
+
+  *out_ipv4 = g_list_reverse (*out_ipv4);
+  *out_ipv6 = g_list_reverse (*out_ipv6);
+}
+
+static GList *
+list_interleave (GList *list1,
+                 GList *list2)
+{
+  GList *interleaved = NULL;
+
+  while (list1 || list2)
+    {
+      if (list1)
+        {
+          interleaved = g_list_append (interleaved, list1->data);
+          list1 = g_list_delete_link (list1, list1);
+        }
+      if (list2)
+        {
+          interleaved = g_list_append (interleaved, list2->data);
+          list2 = g_list_delete_link (list2, list2);
+        }
+    }
+
+  return interleaved;
+}
+
+/* list_copy_interleaved:
+ * @list: (transfer none): List to copy
+ *
+ * Does a shallow copy of a list with address families interleaved.
+ *
+ * Returns: (transfer container): A new list
+ */
+static GList *
+list_copy_interleaved (GList *list)
+{
+  GList *ipv4 = NULL, *ipv6 = NULL;
+
+  list_split_families (list, &ipv4, &ipv6);
+  return list_interleave (ipv6, ipv4);
+}
+
+/* list_concat_interleaved:
+ * @existing_list: (transfer container): Already existing list
+ * @new_list: New list to be interleaved and concatenated
+ *
+ * This differs from g_list_concat() + list_copy_interleaved() in that it takes into
+ * account the items of the previous list into the sorting.
+ *
+ * Returns: (transfer container): New start of list
+ */
+static GList *
+list_concat_interleaved (GList *current_item,
+                         GList *new_list)
+{
+  GList *ipv4 = NULL, *ipv6 = NULL, *interleaved, *trailing = NULL;
+  GSocketFamily last_family = G_SOCKET_FAMILY_IPV4; /* Default to starting with ipv6 */
+
+
+  if (current_item)
+    {
+      last_family = get_address_family (current_item->data);
+
+      /* Unused addresses will get removed, resorted, then readded */
+      trailing = g_list_next (current_item);
+      current_item->next = NULL;
+    }
+
+  list_split_families (trailing, &ipv4, &ipv6);
+  list_split_families (new_list, &ipv4, &ipv6);
+
+  if (last_family == G_SOCKET_FAMILY_IPV4)
+    interleaved = list_interleave (ipv6, ipv4);
+  else
+    interleaved = list_interleave (ipv4, ipv6);
+
+  return g_list_concat (current_item, interleaved);
+}
+
 static GSocketAddress *
 g_network_address_address_enumerator_next (GSocketAddressEnumerator  *enumerator,
                                            GCancellable              *cancellable,
@@ -944,8 +1053,8 @@ g_network_address_address_enumerator_next (GSocketAddressEnumerator  *enumerator
           g_network_address_add_addresses (addr, addresses, serial);
         }
 
-      addr_enum->addresses = addr->priv->sockaddrs;
-      addr_enum->current_item = addr_enum->addresses;
+      addr_enum->current_item = addr_enum->addresses = list_copy_interleaved (addr->priv->sockaddrs);
+      addr_enum->last_tail = g_list_last (addr->priv->sockaddrs);
       g_object_unref (resolver);
     }
 
@@ -963,13 +1072,11 @@ have_addresses (GNetworkAddressAddressEnumerator *addr_enum,
 {
   GSocketAddress *sockaddr;
 
-  addr_enum->addresses = addr_enum->addr->priv->sockaddrs;
-  addr_enum->current_item = addr_enum->addresses;
+  addr_enum->current_item = addr_enum->addresses = list_copy_interleaved (addr_enum->addr->priv->sockaddrs);
+  addr_enum->last_tail = g_list_last (addr_enum->addr->priv->sockaddrs);
 
   if (addr_enum->current_item)
-    {
-      sockaddr = g_object_ref (addr_enum->current_item->data);
-    }
+    sockaddr = g_object_ref (addr_enum->current_item->data);
   else
     sockaddr = NULL;
 
@@ -1143,17 +1250,28 @@ g_network_address_address_enumerator_next_async (GSocketAddressEnumerator  *enum
   if (!addr_enum->addresses)
     {
       g_assert (addr->priv->sockaddrs);
-      addr_enum->addresses = addr->priv->sockaddrs;
-      addr_enum->current_item = addr_enum->addresses;
+
+      addr_enum->current_item = addr_enum->addresses = list_copy_interleaved (addr->priv->sockaddrs);
       sockaddr = g_object_ref (addr_enum->current_item->data);
     }
-  else if (addr_enum->current_item->next)
+  else
     {
-      addr_enum->current_item = g_list_next (addr_enum->current_item);
-      sockaddr = g_object_ref (addr_enum->current_item->data);
+      GList *parent_tail = g_list_last (addr_enum->addr->priv->sockaddrs);
+
+      if (addr_enum->last_tail != parent_tail)
+        {
+          addr_enum->current_item = list_concat_interleaved (addr_enum->current_item, g_list_next 
(addr_enum->last_tail));
+          addr_enum->last_tail = parent_tail;
+        }
+
+      if (addr_enum->current_item->next)
+        {
+          addr_enum->current_item = g_list_next (addr_enum->current_item);
+          sockaddr = g_object_ref (addr_enum->current_item->data);
+        }
+      else
+        sockaddr = NULL;
     }
-  else
-    sockaddr = NULL;
 
   g_task_return_pointer (task, sockaddr, g_object_unref);
   g_object_unref (task);
diff --git a/gio/tests/network-address.c b/gio/tests/network-address.c
index b624bc9d4..7ca3e7892 100644
--- a/gio/tests/network-address.c
+++ b/gio/tests/network-address.c
@@ -115,6 +115,24 @@ test_parse_host (gconstpointer d)
     g_error_free (error);
 }
 
+static void
+assert_list_is_interleaved (GList *result)
+{
+  GSocketFamily last_family = -1;
+
+  while (result)
+    {
+      GInetAddress *address = g_inet_socket_address_get_address (G_INET_SOCKET_ADDRESS (result->data));
+      GSocketFamily family = g_inet_address_get_family (address);
+
+      if (last_family != -1)
+       g_assert_cmpint (family, !=, last_family);
+
+      last_family = family;
+      result = g_list_next (result);
+    }
+}
+
 typedef struct {
   const gchar *input;
   gboolean valid_parse, valid_resolve, valid_ip;
@@ -623,10 +641,12 @@ test_happy_eyeballs_async (void)
 
   /* Sanity check first */
   g_test_message ("Sanity check");
-  data.delay_ms = 1;
+  /* We have a delay because interleaving will (appear to) fail if addresses are consumed too fast */
+  data.delay_ms = 50;
   g_socket_address_enumerator_next_async (enumerator, NULL, got_addr, &data);
   g_main_loop_run (data.loop);
   assert_list_matches_expected (data.addrs, input_all_results);
+  assert_list_is_interleaved (data.addrs);
   CLEANUP ();
 
   /* If ipv4 dns response is a bit slow we just don't get them */
@@ -643,6 +663,7 @@ test_happy_eyeballs_async (void)
   g_socket_address_enumerator_next_async (enumerator, NULL, got_addr, &data);
   g_main_loop_run (data.loop);
   assert_list_matches_expected (data.addrs, input_all_results);
+  assert_list_is_interleaved (data.addrs);
   CLEANUP ();
 
   /* If ipv6 is very slow we don't get them */
@@ -661,6 +682,8 @@ test_happy_eyeballs_async (void)
   g_socket_address_enumerator_next_async (enumerator, NULL, got_addr, &data);
   g_main_loop_run (data.loop);
   assert_list_matches_expected (data.addrs, input_all_results);
+  /* Note that interleaving will not happen here because ipv6 was used before ipv4
+   * responded */
   CLEANUP ();
 
   /* If ipv6 fails we still get ipv4. */