#include "hash.h"
#include "../debug.h"
#include "threads/malloc.h"

Include dependency graph for hash.c:

Macros
#define	list_elem_to_hash_elem(LIST_ELEM) list_entry(LIST_ELEM, struct hash_elem, list_elem)
	Hash table. More...

#define	FNV_32_PRIME 16777619u
	Fowler-Noll-Vo hash constants, for 32-bit word sizes. More...

#define	FNV_32_BASIS 2166136261u

#define	MIN_ELEMS_PER_BUCKET 1
	Element per bucket ratios. More...

#define	BEST_ELEMS_PER_BUCKET 2
	Ideal elems/bucket. More...

#define	MAX_ELEMS_PER_BUCKET 4
	Elems/bucket > 4: increase # of buckets. More...

Functions
static struct list *	find_bucket (struct hash h, struct hash_elem e)
	Returns the bucket in H that E belongs in. More...

static struct hash_elem *	find_elem (struct hash h, struct list bucket, struct hash_elem *e)
	Searches BUCKET in H for a hash element equal to E. More...

static void	insert_elem (struct hash h, struct list bucket, struct hash_elem *e)
	Inserts E into BUCKET (in hash table H). More...

static void	remove_elem (struct hash h, struct hash_elem e)
	Removes E from hash table H. More...

static void	rehash (struct hash *h)
	Changes the number of buckets in hash table H to match the ideal. More...

bool	hash_init (struct hash h, hash_hash_func hash, hash_less_func less, void aux)
	Initializes hash table H to compute hash values using HASH and compare hash elements using LESS, given auxiliary data AUX. More...

void	hash_clear (struct hash h, hash_action_func destructor)
	Removes all the elements from H. More...

void	hash_destroy (struct hash h, hash_action_func destructor)
	Destroys hash table H. More...

struct hash_elem *	hash_insert (struct hash h, struct hash_elem new)
	Inserts NEW into hash table H and returns a null pointer, if no equal element is already in the table. More...

struct hash_elem *	hash_replace (struct hash h, struct hash_elem new)
	Inserts NEW into hash table H, replacing any equal element already in the table, which is returned. More...

struct hash_elem *	hash_find (struct hash h, struct hash_elem e)
	Finds and returns an element equal to E in hash table H, or a null pointer if no equal element exists in the table. More...

struct hash_elem *	hash_delete (struct hash h, struct hash_elem e)
	Finds, removes, and returns an element equal to E in hash table H. More...

void	hash_apply (struct hash h, hash_action_func action)
	Calls ACTION for each element in hash table H in arbitrary order. More...

void	hash_first (struct hash_iterator i, struct hash h)
	Initializes I for iterating hash table H. More...

struct hash_elem *	hash_next (struct hash_iterator *i)
	Advances I to the next element in the hash table and returns it. More...

struct hash_elem *	hash_cur (struct hash_iterator *i)
	Returns the current element in the hash table iteration, or a null pointer at the end of the table. More...

size_t	hash_size (struct hash *h)
	Returns the number of elements in H. More...

bool	hash_empty (struct hash *h)
	Returns true if H contains no elements, false otherwise. More...

unsigned	hash_bytes (const void *buf_, size_t size)
	Returns a hash of the SIZE bytes in BUF. More...

unsigned	hash_string (const char *s_)
	Returns a hash of string S. More...

unsigned	hash_int (int i)
	Returns a hash of integer I. More...

static size_t	turn_off_least_1bit (size_t x)
	Returns X with its lowest-order bit set to 1 turned off. More...

static size_t	is_power_of_2 (size_t x)
	Returns true if X is a power of 2, otherwise false. More...

Macro Definition Documentation

◆ BEST_ELEMS_PER_BUCKET

#define BEST_ELEMS_PER_BUCKET 2

Ideal elems/bucket.

Definition at line 344 of file hash.c.

◆ FNV_32_BASIS

#define FNV_32_BASIS 2166136261u

Definition at line 262 of file hash.c.

◆ FNV_32_PRIME

#define FNV_32_PRIME 16777619u

Fowler-Noll-Vo hash constants, for 32-bit word sizes.

Definition at line 261 of file hash.c.

◆ list_elem_to_hash_elem

#define list_elem_to_hash_elem ( LIST_ELEM ) list_entry(LIST_ELEM, struct hash_elem, list_elem)

Hash table.

This data structure is thoroughly documented in the Tour of Pintos for Project 3.

See hash.h for basic information.

Definition at line 12 of file hash.c.

◆ MAX_ELEMS_PER_BUCKET

#define MAX_ELEMS_PER_BUCKET 4

Elems/bucket > 4: increase # of buckets.

Definition at line 345 of file hash.c.

◆ MIN_ELEMS_PER_BUCKET

#define MIN_ELEMS_PER_BUCKET 1

Element per bucket ratios.

Elems/bucket < 1: reduce # of buckets.

Definition at line 343 of file hash.c.

Function Documentation

◆ find_bucket()

static struct list * find_bucket	(	struct hash *	h,
		struct hash_elem *	e
	)

static

Returns the bucket in H that E belongs in.

Definition at line 306 of file hash.c.

References hash::aux, hash::bucket_cnt, hash::buckets, and hash::hash.

Referenced by hash_delete(), hash_find(), hash_insert(), hash_replace(), and rehash().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_elem()

static struct hash_elem * find_elem	(	struct hash *	h,
		struct list *	bucket,
		struct hash_elem *	e
	)

static

Searches BUCKET in H for a hash element equal to E.

Returns it if found or a null pointer otherwise.

Definition at line 315 of file hash.c.

References hash::aux, hash::less, list_begin(), list_elem_to_hash_elem, list_end(), list_next(), and NULL.

Referenced by hash_delete(), hash_find(), hash_insert(), and hash_replace().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_apply()

void hash_apply	(	struct hash *	h,
		hash_action_func *	action
	)

Calls ACTION for each element in hash table H in arbitrary order.

Iteration.

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.

Definition at line 163 of file hash.c.

References ASSERT, hash::aux, hash::bucket_cnt, hash::buckets, list_begin(), list_elem_to_hash_elem, list_end(), list_next(), next(), and NULL.

Here is the call graph for this function:

◆ hash_bytes()

unsigned hash_bytes	(	const void *	buf_,
		size_t	size
	)

Returns a hash of the SIZE bytes in BUF.

Sample hash functions.

Definition at line 266 of file hash.c.

References ASSERT, buf, FNV_32_BASIS, FNV_32_PRIME, and NULL.

Referenced by hash_int().

Here is the caller graph for this function:

◆ hash_clear()

void hash_clear	(	struct hash *	h,
		hash_action_func *	destructor
	)

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.

Definition at line 54 of file hash.c.

References hash::aux, hash::bucket_cnt, hash::buckets, hash::elem_cnt, list_elem_to_hash_elem, list_empty(), list_init(), list_pop_front(), and NULL.

Referenced by hash_destroy(), and hash_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_cur()

struct hash_elem* hash_cur ( 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().

Definition at line 241 of file hash.c.

References hash_iterator::elem.

◆ hash_delete()

struct hash_elem* hash_delete	(	struct hash *	h,
		struct hash_elem *	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.

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.

Definition at line 145 of file hash.c.

References find_bucket(), find_elem(), NULL, rehash(), and remove_elem().

Here is the call graph for this function:

◆ hash_destroy()

void hash_destroy	(	struct hash *	h,
		hash_action_func *	destructor
	)

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.

Definition at line 87 of file hash.c.

References hash::buckets, free(), hash_clear(), and NULL.

Here is the call graph for this function:

◆ hash_empty()

bool hash_empty ( struct hash * h )

Returns true if H contains no elements, false otherwise.

Definition at line 255 of file hash.c.

References hash::elem_cnt.

◆ hash_find()

struct hash_elem* hash_find	(	struct hash *	h,
		struct hash_elem *	e
	)

Finds and returns an element equal to E in hash table H, or a null pointer if no equal element exists in the table.

Definition at line 132 of file hash.c.

References find_bucket(), and find_elem().

Here is the call graph for this function:

◆ hash_first()

void hash_first	(	struct hash_iterator *	i,
		struct hash *	h
	)

Initializes I for iterating hash table H.

Iteration idiom:

struct hash_iterator i;

hash_first (&i, h); while (hash_next (&i)) { struct foo *f = hash_entry (hash_cur (&i), struct foo, elem); ...do something with f... }

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.

Definition at line 200 of file hash.c.

References ASSERT, hash_iterator::bucket, hash::buckets, hash_iterator::elem, hash_iterator::hash, list_elem_to_hash_elem, list_head(), and NULL.

Here is the call graph for this function:

◆ hash_init()

bool hash_init	(	struct hash *	h,
		hash_hash_func *	hash,
		hash_less_func *	less,
		void *	aux
	)

Initializes hash table H to compute hash values using HASH and compare hash elements using LESS, given auxiliary data AUX.

Basic life cycle.

Definition at line 25 of file hash.c.

References hash::aux, hash::bucket_cnt, hash::buckets, hash::elem_cnt, hash::hash, hash_clear(), hash::less, malloc(), and NULL.

Here is the call graph for this function:

◆ hash_insert()

struct hash_elem* hash_insert	(	struct hash *	h,
		struct hash_elem *	new
	)

Inserts NEW into hash table H and returns a null pointer, if no equal element is already in the table.

Search, insertion, deletion.

If an equal element is already in the table, returns it without inserting NEW.

Definition at line 99 of file hash.c.

References find_bucket(), find_elem(), insert_elem(), NULL, and rehash().

Here is the call graph for this function:

◆ hash_int()

unsigned hash_int ( int i )

Returns a hash of integer I.

lib/kernel/hash.h

Definition at line 299 of file hash.c.

References hash_bytes().

Here is the call graph for this function:

◆ hash_next()

struct hash_elem* hash_next ( struct hash_iterator * i )

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.

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.

Definition at line 219 of file hash.c.

References ASSERT, hash_iterator::bucket, hash::bucket_cnt, hash::buckets, hash_iterator::elem, hash_iterator::hash, list_begin(), hash_elem::list_elem, list_elem_to_hash_elem, list_end(), list_next(), and NULL.