hash.c

linux环境下用纯c写的RTP协议的通用开发库

/*-------------------------------------------------------------------------
 * hash.c - htnew, htreaderbegin, htreaderend, htwriterbegin, htwriterend,
 * htget, htgetent, htdel, htadd, hashstring, hashunsignedint, htcount,
 * htenum, htdestroy, unsignedinteq
 *-------------------------------------------------------------------------
 */

#include <stdio.h>
#include <hash.h>
#include <rtp.h>
#include <stdlib.h>
#include <strings.h>

/*------------------------------------------------------------------------
 * htnew - create and return pointer to a new hashtable 
 *------------------------------------------------------------------------
 */
struct ht *
htnew(int size, int(* hashfcn)(unsigned int, int), int(* cmpfcn)(unsigned int, unsigned int), void(* destroykeyfcn)(unsigned int), void(* destroyobjectfcn)(void *))
{

	struct ht		*ht;
  
	ht = (struct ht *) malloc(sizeof(struct ht));

	if (ht == NULL) 
		return NULL;

	pthread_mutex_init(&ht->ht_writepend, NULL);
	pthread_mutex_init(&ht->ht_readblk, NULL);
	pthread_mutex_init(&ht->ht_writeblk, NULL);
	pthread_mutex_init(&ht->ht_rdcntmutex, NULL);
	pthread_mutex_init(&ht->ht_wrcntmutex, NULL);

	ht->ht_readcnt = 0;
	ht->ht_writecnt = 0;

	ht->ht_entries = (struct htent **) malloc(sizeof(struct htent *) * size);
	ht->ht_count = 0;
	ht->ht_hashfcn = hashfcn;
	ht->ht_cmpfcn = cmpfcn;
	ht->ht_destroykeyfcn = destroykeyfcn;
	ht->ht_destroyobjectfcn = destroyobjectfcn;

	if (ht->ht_entries == NULL) {
		free(ht);
		return NULL;
	}

	bzero((char *)ht->ht_entries, size * sizeof(struct htent *));
	ht->ht_size = size;  
	return ht;
}

/*------------------------------------------------------------------------
 * htreaderbegin - to be called before reader access for locking
 *------------------------------------------------------------------------
 */
void
htreaderbegin(struct ht *ht)
{
	pthread_mutex_lock(&ht->ht_writepend);
	pthread_mutex_lock(&ht->ht_readblk);
	pthread_mutex_lock(&ht->ht_rdcntmutex);
  
	if ((++(ht->ht_readcnt)) == 1) {
		pthread_mutex_lock(&ht->ht_writeblk);
	}
	pthread_mutex_unlock(&ht->ht_rdcntmutex);
	pthread_mutex_unlock(&ht->ht_readblk);
	pthread_mutex_unlock(&ht->ht_writepend);
}

/*------------------------------------------------------------------------
 * htreaderend - to be called after reader access for locking
 *------------------------------------------------------------------------
 */
void
htreaderend(struct ht *ht)
{
	pthread_mutex_lock(&ht->ht_rdcntmutex);
	if (--ht->ht_readcnt == 0) {
		pthread_mutex_unlock(&ht->ht_writeblk);
	}
	pthread_mutex_unlock(&ht->ht_rdcntmutex);
}

/*------------------------------------------------------------------------
 * htwriterbegin - to be called before writer access for locking
 *------------------------------------------------------------------------
 */
void
htwriterbegin(struct ht *ht)
{
	pthread_mutex_lock(&ht->ht_wrcntmutex);
	if ((++(ht->ht_writecnt)) == 1)
		pthread_mutex_lock(&ht->ht_readblk);
	pthread_mutex_unlock(&ht->ht_wrcntmutex);
	pthread_mutex_lock(&ht->ht_writeblk);
}

/*------------------------------------------------------------------------
 * htwriterend - to be called after writer access for locking
 *------------------------------------------------------------------------
 */
void
htwriterend(struct ht *ht)
{
	pthread_mutex_unlock(&ht->ht_writeblk);
	pthread_mutex_lock(&ht->ht_wrcntmutex);
	if ((--(ht->ht_writecnt)) == 0)
		pthread_mutex_unlock(&ht->ht_readblk);
	pthread_mutex_unlock(&ht->ht_wrcntmutex);
}

/*------------------------------------------------------------------------
 * htget - retreive an object from the ht 
 *------------------------------------------------------------------------
 */
char *
htget(struct ht *ht, unsigned int key)
{

	struct htent *p;
	void *object;

	htreaderbegin(ht);
	p = htgetent(ht, key);

	if (p != NULL) {
		object = p->hte_object;
		htreaderend(ht);
		return object;
	}
	else {
		htreaderend(ht);
		return NULL;
	}
}

/*------------------------------------------------------------------------
 * htgetent - non-locking internal call to do the work of retreiving 
 * object from ht
 *------------------------------------------------------------------------
 */
struct htent *
htgetent(struct ht *ht, unsigned int key)
{

	int			hash;
	struct htent		*p;

	hash = ht->ht_hashfcn(key, ht->ht_size);
	p = ht->ht_entries[hash];

	while(p) {
		if (!ht->ht_cmpfcn(p->hte_key, key))
			return p;
		p = p->hte_chain;
	}

	/*
	 * Not found.
	 */
	return NULL;
}

/*------------------------------------------------------------------------
 * htdel - remove an object from the hashtable
 *------------------------------------------------------------------------
 */
int
htdel(struct ht *ht, unsigned int key)
{

	int			hash;
	struct htent		*p, *follow;

	hash = ht->ht_hashfcn(key, ht->ht_size);
  
	htwriterbegin(ht);

	p = ht->ht_entries[hash];
	follow = NULL;

	while(p) {
		if (!ht->ht_cmpfcn(p->hte_key, key)) {
			if (follow)
				follow->hte_chain = p->hte_chain;
			else
				ht->ht_entries[hash] = p->hte_chain;

			if (ht->ht_destroykeyfcn != NULL)
				ht->ht_destroykeyfcn(p->hte_key);
			if (ht->ht_destroyobjectfcn != NULL)
				ht->ht_destroyobjectfcn(p->hte_object);
			free(p);
			ht->ht_count--;
			htwriterend(ht);
			return OK;
		}
		follow = p;
		p = p->hte_chain;
	}
  
	/* 
	 * Not found.
	 */
	htwriterend(ht);
	return ERROR;
}

/*------------------------------------------------------------------------
 * htadd - add an object to the hash table. Returns ERROR
 * if key is already present.
 *------------------------------------------------------------------------
 */
int
htadd(struct ht *ht, unsigned int key, void *object)
{

	int			len;
	int			hash;
	struct htent		*ent, *p;

	/* 
	 * Check for key.
	 */
	htwriterbegin(ht);  
	p = htgetent(ht, key);
	if (p != NULL) {
		htwriterend(ht);
		return ERROR;
	}

	len = ht->ht_size;
	ent = (struct htent *) malloc(sizeof(struct htent));

	if (ent == NULL) {
		htwriterend(ht);
		return ERROR;
	}

	ent->hte_key = key;
	ent->hte_object = object;
	hash = ht->ht_hashfcn(key, len);

	/* 
	 * Add to front of chain.
	 */
	p = ht->ht_entries[hash];
	ent->hte_chain = p;  
	ht->ht_entries[hash] = ent;
	ht->ht_count++;
	htwriterend(ht);
	return OK;
}

/*------------------------------------------------------------------------
 * hashstring - function to generate hash value for a string.
 * Fix me! TBD: Use use better string hash function.
 *------------------------------------------------------------------------
 */
int
hashstring(unsigned int key, int len)
{

	int		i;
	int		acc = 0;
	char          *str = (char *) key;

	for (i = 0; i < strlen(str); i++)
		/*
		 * Convert to uppercase.
		 */
		acc += (str[i] >= 97 && str[i] <= 122 ? str[i] - 32 : str[i]);
  
	return acc % len;
}

/*------------------------------------------------------------------------
 * hashunsignedint - function to generate a hashvalue for an unsigned int
 * Because SSRCs are expected to be random, using value % htsize should
 * suffice as a hash function.
 *------------------------------------------------------------------------
 */
int
hashunsignedint(unsigned int key, int len)
{ 
	return key % len;
}

/*------------------------------------------------------------------------
 * htcount - return number of objects in the hashtable
 *------------------------------------------------------------------------
 */
int
htcount(struct ht *ht)
{

	int count;
	/*
	 * Return number of items in hashtable.
	 */
	htreaderbegin(ht);
	count = ht->ht_count;
	htreaderend(ht);
	return count;
}

/*------------------------------------------------------------------------
 * htenum - enumerate entries in the hashtable
 *------------------------------------------------------------------------
 */
struct htent **
htenum(struct ht *ht)
{

	struct htent	**v, *p;
	int		i;
	int		j;

	htreaderbegin(ht);
	v = (struct htent **) malloc(sizeof(struct htent *) * (ht->ht_count + 1));

	if (v == NULL) {
		htreaderend(ht);
		return NULL;
	}

	for (j = 0, i = 0; j < ht->ht_size; j++) {
		p = ht->ht_entries[j];

		while (p != NULL) {
			v[i++] = p;
			p = p->hte_chain;
		}
	}

	htreaderend(ht);

	/*
	 * Use NULL to mark end
	 */
	v[i] = NULL;
	return v;
}

/*------------------------------------------------------------------------
 * htdestroy - destroy hashtable and free all memory
 *------------------------------------------------------------------------
 */
int
htdestroy(struct ht *ht)
{

	int		j;
	struct htent *p, *q;

	if (ht == NULL)
		return ERROR;

	for (j = 0; j < ht->ht_size; j++) {
		p = ht->ht_entries[j];

		while (p != NULL) {
			q = p->hte_chain;

			/*
			 * Destroy the key and object.
			 */
			if (ht->ht_destroykeyfcn != NULL)
				ht->ht_destroykeyfcn(p->hte_key);
			if (ht->ht_destroyobjectfcn != NULL)
				ht->ht_destroyobjectfcn(p->hte_object);

			/*
			 * Free the memory from the hashtable entry.
			 */
			free(p);
			p = q;
		}
	}

	/*
	 * Free the array of pointers and ht structure.
	 */
	free(ht->ht_entries);
	free(ht);
	return OK;
}

/*------------------------------------------------------------------------
 * unsignedinteq - determine if two unsigned ints are equal
 *------------------------------------------------------------------------
 */
int
unsignedinteq(unsigned int a, unsigned int b)
{
	return !(a == b);
}