#ifndef _MAP_C_ /* -*- linux-c -*- */
#define _MAP_C_

/** @file map.c
 * @brief Implements maps (associative arrays) and lists
 */

#include "alloc.c"
#include "sym.c"

static int map_sizes[] = {
        sizeof(int64_t),
        MAP_STRING_LENGTH,
        sizeof(stat),
        0
};

#ifdef NEED_INT64_KEYS
unsigned int int64_hash (const int64_t v)
{
	return (unsigned int)hash_long ((unsigned long)v, HASH_TABLE_BITS);
}

int int64_eq_p (int64_t key1, int64_t key2)
{
	return key1 == key2;
}
#endif /* NEED_INT64_KEYS */



#if defined (NEED_STRING_KEYS) || defined (NEED_STRING_VALS)
void str_copy(char *dest, char *src)
{
	int len = strlen(src);
	if (len > MAP_STRING_LENGTH - 1)
		len = MAP_STRING_LENGTH - 1;
	strncpy (dest, src, len);
	dest[len] = 0;
}
#endif

#ifdef NEED_STRING_KEYS
int str_eq_p (char *key1, char *key2)
{
	return strncmp(key1, key2, MAP_STRING_LENGTH - 1) == 0;
}

unsigned int str_hash(const char *key1)
{
	int hash = 0, count = 0;
	char *v1 = (char *)key1;
	while (*v1 && count++ < 5) {
		hash += *v1++;
	}
	return (unsigned int)hash_long((unsigned long)hash, HASH_TABLE_BITS);
}
#endif /* NEED_STRING_KEYS */

/** @addtogroup maps 
 * Implements maps (associative arrays) and lists
 * @{ 
 */

/** Return an int64 from a map node.
 * This function will return the int64 value of a map_node
 * from a map containing int64s. You can get the map_nodes in a map
 * with _stp_map_start(), _stp_map_iter() and foreach().
 * @param m pointer to the map_node. 
 * @returns an int64 value.
 */
int64_t _stp_get_int64(struct map_node *m)
{
	return *(int64_t *)((long)m + m->map->data_offset);
}

/** Return a string from a map node.
 * This function will return the string value of a map_node
 * from a map containing strings. You can get the map_nodes in a map
 * with _stp_map_start(), _stp_map_iter() and foreach().
 * @param m pointer to the map_node.
 * @returns a pointer to a string. 
 */
char *_stp_get_str(struct map_node *m)
{
	return (char *)((long)m + m->map->data_offset);
}

/** Return a stat pointer from a map node.
 * This function will return the stats of a map_node
 * from a map containing stats. You can get the map_nodes in a map
 * with _stp_map_start(), _stp_map_iter() and foreach().
 * @param m pointer to the map_node.
 * @returns A pointer to the stats.  
 */
stat *_stp_get_stat(struct map_node *m)
{
	return (stat *)((long)m + m->map->data_offset);
}

/** Return an int64 key from a map node.
 * This function will return an int64 key from a map_node.
 * @param m pointer to the map_node.
 * @param n key number
 * @returns an int64
 * @sa key1int(), key2int()
 */
int64_t _stp_key_get_int64 (struct map_node *mn, int n)
{
	if (mn)
		return (*mn->map->get_key)(mn, n, NULL).val;
	return 0;
}

/** Return a string key from a map node.
 * This function will return an string key from a map_node.
 * @param m pointer to the map_node.
 * @param n key number
 * @returns a pointer to a string
 * @sa key1str(), key2str()
 */
char *_stp_key_get_str (struct map_node *mn, int n)
{
	if (mn)
		return (*mn->map->get_key)(mn, n, NULL).strp;
	return "";
}

/** Create a new map.
 * Maps must be created at module initialization time.
 * @param max_entries The maximum number of entries allowed. Currently that number will
 * be preallocated.  If more entries are required, the oldest ones will be deleted. This makes
 * it effectively a circular buffer.  If max_entries is 0, there will be no maximum and entries
 * will be allocated dynamically.
 * @param type Type of values stored in this map. 
 * @return A MAP on success or NULL on failure.
 * @ingroup map_create
 */

static MAP _stp_map_new(unsigned max_entries, int type, int key_size, int data_size)
{
	int size;
	MAP m = (MAP) _stp_valloc(sizeof(struct map_root));
	if (m == NULL)
		return NULL;

	INIT_LIST_HEAD(&m->head);

	m->maxnum = max_entries;
	m->type = type;
	if (type >= END) {
		dbug ("map_new: unknown type %d\n", type);
		return NULL;
	}
	if (max_entries) {
		void *tmp;
		int i;
		struct list_head *e;

		INIT_LIST_HEAD(&m->pool);
		
		/* size is the size of the map_node. */
		/* add space for the value. */
		key_size = ALIGN(key_size,4);
		m->data_offset = key_size;
		if (data_size == 0)
			data_size = map_sizes[type];
		data_size = ALIGN(data_size,4);
		size = key_size + data_size;

		tmp = _stp_valloc(max_entries * size);

		for (i = max_entries - 1; i >= 0; i--) {
			e = i * size + tmp;
			dbug ("e=%lx\n", (long)e);
			list_add(e, &m->pool);
			((struct map_node *)e)->map = m;
		}
		m->membuf = tmp;
	}
	if (type == STAT)
		m->hist_type = HIST_NONE;
	return m;
}


/** Deletes the current element.
 * If no current element (key) for this map is set, this function does nothing.
 * @param map 
 */

void _stp_map_key_del(MAP map)
{
	struct map_node *m;

	dbug ("create=%d key=%lx\n", map->create, (long)map->key);
	if (map == NULL)
		return;

	if (map->create) {
		map->create = 0;
		map->key = NULL;
		return;
	}

	if (map->key == NULL)
		return;

	m = (struct map_node *)map->key;

	/* remove node from old hash list */
	hlist_del_init(&m->hnode);

	/* remove from entry list */
	list_del(&m->lnode);

	list_add(&m->lnode, &map->pool);

	map->key = NULL;
	map->num--;
}

/** Get the first element in a map.
 * @param map 
 * @returns a pointer to the first element.
 * This is typically used with _stp_map_iter().  See the foreach() macro
 * for typical usage.  It probably does what you want anyway.
 * @sa foreach
 */

struct map_node *_stp_map_start(MAP map)
{
	if (map == NULL)
		return NULL;

	dbug ("%lx\n", (long)map->head.next);

	if (list_empty(&map->head))
		return NULL;

	return (struct map_node *)map->head.next;
}

/** Get the next element in a map.
 * @param map 
 * @param m a pointer to the current element, returned from _stp_map_start()
 * or _stp_map_iter().
 * @returns a pointer to the next element.
 * This is typically used with _stp_map_start().  See the foreach() macro
 * for typical usage.  It probably does what you want anyway.
 * @sa foreach
 */

struct map_node *_stp_map_iter(MAP map, struct map_node *m)
{
	if (map == NULL)
		return NULL;

	dbug ("%lx next=%lx  prev=%lx  map->head.next=%lx\n", (long)m, 
	      (long)m->lnode.next, (long)m->lnode.prev, (long)map->head.next);

	if (m->lnode.next == &map->head)
		return NULL;

	return (struct map_node *)m->lnode.next;
}

/** Deletes a map.
 * Deletes a map, freeing all memory in all elements.  Normally done only when the module exits.
 * @param map
 */

void _stp_map_del(MAP map)
{
	if (map == NULL)
		return;
	_stp_vfree(map->membuf);
	_stp_vfree(map);
}

static int print_keytype (char *fmt, int type, key_data *kd)
{
	dbug ("*fmt = %c\n", *fmt);
	switch (type) {
	case STRING:
		if (*fmt != 's')
			return 1;
		_stp_print_cstr (kd->strp);
		break;
	case INT64:
		if (*fmt == 'x')
			_stp_printf("%llx", kd->val);
		else if (*fmt == 'X')
			_stp_printf("%llX", kd->val);
		else if (*fmt == 'd')
			_stp_printf("%lld", kd->val);
		else if (*fmt == 'p') {
#if BITS_PER_LONG == 64
			_stp_printf("%016llx", kd->val);
#else
			_stp_printf("%08llx", kd->val);
#endif
		} else if (*fmt == 'P')
			_stp_symbol_print ((unsigned long)kd->val);
		else
			return 1;
		break;
	default:
		return 1;
		break;
	}
	return 0;
}

static void print_valtype (MAP map, char *fmt, struct map_node *ptr)
{
	switch (map->type) {
	case STRING:
		if (*fmt == 's')
			_stp_print_cstr(_stp_get_str(ptr));
		break;
	case INT64:
	{
		int64_t val = _stp_get_int64(ptr);
		if (*fmt == 'x')
			_stp_printf("%llx", val);
		else if (*fmt == 'X')
			_stp_printf("%llX", val);
		else if (*fmt == 'd')
			_stp_printf("%lld", val);
		else if (*fmt == 'p') {
#if BITS_PER_LONG == 64
			_stp_printf("%016llx", val);
#else
			_stp_printf("%08llx", val);
#endif
		} else if (*fmt == 'P')
			_stp_symbol_print ((unsigned long)val);
		break;
	}
#ifdef NEED_STAT_VALS
	case STAT:
	{
		Stat st = (Stat)((long)map + offsetof(struct map_root, hist_type));
		stat *sd = _stp_get_stat(ptr);
		_stp_stat_print_valtype (fmt, st, sd, 0); 
		break;
	}
#endif
	default:
		break;
	}
}

/** Print a Map.
 * Print a Map using a format string.
 *
 * @param map Map
 * @param fmt @ref format_string
 */
void _stp_map_print (MAP map, const char *fmt)
{
	struct map_node *ptr;
	int type, num;
	key_data kd;
	dbug ("print map %lx fmt=%s\n", (long)map, fmt);

	foreach (map, ptr) {
		char *f = (char *)fmt;
		while (*f) {
			f = next_fmt (f, &num);
			if (num) {
				/* key */
				kd = (*map->get_key)(ptr, num, &type);
				if (type != END)
					print_keytype (f, type, &kd);
			} else {
				/* value */
				print_valtype (map, f, ptr);
			}
			if (*f)
				f++;
		}
		_stp_print_cstr ("\n");
	}
	_stp_print_cstr ("\n");
	_stp_print_flush();
}

static struct map_node *__stp_map_create (MAP map)
{
	struct map_node *m;
	if (list_empty(&map->pool)) {
		if (map->no_wrap) {
			/* ERROR. FIXME */
			return NULL;
		}
		m = (struct map_node *)map->head.next;
		hlist_del_init(&m->hnode);
		dbug ("got %lx off head\n", (long)m);
	} else {
		m = (struct map_node *)map->pool.next;
		dbug ("got %lx off pool\n", (long)m);
	}
	list_move_tail(&m->lnode, &map->head);
	
	/* copy the key(s) */
	(map->copy_keys)(map, m);
	
	/* add node to new hash list */
	hlist_add_head(&m->hnode, map->c_keyhead);
	
	map->key = m;
	map->create = 0;
	map->num++;
	return m;
}
#endif