test/abc/ab_map.c

/***************************************************************************
 * 
 * 通用代码
 * Map implements
 * 
 * HashMap
 * TreeMap
 *
 * Author		: Li Bo Feng
 * 
 * Update History
 *	DATE		OWNER			DESCRIPTION
 *	-----------	------------	-----------
 *  2010-01-19	Li Bo Feng		Generated
 *
 ***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include "ab_map.h"

//#define _DEBUG
#define STRING_BUFFER_SIZE 	1024

#ifdef _DEBUG
#define debug(args) printf args ; fflush(stdout);
#endif
#ifndef _DEBUG
#define debug(args) {}
#endif

#ifndef NULL
#define NULL 0
#endif

#define MT_HashMap		'H'
#define MT_TreeMap		'T'

#define MVT_Pointer		'P'
#define MVT_Map			'M'
#define MVT_Bytes		'B'
#define MVT_String		'S'
#define MVT_Long		'L'
#define MVT_Double		'D'

typedef void* METHOD;

typedef struct _map
{
	char id[9];
	int type;
	//
	METHOD before_remove_entry;
	METHOD after_put_entry;
	//
	MapEntry items_head;
	MapEntry items_tail;
	int items_size;
	//
	char string_buffer[STRING_BUFFER_SIZE];
}*Map;

#define HASH_TABLE_INITIAL_CAPACITY 	16
#define HASH_TABLE_MAXIMUM_CAPACITY 	1 << 30
#define HASH_TABLE_LOAD_FACTOR 			0.75f

typedef struct _hashmap_entry
{
	struct _map_entry _;
	int hash;
	struct _hashmap_entry *hme_next;
}*HashMapEntry;

struct _hashmap;

typedef struct _hashmap_hashing
{
	int table_size;
	int threshold;
	HashMapEntry *table;
}*Hashing;

typedef struct _hashmap
{
	struct _map _;
	//
	Hashing hashing;
}*HashMap;

typedef struct _treemap_entry
{
	struct _map_entry _;
	//
	struct _treemap_entry* parent;
	struct _treemap_entry* left;
	struct _treemap_entry* right;
	int color;
}*TreeMapEntry;

typedef struct _treemap
{
	struct _map _;
	//
	TreeMapEntry items_root;
}*TreeMap;

///////////////////////////////////////////////////////////////////////////////////////
// predefine
///////////////////////////////////////////////////////////////////////////////////////
void* hm_get(HashMap map, char *key);
void* tm_get(TreeMap map, char *key);
MapEntry hm_put(HashMap map, char *key, void *value, int copy_value_length, char value_type);
MapEntry tm_put(TreeMap map, char *key, void *value, int copy_value_length, char value_type);
void* hm_remove(HashMap map, char *key);
void* tm_remove(TreeMap map, char *key);
int m_build_string(Map m, char *buf, int bufsize);

///////////////////////////////////////////////////////////////////////////////////////
// memory alloc info
///////////////////////////////////////////////////////////////////////////////////////
static int b_mc_flag = -1;
static HashMap mem_map = 0;
static long total_malloc = 0;
int mc_flag()
{
	if (b_mc_flag == -1)
	{
		char* mc = getenv("MEMORY_CHECK");
		b_mc_flag = mc ? atoi(mc) : 0;
		if (b_mc_flag < 0)
		{
			b_mc_flag = 0;
		}
	}
	return b_mc_flag;
}

void mc_print_stdout(long tmc, char *info, char* file, int line)
{
	printf("malloc %ld, %s (%s,%d)\r\n", tmc, info, file, line);
	fflush(stdout);
}

mc_print_function mc_print = mc_print_stdout;

void _mc_print(char* file, int line)
{
	m_build_string(((Map) mem_map), ((Map) mem_map)->string_buffer,
			sizeof(((Map) mem_map)->string_buffer));
	mc_print(total_malloc, ((Map) mem_map)->string_buffer, file, line);
}

void* mc_malloc(int n, char* file, int line)
{
	if (mc_flag() == 0)
	{
		return malloc(n);
	}
	if (mem_map == 0)
	{
		mem_map = (HashMap) new_mapping();
	}
	void* p = malloc(n);
	total_malloc += n;
	char pk[33];
	sprintf(pk, "%lX", (long) p);
	long v = n;
	hm_put(mem_map, pk, &v, sizeof(long), MVT_Long);
	_mc_print(file, line);
	return p;
}

void mc_free(void* p, char* file, int line)
{
	if (mc_flag() == 0)
	{
		free(p);
		return;
	}
	long n = -1;
	if (p)
	{
		char pk[33];
		sprintf(pk, "%lX", (long) p);
		long *pn = (long*) hm_get(mem_map, pk);
		if (pn != 0)
		{
			n = *pn;
			hm_remove(mem_map, pk);
		}
	}
	if (n >= 0)
	{
		total_malloc -= n;
		free(p);
	}
	_mc_print(file, line);
}

///////////////////////////////////////////////////////////////////////////////////////
// global map define
///////////////////////////////////////////////////////////////////////////////////////

static int id = 0;
static HashMap global_map = NULL;

///////////////////////////////////////////////////////////////////////////////////////
// map entry
///////////////////////////////////////////////////////////////////////////////////////

MapEntry m_new_entry(Map m, MapEntry prev, MapEntry next, size_t mesize, char *key, void *value,
		int copy_value_length, char value_type)
{
	size_t meksize = strlen(key);
	int entry_size = mesize + meksize + 1;
	MapEntry e = (MapEntry) malloc(entry_size);
	memset(e, 0, entry_size);
	e->entry_size = entry_size;
	e->key = (char*) ((char*) e + mesize);
	strcpy(e->key, key);
	e->copy_value_length = copy_value_length;
	e->value_type = value_type;
	if (copy_value_length >= 0)
	{
		e->value = malloc(copy_value_length + 1);
		if (copy_value_length > 0)
		{
			memcpy(e->value, value, copy_value_length);
		}
		memset(e->value + copy_value_length, 0, 1);
	}
	else
	{
		e->value = value;
	}
	e->next = next;
	e->prev = prev;
	if (prev)
	{
		prev->next = e;
	}
	else
	{
		m->items_head = e;
	}
	if (next)
	{
		next->prev = e;
	}
	else
	{
		m->items_tail = e;
	}
	m->items_size++;
	m->string_buffer[0] = 0;
	debug(("m_new_entry %lX %s\r\n", (long)e, e->key));
	return e;
}

void m_replace_entry_value(MapEntry entry, void* value, int copy_value_length, char value_type)
{
	if (copy_value_length > 0 && entry->copy_value_length == copy_value_length)
	{
		memcpy(entry->value, value, entry->copy_value_length);
	}
	else
	{
		if (entry->copy_value_length > 0)
		{
			free(entry->value);
		}
		entry->copy_value_length = copy_value_length;
		if (copy_value_length > 0)
		{
			entry->value = malloc(copy_value_length + 1);
			memcpy(entry->value, value, copy_value_length);
			memset(entry->value + copy_value_length, 0, 1);
		}
		else
		{
			entry->value = value;
		}
	}
	entry->value_type = value_type;
}
void m_delete_entry(Map m, MapEntry e)
{
	debug(("hm_delete_entry %lX %s\r\n", (long)e, e->key));
	if (m)
	{
		if (m->before_remove_entry != NULL)
		{
			((event_map_entry) m->before_remove_entry)((long) m, e->key, e->value);
		}
		if (e->next)
		{
			e->next->prev = e->prev;
		}
		else
		{
			m->items_tail = e->prev;
		}
		if (e->prev)
		{
			e->prev->next = e->next;
		}
		else
		{
			m->items_head = e->next;
		}
		m->items_size--;
		m->string_buffer[0] = 0;
	}
	else
	{
		// it's lonely entry, hashing has been seperate from map.
	}
	if (e->copy_value_length > 0)
	{
		free(e->value);
	}
	free(e);
}

///////////////////////////////////////////////////////////////////////////////////////
// new/delete  map
///////////////////////////////////////////////////////////////////////////////////////

Map m_new_map(size_t map_struct_size, int id, event_map_entry before_remove_entry,
		event_map_entry after_put_entry)
{
	debug(("m_new_map entry\r\n"));
	Map m = (Map) malloc(map_struct_size);
	memset(m, 0, map_struct_size);
	snprintf(m->id, 8, "%X", id);
	m->before_remove_entry = (METHOD) before_remove_entry;
	m->after_put_entry = (METHOD) after_put_entry;
	return m;
}

void m_delete_map(Map m)
{
	free(m);
}

///////////////////////////////////////////////////////////////////////////////////////
// map to string
///////////////////////////////////////////////////////////////////////////////////////
int m_build_string(Map m, char *buf, int bufsize);

int m_me_value_string(MapEntry me, char *buf, int bufsize)
{
	if (me->value_type == MVT_Map)
	{
		Map submap;
		if (me->copy_value_length >= 0)
		{
			long pm = *(long*) me->value;
			submap = (Map) pm;
		}
		else
		{
			submap = (Map) me->value;
		}
		int rc = m_build_string(submap, buf, bufsize - 2);
		strcat(buf, ", ");
		return rc + 2;
	}
	else
	{
		char sbv[STRING_BUFFER_SIZE];
		int sbvsize = sizeof(sbv);
		switch (me->value_type)
		{
		case MVT_String:
			snprintf(sbv, sbvsize, "%s", (char*) me->value);
			break;
		case MVT_Long:
			snprintf(sbv, sbvsize, "%ld", *(long*) me->value);
			break;
		case MVT_Double:
			snprintf(sbv, sbvsize, "%lf", *(double*) me->value);
			break;
		default:
			snprintf(sbv, sbvsize, "H%lX", (long) me->value);
			break;
		}
		if (strlen(sbv) < bufsize - 2)
		{
			strcpy(buf, sbv);
			strcat(buf, ", ");
			return strlen(buf);
		}
		else
		{
			strncpy(buf, sbv, bufsize - 5);
			strcat(buf + bufsize - 5, "..., ");
			return bufsize;
		}
	}
	return 0;
}

int m_me_string(MapEntry me, char *buf, int bufsize)
{
	if (strlen(me->key) + 5 < bufsize)
	{
		sprintf(buf, "%s:", me->key);
		int nk = strlen(buf);
		buf += nk;
		bufsize -= nk;
		int nv = m_me_value_string(me, buf, bufsize);
		if (nv < 0)
		{
			return nv;
		}
		return nk + nv;
	}
	else
	{
		return -1;
	}
}

int m_map_string(Map m, char *buf, int bufsize)
{
	int bi = 0;
	int rc = 0;
	MapEntry e;
	e = m->items_head;
	while (e)
	{
		rc = m_me_string(e, buf + bi, bufsize - bi);
		if (rc < 0)
		{
			return rc;
		}
		bi += rc;
		e = e->next;
	}
	return bi;
}

int m_build_string(Map m, char *buf, int bufsize)
{
	memset(buf, 0, bufsize);
	strcat(buf, "{");
	int rc = m_map_string(m, buf + 1, bufsize - 5);
	if (rc < 0)
	{
		strcat(buf, "...");
	}
	else if (rc > 1)
	{
		// cut off the tail ", "
		buf[rc - 1] = 0;
		buf[rc] = 0;
	}
	strcat(buf, "}");
	return strlen(buf);
}

///////////////////////////////////////////////////////////////////////////////////////
// tree map new/delete/get/put/remove
///////////////////////////////////////////////////////////////////////////////////////
TreeMap tm_new_map(int id, event_map_entry before_remove_entry, event_map_entry after_put_entry)
{
	TreeMap m = (TreeMap) m_new_map(sizeof(struct _treemap), id, before_remove_entry,
			after_put_entry);
	((Map) m)->type = MT_TreeMap;
	m->items_root = NULL;
	return m;
}

void tm_delete_map(TreeMap m)
{
	debug(("tm_delete_map entry %lX\r\n", (long)m));
	MapEntry me = ((Map) m)->items_head;
	while (me)
	{
		MapEntry nme = me->next;
		// delete directly, do without rebalance.
		m_delete_entry(((Map) m), me);
		me = nme;
	}
	m_delete_map((Map) m);
}

TreeMapEntry tm_new_entry(TreeMap m, MapEntry prev, MapEntry next, char *key, void *value,
		int copy_value_length, char value_type)
{
	TreeMapEntry hme = (TreeMapEntry) m_new_entry((Map) m, (MapEntry) prev, (MapEntry) next,
			sizeof(struct _treemap_entry), key, value, copy_value_length, value_type);
	return hme;
}

void tm_right_rotate(TreeMap tm, TreeMapEntry x)
{
	TreeMapEntry y = x->left;
	x->left = y->right;
	if (y->right != NULL)
	{
		y->right->parent = x;
	}
	y->parent = x->parent;
	if (x->parent == NULL)
	{
		tm->items_root = y;
	}
	else
	{
		if (x == x->parent->right)
		{
			x->parent->right = y;
		}
		else
		{
			x->parent->left = y;
		}
	}
	y->right = x;
	x->parent = y;
}

void tm_left_rotate(TreeMap tm, TreeMapEntry x)
{
	TreeMapEntry y = x->right;
	x->right = y->left;
	if (y->left != NULL)
	{
		y->left->parent = x;
	}
	y->parent = x->parent;
	if (x->parent == NULL)
	{
		tm->items_root = y;
	}
	else
	{
		if (x == x->parent->left)
		{
			x->parent->left = y;
		}
		else
		{
			x->parent->right = y;
		}
	}
	y->left = x;
	x->parent = y;
}

void tm_balance(TreeMap tm, TreeMapEntry x)
{
	TreeMapEntry y;
	x->color = 1;
	while (x != tm->items_root && x->parent->color)
	{
		if (x->parent == x->parent->parent->left)
		{
			y = x->parent->parent->right;
			if (y != NULL && y->color)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;
			}
			else
			{
				if (x == x->parent->right)
				{
					x = x->parent;
					tm_left_rotate(tm, x);
				}
				x->parent->color = 0;
				x->parent->parent->color = 1;
				tm_right_rotate(tm, x->parent->parent);
			}
		}
		else
		{
			y = x->parent->parent->left;
			if (y != NULL && y->color)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;
			}
			else
			{
				if (x == x->parent->left)
				{
					x = x->parent;
					tm_right_rotate(tm, x);
				}
				x->parent->color = 0;
				x->parent->parent->color = 1;
				tm_left_rotate(tm, x->parent->parent);
			}
		}
	}
	tm->items_root->color = 0;
}

void tm_fixup(TreeMap tm, TreeMapEntry x)
{
	TreeMapEntry w;
	while (x != tm->items_root && !x->color)
	{
		if (x == x->parent->left)
		{
			w = x->parent->right;
			if (w == NULL)
			{
				x = x->parent;
				continue;
			}
			if (w->color)
			{
				w->color = 0;
				x->parent->color = 1;
				tm_left_rotate(tm, x->parent);
				w = x->parent->right;
				if (w == NULL)
				{
					x = x->parent;
					continue;
				}
			}
			if ((w->left == NULL || !w->left->color) && (w->right == NULL || !w->right->color))
			{
				w->color = 1;
				x = x->parent;
			}
			else
			{
				if (w->right == NULL || !w->right->color)
				{
					w->left->color = 0;
					w->color = 1;
					tm_right_rotate(tm, w);
					w = x->parent->right;
				}
				w->color = x->parent->color;
				x->parent->color = 0;
				w->right->color = 0;
				tm_left_rotate(tm, x->parent);
				x = tm->items_root;
			}
		}
		else
		{
			w = x->parent->left;
			if (w == NULL)
			{
				x = x->parent;
				continue;
			}
			if (w->color)
			{
				w->color = 0;
				x->parent->color = 1;
				tm_right_rotate(tm, x->parent);
				w = x->parent->left;
				if (w == NULL)
				{
					x = x->parent;
					continue;
				}
			}
			if ((w->left == NULL || !w->left->color) && (w->right == NULL || !w->right->color))
			{
				w->color = 1;
				x = x->parent;
			}
			else
			{
				if (w->left == NULL || !w->left->color)
				{
					w->right->color = 0;
					w->color = 1;
					tm_left_rotate(tm, w);
					w = x->parent->left;
				}
				w->color = x->parent->color;
				x->parent->color = 0;
				w->left->color = 0;
				tm_right_rotate(tm, x->parent);
				x = tm->items_root;
			}
		}
	}
	x->color = 0;
}

void tm_attach_to_parent_no_fixup(TreeMap tm, TreeMapEntry toDelete, TreeMapEntry toConnect)
{
// assert toConnect!=NULL
	TreeMapEntry parent = toDelete->parent;
	toConnect->parent = parent;
	if (parent == NULL)
	{
		tm->items_root = toConnect;
	}
	else if (toDelete == parent->left)
	{
		parent->left = toConnect;
	}
	else
	{
		parent->right = toConnect;
	}
}

void tm_attach_to_parent(TreeMap tm, TreeMapEntry toDelete, TreeMapEntry toConnect)
{
// assert toConnect!=NULL
	tm_attach_to_parent_no_fixup(tm, toDelete, toConnect);
	if (!toDelete->color)
	{
		tm_fixup(tm, toConnect);
	}
}

void tm_attach_null_to_parent(TreeMap tm, TreeMapEntry toDelete)
{
	TreeMapEntry parent = toDelete->parent;
	if (parent == NULL)
	{
		tm->items_root = NULL;
	}
	else
	{
		if (toDelete == parent->left)
		{
			parent->left = NULL;
		}
		else
		{
			parent->right = NULL;
		}
		if (!toDelete->color)
		{
			tm_fixup(tm, parent);
		}
	}
}

void tm_delete_entry(TreeMap tm, TreeMapEntry tme)
{
	if (tme->right == NULL)
	{
		if (tme->left != NULL)
		{
			tm_attach_to_parent(tm, tme, tme->left);
		}
		else
		{
			tm_attach_null_to_parent(tm, tme);
		}
	}
	else if (tme->left == NULL)
	{
		// tme->right != NULL
		tm_attach_to_parent(tm, tme, tme->right);
	}
	else
	{
		// Here tme->left!=nul && tme->right!=NULL
		// tme->next should replace tme in tree
		// tme->next!=NULL by tree logic.
		// tme->next->left==NULL by tree logic.
		// tme->next->right may be NULL or non-NULL
		TreeMapEntry toMoveUp = (TreeMapEntry) ((MapEntry) tme)->next;
		if (toMoveUp->right == NULL)
		{
			tm_attach_null_to_parent(tm, toMoveUp);
		}
		else
		{
			tm_attach_to_parent(tm, toMoveUp, toMoveUp->right);
		}
		// Here toMoveUp is ready to replace tme
		toMoveUp->left = tme->left;
		if (tme->left != NULL)
		{
			tme->left->parent = toMoveUp;
		}
		toMoveUp->right = tme->right;
		if (tme->right != NULL)
		{
			tme->right->parent = toMoveUp;
		}
		tm_attach_to_parent_no_fixup(tm, tme, toMoveUp);
		toMoveUp->color = tme->color;
	}
	m_delete_entry((Map) tm, (MapEntry) tme);
}

TreeMapEntry tm_put_entry(TreeMap tm, char *key, void *value, int copy_value_length,
		char value_type)
{
	int cmp;
	TreeMapEntry ntme;
	TreeMapEntry ptme = NULL;
	TreeMapEntry tme = tm->items_root;
	if (tme == NULL)
	{
		ntme = (TreeMapEntry) tm_new_entry(tm, NULL, NULL, key, value, copy_value_length,
				value_type);
		tm->items_root = ntme;
		return ntme;
	}
	while (tme != NULL)
	{
		cmp = strcmp(key, ((MapEntry) tme)->key);
		if (cmp == 0)
		{
			return tme;
		}
		if (cmp < 0)
		{
			ptme = tme;
			tme = ptme->left;
			if (tme == NULL)
			{
				ntme = (TreeMapEntry) tm_new_entry(tm, ((MapEntry) ptme)->prev, ((MapEntry) ptme),
						key, value, copy_value_length, value_type);
				ptme->left = ntme;
				ntme->parent = ptme;
			}
		}
		else
		{
			ptme = tme;
			tme = tme->right;
			if (tme == NULL)
			{
				ntme = (TreeMapEntry) tm_new_entry(tm, ((MapEntry) ptme), ((MapEntry) ptme)->next,
						key, value, copy_value_length, value_type);
				ptme->right = ntme;
				ntme->parent = ptme;
			}
		}
	}
	tm_balance(tm, ntme);
	return ntme;
}

MapEntry tm_put(TreeMap tm, char *key, void *value, int copy_value_length, char value_type)
{
#ifdef _DEBUG
	{
		m_build_string((Map) tm, ((Map) tm)->string_buffer, sizeof(((Map) tm)->string_buffer));
		debug(("tm_put %s into %s\r\n", key, ((Map)tm)->string_buffer));
	}
#endif
	int n = ((Map) tm)->items_size;
	TreeMapEntry tme = (TreeMapEntry) tm_put_entry(tm, key, value, copy_value_length, value_type);
	if (n == ((Map) tm)->items_size)
	{
		if (((Map) tm)->before_remove_entry)
		{
			((event_map_entry) ((Map) tm)->before_remove_entry)(((long) tm), ((MapEntry) tme)->key,
					((MapEntry) tme)->value);
		}
		m_replace_entry_value((MapEntry) tme, value, copy_value_length, value_type);
		if (((Map) tm)->after_put_entry)
		{
			((event_map_entry) ((Map) tm)->after_put_entry)(((long) tm), ((MapEntry) tme)->key,
					((MapEntry) tme)->value);
		}
		debug(("tm_put returned exsiting entry %lX\r\n", (long)tme));
	}
	else
	{
		if (((Map) tm)->after_put_entry)
		{
			((event_map_entry) ((Map) tm)->after_put_entry)(((long) tm), ((MapEntry) tme)->key,
					((MapEntry) tme)->value);
		}
		debug(("tm_put returned new entry %lX\r\n", (long)tme));
	}
	return ((MapEntry) tme);
}

TreeMapEntry tm_get_entry(TreeMap tm, char *key)
{
	int cmp;
	TreeMapEntry tme = tm->items_root;
	while (tme != NULL)
	{
		cmp = strcmp(key, ((MapEntry) tme)->key);
		if (cmp == 0)
		{
			return tme;
		}
		if (cmp < 0)
		{
			tme = tme->left;
		}
		else
		{
			tme = tme->right;
		}
	}
	return NULL;
}

TreeMapEntry tm_get_nearby_entry(TreeMap tm, char *key)
{
	int cmp;
	TreeMapEntry tme = tm->items_root;
	TreeMapEntry rtme = tme;
	while (tme != NULL)
	{
		cmp = strcmp(key, ((MapEntry) tme)->key);
		if (cmp == 0)
		{
			return tme;
		}
		if (cmp < 0)
		{
			rtme = (TreeMapEntry) ((MapEntry) tme)->prev;
			tme = tme->left;
		}
		else
		{
			rtme = tme;
			tme = tme->right;
		}
	}
	return rtme;
}

void* tm_get(TreeMap map, char *key)
{
	TreeMapEntry tme = tm_get_entry(map, key);
	void*value = NULL;
	if (tme)
	{
		value = ((MapEntry) tme)->value;
	}
	return value;
}

void* tm_remove(TreeMap map, char *key)
{
	TreeMapEntry tme = tm_get_entry(map, key);
	void*value = NULL;
	if (tme)
	{
		if (((MapEntry) tme)->copy_value_length < 0)
		{
			value = ((MapEntry) tme)->value;
		}
		tm_delete_entry(map, tme);
	}
	return value;
}

void tm_put_all_map(TreeMap dest, Map src)
{
	MapEntry me = src->items_head;
	while (me)
	{
		tm_put(dest, me->key, me->value, me->copy_value_length, me->value_type);
		me = me->next;
	}
}

///////////////////////////////////////////////////////////////////////////////////////
// hash calculate method define
///////////////////////////////////////////////////////////////////////////////////////

int hash(char* key)
{
	char c;
	int h = 0;
	while ((c = *key++) != 0)
	{
		h = 31 * h + (unsigned int) c;
	}
	return h ^ (h << 20) ^ (h << 12) ^ (h << 7) ^ (h << 4);
}

///////////////////////////////////////////////////////////////////////////////////////
// hash map hashing
///////////////////////////////////////////////////////////////////////////////////////

Hashing hm_new_hashing(int table_size)
{
	int hashing_bytes_size = sizeof(struct _hashmap_hashing)
			+ (sizeof(HashMapEntry *)) * table_size;
	Hashing m = (Hashing) malloc(hashing_bytes_size);
	memset(m, 0, hashing_bytes_size);
	m->table = (HashMapEntry*) (((char*) m) + sizeof(struct _hashmap_hashing));
	m->table_size = table_size;
	m->threshold = table_size * HASH_TABLE_LOAD_FACTOR;
	return m;
}

void hm_delete_hashing(Hashing hashing)
{
	free(hashing);
}

///////////////////////////////////////////////////////////////////////////////////////
// hash map new/delete/get/put/remove
///////////////////////////////////////////////////////////////////////////////////////
HashMap hm_new_map(int id, event_map_entry before_remove_entry, event_map_entry after_put_entry)
{
	HashMap m = (HashMap) m_new_map(sizeof(struct _hashmap), id, before_remove_entry,
			after_put_entry);
	((Map) m)->type = MT_HashMap;
	m->hashing = hm_new_hashing(HASH_TABLE_INITIAL_CAPACITY);
	return m;
}

void hm_increase_capacity(HashMap m)
{
	Hashing old_hashing = m->hashing;
	int new_size = old_hashing->table_size << 1;
	if (new_size >= HASH_TABLE_MAXIMUM_CAPACITY)
	{
		new_size = HASH_TABLE_MAXIMUM_CAPACITY;
		old_hashing->threshold = (int) (((unsigned int) (1) << 31) - 1); // MAX_INTEGER
		return;
	}
	debug(("hm_increase_capacity %d\r\n", new_size));
	m->hashing = hm_new_hashing(new_size);
	// transfer entries
	HashMapEntry *old_table = old_hashing->table;
	HashMapEntry *new_table = m->hashing->table;
	int j;
	for (j = 0; j < old_hashing->table_size; j++)
	{
		HashMapEntry hme = old_table[j];
		while (hme)
		{
			HashMapEntry next = hme->hme_next;
			int i = hme->hash & (new_size - 1);
			hme->hme_next = new_table[i];
			new_table[i] = hme;
			hme = next;
		}
	}
	hm_delete_hashing(old_hashing);
}

void hm_delete_map(HashMap m)
{
	debug(("hm_delete_map entry %lX\r\n", (long)m));
	HashMapEntry *table = m->hashing->table;
	int table_size = m->hashing->table_size;
	int j;
	for (j = 0; j < table_size; j++)
	{
		HashMapEntry hme = table[j];
		while (hme)
		{
			HashMapEntry next = hme->hme_next;
			m_delete_entry((Map) m, (MapEntry) hme);
			hme = next;
		}
	}
	hm_delete_hashing(m->hashing);
	m_delete_map((Map) m);
}

HashMapEntry hm_new_entry(HashMap map, int h, int table_index, char *key, void *value,
		int copy_value_length, char value_type)
{
	HashMapEntry hme = (HashMapEntry) m_new_entry(((Map) map), ((Map) map)->items_tail, NULL,
			sizeof(struct _hashmap_entry), key, value, copy_value_length, value_type);
	HashMapEntry next = map->hashing->table[table_index];
	hme->hash = h;
	hme->hme_next = next;
	map->hashing->table[table_index] = hme;
	if (((Map) map)->items_size >= map->hashing->threshold)
	{
		hm_increase_capacity(map);
	}
	debug(("hm new entry key %s, %016X, %d\r\n", key, h, table_index));
	return hme;
}

HashMapEntry hm_get_entry(Hashing hashing, int h, int table_index, char*key)
{
	debug(("find key %s, %016X, %d\r\n", key, h, table_index));
	HashMapEntry hme = hashing->table[table_index];
#ifdef _DEBUG
	int i = 0;
#endif
	for (; hme; hme = hme->hme_next)
	{
		debug(("find key %s\r\n", key));
		if (hme->hash == h && strcmp(((MapEntry) hme)->key, key) == 0)
		{
			debug( ("found key %s, hash %016X, index %d, no %d\r\n", key, h, table_index, i));
			return hme;
		}
#ifdef _DEBUG
		i++;
#endif
	}
	return NULL;
}

MapEntry hm_put(HashMap map, char *key, void *value, int copy_value_length, char value_type)
{
#ifdef _DEBUG
	{
		m_build_string((Map) map, ((Map) map)->string_buffer, sizeof(((Map) map)->string_buffer));
		debug(("hm_put %s into %s\r\n", key, ((Map)map)->string_buffer));
	}
#endif
	int h = hash(key);
	int table_index = h & (map->hashing->table_size - 1);
	debug(("hash %s ==> %016X, %d\r\n", key, h, table_index));
	HashMapEntry entry = hm_get_entry(map->hashing, h, table_index, key);
	if (entry)
	{
		if (((Map) map)->before_remove_entry)
		{
			((event_map_entry) ((Map) map)->before_remove_entry)(((long) map),
					((MapEntry) entry)->key, ((MapEntry) entry)->value);
		}
		m_replace_entry_value((MapEntry) entry, value, copy_value_length, value_type);
		if (((Map) map)->after_put_entry)
		{
			((event_map_entry) ((Map) map)->after_put_entry)(((long) map), ((MapEntry) entry)->key,
					((MapEntry) entry)->value);
		}
		debug(("hm_put returned exsiting entry %lX\r\n", (long)entry));
		return (MapEntry) entry;
	}
	entry = hm_new_entry(map, h, table_index, key, value, copy_value_length, value_type);
	if (((Map) map)->after_put_entry)
	{
		((event_map_entry) ((Map) map)->after_put_entry)(((long) map), ((MapEntry) entry)->key,
				((MapEntry) entry)->value);
	}
	debug(("hm_put returned new entry %lX\r\n", (long)entry));
	return (MapEntry) entry;
}

void* hm_get(HashMap map, char *key)
{
#ifdef _DEBUG
	{
		debug(("hm_get %s from %lX\r\n", key, (long)map));
		m_build_string(((Map) map), ((Map) map)->string_buffer, sizeof(((Map) map)->string_buffer));
		debug(("hm_get %s from %s\r\n", key, ((Map)map)->string_buffer));
	}
#endif
	int h = hash(key);
	Hashing hashing = map->hashing;
	int table_index = h & (hashing->table_size - 1);
	debug(("hash %s ==> %016X, %d\r\n", key, h, table_index));
	HashMapEntry entry = hm_get_entry(hashing, h, table_index, key);
	if (entry)
	{
		return ((MapEntry) entry)->value;
	}
	return NULL;
}

void* hm_remove(HashMap map, char *key)
{
#ifdef _DEBUG
	{
		m_build_string(((Map) map), ((Map) map)->string_buffer, sizeof(((Map) map)->string_buffer));
		debug(("hm_remove %s from %s\r\n", key, ((Map)map)->string_buffer));
	}
#endif
	int h = hash(key);
	int table_index = h & (map->hashing->table_size - 1);
	debug(("hash %s ==> %016X, %d\r\n", key, h, table_index));
	HashMapEntry prev = NULL;
	HashMapEntry hme = map->hashing->table[table_index];
	while (hme)
	{
		if (hme->hash == h && strcmp(((MapEntry) hme)->key, key) == 0)
		{
			void* value =
					(((MapEntry) hme)->copy_value_length >= 0) ? NULL : ((MapEntry) hme)->value;
			if (prev)
			{
				prev->hme_next = hme->hme_next;
			}
			else
			{
				map->hashing->table[table_index] = hme->hme_next;
			}
			m_delete_entry((Map) map, (MapEntry) hme);
			return value;
		}
		prev = hme;
		hme = hme->hme_next;
	}
	return NULL;
}

void hm_put_all_map(HashMap dest, Map src)
{
	MapEntry me = src->items_head;
	while (me)
	{
		hm_put(dest, me->key, me->value, me->copy_value_length, me->value_type);
		me = me->next;
	}
}

///////////////////////////////////////////////////////////////////////////////////////
// map event define
///////////////////////////////////////////////////////////////////////////////////////
int on_before_delete_mapping(long mapid, char*key, void*value)
{
	debug(("on_before_delete_mapping %s\r\n", key));
	if (mapid == ((long) global_map))
	{
		Map map = (Map) value;
		if (map->type == MT_HashMap)
		{
			hm_delete_map((HashMap) map);
		}
		else if (map->type == MT_TreeMap)
		{
			tm_delete_map((TreeMap) map);
		}
		else
		{
		}
	}
	return 0;
}

int on_after_new_mapping(long mapid, char*key, void*value)
{
	debug(("on_after_new_mapping %s\r\n", key));
	return 0;
}

int on_before_remove_entry(long mapid, char*key, void*value)
{
	debug(("on_before_remove_entry %s\r\n", key));
	return 0;
}

int on_after_put_entry(long mapid, char*key, void*value)
{
	debug(("on_after_put_entry %s\r\n", key));
	return 0;
}

///////////////////////////////////////////////////////////////////////////////////////

/**
 * init mapping, it is auto called while new_mapping
 */
void init_mapping()
{
	if (global_map == NULL)
	{
		id = 0;
		global_map = hm_new_map(id++, on_before_delete_mapping, on_after_new_mapping);
	}
}

long new_mapping()
{
	if (global_map == NULL)
	{
		init_mapping();
	}
	debug(("new_mapping entry\r\n"));
	HashMap m = hm_new_map(id++, on_before_remove_entry, on_after_put_entry);
	hm_put(global_map, ((Map) m)->id, (Map) m, -1, MVT_Map);
#ifdef _DEBUG
	m_build_string(((Map) global_map), ((Map) global_map)->string_buffer,
			sizeof(((Map) global_map)->string_buffer));
	debug(("global_map map %s\r\n", ((Map)global_map)->string_buffer));
#endif
	debug(("new_mapping exit %lX\r\n", (long) m));
	return (long) m;
}

long new_sorted_mapping()
{
	if (global_map == NULL)
	{
		init_mapping();
	}
	debug(("new_sorted_mapping entry\r\n"));
	TreeMap m = tm_new_map(id++, on_before_remove_entry, on_after_put_entry);
	hm_put(global_map, ((Map) m)->id, (Map) m, -1, MVT_Map);
#ifdef _DEBUG
	m_build_string(((Map) global_map), ((Map) global_map)->string_buffer,
			sizeof(((Map) global_map)->string_buffer));
	debug(("global_map map %s\r\n", ((Map)global_map)->string_buffer));
#endif
	debug(("new_sorted_mapping exit\r\n"));
	return (long) m;
}

int is_map(Map m)
{
	debug(("is_map %lX\r\n", (long)m));
	debug(("m->id %s\r\n", m->id));
	debug(("global_map v %lX\r\n", (long)(hm_get(global_map, m->id))));
	return (hm_get(global_map, m->id) == m);
}

void _put_mapping(long mapid, char* key, void* value, int copy_value_length, char value_type)
{
	if (global_map == NULL)
	{
		return;
	}
	if (key == NULL)
	{
		return;
	}
	if (value == NULL)
	{
		copy_value_length = -1;
	}
	debug(("put_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("put_mapping m=%lX\r\n", (long)map));
	if (is_map(map))
	{
		if (map->type == MT_HashMap)
		{
			hm_put((HashMap) map, key, value, copy_value_length, value_type);
		}
		else
		{
			tm_put((TreeMap) map, key, value, copy_value_length, value_type);
		}
	}
	debug(("put_mapping exit\r\n"));
}

void put_mapping(long mapid, char* key, void* value, int copy_value_length)
{
	_put_mapping(mapid, key, value, copy_value_length,
			copy_value_length < 0 ? MVT_Pointer : MVT_Bytes);
}

void put_string_mapping(long mapid, char* key, char* value)
{
	_put_mapping(mapid, key, value, strlen(value), MVT_String);
}

void put_submap_mapping(long mapid, char* key, long value)
{
	_put_mapping(mapid, key, &value, sizeof(value), MVT_Map);
}

void put_long_mapping(long mapid, char* key, long value)
{
	_put_mapping(mapid, key, &value, sizeof(value), MVT_Long);
}

void put_double_mapping(long mapid, char* key, double value)
{
	_put_mapping(mapid, key, &value, sizeof(value), MVT_Double);
}

char* get_string_mapping(long mapid, char* key)
{
	return (char*) get_mapping(mapid, key);
}

long get_submap_mapping(long mapid, char* key)
{
	return get_long_mapping(mapid, key);
}

long get_long_mapping(long mapid, char* key)
{
	long *smid = (long*) get_mapping(mapid, key);
	if (smid)
	{
		return *smid;
	}
	return 0;
}

double get_double_mapping(long mapid, char* key)
{
	double *smid = (double*) get_mapping(mapid, key);
	if (smid)
	{
		return *smid;
	}
	return 0;
}

void* get_mapping(long mapid, char* key)
{
	if (global_map == NULL)
	{
		return NULL;
	}
	if (key == NULL)
	{
		return NULL;
	}
	debug(("get_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("get_mapping m=%lX\r\n", mapid));
	void *value = NULL;
	if (is_map(map))
	{
		debug(("get_mapping %lX is a map\r\n", mapid));
		if (map->type == MT_HashMap)
		{
			value = hm_get((HashMap) map, key);
		}
		else
		{
			value = tm_get((TreeMap) map, key);
		}
	}
	debug(("get_mapping exit\r\n"));
	return value;
}

void* remove_mapping(long mapid, char* key)
{
	if (global_map == NULL)
	{
		return NULL;
	}
	if (key == NULL)
	{
		return NULL;
	}
	debug(("remove_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("remove_mapping m=%lX\r\n", (long)map));
	void *value = NULL;
	if (is_map(map))
	{
		if (map->type == MT_HashMap)
		{
			value = hm_remove((HashMap) map, key);
		}
		else
		{
			value = tm_remove((TreeMap) map, key);
		}
	}
	debug(("remove_mapping exit\r\n"));
	return value;
}

void delete_mapping(long mapid)
{
	if (global_map == NULL)
	{
		return;
	}
	debug(("delete_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("delete_mapping m=%lX\r\n", (long)map));
	if (is_map(map))
	{
		hm_remove(global_map, map->id);
	}
#ifdef _DEBUG
	m_build_string(((Map) global_map), ((Map) global_map)->string_buffer,
			sizeof(((Map) global_map)->string_buffer));
	debug(("global_map map %s\r\n", ((Map)global_map)->string_buffer));
#endif
	debug(("delete_mapping exit\r\n"));
}

void clear_mapping()
{
	if (global_map == NULL)
	{
		return;
	}
	debug(("clear_mapping entry\r\n"));
	hm_delete_map(global_map);
	global_map = NULL;
	debug(("clear_mapping exit\r\n"));
}

MapEntry items_mapping(long mapid)
{
	if (global_map == NULL)
	{
		return NULL;
	}
	debug(("items_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("items_mapping m=%lX\r\n", (long)map));
	MapEntry value = NULL;
	if (is_map(map))
	{
		value = map->items_head;
	}
	debug(("items_mapping exit\r\n"));
	return value;
}

int size_mapping(long mapid)
{
	if (global_map == NULL)
	{
		return 0;
	}
	debug(("size_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("size_mapping m=%lX\r\n", (long)map));
	int value = 0;
	if (is_map(map))
	{
		value = map->items_size;
	}
	debug(("size_mapping exit\r\n"));
	return value;
}

MapEntry nearby_item_sorted_mapping(long mapid, char* key)
{
	if (global_map == NULL)
	{
		return NULL;
	}
	if (key == NULL)
	{
		return NULL;
	}
	debug(("nearby_item_sorted_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("nearby_item_sorted_mapping m=%lX\r\n", (long)map));
	MapEntry value = NULL;
	if (is_map(map) && map->type == MT_TreeMap)
	{
		value = (MapEntry) tm_get_nearby_entry((TreeMap) map, key);
	}
	debug(("nearby_item_sorted_mapping exit\r\n"));
	return value;
}

void put_all_mapping(long destid, long srcid)
{
	if (global_map == NULL)
	{
		return;
	}
	debug(("clone_mapping entry\r\n"));
	Map destmap = (Map) destid;
	Map srcmap = (Map) srcid;
	debug(("clone_mapping from m=%lX to m=%lX\r\n", (long)srcmap,(long)destmap));
	if (is_map(srcmap) && is_map(destmap))
	{
		if (destmap->type == MT_HashMap)
		{
			hm_put_all_map((HashMap) destmap, srcmap);
		}
		else
		{
			tm_put_all_map((TreeMap) destmap, srcmap);
		}
	}
	debug(("clone_mapping exit\r\n"));
}

char* string_mapping(long mapid)
{
	if (global_map == NULL)
	{
		return NULL;
	}
	debug(("string_mapping entry\r\n"));
	Map map = (Map) mapid;
	debug(("string_mapping m=%lX\r\n", (long)map));
	char *svalue = NULL;
	if (is_map(map))
	{
		if (map->string_buffer[0] == 0)
		{
			m_build_string(map, map->string_buffer, sizeof(map->string_buffer));
		}
		svalue = map->string_buffer;
	}
	debug(("string_mapping exit\r\n"));
	return svalue;
}

#include <time.h>
void performace_test_mapping()
{
	// referrence java testing code:
	// public static void main(String[] args)
	// {
	//		HashMap hm = new HashMap();
	//		long t = System.currentTimeMillis();
	//		for(int i = 0; i < 5000000; i++)
	//		{
	//			hm.put("K" + i, "K" + i);
	//		}
	//		System.out.println("put :" + (System.currentTimeMillis() - t));
	//		t = System.currentTimeMillis();
	//		for(int i = 0; i < 5000000; i++)
	//		{
	//			String k = "K" + i;
	//			String v = (String)hm.get(k);
	//			if (!k.equals(v))
	//			{
	//				System.out.println("??");
	//			}
	//		}
	//		System.out.println("get :" + (System.currentTimeMillis() - t));
	// }
	// java testing result:
	//   hashmap put :14601
	//   hashmap get :9268
	//   treemap put :12932
	//   treemap get :5492
	// c testing result:
	//   hashmap put :5319
	//   hashmap get :2028
	//   treemap put :5803
	//   treemap get :2839
	int i;
	char key[100];
	char value[100];
	long hmid = new_sorted_mapping();
	double t = (double) clock() / CLOCKS_PER_SEC * 1000;
	for (i = 0; i < 5000000; i++)
	{
		sprintf(key, "K%d", i);
		sprintf(value, "K%d", i);
		put_string_mapping(hmid, key, value);
	}
	printf("put :%lf\r\n", ((double) clock() / CLOCKS_PER_SEC * 1000 - t));
	t = (double) clock() / CLOCKS_PER_SEC * 1000;
	for (i = 0; i < 5000000; i++)
	{
		sprintf(key, "K%d", i);
		char* v = get_string_mapping(hmid, key);
		if (strcmp(v, key))
		{
			printf("??");
		}
	}
	printf("get :%lf\r\n", ((double) clock() / CLOCKS_PER_SEC * 1000 - t));
	clear_mapping();
}