Make list_entry, hash_entry more type-safe.

[pintos-anon] / src / lib / kernel / hash.h

diff --git a/src/lib/kernel/hash.h b/src/lib/kernel/hash.h
index b7eadd31a57a147b7590efb142383bf2ab612e43..db9f6746431a4aa24f60baf762b2c37fb965275e 100644 (file)
--- a/src/lib/kernel/hash.h
+++ b/src/lib/kernel/hash.h
@@ -3,6 +3,9 @@
 
 /* Hash table.
 
+   This data structure is thoroughly documented in the Tour of
+   Pintos for Project 3.
+
    This is a standard hash table with chaining.  To locate an
    element in the table, we compute a hash function over the
    element's data and use that as an index into an array of
@@ -10,13 +13,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.
-
-   
-
-*/
+   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. */
 
 #include <stdbool.h>
 #include <stddef.h>
@@ -24,26 +26,35 @@
 #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
    name of the outer structure STRUCT and the member name MEMBER
    of the hash element.  See the big comment at the top of the
    file for an example. */
-#define hash_entry(HASH_ELEM, STRUCT, MEMBER)                              \
-        ((STRUCT *) ((uint8_t *) (HASH_ELEM) - offsetof (STRUCT, MEMBER)))
+#define hash_entry(HASH_ELEM, STRUCT, MEMBER)                   \
+        ((STRUCT *) ((uint8_t *) &(HASH_ELEM)->list_elem        \
+                     - offsetof (STRUCT, MEMBER.list_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);
 
+/* Performs some operation on hash element E, given auxiliary
+   data AUX. */
+typedef void hash_action_func (struct hash_elem *e, void *aux);
+
 /* Hash table. */
 struct hash 
   {
@@ -60,24 +71,25 @@ 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. */
 bool hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux);
-void hash_clear (struct hash *);
-void hash_destroy (struct hash *);
+void hash_clear (struct hash *, hash_action_func *);
+void hash_destroy (struct hash *, hash_action_func *);
 
 /* 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_apply (struct hash *, hash_action_func *);
 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 *);