hash.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include "list.h"

Include dependency graph for hash.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	hash_elem
struct	hash
struct	hash_iterator

Macros
#define	hash_entry(HASH_ELEM, STRUCT, MEMBER)

Typedefs
typedef uint64_t	hash_hash_func(const struct hash_elem *e, void *aux)
typedef bool	hash_less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux)
typedef void	hash_action_func(struct hash_elem *e, void *aux)

Functions
bool	hash_init (struct hash *, hash_hash_func *, hash_less_func *, void *aux)
void	hash_clear (struct hash *, hash_action_func *)
void	hash_destroy (struct hash *, hash_action_func *)
struct hash_elem *	hash_insert (struct hash *, struct hash_elem *)
struct hash_elem *	hash_replace (struct hash *, struct hash_elem *)
struct hash_elem *	hash_find (struct hash *, struct hash_elem *)
struct hash_elem *	hash_delete (struct hash *, struct hash_elem *)
void	hash_apply (struct hash *, hash_action_func *)
void	hash_first (struct hash_iterator *, struct hash *)
struct hash_elem *	hash_next (struct hash_iterator *)
struct hash_elem *	hash_cur (struct hash_iterator *)
size_t	hash_size (struct hash *)
bool	hash_empty (struct hash *)
uint64_t	hash_bytes (const void *, size_t)
uint64_t	hash_string (const char *)
uint64_t	hash_int (int)

Macro Definition Documentation

hash_entry

#define hash_entry	(		HASH_ELEM,
			STRUCT,
			MEMBER
	)

Value:

    ((STRUCT *) ((uint8_t *) &(HASH_ELEM)->list_elem        \
        - offsetof (STRUCT, MEMBER.list_elem)))

Typedef Documentation

hash_action_func

typedef void hash_action_func(struct hash_elem *e, void *aux)

hash_hash_func

typedef uint64_t hash_hash_func(const struct hash_elem *e, void *aux)

hash_less_func

typedef bool hash_less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux)

Function Documentation

hash_apply()

void hash_apply	(	struct hash *	h,
		hash_action_func *	action
	)

                                                      {
    size_t i;
 
    ASSERT (action != NULL);
 
    for (i = 0; i < h->bucket_cnt; i++) {
        struct list *bucket = &h->buckets[i];
        struct list_elem *elem, *next;
 
        for (elem = list_begin (bucket); elem != list_end (bucket); elem = next) {
            next = list_next (elem);
            action (list_elem_to_hash_elem (elem), h->aux);
        }
    }
}

Here is the call graph for this function:

hash_bytes()

uint64_t hash_bytes	(	const void *	buf_,
		size_t	size
	)

                                           {
    /* Fowler-Noll-Vo 32-bit hash, for bytes. */
    const unsigned char *buf = buf_;
    uint64_t hash;
 
    ASSERT (buf != NULL);
 
    hash = FNV_64_BASIS;
    while (size-- > 0)
        hash = (hash * FNV_64_PRIME) ^ *buf++;
 
    return hash;
}

Here is the caller graph for this function:

hash_clear()

void hash_clear	(	struct hash *	h,
		hash_action_func *	destructor
	)

                                                          {
    size_t i;
 
    for (i = 0; i < h->bucket_cnt; i++) {
        struct list *bucket = &h->buckets[i];
 
        if (destructor != NULL)
            while (!list_empty (bucket)) {
                struct list_elem *list_elem = list_pop_front (bucket);
                struct hash_elem *hash_elem = list_elem_to_hash_elem (list_elem);
                destructor (hash_elem, h->aux);
            }
 
        list_init (bucket);
    }
 
    h->elem_cnt = 0;
}

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

)

                                   {
    return i->elem;
}

Here is the caller graph for this function:

hash_delete()

struct hash_elem * hash_delete	(	struct hash *	h,
		struct hash_elem *	e
	)

                                                  {
    struct hash_elem *found = find_elem (h, find_bucket (h, e), e);
    if (found != NULL) {
        remove_elem (h, found);
        rehash (h);
    }
    return found;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_destroy()

void hash_destroy	(	struct hash *	h,
		hash_action_func *	destructor
	)

                                                            {
    if (destructor != NULL)
        hash_clear (h, destructor);
    free (h->buckets);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_empty()

bool hash_empty

(

struct hash *

h

)

                            {
    return h->elem_cnt == 0;
}

Here is the caller graph for this function:

hash_find()

struct hash_elem * hash_find	(	struct hash *	h,
		struct hash_elem *	e
	)

                                                {
    return find_elem (h, find_bucket (h, e), e);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_first()

void hash_first	(	struct hash_iterator *	i,
		struct hash *	h
	)

                                                     {
    ASSERT (i != NULL);
    ASSERT (h != NULL);
 
    i->hash = h;
    i->bucket = i->hash->buckets;
    i->elem = list_elem_to_hash_elem (list_head (i->bucket));
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_init()

bool hash_init	(	struct hash *	h,
		hash_hash_func *	hash,
		hash_less_func *	less,
		void *	aux
	)

                                                               {
    h->elem_cnt = 0;
    h->bucket_cnt = 4;
    h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
    h->hash = hash;
    h->less = less;
    h->aux = aux;
 
    if (h->buckets != NULL) {
        hash_clear (h, NULL);
        return true;
    } else
        return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_insert()

struct hash_elem * hash_insert	(	struct hash *	h,
		struct hash_elem *	new
	)

                                                    {
    struct list *bucket = find_bucket (h, new);
    struct hash_elem *old = find_elem (h, bucket, new);
 
    if (old == NULL)
        insert_elem (h, bucket, new);
 
    rehash (h);
 
    return old;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_int()

uint64_t hash_int

(

int

i

)

                 {
    return hash_bytes (&i, sizeof i);
}

Here is the call graph for this function:

hash_next()

struct hash_elem * hash_next

(

struct hash_iterator *

i

)

                                    {
    ASSERT (i != NULL);
 
    i->elem = list_elem_to_hash_elem (list_next (&i->elem->list_elem));
    while (i->elem == list_elem_to_hash_elem (list_end (i->bucket))) {
        if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt) {
            i->elem = NULL;
            break;
        }
        i->elem = list_elem_to_hash_elem (list_begin (i->bucket));
    }
 
    return i->elem;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_replace()

struct hash_elem * hash_replace	(	struct hash *	h,
		struct hash_elem *	new
	)

                                                     {
    struct list *bucket = find_bucket (h, new);
    struct hash_elem *old = find_elem (h, bucket, new);
 
    if (old != NULL)
        remove_elem (h, old);
    insert_elem (h, bucket, new);
 
    rehash (h);
 
    return old;
}

Here is the call graph for this function:

hash_size()

size_t hash_size

(

struct hash *

h

)

                           {
    return h->elem_cnt;
}

hash_string()

uint64_t hash_string

(

const char *

s_

)

                             {
    const unsigned char *s = (const unsigned char *) s_;
    uint64_t hash;
 
    ASSERT (s != NULL);
 
    hash = FNV_64_BASIS;
    while (*s != '\0')
        hash = (hash * FNV_64_PRIME) ^ *s++;
 
    return hash;
}