hash.h

hash表：用C++实现的HASH表及测试

#ifndef __HASH__H__
#define __HASH__H__
#include <string.h>

#define MAX_HASH_QUEUE_SIZE    10000

typedef struct qnode_t 
{
    struct qnode_t *prev;
    struct qnode_t *next;
    void *data;
} qnode_t;

typedef struct qc_t {
    qnode_t *head;
    qnode_t *tail;
} qc_t;

template <class qe_t>
class Hash
{
private:
    int _qsize;        /* hash key maximum size */
    qc_t *_pq;         /* pointer to hash queue */
public:
    Hash(int qsize) 
    { 
        _qsize = qsize;
	_pq = (qc_t *)malloc(_qsize * sizeof(qc_t));
	memset(_pq,0,_qsize*sizeof(qc_t));
    };
    Hash() 
    {
        _qsize = MAX_HASH_QUEUE_SIZE; 
	_pq = malloc(_qsize * sizeof(qc_t));
	memset(_pq,0,_qsize*sizeof(qc_t));
    };
    ~Hash(void);
    /* insert an element into hash queue */
    /* if success,return 0,else return -1 */
    int hashInsertElement(qe_t *pqe);
    /* delete an elemnt from hash queue */
    /* if success,return 0,else return -1 */
    int hashDeleteElement(qe_t *pqe);
    /* find the elemnt in hashqueue,if not found,return NULL */
    qe_t *hashFindElement(qe_t *pqe);
private: 
    qnode_t *hashFindNode(qe_t *pqe);
public:
    unsigned int hashKey(qe_t *pqe);
    int cmpFunc(qe_t *pqe1,qe_t *pqe2);
};

template <class qe_t> 
Hash<qe_t>::~Hash(void)
{
    if(_pq) {
        /* free all the allocated memory */
        for(int i = 0; i < _qsize; i ++) {
	    qc_t *pqc;
	    qnode_t *pnode;
	    pqc = _pq + i;
	    pnode = pqc->head;
	    while(pnode) {
	        qnode_t *p0;
		p0 = pnode;
	        pnode = pnode->next;
	        if(p0->data) free(p0->data);
		free(p0);
	    }
	}
        free(_pq);
    }
};

template <class qe_t>
int Hash<qe_t>::hashInsertElement(qe_t *pqe)
{
    qc_t *pqc;
    qnode_t *pnode;

    if(pqe == NULL) return -1;

    if((pqc = _pq + hashKey(pqe)%_qsize) == NULL) {
        fprintf(stderr,"pqc is null\n");
	return -1;
    }
    if((pnode = (qnode_t *)malloc(sizeof(qnode_t))) == NULL) {
        fprintf(stderr,"memeory limited\n");
	return -1;
    }
    if((pnode->data = (qe_t *)malloc(sizeof(qe_t))) == NULL) {
        fprintf(stderr,"memeory limited\n");
	free(pnode);
	return -1;
    }
    pnode->next = NULL;
    memcpy(pnode->data,pqe,sizeof(qe_t));

    if(pqc->head == NULL) {
        pqc->head = pqc->tail = pnode;
    } else {
        qnode_t *p;
	p = pqc->head;
	while(p->next != NULL) p = p->next;
	p->next = pnode;
	pnode->prev = p;
    }
    return 0;
};

template <class qe_t>
qnode_t *Hash<qe_t>::hashFindNode(qe_t *pqe)
{
    qc_t *pqc;
    qnode_t *pnode;

    if(pqe == NULL) return NULL;
    if((pqc = _pq + hashKey(pqe)%_qsize) == NULL) {
        fprintf(stderr,"pqc is null\n");
	return NULL;
    }
    if(pqc->head == NULL) return NULL;
    pnode = pqc->head;
    while(pnode) {
        if(cmpFunc((qe_t *)pnode->data,pqe) == 0)
	    return pnode;
        pnode = pnode->next;
    }
    return NULL;
};

template <class qe_t>
int Hash<qe_t>::hashDeleteElement(qe_t *pqe)
{
    qnode_t *pnode;
    if(pqe == NULL) return -1;
    if((pnode = hashFindNode(pqe)) == NULL) return -1;
    if(pnode->prev != NULL) {
        qnode_t *p;
	p = pnode->prev;
	p->next = pnode->next;
	if(pnode->next) (pnode->next)->prev = p;
    } else {
        qc_t *pqc;
        if((pqc = _pq + hashKey(pqe)%_qsize) == NULL) 
	    return -1;
        if(pnode->next != NULL) (pnode->next)->prev = NULL;
	pqc->head = pnode->next;
    }
    free(pnode);
    return 0;
};

template <class qe_t>
qe_t *Hash<qe_t>::hashFindElement(qe_t *pqe)
{
    qnode_t *pnode;
    if((pnode = hashFindNode(pqe)) == NULL) return NULL;
    return (qe_t *)(pnode->data);
};

#endif