pintos-os.org Git - pintos-anon/blob - src/lib/hash.h

   1 #ifndef HEADER_HASH_H
   2 #define HEADER_HASH_H 1
   3
   4 /* Hash table.
   5
   6    This is a standard hash table with chaining.  To locate an
   7    element in the table, we compute a hash function over the
   8    element's data and use that as an index into an array of
   9    doubly linked lists, then linearly search the list.
  10
  11    The chain lists do not use dynamic allocation.  Instead, each
  12    structure that can potentially be in a hash must embed a
  13    hash_elem member.  All of the hash functions operate on these
  14    `hash_elem's.  The hash_entry macro allows conversion from a
  15    hash_elem back to a structure object that contains it.
  16
  17
  18
  19 */
  20
  21 #include <stdbool.h>
  22 #include <stddef.h>
  23 #include <stdint.h>
  24 #include "list.h"
  25
  26 /* Hash element. */
  27 typedef list_elem hash_elem;
  28
  29 /* Converts pointer to hash element HASH_ELEM into a pointer to
  30    the structure that HASH_ELEM is embedded inside.  Supply the
  31    name of the outer structure STRUCT and the member name MEMBER
  32    of the hash element.  See the big comment at the top of the
  33    file for an example. */
  34 #define hash_entry(HASH_ELEM, STRUCT, MEMBER)                              \
  35         ((STRUCT *) ((uint8_t *) (HASH_ELEM) - offsetof (STRUCT, MEMBER)))
  36
  37 /* Computes and returns the hash value for hash element E, given
  38    auxiliary data AUX. */
  39 typedef unsigned hash_hash_func (const hash_elem *e, void *aux);
  40
  41 /* Compares the value of two hash elements A and B, given
  42    auxiliary data AUX.  Returns true if A is less than B, or
  43    false if A is greater than or equal to B. */
  44 typedef bool hash_less_func (const hash_elem *a, const hash_elem *b,
  45                              void *aux);
  46
  47 /* Hash table. */
  48 struct hash
  49   {
  50     size_t elem_cnt;            /* Number of elements in table. */
  51     size_t bucket_cnt;          /* Number of buckets, a power of 2. */
  52     struct list *buckets;       /* Array of `bucket_cnt' lists. */
  53     hash_hash_func *hash;       /* Hash function. */
  54     hash_less_func *less;       /* Comparison function. */
  55     void *aux;                  /* Auxiliary data for `hash' and `less'. */
  56   };
  57
  58 /* A hash table iterator. */
  59 struct hash_iterator
  60   {
  61     struct hash *hash;          /* The hash table. */
  62     struct list *bucket;        /* Current bucket. */
  63     hash_elem *elem;            /* Current hash element in current bucket. */
  64   };
  65
  66 /* Basic life cycle. */
  67 bool hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux);
  68 void hash_clear (struct hash *);
  69 void hash_destroy (struct hash *);
  70
  71 /* Search, insertion, deletion. */
  72 hash_elem *hash_insert (struct hash *, hash_elem *);
  73 hash_elem *hash_replace (struct hash *, hash_elem *);
  74 hash_elem *hash_find (struct hash *, hash_elem *);
  75 hash_elem *hash_delete (struct hash *, hash_elem *);
  76
  77 /* Iteration. */
  78 void hash_first (struct hash_iterator *, struct hash *);
  79 hash_elem *hash_next (struct hash_iterator *);
  80 hash_elem *hash_cur (struct hash_iterator *);
  81
  82 /* Information. */
  83 size_t hash_size (struct hash *);
  84 bool hash_empty (struct hash *);
  85
  86 /* Sample hash functions. */
  87 unsigned hash_bytes (const void *, size_t);
  88 unsigned hash_string (const char *);
  89 unsigned hash_int (int);
  90
  91 #endif /* hash.h */