rvhash.h

h.248协议源码

	} \
	_RvHashIter##K##T _RvHash##K##T##End(_RvHash##K##T *h) { \
		return _rvHashEnd##K##T##_; \
	} \
	_RvHashIter##K##T _RvHash##K##T##Begin(_RvHash##K##T *h) { \
		_RvHashIter##K##T iter; \
		size_t i; \
		for (i = 0; i < rvPtrVectorSize(&h->buckets); ++i) \
			if ((iter.node = *(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, i))) { \
				iter.hash = h; \
				return iter; \
			} \
		return _rvHashEnd##K##T##_; \
	} \
	void _RvHash##K##T##Resize(_RvHash##K##T* h, size_t n) { \
		void* null = (void*)NULL; \
		size_t oldSize = rvPtrVectorSize(&h->buckets); \
		if (n > oldSize) { \
			size_t newSize = _rvHashNextPrime(n); \
			size_t i; \
			RvPtrVector v; \
			rvPtrVectorConstruct(&v, rvPtrVectorGetAllocator(&h->buckets)); \
			rvPtrVectorFill(&v, newSize, &null); \
   	     	for (i = 0; i < oldSize; ++i) { \
				_RvHashNode##K##T* oldBucket = *(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, i); \
				while (oldBucket) { \
					_RvHashNode##K##T* node = oldBucket; \
					_RvHashNode##K##T** newBucket = (_RvHashNode##K##T**)rvPtrVectorAt(&v, node->index % newSize); \
					oldBucket = oldBucket->next; \
					node->next = *newBucket; \
					*newBucket = node; \
				} \
			} \
			rvPtrVectorSwap(&h->buckets, &v); \
			rvPtrVectorDestruct(&v); \
		} \
	} \
	_RvHashIter##K##T _RvHash##K##T##InsertUnique(_RvHash##K##T* h, const K* key, T* data) { \
		_RvHashIter##K##T iter; \
		_RvHashNode##K##T *tmp = NULL; \
		if (_RvHash##K##T##Find(h, key) == NULL) { \
			_RvHashNode##K##T *tmp = (_RvHashNode##K##T*)rvAllocAllocate(h->allocator, sizeof(_RvHashNode##K##T)); \
			if (tmp) { \
				_RvHashNode##K##T **first; \
				size_t index = h->hasher(key); \
				rvHashResize(K, T)(h, h->size + 1); \
				first = (_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, index % rvPtrVectorSize(&h->buckets)); \
				_RvHashNode##K##T##Construct(tmp, key, data, index, *first); \
				*first = tmp; \
				++(h->size); \
			} \
		} \
		iter.hash = h; \
		iter.node = tmp; \
		return iter; \
	} \
	_RvHashIter##K##T _RvHash##K##T##InsertEqual(_RvHash##K##T* h, const K* key, T* data) { \
		_RvHashIter##K##T iter; \
		_RvHashNode##K##T *tmp = (_RvHashNode##K##T*)rvAllocAllocate(h->allocator, sizeof(_RvHashNode##K##T)); \
		if (tmp) { \
			size_t index = h->hasher(key); \
			rvHashResize(K, T)(h, h->size + 1); \
			iter = _RvHash##K##T##FindIter(h, key); \
			if (iter.node) { \
				_RvHashNode##K##T##Construct(tmp, key, data, index, iter.node->next); \
				iter.node->next = tmp; \
			} else { \
				size_t n = rvPtrVectorSize(&h->buckets); \
				_RvHashNode##K##T **first = (_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, index % n); \
				_RvHashNode##K##T##Construct(tmp, key, data, index, *first); \
				*first = tmp; \
			} \
			++(h->size); \
		} \
		iter.hash = h; \
		iter.node = tmp; \
		return iter; \
	} \
	_RvHashIter##K##T _RvHash##K##T##Erase(_RvHash##K##T* h, _RvHashIter##K##T i) { \
		_RvHashIter##K##T nextIter = _RvHashIter##K##T##Next(i); \
		size_t n = rvPtrVectorSize(&h->buckets); \
		_RvHashNode##K##T* node = *(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, i.node->index % n); \
		if (node == i.node) { \
			*(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, i.node->index % n) = node->next; \
		} else { \
			_RvHashNode##K##T* prev = node; \
			node = node->next; \
			while (node && (node != i.node)) { \
				prev = node; \
				node = node->next; \
			} \
			if (!node) return nextIter; \
			prev->next = node->next; \
		} \
		K##Destruct(&node->key); \
		T##Destruct(&node->data); \
		rvAllocDeallocate(h->allocator, sizeof(_RvHashNode##K##T), node); \
		--(h->size); \
		return nextIter; \
	} \
	void _RvHash##K##T##EraseKey(_RvHash##K##T* h, const K* key) { \
		size_t n = rvPtrVectorSize(&h->buckets); \
		size_t index = h->hasher(key); \
		_RvHashNode##K##T* node = *(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, index % n); \
		if (node) { \
			if (K##Equal(&node->key, key)) { \
				*(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, index % n) = node->next; \
			} else { \
				_RvHashNode##K##T* prev = node; \
				node = node->next; \
				while (node && !K##Equal(&node->key, key)) { \
					prev = node; \
					node = node->next; \
				} \
				if (!node) return; \
				prev->next = node->next; \
			} \
		K##Destruct(&node->key); \
		T##Destruct(&node->data); \
		rvAllocDeallocate(h->allocator, sizeof(_RvHashNode##K##T), node); \
		--(h->size); \
		} \
	} \
	T* _RvHash##K##T##Find(_RvHash##K##T* h, const K* key) { \
		size_t n = rvPtrVectorSize(&h->buckets); \
		size_t index = h->hasher(key); \
		_RvHashNode##K##T* node = *(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, index % n); \
		for (; node; node = node->next) \
			if (K##Equal(&node->key, key)) \
				return &node->data; \
		return NULL; \
	} \
	_RvHashIter##K##T _RvHash##K##T##FindIter(_RvHash##K##T* h, const K* key) { \
		size_t n = rvPtrVectorSize(&h->buckets); \
		size_t index = h->hasher(key); \
		_RvHashIter##K##T r; \
		_RvHashNode##K##T* node = *(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, index % n); \
		for (; node; node = node->next) \
			if (K##Equal(&node->key, key)) { \
				r.hash = h; \
				r.node = node; \
				return r; \
			} \
		return _rvHashEnd##K##T##_; \
	} /* \
	RvPair(_RvHashIter##K##T, _RvHashIter##K##T) _RvHash##K##T##EqualRange(_RvHash##K##T* h, \
		K* key) { \
		RvPair(_RvHashIter##K##T, _RvHashIter##K##T) p; \
		size_t n = rvPtrVectorSize(&h->buckets); \
		size_t index = h->hasher(key); \
		_RvHashNode##K##T* node = *(_RvHashNode##K##T**)rvPtrVectorAt(&h->buckets, index % n); \
		for (; node; node = node->next) \
			if (K##Equal(&node->key, key)) { \
				p.first.hash = p.second.hash = h; \
				p.first.node = p.second.node = node; \
				while (p.second.node && K##Equal(&p.second.node->key, key)) \
					p.second.node = p.second.node->next; \
				return p; \
			} \
		p.first = p.second = _rvHashEnd##K##T##_; \
		return p; \
	} */

/* rvHashEqualRange<K, T> does not compile on Diab because of preprocessor 
bugs, so use rvHashFindIter to get the first node in the range and walk the 
iterator until either the key of the node is not the same or the end of the 
hash is reached. */

size_t _rvHashNextPrime(size_t n);

/* Public */

/* Hash */
#define RvHash(K, T)					_RvHash##K##T
#define rvHashSize(h)					((h)->size)
#define rvHashBegin(K, T)				_RvHash##K##T##Begin
#define rvHashEnd(K, T)					_RvHash##K##T##End
#define rvHashConstruct(K, T)			_RvHash##K##T##Construct
#define rvHashDestruct(K, T)			_RvHash##K##T##Destruct
#define rvHashClear(K, T)				_RvHash##K##T##Clear
#define rvHashResize(K, T)				_RvHash##K##T##Resize
#define rvHashInsertUnique(K, T)		_RvHash##K##T##InsertUnique
#define rvHashInsertEqual(K, T)			_RvHash##K##T##InsertEqual
#define rvHashErase(K, T)				_RvHash##K##T##Erase
#define rvHashEraseKey(K, T)			_RvHash##K##T##EraseKey
#define rvHashFind(K, T)				_RvHash##K##T##Find
#define rvHashFindIter(K, T)			_RvHash##K##T##FindIter
/*#define rvHashEqualRange(K, T)			_RvHash##K##T##EqualRange*/

/* Hash iterator */
#define RvHashIter(K, T)				_RvHashIter##K##T
#define rvHashIterConstructCopy(K, T)	_RvHashIter##K##T##ConstructCopy
#define rvHashIterDestruct(K, T)		_RvHashIter##K##T##Destruct
#define rvHashIterGetAllocator(K, T)	_RvHashIter##K##T##GetAllocator
#define rvHashIterSwap(K, T)			_RvHashIter##K##T##Swap
#define rvHashIterEqual(K, T)			_RvHashIter##K##T##Equal
#define rvHashIterCopy(K, T)			_RvHashIter##K##T##Copy
#define rvHashIterNext(K, T)			_RvHashIter##K##T##Next
#define rvHashIterKey(K, T)				_RvHashIter##K##T##Key
#define rvHashIterData(K, T)			_RvHashIter##K##T##Data

/*#define RvHashIterPair(K, T)			_RvHashIterPair##K##T*/

	
#endif