+/* 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
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);
}
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:
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)
{
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;
/* 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;
unsigned
hash_string (const char *s_)
{
- const unsigned char *s = s_;
+ const unsigned char *s = (const unsigned char *) s_;
unsigned hash;
ASSERT (s != NULL);
\f
/* 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];
/* 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;
}
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);
}
projects / pintos-anon / blobdiff