[Rtk-cvs] rtk/src/core Dict.cpp,1.7,1.8

[<laz...@us...>]

Update of /cvsroot/rtk/rtk/src/core
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv32596/src/core

Modified Files:
	Dict.cpp 
Log Message:
 - Added custom key support for Dict
 - template based (T)Dict classes
 - Int / Str Dict added



Index: Dict.cpp
===================================================================
RCS file: /cvsroot/rtk/rtk/src/core/Dict.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** Dict.cpp	21 Feb 2004 10:50:48 -0000	1.7
--- Dict.cpp	7 Mar 2004 20:53:00 -0000	1.8
***************
*** 61,315 ****
  	// C/C++ code here
  
  /**
!  * T0D0: We should have some kind of check if it can't allocate sufficient memory.
!  * It will for now just set the size of table to 0 as initiator that something went wrong.
   */
!     Dict::Dict(unsigned int size)
!     {
!     	DictNode** oTmpTable;
! 		unsigned int ii;
! 		this->m_size = size;
! 		this->m_count = 0;
!         this->m_table = (DictNode **)malloc(sizeof(DictNode *) * size);
! 		oTmpTable = this->m_table;
! 		if (oTmpTable == (DictNode**)0)
! 		{
!             this->m_size = 0;
!             return; // T0D0: This part MUST be changed, and allowed better error checking!
! 		} // if
! 		for (ii=0; ii<size; ii++)
! 			oTmpTable[ii] = (DictNode*)0;
!     } // Dict()
  
! //---------------------------------------------------------------------------
  
!     unsigned int Dict::Hash(const RCHAR *string)
!     {
! 		unsigned int rv = 0;
! 		int i;
  
! 		while (*string)
! 		{
! 			i = (unsigned int)(*string);
! 			rv ^= i;
! 			rv <<= 1;
! 			string ++;
! 		} // while
!         return rv;
! 	} // Hash()
  
  //---------------------------------------------------------------------------
  
!     bool Dict::Insert(const RCHAR *key, void *data)
!     {
!     	unsigned int val = this->Hash(key) % this->m_size;
! 		DictNode *oBucket;
! 
! 		assert(NULL != key);
  
! 		/**
!          * NULL means this oBucket hasn't been used yet.  We'll simply
!          * allocate space for our new oBucket and put our data there, with
!          * the table pointing at it.
! 		 */
! 		if ((this->m_table)[val] == 0) // NULL
! 		{
! 			(this->m_table)[val] = (DictNode *)malloc(sizeof(oBucket));
! 			if ((this->m_table)[val] == 0) // NULL
! 				return (void*)0; // NULL
  
!             if (((this->m_table)[val]->key = (RCHAR*)malloc(rstrlen(key) + 1)) == 0) // NULL
!             {
!                 free((this->m_table)[val]);
!                 (this->m_table)[val] = 0; // NULL
!                 return (void*)0; // NULL
!             } // if
!             rstrcpy((this->m_table)[val]->key, key);
!             (this->m_table)[val] -> next = NULL;
!             (this->m_table)[val] -> data = data;
!             this->m_count++;
!             return true;
!           } // if
  
! 		// Check for bucket with same key.
! 		// Return false, if found
! 		oBucket = (this->m_table)[val];
! 		while(oBucket) {
! 			if( rstrcmp(key, oBucket->key) == 0)
  				return false;
! 			oBucket = oBucket->next;
  		}
  
! 		/**
!          * This key must not be in the table yet.  We'll add it to the head of
!          * the list at this spot in the hash table.  Speed would be
!          * slightly improved if the list was kept sorted instead.  In this case,
!          * this code would be moved into the loop above, and the insertion would
!          * take place as soon as it was determined that the present key in the
!          * list was larger than this one.
!          */
! 		oBucket = (DictNode *)malloc(sizeof(oBucket));
! 		if (oBucket == 0) // NULL
! 			return false;
! 		if ((oBucket->key = (RCHAR*)malloc(rstrlen(key)+1)) == 0) // NULL
! 		{
! 			free(oBucket);
! 			return false;
! 		}
! 		rstrcpy(oBucket->key, key);
! 		oBucket->data = data;
!         oBucket->next = (this->m_table)[val];
! 		(this->m_table)[val] = oBucket;
! 		this->m_count++;
  
! 		return true;
!     } // Insert()
  
  //---------------------------------------------------------------------------
  
! 	void *Dict::Replace(const RCHAR *key, void *data, bool insert)
! 	{
! 		unsigned int val = this->Hash(key) % this->m_size;
! 		DictNode *oBucket;
  
! 		oBucket = (this->m_table)[val];
! 		while(oBucket) {
! 			if( rstrcmp(key, oBucket->key) == 0) {
! 				void *old_data = oBucket->data;
! 				oBucket->data = data;
! 				return old_data;
! 			}
! 			oBucket = oBucket->next;
  		}
! 		if(!insert) return NULL;
! 		Insert(key, data);
! 		return data;
  	}
  
  //---------------------------------------------------------------------------
  
!     void* Dict::Lookup(const RCHAR *key) const
!     {
! 		unsigned int val = this->Hash(key) % this->m_size;
! 		DictNode *oBucket;
  
! 		assert(NULL != key);
  
! 		if ((this->m_table)[val] == 0) // NULL
! 			return NULL;
! 		for (oBucket = (this->m_table)[val]; oBucket != 0; oBucket = oBucket->next )
! 		{
! 			if (0 == rstrcmp(key, oBucket->key))
! 				return oBucket->data;
! 		}
! 		return (void*)0;
!     } // Lookup()
  
! //---------------------------------------------------------------------------
  
!     void* Dict::Delete(RCHAR* key)
!     {
!     	unsigned int val = this->Hash(key) % this->m_size;
! 		void* data;
!         DictNode *ptr, *last = 0;
  
! 		assert (key != 0); // NULL
  
! 		if ((this->m_table)[val] == 0) // NULL
! 			return 0;
  
! 		/**
!          * List traversal.
!          * When we find DictNode to delete, we set the previous node's 'next' pointer
!          * to point to the node after found DictNode. After that we can safely delete
!          * found DictNode.
!          */
! 		for (last = 0, ptr = (this->m_table)[val];
! 			ptr != 0;
! 			last = ptr, ptr = ptr->next)
  		{
! 			if (rstrcmp(key, ptr->key) == 0)
! 			{
! 				if (last != 0)
! 				{
! 					data = ptr->data;
! 					last -> next = ptr -> next;
!                     free(ptr->key);
! 					free(ptr);
! 					this->m_count--;
! 					return data;
! 				} // if
! 				else
! 				{
! 					/**
!                      * If 'last' pointer is still NULL than we have to delete first
!                      * node in the list. All we have to do is to put 'next' pointer
!                      * of found DictNode in the array. After that we delete current
!                      * DictNode as above.
!                      */
! 					data = ptr->data;
!                     (this->m_table)[val] = ptr->next;
!                     free(ptr->key);
!                     free(ptr);
!                     this->m_count--;
! 					return data;
! 				} // else
! 			} // if
!         } // for
! 		// We didn't find key in the table - return NULL.
!         return (void*)0;
! 	} // Delete()
  
  //---------------------------------------------------------------------------
  
! 	int Dict::FreeNode(RCHAR *key, void *data)
!     {
! 		(void) data;
! 
! 		assert(key != 0); // NULL
  
! 		if (this->m_free_func != 0) // NULL
  		{
! 			this->m_free_func(this->Delete(key));
  		}
! 		else
!         	this->Delete(key);
!         return 0; // everything is OK
!     } // FreeNode
  
  //---------------------------------------------------------------------------
  
!     void Dict::Clear()
!     {
  
! 		this->m_count = 0;
!         // this->m_free_func = 0;
! 		this->m_table = 0;
!     } // Clear
  
! //---------------------------------------------------------------------------
  
! 	void Dict::Enumerate(DictEnumFunc func, void *user_data)
!     {
! 		unsigned ii;
! 		DictNode *temp;
!         DictNode *swap;
  
! 		for (ii=0; ii<this->m_size; ii++)
! 		{
! 			if (this->m_table[ii] != 0) // NULL
! 			{
! 				temp = this->m_table[ii];
! 				while (temp != 0) // NULL
! 				{
! 					swap = temp->next;
! 					(*func)(temp->key, temp->data, user_data);
! 					temp = swap;
! 				} // while
! 			} // if
! 		} // for
!     } // Enumerate()
  
! //---------------------------------------------------------------------------
  
  }; // Rtk
--- 61,379 ----
  	// C/C++ code here
  
+ #define FREEDATA(d)	if(_free_func) (*_free_func)(d)
+ 
+ #define COPYKEY(dst, src)	if(_keycopy_func) dst = (*_keycopy_func)(src); else dst = src
+ #define FREEKEY(d)	if(_keyfree_func) (*_keyfree_func)(d)
+ 
+ #define FREENODE(node) \
+ 	FREEDATA(node->data); \
+ 	FREEKEY(node->key); \
+ 	free(node)
+ 
  /**
!  * Internal method to test if a positive number is prime.
!  * Not an efficient algorithm.
   */
! static bool is_prime(int n)
! {
!     if( n == 2 || n == 3 ) return true;
!     if( n == 1 || n % 2 == 0 ) return false;
!     for( int i = 3; i * i <= n; i += 2 )
!         if( n % i == 0 )
!             return false;
!     return true;
! }
  
! /**
!  * Internal method to return a prime number at least as large as n.
!  * Assumes n > 0.
!  */
! static int next_prime(int n)
! {
!     if( n % 2 == 0 ) n++;
!     for( ; !is_prime(n); n += 2 );
!     return n;
! }
  
! Dict::Dict(KeyCopyFunc keycopy_f, KeyFreeFunc keyfree_f, KeyCmpFunc keycmp_f, HashFunc hash_f, FreeDataFunc free_f, uint size)
! 	: _keycopy_func(keycopy_f), _keyfree_func(keyfree_f), _keycmp_func(keycmp_f), _hash_func(hash_f), _free_func(free_f)
! {
! 	_size = next_prime(size);
! 	_count = 0;
! 	
! 	_table = (DictNode **)malloc(sizeof(DictNode*) * _size);
! 	memset(_table, 0, sizeof(DictNode*) * _size);
! }
  
! Dict::~Dict() 
! {
! 	Clear();
! 	free(_table);
! }
  
  //---------------------------------------------------------------------------
  
! bool Dict::Insert(void *key, void *data, bool replace)
! {
! 	uint val = Hash(key);
! 	DictNode *oBucket;
  
! 	/**
! 	* NULL means this oBucket hasn't been used yet.  We'll simply
!     * allocate space for our new oBucket and put our data there, with
!     * the table pointing at it.
! 	*/
! 	if(_table[val] == 0) // NULL
! 	{
! 		oBucket = (DictNode *)malloc(sizeof(DictNode));
! 		COPYKEY(oBucket->key, key);
!         oBucket->next = NULL;
!         oBucket->data = data;
! 		_table[val] = oBucket;
!         _count++;
  
!         return true;
! 	} // if
  
! 	// Check for bucket with same key.
! 	// Return false, if found
! 	oBucket = _table[val];
! 	while(oBucket) {
! 		if( (*_keycmp_func)(key, oBucket->key) ) {
! 			if(replace) {
! 				FREEDATA(oBucket->data);
! 				oBucket->data = data;
! 				return true;
! 			} else {
  				return false;
! 			}
  		}
+ 		oBucket = oBucket->next;
+ 	}
  
! 	/**
!      * This key must not be in the table yet.  We'll add it to the head of
!      * the list at this spot in the hash table.  Speed would be
!      * slightly improved if the list was kept sorted instead.  In this case,
!      * this code would be moved into the loop above, and the insertion would
!      * take place as soon as it was determined that the present key in the
!      * list was larger than this one.
!      */
! 	oBucket = (DictNode *)malloc(sizeof(DictNode));
! 	COPYKEY(oBucket->key, key);
! 	oBucket->data = data;
!     oBucket->next = _table[val];
! 	_table[val] = oBucket;
! 	_count++;
  
! 	return true;
! } // Insert()
  
  //---------------------------------------------------------------------------
  
! void *Dict::Replace(void *key, void *data, bool insert)
! {
! 	uint val = Hash(key);
! 	DictNode *oBucket;
  
! 	oBucket = _table[val];
! 	while(oBucket) {
! 		if( (*_keycmp_func)(key, oBucket->key) ) {
! 			void *old_data = oBucket->data;
! 			oBucket->data = data;
! 			return old_data;
  		}
! 		oBucket = oBucket->next;
  	}
+ 	if(!insert) return NULL;
+ 	Insert(key, data);
+ 	return data;
+ }
  
  //---------------------------------------------------------------------------
  
! void *Dict::Lookup(void *key) const
! {
! 	uint val = Hash(key);
! 	DictNode *oBucket;	
  
! 	assert(NULL != key);
  
! 	if (_table[val] == 0) // NULL
! 		return NULL;
  
! 	for (oBucket = _table[val]; oBucket != 0; oBucket = oBucket->next )
! 	{
! 		if ( (*_keycmp_func)(key, oBucket->key) )
! 			return oBucket->data;
! 	}
! 	return (void*)0;
! }
  
! //---------------------------------------------------------------------------
  
! bool Dict::Delete(void *key)
! {
! 	uint val = Hash(key);
! 	DictNode *ptr, *last = 0;
  
! 	if (_table[val] == 0) // NULL
! 		return 0;
  
! 	/**
!       * List traversal.
!       * When we find DictNode to delete, we set the previous node's 'next' pointer
!       * to point to the node after found DictNode. After that we can safely delete
!       * found DictNode.
!       */
! 	for (last = 0, ptr = _table[val];
! 		ptr != 0;
! 		last = ptr, ptr = ptr->next)
! 	{
! 		if ( (*_keycmp_func)(key, ptr->key) )
  		{
! 			if (last != 0) {
! 				last->next = ptr->next;
! 			} else {
! 				/**
!                   * If 'last' pointer is still NULL than we have to delete first
!                   * node in the list. All we have to do is to put 'next' pointer
!                   * of found DictNode in the array. After that we delete current
!                   * DictNode as above.
!                   */
!                 _table[val] = ptr->next;
! 			}
! 			FREENODE(ptr);                
!             _count--;
! 			return true;
! 		} // if
! 	} // for
! 	
! 	// We didn't find key in the table - return false.
!     return false;
! }
  
  //---------------------------------------------------------------------------
  
! void Dict::Clear()
! {
! 	DictNode *temp;
! 	DictNode *swap;
! 	uint n = _size;
  
! 	while(n--)
! 	{
! 		temp = _table[n];
! 		while(temp != 0)
  		{
! 			swap = temp->next;
! 			FREENODE(temp);
! 			temp = swap;
  		}
! 		_table[n] = 0;
! 	}
! 
! 	_count = 0;
! }
  
  //---------------------------------------------------------------------------
  
! void Dict::Enumerate(DictEnumFunc func, void *user_data)
! {
! 	uint ii;
! 	DictNode *temp;
  
! 	for (ii=0; ii<_size; ii++)
! 	{
! 		temp = _table[ii];
! 		while (temp != 0)
! 		{
! 			(*func)(temp->key, temp->data, user_data);
! 			temp = temp->next;
! 		}
! 	}
! }
  
! /**************************************************/
! /**************************************************/
  
! uint StrDict::Hash(void *key)
! {
! 	const RCHAR *string = ((const String *)key)->c_str();
! 	uint rv = 0;
! 	int i;
  
! 	while (*string)
! 	{
! 		i = (unsigned int)(*string);
! 		rv ^= i;
! 		rv <<= 1;
! 		string++;
! 	} // while
  
! 	return rv;
! }
! 
! void *StrDict::KeyCopy(void *key)
! {
! 	return new String(*(String*)key);
! }
! 
! void StrDict::KeyFree(void *key)
! {
! 	delete ((String*)key);
! }
! 
! bool StrDict::KeyCmp(void *i1, void *i2)
! {
! 	String &s1 = *(String *)i1;
! 	String &s2 = *(String *)i2;
! 	return (s1==s2);
! }
! 
! StrDict::StrDict(uint size)
! : Dict(StrDict::KeyCopy, StrDict::KeyFree, StrDict::KeyCmp, StrDict::Hash, 0, size)
! {
! 
! }
! 
! /**************************************************/
! /**************************************************/
! 
! uint IntDict::Hash(void *key)
! {
! 	int ikey = *(int*)key;
!     ikey += ~(ikey << 15);
!     ikey ^=  (ikey >> 10);
!     ikey +=  (ikey << 3);
!     ikey ^=  (ikey >> 6);
!     ikey += ~(ikey << 11);
!     ikey ^=  (ikey >> 16);
!     if(ikey < 0) ikey = -ikey;
!     return ikey;
! }
! 
! void *IntDict::KeyCopy(void *key)
! {
! 	return new int(*(int*)key);
! }
! 
! void IntDict::KeyFree(void *key)
! {
! 	delete ((int*)key);
! }
! 
! bool IntDict::KeyCmp(void *i1, void *i2)
! {
! 	int &s1 = *(int*)i1;
! 	int &s2 = *(int*)i2;
! 	return (s1==s2);
! }
! 
! IntDict::IntDict(uint size)
! : Dict(IntDict::KeyCopy, IntDict::KeyFree, IntDict::KeyCmp, IntDict::Hash, 0, size)
! {
! 
! }
  
  }; // Rtk