PKUOS - Pintos
Pintos source browser for PKU Operating System course
Data Structures | Macros | Typedefs | Functions
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_elemhash_insert (struct hash *, struct hash_elem *)
 Search, insertion, deletion. More...
 
struct hash_elemhash_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_elemhash_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_elemhash_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_elemhash_next (struct hash_iterator *)
 Advances I to the next element in the hash table and returns it. More...
 
struct hash_elemhash_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)))
#define offsetof(TYPE, MEMBER)
Definition: stddef.h:5
unsigned char uint8_t
Definition: stdint.h:20
Doubly linked list.
Definition: list.h:91

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 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 
)

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

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 *  s_)

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.