CToolBox/include/toolbox/ht.h

#ifndef HT_H
#define HT_H

#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#include "da.h"

#ifndef typeof
#define typeof __typeof__
#endif

#define CONCAT(a, b) CONCAT_INNER(a, b)
#define CONCAT_INNER(a, b) a ## b
#define UNIQUE_NAME(base) CONCAT(base, __COUNTER__)

typedef uint64_t (*ht_hash_func)(const char *, size_t);

uint64_t ht_default_hash(const char *str, size_t str_size);

#define HT_DEF_STRUCT(type, name)			\
	struct name##_item {				\
		struct {				\
			const char *data;		\
			size_t size;			\
		} key_str;				\
		uint64_t key;				\
		type data;				\
		void *next;				\
	};						\
	struct name {					\
		struct name##_item *items;		\
		size_t size;				\
		size_t cap;				\
		DA_DEF_STRUCT_ITEM(uint64_t, keys);	\
		ht_hash_func hash;			\
		size_t collisions;			\
	}

#define HT_DEF_STRUCT_ITEM(type, name)			\
	struct {					\
		struct {				\
			uint64_t key;			\
			type data;			\
			void *next;			\
		} *items;				\
		size_t size;				\
		size_t cap;				\
		ht_hash_func hash;			\
	} name


#define HT_CREATE(ht, init_cap)					\
	do {								\
		(ht).cap = (init_cap);					\
		(ht).size = 0;						\
		(ht).items = calloc((ht).cap, sizeof(*(ht).items));	\
		(ht).hash = ht_default_hash;				\
		DA_CREATE((ht).keys);					\
	} while(0)

#define _HT_DESTROY(ht, _t, _hi)					\
	do{								\
		void *_t = NULL;					\
		for ( i = 0; i < (ht).cap; ++i ) {			\
			typeof(*(ht).items) *_hi = &(ht).items[i];	\
			while( _hi->next != NULL ) {			\
				_t = _hi;				\
				_hi = _hi->next;			\
				free(_t);				\
			}						\
		}							\
		free((ht).items);					\
		free((ht).keys.items);					\
	} while(0)

#define HT_DESTROY(ht)		\
	_HT_DESTROY(ht, UNIQUE_NAME(_t), UNIQUE_NAME(_hi))


#define _HT_INC_CAP(ht, _ht, _it, _i, _j, _k)				\
	do {								\
		typeof((ht)) _ht = {0};				\
		HT_CREATE(_ht, (ht).cap*2);				\
		for ( size_t _i = 0; _i < (ht).keys.size; ++_i ) {	\
			uint64_t _k = (ht).keys.items[_i];		\
			typeof(*(ht).items) _hi = (ht).items[_k % (ht).cap]; \
			uint64_t _j = 0;				\
			while( _hi.key != _k) {			\
				_hi = (ht).items[(_k + ++_j) % (ht).cap]; \
			}						\
			typeof(*_ht.items) *_it = &_ht.items[_hi.key	\
							     % _ht.cap]; \
			_j = _hi.key;					\
			while ( _it->key != 0 && _it->key != _hi.key ) { \
				_it = &_ht.items[(++_j) % _ht.cap];	\
				++_ht.collisions;			\
			}						\
			DA_APPEND(_ht.keys, _hi.key);			\
			_it->key_str.data = _hi.key_str.data;		\
			_it->key_str.size = _hi.key_str.size;		\
			_it->key = _hi.key;				\
			_it->data = _hi.data;				\
			_it->next = NULL;				\
			++_ht.size;					\
		}							\
		HT_DESTROY(ht);					\
		(ht) = _ht;						\
	} while(0)

#define HT_INC_CAP(ht)						\
	_HT_INC_CAP(ht, UNIQUE_NAME(_ht), UNIQUE_NAME(_it),	\
		    UNIQUE_NAME(_i), UNIQUE_NAME(_j), UNIQUE_NAME(_k))

#include <stdio.h>
#define _HT_SET(ht, _key, _key_size, val, _k, _it, _i)			\
	do {								\
		if ( (ht).size + 1 >= (ht).cap ) { \
			HT_INC_CAP(ht);				\
		}							\
		uint64_t _k = (ht).hash((_key), (_key_size));		\
		typeof(*(ht).items) *_it = &(ht).items[_k % (ht).cap];	\
		uint64_t _i = _k;					\
		while ( _it->key != 0 && _it->key != _k ) {		\
			_it = &(ht).items[(++_i) % (ht).cap];		\
			++(ht).collisions;				\
		}							\
		if ( _it->key == _k ) {				\
			_it->data = val;				\
			break;						\
		}							\
		DA_APPEND((ht).keys, _k);				\
		_it->key_str.data = _key;				\
		_it->key_str.size = _key_size;				\
		_it->key = _k;						\
		_it->data = val;					\
		_it->next = NULL;					\
		++(ht).size;						\
	} while(0)

#define HT_SET(ht, key, key_size, val)					\
	_HT_SET(ht, key, key_size, val,				\
		UNIQUE_NAME(_k), UNIQUE_NAME(_it), UNIQUE_NAME(_i))

#define _HT_GET(ht, _key, _key_size, ret, _k, _it)			\
	do {								\
		uint64_t _k = (ht).hash((_key), (_key_size));		\
		typeof(*(ht).items) *_it = &(ht).items[_k % (ht).cap];	\
		(ret) = _it->data;					\
	} while(0)

#define HT_GET(ht, key, key_size, ret)					\
	_HT_GET(ht, key, key_size, ret, UNIQUE_NAME(_k), UNIQUE_NAME(_it))

#if defined(HT_IMP) || defined(IMP)

uint64_t
ht_default_hash(const char *str, size_t str_size)
{
	uint64_t k = (uint64_t)((char)str[0]) << 56;
	k |= (((uint64_t) (str[1 * (str_size > 1)])) << 48);
	k |= (((uint64_t) (str[2 * (str_size > 2)])) << 40);
	k |= (((uint64_t) (str[3 * (str_size > 3)])) << 32);
	k |= (((uint64_t) (str[(str_size-4) * (str_size >= 4)])) <<  24);
	k |= (((uint64_t) (str[(str_size-3) * (str_size >= 3)])) <<  16);
	k |= (((uint64_t) (str[(str_size-2) * (str_size >= 2)])) <<  8);
	k |= (((uint64_t) (str[(str_size-1) * (str_size >= 1)])) <<  0);
	return k + ((uint64_t)str[4 * (str_size > 4)] * 31)
		 + ((uint64_t)str[(str_size-5) * (str_size >= 5)] * 13)
		+ ((uint64_t)str[str_size/2] * 41);
	/* static uint8_t _primes_list[] = { */
	/* 	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, */
	/* 	61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, */
	/* 	131, 137, 139, 149, 151, 157, 163, 167, 173 */
	/* }; */
	/* static uint8_t _primes_list_size = 8; */
	/* uint64_t max = UINT64_MAX >> 1; */
	/* uint64_t ret = 1; */
	/* uint8_t p = 0; */
	/* size_t i = 0; */
	/* uint8_t b = 0; */

	/* for ( i = 0; i < str_size; ++i ) { */
	/* 	b = (uint8_t)str[i]; */
	/* 	p = _primes_list[(i + b) & _primes_list_size]; */
	/* 	ret = (ret * (b * p)) % max; */
	/* } */

	/* return ret; */
}


#endif /* defined(HT_IMP) || defined(IMP) */

#undef CONCAT
#undef CONCAT_INNER
#undef UNIQUE_NAME

#endif