gistfile1.c

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <string.h>
#include <ctime>

struct INTEGER_LIST
{
  int* base;
	unsigned int capacity;
	unsigned int count;
};

INTEGER_LIST* CreateIntegerList(unsigned int capacity)
{
	if (capacity == 0) return NULL;
	INTEGER_LIST* list = (INTEGER_LIST*) malloc(sizeof(INTEGER_LIST));
	if (list == NULL) return NULL;
	list->base = (int*) malloc(sizeof(int) * capacity);
	if (list->base == NULL)
	{
		free(list);
		return NULL;
	}
	list->capacity = capacity;
	list->count = 0;
	return list;
}

bool IntegerListContains(INTEGER_LIST *list, int n)
{
	int *ip = list->base;
	for (int i = 0; i < list->count; i++, ip++)
	{
		if (*ip == n) return true;
	}
	return false;
}

bool IntegerListAdd(INTEGER_LIST *list, int n)
{
	if (list->capacity <= list->count)
	{
		unsigned int newCapacity = list->capacity * 2;
		int* newBase = (int*) malloc(newCapacity * sizeof(int));
		if (newBase == NULL) return false;
		memcpy(newBase, list->base, list->capacity * sizeof(int));
		free(list->base);
		list->base = newBase;
		list->capacity = newCapacity;
	}
	list->base[list->count] = n;
	list->count++;
	return true;
}

void IntegerListDestroy(INTEGER_LIST *list)
{
	free(list->base);
	free(list);
}

struct POORMAN_INTEGER_HASHSET
{
	unsigned int bucketsCount;
	INTEGER_LIST** buckets;
};

POORMAN_INTEGER_HASHSET* CreateIntegerHashSet(unsigned int bucketsCount)
{
	POORMAN_INTEGER_HASHSET* hashSet = (POORMAN_INTEGER_HASHSET*) malloc(sizeof(POORMAN_INTEGER_HASHSET));
	if (hashSet == NULL) return NULL;
	hashSet->buckets = (INTEGER_LIST **) malloc(sizeof(INTEGER_LIST*) * bucketsCount);
	if (hashSet->buckets == NULL)
	{
		free(hashSet);
		return NULL;
	}
	memset(hashSet->buckets, 0, sizeof(INTEGER_LIST*) * bucketsCount);
	hashSet->bucketsCount = bucketsCount;
	return hashSet;
}

bool HashSetContains(POORMAN_INTEGER_HASHSET *hashSet, int n)
{
	unsigned int bucketIndex = ((unsigned int) n) % hashSet->bucketsCount;
	INTEGER_LIST* bucket = hashSet->buckets[bucketIndex];
	if (bucket == NULL) return false;
	return IntegerListContains(bucket, n);
}

bool IntegerHashSetTryAdd(POORMAN_INTEGER_HASHSET *hashSet, int n, bool *added)
{
	unsigned int bucketIndex = ((unsigned int) n) % hashSet->bucketsCount;
	INTEGER_LIST* bucket = hashSet->buckets[bucketIndex];
	if (bucket == NULL)
	{
		bucket = CreateIntegerList(8);
		if (bucket == NULL) return false;
		hashSet->buckets[bucketIndex] = bucket;
	}
	if (IntegerListContains(bucket, n))
	{
		*added = false;
		return true;
	}
	if (IntegerListAdd(bucket, n))
	{
		*added = true;
		return true;
	}
	return false;
}

void IntegerHashSetDestroy(POORMAN_INTEGER_HASHSET* hasSet)
{
	for (int i = 0; i < hasSet->bucketsCount; i++)
	{
		INTEGER_LIST* bucket;
		bucket = hasSet->buckets[i];
		
		if (bucket != NULL)
		{
			IntegerListDestroy(bucket);
		}
	}
	free(hasSet->buckets);
	free(hasSet);
}

int GetRand()
{
	return (rand() << 16) | rand();
}


int _tmain(int argc, _TCHAR* argv[])
{
	POORMAN_INTEGER_HASHSET *hashSet;
	unsigned int oneMillion = 1000000;
	unsigned int oneUndred = 100;
	clock_t initialTime;
	clock_t finalTime;
	double elapsetTime;
	initialTime = clock();
	hashSet = CreateIntegerHashSet(oneMillion / oneUndred);
	if (hashSet == NULL) return -1;
	for (unsigned int i = 0; i < oneMillion; i++)
	{
		bool added = false;
		do
		{
			int r = GetRand();
			if (!IntegerHashSetTryAdd(hashSet, r, &added))
			{
				return -1;
			}
		} while (!added);
	}
	IntegerHashSetDestroy(hashSet);
	finalTime = clock();
	elapsetTime =  double(finalTime - initialTime) / CLOCKS_PER_SEC;
	printf("Elapsed seconds %lf \n", elapsetTime);
	return 0;
}