[glib] Fix multiple bugs in g_srv_target_list_sort()

[Dan Winship <danw src gnome org>]

commit ce6fbd623115c88cfdf0f5ed36b01cca201ba78e
Author: Dan Winship <danw gnome org>
Date:   Thu May 28 15:27:04 2009 -0400

    Fix multiple bugs in g_srv_target_list_sort()
    
    In particular, targets with weight 0 should be very UNlikely to be
    selected, not very likely, as they were before. However, even ignoring
    that bug in the logic, there was an additional bug (swapping list
    items would cause the 0-weight items to get re-ordered incorrectly
    anyway), and the code contained several fencepost errors.
    
    This patch also adds gio/tests/srvtarget.c, which confirms that for a
    sample list of targets, we now generate all possible correct random
    sortings and no incorrect sortings, and the correct sortings occur in
    roughly the expected proportions (though if the current code is
    still wrong, those proportions may be wrong as well).
    
    http://bugzilla.gnome.org/show_bug.cgi?id=583398
---
 gio/gsrvtarget.c      |   92 +++++++++++++---------------
 gio/tests/Makefile.am |    6 ++-
 gio/tests/srvtarget.c |  157 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 205 insertions(+), 50 deletions(-)

diff --git a/gio/gsrvtarget.c b/gio/gsrvtarget.c
index 4210ea1..526b0dd 100644
--- a/gio/gsrvtarget.c
+++ b/gio/gsrvtarget.c
@@ -229,12 +229,7 @@ compare_target (gconstpointer a, gconstpointer b)
        * that all those with weight 0 are placed at the beginning of
        * the list"
        */
-      if (ta->weight == 0)
-        return -1;
-      else if (tb->weight == 0)
-        return 1;
-      else
-        return g_random_int_range (-1, 1);
+      return ta->weight - tb->weight;
     }
   else
     return ta->priority - tb->priority;
@@ -253,10 +248,9 @@ compare_target (gconstpointer a, gconstpointer b)
 GList *
 g_srv_target_list_sort (GList *targets)
 {
-  gint sum, val, priority, weight;
-  GList *first, *last, *n;
+  gint sum, num, val, priority, weight;
+  GList *t, *out, *tail;
   GSrvTarget *target;
-  gpointer tmp;
 
   if (!targets)
     return NULL;
@@ -275,62 +269,62 @@ g_srv_target_list_sort (GList *targets)
         }
     }
 
-  /* Sort by priority, and partly by weight */
+  /* Sort input list by priority, and put the 0-weight targets first
+   * in each priority group. Initialize output list to %NULL.
+   */
   targets = g_list_sort (targets, compare_target);
+  out = tail = NULL;
 
-  /* For each group of targets with the same priority, rebalance them
-   * according to weight.
+  /* For each group of targets with the same priority, remove them
+   * from @targets and append them to @out in a valid order.
    */
-  for (first = targets; first; first = last->next)
+  while (targets)
     {
-      /* Skip @first to a non-0-weight target. */
-      while (first && ((GSrvTarget *)first->data)->weight == 0)
-        first = first->next;
-      if (!first)
-        break;
-
-      /* Skip @last to the last target of the same priority. */
-      priority = ((GSrvTarget *)first->data)->priority;
-      last = first;
-      while (last->next &&
-             ((GSrvTarget *)last->next->data)->priority == priority)
-        last = last->next;
-
-      /* If there's only one non-0 weight target at this priority,
-       * we can move on to the next priority level.
-       */
-      if (last == first)
-        continue;
-
-      /* Randomly reorder the non-0 weight targets, giving precedence
-       * to the ones with higher weight. RFC 2782 describes this in
-       * terms of assigning a running sum to each target and building
-       * a new list. We do things slightly differently, but should get
-       * the same result.
+      priority = ((GSrvTarget *)targets->data)->priority;
+
+      /* Count the number of targets at this priority level, and
+       * compute the sum of their weights.
        */
-      for (n = first, sum = 0; n != last->next; n = n->next)
-        sum += ((GSrvTarget *)n->data)->weight;
-      while (first != last)
+      sum = num = 0;
+      for (t = targets; t; t = t->next)
+        {
+          target = (GSrvTarget *)t->data;
+          if (target->priority != priority)
+            break;
+          sum += target->weight;
+          num++;
+        }
+
+      /* While there are still targets at this priority level... */
+      while (num)
         {
-          val = g_random_int_range (0, sum);
-          for (n = first; n != last; n = n->next)
+          /* Randomly select from the targets at this priority level,
+           * giving precedence to the ones with higher weight,
+           * according to the rules from RFC 2782.
+           */
+          val = g_random_int_range (0, sum + 1);
+          for (t = targets; ; t = t->next)
             {
-              weight = ((GSrvTarget *)n->data)->weight;
-              if (val < weight)
+              weight = ((GSrvTarget *)t->data)->weight;
+              if (weight >= val)
                 break;
               val -= weight;
             }
 
-          tmp = first->data;
-          first->data = n->data;
-          n->data = tmp;
+          targets = g_list_remove_link (targets, t);
+
+          if (!out)
+            out = t;
+          else
+            tail->next = t;
+          tail = t;
 
           sum -= weight;
-          first = first->next;
+          num--;
         }
     }
 
-  return targets;
+  return out;
 }
 
 #define __G_SRV_TARGET_C__
diff --git a/gio/tests/Makefile.am b/gio/tests/Makefile.am
index 46b9fa6..e49c29e 100644
--- a/gio/tests/Makefile.am
+++ b/gio/tests/Makefile.am
@@ -28,7 +28,8 @@ TEST_PROGS +=	 		\
 	buffered-input-stream	\
 	sleepy-stream		\
 	filter-streams		\
-	simple-async-result
+	simple-async-result	\
+	srvtarget
 
 SAMPLE_PROGS = resolver socket-server socket-client echo-server httpd send-data
 
@@ -106,4 +107,7 @@ send_data_SOURCES	  = send-data.c
 send_data_LDADD		  = $(progs_ldadd) \
 	$(top_builddir)/gthread/libgthread-2.0.la
 
+srvtarget_SOURCES	  = srvtarget.c
+srvtarget_LDADD		  = $(progs_ldadd)
+
 DISTCLEAN_FILES = applications/mimeinfo.cache
diff --git a/gio/tests/srvtarget.c b/gio/tests/srvtarget.c
new file mode 100644
index 0000000..dcbc143
--- /dev/null
+++ b/gio/tests/srvtarget.c
@@ -0,0 +1,157 @@
+/* GLib testing framework examples and tests
+ * Copyright (C) 2009 Red Hat, Inc.
+ *
+ * This work is provided "as is"; redistribution and modification
+ * in whole or in part, in any medium, physical or electronic is
+ * permitted without restriction.
+ *
+ * This work is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * In no event shall the authors or contributors be liable for any
+ * direct, indirect, incidental, special, exemplary, or consequential
+ * damages (including, but not limited to, procurement of substitute
+ * goods or services; loss of use, data, or profits; or business
+ * interruption) however caused and on any theory of liability, whether
+ * in contract, strict liability, or tort (including negligence or
+ * otherwise) arising in any way out of the use of this software, even
+ * if advised of the possibility of such damage.
+ */
+
+#include <glib/glib.h>
+#include <gio/gio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define NUM_TRIALS 250000
+
+struct {
+  const char *order;
+  int expected, seen;
+} ordering[] = {
+  /* There are 32 legitimate orderings; the result always has to start
+   * with either "fe" (usually) or "ef" (rarely). For the remaining
+   * letters, "cbda" is the most likely, with various other orders
+   * possible, down to "adbc" being the most improbable. However,
+   * almost all "fe" orderings are more likely than almost any "ef"
+   * orderings. The complete probability ordering, from most-likely
+   * to least-likely is something roughly like:
+   */
+  { "fecbda", 0.2468 * NUM_TRIALS, 0},
+  { "febcda", 0.1885 * NUM_TRIALS, 0},
+  { "fecdba", 0.1346 * NUM_TRIALS, 0},
+  { "fedcba", 0.0830 * NUM_TRIALS, 0},
+  { "febdca", 0.0706 * NUM_TRIALS, 0},
+  { "fedbca", 0.0571 * NUM_TRIALS, 0},
+  { "fecbad", 0.0496 * NUM_TRIALS, 0},
+  { "febcad", 0.0374 * NUM_TRIALS, 0},
+  { "fecabd", 0.0185 * NUM_TRIALS, 0},
+  { "fecdab", 0.0136 * NUM_TRIALS, 0},
+  { "fecadb", 0.0110 * NUM_TRIALS, 0},
+  { "febacd", 0.0108 * NUM_TRIALS, 0},
+  { "feacbd", 0.0096 * NUM_TRIALS, 0},
+  { "fedcab", 0.0083 * NUM_TRIALS, 0},
+  { "feabcd", 0.0073 * NUM_TRIALS, 0},
+  { "feacdb", 0.0058 * NUM_TRIALS, 0},
+  { "efcbda", 0.0049 * NUM_TRIALS, 0},
+  { "febdac", 0.0048 * NUM_TRIALS, 0},
+  { "febadc", 0.0043 * NUM_TRIALS, 0},
+  { "fedbac", 0.0038 * NUM_TRIALS, 0},
+  { "efbcda", 0.0038 * NUM_TRIALS, 0},
+  { "feadcb", 0.0036 * NUM_TRIALS, 0},
+  { "fedacb", 0.0035 * NUM_TRIALS, 0},
+  { "feabdc", 0.0029 * NUM_TRIALS, 0},
+  { "feadbc", 0.0026 * NUM_TRIALS, 0},
+  { "fedabc", 0.0026 * NUM_TRIALS, 0},
+  { "efcdba", 0.0026 * NUM_TRIALS, 0},
+  { "efdcba", 0.0017 * NUM_TRIALS, 0},
+  { "efbdca", 0.0014 * NUM_TRIALS, 0},
+  { "efdbca", 0.0011 * NUM_TRIALS, 0},
+  { "efcbad", 0.0010 * NUM_TRIALS, 0},
+  { "efbcad", 0.0008 * NUM_TRIALS, 0},
+  { "efcabd", 0.0004 * NUM_TRIALS, 0},
+  { "efcdab", 0.0003 * NUM_TRIALS, 0},
+  { "efcadb", 0.0002 * NUM_TRIALS, 0},
+  { "efbacd", 0.0002 * NUM_TRIALS, 0},
+  { "efacbd", 0.0002 * NUM_TRIALS, 0},
+  { "efdcab", 0.0002 * NUM_TRIALS, 0},
+  { "efabcd", 0.0002 * NUM_TRIALS, 0},
+  { "efacdb", 0.0001 * NUM_TRIALS, 0},
+  { "efbdac", 0.0001 * NUM_TRIALS, 0},
+  { "efadcb", 0.0001 * NUM_TRIALS, 0},
+  { "efdbac", 0.0001 * NUM_TRIALS, 0},
+  { "efbadc", 0.0001 * NUM_TRIALS, 0},
+  { "efdacb", 0.0001 * NUM_TRIALS, 0},
+  { "efabdc", 0.0001 * NUM_TRIALS, 0},
+  { "efadbc", 0.00005 * NUM_TRIALS, 0},
+  { "efdabc", 0.00005 * NUM_TRIALS, 0}
+};
+#define NUM_ORDERINGS G_N_ELEMENTS (ordering)
+
+static void
+test_srv_target_ordering (void)
+{
+  GList *targets, *sorted, *t;
+  char result[7], *p;
+  int i, o;
+
+  targets = NULL;
+  /*                                 name, port, priority, weight */
+  targets = g_list_append (targets, g_srv_target_new ("a", 0, 2, 0));
+  targets = g_list_append (targets, g_srv_target_new ("b", 0, 2, 10));
+  targets = g_list_append (targets, g_srv_target_new ("c", 0, 2, 15));
+  targets = g_list_append (targets, g_srv_target_new ("d", 0, 2, 5));
+  targets = g_list_append (targets, g_srv_target_new ("e", 0, 1, 0));
+  targets = g_list_append (targets, g_srv_target_new ("f", 0, 1, 50));
+
+  for (i = 0; i < NUM_TRIALS; i++)
+    {
+      g_random_set_seed (i);
+
+      sorted = g_srv_target_list_sort (g_list_copy (targets));
+
+      for (t = sorted, p = result; t; t = t->next)
+	*(p++) = *g_srv_target_get_hostname (t->data);
+      *p = '\0';
+      g_list_free (sorted);
+
+      for (o = 0; o < NUM_ORDERINGS; o++)
+	{
+	  if (!strcmp (result, ordering[o].order))
+	    {
+	      ordering[o].seen++;
+	      break;
+	    }
+	}
+
+      /* Assert that @result matched one of the valid orderings */
+      if (o == NUM_ORDERINGS)
+	{
+	  char *msg = g_strdup_printf ("result '%s' is invalid", result);
+	  g_assertion_message (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, msg);
+	}
+    }
+
+  /* Assert that each ordering appeared roughly the expected
+   * number of times.
+   */
+  for (o = 0; o < NUM_ORDERINGS; o++)
+    {
+      g_assert_cmpint (ordering[o].seen, >, ordering[o].expected / 2);
+      g_assert_cmpint (ordering[o].seen, <, ordering[o].expected * 2);
+    }
+
+  g_resolver_free_targets (targets);
+}
+
+int
+main (int argc, char **argv)
+{
+  g_type_init ();
+  g_test_init (&argc, &argv, NULL);
+
+  g_test_add_func ("/srvtarget/srv-target-ordering", test_srv_target_ordering);
+
+  return g_test_run();
+}