[glib: 1/2] gnetworkmonitorbase: Use a hash table for storing networks

[Philip Withnall <pwithnall src gnome org>]

commit 4a488ced5d08fb3e28e92b022c407f4669d97029
Author: Philip Withnall <withnall endlessm com>
Date:   Fri Jan 10 12:34:45 2020 +0000

    gnetworkmonitorbase: Use a hash table for storing networks
    
    Rather than using an array, which requires a lot of iteration over it to
    check whether a particular network is present. Using a hash table only
    requires iteration in the can_reach() case, where we need to match a
    mask in the networks array, rather than equal it.
    
    This should improve performance for large numbers of routes.
    
    Signed-off-by: Philip Withnall <withnall endlessm com>
    
    Fixes: #1925

 gio/gnetworkmonitorbase.c | 128 ++++++++++++++++++++++++++++++++--------------
 1 file changed, 89 insertions(+), 39 deletions(-)
---
diff --git a/gio/gnetworkmonitorbase.c b/gio/gnetworkmonitorbase.c
index 6ac37c490..be6ec7277 100644
--- a/gio/gnetworkmonitorbase.c
+++ b/gio/gnetworkmonitorbase.c
@@ -45,7 +45,7 @@ enum
 
 struct _GNetworkMonitorBasePrivate
 {
-  GPtrArray    *networks;
+  GHashTable   *networks  /* (element-type GInetAddressMask) (owned) */;
   gboolean      have_ipv4_default_route;
   gboolean      have_ipv6_default_route;
   gboolean      is_available;
@@ -58,6 +58,9 @@ struct _GNetworkMonitorBasePrivate
 static guint network_changed_signal = 0;
 
 static void queue_network_changed (GNetworkMonitorBase *monitor);
+static guint inet_address_mask_hash (gconstpointer key);
+static gboolean inet_address_mask_equal (gconstpointer a,
+                                         gconstpointer b);
 
 G_DEFINE_TYPE_WITH_CODE (GNetworkMonitorBase, g_network_monitor_base, G_TYPE_OBJECT,
                          G_ADD_PRIVATE (GNetworkMonitorBase)
@@ -75,7 +78,9 @@ static void
 g_network_monitor_base_init (GNetworkMonitorBase *monitor)
 {
   monitor->priv = g_network_monitor_base_get_instance_private (monitor);
-  monitor->priv->networks = g_ptr_array_new_with_free_func (g_object_unref);
+  monitor->priv->networks = g_hash_table_new_full (inet_address_mask_hash,
+                                                   inet_address_mask_equal,
+                                                   g_object_unref, NULL);
   monitor->priv->context = g_main_context_get_thread_default ();
   if (monitor->priv->context)
     g_main_context_ref (monitor->priv->context);
@@ -149,7 +154,7 @@ g_network_monitor_base_finalize (GObject *object)
 {
   GNetworkMonitorBase *monitor = G_NETWORK_MONITOR_BASE (object);
 
-  g_ptr_array_free (monitor->priv->networks, TRUE);
+  g_hash_table_unref (monitor->priv->networks);
   if (monitor->priv->network_changed_source)
     {
       g_source_destroy (monitor->priv->network_changed_source);
@@ -180,15 +185,18 @@ g_network_monitor_base_can_reach_sockaddr (GNetworkMonitorBase *base,
                                            GSocketAddress *sockaddr)
 {
   GInetAddress *iaddr;
-  int i;
+  GHashTableIter iter;
+  gpointer key;
 
   if (!G_IS_INET_SOCKET_ADDRESS (sockaddr))
     return FALSE;
 
   iaddr = g_inet_socket_address_get_address (G_INET_SOCKET_ADDRESS (sockaddr));
-  for (i = 0; i < base->priv->networks->len; i++)
+  g_hash_table_iter_init (&iter, base->priv->networks);
+  while (g_hash_table_iter_next (&iter, &key, NULL))
     {
-      if (g_inet_address_mask_matches (base->priv->networks->pdata[i], iaddr))
+      GInetAddressMask *mask = key;
+      if (g_inet_address_mask_matches (mask, iaddr))
         return TRUE;
     }
 
@@ -205,7 +213,7 @@ g_network_monitor_base_can_reach (GNetworkMonitor      *monitor,
   GSocketAddressEnumerator *enumerator;
   GSocketAddress *addr;
 
-  if (base->priv->networks->len == 0)
+  if (g_hash_table_size (base->priv->networks) == 0)
     {
       g_set_error_literal (error, G_IO_ERROR, G_IO_ERROR_NETWORK_UNREACHABLE,
                            _("Network unreachable"));
@@ -309,7 +317,7 @@ g_network_monitor_base_can_reach_async (GNetworkMonitor     *monitor,
   task = g_task_new (monitor, cancellable, callback, user_data);
   g_task_set_source_tag (task, g_network_monitor_base_can_reach_async);
 
-  if (G_NETWORK_MONITOR_BASE (monitor)->priv->networks->len == 0)
+  if (g_hash_table_size (G_NETWORK_MONITOR_BASE (monitor)->priv->networks) == 0)
     {
       g_task_return_new_error (task, G_IO_ERROR, G_IO_ERROR_NETWORK_UNREACHABLE,
                                _("Network unreachable"));
@@ -361,6 +369,60 @@ g_network_monitor_base_initable_iface_init (GInitableIface *iface)
   iface->init = g_network_monitor_base_initable_init;
 }
 
+static guint
+inet_address_mask_hash (gconstpointer key)
+{
+  GInetAddressMask *mask = G_INET_ADDRESS_MASK (key);
+  guint addr_hash;
+  guint mask_length = g_inet_address_mask_get_length (mask);
+  GInetAddress *addr = g_inet_address_mask_get_address (mask);
+  const guint8 *bytes = g_inet_address_to_bytes (addr);
+  gsize bytes_length = g_inet_address_get_native_size (addr);
+
+  union
+    {
+      const guint8 *bytes;
+      guint32 *hash32;
+      guint64 *hash64;
+    } integerifier;
+
+  /* If we can fit the entire address into the hash key, do it. Don’t worry
+   * about endianness; the address should always be in network endianness. */
+  if (bytes_length == sizeof (guint32))
+    {
+      integerifier.bytes = bytes;
+      addr_hash = *integerifier.hash32;
+    }
+  else if (bytes_length == sizeof (guint64))
+    {
+      integerifier.bytes = bytes;
+      addr_hash = *integerifier.hash64;
+    }
+  else
+    {
+      gsize i;
+
+      /* Otherwise, fall back to adding the bytes together. We do this, rather
+       * than XORing them, as routes often have repeated tuples which would
+       * cancel out under XOR. */
+      addr_hash = 0;
+      for (i = 0; i < bytes_length; i++)
+        addr_hash += bytes[i];
+    }
+
+  return addr_hash + mask_length;;
+}
+
+static gboolean
+inet_address_mask_equal (gconstpointer a,
+                         gconstpointer b)
+{
+  GInetAddressMask *mask_a = G_INET_ADDRESS_MASK (a);
+  GInetAddressMask *mask_b = G_INET_ADDRESS_MASK (b);
+
+  return g_inet_address_mask_equal (mask_a, mask_b);
+}
+
 static gboolean
 emit_network_changed (gpointer user_data)
 {
@@ -424,7 +486,7 @@ queue_network_changed (GNetworkMonitorBase *monitor)
 /**
  * g_network_monitor_base_add_network:
  * @monitor: the #GNetworkMonitorBase
- * @network: a #GInetAddressMask
+ * @network: (transfer none): a #GInetAddressMask
  *
  * Adds @network to @monitor's list of available networks.
  *
@@ -434,15 +496,11 @@ void
 g_network_monitor_base_add_network (GNetworkMonitorBase *monitor,
                                     GInetAddressMask    *network)
 {
-  int i;
+  if (!g_hash_table_add (monitor->priv->networks, network))
+    return;
 
-  for (i = 0; i < monitor->priv->networks->len; i++)
-    {
-      if (g_inet_address_mask_equal (monitor->priv->networks->pdata[i], network))
-        return;
-    }
+  g_object_ref (network);  /* for the element now stored in the hash table */
 
-  g_ptr_array_add (monitor->priv->networks, g_object_ref (network));
   if (g_inet_address_mask_get_length (network) == 0)
     {
       switch (g_inet_address_mask_get_family (network))
@@ -481,33 +539,25 @@ void
 g_network_monitor_base_remove_network (GNetworkMonitorBase *monitor,
                                        GInetAddressMask    *network)
 {
-  int i;
+  if (!g_hash_table_remove (monitor->priv->networks, network))
+    return;
 
-  for (i = 0; i < monitor->priv->networks->len; i++)
+  if (g_inet_address_mask_get_length (network) == 0)
     {
-      if (g_inet_address_mask_equal (monitor->priv->networks->pdata[i], network))
+      switch (g_inet_address_mask_get_family (network))
         {
-          g_ptr_array_remove_index_fast (monitor->priv->networks, i);
-
-          if (g_inet_address_mask_get_length (network) == 0)
-            {
-              switch (g_inet_address_mask_get_family (network))
-                {
-                case G_SOCKET_FAMILY_IPV4:
-                  monitor->priv->have_ipv4_default_route = FALSE;
-                  break;
-                case G_SOCKET_FAMILY_IPV6:
-                  monitor->priv->have_ipv6_default_route = FALSE;
-                  break;
-                default:
-                  break;
-                }
-            }
-
-          queue_network_changed (monitor);
-          return;
+        case G_SOCKET_FAMILY_IPV4:
+          monitor->priv->have_ipv4_default_route = FALSE;
+          break;
+        case G_SOCKET_FAMILY_IPV6:
+          monitor->priv->have_ipv6_default_route = FALSE;
+          break;
+        default:
+          break;
         }
     }
+
+  queue_network_changed (monitor);
 }
 
 /**
@@ -526,7 +576,7 @@ g_network_monitor_base_set_networks (GNetworkMonitorBase  *monitor,
 {
   int i;
 
-  g_ptr_array_set_size (monitor->priv->networks, 0);
+  g_hash_table_remove_all (monitor->priv->networks);
   monitor->priv->have_ipv4_default_route = FALSE;
   monitor->priv->have_ipv6_default_route = FALSE;