/* 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
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. */
+ detailed explanation. */
#include <stdbool.h>
#include <stddef.h>
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. */
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
{
/* 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. */
struct hash_elem *hash_insert (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 *);
struct hash_elem *hash_next (struct hash_iterator *);
struct hash_elem *hash_cur (struct hash_iterator *);