myvtm/libtoolkit/hashset.h

#ifndef HASHSET_H
#define HASHSET_H

#pragma once

#include "config.h"

#ifdef __cplusplus
extern "C" {
#endif


#include "list.h"

#define HASH_DEFAULT_INIT_HASH_SIZE		15
#define HASH_DEFAULT_LOAD_FACTOR		0.72f

typedef struct hashset_t hashset_t;
typedef struct hashset_iterator hashset_iterator;

TOOLKIT_API int hash_get_prime(int min);

typedef const void* (*hashset_getkey)(const void *obj);
typedef unsigned int (*hashset_hash)(const void *key);
typedef int (*hashset_cmpkey)(const void *key_x, const void *key_y);

struct hashset_iterator {
	hashset_t *ht;
	int slot;
	struct hlist_node *pos, *pos_next;
};

struct hashset_t {
	struct hlist_head *buckets;
	int count;
	int size;
	int node_offset;
	float load_factor;
	hashset_getkey getkey_fn;
	hashset_hash hash_fn;
	hashset_cmpkey cmp_fn;
	hashset_iterator default_iterator;
};

/**
 * hash a set of object pointers
 * @param node_offset struct hlist_node offset in the structure, use offset_of macro
 * @param init_size initial size
 * @param getkey_fn get key from object
 * @param hash_fn get hashcode from key
 * @param cmp_fn compare key 
 */
TOOLKIT_API hashset_t *hashset_create2(int init_size,
					float load_factor, 
					int node_offset, 
					hashset_getkey getkey_fn, 
					hashset_hash hash_fn, 
					hashset_cmpkey cmp_fn);
TOOLKIT_API hashset_t * hashset_create(int node_offset, 
				   hashset_getkey getkey_fn, 
				   hashset_hash hash_fn, 
				   hashset_cmpkey cmp_fn);

/**
 * remove an object by key 
 * @return NULL obj not find
 */
TOOLKIT_API void* hashset_remove(hashset_t *ht, const void *key);

/**
 * add an object to hashset
 */
TOOLKIT_API int hashset_add(hashset_t *ht, void *obj);

/**
 * find object by key
 * @return null failed
 */
TOOLKIT_API void* hashset_find(hashset_t *ht, const void *key);

/**
 * get the number of objects in the hashset
 */
TOOLKIT_API int hashset_count(hashset_t *ht);

/**
 * destroy hashset 
 */
TOOLKIT_API void hashset_destroy(hashset_t *ht);

TOOLKIT_API hashset_iterator *hashset_default_iterator(hashset_t *ht);
TOOLKIT_API hashset_iterator *hashset_iterator_create(hashset_t *ht);
TOOLKIT_API void hashset_iterator_destroy(hashset_iterator *iter);
TOOLKIT_API int hashset_iterator_next(hashset_iterator *iter);
TOOLKIT_API void *hashset_iterator_get_object(hashset_iterator *iter);
TOOLKIT_API hashset_iterator *hashset_iterator_reset(hashset_iterator *iter);

static __inline struct hlist_node * __hashset_next_node(hashset_t *ht, struct hlist_node *pos, int *slot)
{
	if (pos)
		pos = pos->next;
	while (*slot < ht->size && !pos) {
		pos = ht->buckets[*slot].first;
		*slot = *slot + 1;
	}
	return pos;
}

/**
 * walk through hashset
 * @param tpos pointer to type 
 * @param pos temp pointer to struct hlist_node
 * @param slot temp int variable
 * @param ht hashtable pointer
 * @param type object type
 */
#define hashset_for_each(tpos, pos, slot, ht, type) \
	for (slot = 0, pos = NULL; \
	pos = __hashset_next_node(ht, pos, &slot), tpos = pos ? (type*)((char*)pos-(ht)->node_offset) : NULL;)

/**
 * walk through hashset, can remove tpos
 * @param pos temp pointer to struct hlist_node
 * @param n temp pointer to struct hlist_node
 */
#define hashset_for_each_safe(tpos, pos, n, slot, ht, type) \
	for (slot = 0, pos = __hashset_next_node(ht, NULL, &slot), n = __hashset_next_node(ht, pos, &slot); \
	tpos = (pos) ? (type*)((char*)pos-(ht)->node_offset) : NULL; \
	pos = n, n = __hashset_next_node(ht, pos, &slot))

/* string map(hash table) */

typedef struct stringmap_t stringmap_t;

TOOLKIT_API stringmap_t *stringmap_create(int init_size);
TOOLKIT_API void stringmap_destroy(stringmap_t *map);

typedef struct stringmap_kv_pair stringmap_kv_pair;

TOOLKIT_API const char* stringmap_kv_pair_get_key(stringmap_kv_pair *kv);
TOOLKIT_API void *stringmap_kv_pair_get_value(stringmap_kv_pair *kv);
TOOLKIT_API void *stringmap_kv_pair_set_value(stringmap_kv_pair *kv, void *newval);

TOOLKIT_API stringmap_kv_pair *stringmap_find(stringmap_t *map, const char *key);
TOOLKIT_API int stringmap_add(stringmap_t *map, const char *key, void *value);
TOOLKIT_API void *stringmap_remove(stringmap_t *map, const char *key);
TOOLKIT_API int stringmap_count(stringmap_t *map);

typedef struct stringmap_iterator stringmap_iterator;

TOOLKIT_API stringmap_iterator *stringmap_default_iterator(stringmap_t *map);
TOOLKIT_API stringmap_iterator *stringmap_iterator_create(stringmap_t *map);
TOOLKIT_API void stringmap_iterator_destroy(stringmap_iterator *iter);
TOOLKIT_API int stringmap_iterator_next(stringmap_iterator *iter);
TOOLKIT_API const char *stringmap_iterator_get_key(stringmap_iterator *iter);
TOOLKIT_API void *stringmap_iterator_get_value(stringmap_iterator *iter);
TOOLKIT_API stringmap_iterator *stringmap_iterator_reset(stringmap_iterator *iter);


// template version of hash table

typedef unsigned int (*__htable_hash)(const void *key);
typedef int (*__htable_compare)(const void *key1, const void *key2);

typedef struct htable_t {
	struct hlist_head *buckets;
	int count;
	int size;
}htable_t;

TOOLKIT_API int htable_init(htable_t *ht, int init_size);
TOOLKIT_API void htable_term(htable_t *ht);
TOOLKIT_API htable_t *htable_create(int init_size);
TOOLKIT_API void htable_destroy(htable_t *ht);

static __inline int htable_get_count(htable_t *ht) 
{ 
	return ht->count; 
}

#define __DECLARE_HTABLE(prefix, TKey, TObject, modifier)	\
modifier int prefix##_check_expand(htable_t *ht);	\
modifier TObject* prefix##_find(htable_t *ht, TKey* key);	\
modifier int prefix##_add(htable_t *ht, TObject* obj);		\
modifier void prefix##_remove(htable_t *ht, TObject* obj);


#define __IMPLEMENT_HTABLE(prefix, TKey, TObject, member_key, member_node, fun_hash, fun_cmp, modifier)	\
modifier int prefix##_check_expand(htable_t *ht) \
{	\
	if ((ht->count+1)/(float)ht->size > HASH_DEFAULT_LOAD_FACTOR) { \
		int i;	\
		int new_size = hash_get_prime(ht->size * 2);	\
		struct hlist_head *new_buckets = (struct hlist_head *)toolkit_zalloc(new_size*sizeof(struct hlist_head)); \
		if (!new_buckets)	\
			return -1;	\
		for (i = 0; i < ht->size; ++i) {	\
			TObject *tpos;	\
			struct hlist_node *pos, *n;	\
			hlist_for_each_entry_safe(tpos, pos, n, &ht->buckets[i], TObject, member_node) {	\
				unsigned int new_slot = fun_hash(&tpos->member_key) % new_size;	\
				hlist_del(pos);	\
				hlist_add_head(&tpos->member_node, &new_buckets[new_slot]);	\
			}	\
		}	\
		toolkit_free(ht->buckets);	\
		ht->buckets = new_buckets;	\
		ht->size = new_size;	\
	}	\
	return 0;	\
}	\
modifier TObject* prefix##_find_continue(htable_t *ht, struct hlist_node *position, TKey *key) \
{ \
	TObject *tpos; \
	struct hlist_node *pos = position;	\
	hlist_for_each_entry_continue(tpos, pos, TObject, member_node) { \
		if (fun_cmp(&tpos->member_key, key) == 0) \
			return tpos;	\
	} \
	return NULL; \
} \
modifier TObject* prefix##_find_from(htable_t *ht, struct hlist_node *position, TKey *key) \
{ \
	TObject *tpos; \
	struct hlist_node *pos = position;	\
	hlist_for_each_entry_from(tpos, pos, TObject, member_node) { \
		if (fun_cmp(&tpos->member_key, key) == 0) \
			return tpos;	\
	} \
	return NULL; \
} \
modifier TObject* prefix##_find(htable_t *ht, TKey *key)	\
{	\
	unsigned int k = fun_hash(key);	\
	int slot = k % ht->size;	\
	TObject *tpos;	\
	struct hlist_node *pos;	\
	hlist_for_each_entry(tpos, pos, &ht->buckets[slot], TObject, member_node) {	\
		if (fun_cmp(&tpos->member_key, key) == 0)	\
			return tpos;	\
	}	\
	return NULL;	\
}	\
modifier int prefix##_add(htable_t *ht, TObject *obj) \
{	\
	int rc;	\
	rc = prefix##_check_expand(ht);	\
	if (rc == 0) {	\
		unsigned int k = fun_hash(&obj->member_key);	\
		int slot = k % ht->size;	\
		hlist_add_head(&obj->member_node, &ht->buckets[slot]);	\
		ht->count++; \
	}	\
	return rc;	\
}	\
modifier void prefix##_remove(htable_t *ht, TObject* obj)	\
{	\
	hlist_del_init(&obj->member_node); \
	ht->count --; \
}

#define __HTABLE_NOTHING
#define __HTABLE_STATIC	static

#define DECLARE_HTABLE(prefix, TKey, TObject) __DECLARE_HTABLE(prefix, TKey, TObject, __HTABLE_NOTHING)
#define DECLARE_HTABLE_STATIC(prefix, TKey, TObject) __DECLARE_HTABLE(prefix, TKey, TObject, __HTABLE_STATIC)

#define IMPLEMENT_HTABLE(prefix, TKey, TObject, member_key, member_node, fun_hash, fun_cmp) __IMPLEMENT_HTABLE(prefix, TKey, TObject, member_key, member_node, fun_hash, fun_cmp, __HTABLE_NOTHING)
#define IMPLEMENT_HTABLE_STATIC(prefix, TKey, TObject, member_key, member_node, fun_hash, fun_cmp) __IMPLEMENT_HTABLE(prefix, TKey, TObject, member_key, member_node, fun_hash, fun_cmp, __HTABLE_STATIC)


#ifdef __cplusplus
} // extern "C" {
#endif

#endif // HASHSET_H