projects
/
pintos-anon
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Grading library files.
[pintos-anon]
/
src
/
lib
/
kernel
/
list.c
diff --git
a/src/lib/kernel/list.c
b/src/lib/kernel/list.c
index 3631b2e68da0ddc5292c588bf0acbe34fb1ca996..ba4fae68bfe51919dc30a43007f634c2fa8d0474 100644
(file)
--- a/
src/lib/kernel/list.c
+++ b/
src/lib/kernel/list.c
@@
-78,7
+78,7
@@
list_begin (struct list *list)
list_elem *
list_next (list_elem *elem)
{
list_elem *
list_next (list_elem *elem)
{
- ASSERT (is_interior (elem));
+ ASSERT (is_
head (elem) || is_
interior (elem));
return elem->next;
}
return elem->next;
}
@@
-216,15
+216,15
@@
list_push_back (struct list *list, list_elem *elem)
list_insert (list_end (list), elem);
}
list_insert (list_end (list), elem);
}
-/* Removes ELEM from its list
. Undefined behavior if ELEM is no
t
-
in a list.
*/
+/* Removes ELEM from its list
and returns the element tha
t
+
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;
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.
}
/* Removes the front element from LIST and returns it.
@@
-232,8
+232,9
@@
list_remove (list_elem *elem)
list_elem *
list_pop_front (struct list *list)
{
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.
}
/* Removes the back element from LIST and returns it.
@@
-241,8
+242,9
@@
list_pop_front (struct list *list)
list_elem *
list_pop_back (struct list *list)
{
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.
}
/* Returns the front element in LIST.
@@
-283,24
+285,28
@@
list_empty (struct list *list)
return list_begin (list) == list_end (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)
{
/* 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
}
/* Merges lists AL and BL, which must each be sorted according to
@@
-351,8
+357,7
@@
list_sort (struct list *list,
/* Find middle of LIST. (We're not interested in the end of
the list but it's incidentally needed.) */
/* 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);
while (last != list_end (list) && list_next (last) != list_end (list))
{
middle = list_next (middle);