list_elem *
list_next (list_elem *elem)
{
- ASSERT (is_interior (elem));
+ ASSERT (is_head (elem) || is_interior (elem));
return elem->next;
}
list_insert (list_end (list), elem);
}
-/* Removes ELEM from its list. Undefined behavior if ELEM is not
- in a list. */
+/* Removes ELEM from its list and returns the element that
+ followed it. Undefined behavior if ELEM is not in a list. */
list_elem *
list_remove (list_elem *elem)
{
ASSERT (is_interior (elem));
elem->prev->next = elem->next;
elem->next->prev = elem->prev;
- return elem;
+ return elem->next;
}
/* Removes the front element from LIST and returns it.
list_elem *
list_pop_front (struct list *list)
{
- ASSERT (list != NULL);
- return list_remove (list_front (list));
+ list_elem *front = list_front (list);
+ list_remove (front);
+ return front;
}
/* Removes the back element from LIST and returns it.
list_elem *
list_pop_back (struct list *list)
{
- ASSERT (list != NULL);
- return list_remove (list_back (list));
+ list_elem *back = list_back (list);
+ list_remove (back);
+ return back;
}
/* Returns the front element in LIST.
return list_begin (list) == list_end (list);
}
+/* Swaps the `list_elem *'s that A and B point to. */
+static void
+swap (list_elem **a, list_elem **b)
+{
+ list_elem *t = *a;
+ *a = *b;
+ *b = t;
+}
+
/* Reverses the order of LIST. */
void
list_reverse (struct list *list)
{
- list_elem te, *e;
-
- /* Swap the prev and next pointers in each element of LIST. */
- for (e = &list->head; e != NULL; e = e->prev)
+ if (!list_empty (list))
{
- list_elem *tep = e->prev;
- e->prev = e->next;
- e->next = tep;
- }
+ list_elem *e;
- /* Swap the head and tail. */
- te = list->head;
- list->head = list->tail;
- list->tail = te;
+ for (e = list_begin (list); e != list_end (list); e = e->prev)
+ swap (&e->prev, &e->next);
+ swap (&list->head.next, &list->tail.prev);
+ swap (&list->head.next->prev, &list->tail.prev->next);
+ }
}
/* Merges lists AL and BL, which must each be sorted according to
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 = list_begin (list);
- last = list_next (middle);
+ 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
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;
+}
projects / pintos-anon / blobdiff