From 96c122af8890db8f39dfd2ee21df761c6131e8f5 Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@cs.stanford.edu>
Date: Tue, 29 Mar 2005 07:40:25 +0000
Subject: [PATCH] Change list_elem from typedef to struct. Ditto for hash_elem.

---
 doc/tour.texi            |  2 +-
 doc/vm.texi              | 16 +++----
 src/filesys/inode.c      |  4 +-
 src/lib/kernel/hash.c    | 70 +++++++++++++++++--------------
 src/lib/kernel/hash.h    | 35 +++++++++-------
 src/lib/kernel/list.c    | 90 ++++++++++++++++++++--------------------
 src/lib/kernel/list.h    | 74 ++++++++++++++++-----------------
 src/tests/threads/list.c | 14 ++++---
 src/threads/malloc.c     |  2 +-
 src/threads/synch.c      |  2 +-
 src/threads/thread.h     |  2 +-
 11 files changed, 163 insertions(+), 148 deletions(-)

diff --git a/doc/tour.texi b/doc/tour.texi
index d1147dd..4d0ce03 100644
--- a/doc/tour.texi
+++ b/doc/tour.texi
@@ -264,7 +264,7 @@ A thread priority, ranging from the lowest possible priority
 implement priority scheduling in problem 1-3 (@pxref{Problem 1-3
 Priority Scheduling}).
 
-@item list_elem elem;
+@item struct list_elem elem;
 A ``list element'' used to put the thread into doubly linked lists,
 either the list of threads ready to run or a list of threads waiting
 on a semaphore.  Take a look at @file{lib/kernel/list.h} for
diff --git a/doc/vm.texi b/doc/vm.texi
index 37769f9..42bb3ce 100644
--- a/doc/vm.texi
+++ b/doc/vm.texi
@@ -533,12 +533,12 @@ Yes.
 @anchor{Hash Table}
 @b{How do I use the hash table provided in @file{lib/kernel/hash.c}?}
 
-First, you need to embed a @code{hash_elem} object as a member of the
-object that the hash table will contain.  Each @code{hash_elem} allows
+First, you need to embed a @struct{hash_elem} as a member of the
+object that the hash table will contain.  Each @struct{hash_elem} allows
 the object to a member of at most one hash table at a given time.  All
 the hash table functions that deal with hash table items actually use
-the address of a @code{hash_elem}.  You can convert a pointer to a
-@code{hash_elem} member into a pointer to the structure in which
+the address of a @struct{hash_elem}.  You can convert a pointer to a
+@struct{hash_elem} member into a pointer to the structure in which
 member is embedded using the @code{hash_entry} macro.
 
 Second, you need to decide on a key type.  The key should be something
@@ -553,11 +553,11 @@ to be compatible with the prototypes for @code{hash_hash_func} and
 @code{hash_less_func} in @file{lib/kernel/hash.h}.
 
 Here's a quick example.  Suppose you want to put @struct{thread}s
-in a hash table.  First, add a @code{hash_elem} to the thread
+in a hash table.  First, add a @struct{hash_elem} to the thread
 structure by adding a line to its definition:
 
 @example
-hash_elem h_elem;               /* Hash table element. */
+struct hash_elem h_elem;                /* Hash table element. */
 @end example
 
 We'll choose the @code{tid} member in @struct{thread} as the key,
@@ -566,7 +566,7 @@ and write a hash function and a comparison function:
 @example
 /* Returns a hash for E. */
 unsigned
-thread_hash (const hash_elem *e, void *aux UNUSED)
+thread_hash (const struct hash_elem *e, void *aux UNUSED)
 @{
   struct thread *t = hash_entry (e, struct thread, h_elem);
   return hash_int (t->tid);
@@ -574,7 +574,7 @@ thread_hash (const hash_elem *e, void *aux UNUSED)
 
 /* Returns true if A's tid is less than B's tid. */
 bool
-thread_less (const hash_elem *a_, const hash_elem *b_, 
+thread_less (const struct hash_elem *a_, const struct hash_elem *b_, 
              void *aux UNUSED)
 @{
   struct thread *a = hash_entry (a_, struct thread, h_elem);
diff --git a/src/filesys/inode.c b/src/filesys/inode.c
index be1df57..749af37 100644
--- a/src/filesys/inode.c
+++ b/src/filesys/inode.c
@@ -27,7 +27,7 @@ bytes_to_sectors (off_t size)
 /* In-memory inode. */
 struct inode 
   {
-    list_elem elem;                     /* Element in inode list. */
+    struct list_elem elem;              /* Element in inode list. */
     disk_sector_t sector;               /* Sector number of disk location. */
     int open_cnt;                       /* Number of openers. */
     bool removed;                       /* True if deleted, false otherwise. */
@@ -91,7 +91,7 @@ inode_create (struct bitmap *free_map, disk_sector_t sector, off_t length)
 struct inode *
 inode_open (disk_sector_t sector) 
 {
-  list_elem *e;
+  struct list_elem *e;
   struct inode *idx;
 
   /* Check whether this inode is already open.
diff --git a/src/lib/kernel/hash.c b/src/lib/kernel/hash.c
index 155f097..93813c0 100644
--- a/src/lib/kernel/hash.c
+++ b/src/lib/kernel/hash.c
@@ -2,10 +2,14 @@
 #include "../debug.h"
 #include "threads/malloc.h"
 
-static struct list *find_bucket (struct hash *, hash_elem *);
-static struct list_elem *find_elem (struct hash *, struct list *, hash_elem *);
-static void insert_elem (struct hash *, struct list *, hash_elem *);
-static void remove_elem (struct hash *, hash_elem *);
+#define list_elem_to_hash_elem(LIST_ELEM)                       \
+        list_entry(LIST_ELEM, struct hash_elem, list_elem)
+
+static struct list *find_bucket (struct hash *, struct hash_elem *);
+static struct hash_elem *find_elem (struct hash *, struct list *,
+                                    struct hash_elem *);
+static void insert_elem (struct hash *, struct list *, struct hash_elem *);
+static void remove_elem (struct hash *, struct hash_elem *);
 static void rehash (struct hash *);
 
 /* Initializes hash table H to compute hash values using HASH and
@@ -52,11 +56,11 @@ hash_destroy (struct hash *h)
    no equal element is already in the table.
    If an equal element is already in the table, returns it
    without inserting NEW. */   
-hash_elem *
-hash_insert (struct hash *h, hash_elem *new)
+struct hash_elem *
+hash_insert (struct hash *h, struct hash_elem *new)
 {
   struct list *bucket = find_bucket (h, new);
-  struct list_elem *old = find_elem (h, bucket, new);
+  struct hash_elem *old = find_elem (h, bucket, new);
 
   if (old == NULL) 
     insert_elem (h, bucket, new);
@@ -68,11 +72,11 @@ hash_insert (struct hash *h, hash_elem *new)
 
 /* Inserts NEW into hash table H, replacing any equal element
    already in the table, which is returned. */
-hash_elem *
-hash_replace (struct hash *h, hash_elem *new) 
+struct hash_elem *
+hash_replace (struct hash *h, struct hash_elem *new) 
 {
   struct list *bucket = find_bucket (h, new);
-  struct list_elem *old = find_elem (h, bucket, new);
+  struct hash_elem *old = find_elem (h, bucket, new);
 
   if (old != NULL)
     remove_elem (h, old);
@@ -85,8 +89,8 @@ hash_replace (struct hash *h, hash_elem *new)
 
 /* Finds and returns an element equal to E in hash table H, or a
    null pointer if no equal element exists in the table. */
-hash_elem *
-hash_find (struct hash *h, hash_elem *e) 
+struct hash_elem *
+hash_find (struct hash *h, struct hash_elem *e) 
 {
   return find_elem (h, find_bucket (h, e), e);
 }
@@ -94,10 +98,10 @@ hash_find (struct hash *h, hash_elem *e)
 /* Finds, removes, and returns an element equal to E in hash
    table H.  Returns a null pointer if no equal element existed
    in the table. */
-hash_elem *
-hash_delete (struct hash *h, hash_elem *e)
+struct hash_elem *
+hash_delete (struct hash *h, struct hash_elem *e)
 {
-  struct list_elem *found = find_elem (h, find_bucket (h, e), e);
+  struct hash_elem *found = find_elem (h, find_bucket (h, e), e);
   if (found != NULL) 
     {
       remove_elem (h, found);
@@ -130,7 +134,7 @@ hash_first (struct hash_iterator *i, struct hash *h)
 
   i->hash = h;
   i->bucket = i->hash->buckets;
-  i->elem = list_head (i->bucket);
+  i->elem = list_elem_to_hash_elem (list_head (i->bucket));
 }
 
 /* Advances I to the next element in the hash table and returns
@@ -139,20 +143,20 @@ hash_first (struct hash_iterator *i, struct hash *h)
 
    NOTE: Modifying a hash table during iteration invalidates all
    iterators. */
-hash_elem *
+struct hash_elem *
 hash_next (struct hash_iterator *i)
 {
   ASSERT (i != NULL);
 
-  i->elem = list_next (i->elem);
-  while (i->elem == list_end (i->bucket)) 
+  i->elem = list_elem_to_hash_elem (list_next (&i->elem->list_elem));
+  while (i->elem == list_elem_to_hash_elem (list_end (i->bucket)))
     {
       if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
         {
           i->elem = NULL;
           break;
         }
-      i->elem = list_begin (i->bucket);
+      i->elem = list_elem_to_hash_elem (list_begin (i->bucket));
     }
   
   return i->elem;
@@ -161,7 +165,7 @@ hash_next (struct hash_iterator *i)
 /* Returns the current element in the hash table iteration, or a
    null pointer at the end of the table.  Undefined behavior
    after calling hash_first() but before hash_next(). */
-hash_elem *
+struct hash_elem *
 hash_cur (struct hash_iterator *i) 
 {
   return i->elem;
@@ -227,7 +231,7 @@ hash_int (int i)
 
 /* Returns the bucket in H that E belongs in. */
 static struct list *
-find_bucket (struct hash *h, hash_elem *e) 
+find_bucket (struct hash *h, struct hash_elem *e) 
 {
   size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
   return &h->buckets[bucket_idx];
@@ -235,14 +239,17 @@ find_bucket (struct hash *h, hash_elem *e)
 
 /* Searches BUCKET in H for a hash element equal to E.  Returns
    it if found or a null pointer otherwise. */
-static struct list_elem *
-find_elem (struct hash *h, struct list *bucket, hash_elem *e) 
+static struct hash_elem *
+find_elem (struct hash *h, struct list *bucket, struct hash_elem *e) 
 {
   struct list_elem *i;
 
   for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i)) 
-    if (!h->less (i, e, h->aux) && !h->less (e, i, h->aux))
-      return i; 
+    {
+      struct hash_elem *hi = list_elem_to_hash_elem (i);
+      if (!h->less (hi, e, h->aux) && !h->less (e, hi, h->aux))
+        return hi; 
+    }
   return NULL;
 }
 
@@ -322,7 +329,8 @@ rehash (struct hash *h)
       for (elem = list_begin (old_bucket);
            elem != list_end (old_bucket); elem = next) 
         {
-          struct list *new_bucket = find_bucket (h, elem);
+          struct list *new_bucket
+            = find_bucket (h, list_elem_to_hash_elem (elem));
           next = list_next (elem);
           list_remove (elem);
           list_push_front (new_bucket, elem);
@@ -334,17 +342,17 @@ rehash (struct hash *h)
 
 /* Inserts E into BUCKET (in hash table H). */
 static void
-insert_elem (struct hash *h, struct list *bucket, hash_elem *e) 
+insert_elem (struct hash *h, struct list *bucket, struct hash_elem *e) 
 {
   h->elem_cnt++;
-  list_push_front (bucket, e);
+  list_push_front (bucket, &e->list_elem);
 }
 
 /* Removes E from hash table H. */
 static void
-remove_elem (struct hash *h, hash_elem *e) 
+remove_elem (struct hash *h, struct hash_elem *e) 
 {
   h->elem_cnt--;
-  list_remove (e);
+  list_remove (&e->list_elem);
 }
 
diff --git a/src/lib/kernel/hash.h b/src/lib/kernel/hash.h
index 0dd0c3d..b642338 100644
--- a/src/lib/kernel/hash.h
+++ b/src/lib/kernel/hash.h
@@ -10,11 +10,12 @@
 
    The chain lists do not use dynamic allocation.  Instead, each
    structure that can potentially be in a hash must embed a
-   hash_elem member.  All of the hash functions operate on these
-   `hash_elem's.  The hash_entry macro allows conversion from a
-   hash_elem back to a structure object that contains it.  This
-   is the same technique used in the linked list implementation.
-   Refer to lib/kernel/list.h for a detailed explanation.
+   struct hash_elem member.  All of the hash functions operate on
+   these `struct hash_elem's.  The hash_entry macro allows
+   conversion from a struct hash_elem back to a structure object
+   that contains it.  This is the same technique used in the
+   linked list implementation.  Refer to lib/kernel/list.h for a
+   detailed explanation.
 
    The FAQ for the VM project contains a detailed example of how
    to use the hash table. */
@@ -25,7 +26,10 @@
 #include "list.h"
 
 /* Hash element. */
-typedef list_elem hash_elem;
+struct hash_elem 
+  {
+    struct list_elem list_elem;
+  };
 
 /* Converts pointer to hash element HASH_ELEM into a pointer to
    the structure that HASH_ELEM is embedded inside.  Supply the
@@ -37,12 +41,13 @@ typedef list_elem hash_elem;
 
 /* Computes and returns the hash value for hash element E, given
    auxiliary data AUX. */
-typedef unsigned hash_hash_func (const hash_elem *e, void *aux);
+typedef unsigned hash_hash_func (const struct hash_elem *e, void *aux);
 
 /* Compares the value of two hash 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 hash_less_func (const hash_elem *a, const hash_elem *b,
+typedef bool hash_less_func (const struct hash_elem *a,
+                             const struct hash_elem *b,
                              void *aux);
 
 /* Hash table. */
@@ -61,7 +66,7 @@ struct hash_iterator
   {
     struct hash *hash;          /* The hash table. */
     struct list *bucket;        /* Current bucket. */
-    hash_elem *elem;            /* Current hash element in current bucket. */
+    struct hash_elem *elem;     /* Current hash element in current bucket. */
   };
 
 /* Basic life cycle. */
@@ -70,15 +75,15 @@ void hash_clear (struct hash *);
 void hash_destroy (struct hash *);
 
 /* Search, insertion, deletion. */
-hash_elem *hash_insert (struct hash *, hash_elem *);
-hash_elem *hash_replace (struct hash *, hash_elem *);
-hash_elem *hash_find (struct hash *, hash_elem *);
-hash_elem *hash_delete (struct hash *, hash_elem *);
+struct hash_elem *hash_insert (struct hash *, struct hash_elem *);
+struct hash_elem *hash_replace (struct hash *, struct hash_elem *);
+struct hash_elem *hash_find (struct hash *, struct hash_elem *);
+struct hash_elem *hash_delete (struct hash *, struct hash_elem *);
 
 /* Iteration. */
 void hash_first (struct hash_iterator *, struct hash *);
-hash_elem *hash_next (struct hash_iterator *);
-hash_elem *hash_cur (struct hash_iterator *);
+struct hash_elem *hash_next (struct hash_iterator *);
+struct hash_elem *hash_cur (struct hash_iterator *);
 
 /* Information. */
 size_t hash_size (struct hash *);
diff --git a/src/lib/kernel/list.c b/src/lib/kernel/list.c
index ee47669..d9eaa95 100644
--- a/src/lib/kernel/list.c
+++ b/src/lib/kernel/list.c
@@ -33,7 +33,7 @@
 
 /* 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;
 }
@@ -41,14 +41,14 @@ is_head (list_elem *elem)
 /* 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;
 }
@@ -65,7 +65,7 @@ list_init (struct list *list)
 }
 
 /* Returns the beginning of LIST.  */
-list_elem *
+struct list_elem *
 list_begin (struct list *list)
 {
   ASSERT (list != NULL);
@@ -75,8 +75,8 @@ list_begin (struct list *list)
 /* 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;
@@ -87,7 +87,7 @@ list_next (list_elem *elem)
    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);
@@ -96,7 +96,7 @@ list_end (struct list *list)
 
 /* 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);
@@ -106,8 +106,8 @@ list_rbegin (struct list *list)
 /* 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;
@@ -126,7 +126,7 @@ list_prev (list_elem *elem)
           ...do something with f...
         }
 */
-list_elem *
+struct list_elem *
 list_rend (struct list *list) 
 {
   ASSERT (list != NULL);
@@ -144,7 +144,7 @@ list_rend (struct list *list)
           ...
         }
 */
-list_elem *
+struct list_elem *
 list_head (struct list *list) 
 {
   ASSERT (list != NULL);
@@ -152,7 +152,7 @@ list_head (struct list *list)
 }
 
 /* Return's LIST's tail. */
-list_elem *
+struct list_elem *
 list_tail (struct list *list) 
 {
   ASSERT (list != NULL);
@@ -163,7 +163,7 @@ list_tail (struct list *list)
    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);
@@ -178,8 +178,8 @@ list_insert (list_elem *before, list_elem *elem)
    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)
@@ -203,7 +203,7 @@ list_splice (list_elem *before,
 /* 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);
 }
@@ -211,15 +211,15 @@ list_push_front (struct list *list, list_elem *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;
@@ -229,27 +229,27 @@ list_remove (list_elem *elem)
 
 /* 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));
@@ -258,7 +258,7 @@ list_front (struct list *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));
@@ -270,7 +270,7 @@ list_back (struct list *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))
@@ -285,11 +285,11 @@ list_empty (struct list *list)
   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;
 }
@@ -300,7 +300,7 @@ list_reverse (struct list *list)
 {
   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);
@@ -317,7 +317,7 @@ void
 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);
@@ -326,7 +326,7 @@ list_merge (struct list *al, struct list *bl,
   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));
@@ -342,10 +342,10 @@ list_merge (struct list *al, struct list *bl,
 /* 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))
@@ -363,7 +363,7 @@ list_sort (struct list *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. */
@@ -389,10 +389,10 @@ list_sort (struct list *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);
@@ -412,7 +412,7 @@ void
 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);
@@ -435,13 +435,13 @@ list_unique (struct list *list, struct list *duplicates,
    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))
@@ -454,13 +454,13 @@ list_max (struct list *list, list_less_func *less, void *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))
diff --git a/src/lib/kernel/list.h b/src/lib/kernel/list.h
index 262d5b5..e71c1ca 100644
--- a/src/lib/kernel/list.h
+++ b/src/lib/kernel/list.h
@@ -5,18 +5,18 @@
 
    This implementation of a doubly linked list does not require
    use of dynamically allocated memory.  Instead, each structure
-   that is a potential list element must embed a list_elem
-   member.  All of the list functions operate on these
-   `list_elem's.  The list_entry macro allows conversion from a
-   list_elem back to a structure object that contains it.
+   that is a potential list element must embed a struct list_elem
+   member.  All of the list functions operate on these `struct
+   list_elem's.  The list_entry macro allows conversion from a
+   struct list_elem back to a structure object that contains it.
 
    For example, suppose there is a needed for a list of `struct
-   foo'.  `struct foo' should contain a `list_elem' member, like
-   so:
+   foo'.  `struct foo' should contain a `struct list_elem'
+   member, like so:
 
       struct foo
         {
-          list_elem elem;
+          struct list_elem elem;
           int bar;
           ...other members...
         };
@@ -29,10 +29,10 @@
       list_init (&foo_list);
 
    Iteration is a typical situation where it is necessary to
-   convert from a list_elem back to its enclosing structure.
-   Here's an example using foo_list:
+   convert from a struct list_elem back to its enclosing
+   structure.  Here's an example using foo_list:
 
-      list_elem *e;
+      struct list_elem *e;
 
       for (e = list_begin (&foo_list); e != list_end (&foo_list);
            e = list_next (e))
@@ -87,18 +87,17 @@
 #include <stdint.h>
 
 /* List element. */
-typedef struct list_elem 
+struct list_elem 
   {
     struct list_elem *prev;     /* Previous list element. */
     struct list_elem *next;     /* Next list element. */
-  }
-list_elem;
+  };
 
 /* List. */
 struct list 
   {
-    list_elem head;             /* List head. */
-    list_elem tail;             /* List tail. */
+    struct list_elem head;      /* List head. */
+    struct list_elem tail;      /* List tail. */
   };
 
 /* Converts pointer to list element LIST_ELEM into a pointer to
@@ -112,32 +111,32 @@ struct list
 void list_init (struct list *);
 
 /* List traversal. */
-list_elem *list_begin (struct list *);
-list_elem *list_next (list_elem *);
-list_elem *list_end (struct list *);
+struct list_elem *list_begin (struct list *);
+struct list_elem *list_next (struct list_elem *);
+struct list_elem *list_end (struct list *);
 
-list_elem *list_rbegin (struct list *);
-list_elem *list_prev (list_elem *);
-list_elem *list_rend (struct list *);
+struct list_elem *list_rbegin (struct list *);
+struct list_elem *list_prev (struct list_elem *);
+struct list_elem *list_rend (struct list *);
 
-list_elem *list_head (struct list *);
-list_elem *list_tail (struct list *);
+struct list_elem *list_head (struct list *);
+struct list_elem *list_tail (struct list *);
 
 /* List insertion. */
-void list_insert (list_elem *, list_elem *);
-void list_splice (list_elem *before,
-                  list_elem *first, list_elem *last);
-void list_push_front (struct list *, list_elem *);
-void list_push_back (struct list *, list_elem *);
+void list_insert (struct list_elem *, struct list_elem *);
+void list_splice (struct list_elem *before,
+                  struct list_elem *first, struct list_elem *last);
+void list_push_front (struct list *, struct list_elem *);
+void list_push_back (struct list *, struct list_elem *);
 
 /* List removal. */
-list_elem *list_remove (list_elem *);
-list_elem *list_pop_front (struct list *);
-list_elem *list_pop_back (struct list *);
+struct list_elem *list_remove (struct list_elem *);
+struct list_elem *list_pop_front (struct list *);
+struct list_elem *list_pop_back (struct list *);
 
 /* List elements. */
-list_elem *list_front (struct list *);
-list_elem *list_back (struct list *);
+struct list_elem *list_front (struct list *);
+struct list_elem *list_back (struct list *);
 
 /* List properties. */
 size_t list_size (struct list *);
@@ -149,7 +148,8 @@ void list_reverse (struct list *);
 /* 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,
+typedef bool list_less_func (const struct list_elem *a,
+                             const struct list_elem *b,
                              void *aux);
 
 /* Operations on lists with ordered elements. */
@@ -157,13 +157,13 @@ void list_merge (struct list *, struct list *,
                  list_less_func *, void *aux);
 void list_sort (struct list *,
                 list_less_func *, void *aux);
-void list_insert_ordered (struct list *, list_elem *,
+void list_insert_ordered (struct list *, struct list_elem *,
                           list_less_func *, void *aux);
 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);
+struct list_elem *list_max (struct list *, list_less_func *, void *aux);
+struct 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 2300bc3..836c69e 100644
--- a/src/tests/threads/list.c
+++ b/src/tests/threads/list.c
@@ -21,12 +21,13 @@
 /* A linked list element. */
 struct value 
   {
-    list_elem elem;             /* List element. */
+    struct list_elem elem;      /* List element. */
     int value;                  /* Item value. */
   };
 
 static void shuffle (struct value[], size_t);
-static bool value_less (const list_elem *, const list_elem *, void *);
+static bool value_less (const struct list_elem *, const struct list_elem *,
+                        void *);
 static void verify_list_fwd (struct list *, int size);
 static void verify_list_bkwd (struct list *, int size);
 
@@ -46,7 +47,7 @@ test (void)
         {
           static struct value values[MAX_SIZE * 4];
           struct list list;
-          list_elem *e;
+          struct list_elem *e;
           int i, ofs;
 
           /* Put values 0...SIZE in random order in VALUES. */
@@ -125,7 +126,8 @@ shuffle (struct value *array, size_t cnt)
 /* Returns true if value A is less than value B, false
    otherwise. */
 static bool
-value_less (const list_elem *a_, const list_elem *b_, void *aux UNUSED) 
+value_less (const struct list_elem *a_, const struct list_elem *b_,
+            void *aux UNUSED) 
 {
   const struct value *a = list_entry (a_, struct value, elem);
   const struct value *b = list_entry (b_, struct value, elem);
@@ -138,7 +140,7 @@ value_less (const list_elem *a_, const list_elem *b_, void *aux UNUSED)
 static void
 verify_list_fwd (struct list *list, int size) 
 {
-  list_elem *e;
+  struct list_elem *e;
   int i;
   
   for (i = 0, e = list_begin (list);
@@ -157,7 +159,7 @@ verify_list_fwd (struct list *list, int size)
 static void
 verify_list_bkwd (struct list *list, int size) 
 {
-  list_elem *e;
+  struct list_elem *e;
   int i;
 
   for (i = 0, e = list_rbegin (list);
diff --git a/src/threads/malloc.c b/src/threads/malloc.c
index 8e6b459..f74d439 100644
--- a/src/threads/malloc.c
+++ b/src/threads/malloc.c
@@ -57,7 +57,7 @@ struct arena
 /* Free block. */
 struct block 
   {
-    list_elem free_elem;        /* Free list element. */
+    struct list_elem free_elem; /* Free list element. */
   };
 
 /* Our set of descriptors. */
diff --git a/src/threads/synch.c b/src/threads/synch.c
index 10a7dad..1504d98 100644
--- a/src/threads/synch.c
+++ b/src/threads/synch.c
@@ -231,7 +231,7 @@ lock_name (const struct lock *lock)
 /* One semaphore in a list. */
 struct semaphore_elem 
   {
-    list_elem elem;                     /* List element. */
+    struct list_elem elem;              /* List element. */
     struct semaphore semaphore;         /* This semaphore. */
   };
 
diff --git a/src/threads/thread.h b/src/threads/thread.h
index af1f16d..fe7db89 100644
--- a/src/threads/thread.h
+++ b/src/threads/thread.h
@@ -90,7 +90,7 @@ struct thread
     int priority;                       /* Priority. */
 
     /* Shared between thread.c and synch.c. */
-    list_elem elem;                     /* List element. */
+    struct list_elem elem;              /* List element. */
 
 #ifdef USERPROG
     /* Owned by userprog/process.c. */
-- 
2.30.2