hash.c File Reference

#include "hash.h"
#include "../debug.h"
#include "threads/malloc.h"

Include dependency graph for hash.c:

Macros
#define	list_elem_to_hash_elem(LIST_ELEM)    list_entry(LIST_ELEM, struct hash_elem, list_elem)
#define	FNV_64_PRIME   0x00000100000001B3UL
#define	FNV_64_BASIS   0xcbf29ce484222325UL
#define	MIN_ELEMS_PER_BUCKET   1 /* Elems/bucket < 1: reduce # of buckets. */
#define	BEST_ELEMS_PER_BUCKET   2 /* Ideal elems/bucket. */
#define	MAX_ELEMS_PER_BUCKET   4 /* Elems/bucket > 4: increase # of buckets. */

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)
uint64_t	hash_bytes (const void *buf_, size_t size)
uint64_t	hash_string (const char *s_)
uint64_t	hash_int (int i)
static size_t	turn_off_least_1bit (size_t x)
static size_t	is_power_of_2 (size_t x)

Macro Definition Documentation

BEST_ELEMS_PER_BUCKET

#define BEST_ELEMS_PER_BUCKET   2 /* Ideal elems/bucket. */

FNV_64_BASIS

#define FNV_64_BASIS   0xcbf29ce484222325UL

FNV_64_PRIME

#define FNV_64_PRIME   0x00000100000001B3UL

list_elem_to_hash_elem

#define list_elem_to_hash_elem

(

LIST_ELEM

)

list_entry(LIST_ELEM, struct hash_elem, list_elem)

MAX_ELEMS_PER_BUCKET

#define MAX_ELEMS_PER_BUCKET   4 /* Elems/bucket > 4: increase # of buckets. */

MIN_ELEMS_PER_BUCKET

#define MIN_ELEMS_PER_BUCKET   1 /* Elems/bucket < 1: reduce # of buckets. */

Function Documentation

find_bucket()

static struct list * find_bucket ( struct hash *  h, struct hash_elem *  e  )

static

                                                  {
    size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
    return &h->buckets[bucket_idx];
}

Here is the call graph for this function:

Here is the caller graph for this function:

find_elem()

static struct hash_elem * find_elem ( struct hash *  h, struct list *  bucket, struct hash_elem *  e  )

static

                                                                     {
    struct list_elem *i;
 
    for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i)) {
        struct hash_elem *hi = list_elem_to_hash_elem (i);
        if (!h->less (hi, e, h->aux) && !h->less (e, hi, h->aux))
            return hi;
    }
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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;
}

insert_elem()

static void insert_elem ( struct hash *  h, struct list *  bucket, struct hash_elem *  e  )

static

                                                                       {
    h->elem_cnt++;
    list_push_front (bucket, &e->list_elem);
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_power_of_2()

static size_t is_power_of_2 ( size_t  x )

inlinestatic

                         {
    return x != 0 && turn_off_least_1bit (x) == 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

rehash()

static void rehash ( struct hash *  h )

static

                        {
    size_t old_bucket_cnt, new_bucket_cnt;
    struct list *new_buckets, *old_buckets;
    size_t i;
 
    ASSERT (h != NULL);
 
    /* Save old bucket info for later use. */
    old_buckets = h->buckets;
    old_bucket_cnt = h->bucket_cnt;
 
    /* Calculate the number of buckets to use now.
       We want one bucket for about every BEST_ELEMS_PER_BUCKET.
       We must have at least four buckets, and the number of
       buckets must be a power of 2. */
    new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
    if (new_bucket_cnt < 4)
        new_bucket_cnt = 4;
    while (!is_power_of_2 (new_bucket_cnt))
        new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
 
    /* Don't do anything if the bucket count wouldn't change. */
    if (new_bucket_cnt == old_bucket_cnt)
        return;
 
    /* Allocate new buckets and initialize them as empty. */
    new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
    if (new_buckets == NULL) {
        /* Allocation failed.  This means that use of the hash table will
           be less efficient.  However, it is still usable, so
           there's no reason for it to be an error. */
        return;
    }
    for (i = 0; i < new_bucket_cnt; i++)
        list_init (&new_buckets[i]);
 
    /* Install new bucket info. */
    h->buckets = new_buckets;
    h->bucket_cnt = new_bucket_cnt;
 
    /* Move each old element into the appropriate new bucket. */
    for (i = 0; i < old_bucket_cnt; i++) {
        struct list *old_bucket;
        struct list_elem *elem, *next;
 
        old_bucket = &old_buckets[i];
        for (elem = list_begin (old_bucket);
                elem != list_end (old_bucket); elem = next) {
            struct list *new_bucket
                = find_bucket (h, list_elem_to_hash_elem (elem));
            next = list_next (elem);
            list_remove (elem);
            list_push_front (new_bucket, elem);
        }
    }
 
    free (old_buckets);
}

Here is the call graph for this function:

Here is the caller graph for this function:

remove_elem()

static void remove_elem ( struct hash *  h, struct hash_elem *  e  )

static

                                                  {
    h->elem_cnt--;
    list_remove (&e->list_elem);
}

Here is the call graph for this function:

Here is the caller graph for this function:

turn_off_least_1bit()

static size_t turn_off_least_1bit ( size_t  x )

inlinestatic

                               {
    return x & (x - 1);
}

Here is the caller graph for this function: