From 9b027546c7ee1921aea0024b5a88209992471714 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 31 Dec 2004 22:05:29 +0000 Subject: [PATCH] Add list_min(), list_max(). Refactor list_sort(). Add tests for list_min(), list_max(). --- src/lib/kernel/list.c | 95 ++++++++++++++++++++++++++++++---------- src/lib/kernel/list.h | 10 +++-- src/tests/threads/list.c | 8 ++++ 3 files changed, 87 insertions(+), 26 deletions(-) diff --git a/src/lib/kernel/list.c b/src/lib/kernel/list.c index ba4fae6..ee47669 100644 --- 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 88ed595..262d5b5 100644 --- 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 *); -/* 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 aac583f..3704af9 100644 --- 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); -- 2.30.2