Hi,

I looked at some standart C libraries and tried to convert a hashmap to Lite-C.

Important:
You need to destroy the containers when you close the engine whith the implemented Hashmap_destroy() function, because I don't use sys_malloc. I am using malloc realloc and free to do the memory work. Why? Because there is no sys_realloc and don't want to use a workaround. So the memory is not automaticly freed, if you close the engine.

The code is not complete and not fully tested. There are a lot of things that need to be improved, like the memory allocation. It is not optimal.

If you know better hashfunctions, please tell me.

Why creating a independent hashmap code unit for each data type? Because it is difficult to typecheck in Lite-C and you can't do something like templates there, too.


You only need to include the header files .. but you need to save the .c files too, of course.

this post gets very big so here is a zip file with all needed files. The hashmap_int is included, too.
Lite-C_collections.zip

If you need other data types like double or var, you need to rewrite the hashmap and add the fitting hash_fuction.
if you need to use pointers just rewrite the hashmap_int to a hashmap_long (just replace int key, with long key.

Please post your improvements.

First the dynamic array, which is needed, to use the hashmap:
darray.h
Code:
#ifndef _darray_h
	#define _darray_h
	
	typedef struct DArray 
	{
		int end;
		int max;
		long element_size;
		long expand_rate;
		void **contents;
	} DArray;

	DArray *DArray_create(long element_size, long initial_max);

	void DArray_destroy(DArray *array);

	void DArray_clear(DArray *array);

	int DArray_expand(DArray *array);

	int DArray_contract(DArray *array);

	int DArray_push(DArray *array, void *el);

	void *DArray_pop(DArray *array);

	void DArray_clear_destroy(DArray *array);

	#define DArray_last(A) (((A)->contents)[(A)->end - 1])
	#define DArray_first(A) (((A)->contents)[0])
	#define DArray_end(A) ((A)->end)
	#define DArray_count(A) DArray_end(A)
	#define DArray_max(A) ((A)->max)

	#define DEFAULT_EXPAND_RATE 300

	void DArray_set(DArray *array, int i, void *el)
	{
		if(i >= array->max)
		{
			error("darray attempt to set past max");
			return;
		}
		(array->contents)[i] = el;
	}
	
	void *DArray_get(DArray *array, int i)
	{
		if(i >= array->max)
		{
			error("darray attempt to get past max");
			return NULL;
		}
		return (array->contents)[i];
	}
	
	void *DArray_remove(DArray *array, int i)
	{
		void *el = (array->contents)[i];

		(array->contents)[i] = NULL;

		return el;
	}
	
	void *DArray_new(DArray *array)
	{
		if(array->element_size == 0)
		{
			error("Can't use DArray_new on 0 size darrays.");
			return NULL;
		}

		return malloc(sizeof(array->element_size));
	}
	
	#define DArray_free(E) free((E))

	#include "darray.c"

#endif


darray.c:
Code:
#ifndef _darray_c
	#define _darray_c

	#include "darray.h"

	DArray *DArray_create(long element_size, long initial_max)
	{
		DArray *array = (DArray*)malloc(sizeof(DArray));
		
		array->max = initial_max;
		
		if(array->max == 0)
		{
			error("You must set an initial_max > 0.");
			return NULL;
		}

		array->contents = (void **)malloc(sizeof(void *) * initial_max);
		
		memset(array->contents, 0, sizeof(void *) * initial_max);

		array->end = 0;
		array->element_size = element_size;
		array->expand_rate = DEFAULT_EXPAND_RATE;

		return array;
	}


	void DArray_clear(DArray *array)
	{
		int i = 0;
		if(array->element_size > 0) 
		{
			for(i = 0; i < array->max; i++) 
			{
				if((array->contents)[i] != NULL) 
				{
					free((array->contents)[i]);
				}
			}
		}
	}
	
	int DArray_resize(DArray *array, long newsize)
	{
		array->max = newsize;
		if(array->max == 0)
		{
			error("The newsize must be > 0.");
			return -1;
		}
		array->contents = realloc(array->contents, array->max * sizeof(void *));
		return 0;
	}
	
	int DArray_expand(DArray *array)
	{
		long old_max = array->max;
		if(DArray_resize(array, array->max + array->expand_rate) == -1)
		{
			printf("Failed to expand array to new size: %d", array->max + (int)array->expand_rate); 
			return -1;
		}

		memset(array->contents + old_max, 0, array->expand_rate + 1);
		return 0;
	}
	
	int DArray_contract(DArray *array)
	{
		int new_size;
		if(array->end < (int)array->expand_rate)
		{
			new_size = (int)array->expand_rate;
		}
		else
		{
			new_size = array->end;
		}
		return DArray_resize(array, new_size + 1);
	}
	
	void DArray_destroy(DArray *array)
	{
		if(array) 
		{
			if(array->contents) free(array->contents);
			sys_free(array);
		}
	}
	
	void DArray_clear_destroy(DArray *array)
	{
		DArray_clear(array);
		DArray_destroy(array);
	}
	
	int DArray_push(DArray *array, void *el)
	{
		(array->contents)[array->end] = el;
		array->end++;

		if(DArray_end(array) >= DArray_max(array))
		{
			return DArray_expand(array);
		} 
		else 
		{
			return 0;
		}
	}
	
	void *DArray_pop(DArray *array)
	{
		if(array->end - 1 < 0)
		{
			error("Attempt to pop from empty array.");
			return NULL;
		}

		void *el = DArray_remove(array, array->end - 1);
		array->end--;

		if(DArray_end(array) > (int)array->expand_rate && DArray_end(array) % array->expand_rate) 
		{
			DArray_contract(array);
		}

		return el;
	}


#endif


hashmap_string.h

Code:
#ifndef _Hashmap_string_h
#define _Hashmap_string_h

#define DEFAULT_NUMBER_OF_BUCKETS 100

#include "darray.h"

int Hahmap_compare_ptr(void *a, void *b);
UINT Hashmap_hash_ptr(void *key);

typedef struct Hashmap 
{
    DArray *buckets;
    void *compare;
    void *hash;
}Hashmap;

typedef struct HashmapNode 
{
    void *key;
    void *data;
    UINT hash;
}HashmapNode;

int Hashmap_traverse_cb_ptr(HashmapNode *node);

Hashmap *Hashmap_create(void *compare, void *Hashmap_hash);
void Hashmap_destroy(Hashmap *map);

int Hashmap_set(Hashmap *map, char *rkey, void *data);
void *Hashmap_get(Hashmap *map, STRING *key);

int Hashmap_traverse(Hashmap *map, void *traverse_cb);

void *Hashmap_delete(Hashmap *map, STRING *key);

#include "hashmap.c"

#endif


hashmap_string.c

Code:
#ifndef _Hashmap_string_c
	#define _Hashmap_string_c
	
	int default_compare(STRING *b0, STRING *b1)
	{
		int i, v, n;
		
		if(b0 == NULL || b1 == NULL) { return 5; }
		if(str_len(b0) == 0 || str_len(b1) == 0) { return 5; }
		
		n = str_len(b0);
		if(n > str_len(b1))
		{
			n = str_len(b1);
		}
		
		if(str_len(b0) == str_len(b1) && (str_cmp(b0, b1) == 1 || str_len(b0) == 0))
		{
			return 0;
		}
		
		for(i = 0; i < n; i++)
		{
			v = (b0->chars)[i] - (b1->chars)[i];
			if(v != 0) { return v; }
			if((b0->chars)[i] == '\0') return 0;
		}
		if(str_len(b0) > n) return 1;
		if(str_len(b1) > n) return -1;
		return 0;
	}
	
	int int_hash(int a)
	{
		int hash = a;
		hash = ((hash >> 16) ^ hash) * 0x45d9f3b;
		hash = ((hash >> 16) ^ hash) * 0x45d9f3b;
		hash = ((hash >> 16) ^ hash);
		return hash;
	}
	
	int default_hash(STRING *a)
	{
		int len = str_len(a);
		
		char *key = a->chars;
		char hash = 0;
		int i = 0;

		for(hash = i = 0; i < len; ++i)
		{
			hash += key[i];
			hash += (hash << 10);
			hash ^= (hash >> 6);
		}

		hash += (hash << 3);
		hash ^= (hash >> 11);
		hash += (hash << 15);

		return hash;
	}
	
	
	Hashmap *Hashmap_create(void *compare, void *hash)
	{
		Hashmap *map = malloc(sizeof(Hashmap));
		
		if(compare == NULL)
		{
			map->compare = default_compare;
		}
		if(hash == NULL)
		{
			map->hash = default_hash;
		}

		map->buckets = DArray_create(sizeof(DArray *), DEFAULT_NUMBER_OF_BUCKETS);
		map->buckets->end = map->buckets->max;
		
		return map;
	}
	
	
	void Hashmap_destroy(Hashmap *map)
	{
		int i = 0;
		int j = 0;

		if(map) 
		{
			if(map->buckets) 
			{
				for(i = 0; i < map->buckets->end; i++) 
				{
					DArray *bucket = DArray_get(map->buckets, i);
					if(bucket) 
					{
						for(j = 0; j < bucket->end; j++) 
						{
							free(DArray_get(bucket, j));
						}
						DArray_destroy(bucket);
					}
				}
				DArray_destroy(map->buckets);
			}
			free(map);
		}
	}
	
	HashmapNode *Hashmap_node_create(int hash, STRING *key, void *data)
	{
		HashmapNode *node = malloc(sizeof(HashmapNode));

		node->key = key;
		node->data = data;
		node->hash = hash;

		return node;
	}
	
	DArray *Hashmap_find_bucket(Hashmap *map, STRING *key, int create, UINT *hash_out)
	{
		Hashmap_hash_ptr = map->hash;
		UINT hash = Hashmap_hash_ptr(key);
		int bucket_n = hash % DEFAULT_NUMBER_OF_BUCKETS;
		if(bucket_n < 0) { printf("Invalid bucket found: %d, %d", bucket_n, hash); return NULL; }
		*hash_out = hash;


		DArray *bucket = DArray_get(map->buckets, bucket_n);

		if(bucket == NULL && create == 1) 
		{
			bucket = DArray_create(sizeof(HashmapNode*), DEFAULT_NUMBER_OF_BUCKETS);
			DArray_set(map->buckets, bucket_n, bucket);
		}

		return bucket;
	}
	
	int Hashmap_set(Hashmap *map, char *rkey, void *data)
	{
		STRING *key = str_create(rkey);
		UINT hash = 0;
		DArray *bucket = Hashmap_find_bucket(map, key, 1, &hash);
		if(!bucket) { error("Error can't create bucket"); return -1; }

		HashmapNode *node = Hashmap_node_create(hash, key, data);

		DArray_push(bucket, node);

		return 0;
	}
	
	int Hashmap_get_node(Hashmap *map, UINT hash, DArray *bucket, STRING *key)
	{
		int i = 0;

		for(i = 0; i < DArray_end(bucket); i++) 
		{
			HashmapNode *node = DArray_get(bucket, i);
			Hahmap_compare_ptr = map->compare;
			if(node->hash == hash && Hahmap_compare_ptr(node->key, key) == 0)
			{
				return i;
			}
		}
		return -1;
	}
	
	void *Hashmap_get(Hashmap *map, STRING *key)
	{
		UINT hash = 0;
		DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
		if(!bucket) return NULL;

		int i = Hashmap_get_node(map, hash, bucket, key);
		if(i == -1) return NULL;

		HashmapNode *node = DArray_get(bucket, i);
		if(node == NULL) { error("Failed to get node from bucket when it should exist."); return NULL; }

		return node->data;
	}
	
	
	int Hashmap_traverse(Hashmap *map, void *traverse_cb)
	{
		int i = 0;
		int j = 0;
		int rc = 0;

		for(i = 0; i < DArray_count(map->buckets); i++) 
		{
			DArray *bucket = DArray_get(map->buckets, i);
			if(bucket) 
			{
				for(j = 0; j < DArray_count(bucket); j++) 
				{
					HashmapNode *node = DArray_get(bucket, j);
					Hashmap_traverse_cb_ptr = traverse_cb;
					rc = Hashmap_traverse_cb_ptr(node);
					if(rc != 0) return rc;
				}
			}
		}
		return 0;
	}
	
	void *Hashmap_delete(Hashmap *map, STRING *key)
	{
		UINT hash = 0;
		DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
		if(!bucket) return NULL;

		int i = Hashmap_get_node(map, hash, bucket, key);
		if(i == -1) return NULL;

		HashmapNode *node = DArray_get(bucket, i);
		void *data = node->data;
		free(node);

		HashmapNode *ending = DArray_pop(bucket);

		if(ending != node) 
		{
			DArray_set(bucket, i, ending);
		}

		return data;
	}
	

#endif