elements allows us to do a little bit of checking on some
operations, which can be valuable.) */
+static bool is_sorted (struct list_elem *a, struct list_elem *b,
+ list_less_func *less, void *aux) UNUSED;
+
/* Returns true if ELEM is a head, false otherwise. */
static inline bool
-is_head (list_elem *elem)
+is_head (struct list_elem *elem)
{
return elem != NULL && elem->prev == NULL && elem->next != NULL;
}
/* Returns true if ELEM is an interior element,
false otherwise. */
static inline bool
-is_interior (list_elem *elem)
+is_interior (struct list_elem *elem)
{
return elem != NULL && elem->prev != NULL && elem->next != NULL;
}
/* Returns true if ELEM is a tail, false otherwise. */
static inline bool
-is_tail (list_elem *elem)
+is_tail (struct list_elem *elem)
{
return elem != NULL && elem->prev != NULL && elem->next == NULL;
}
}
/* Returns the beginning of LIST. */
-list_elem *
+struct list_elem *
list_begin (struct list *list)
{
ASSERT (list != NULL);
/* Returns the element after ELEM in its list. If ELEM is the
last element in its list, returns the list tail. Results are
undefined if ELEM is itself a list tail. */
-list_elem *
-list_next (list_elem *elem)
+struct list_elem *
+list_next (struct list_elem *elem)
{
ASSERT (is_head (elem) || is_interior (elem));
return elem->next;
list_end() is often used in iterating through a list from
front to back. See the big comment at the top of list.h for
an example. */
-list_elem *
+struct list_elem *
list_end (struct list *list)
{
ASSERT (list != NULL);
/* Returns the LIST's reverse beginning, for iterating through
LIST in reverse order, from back to front. */
-list_elem *
+struct list_elem *
list_rbegin (struct list *list)
{
ASSERT (list != NULL);
/* Returns the element before ELEM in its list. If ELEM is the
first element in its list, returns the list head. Results are
undefined if ELEM is itself a list head. */
-list_elem *
-list_prev (list_elem *elem)
+struct list_elem *
+list_prev (struct list_elem *elem)
{
ASSERT (is_interior (elem) || is_tail (elem));
return elem->prev;
...do something with f...
}
*/
-list_elem *
+struct list_elem *
list_rend (struct list *list)
{
ASSERT (list != NULL);
...
}
*/
-list_elem *
+struct list_elem *
list_head (struct list *list)
{
ASSERT (list != NULL);
}
/* Return's LIST's tail. */
-list_elem *
+struct list_elem *
list_tail (struct list *list)
{
ASSERT (list != NULL);
interior element or a tail. The latter case is equivalent to
list_push_back(). */
void
-list_insert (list_elem *before, list_elem *elem)
+list_insert (struct list_elem *before, struct list_elem *elem)
{
ASSERT (is_interior (before) || is_tail (before));
ASSERT (elem != NULL);
current list, then inserts them just before BEFORE, which may
be either an interior element or a tail. */
void
-list_splice (list_elem *before,
- list_elem *first, list_elem *last)
+list_splice (struct list_elem *before,
+ struct list_elem *first, struct list_elem *last)
{
ASSERT (is_interior (before) || is_tail (before));
if (first == last)
/* Inserts ELEM at the beginning of LIST, so that it becomes the
front in LIST. */
void
-list_push_front (struct list *list, list_elem *elem)
+list_push_front (struct list *list, struct list_elem *elem)
{
list_insert (list_begin (list), elem);
}
/* Inserts ELEM at the end of LIST, so that it becomes the
back in LIST. */
void
-list_push_back (struct list *list, list_elem *elem)
+list_push_back (struct list *list, struct list_elem *elem)
{
list_insert (list_end (list), elem);
}
/* 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)
+ followed it. Undefined behavior if ELEM is not in a list.
+
+ It's not safe to treat ELEM as an element in a list after
+ removing it. In particular, using list_next() or list_prev()
+ on ELEM after removal yields undefined behavior. This means
+ that a naive loop to remove the elements in a list will fail:
+
+ ** DON'T DO THIS **
+ for (e = list_begin (&list); e != list_end (&list); e = list_next (e))
+ {
+ ...do something with e...
+ list_remove (e);
+ }
+ ** DON'T DO THIS **
+
+ Here is one correct way to iterate and remove elements from a
+ list:
+
+ for (e = list_begin (&list); e != list_end (&list); e = list_remove (e))
+ {
+ ...do something with e...
+ }
+
+ If you need to free() elements of the list then you need to be
+ more conservative. Here's an alternate strategy that works
+ even in that case:
+
+ while (!list_empty (&list))
+ {
+ struct list_elem *e = list_pop_front (&list);
+ ...do something with e...
+ }
+*/
+struct list_elem *
+list_remove (struct list_elem *elem)
{
ASSERT (is_interior (elem));
elem->prev->next = elem->next;
/* Removes the front element from LIST and returns it.
Undefined behavior if LIST is empty before removal. */
-list_elem *
+struct list_elem *
list_pop_front (struct list *list)
{
- list_elem *front = list_front (list);
+ struct list_elem *front = list_front (list);
list_remove (front);
return front;
}
/* Removes the back element from LIST and returns it.
Undefined behavior if LIST is empty before removal. */
-list_elem *
+struct list_elem *
list_pop_back (struct list *list)
{
- list_elem *back = list_back (list);
+ struct list_elem *back = list_back (list);
list_remove (back);
return back;
}
/* Returns the front element in LIST.
Undefined behavior if LIST is empty. */
-list_elem *
+struct list_elem *
list_front (struct list *list)
{
ASSERT (!list_empty (list));
/* Returns the back element in LIST.
Undefined behavior if LIST is empty. */
-list_elem *
+struct list_elem *
list_back (struct list *list)
{
ASSERT (!list_empty (list));
size_t
list_size (struct list *list)
{
- list_elem *e;
+ struct list_elem *e;
size_t cnt = 0;
for (e = list_begin (list); e != list_end (list); e = list_next (e))
return list_begin (list) == list_end (list);
}
-/* Swaps the `list_elem *'s that A and B point to. */
+/* Swaps the `struct list_elem *'s that A and B point to. */
static void
-swap (list_elem **a, list_elem **b)
+swap (struct list_elem **a, struct list_elem **b)
{
- list_elem *t = *a;
+ struct list_elem *t = *a;
*a = *b;
*b = t;
}
{
if (!list_empty (list))
{
- list_elem *e;
+ struct list_elem *e;
for (e = list_begin (list); e != list_end (list); e = e->prev)
swap (&e->prev, &e->next);
}
}
-/* Merges lists AL and BL, which must each be sorted according to
- LESS given auxiliary data AUX, by inserting each element of BL
- at the proper place in AL to preserve the ordering.
- Runs in O(n) in the combined length of AL and BL. */
-void
-list_merge (struct list *al, struct list *bl,
- list_less_func *less, void *aux)
+/* Returns true only if the list elements A through B (exclusive)
+ are in order according to LESS given auxiliary data AUX. */
+static bool
+is_sorted (struct list_elem *a, struct list_elem *b,
+ list_less_func *less, void *aux)
{
- list_elem *a;
+ if (a != b)
+ while ((a = list_next (a)) != b)
+ if (less (a, list_prev (a), aux))
+ return false;
+ return true;
+}
- ASSERT (al != NULL);
- ASSERT (bl != NULL);
+/* Finds a run, starting at A and ending not after B, of list
+ elements that are in nondecreasing order according to LESS
+ given auxiliary data AUX. Returns the (exclusive) end of the
+ run.
+ A through B (exclusive) must form a non-empty range. */
+static struct list_elem *
+find_end_of_run (struct list_elem *a, struct list_elem *b,
+ list_less_func *less, void *aux)
+{
+ ASSERT (a != NULL);
+ ASSERT (b != NULL);
ASSERT (less != NULL);
-
- a = list_begin (al);
- while (a != list_end (al))
+ ASSERT (a != b);
+
+ do
{
- list_elem *b = list_begin (bl);
- if (less (b, a, aux))
- {
- list_splice (a, b, list_next (b));
- if (list_empty (bl))
- break;
- }
- else
- a = list_next (a);
+ a = list_next (a);
}
- list_splice (list_end (al), list_begin (bl), list_end (bl));
+ while (a != b && !less (a, list_prev (a), aux));
+ return a;
}
-/* 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)
+/* Merges A0 through A1B0 (exclusive) with A1B0 through B1
+ (exclusive) to form a combined range also ending at B1
+ (exclusive). Both input ranges must be nonempty and sorted in
+ nondecreasing order according to LESS given auxiliary data
+ AUX. The output range will be sorted the same way. */
+static void
+inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
+ struct list_elem *b1,
+ list_less_func *less, void *aux)
{
- list_elem *middle, *last;
+ ASSERT (a0 != NULL);
+ ASSERT (a1b0 != NULL);
+ ASSERT (b1 != NULL);
+ ASSERT (less != NULL);
+ ASSERT (is_sorted (a0, a1b0, less, aux));
+ ASSERT (is_sorted (a1b0, b1, less, aux));
- 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;
+ while (a0 != a1b0 && a1b0 != b1)
+ if (!less (a1b0, a0, aux))
+ a0 = list_next (a0);
+ else
+ {
+ a1b0 = list_next (a1b0);
+ list_splice (a0, list_prev (a1b0), a1b0);
+ }
}
-/* Sorts LIST according to LESS given auxiliary data AUX.
- Runs in O(n lg n) time in the number of elements in LIST. */
+/* Sorts LIST according to LESS given auxiliary data AUX, using a
+ natural iterative merge sort that runs in O(n lg n) time and
+ O(1) space in the number of elements in LIST. */
void
-list_sort (struct list *list,
- list_less_func *less, void *aux)
+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
+ size_t output_run_cnt; /* Number of runs output in current pass. */
+
+ ASSERT (list != NULL);
+ ASSERT (less != NULL);
+
+ /* Pass over the list repeatedly, merging adjacent runs of
+ nondecreasing elements, until only one run is left. */
+ do
{
- /* 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. */
+ struct list_elem *a0; /* Start of first run. */
+ struct list_elem *a1b0; /* End of first run, start of second. */
+ struct list_elem *b1; /* End of second run. */
+
+ output_run_cnt = 0;
+ for (a0 = list_begin (list); a0 != list_end (list); a0 = b1)
+ {
+ /* Each iteration produces one output run. */
+ output_run_cnt++;
+
+ /* Locate two adjacent runs of nondecreasing elements
+ A0...A1B0 and A1B0...B1. */
+ a1b0 = find_end_of_run (a0, list_end (list), less, aux);
+ if (a1b0 == list_end (list))
+ break;
+ b1 = find_end_of_run (a1b0, list_end (list), less, aux);
+
+ /* Merge the runs. */
+ inplace_merge (a0, a1b0, b1, less, aux);
+ }
}
+ while (output_run_cnt > 1);
+
+ ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
}
/* Inserts ELEM in the proper position in LIST, which must be
sorted according to LESS given auxiliary data AUX.
Runs in O(n) average case in the number of elements in LIST. */
void
-list_insert_ordered (struct list *list, list_elem *elem,
+list_insert_ordered (struct list *list, struct list_elem *elem,
list_less_func *less, void *aux)
{
- list_elem *e;
+ struct list_elem *e;
ASSERT (list != NULL);
ASSERT (elem != NULL);
list_unique (struct list *list, struct list *duplicates,
list_less_func *less, void *aux)
{
- list_elem *elem, *next;
+ struct list_elem *elem, *next;
ASSERT (list != NULL);
ASSERT (less != NULL);
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 *
+struct list_elem *
list_max (struct list *list, list_less_func *less, void *aux)
{
- list_elem *max = list_begin (list);
+ struct list_elem *max = list_begin (list);
if (max != list_end (list))
{
- list_elem *e;
+ struct list_elem *e;
for (e = list_next (max); e != list_end (list); e = list_next (e))
if (less (max, e, aux))
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 *
+struct list_elem *
list_min (struct list *list, list_less_func *less, void *aux)
{
- list_elem *min = list_begin (list);
+ struct list_elem *min = list_begin (list);
if (min != list_end (list))
{
- list_elem *e;
+ struct list_elem *e;
for (e = list_next (min); e != list_end (list); e = list_next (e))
if (less (e, min, aux))
projects / pintos-anon / blobdiff