1 #ifndef __LIB_KERNEL_HASH_H
2 #define __LIB_KERNEL_HASH_H
6 This data structure is thoroughly documented in the Tour of
9 This is a standard hash table with chaining. To locate an
10 element in the table, we compute a hash function over the
11 element's data and use that as an index into an array of
12 doubly linked lists, then linearly search the list.
14 The chain lists do not use dynamic allocation. Instead, each
15 structure that can potentially be in a hash must embed a
16 struct hash_elem member. All of the hash functions operate on
17 these `struct hash_elem's. The hash_entry macro allows
18 conversion from a struct hash_elem back to a structure object
19 that contains it. This is the same technique used in the
20 linked list implementation. Refer to lib/kernel/list.h for a
21 detailed explanation. */
31 struct list_elem list_elem;
34 /* Converts pointer to hash element HASH_ELEM into a pointer to
35 the structure that HASH_ELEM is embedded inside. Supply the
36 name of the outer structure STRUCT and the member name MEMBER
37 of the hash element. See the big comment at the top of the
38 file for an example. */
39 #define hash_entry(HASH_ELEM, STRUCT, MEMBER) \
40 ((STRUCT *) ((uint8_t *) (HASH_ELEM) - offsetof (STRUCT, MEMBER)))
42 /* Computes and returns the hash value for hash element E, given
43 auxiliary data AUX. */
44 typedef unsigned hash_hash_func (const struct hash_elem *e, void *aux);
46 /* Compares the value of two hash elements A and B, given
47 auxiliary data AUX. Returns true if A is less than B, or
48 false if A is greater than or equal to B. */
49 typedef bool hash_less_func (const struct hash_elem *a,
50 const struct hash_elem *b,
53 /* Performs some operation on hash element E, given auxiliary
55 typedef void hash_action_func (struct hash_elem *e, void *aux);
60 size_t elem_cnt; /* Number of elements in table. */
61 size_t bucket_cnt; /* Number of buckets, a power of 2. */
62 struct list *buckets; /* Array of `bucket_cnt' lists. */
63 hash_hash_func *hash; /* Hash function. */
64 hash_less_func *less; /* Comparison function. */
65 void *aux; /* Auxiliary data for `hash' and `less'. */
68 /* A hash table iterator. */
71 struct hash *hash; /* The hash table. */
72 struct list *bucket; /* Current bucket. */
73 struct hash_elem *elem; /* Current hash element in current bucket. */
76 /* Basic life cycle. */
77 bool hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux);
78 void hash_clear (struct hash *, hash_action_func *);
79 void hash_destroy (struct hash *, hash_action_func *);
81 /* Search, insertion, deletion. */
82 struct hash_elem *hash_insert (struct hash *, struct hash_elem *);
83 struct hash_elem *hash_replace (struct hash *, struct hash_elem *);
84 struct hash_elem *hash_find (struct hash *, struct hash_elem *);
85 struct hash_elem *hash_delete (struct hash *, struct hash_elem *);
88 void hash_apply (struct hash *, hash_action_func *);
89 void hash_first (struct hash_iterator *, struct hash *);
90 struct hash_elem *hash_next (struct hash_iterator *);
91 struct hash_elem *hash_cur (struct hash_iterator *);
94 size_t hash_size (struct hash *);
95 bool hash_empty (struct hash *);
97 /* Sample hash functions. */
98 unsigned hash_bytes (const void *, size_t);
99 unsigned hash_string (const char *);
100 unsigned hash_int (int);
102 #endif /* lib/kernel/hash.h */