#include "hash.h"#include "../debug.h"#include "threads/malloc.h"Go to the source code of this file.
Defines | |
| #define | list_elem_to_hash_elem(LIST_ELEM) list_entry(LIST_ELEM, struct hash_elem, list_elem) |
| #define | FNV_32_PRIME 16777619u |
| #define | FNV_32_BASIS 2166136261u |
| #define | MIN_ELEMS_PER_BUCKET 1 |
| #define | BEST_ELEMS_PER_BUCKET 2 |
| #define | MAX_ELEMS_PER_BUCKET 4 |
Functions | |
| 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 *) |
| bool | hash_init (struct hash *h, hash_hash_func *hash, hash_less_func *less, void *aux) |
| void | hash_clear (struct hash *h, hash_action_func *destructor) |
| void | hash_destroy (struct hash *h, hash_action_func *destructor) |
| struct hash_elem * | hash_insert (struct hash *h, struct hash_elem *new) |
| struct hash_elem * | hash_replace (struct hash *h, struct hash_elem *new) |
| struct hash_elem * | hash_find (struct hash *h, struct hash_elem *e) |
| struct hash_elem * | hash_delete (struct hash *h, struct hash_elem *e) |
| void | hash_apply (struct hash *h, hash_action_func *action) |
| void | hash_first (struct hash_iterator *i, struct hash *h) |
| struct hash_elem * | hash_next (struct hash_iterator *i) |
| struct hash_elem * | hash_cur (struct hash_iterator *i) |
| size_t | hash_size (struct hash *h) |
| bool | hash_empty (struct hash *h) |
| unsigned | hash_bytes (const void *buf_, size_t size) |
| unsigned | hash_string (const char *s_) |
| unsigned | hash_int (int i) |
| static size_t | turn_off_least_1bit (size_t x) |
| static size_t | is_power_of_2 (size_t x) |
| #define FNV_32_BASIS 2166136261u |
| #define FNV_32_PRIME 16777619u |
Definition at line 12 of file hash.c.
Referenced by find_elem(), hash_apply(), hash_clear(), hash_first(), hash_next(), and rehash().
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().
| static struct hash_elem * find_elem | ( | struct hash * | h, | |
| struct list * | bucket, | |||
| struct hash_elem * | e | |||
| ) | [static, read] |
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().
| void hash_apply | ( | struct hash * | h, | |
| hash_action_func * | action | |||
| ) |
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.
| unsigned hash_bytes | ( | const void * | buf_, | |
| size_t | size | |||
| ) |
Definition at line 266 of file hash.c.
References ASSERT, buf, FNV_32_BASIS, FNV_32_PRIME, and NULL.
Referenced by hash_int().
| void hash_clear | ( | struct hash * | h, | |
| hash_action_func * | destructor | |||
| ) |
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().
| struct hash_elem* hash_cur | ( | struct hash_iterator * | i | ) | [read] |
Definition at line 145 of file hash.c.
References find_bucket(), find_elem(), NULL, rehash(), and remove_elem().
| void hash_destroy | ( | struct hash * | h, | |
| hash_action_func * | destructor | |||
| ) |
| bool hash_empty | ( | struct hash * | h | ) |
| void hash_first | ( | struct hash_iterator * | i, | |
| struct hash * | h | |||
| ) |
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.
| bool hash_init | ( | struct hash * | h, | |
| hash_hash_func * | hash, | |||
| hash_less_func * | less, | |||
| void * | aux | |||
| ) |
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.
Definition at line 99 of file hash.c.
References find_bucket(), find_elem(), insert_elem(), NULL, and rehash().
| unsigned hash_int | ( | int | i | ) |
| struct hash_elem* hash_next | ( | struct hash_iterator * | i | ) | [read] |
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.
Definition at line 115 of file hash.c.
References find_bucket(), find_elem(), insert_elem(), NULL, rehash(), and remove_elem().
| unsigned hash_string | ( | const char * | s_ | ) |
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().
| static void rehash | ( | struct hash * | h | ) | [static] |
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().
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().
1.5.6