From 96c122af8890db8f39dfd2ee21df761c6131e8f5 Mon Sep 17 00:00:00 2001 From: Ben Pfaff 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 /* 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