hash.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include "list.h"

Include dependency graph for hash.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	hash_elem
	Hash table. More...
struct	hash
	Hash table. More...
struct	hash_iterator
	A hash table iterator. More...

Macros
#define	hash_entry(HASH_ELEM, STRUCT, MEMBER)
	Converts pointer to hash element HASH_ELEM into a pointer to the structure that HASH_ELEM is embedded inside. More...

Typedefs
typedef unsigned	hash_hash_func(const struct hash_elem *e, void *aux)
	Computes and returns the hash value for hash element E, given auxiliary data AUX. More...
typedef bool	hash_less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux)
	Compares the value of two hash elements A and B, given auxiliary data AUX. More...
typedef void	hash_action_func(struct hash_elem *e, void *aux)
	Performs some operation on hash element E, given auxiliary data AUX. More...

Functions
bool	hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux)
	Basic life cycle. More...
void	hash_clear (struct hash *, hash_action_func *)
	Removes all the elements from H. More...
void	hash_destroy (struct hash *, hash_action_func *)
	Destroys hash table H. More...
struct hash_elem *	hash_insert (struct hash *, struct hash_elem *)
	Search, insertion, deletion. More...
struct hash_elem *	hash_replace (struct hash *, struct hash_elem *)
	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 *, struct hash_elem *)
	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 *, struct hash_elem *)
	Finds, removes, and returns an element equal to E in hash table H. More...
void	hash_apply (struct hash *, hash_action_func *)
	Iteration. More...
void	hash_first (struct hash_iterator *, struct hash *)
	Initializes I for iterating hash table H. More...
struct hash_elem *	hash_next (struct hash_iterator *)
	Advances I to the next element in the hash table and returns it. More...
struct hash_elem *	hash_cur (struct hash_iterator *)
	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 *)
	Information. More...
bool	hash_empty (struct hash *)
	Returns true if H contains no elements, false otherwise. More...
unsigned	hash_bytes (const void *, size_t)
	Sample hash functions. More...
unsigned	hash_string (const char *)
	Returns a hash of string S. More...
unsigned	hash_int (int)
	lib/kernel/hash.h More...

Macro Definition Documentation

hash_entry

#define hash_entry	(		HASH_ELEM,
			STRUCT,
			MEMBER
	)

Value:

((STRUCT *) ((uint8_t *) &(HASH_ELEM)->list_elem        \
                     - offsetof (STRUCT, MEMBER.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.

Definition at line 39 of file hash.h.

Typedef Documentation

hash_action_func

typedef void hash_action_func(struct hash_elem *e, void *aux)

Performs some operation on hash element E, given auxiliary data AUX.

Definition at line 56 of file hash.h.

hash_hash_func

typedef unsigned hash_hash_func(const struct hash_elem *e, void *aux)

Computes and returns the hash value for hash element E, given auxiliary data AUX.

Definition at line 45 of file hash.h.

hash_less_func

typedef bool hash_less_func(const struct hash_elem *a, const struct hash_elem *b, 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.

Definition at line 50 of file hash.h.

Function Documentation

hash_apply()

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

Iteration.

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
	)

Sample hash functions.

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 *

)

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 *	,
		struct hash_elem *
	)

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
	)

Basic life cycle.

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
	)

Search, insertion, deletion.

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

)

lib/kernel/hash.h

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.

Here is the call graph for this function:

hash_replace()

struct hash_elem* hash_replace	(	struct hash *	,
		struct hash_elem *
	)

Inserts NEW into hash table H, replacing any equal element already in the table, which is returned.

Definition at line 115 of file hash.c.

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

Here is the call graph for this function:

hash_size()

size_t hash_size

(

struct hash *

h

)

Information.

Information.

Definition at line 248 of file hash.c.

References hash::elem_cnt.

hash_string()

unsigned hash_string

(

const char *

)

Returns a hash of string S.

Definition at line 283 of file hash.c.

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