[GitHub/mt8127/android_kernel_alcatel_ttab.git] / drivers / misc / mediatek / gpu / ged / src / ged_hashtable.c

#include "ged_base.h"
#include "ged_hashtable.h"
#include <linux/hashtable.h>

typedef struct GED_HASHTABLE_TAG
{
	unsigned int        ui32Bits;
	unsigned int        ui32Length;
	unsigned int        ui32CurrentID;
	unsigned int        ui32Count;
	struct hlist_head*  psHashTable;
} GED_HASHTABLE;

typedef struct GED_HASHNODE_TAG
{
	unsigned int        ui32ID;
	void*               pvoid;
	struct hlist_node   sNode;
} GED_HASHNODE;

#define GED_HASHTABLE_INIT_ID 1234 // 0 = invalid

void* __ged_hashtable_find(struct hlist_head *head, unsigned int ui32ID)
{
	GED_HASHNODE* psHN;
	hlist_for_each_entry_rcu(psHN, head, sNode) 
	{
		if (psHN->ui32ID == ui32ID)
		{
			return psHN;
		}
	}
	return NULL;
}

static int ged_hash(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
{
	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	return hash_32(ui32ID, psHT->ui32Bits);
}

GED_HASHTABLE_HANDLE ged_hashtable_create(unsigned int ui32Bits)
{
	GED_HASHTABLE* psHT;
	unsigned int i;

	if (ui32Bits > 20)
	{
		// 1048576 slots !?
		// Need to check the necessary
		return NULL;
	}

	psHT = (GED_HASHTABLE*)ged_alloc(sizeof(GED_HASHTABLE));
	if (psHT)
	{
		psHT->ui32Bits = ui32Bits;
		psHT->ui32Length = 1 << ui32Bits;
		psHT->ui32CurrentID = GED_HASHTABLE_INIT_ID; // 0 = invalid
		psHT->psHashTable = (struct hlist_head*)ged_alloc(psHT->ui32Length * sizeof(struct hlist_head));
		if (psHT->psHashTable)
		{
			for (i = 0; i < psHT->ui32Length; i++)
			{
				INIT_HLIST_HEAD(&psHT->psHashTable[i]);
			}
			return (GED_HASHTABLE_HANDLE)psHT;
		}
	}

	ged_hashtable_destroy(psHT);
	return NULL;
}

void ged_hashtable_destroy(GED_HASHTABLE_HANDLE hHashTable)
{
	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	if (psHT)
	{
		int i = 0;
		while(psHT->ui32Count > 0)
		{
			unsigned int ui32ID = 0;
			GED_HASHNODE* psHN;
			// get one to be freed
			for (;i < psHT->ui32Length; i++)
			{
				struct hlist_head *head = &psHT->psHashTable[i];
				hlist_for_each_entry_rcu(psHN, head, sNode) 
				{
					ui32ID = psHN->ui32ID;
					break;
				}
				if (0 < ui32ID)
				{
					break;
				}
			}

			if (i >= psHT->ui32Length)
			{
				break;
			}

			ged_hashtable_remove(psHT, ui32ID);
		}

		/* free the hash table */
		ged_free(psHT->psHashTable, psHT->ui32Length * sizeof(struct hlist_head));
		ged_free(psHT, sizeof(GED_HASHTABLE));
	}
}

GED_ERROR ged_hashtable_insert(GED_HASHTABLE_HANDLE hHashTable, void* pvoid, unsigned int* pui32ID)
{
	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	GED_HASHNODE* psHN = NULL;
	unsigned int ui32Hash, ui32ID;

	if ((!psHT) || (!pui32ID))
	{
		return GED_ERROR_INVALID_PARAMS;
	}

	ui32ID = psHT->ui32CurrentID + 1;
	while(1)
	{
		ui32Hash = ged_hash(psHT, ui32ID);
		psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
		if (psHN != NULL)
		{
			ui32ID++;
			if (ui32ID == 0)//skip the value 0
			{
				ui32ID = 1;
			}
			if (ui32ID == psHT->ui32CurrentID)
			{
				return GED_ERROR_FAIL;
			}
		}
		else
		{
			break;
		}
	};

	psHN = (GED_HASHNODE*)ged_alloc(sizeof(GED_HASHNODE));
	if (psHN)
	{
		psHN->pvoid = pvoid;
		psHN->ui32ID = ui32ID;
		psHT->ui32CurrentID = ui32ID;
		*pui32ID = ui32ID;
		hlist_add_head_rcu(&psHN->sNode, &psHT->psHashTable[ui32Hash]);
		psHT->ui32Count += 1;
		return GED_OK;
	}

	return GED_ERROR_OOM;
}

void ged_hashtable_remove(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
{
	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	if (psHT)
	{
		unsigned int ui32Hash = ged_hash(psHT, ui32ID);
		GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
		if (psHN)
		{
			hlist_del_rcu(&psHN->sNode);
			synchronize_rcu();
			ged_free(psHN, sizeof(GED_HASHNODE));
			psHT->ui32Count -= 1;
		}
	}
}

void* ged_hashtable_find(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
{
	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	if (psHT)
	{
		unsigned int ui32Hash = ged_hash(psHT, ui32ID);
		GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
		if (psHN)
		{
			return psHN->pvoid;
		}
#ifdef GED_DEBUG
		if (ui32ID != 0)
		{
			GED_LOGE("ged_hashtable_find: ui32ID=%u ui32Hash=%u psHN=%p\n", ui32ID, ui32Hash, psHN);
		}
#endif
	}
	return NULL;
}

GED_ERROR ged_hashtable_set(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID, void* pvoid)
{
	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	if (psHT)
	{
		unsigned int ui32Hash = ged_hash(psHT, ui32ID);
		GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
		if (psHN)
		{
			psHN->pvoid = pvoid;
			return GED_OK;
		}
	}

	return GED_ERROR_INVALID_PARAMS;
}
Commit	Line	Data
6fa3eb70 S	1	#include "ged_base.h"
	2	#include "ged_hashtable.h"
	3	#include <linux/hashtable.h>
	4
	5	typedef struct GED_HASHTABLE_TAG
	6	{
db9a41fa S	7	unsigned int ui32Bits;
	8	unsigned int ui32Length;
	9	unsigned int ui32CurrentID;
	10	unsigned int ui32Count;
	11	struct hlist_head* psHashTable;
6fa3eb70 S	12	} GED_HASHTABLE;
	13
	14	typedef struct GED_HASHNODE_TAG
	15	{
db9a41fa S	16	unsigned int ui32ID;
	17	void* pvoid;
	18	struct hlist_node sNode;
6fa3eb70 S	19	} GED_HASHNODE;
	20
	21	#define GED_HASHTABLE_INIT_ID 1234 // 0 = invalid
	22
	23	void* __ged_hashtable_find(struct hlist_head *head, unsigned int ui32ID)
	24	{
db9a41fa S	25	GED_HASHNODE* psHN;
	26	hlist_for_each_entry_rcu(psHN, head, sNode)
	27	{
	28	if (psHN->ui32ID == ui32ID)
	29	{
	30	return psHN;
	31	}
	32	}
	33	return NULL;
6fa3eb70 S	34	}
	35
	36	static int ged_hash(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
	37	{
db9a41fa S	38	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
db9a41fa S	39	return hash_32(ui32ID, psHT->ui32Bits);
6fa3eb70 S	40	}
	41
	42	GED_HASHTABLE_HANDLE ged_hashtable_create(unsigned int ui32Bits)
	43	{
db9a41fa S	44	GED_HASHTABLE* psHT;
	45	unsigned int i;
	46
	47	if (ui32Bits > 20)
	48	{
	49	// 1048576 slots !?
	50	// Need to check the necessary
	51	return NULL;
	52	}
	53
	54	psHT = (GED_HASHTABLE*)ged_alloc(sizeof(GED_HASHTABLE));
	55	if (psHT)
	56	{
	57	psHT->ui32Bits = ui32Bits;
	58	psHT->ui32Length = 1 << ui32Bits;
	59	psHT->ui32CurrentID = GED_HASHTABLE_INIT_ID; // 0 = invalid
	60	psHT->psHashTable = (struct hlist_head)ged_alloc(psHT->ui32Length sizeof(struct hlist_head));
	61	if (psHT->psHashTable)
	62	{
	63	for (i = 0; i < psHT->ui32Length; i++)
	64	{
	65	INIT_HLIST_HEAD(&psHT->psHashTable[i]);
	66	}
	67	return (GED_HASHTABLE_HANDLE)psHT;
	68	}
	69	}
	70
	71	ged_hashtable_destroy(psHT);
	72	return NULL;
6fa3eb70 S	73	}
	74
	75	void ged_hashtable_destroy(GED_HASHTABLE_HANDLE hHashTable)
	76	{
db9a41fa S	77	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	78	if (psHT)
	79	{
	80	int i = 0;
	81	while(psHT->ui32Count > 0)
	82	{
	83	unsigned int ui32ID = 0;
	84	GED_HASHNODE* psHN;
	85	// get one to be freed
	86	for (;i < psHT->ui32Length; i++)
	87	{
	88	struct hlist_head *head = &psHT->psHashTable[i];
	89	hlist_for_each_entry_rcu(psHN, head, sNode)
	90	{
	91	ui32ID = psHN->ui32ID;
	92	break;
	93	}
	94	if (0 < ui32ID)
	95	{
	96	break;
	97	}
	98	}
	99
	100	if (i >= psHT->ui32Length)
	101	{
	102	break;
	103	}
	104
	105	ged_hashtable_remove(psHT, ui32ID);
	106	}
	107
	108	/* free the hash table */
	109	ged_free(psHT->psHashTable, psHT->ui32Length * sizeof(struct hlist_head));
	110	ged_free(psHT, sizeof(GED_HASHTABLE));
	111	}
6fa3eb70 S	112	}
	113
	114	GED_ERROR ged_hashtable_insert(GED_HASHTABLE_HANDLE hHashTable, void* pvoid, unsigned int* pui32ID)
	115	{
db9a41fa S	116	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	117	GED_HASHNODE* psHN = NULL;
	118	unsigned int ui32Hash, ui32ID;
	119
	120	if ((!psHT) \|\| (!pui32ID))
	121	{
	122	return GED_ERROR_INVALID_PARAMS;
	123	}
	124
	125	ui32ID = psHT->ui32CurrentID + 1;
	126	while(1)
	127	{
	128	ui32Hash = ged_hash(psHT, ui32ID);
	129	psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
	130	if (psHN != NULL)
	131	{
	132	ui32ID++;
	133	if (ui32ID == 0)//skip the value 0
	134	{
	135	ui32ID = 1;
	136	}
	137	if (ui32ID == psHT->ui32CurrentID)
	138	{
	139	return GED_ERROR_FAIL;
	140	}
	141	}
	142	else
	143	{
	144	break;
	145	}
	146	};
	147
	148	psHN = (GED_HASHNODE*)ged_alloc(sizeof(GED_HASHNODE));
	149	if (psHN)
	150	{
	151	psHN->pvoid = pvoid;
	152	psHN->ui32ID = ui32ID;
	153	psHT->ui32CurrentID = ui32ID;
	154	*pui32ID = ui32ID;
	155	hlist_add_head_rcu(&psHN->sNode, &psHT->psHashTable[ui32Hash]);
	156	psHT->ui32Count += 1;
	157	return GED_OK;
	158	}
	159
	160	return GED_ERROR_OOM;
6fa3eb70 S	161	}
	162
	163	void ged_hashtable_remove(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
	164	{
db9a41fa S	165	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	166	if (psHT)
	167	{
	168	unsigned int ui32Hash = ged_hash(psHT, ui32ID);
	169	GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
	170	if (psHN)
	171	{
	172	hlist_del_rcu(&psHN->sNode);
	173	synchronize_rcu();
	174	ged_free(psHN, sizeof(GED_HASHNODE));
	175	psHT->ui32Count -= 1;
	176	}
	177	}
6fa3eb70 S	178	}
	179
	180	void* ged_hashtable_find(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID)
	181	{
db9a41fa S	182	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	183	if (psHT)
	184	{
	185	unsigned int ui32Hash = ged_hash(psHT, ui32ID);
	186	GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
	187	if (psHN)
	188	{
	189	return psHN->pvoid;
	190	}
6fa3eb70	191	#ifdef GED_DEBUG
db9a41fa S	192	if (ui32ID != 0)
	193	{
	194	GED_LOGE("ged_hashtable_find: ui32ID=%u ui32Hash=%u psHN=%p\n", ui32ID, ui32Hash, psHN);
	195	}
6fa3eb70	196	#endif
db9a41fa S	197	}
db9a41fa S	198	return NULL;
6fa3eb70 S	199	}
	200
	201	GED_ERROR ged_hashtable_set(GED_HASHTABLE_HANDLE hHashTable, unsigned int ui32ID, void* pvoid)
	202	{
db9a41fa S	203	GED_HASHTABLE* psHT = (GED_HASHTABLE*)hHashTable;
	204	if (psHT)
	205	{
	206	unsigned int ui32Hash = ged_hash(psHT, ui32ID);
	207	GED_HASHNODE* psHN = __ged_hashtable_find(&psHT->psHashTable[ui32Hash], ui32ID);
	208	if (psHN)
	209	{
	210	psHN->pvoid = pvoid;
	211	return GED_OK;
	212	}
	213	}
	214
	215	return GED_ERROR_INVALID_PARAMS;
6fa3eb70 S	216	}
6fa3eb70 S	217