PKUOS - Pintos
Pintos source browser for PKU Operating System course
Macros | Functions
hash.c File Reference
#include "hash.h"
#include "../debug.h"
#include "threads/malloc.h"
Include dependency graph for hash.c:

Go to the source code of this file.

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 listfind_bucket (struct hash *h, struct hash_elem *e)
 Returns the bucket in H that E belongs in. More...
 
static struct hash_elemfind_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_elemhash_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_elemhash_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_elemhash_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_elemhash_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_elemhash_next (struct hash_iterator *i)
 Advances I to the next element in the hash table and returns it. More...
 
struct hash_elemhash_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.

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)

Returns the number of elements in H.

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.

◆ insert_elem()

static void insert_elem ( struct hash h,
struct list bucket,
struct hash_elem e 
)
static

Inserts E into BUCKET (in hash table H).

Definition at line 417 of file hash.c.

References hash::elem_cnt, hash_elem::list_elem, and list_push_front().

Referenced by hash_insert(), and hash_replace().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ is_power_of_2()

static size_t is_power_of_2 ( size_t  x)
inlinestatic

Returns true if X is a power of 2, otherwise false.

Definition at line 337 of file hash.c.

References turn_off_least_1bit(), and x.

Referenced by rehash().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ rehash()

static void rehash ( struct hash h)
static

Changes the number of buckets in hash table H to match the ideal.

This function can fail because of an out-of-memory condition, but that'll just make hash accesses less efficient; we can still continue.

Definition at line 352 of file hash.c.

References ASSERT, BEST_ELEMS_PER_BUCKET, hash::bucket_cnt, hash::buckets, hash::elem_cnt, find_bucket(), free(), is_power_of_2(), list_begin(), list_elem_to_hash_elem, list_end(), list_init(), list_next(), list_push_front(), list_remove(), malloc(), next(), NULL, and turn_off_least_1bit().

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ remove_elem()

static void remove_elem ( struct hash h,
struct hash_elem e 
)
static

Removes E from hash table H.

Definition at line 425 of file hash.c.

References hash::elem_cnt, hash_elem::list_elem, and list_remove().

Referenced by hash_delete(), and hash_replace().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ turn_off_least_1bit()

static size_t turn_off_least_1bit ( size_t  x)
inlinestatic

Returns X with its lowest-order bit set to 1 turned off.

Definition at line 330 of file hash.c.

References x.

Referenced by is_power_of_2(), and rehash().

Here is the caller graph for this function: