Add hash_apply() function.

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

diff --git a/src/lib/kernel/hash.h b/src/lib/kernel/hash.h
index e37592bfbeae5d32ac2928dcecb8b6470b1f0ad2..7f25c1025769327a88eeee4e202dffa20f28cedd 100644 (file)
--- a/src/lib/kernel/hash.h
+++ b/src/lib/kernel/hash.h
@@ -1,5 +1,5 @@
-#ifndef HEADER_HASH_H
-#define HEADER_HASH_H 1
+#ifndef __LIB_KERNEL_HASH_H
+#define __LIB_KERNEL_HASH_H
 
 /* Hash table.
 
@@ -10,13 +10,15 @@
 
    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.
 
-   
-
-*/
+   The FAQ for the VM project contains a detailed example of how
+   to use the hash table. */
 
 #include <stdbool.h>
 #include <stddef.h>
@@ -24,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
@@ -36,14 +41,19 @@ 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);
 
+/* 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 +70,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 *);
@@ -88,4 +99,4 @@ unsigned hash_bytes (const void *, size_t);
 unsigned hash_string (const char *);
 unsigned hash_int (int);
 
-#endif /* hash.h */
+#endif /* lib/kernel/hash.h */