kwqhashtable.h

手机浏览器源码程序,功能强大

/*
 * Copyright (c) 2005 Nokia Corporation, Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the Nokia Corporation nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef __KWQHashTable_H_
#define __KWQHashTable_H_

#include "KWQMemArray.h"
#include <stdlib.h>
#include <string.h>
#include <oom.h>

// auxillary function
unsigned int getNextPrime(unsigned int);

#define EMPTY_PAIR			0x00000000
#define DELETED_PAIR		0xFFFFFFFF
#define IS_EMPTY(p)			((int)p==EMPTY_PAIR)
#define IS_DELETED(p)		((int)p==DELETED_PAIR)


template <typename K, typename V>
struct HashPair
{
OOM_NEW_DELETE
	K key;
	V value;
	HashPair(K k, V v) : key(k), value(v)			{}
};

template <typename K, typename V>
struct HashEntry
OOM_MODIFIED
{
	HashPair<K,V>* pair;

	HashEntry() : pair(EMPTY_PAIR)		{}
	HashEntry(K k, V v)					{ pair = new HashPair<K,V>( k, v ); }

	void remove()						{ delete pair; pair = (HashPair<K,V>*)DELETED_PAIR; }
	bool valid()						{ return ( !IS_EMPTY(pair) && !IS_DELETED(pair)); }
	bool empty()						{ return IS_EMPTY(pair); }

	K key()								{ return pair->key; }
	V value()							{ return pair->value; }
	operator bool()						{ return valid(); }
};

template <typename K, typename V>
class KWQHashTable
OOM_MODIFIED
{
public:
	class iterator
OOM_MODIFIED
	{
	public:
		iterator( KWQHashTable<K,V>* t ) : table(t), current(-1)				{}
		iterator( KWQHashTable<K,V>* t, int cur ) : table( t ), current( cur )		{}
		bool operator==( const iterator& other ) const  { return table == other.table && current == other.current; }
		bool operator!=( const iterator& other ) const  { return !(*this == other); }
		iterator& operator=( const iterator& other )	{ table = other.table; current = other.current; return *this; }
		iterator& operator++()
		{
			if( current != -1 )
			{
				unsigned int pos=current+1;
				for(; pos<table->entries.count() && !table->entries[pos]; ++pos ) {}
				if(pos == table->entries.count()) current = -1;
				else current = pos;
			}
			return *this;
		}

		K key()	const				{ return (table->entries[current]).key(); }
		V value() const				{ return (table->entries[current]).value(); }
		void remove()				{ if( current != -1 ) table->entries[current].remove(); }

	private:
		KWQHashTable<K,V>* 	table;
		int					current;
	};

	typedef unsigned int (*HashFunc)(K, unsigned int);

	// constructor & destructor
	KWQHashTable(HashFunc func_, unsigned int size_=17 )
		: hash(func_), items(0), entries( getNextPrime(size_) ), refCount( 0 )
	{
		entries.fill( HashEntry<K,V>() );
	}

	unsigned int count() const							{ return items; }
	bool operator==( const KWQHashTable& other ) const	{ return entries == other.entries && items == other.items && hash == other.hash; }

	~KWQHashTable()
	{
		clear();
	}

	bool insert( K key, V value )
	{
		int pos = probe( key, true );
		if( entries[pos] ) return false;
		entries[pos] = HashEntry<K,V>( key, value );
		if( ++items > entries.count()>>1 ) rehash();
		return true;
	}

	void remove( K key )
	{
		int pos = probe( key, false );
		if( pos == -1 ) return;
		if( entries[pos] )
		{
			entries[pos].remove();
			--items;
		}
	}

	iterator find( K key )
	{
		int pos = probe( key, false );
		if( pos == -1 || ( !entries[pos] ) )
			return iterator( this, -1 );
		return iterator( this, pos );
	}

	iterator begin()
	{
		int pos = 0;
		for(; pos<entries.count() && !entries[pos]; ++pos ) {}
		if(pos == entries.count()) pos = -1;
		return iterator(this, pos);
	}

	iterator end()		{ return iterator(this, -1); }

	void clear()
	{
		for( int i=0; i<entries.count(); ++i )
		{
			if( entries[i] )
			{
				entries[i].remove();
				entries[i].pair = EMPTY_PAIR;
			}
		}
		items = 0;
	}

private:
	// disabled functions so far
	KWQHashTable();									// not implemented
	KWQHashTable( const KWQHashTable& );			// not implemented
	KWQHashTable& operator=(const KWQHashTable& );	// not implemented

	void rehash();
	int probe( K key, bool isInsert );

	HashFunc			hash;
	unsigned int		items;
	QMemArray<HashEntry<K,V> > entries;

	unsigned int		refCount;					// for KWQRefPtr

	friend class KWQRefPtr<KWQHashTable<K,V> >;
	friend class iterator;
};

// qudratic probing: in reference to
// Robert Kruse's <Data Structures & Program Design in C>, section 8.6
template <typename K, typename V>
int KWQHashTable<K,V>::probe( K key, bool isInsert )
{
	int collision = 0;
	int pos = hash( key, entries.count() );

	if( isInsert )
	{
		while ( entries[ pos ].valid() )
		{
			pos += ++collision * 2 - 1;
			pos = pos % entries.count();
		}
	}
	else
	{
		while ( !entries[ pos ].empty() )
		{
			if( entries[ pos ].valid() && entries[ pos ].key() == key ) break;
			if( collision > entries.count() ) return -1;

			pos += ++collision * 2 - 1;
			pos = pos % entries.count();
		}
	}

	return pos;
}

template <typename K, typename V>
void KWQHashTable<K,V>::rehash()
{
	unsigned int new_size = getNextPrime( entries.count() * 2 );
	QMemArray<HashEntry<K,V> > tmp = entries;
	QMemArray<HashEntry<K,V> > new_table( new_size );
	new_table.fill( HashEntry<K,V>() );
	entries = new_table;

	for(unsigned int i=0; i<tmp.count(); ++i)
	{
		HashEntry<K,V> ele = tmp[i];
		if( ele ){
			unsigned int pos = probe( ele.key(), true );
			if( !entries[pos] ) entries[pos] = ele;
		}
	}
}

#endif // !__KWQHashTable_H_