libqb/lib/hashtable.c - actifio - Git at Google

 /*
  * Copyright (C) 2010 Red Hat, Inc.
  *
  * Author: Steven Dake <sdake@redhat.com>
  *
  * This file is part of libqb.
  *
  * libqb is free software: you can redistribute it and/or modify
  * it under the terms of the GNU Lesser General Public License as published by
  * the Free Software Foundation, either version 2.1 of the License, or
  * (at your option) any later version.
  *
  * libqb is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public License
  * along with libqb.  If not, see <http://www.gnu.org/licenses/>.
  */
 #include "os_base.h"

 #include <qb/qbmap.h>
 #include "util_int.h"
 #include "map_int.h"
 #include <qb/qblist.h>

 #define FNV_32_PRIME ((uint32_t)0x01000193)

 struct hash_node {
 	struct qb_list_head list;
 	void *value;
 	const char *key;
 	uint32_t refcount;
 	struct qb_list_head notifier_head;
 };

 struct hash_bucket {
 	struct qb_list_head list_head;
 };

 struct hash_table {
 	struct qb_map map;
 	size_t count;
 	uint32_t order;
 	uint32_t hash_buckets_len;
 	struct qb_list_head notifier_head;
 	struct hash_bucket hash_buckets[0];
 };

 struct hashtable_iter {
 	struct qb_map_iter i;
 	struct hash_node *node;
 	uint32_t bucket;
 };

 static void hashtable_notify(struct hash_table *t, struct hash_node *n,
 			     uint32_t event, const char *key,
 			     void *old_value, void *value);
 static void hashtable_node_deref_under_bucket(struct qb_map *map,
 					      int32_t hash_entry);
 static void hashtable_node_destroy(struct hash_table *t,
 				   struct hash_node *hash_node);

 static uint32_t
 hash_fnv(const void *value, uint32_t valuelen, uint32_t order)
 {
 	uint8_t *cd = (uint8_t *) value;
 	uint8_t *ed = (uint8_t *) value + valuelen;
 	uint32_t hash_result = 0x811c9dc5;
 	int32_t res;

 	while (cd < ed) {
 		hash_result ^= *cd;
 		hash_result *= FNV_32_PRIME;
 		cd++;
 	}
 	res = ((hash_result >> order) ^ hash_result) & ((1 << order) - 1);
 	return (res);
 }

 static uint32_t
 qb_hash_string(const void *key, uint32_t order)
 {
 	char *str = (char *)key;
 	return hash_fnv(key, strlen(str), order);
 }

 static struct hash_node *
 hashtable_lookup(struct hash_table *t, const char *key)
 {
 	uint32_t hash_entry;
 	struct qb_list_head *list;
 	struct hash_node *hash_node;

 	hash_entry = qb_hash_string(key, t->order);

 	qb_list_for_each(list, &t->hash_buckets[hash_entry].list_head) {

 		hash_node = qb_list_entry(list, struct hash_node, list);
 		if (strcmp(hash_node->key, key) == 0) {
 			return hash_node;
 		}
 	}

 	return NULL;
 }

 static void *
 hashtable_get(struct qb_map *map, const char *key)
 {
 	struct hash_table *t = (struct hash_table *)map;
 	struct hash_node *n = hashtable_lookup(t, key);
 	if (n) {
 		return n->value;
 	}
 	return NULL;
 }

 static void
 hashtable_node_destroy(struct hash_table *t, struct hash_node *hash_node)
 {
 	struct qb_list_head *pos;
 	struct qb_list_head *next;
 	struct qb_map_notifier *tn;

 	hashtable_notify(t, hash_node,
 			 QB_MAP_NOTIFY_DELETED,
 			 hash_node->key, hash_node->value, NULL);

 	qb_list_for_each_safe(pos, next, &hash_node->notifier_head) {
 		tn = qb_list_entry(pos, struct qb_map_notifier, list);
 		qb_list_del(&tn->list);
 		free(tn);
 	}

 	qb_list_del(&hash_node->list);
 	free(hash_node);
 }

 static void
 hashtable_node_deref(struct qb_map *map, struct hash_node *hash_node)
 {
 	struct hash_table *t = (struct hash_table *)map;

 	hash_node->refcount--;
 	if (hash_node->refcount > 0) {
 		return;
 	}
 	hashtable_node_destroy(t, hash_node);
 }

 static int32_t
 hashtable_rm_with_hash(struct qb_map *map, const char *key, uint32_t hash_entry)
 {
 	struct hash_table *hash_table = (struct hash_table *)map;
 	struct qb_list_head *list;
 	struct qb_list_head *next;
 	struct hash_node *hash_node;

 	qb_list_for_each_safe(list, next,
 	                      &hash_table->hash_buckets[hash_entry].list_head) {

 		hash_node = qb_list_entry(list, struct hash_node, list);
 		if (strcmp(hash_node->key, key) == 0) {
 			hashtable_node_deref(map, hash_node);
 			hash_table->count--;
 			return QB_TRUE;
 		}
 	}

 	return QB_FALSE;
 }

 static int32_t
 hashtable_rm(struct qb_map *map, const char *key)
 {
 	struct hash_table *hash_table = (struct hash_table *)map;
 	uint32_t hash_entry;

 	hash_entry = qb_hash_string(key, hash_table->order);
 	return hashtable_rm_with_hash(map, key, hash_entry);
 }

 static void
 hashtable_put(struct qb_map *map, const char *key, const void *value)
 {
 	struct hash_table *hash_table = (struct hash_table *)map;
 	uint32_t hash_entry;
 	struct hash_node *hash_node = NULL;
 	struct hash_node *node_try;
 	struct qb_list_head *list;

 	hash_entry = qb_hash_string(key, hash_table->order);

 	qb_list_for_each(list, &hash_table->hash_buckets[hash_entry].list_head) {

 		node_try = qb_list_entry(list, struct hash_node, list);
 		if (strcmp(node_try->key, key) == 0) {
 			hash_node = node_try;
 			break;
 		}
 	}

 	if (hash_node == NULL) {
 		hash_node = calloc(1, sizeof(struct hash_node));
 		if (hash_node == NULL) {
 			errno = ENOMEM;
 			return;
 		}

 		hash_table->count++;
 		hash_node->refcount = 1;
 		hash_node->key = key;
 		hash_node->value = (void *)value;
 		qb_list_init(&hash_node->list);
 		qb_list_add_tail(&hash_node->list,
 				 &hash_table->hash_buckets[hash_entry].
 				 list_head);
 		qb_list_init(&hash_node->notifier_head);

 		hashtable_notify(hash_table, hash_node,
 				 QB_MAP_NOTIFY_INSERTED,
 				 hash_node->key, NULL, hash_node->value);
 	} else {
 		char *old_k = (char *)hash_node->key;
 		char *old_v = (void *)hash_node->value;
 		hash_node->key = key;
 		hash_node->value = (void *)value;

 		hashtable_notify(hash_table, hash_node,
 				 QB_MAP_NOTIFY_REPLACED,
 				 old_k, old_v, hash_node->value);
 	}
 }

 static void
 hashtable_notify(struct hash_table *t, struct hash_node *n,
 		 uint32_t event, const char *key,
 		 void *old_value, void *value)
 {
 	struct qb_list_head *list;
 	struct qb_map_notifier *tn;

 	qb_list_for_each(list, &n->notifier_head) {
 		tn = qb_list_entry(list, struct qb_map_notifier, list);

 		if (tn->events & event) {
 			tn->callback(event, (char *)key, old_value, value,
 				     tn->user_data);
 		}
 	}
 	qb_list_for_each(list, &t->notifier_head) {
 		tn = qb_list_entry(list, struct qb_map_notifier, list);

 		if (tn->events & event) {
 			tn->callback(event, (char *)key, old_value, value,
 				     tn->user_data);
 		}
 		if (((event & QB_MAP_NOTIFY_DELETED) ||
 		     (event & QB_MAP_NOTIFY_REPLACED)) &&
 		    (tn->events & QB_MAP_NOTIFY_FREE)) {
 			tn->callback(QB_MAP_NOTIFY_FREE, (char *)key,
 				     old_value, value, tn->user_data);
 		}
 	}
 }

 static int32_t
 hashtable_notify_add(qb_map_t * m, const char *key,
 		     qb_map_notify_fn fn, int32_t events, void *user_data)
 {
 	struct hash_table *t = (struct hash_table *)m;
 	struct qb_map_notifier *f;
 	struct hash_node *n;
 	struct qb_list_head *head = NULL;
 	struct qb_list_head *list;
 	int add_to_tail = QB_FALSE;

 	if (key) {
 		n = hashtable_lookup(t, key);
 		if (n) {
 			head = &n->notifier_head;
 		}
 	} else {
 		head = &t->notifier_head;
 	}
 	if (head == NULL) {
 		return -ENOENT;
 	}
 	if (events & QB_MAP_NOTIFY_FREE) {
 		add_to_tail = QB_TRUE;
 	}

 	qb_list_for_each(list, head) {
 		f = qb_list_entry(list, struct qb_map_notifier, list);

 		if (events & QB_MAP_NOTIFY_FREE &&
 		    f->events == events) {
 			/* only one free notifier */
 			return -EEXIST;
 		}
 		if (f->events == events &&
 		    f->user_data == user_data &&
 		    f->callback == fn) {
 			return -EEXIST;
 		}
 	}

 	f = malloc(sizeof(struct qb_map_notifier));
 	if (f == NULL) {
 		return -errno;
 	}
 	f->events = events;
 	f->user_data = user_data;
 	f->callback = fn;
 	qb_list_init(&f->list);

 	if (add_to_tail) {
 		qb_list_add_tail(&f->list, head);
 	} else {
 		qb_list_add(&f->list, head);
 	}
 	return 0;
 }

 static int32_t
 hashtable_notify_del(qb_map_t * m, const char *key,
 		     qb_map_notify_fn fn, int32_t events,
 		     int32_t cmp_userdata, void *user_data)
 {
 	struct hash_table *t = (struct hash_table *)m;
 	struct qb_map_notifier *f;
 	struct hash_node *n;
 	struct qb_list_head *head = NULL;
 	struct qb_list_head *list;
 	struct qb_list_head *next;
 	int32_t found = QB_FALSE;

 	if (key) {
 		n = hashtable_lookup(t, key);
 		if (n) {
 			head = &n->notifier_head;
 		}
 	} else {
 		head = &t->notifier_head;
 	}
 	if (head == NULL) {
 		return -ENOENT;
 	}

 	qb_list_for_each_safe(list, next, head) {
 		f = qb_list_entry(list, struct qb_map_notifier, list);

 		if (f->events == events && f->callback == fn) {
 			if (cmp_userdata && (f->user_data == user_data)) {
 				found = QB_TRUE;
 				qb_list_del(&f->list);
 				free(f);
 			} else if (!cmp_userdata) {
 				found = QB_TRUE;
 				qb_list_del(&f->list);
 				free(f);
 			}
 		}
 	}
 	if (found) {
 		return 0;
 	} else {
 		return -ENOENT;
 	}
 }

 static size_t
 hashtable_count_get(struct qb_map *map)
 {
 	struct hash_table *hash_table = (struct hash_table *)map;
 	return hash_table->count;
 }

 static qb_map_iter_t *
 hashtable_iter_create(struct qb_map *map, const char *prefix)
 {
 	struct hashtable_iter *i = malloc(sizeof(struct hashtable_iter));
 	if (i == NULL) {
 		return NULL;
 	}
 	i->i.m = map;
 	i->node = NULL;
 	i->bucket = 0;
 	return (qb_map_iter_t *) i;
 }

 static const char *
 hashtable_iter_next(qb_map_iter_t * it, void **value)
 {
 	struct hashtable_iter *hi = (struct hashtable_iter *)it;
 	struct hash_table *hash_table = (struct hash_table *)hi->i.m;
 	struct qb_list_head *ln;
 	struct hash_node *hash_node = NULL;
 	int found = QB_FALSE;
 	int cont = QB_TRUE;
 	int b;

 	if (hi->node == NULL) {
 		cont = QB_FALSE;
 	}
 	for (b = hi->bucket; b < hash_table->hash_buckets_len && !found; b++) {
 		if (cont) {
 			ln = &hi->node->list;
 			cont = QB_FALSE;
 		} else {
 			ln = &hash_table->hash_buckets[b].list_head;
 		}
 		hash_node = qb_list_first_entry(ln, struct hash_node, list);
 		qb_list_for_each_entry_from(hash_node,
 		                &hash_table->hash_buckets[b].list_head, list) {
 			if (hash_node->refcount > 0) {
 				found = QB_TRUE;
 				hash_node->refcount++;
 				hi->bucket = b;
 				*value = hash_node->value;
 				break;
 			}
 		}
 	}

 	if (hi->node) {
 		hashtable_node_deref(hi->i.m, hi->node);
 	}
 	if (!found) {
 		return NULL;
 	}
 	hi->node = hash_node;
 	return hash_node->key;
 }

 static void
 hashtable_iter_free(qb_map_iter_t * i)
 {
 	free(i);
 }

 static void
 hashtable_destroy(struct qb_map *map)
 {
 	struct hash_table *hash_table = (struct hash_table *)map;
 	struct qb_list_head *pos;
 	struct qb_list_head *next;
 	struct qb_map_notifier *tn;
 	int32_t i;

 	for (i = 0; i < hash_table->hash_buckets_len; i++) {
 		hashtable_node_deref_under_bucket(map, i);
 	}

 	qb_list_for_each_safe(pos, next, &hash_table->notifier_head) {
 		tn = qb_list_entry(pos, struct qb_map_notifier, list);
 		qb_list_del(&tn->list);
 		free(tn);
 	}

 	free(hash_table);
 }

 static void
 hashtable_node_deref_under_bucket(struct qb_map *map, int32_t hash_entry)
 {
 	struct hash_table *hash_table = (struct hash_table *)map;
 	struct hash_node *hash_node;
 	struct qb_list_head *pos;
 	struct qb_list_head *next;

 	qb_list_for_each_safe(pos, next,
 			      &hash_table->hash_buckets[hash_entry].list_head) {
 		hash_node = qb_list_entry(pos, struct hash_node, list);
 		hashtable_node_deref(map, hash_node);
 		hash_table->count--;
 	}
 }

 qb_map_t *
 qb_hashtable_create(size_t max_size)
 {
 	int32_t i;
 	int32_t order;
 	int32_t n = max_size;
 	uint64_t size;
 	struct hash_table *ht;

 	for (i = 0; n; i++) {
 		n >>= 1;
 	}
 	order = QB_MAX(i, 3);

 	size = sizeof(struct hash_table) +
 	    (sizeof(struct hash_bucket) * (1 << order));

 	ht = calloc(1, size);
 	if (ht == NULL) {
 		return NULL;
 	}

 	ht->map.put = hashtable_put;
 	ht->map.get = hashtable_get;
 	ht->map.rm = hashtable_rm;
 	ht->map.count_get = hashtable_count_get;
 	ht->map.iter_create = hashtable_iter_create;
 	ht->map.iter_next = hashtable_iter_next;
 	ht->map.iter_free = hashtable_iter_free;
 	ht->map.destroy = hashtable_destroy;
 	ht->map.notify_add = hashtable_notify_add;
 	ht->map.notify_del = hashtable_notify_del;
 	ht->count = 0;
 	ht->order = order;
 	qb_list_init(&ht->notifier_head);

 	ht->hash_buckets_len = 1 << order;
 	for (i = 0; i < ht->hash_buckets_len; i++) {
 		qb_list_init(&ht->hash_buckets[i].list_head);
 	}
 	return (qb_map_t *) ht;
 }
	/*
	* Copyright (C) 2010 Red Hat, Inc.
	*
	* Author: Steven Dake <sdake@redhat.com>
	*
	* This file is part of libqb.
	*
	* libqb is free software: you can redistribute it and/or modify
	* it under the terms of the GNU Lesser General Public License as published by
	* the Free Software Foundation, either version 2.1 of the License, or
	* (at your option) any later version.
	*
	* libqb is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	* GNU Lesser General Public License for more details.
	*
	* You should have received a copy of the GNU Lesser General Public License
	* along with libqb. If not, see <http://www.gnu.org/licenses/>.
	*/
	#include "os_base.h"

	#include <qb/qbmap.h>
	#include "util_int.h"
	#include "map_int.h"
	#include <qb/qblist.h>

	#define FNV_32_PRIME ((uint32_t)0x01000193)

	struct hash_node {
	struct qb_list_head list;
	void *value;
	const char *key;
	uint32_t refcount;
	struct qb_list_head notifier_head;
	};

	struct hash_bucket {
	struct qb_list_head list_head;
	};

	struct hash_table {
	struct qb_map map;
	size_t count;
	uint32_t order;
	uint32_t hash_buckets_len;
	struct qb_list_head notifier_head;
	struct hash_bucket hash_buckets[0];
	};

	struct hashtable_iter {
	struct qb_map_iter i;
	struct hash_node *node;
	uint32_t bucket;
	};

	static void hashtable_notify(struct hash_table t, struct hash_node n,
	uint32_t event, const char *key,
	void old_value, void value);
	static void hashtable_node_deref_under_bucket(struct qb_map *map,
	int32_t hash_entry);
	static void hashtable_node_destroy(struct hash_table *t,
	struct hash_node *hash_node);

	static uint32_t
	hash_fnv(const void *value, uint32_t valuelen, uint32_t order)
	{
	uint8_t cd = (uint8_t ) value;
	uint8_t ed = (uint8_t ) value + valuelen;
	uint32_t hash_result = 0x811c9dc5;
	int32_t res;

	while (cd < ed) {
	hash_result ^= *cd;
	hash_result *= FNV_32_PRIME;
	cd++;
	}
	res = ((hash_result >> order) ^ hash_result) & ((1 << order) - 1);
	return (res);
	}

	static uint32_t
	qb_hash_string(const void *key, uint32_t order)
	{
	char str = (char )key;
	return hash_fnv(key, strlen(str), order);
	}

	static struct hash_node *
	hashtable_lookup(struct hash_table t, const char key)
	{
	uint32_t hash_entry;
	struct qb_list_head *list;
	struct hash_node *hash_node;

	hash_entry = qb_hash_string(key, t->order);

	qb_list_for_each(list, &t->hash_buckets[hash_entry].list_head) {

	hash_node = qb_list_entry(list, struct hash_node, list);
	if (strcmp(hash_node->key, key) == 0) {
	return hash_node;
	}
	}

	return NULL;
	}

	static void *
	hashtable_get(struct qb_map map, const char key)
	{
	struct hash_table t = (struct hash_table )map;
	struct hash_node *n = hashtable_lookup(t, key);
	if (n) {
	return n->value;
	}
	return NULL;
	}

	static void
	hashtable_node_destroy(struct hash_table t, struct hash_node hash_node)
	{
	struct qb_list_head *pos;
	struct qb_list_head *next;
	struct qb_map_notifier *tn;

	hashtable_notify(t, hash_node,
	QB_MAP_NOTIFY_DELETED,
	hash_node->key, hash_node->value, NULL);

	qb_list_for_each_safe(pos, next, &hash_node->notifier_head) {
	tn = qb_list_entry(pos, struct qb_map_notifier, list);
	qb_list_del(&tn->list);
	free(tn);
	}

	qb_list_del(&hash_node->list);
	free(hash_node);
	}

	static void
	hashtable_node_deref(struct qb_map map, struct hash_node hash_node)
	{
	struct hash_table t = (struct hash_table )map;

	hash_node->refcount--;
	if (hash_node->refcount > 0) {
	return;
	}
	hashtable_node_destroy(t, hash_node);
	}

	static int32_t
	hashtable_rm_with_hash(struct qb_map map, const char key, uint32_t hash_entry)
	{
	struct hash_table hash_table = (struct hash_table )map;
	struct qb_list_head *list;
	struct qb_list_head *next;
	struct hash_node *hash_node;

	qb_list_for_each_safe(list, next,
	&hash_table->hash_buckets[hash_entry].list_head) {

	hash_node = qb_list_entry(list, struct hash_node, list);
	if (strcmp(hash_node->key, key) == 0) {
	hashtable_node_deref(map, hash_node);
	hash_table->count--;
	return QB_TRUE;
	}
	}

	return QB_FALSE;
	}

	static int32_t
	hashtable_rm(struct qb_map map, const char key)
	{
	struct hash_table hash_table = (struct hash_table )map;
	uint32_t hash_entry;

	hash_entry = qb_hash_string(key, hash_table->order);
	return hashtable_rm_with_hash(map, key, hash_entry);
	}

	static void
	hashtable_put(struct qb_map map, const char key, const void *value)
	{
	struct hash_table hash_table = (struct hash_table )map;
	uint32_t hash_entry;
	struct hash_node *hash_node = NULL;
	struct hash_node *node_try;
	struct qb_list_head *list;

	hash_entry = qb_hash_string(key, hash_table->order);

	qb_list_for_each(list, &hash_table->hash_buckets[hash_entry].list_head) {

	node_try = qb_list_entry(list, struct hash_node, list);
	if (strcmp(node_try->key, key) == 0) {
	hash_node = node_try;
	break;
	}
	}

	if (hash_node == NULL) {
	hash_node = calloc(1, sizeof(struct hash_node));
	if (hash_node == NULL) {
	errno = ENOMEM;
	return;
	}

	hash_table->count++;
	hash_node->refcount = 1;
	hash_node->key = key;
	hash_node->value = (void *)value;
	qb_list_init(&hash_node->list);
	qb_list_add_tail(&hash_node->list,
	&hash_table->hash_buckets[hash_entry].
	list_head);
	qb_list_init(&hash_node->notifier_head);

	hashtable_notify(hash_table, hash_node,
	QB_MAP_NOTIFY_INSERTED,
	hash_node->key, NULL, hash_node->value);
	} else {
	char old_k = (char )hash_node->key;
	char old_v = (void )hash_node->value;
	hash_node->key = key;
	hash_node->value = (void *)value;

	hashtable_notify(hash_table, hash_node,
	QB_MAP_NOTIFY_REPLACED,
	old_k, old_v, hash_node->value);
	}
	}

	static void
	hashtable_notify(struct hash_table t, struct hash_node n,
	uint32_t event, const char *key,
	void old_value, void value)
	{
	struct qb_list_head *list;
	struct qb_map_notifier *tn;

	qb_list_for_each(list, &n->notifier_head) {
	tn = qb_list_entry(list, struct qb_map_notifier, list);

	if (tn->events & event) {
	tn->callback(event, (char *)key, old_value, value,
	tn->user_data);
	}
	}
	qb_list_for_each(list, &t->notifier_head) {
	tn = qb_list_entry(list, struct qb_map_notifier, list);

	if (tn->events & event) {
	tn->callback(event, (char *)key, old_value, value,
	tn->user_data);
	}
	if (((event & QB_MAP_NOTIFY_DELETED) \|\|
	(event & QB_MAP_NOTIFY_REPLACED)) &&
	(tn->events & QB_MAP_NOTIFY_FREE)) {
	tn->callback(QB_MAP_NOTIFY_FREE, (char *)key,
	old_value, value, tn->user_data);
	}
	}
	}

	static int32_t
	hashtable_notify_add(qb_map_t * m, const char *key,
	qb_map_notify_fn fn, int32_t events, void *user_data)
	{
	struct hash_table t = (struct hash_table )m;
	struct qb_map_notifier *f;
	struct hash_node *n;
	struct qb_list_head *head = NULL;
	struct qb_list_head *list;
	int add_to_tail = QB_FALSE;

	if (key) {
	n = hashtable_lookup(t, key);
	if (n) {
	head = &n->notifier_head;
	}
	} else {
	head = &t->notifier_head;
	}
	if (head == NULL) {
	return -ENOENT;
	}
	if (events & QB_MAP_NOTIFY_FREE) {
	add_to_tail = QB_TRUE;
	}

	qb_list_for_each(list, head) {
	f = qb_list_entry(list, struct qb_map_notifier, list);

	if (events & QB_MAP_NOTIFY_FREE &&
	f->events == events) {
	/* only one free notifier */
	return -EEXIST;
	}
	if (f->events == events &&
	f->user_data == user_data &&
	f->callback == fn) {
	return -EEXIST;
	}
	}

	f = malloc(sizeof(struct qb_map_notifier));
	if (f == NULL) {
	return -errno;
	}
	f->events = events;
	f->user_data = user_data;
	f->callback = fn;
	qb_list_init(&f->list);

	if (add_to_tail) {
	qb_list_add_tail(&f->list, head);
	} else {
	qb_list_add(&f->list, head);
	}
	return 0;
	}

	static int32_t
	hashtable_notify_del(qb_map_t * m, const char *key,
	qb_map_notify_fn fn, int32_t events,
	int32_t cmp_userdata, void *user_data)
	{
	struct hash_table t = (struct hash_table )m;
	struct qb_map_notifier *f;
	struct hash_node *n;
	struct qb_list_head *head = NULL;
	struct qb_list_head *list;
	struct qb_list_head *next;
	int32_t found = QB_FALSE;

	if (key) {
	n = hashtable_lookup(t, key);
	if (n) {
	head = &n->notifier_head;
	}
	} else {
	head = &t->notifier_head;
	}
	if (head == NULL) {
	return -ENOENT;
	}

	qb_list_for_each_safe(list, next, head) {
	f = qb_list_entry(list, struct qb_map_notifier, list);

	if (f->events == events && f->callback == fn) {
	if (cmp_userdata && (f->user_data == user_data)) {
	found = QB_TRUE;
	qb_list_del(&f->list);
	free(f);
	} else if (!cmp_userdata) {
	found = QB_TRUE;
	qb_list_del(&f->list);
	free(f);
	}
	}
	}
	if (found) {
	return 0;
	} else {
	return -ENOENT;
	}
	}

	static size_t
	hashtable_count_get(struct qb_map *map)
	{
	struct hash_table hash_table = (struct hash_table )map;
	return hash_table->count;
	}

	static qb_map_iter_t *
	hashtable_iter_create(struct qb_map map, const char prefix)
	{
	struct hashtable_iter *i = malloc(sizeof(struct hashtable_iter));
	if (i == NULL) {
	return NULL;
	}
	i->i.m = map;
	i->node = NULL;
	i->bucket = 0;
	return (qb_map_iter_t *) i;
	}

	static const char *
	hashtable_iter_next(qb_map_iter_t * it, void **value)
	{
	struct hashtable_iter hi = (struct hashtable_iter )it;
	struct hash_table hash_table = (struct hash_table )hi->i.m;
	struct qb_list_head *ln;
	struct hash_node *hash_node = NULL;
	int found = QB_FALSE;
	int cont = QB_TRUE;
	int b;

	if (hi->node == NULL) {
	cont = QB_FALSE;
	}
	for (b = hi->bucket; b < hash_table->hash_buckets_len && !found; b++) {
	if (cont) {
	ln = &hi->node->list;
	cont = QB_FALSE;
	} else {
	ln = &hash_table->hash_buckets[b].list_head;
	}
	hash_node = qb_list_first_entry(ln, struct hash_node, list);
	qb_list_for_each_entry_from(hash_node,
	&hash_table->hash_buckets[b].list_head, list) {
	if (hash_node->refcount > 0) {
	found = QB_TRUE;
	hash_node->refcount++;
	hi->bucket = b;
	*value = hash_node->value;
	break;
	}
	}
	}

	if (hi->node) {
	hashtable_node_deref(hi->i.m, hi->node);
	}
	if (!found) {
	return NULL;
	}
	hi->node = hash_node;
	return hash_node->key;
	}

	static void
	hashtable_iter_free(qb_map_iter_t * i)
	{
	free(i);
	}

	static void
	hashtable_destroy(struct qb_map *map)
	{
	struct hash_table hash_table = (struct hash_table )map;
	struct qb_list_head *pos;
	struct qb_list_head *next;
	struct qb_map_notifier *tn;
	int32_t i;

	for (i = 0; i < hash_table->hash_buckets_len; i++) {
	hashtable_node_deref_under_bucket(map, i);
	}

	qb_list_for_each_safe(pos, next, &hash_table->notifier_head) {
	tn = qb_list_entry(pos, struct qb_map_notifier, list);
	qb_list_del(&tn->list);
	free(tn);
	}

	free(hash_table);
	}

	static void
	hashtable_node_deref_under_bucket(struct qb_map *map, int32_t hash_entry)
	{
	struct hash_table hash_table = (struct hash_table )map;
	struct hash_node *hash_node;
	struct qb_list_head *pos;
	struct qb_list_head *next;

	qb_list_for_each_safe(pos, next,
	&hash_table->hash_buckets[hash_entry].list_head) {
	hash_node = qb_list_entry(pos, struct hash_node, list);
	hashtable_node_deref(map, hash_node);
	hash_table->count--;
	}
	}

	qb_map_t *
	qb_hashtable_create(size_t max_size)
	{
	int32_t i;
	int32_t order;
	int32_t n = max_size;
	uint64_t size;
	struct hash_table *ht;

	for (i = 0; n; i++) {
	n >>= 1;
	}
	order = QB_MAX(i, 3);

	size = sizeof(struct hash_table) +
	(sizeof(struct hash_bucket) * (1 << order));

	ht = calloc(1, size);
	if (ht == NULL) {
	return NULL;
	}

	ht->map.put = hashtable_put;
	ht->map.get = hashtable_get;
	ht->map.rm = hashtable_rm;
	ht->map.count_get = hashtable_count_get;
	ht->map.iter_create = hashtable_iter_create;
	ht->map.iter_next = hashtable_iter_next;
	ht->map.iter_free = hashtable_iter_free;
	ht->map.destroy = hashtable_destroy;
	ht->map.notify_add = hashtable_notify_add;
	ht->map.notify_del = hashtable_notify_del;
	ht->count = 0;
	ht->order = order;
	qb_list_init(&ht->notifier_head);

	ht->hash_buckets_len = 1 << order;
	for (i = 0; i < ht->hash_buckets_len; i++) {
	qb_list_init(&ht->hash_buckets[i].list_head);
	}
	return (qb_map_t *) ht;
	}