/* 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)
+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);
list_merge (struct list *al, struct list *bl,
list_less_func *less, void *aux)
{
- list_elem *a;
+ struct list_elem *a;
ASSERT (al != NULL);
ASSERT (bl != NULL);
a = list_begin (al);
while (a != list_end (al))
{
- list_elem *b = list_begin (bl);
+ struct list_elem *b = list_begin (bl);
if (less (b, a, aux))
{
list_splice (a, b, list_next (b));
/* 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 *
+static struct list_elem *
middle_of_list (struct list *list)
{
- list_elem *middle, *last;
+ struct list_elem *middle, *last;
middle = last = list_begin (list);
while (last != list_end (list) && list_next (last) != list_end (list))
list_less_func *less, void *aux)
{
/* Find the middle of the list. */
- list_elem *middle = middle_of_list (list);
+ struct list_elem *middle = middle_of_list (list);
if (middle != list_begin (list))
{
/* Extract first half of LIST into a temporary list. */
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