Add list_min(), list_max().

Refactor list_sort().
Add tests for list_min(), list_max().

diff --git a/src/lib/kernel/list.c b/src/lib/kernel/list.c
index ba4fae68bfe51919dc30a43007f634c2fa8d0474..ee47669fd1213098f352f210538e4592f5261d3f 100644 (file)
--- a/src/lib/kernel/list.c
+++ b/src/lib/kernel/list.c
@@ -339,39 +339,50 @@ list_merge (struct list *al, struct list *bl,
   list_splice (list_end (al), list_begin (bl), list_end (bl));
 }
 
-/* Sorts LIST according to LESS given auxiliary data AUX.
-   Runs in O(n lg n) in the number of elements in LIST. */
-void
-list_sort (struct list *list,
-           list_less_func *less, void *aux)
+/* Returns the middle element in LIST, that is, the N/2'th
+   element (rounding down) in a N-element list.
+   Given an empty list, returns the list tail. */
+static list_elem *
+middle_of_list (struct list *list) 
 {
-  struct list tmp;
   list_elem *middle, *last;
 
-  ASSERT (list != NULL);
-  ASSERT (less != NULL);
-
-  /* Empty and 1-element lists are already sorted. */
-  if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
-    return;
-
-  /* Find middle of LIST.  (We're not interested in the end of
-     the list but it's incidentally needed.) */
   middle = last = list_begin (list);
   while (last != list_end (list) && list_next (last) != list_end (list))
     {
       middle = list_next (middle);
       last = list_next (list_next (last));
     }
+  return middle;
+}
 
-  /* Extract first half of LIST into a temporary list. */
-  list_init (&tmp);
-  list_splice (list_begin (&tmp), list_begin (list), middle);
-
-  /* Sort each half-list and merge the result. */
-  list_sort (&tmp, less, aux);
-  list_sort (list, less, aux);
-  list_merge (list, &tmp, less, aux);
+/* Sorts LIST according to LESS given auxiliary data AUX.
+   Runs in O(n lg n) time in the number of elements in LIST. */
+void
+list_sort (struct list *list,
+           list_less_func *less, void *aux)
+{
+  /* Find the middle of the list. */
+  list_elem *middle = middle_of_list (list);
+  if (middle != list_begin (list))
+    {
+      /* Extract first half of LIST into a temporary list. */
+      struct list tmp;
+      list_init (&tmp);
+      list_splice (list_begin (&tmp), list_begin (list), middle);
+
+      /* Sort each half-list and merge the result. */
+      list_sort (&tmp, less, aux);
+      list_sort (list, less, aux);
+      list_merge (list, &tmp, less, aux);
+    }
+  else 
+    {
+      /* The middle is at the beginning of the list.
+         This only happens in empty lists and 1-element lists.
+         Because such lists are already sorted, we have nothing
+         to do. */
+    }
 }
 
 /* Inserts ELEM in the proper position in LIST, which must be
@@ -419,3 +430,41 @@ list_unique (struct list *list, struct list *duplicates,
     else
       elem = next;
 }
+
+/* Returns the element in LIST with the largest value according
+   to LESS given auxiliary data AUX.  If there is more than one
+   maximum, returns the one that appears earlier in the list.  If
+   the list is empty, returns its tail. */
+list_elem *
+list_max (struct list *list, list_less_func *less, void *aux)
+{
+  list_elem *max = list_begin (list);
+  if (max != list_end (list)) 
+    {
+      list_elem *e;
+      
+      for (e = list_next (max); e != list_end (list); e = list_next (e))
+        if (less (max, e, aux))
+          max = e; 
+    }
+  return max;
+}
+
+/* Returns the element in LIST with the smallest value according
+   to LESS given auxiliary data AUX.  If there is more than one
+   minimum, returns the one that appears earlier in the list.  If
+   the list is empty, returns its tail. */
+list_elem *
+list_min (struct list *list, list_less_func *less, void *aux)
+{
+  list_elem *min = list_begin (list);
+  if (min != list_end (list)) 
+    {
+      list_elem *e;
+      
+      for (e = list_next (min); e != list_end (list); e = list_next (e))
+        if (less (e, min, aux))
+          min = e; 
+    }
+  return min;
+}

diff --git a/src/lib/kernel/list.h b/src/lib/kernel/list.h
index 88ed5952650a033de6d36a84e171eb79dc502f3b..262d5b5c8ef78bb4d3fefe7f808f550591d1ab38 100644 (file)
--- a/src/lib/kernel/list.h
+++ b/src/lib/kernel/list.h
@@ -143,16 +143,16 @@ list_elem *list_back (struct list *);
 size_t list_size (struct list *);
 bool list_empty (struct list *);
 
-/* Weirdness. */
+/* Miscellaneous. */
 void list_reverse (struct list *);
 \f
-/* Operations on lists with ordered elements. */
-
 /* Compares the value of two list elements A and B, given
    auxiliary data AUX.  Returns true if A is less than B, or
    false if A is greater than or equal to B. */
 typedef bool list_less_func (const list_elem *a, const list_elem *b,
                              void *aux);
+
+/* Operations on lists with ordered elements. */
 void list_merge (struct list *, struct list *,
                  list_less_func *, void *aux);
 void list_sort (struct list *,
@@ -162,4 +162,8 @@ void list_insert_ordered (struct list *, list_elem *,
 void list_unique (struct list *, struct list *duplicates,
                   list_less_func *, void *aux);
 
+/* Max and min. */
+list_elem *list_max (struct list *, list_less_func *, void *aux);
+list_elem *list_min (struct list *, list_less_func *, void *aux);
+
 #endif /* lib/kernel/list.h */

diff --git a/src/tests/threads/list.c b/src/tests/threads/list.c
index aac583f8bb2b1fd1403856c0a1270922b1fcffdc..3704af93c68b1c8497b3ff161feef35377bfe09b 100644 (file)
--- a/src/tests/threads/list.c
+++ b/src/tests/threads/list.c
@@ -59,6 +59,14 @@ test (void)
           for (i = 0; i < size; i++)
             list_push_back (&list, &values[i].elem);
 
+          /* Verify correct minimum and maximum elements. */
+          e = list_min (&list, value_less, NULL);
+          ASSERT (size ? list_entry (e, struct value, elem)->value == 0
+                  : e == list_begin (&list));
+          e = list_max (&list, value_less, NULL);
+          ASSERT (size ? list_entry (e, struct value, elem)->value == size - 1
+                  : e == list_begin (&list));
+
           /* Sort and verify list. */
           list_sort (&list, value_less, NULL);
           verify_list_fwd (&list, size);