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

[Patrick Griffis <pgriffis src gnome org>]

commit 9f83c6329c801788a7d3039cc0ccee41f414d49d
Author: Patrick Griffis <tingping tingping se>
Date:   Tue Nov 6 13:36:19 2018 -0500

    gnetworkaddress: Interleave ipv4 and ipv6 addresses

 gio/gnetworkaddress.c       | 157 ++++++++++++++++++++++++++++++++++++++++----
 gio/tests/network-address.c |   2 -
 2 files changed, 143 insertions(+), 16 deletions(-)
---
diff --git a/gio/gnetworkaddress.c b/gio/gnetworkaddress.c
index 39ce3bf6f..618e79897 100644
--- a/gio/gnetworkaddress.c
+++ b/gio/gnetworkaddress.c
@@ -884,6 +884,7 @@ typedef struct {
 
   GNetworkAddress *addr; /* (owned) */
   GList *addresses; /* (owned) (nullable) */
+  GList *last_tail; /* (unowned) (nullable) */
   GList *current_item; /* (unowned) (nullable) */
   GTask *queued_task; /* (owned) (nullable) */
   GError *last_error; /* (owned) (nullable) */
@@ -919,6 +920,125 @@ g_network_address_address_enumerator_finalize (GObject *object)
   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);
+      switch (family)
+        {
+          case G_SOCKET_FAMILY_IPV4:
+            *out_ipv4 = g_list_prepend (*out_ipv4, list->data);
+            break;
+          case G_SOCKET_FAMILY_IPV6:
+            *out_ipv6 = g_list_prepend (*out_ipv6, list->data);
+            break;
+          case G_SOCKET_FAMILY_INVALID:
+          case G_SOCKET_FAMILY_UNIX:
+            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_families (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 container): List to copy
+ *
+ * Does a shallow copy of a list with address families interleaved.
+ *
+ * For example:
+ *   Input: [ipv6, ipv6, ipv4, ipv4]
+ *   Output: [ipv6, ipv4, ipv6, ipv4]
+ *
+ * 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_families (ipv6, ipv4);
+}
+
+/* list_concat_interleaved:
+ * @current_item: (transfer container): Already existing list
+ * @new_list: (transfer none): New list to be interleaved and concatenated
+ *
+ * This differs from g_list_concat() + list_copy_interleaved() in that it sorts
+ * items in the previous list starting from @current_item.
+ *
+ * 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 (trailing)
+    g_list_free (trailing);
+
+  if (last_family == G_SOCKET_FAMILY_IPV4)
+    interleaved = list_interleave_families (ipv6, ipv4);
+  else
+    interleaved = list_interleave_families (ipv4, ipv6);
+
+  return g_list_concat (current_item, interleaved);
+}
+
 static GSocketAddress *
 g_network_address_address_enumerator_next (GSocketAddressEnumerator  *enumerator,
                                            GCancellable              *cancellable,
@@ -960,8 +1080,8 @@ g_network_address_address_enumerator_next (GSocketAddressEnumerator  *enumerator
           g_network_address_add_addresses (addr, g_steal_pointer (&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);
     }
 
@@ -980,13 +1100,11 @@ complete_queued_task (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;
 
@@ -1180,17 +1298,28 @@ g_network_address_address_enumerator_next_async (GSocketAddressEnumerator  *enum
   if (addr_enum->addresses == NULL)
     {
       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 c10f84139..4a2718e24 100644
--- a/gio/tests/network-address.c
+++ b/gio/tests/network-address.c
@@ -707,8 +707,6 @@ test_happy_eyeballs_slow_connection_and_ipv4 (HappyEyeballsFixture *fixture,
   g_main_loop_run (fixture->loop);
 
   assert_list_matches_expected (data.addrs, fixture->input_all_results);
-  /* Note that interleaving will not happen here because ipv6 was used before ipv4
-   * responded */
 }
 
 static void