X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flib%2Fkernel%2Fhash.c;h=57eed450c91cc5dbae214445d16b72f52d7a7c3c;hb=4ae5b30e5eb0be98521235060001c2d6d9828345;hp=3c0243b1c39619c247faa3e46bdef7b37618bb0d;hpb=f2f8875638593bd5365cfd6a5ba7c9578e52322f;p=pintos-anon

diff --git a/src/lib/kernel/hash.c b/src/lib/kernel/hash.c
index 3c0243b..57eed45 100644
--- a/src/lib/kernel/hash.c
+++ b/src/lib/kernel/hash.c
@@ -1,11 +1,22 @@
+/* Hash table.
+
+   This data structure is thoroughly documented in the Tour of
+   Pintos for Project 3.
+
+   See hash.h for basic information. */
+
 #include "hash.h"
 #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
@@ -23,28 +34,60 @@ hash_init (struct hash *h,
 
   if (h->buckets != NULL) 
     {
-      hash_clear (h);
+      hash_clear (h, NULL);
       return true;
     }
   else
     return false;
 }
 
-/* Removes all the elements from H. */
+/* Removes all the elements from H.
+   
+   If DESTRUCTOR is non-null, then it is called for each element
+   in the hash.  DESTRUCTOR may, if appropriate, deallocate the
+   memory used by the hash element.  However, modifying hash
+   table H while hash_clear() is running, using any of the
+   functions hash_clear(), hash_destroy(), hash_insert(),
+   hash_replace(), or hash_delete(), yields undefined behavior,
+   whether done in DESTRUCTOR or elsewhere. */
 void
-hash_clear (struct hash *h) 
+hash_clear (struct hash *h, hash_action_func *destructor) 
 {
   size_t i;
-      
-  for (i = 0; i < h->bucket_cnt; h++) 
-    list_init (&h->buckets[i]);
+
+  for (i = 0; i < h->bucket_cnt; i++) 
+    {
+      struct list *bucket = &h->buckets[i];
+
+      if (destructor != NULL) 
+        while (!list_empty (bucket)) 
+          {
+            struct list_elem *list_elem = list_pop_front (bucket);
+            struct hash_elem *hash_elem = list_elem_to_hash_elem (list_elem);
+            destructor (hash_elem, h->aux);
+          }
+
+      list_init (bucket); 
+    }    
+
   h->elem_cnt = 0;
 }
 
-/* Destroys hash table H. */
+/* Destroys hash table H.
+
+   If DESTRUCTOR is non-null, then it is first called for each
+   element in the hash.  DESTRUCTOR may, if appropriate,
+   deallocate the memory used by the hash element.  However,
+   modifying hash table H while hash_clear() is running, using
+   any of the functions hash_clear(), hash_destroy(),
+   hash_insert(), hash_replace(), or hash_delete(), yields
+   undefined behavior, whether done in DESTRUCTOR or
+   elsewhere. */
 void
-hash_destroy (struct hash *h) 
+hash_destroy (struct hash *h, hash_action_func *destructor) 
 {
+  if (destructor != NULL)
+    hash_clear (h, destructor);
   free (h->buckets);
 }
 
@@ -52,52 +95,90 @@ 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);
+
+  rehash (h);
+
   return old; 
 }
 
 /* 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);
-  
   insert_elem (h, bucket, new);
+
+  rehash (h);
+
   return old;
 }
 
 /* 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);
 }
 
 /* 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)
+   in the table.
+
+   If the elements of the hash table are dynamically allocated,
+   or own resources that are, then it is the caller's
+   responsibility to deallocate them. */
+struct hash_elem *
+hash_delete (struct hash *h, struct hash_elem *e)
 {
-  struct list_elem *found = find_elem (h, find_bucket (h, e), e);
-  if (found != NULL)
-    remove_elem (h, found);
+  struct hash_elem *found = find_elem (h, find_bucket (h, e), e);
+  if (found != NULL) 
+    {
+      remove_elem (h, found);
+      rehash (h); 
+    }
   return found;
 }
 
+/* Calls ACTION for each element in hash table H in arbitrary
+   order. 
+   Modifying hash table H while hash_apply() is running, using
+   any of the functions hash_clear(), hash_destroy(),
+   hash_insert(), hash_replace(), or hash_delete(), yields
+   undefined behavior, whether done from ACTION or elsewhere. */
+void
+hash_apply (struct hash *h, hash_action_func *action) 
+{
+  size_t i;
+  
+  ASSERT (action != NULL);
+
+  for (i = 0; i < h->bucket_cnt; i++) 
+    {
+      struct list *bucket = &h->buckets[i];
+      struct list_elem *elem, *next;
+
+      for (elem = list_begin (bucket); elem != list_end (bucket); elem = next) 
+        {
+          next = list_next (elem);
+          action (list_elem_to_hash_elem (elem), h->aux);
+        }
+    }
+}
+
 /* Initializes I for iterating hash table H.
 
    Iteration idiom:
@@ -105,15 +186,16 @@ hash_delete (struct hash *h, hash_elem *e)
       struct hash_iterator i;
 
       hash_first (&i, h);
-      while (hash_next (&i, h))
+      while (hash_next (&i))
         {
-          struct foo *f = list_entry (hash_cur (&i), struct foo, elem);
+          struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
           ...do something with f...
         }
 
-   NOTE: Modifying a hash table during iteration invalidates all
-   iterators.
-*/
+   Modifying hash table H during iteration, using any of the
+   functions hash_clear(), hash_destroy(), hash_insert(),
+   hash_replace(), or hash_delete(), invalidates all
+   iterators. */
 void
 hash_first (struct hash_iterator *i, struct hash *h) 
 {
@@ -122,29 +204,31 @@ 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
    it.  Returns a null pointer if no elements are left.  Elements
    are returned in arbitrary order.
 
-   NOTE: Modifying a hash table during iteration invalidates all
+   Modifying a hash table H during iteration, using any of the
+   functions hash_clear(), hash_destroy(), hash_insert(),
+   hash_replace(), or hash_delete(), 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;
@@ -153,7 +237,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;
@@ -198,7 +282,7 @@ hash_bytes (const void *buf_, size_t size)
 unsigned
 hash_string (const char *s_) 
 {
-  const unsigned char *s = s_;
+  const unsigned char *s = (const unsigned char *) s_;
   unsigned hash;
 
   ASSERT (s != NULL);
@@ -219,7 +303,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];
@@ -227,14 +311,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;
+  for (i = list_begin (bucket); i != list_end (bucket); i = list_next (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;
 }
 
@@ -314,34 +401,30 @@ 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);
         }
     }
+
+  free (old_buckets);
 }
 
-/* Inserts E into BUCKET (in hash table H).
-   Rehashes if this increases elems/bucket above
-   MAX_ELEMS_PER_BUCKET. */
+/* 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++;
-  if (h->elem_cnt > h->bucket_cnt * MAX_ELEMS_PER_BUCKET)
-    rehash (h);
-  list_push_front (bucket, e);
+  list_push_front (bucket, &e->list_elem);
 }
 
-/* Removes E from hash table H.
-   Rehashes if this decreases elems/bucket below
-   MIN_ELEMS_PER_BUCKET. */
+/* 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--;
-  if (h->elem_cnt < h->bucket_cnt * MIN_ELEMS_PER_BUCKET)
-    rehash (h);
-  list_remove (e);
+  list_remove (&e->list_elem);
 }