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

   1 #ifndef HEADER_HASH_H
   2 #define HEADER_HASH_H 1
   3
   4 #include <stdbool.h>
   5 #include <stddef.h>
   6 #include <stdint.h>
   7 #include "list.h"
   8
   9 typedef list_elem hash_elem;
  10
  11 #define hash_entry(HASH_ELEM, STRUCT, MEMBER)                              \
  12         ((STRUCT *) ((uint8_t *) (HASH_ELEM) - offsetof (STRUCT, MEMBER)))
  13
  14 typedef bool hash_less_func (const hash_elem *a, const hash_elem *b,
  15                              void *aux);
  16 typedef unsigned hash_hash_func (const hash_elem *, void *aux);
  17
  18 struct hash
  19   {
  20     size_t elem_cnt;
  21     size_t bucket_cnt;
  22     struct list *buckets;
  23     hash_less_func *less;
  24     hash_hash_func *hash;
  25     void *aux;
  26   };
  27
  28 struct hash_iterator
  29   {
  30     struct hash *hash;
  31     struct list **bucket;
  32     hash_elem *elem;
  33   };
  34
  35 bool hash_init (struct hash *, hash_less_func *, hash_hash_func *, void *aux);
  36 void hash_clear (struct hash *);
  37 void hash_destroy (struct hash *);
  38
  39 hash_elem *hash_insert (struct hash *, hash_elem *);
  40 hash_elem *hash_replace (struct hash *, hash_elem *);
  41 hash_elem *hash_find (struct hash *, hash_elem *);
  42 hash_elem *hash_delete (struct hash *, hash_elem *);
  43
  44 void hash_first (struct hash_iterator *, struct hash *);
  45 hash_elem *hash_next (struct hash_iterator *);
  46 hash_elem *hash_cur (struct hash_iterator *);
  47
  48 size_t hash_size (struct hash *);
  49 bool hash_empty (struct hash *);
  50
  51 unsigned hash_bytes (const void *, size_t);
  52 unsigned hash_string (const char *);
  53 unsigned hash_int (int);
  54
  55 #endif /* hash.h */