Extern "C"
	Declare Function crt_memcpy Alias "memcpy"(As Any Ptr,As Any Ptr, As Integer) As Any Ptr
End Extern

#macro MHashTemplate(_mk_ , _mv_)
	
	'-------- set type for key and value -----
	#ifndef HASHTYPEKEY##_mk_##_mv_
		Type HASHTYPEKEY##_mk_##_mv_ As _mk_
	#endif
	#ifndef HASHTYPEVALUE##_mk_##_mv_
		Type HASHTYPEVALUE##_mk_##_mv_ As _mv_
	#endif
	
	'-----------------------------------------
	#ifndef THASHDATA##_mk_##_mv_
		Type THASHDATA##_mk_##_mv_
			
			pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr = 0
			
			pszValue As HASHTYPEVALUE##_mk_##_mv_ Ptr = 0
			
		End Type
		
		Type TLIST##_mk_##_mv_ Extends THASHDATA##_mk_##_mv_
			
			As TLIST##_mk_##_mv_ Ptr p = 0
			
		End Type
		
		Type TGLLIST##_mk_##_mv_
			
			As TLIST##_mk_##_mv_ Ptr pFirst = 0
			
			As TLIST##_mk_##_mv_ Ptr pEnd = 0
			
			Declare Sub add_last (pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr , pszValue As HASHTYPEVALUE##_mk_##_mv_ Ptr)
			
			Declare Sub delete_element (pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr)
			
			Declare Function get_element ( pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr) As TLIST##_mk_##_mv_ Ptr
			
		End Type
		
		Sub TGLLIST##_mk_##_mv_.add_last (pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr , pszValue As HASHTYPEVALUE##_mk_##_mv_ Ptr)
			
			Dim As TLIST##_mk_##_mv_ Ptr nw = Allocate(Sizeof(TLIST##_mk_##_mv_))
			
			If nw = 0 Then Exit Sub
			
			nw->pszKey = pszKey
			
			nw->pszValue = pszValue
			
			nw->p = 0
			
			If pFirst = 0 Then
				
				pFirst = nw
				
				pEnd = pFirst
				
			Else
				
				pEnd->p = nw
				
				pEnd = nw
				
			Endif
			
		End Sub
		
		Sub TGLLIST##_mk_##_mv_.delete_element (pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr)
			
			Dim As TLIST##_mk_##_mv_ Ptr pTemp = pFirst, pTempOld
			
			pTempOld = pTemp
			
			While pTemp
				
				If *(pTemp->pszKey) = *pszKey Then
					
					If pTemp->p <> 0 Then
						
						If pTemp = pFirst Then
							
							pFirst = pTemp->p
							
						Else
							
							pTempOld->p = pTemp->p
							
						Endif
						
					Else
						
						If pTemp = pFirst Then
							
							pFirst = 0
							
							pEnd = 0
							
						Else
							
							pTempOld->p = 0
							
							pEnd = pTempOld
							
						Endif
						
					Endif
					
					Deallocate(pTemp->pszKey)
					
					#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
					#else           
						Deallocate(pTemp->pszValue)
					#endif
					
					Deallocate(pTemp)
					
					Exit While
					
				Endif
				
				pTempOld = pTemp
				
				pTemp = pTemp->p
				
			Wend
			
		End Sub
		
		Function TGLLIST##_mk_##_mv_.get_element ( pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr) As TLIST##_mk_##_mv_ Ptr
			
			Dim As TLIST##_mk_##_mv_ Ptr pTemp = pFirst
			
			Dim As Long iLen = Len(*pszKey)
			
			While pTemp
				
				If Len(*(pTemp->pszKey)) = iLen Andalso *(pTemp->pszKey) = *pszKey Then
					
					Return pTemp
					
				Endif
				
				pTemp = pTemp->p
				
			Wend
			
		End Function
		
		Type THASHITEM##_mk_##_mv_ Extends THASHDATA##_mk_##_mv_
			
			pList As TGLLIST##_mk_##_mv_ Ptr
			
			iFdelete As Long
			
		End Type
		
		Type THASHTABLE##_mk_##_mv_
			
			pArray As THASHITEM##_mk_##_mv_ Ptr
			
			iCountItem As Ulong
			
			iSize As Ulong
			
			Declare Constructor()
			
			Declare Sub deleteitem(pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr)
			
			Declare Sub cleartable()
			
			Declare Sub freetable()
			
			Declare Function count() As Long
			
			Declare Function size() As Long
			
			Declare Sub insert(pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr , pszValue As HASHTYPEVALUE##_mk_##_mv_ Ptr)
			
			Declare Sub add_rehash(pNew As THASHITEM##_mk_##_mv_ Ptr , pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr , pszValue As HASHTYPEVALUE##_mk_##_mv_ Ptr)
			
			Declare Function find(pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr) As HASHTYPEVALUE##_mk_##_mv_ Ptr
			
			Declare Function hash_horner(psz As HASHTYPEKEY##_mk_##_mv_ Ptr) As Long
			
			Declare Sub rehash()
			
		End Type
		
		Constructor THASHTABLE##_mk_##_mv_()
			
			iCountItem = 0
			
			iSize = 64
			
			pArray = Callocate(Sizeof(THASHITEM##_mk_##_mv_)*(iSize+4))
			
		End Constructor
		
		Sub THASHTABLE##_mk_##_mv_.deleteitem(pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr)
			
			Dim As Long iIndex = hash_horner(pszKey)
			
			If pArray[iIndex].pszKey Then
				
				If pArray[iIndex].iFdelete = 0 Andalso *(pArray[iIndex].pszKey) = *pszKey Then
					
					Deallocate(pArray[iIndex].pszKey)
					
					#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
					#else
						Deallocate(pArray[iIndex].pszValue)
					#endif
					
					pArray[iIndex].iFdelete = 1
					
				Else
					
					If pArray[iIndex].pList Then
						
						pArray[iIndex].pList->delete_element(pszKey)
						
					Endif
					
				Endif
				
				iCountItem-=1
				
				If iCountItem*4 < iSize Then
					
					rehash()
					
				Endif
				
			Endif
			
		End Sub
		
		Sub THASHTABLE##_mk_##_mv_.cleartable()
			
			For i As Long = 0 To iSize
				
				If pArray[i].pszKey Then
					
					If pArray[i].iFdelete = 0 Then
						
						Deallocate(pArray[i].pszKey)
						
						#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
						#else
							Deallocate(pArray[i].pszValue)
						#endif
						
						pArray[i].pszKey = 0
						
						pArray[i].pszValue = 0
						
					Endif
					
					If pArray[i].pList Then
						
						Dim As TLIST##_mk_##_mv_ Ptr pTemp , pTemp2
						
						pTemp = pArray[i].pList->pFirst
						
						pTemp2 = pArray[i].pList->pFirst
						
						While pTemp
							
							pTemp2 = pTemp->P
							
							Deallocate(pTemp->pszKey)
							
							#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
							#else
								Deallocate(pTemp->pszValue)
							#endif
							
							Deallocate(pTemp)
							
							pTemp = pTemp2
							
						Wend
						
						Deallocate(pArray[i].pList)
						
						pArray[i].pList = 0
						
					Endif
					
				Endif
				
			Next
			
			iCountItem = 0
			
			rehash()
			
		End Sub
		
		Sub THASHTABLE##_mk_##_mv_.freetable()
			
			cleartable()
			
			Deallocate(pArray)
			
		End Sub
		
		Function THASHTABLE##_mk_##_mv_.count() As Long
		    Return iCountItem
		End Function
		
		Function THASHTABLE##_mk_##_mv_.size() As Long
		    Return iSize
		End Function		
		
		Sub THASHTABLE##_mk_##_mv_.insert(pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr , pszValue As HASHTYPEVALUE##_mk_##_mv_ Ptr)
			
			If pszKey = 0 Orelse pszValue = 0 Then
				
				? "Invalidate value!"
				
				Exit Sub
				
			Endif
			
			If iCountItem > (iSize Shr 1) Andalso iCountItem < 32770 Then
				
				reHash()
				
			Endif
			
			Dim As Long iIndex = hash_horner(pszKey)
			
			If pArray[iIndex].pszKey = 0 Orelse pArray[iIndex].iFdelete Then
				
				pArray[iIndex].pszKey = Allocate((Len(*pszKey)+1)*Sizeof(HASHTYPEKEY##_mk_##_mv_))
				
				*(pArray[iIndex].pszKey) = *pszKey
				
				#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
					pArray[iIndex].pszValue = pszValue
				#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Wstring)
					pArray[iIndex].pszValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					*(pArray[iIndex].pszValue) = *pszValue
				#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Zstring)
					pArray[iIndex].pszValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					*(pArray[iIndex].pszValue) = *pszValue      
				#else
					pArray[iIndex].pszValue = Allocate(Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					crt_memcpy(pArray[iIndex].pszValue , pszValue , Sizeof(HASHTYPEVALUE##_mk_##_mv_))
				#endif
				
				If pArray[iIndex].iFdelete Then pArray[iIndex].iFdelete = 0
				
			Else
				
				If *(pArray[iIndex].pszKey) = *pszKey Then
					#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Zstring)
						If pArray[iIndex].pszValue Then Deallocate(pArray[iIndex].pszValue)
						pArray[iIndex].pszValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
						*(pArray[iIndex].pszValue) = *pszValue
					#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Wstring) 
						If pArray[iIndex].pszValue Then Deallocate(pArray[iIndex].pszValue)
						pArray[iIndex].pszValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
						*(pArray[iIndex].pszValue) = *pszValue              
					#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
						pArray[iIndex].pszValue = pszValue
					#else
						If pArray[iIndex].pszValue Then Deallocate(pArray[iIndex].pszValue)
						pArray[iIndex].pszValue = Allocate(Sizeof(HASHTYPEVALUE##_mk_##_mv_))
						crt_memcpy(pArray[iIndex].pszValue , pszValue , Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					#endif
					
					Exit Sub
					
				Endif
				
				Dim As TLIST##_mk_##_mv_ Ptr pPrevData
				
				If pArray[iIndex].pList = 0 Then
					
					pArray[iIndex].pList = Callocate(Sizeof(TGLLIST##_mk_##_mv_))
					
				Else
				
					pPrevData = pArray[iIndex].pList->get_element(pszKey)
					
					If pPrevData Then
						
						#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
							pPrevData->pszValue = pszValue
						#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Wstring)
							If pPrevData->pszValue Then Deallocate(pPrevData->pszValue)
							pPrevData->pszValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
							*(pPrevData->pszValue) = *pszValue
						#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Zstring)
							If pPrevData->pszValue Then Deallocate(pPrevData->pszValue)
							pPrevData->pszValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
							*(pPrevData->pszValue) = *pszValue 
						#else
							If pPrevData->pszValue Then Deallocate(pPrevData->pszValue)
							pPrevData->pszValue = Allocate(Sizeof(HASHTYPEVALUE##_mk_##_mv_))
							crt_memcpy(pPrevData->pszValue , pszValue , Sizeof(HASHTYPEVALUE##_mk_##_mv_))
						#endif
						
						Exit Sub
						
					Endif
					
				Endif
				
				Dim As HASHTYPEKEY##_mk_##_mv_ Ptr pTempKey = Allocate((Len(*pszKey)+1)*Sizeof(HASHTYPEKEY##_mk_##_mv_))
				
				*pTempKey = *pszKey
				
				#if Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Any)
					pArray[iIndex].pList->add_last(pTempKey , pszValue)
				#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Wstring)
					Dim As HASHTYPEVALUE##_mk_##_mv_ Ptr pTempValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					*pTempValue = *pszValue
					pArray[iIndex].pList->add_last(pTempKey , pTempValue)
				#elseif Typeof(HASHTYPEVALUE##_mk_##_mv_) = Typeof(Zstring)
					Dim As HASHTYPEVALUE##_mk_##_mv_ Ptr pTempValue = Allocate((Len(*pszValue)+1)*Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					*pTempValue = *pszValue
					pArray[iIndex].pList->add_last(pTempKey , pTempValue)   
				#else
					Dim As HASHTYPEVALUE##_mk_##_mv_ Ptr pTempValue = Allocate(Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					crt_memcpy(pTempValue , pszValue , Sizeof(HASHTYPEVALUE##_mk_##_mv_))
					pArray[iIndex].pList->add_last(pTempKey , pTempValue)
				#endif
				
			Endif
			
			iCountItem+=1
			
		End Sub
		
		Sub THASHTABLE##_mk_##_mv_.add_rehash(pNew As THASHITEM##_mk_##_mv_ Ptr , pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr , pszValue As HASHTYPEVALUE##_mk_##_mv_ Ptr)
			
			Dim As Long iIndex = hash_horner(pszKey)
			
			If pNew[iIndex].pszKey = 0 Then
				
				pNew[iIndex].pszKey = pszKey
				
				pNew[iIndex].pszValue = pszValue
				
			Else
				
				If pNew[iIndex].pList = 0 Then
					
					pNew[iIndex].pList = Callocate(Sizeof(TGLLIST##_mk_##_mv_))
					
				Endif
				
				pNew[iIndex].pList->add_last(pszKey , pszValue)
				
			Endif
			
		End Sub
		
		Function THASHTABLE##_mk_##_mv_.find(pszKey As HASHTYPEKEY##_mk_##_mv_ Ptr) As HASHTYPEVALUE##_mk_##_mv_ Ptr
			
			If pszKey = 0 Then
				
				? "Invalidate value!"
				
				Return 0
				
			Endif
			
			Dim As Long iIndex = hash_horner(pszKey)
			
			If (pArray[iIndex].pszKey Andalso pArray[iIndex].iFdelete = 0) Andalso *(pArray[iIndex].pszKey) = *pszKey Then
				
				Return pArray[iIndex].pszValue
				
			Else
				
				If pArray[iIndex].pList Then
					
					Dim As TLIST##_mk_##_mv_ Ptr p = pArray[iIndex].pList->get_element(pszKey)
					
					If p Then
						
						Return p->pszValue
						
					Else
						
						Return 0
						
					Endif
					
				Endif
				
			Endif
			
		End Function
		
		Function THASHTABLE##_mk_##_mv_.hash_horner(psz As HASHTYPEKEY##_mk_##_mv_ Ptr) As Long
			
			Dim As Ulong iResult
			
			For i As Long = 0 To Len(*psz)-1
				
				iResult = (11 * iResult + (*psz)[i]) 
				
			Next
			
			Return iResult Mod iSize
			
		End Function
		
		Sub THASHTABLE##_mk_##_mv_.rehash()
			
			Dim As Long iOldSize = iSize
			
			If iCountItem > 32768 Then
				
				iSize = 131072
				
			Elseif iCountItem > 16384 Then
				
				iSize = 65536
				
			Elseif iCountItem > 8192 Then
				
				iSize = 32768
				
			Elseif iCountItem > 4096 Then
				
				iSize = 16384
				
			Elseif iCountItem > 2048 Then
				
				iSize = 8192
				
			Elseif iCountItem > 1024 Then
				
				iSize = 4096
				
			Elseif iCountItem > 512 Then
				
				iSize = 2048
				
			Elseif iCountItem > 256 Then
				
				iSize = 1024
				
			Elseif iCountItem > 128 Then
				
				iSize = 512
				
			Elseif iCountItem > 64 Then
				
				iSize = 256
				
			Elseif iCountItem > 32 Then
				
				iSize = 128
				
			Elseif iCountItem > 16 Then
				
				iSize = 64
				
			Endif
			
			Dim As THASHITEM##_mk_##_mv_ Ptr pNew = Callocate(Sizeof(THASHITEM##_mk_##_mv_)*(iSize+4))
			
			For i As Long = 0 To iOldSize
				
				If pArray[i].pszKey Then
					
					If pArray[i].iFdelete = 0 Then
						
						add_rehash(pNew , pArray[i].pszKey , pArray[i].pszValue)
						
					Endif
					
					If pArray[i].pList Then
						
						Dim As TLIST##_mk_##_mv_ Ptr pTemp = pArray[i].pList->pFirst , pTemp2
						
						While pTemp
							
							add_rehash(pNew , pTemp->pszKey , pTemp->pszValue)
							
							pTemp2 = pTemp->P
							
							Deallocate(pTemp)
							
							pTemp = pTemp2
							
						Wend
						
						Deallocate(pArray[i].pList)
						
					Endif
					
				Endif
				
			Next
			
			Deallocate(pArray)
			
			pArray = pNew
			
		End Sub
	#endif
#endmacro
