Keyed Linked List / Hash Table (32-bit and 64 bit)

[PaulSquires]

Keyed Linked List

Example test program for Keyed Linked List

Code: Select all

#Include Once "windows.bi"
#Include Once "clsKeyList.bas"


'  Create the actual list. By default the class creates a list
'  large enough to hold 20 items. Once that limit is reached, the
'  list will grow in size by another 20 items, etc. You can control
'  how much to grow the list by either through the constructor
'  or by using the GrowBy property.
'
'        Dim cList As clsKeyList = 100    ' allow list to grow by 100 items
'        - or -
'        cList.GrowBy = 100
'
'
'  Keys must be unique otherwise the data of the found key simply gets updated 
'  with the new information rather than added.
'   
'  The class allows you add items as either String, Integer, Double or
'  any arbitrary memory location and size. This is accomplished by the class
'  simply overloading the AddItem function call.
'
'        cList.Additem( "1000", 32456 )      ' <-- add an integer with a key of "1000"
'        cList.Additem( "1000", @e, len(e))  ' <-- add an EMPLOYEE_TYPE structure/record held 
'                                                  in variable "e" With a Key of "1000"
'
'  You can use the convenience class property GetKeyString(i) to retrieve the key for the 
'  current active node. 
'  Data values can be retrieved using several convenience properties depending on the
'  type of data being stored. 
'        cList.GetDataString(i)   ' Retrieves a string (based on zstring or wstring stored data)
'                                 ' If an integer or double is stored in the data area then that
'                                 ' value is returned in string format.
'        cList.GetDataInteger(i)  ' Retrieves an integer
'        cList.GetDataDouble(i)   ' Retrieves a double
'  There is no convenience property to retrieve unstructured data stored in the node. You must
'  maniuplate the node.pData as you require.
'

Dim cList As clsKeyList 
Dim node  As clsListNode 
Dim i     As Integer
       
With cList
   .AddItem( "1",  "Paul Squires" )
   .AddItem( "2",  "Harry Potter" )
   .AddItem( "3",  "Lord Voldemort" )
   .AddItem( "4",  "Ron Weasley" )
   .AddItem( "5",  "Hermione Granger" )
   .AddItem( "6",  "Albus Dumbledore" )
   .AddItem( "7",  "Bellatrix Lestrange" )
   .AddItem( "8",  "Hedwig" )
   .AddItem( "9",  "Tom Riddle" )
   .AddItem( "10", "Sirius Black" )
End With

'  Print the list of items. This demonstrates how to retieve items based 
'  on their index position. Retrieval is very fast (as fast as array access).
?
? "Print the keys and the strings held in the list."
For i = 0 To cList.Count - 1          
   If cList.GetByIndex(i) Then
      ' if we needed to manipulate the node data directly then we would
      ' call the GetNode property. In this case, we do not need to.
      'node = cList.GetNode(i)
      ? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)
   End If   
Next


'  Retrieve a list item using its key value. This method is a little slower 
'  because a linear search must be performed on the list in order to match the
'  key value. For much faster access (especially if the list is large) consider 
'  using the clsHashTable class. That class provides almost instant access to
'  keys and their associated data with the downside of being having little more
'  memory usage.                                                   
?
? "Get using Key = 5";
If cList.GetByKey("5") Then
   ' if we needed to manipulate the node data directly then we would
   ' call the GetNode property. In this case, we do not need to.
   'node = cList.GetNode(i)
   ? " FOUND Key: "; cList.GetKeyString, "Data: "; cList.GetDataString  
Else
   ? " KEY NOT FOUND"
End If


?
? "Get using Key = 999999";
If cList.GetByKey("999999") Then
   ' if we needed to manipulate the node data directly then we would
   ' call the GetNode property. In this case, we do not need to.
   'node = cList.GetNode(i)
   ? " FOUND Key: "; cList.GetKeyString, "Data: "; cList.GetDataString
Else
   ? " KEY NOT FOUND"
End If


?
? "Delete Key = 3";
If cList.DeleteByKey("3") Then
   ? " FOUND and DELETED"
Else
   ? " NOT FOUND"
End If    


'  Keys must be unique in a list. If you try to add data and the key already
'  exists then the new data simply replaces the old. This is a very fast way
'  of updating an existing list item.
?
? "Change the string held in key = 4"
cList.AddItem( "4", "The text in this item has been updated.")


?
? "Print the keys and the strings held in the list."
For i = 0 To cList.Count - 1          
   If cList.GetByIndex(i) Then
      ' if we needed to manipulate the node data directly then we would
      ' call the GetNode property. In this case, we do not need to.
      'node = cList.GetNode(i)
      ? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)  
   End If   
Next
?

cList.ClearList    ' Clear the list so that we can re-use it again if we wish

?
? "Create an Integer list"
With cList
   .AddItem( "1",  100 )
   .AddItem( "2",  200 )
   .AddItem( "3",  300 )
   .AddItem( "4",  400 )
End With

?
? "Print the keys and the integers held in the list."
For i = 0 To cList.Count - 1          
   If cList.GetByIndex(i) Then
      ' if we needed to manipulate the node data directly then we would
      ' call the GetNode property. In this case, we do not need to.
      'node = cList.GetNode(i)

      ' Get the raw Integer value using cList.GetDataInteger. For display
      ' purposes we can call cList.GetDataString(i) which does the conversion to
      ' string for us.
      ? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)
   End If   
Next
?

cList.ClearList    ' Clear the list so that we can re-use it again if we wish

?
? "Create a Double list"
With cList
   .AddItem( "1",  14521.5879 )
   .AddItem( "2",  547.4754 )
   .AddItem( "3",  548968.77 )
   .AddItem( "4",  98487456.436 )
End With

?
? "Print the keys and the doubles held in the list."
For i = 0 To cList.Count - 1          
   If cList.GetByIndex(i) Then
      ' if we needed to manipulate the node data directly then we would
      ' call the GetNode property. In this case, we do not need to.
      'node = cList.GetNode(i)

      ' Get the raw Double value using cList.GetDataDouble. For display
      ' purposes we can call cList.GetDataString(i) which does the conversion to
      ' string for us.
      ? "Index:"; i, "Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)
   End If   
Next
?


? "Done."

Sleep
                    

Keyed Linked List - Source Code (clsKeyList.bas)

Code: Select all

'' 
''  clsKeyList
''    

Type clsListNode
   sKey      As String
   pData     As Any Ptr
   nDataType As Byte    ' 0:ZString ptr, 1:WString ptr, 2:Unstructured, 3:Integer ptr, 4:Double ptr
End Type

Type clsKeyList
   Private:
      m_nGrowBy   As Integer     ' how big to grow the list by when needed
      m_nCount    As Integer     ' current number of elements in the list
      m_nCurrent  As Integer     ' current position in the list
      
      m_arrayList(Any) As clsListNode
      Declare Function _CreateNode() As Integer
      Declare Function _DeleteNode( ByVal nIndex As Integer ) As Integer

   Public:
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef sData As Const String) As Integer   
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef sData As Const WString) As Integer   
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nData As Integer) As Integer   
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nData As Double) As Integer   
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nAddr As Any Ptr, ByRef nSize As Integer) As Integer   
      Declare Function GetByIndex( ByVal nIndex As Integer ) As Integer
      Declare Function GetByKey( ByRef sKey As Const String ) As Integer
      Declare Function ClearList() As Integer
      Declare Function DeleteByIndex( ByVal nIndex As Integer ) As Integer
      Declare Function DeleteByKey( ByRef sKey As Const String ) As Integer
      Declare Function GetNode( ByVal nIndex As Integer ) ByRef As clsListNode
      Declare Function GetKeyString( ByVal nIndex As Integer = -1 ) As String
      Declare Function GetDataString( ByVal nIndex As Integer = -1) As String
      Declare Function GetDataInteger( ByVal nIndex As Integer = -1) As Integer
      Declare Function GetDataDouble( ByVal nIndex As Integer = -1 ) As Double
      Declare Property GrowBy( ByVal nValue As Integer)
      Declare Property GrowBy() As Integer
      Declare Property Count() As Integer
      Declare Constructor ( ByVal nInitalGrowBy As Integer = -1)
      Declare Destructor
      
End Type


''
''
Constructor clsKeyList( ByVal nInitalGrowBy As Integer = -1)
   m_nGrowBy = Iif( nInitalGrowBy = -1, 20, nInitalGrowBy)
   m_nCount    = 0         
End Constructor

''
''
Destructor clsKeyList
   this.ClearList
End Destructor


''
''
Property clsKeyList.GrowBy( ByVal nValue As Integer)
   If nValue <= 0 Then Exit Property
   this.m_nGrowBy = nValue
End Property

Property clsKeyList.GrowBy() As Integer
   Property = this.m_nGrowBy
End Property


''
''
Property clsKeyList.Count() As Integer
   Property = this.m_nCount
End Property


''
''
Function clsKeyList.ClearList() As Integer
   ' Deallocate all manually allocated memory in this list
   For i As Integer = LBound(m_arrayList) To Ubound(m_arrayList)
      Deallocate m_arrayList(i).pData
   Next
   Erase m_arrayList
   m_nCount    = 0
   Function = True
End Function


''
''
Function clsKeyList._CreateNode() As Integer

   Dim ub As Integer = Ubound(m_arrayList)

   m_nCount = m_nCount + 1

   ' Determine if the lists need to be grown in order to
   ' accomodate the new node.
   If m_nCount > ub Then
      ReDim Preserve m_arrayList(ub + m_nGrowBy) As clsListNode
   End If
   
   Return m_nCount - 1   ' zero based position in array
End Function


''
''
Function clsKeyList.AddItem Overload ( ByRef sKey  As Const String, _ 
                                       ByRef sData As Const String _
                                       ) As Integer   

   ' If key already exists in this list then simply update the
   ' node with the new data, otherwise create the new node with
   ' data at the end of the list.
   If this.GetByKey(sKey) Then
      ' m_nCurrent is already set in GetByKey if found successfully
   Else
      m_nCurrent = this._CreateNode() 
   End If
   m_arrayList(m_nCurrent).pData = CAllocate(1, Len(sData)+1)
   m_arrayList(m_nCurrent).nDataType = 0   ' zstring ptr
   m_arrayList(m_nCurrent).sKey = sKey
   *Cast(ZString Ptr, m_arrayList(m_nCurrent).pData) = sData 

   Return True

End Function


''
''
Function clsKeyList.AddItem Overload ( ByRef sKey  As Const String, _ 
                                       ByRef sData As Const WString _
                                       ) As Integer   
   
   ' If key already exists in this list then simply update the
   ' node with the new data, otherwise create the new node with
   ' data at the end of the list.
   If this.GetByKey(sKey) Then
      ' m_nCurrent is already set in GetByKey if found successfully
   Else
      m_nCurrent = this._CreateNode() 
   End If
   m_arrayList(m_nCurrent).pData = CAllocate(1, Len(sData)+1)
   m_arrayList(m_nCurrent).nDataType = 1   ' wstring ptr
   m_arrayList(m_nCurrent).sKey = sKey
   *Cast(WString Ptr, m_arrayList(m_nCurrent).pData) = sData 

   Return True

End Function


''
''
Function clsKeyList.AddItem Overload ( ByRef sKey  As Const String, _ 
                                       ByRef nData As Integer _
                                       ) As Integer   

   ' If key already exists in this list then simply update the
   ' node with the new data, otherwise create the new node with
   ' data at the end of the list.
   If this.GetByKey(sKey) Then
      ' m_nCurrent is already set in GetByKey if found successfully
   Else
      m_nCurrent = this._CreateNode() 
   End If
   m_arrayList(m_nCurrent).pData = CAllocate(1, Len(Integer))
   m_arrayList(m_nCurrent).nDataType = 3   ' integer ptr
   m_arrayList(m_nCurrent).sKey = sKey
   *Cast(Integer Ptr, m_arrayList(m_nCurrent).pData) = nData 

   Return True

End Function


''
''
Function clsKeyList.AddItem Overload ( ByRef sKey  As Const String, _ 
                                       ByRef nData As Double _
                                       ) As Integer   
   
   ' If key already exists in this list then simply update the
   ' node with the new data, otherwise create the new node with
   ' data at the end of the list.
   If this.GetByKey(sKey) Then
      ' m_nCurrent is already set in GetByKey if found successfully
   Else
      m_nCurrent = this._CreateNode() 
   End If
   m_arrayList(m_nCurrent).pData = CAllocate(1, Len(Integer))
   m_arrayList(m_nCurrent).nDataType = 4   ' double ptr
   m_arrayList(m_nCurrent).sKey = sKey
   *Cast(Double Ptr, m_arrayList(m_nCurrent).pData) = nData 

   Return True

End Function


''
''
Function clsKeyList.AddItem Overload ( ByRef sKey  As Const String, _ 
                                       ByRef nAddr As Any Ptr, _
                                       ByRef nSize As Integer _
                                       ) As Integer   
   
   ' If key already exists in this list then simply update the
   ' node with the new data, otherwise create the new node with
   ' data at the end of the list.
   If this.GetByKey(sKey) Then
      ' m_nCurrent is already set in GetByKey if found successfully
   Else
      m_nCurrent = this._CreateNode() 
   End If
   m_arrayList(m_nCurrent).sKey = sKey
   If nSize > 0 Then
      m_arrayList(m_nCurrent).pData = CAllocate(1, nSize)
      MemCpy m_arrayList(m_nCurrent).pData, nAddr, nSize 
   End If
   
   Return True

End Function


''
''
Function clsKeyList.GetByIndex( ByVal nIndex As Integer ) As Integer
   If (nIndex >=0) And (nIndex < m_nCount) Then           
      m_nCurrent = nIndex
      Return True
   End If            
   Return False
End function


''
''
Function clsKeyList.GetByKey( ByRef sKey As Const String ) As Integer
   For i As Integer = LBound(m_arrayList) To Ubound(m_arrayList)
      If m_arrayList(i).sKey = sKey Then
         m_nCurrent = i
         Return True
      End If   
   Next             
   Return False
End Function


''
''
Function clsKeyList.GetNode( ByVal nIndex As Integer = -1) ByRef As clsListNode
   If nIndex <> -1 Then this.GetByIndex(nIndex)
   If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
      (m_nCurrent <= Ubound(m_arrayList)) Then
      Return m_arrayList(m_nCurrent)
   End If   
End Function


''
''
Function clsKeyList.GetKeyString( ByVal nIndex As Integer = -1 ) As String
   If nIndex <> -1 Then this.GetByIndex(nIndex)
   If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
      (m_nCurrent <= Ubound(m_arrayList)) Then
      Return m_arrayList(m_nCurrent).sKey
   End If   
End Function


''
''
Function clsKeyList.GetDataString( ByVal nIndex As Integer = -1) As String
   If nIndex <> -1 Then this.GetByIndex(nIndex)
   If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
      (m_nCurrent <= Ubound(m_arrayList)) Then
      Select Case m_arrayList(m_nCurrent).nDataType
         Case 0   ' ztring ptr
            Return *Cast(ZString Ptr, m_arrayList(m_nCurrent).pData)
         Case 1   ' wstring ptr
            Return *Cast(WString Ptr, m_arrayList(m_nCurrent).pData)
         Case 2   ' unstructured data                              
            ' The programmer need to manipulate the node data directly
            ' in order to get meaningful data. Therefore, simply
            ' return a null string.
            Return ""
         Case 3   ' Integer ptr
            Return Str(*Cast(Integer Ptr, m_arrayList(m_nCurrent).pData))
         Case 4   ' Double ptr
            Return Str(*Cast(Double Ptr, m_arrayList(m_nCurrent).pData))
      End Select   
   End If   
End Function


''
''
Function clsKeyList.GetDataInteger( ByVal nIndex As Integer = -1) As Integer
   If nIndex <> -1 Then this.GetByIndex(nIndex)
   If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
      (m_nCurrent <= Ubound(m_arrayList)) Then
      If m_arrayList(m_nCurrent).nDataType = 3 Then
         Return *Cast(Integer Ptr, m_arrayList(m_nCurrent).pData)
      End If
   End If   
   Return 0   ' not an integer being stored in the data area
End Function


''
''
Function clsKeyList.GetDataDouble( ByVal nIndex As Integer = -1) As Double
   If nIndex <> -1 Then this.GetByIndex(nIndex)
   If (m_nCount > 0) And (m_nCurrent >= LBound(m_arrayList)) And _
      (m_nCurrent <= Ubound(m_arrayList)) Then
      If m_arrayList(m_nCurrent).nDataType = 4 Then
         Return *Cast(Double Ptr, m_arrayList(m_nCurrent).pData)
      End If
   End If   
   Return 0   ' not an double being stored in the data area
End Function


''
''
Function clsKeyList._DeleteNode( ByVal nIndex As Integer ) As Integer
   ' Private function that compresses the array and frees any allocated pData memory.
   Deallocate m_arrayList(nIndex).pData  
   ' Do the delete
   For i As Integer = nIndex To Ubound(m_arrayList) - 1
       m_arrayList(i) = m_arrayList(i+1) 
   Next
   Deallocate m_arrayList(m_nCount).pData  ' free the allocated memory in pData
   m_nCount = m_nCount - 1
   Return True
End Function


''
''
Function clsKeyList.DeleteByIndex( ByVal nIndex As Integer ) As Integer
   If this.GetByIndex(nIndex) Then
      this._DeleteNode(nIndex)
      Return True
   End If   
   Return False
End Function


''
''
Function clsKeyList.DeleteByKey( ByRef sKey As Const String ) As Integer
   If this.GetByKey(sKey) Then
      this._DeleteNode(m_nCurrent)
      Return True
   End If   
   Return False
End Function

[PaulSquires]

Hash Table

Example test program for Hash Table

Code: Select all

#Include Once "windows.bi"
#Include Once "clsHashTable.bas"


'  Create the actual hash table. By default the class creates a hash table
'  large enough to hold 500 slots. You can control how large the table size 
'  is through overloading the constructor (once set, the table size can 
'  not be changed).
'
'        Dim cHash As clsHashTable   ' table size of 500 slots and
'                                    ' lists can grow by 20 items (default)
'
'        Dim cHash As clsHashTable = 1000 ' table size of 1000 slots and
'                                    ' lists can grow by 20 items (default)
'
'        Dim cHash As clsHashTable = clsHashTable(5000, 50)
'                                    ' table size of 1000 slots and
'                                    ' lists can grow by 50 items
'                                    ' at a time (see below)
'
'  The hash of the key to find/add is computed and then converted to
'  a 'slot' that falls within the TableSize range. This slot is where
'  the linked list begins for all keys having that hash value. The keys
'  are stored in a simple list (dynamic array) and is not sorted (this
'  arrangement is plenty fast even for large lists and it decreases the
'  complexity of the algorithm).
' 
'  You can change the default number of items that will be stored in a
'  linked list by using the GrowListsBy property. By default this value
'  is 20 items. When the list reaches this amount it will grow by an
'  additional GrowListsBy amount. 
'        cHash.GrowListsBy = 100
'
'  The key is found iterating through the linked list at the initial
'  found hash 'slot'. If the key matches then the search is over. When
'  adding a Key/Data, if the Key already exists then the new Data simply
'  replaces the old data.
'    -----------------------------------------
'   | 0    | 0   | 121120 |  0  |  0  |  0 |     <--- m_hList(n) (if > 0 then pointer to clsKeyList)
'    -----------------------------------------
'                |  4366  |  clsListNode item ( linked list )
'                 --------
'                |  2314  |  clsListNode item ( linked list )
'                 --------
'                |  etc.. |
'                 --------
'
'  The class allows you add items as either String, Integer, Double or
'  any arbitrary memory location and size. This is accomplished by the class
'  simply overloading the AddItem function call.
'
'        cHash.Additm( "1000", 32456 )      ' <-- add an integer with a key of "1000"
'        cHash.Additm( "1000", @e, len(e))  ' <-- add an EMPLOYEE_TYPE structure/record held 
'                                                 in variable "e" With a Key of "1000"
'         

Dim cHash As clsHashTable = clsHashTable(5000, 50)
Dim sKey  As String
Dim sData As String 
Dim i     As Integer


' Create random keys and data to load into the hash table
Randomize Timer

'' Function to a random number in the range [first, last), or {first <= x < last}.
Function rnd_range (first As Double, last As Double) As String
    Function = Str( Fix(Rnd * (last - first) + first) )
End Function


For i = 1 To 10000
   sKey  = rnd_range( 100000, 999999 )
   sData = "Data" & Str(i)
   cHash.AddItem sKey, sData 
Next


?
? "COUNT = "; cHash.Count


?
If cHash.FindItem( "100000" ) Then
   ' if we needed to manipulate the node data directly then we would
   ' call the GetNode property. In this case, we do not need to.
   'node = cHash.GetNode
   ? " FOUND Key: "; cHash.GetKeyString, "Data: "; cHash.GetDataString  
Else
   ? " KEY NOT FOUND"
End If


?
? " UPDATE or ADD data for Key = 500000"
cHash.AddItem WSTR("500000"), "This is updated data for Key 500000" 


?
? "Delete Key = 500000";
If cHash.DeleteItem("500000") Then
   ? " FOUND and DELETED"
Else
   ? " NOT FOUND"
End If    


?
? "COUNT = "; cHash.Count

'?
'? "ITERATE THE LIST"
'cHash.MoveFirst
'Do Until cHash.Eof   
'   ? "Key: "; cHash.GetKeyString, "Data: "; cHash.GetDataString  
'   cHash.MoveNext
'Loop

' Rather than iterate the list and output it to the screen, we will
' print it to a disk file.
?
? "Debug data output to _debug.txt file"
cHash.Debug( "_debug.txt" )
? "Debug file created."

cHash.ClearTable   

? "Done."

Sleep
                   

Hash Table - Source Code (clsHashTable.bas)

Code: Select all

#Include Once "clsKeyList.bas"
 
'' 
''  clsHashTable
''    

''
''
''
Type clsHashTable 
   Private:
      m_nTableSize   As Integer     ' how big the main hash list is
      m_nCount       As Integer     ' current number of elements in all lists in the hash table
      m_nSlot        As Integer     ' current position in the hash list
      m_nGrowListsBy As Integer     ' how big to grow the linked lists by when needed
      
      ' Iterating the hash table (iterating uses the m_nSlot postion to know what the
      ' current linked list, and the nLLIndex to position within that linked list)
      m_nEOF      As Integer     ' signals that we are at the end of the table
      m_nLLIndex  As Integer     ' position within the current m_nSlot linked list
      
      m_hList(Any) As clsKeyList Ptr 

      Declare Function _GetSlot( ByRef sKey As Const String ) As Integer

   Public:
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef sData As Const String) As Integer   
'      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef sData As Const WString) As Integer   
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nData As Integer) As Integer   
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nData As Double) As Integer   
      Declare Function AddItem Overload ( ByRef sKey As Const String, ByRef nAddr As Any Ptr, ByRef nSize As Integer) As Integer   
      Declare Function FindItem( ByRef sKey As Const String ) As Integer
      Declare Function DeleteItem( ByRef sKey As Const String ) As Integer
      Declare Function ClearTable() As Integer
      Declare Function GetNode() ByRef As clsListNode
      Declare Function GetKeyString() As String
      Declare Function GetDataString() As String
      Declare Function GetDataInteger() As Integer
      Declare Function GetDataDouble() As Double
      Declare Property Count() As Integer
      Declare Function MoveFirst() As Integer
      Declare Function MoveNext() As Integer
      Declare Property Eof() As Integer
      Declare Property GrowListsBy( ByVal nValue As Integer)
      Declare Property GrowListsBy() As Integer
      Declare Function Debug( ByRef sFilename As Const String = "_debug.txt" ) As Integer
      Declare Constructor ( ByVal nTableSize As Integer = -1, ByVal nGrowListsBy As Integer = -1)
      Declare Destructor
End Type


''
''
Constructor clsHashTable( ByVal nTableSize As Integer = -1, ByVal nGrowListsBy As Integer = -1)
   m_nTableSize   = Iif( nTableSize = -1, 500, nTableSize) 
   m_nGrowListsBy = Iif( nGrowlistsBy = -1, 20, nGrowlistsBy) 
   m_nCount  = 0
   ReDim m_hList(m_nTableSize) As clsKeyList Ptr
End Constructor


''
''
Destructor clsHashTable
   this.ClearTable
End Destructor


''
''
Property clsHashTable.Count() As Integer
   m_nCount  = 0
   For i As Integer = LBound(m_hList) To Ubound(m_hList)
      If m_hList(i) Then
         m_nCount = m_nCount + m_hList(i)->Count
      End If   
   Next
   Property = this.m_nCount
End Property
      
      
''
''
Property clsHashTable.Eof() As Integer
   Property = this.m_nEOF
End Property


''
''
Property clsHashTable.GrowListsBy( ByVal nValue As Integer)
   If nValue <= 0 Then Exit Property
   this.m_nGrowListsBy = nValue
End Property

Property clsHashTable.GrowListsBy() As Integer
   Property = this.m_nGrowListsBy
End Property

''
''
Function clsHashTable.ClearTable() As Integer
   ' Deallocate all manually allocated memory in this list
   For i As Integer = LBound(m_hList) To Ubound(m_hList)
      If m_hList(i) Then 
         Delete m_hList(i)      
      End If
   Next
   Erase m_hList
   m_nCount  = 0
   Return True
End Function


''
''
''   Compute the hash value of the incoming key to determine the slot
''
Function clsHashTable._GetSlot( ByRef sKey As Const String ) As Integer
    
    Dim nLen  As Integer  = Len(sKey)
    Dim accul As UInteger = 0
    Dim last  As UInteger = 0
    Dim i     As Integer  = 0
    
    For i = 0 To nLen - 1
        last = accul
        accul = (accul Shl 5 )
        accul = accul - last + sKey[i]
    Next
    
    Function = (accul Mod m_nTableSize)
End Function


''
''
Function clsHashTable.AddItem Overload ( ByRef sKey  As Const String, _ 
                                         ByRef sData As Const String _
                                         ) As Integer
   
   Dim nPosition As Integer = this._GetSlot(sKey)
   
   ' Determine if a linked list exists at this position.
   If m_hList(nPosition) = Null Then
      m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
   End If   
   
   ' Add the key/data to the linked list at nPosition in the hash array
   m_hList(nPosition)->AddItem(sKey, sData)

   Return True  
   
End Function


''
''
'Function clsHashTable.AddItem Overload ( ByRef sKey  As Const String, _ 
'                                         ByRef sData As Const WString _
'                                         ) As Integer
'   
'   Dim nPosition As Integer = this._GetSlot(sKey)
'   
'   ' Determine if a linked list exists at this position.
'   If m_hList(nPosition) = Null Then
'      m_hList(nPosition) = New clsKeyList
'   End If   
'   
'   ' Add the key/data to the linked list at nPosition in the hash array
'   m_hList(nPosition)->AddItem(sKey, sData)
'
'   Return True  
'   
'End Function


''
''
Function clsHashTable.AddItem Overload ( ByRef sKey  As Const String, _ 
                                         ByRef nData As Integer _
                                         ) As Integer
   
   Dim nPosition As Integer = this._GetSlot(sKey)
   
   ' Determine if a linked list exists at this position.
   If m_hList(nPosition) = Null Then
      m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
   End If   
   
   ' Add the key/data to the linked list at nPosition in the hash array
   m_hList(nPosition)->AddItem(sKey, nData)
   
   Return True  
   
End Function


''
''
Function clsHashTable.AddItem Overload ( ByRef sKey  As Const String, _ 
                                         ByRef nData As Double _
                                         ) As Integer
   
   Dim nPosition As Integer = this._GetSlot(sKey)
   
   ' Determine if a linked list exists at this position.
   If m_hList(nPosition) = Null Then
      m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
   End If   
   
   ' Add the key/data to the linked list at nPosition in the hash array
   m_hList(nPosition)->AddItem(sKey, nData)
   
   Return True  
   
End Function


''
''
Function clsHashTable.AddItem Overload ( ByRef sKey  As Const String, _
                                         ByRef nAddr As Any Ptr, _
                                         ByRef nSize As Integer _
                                         ) As Integer   
   
   Dim nPosition As Integer = this._GetSlot(sKey)
   
   ' Determine if a linked list exists at this position.
   If m_hList(nPosition) = Null Then
      m_hList(nPosition) = New clsKeyList(m_nGrowListsBy)
   End If   
   
   ' Add the key/data to the linked list at nPosition in the hash array
   m_hList(nPosition)->AddItem(sKey, nAddr, nSize)
   
   Return True  
   
End Function


''
''
Function clsHashTable.FindItem( ByRef sKey As Const String ) As Integer
   Dim nPosition As Integer = this._GetSlot(sKey)

   ' Determine if a linked list exists at this position. If it does
   ' not then create the list.
   If m_hList(nPosition) = Null Then Return False
   
   ' Search the linked list to find the sKey at this hash position
   ' because multiple keys could be hashed to the same linked list.
   If m_hList(nPosition)->GetByKey(sKey) Then
      m_nSlot = nPosition
      Return True
   End If
   
   m_nSlot = -1
   Return False

End Function


''
''
Function clsHashTable.DeleteItem( ByRef sKey As Const String ) As Integer
   Dim nPosition As Integer = this._GetSlot(sKey)

   ' Determine if a linked list exists at this position. 
   If m_hList(nPosition) = Null Then Return False
   
   m_nSlot = -1

   If m_hList(nPosition)->DeleteByKey(sKey) Then
      ' If there are no more entries in this linked list then destroy it
      If m_hList(nPosition)->Count = 0 Then
         Delete m_hList(nPosition)
         m_hList(nPosition) = Null
      End If   
      Return True
   End If
   
   Return False

End Function


''
''
Function clsHashTable.GetNode() ByRef As clsListNode
   If m_nSlot >= 0 Then
      If m_hList(m_nSlot) <> Null Then
         Return m_hList(m_nSlot)->GetNode(m_nLLIndex)   
      End If   
   End If   
End Function


''
''
Function clsHashTable.GetKeyString() As String
   If m_nSlot >= 0 Then
      If m_hList(m_nSlot) <> Null Then
         Return m_hList(m_nSlot)->GetKeyString(m_nLLIndex)   
      End If   
   End If   
End Function


''
''
Function clsHashTable.GetDataString() As String
   If m_nSlot >= 0 Then
      If m_hList(m_nSlot) <> Null Then
         Return m_hList(m_nSlot)->GetDataString(m_nLLIndex)   
      End If   
   End If   
End Function


''
''
Function clsHashTable.GetDataInteger() As Integer
   If m_nSlot >= 0 Then
      If m_hList(m_nSlot) <> Null Then
         Return m_hList(m_nSlot)->GetDataInteger(m_nLLIndex)   
      End If   
   End If   
End Function


''
''
Function clsHashTable.GetDataDouble() As Double
   If m_nSlot >= 0 Then
      If m_hList(m_nSlot) <> Null Then
         Return m_hList(m_nSlot)->GetDataDouble(m_nLLIndex)   
      End If   
   End If   
End Function


''
''
Function clsHashTable.MoveFirst() As Integer
   m_nSlot = -1
   m_nEOF = False
   
   For i As Integer = LBound(m_hList) To Ubound(m_hList)
      If m_hList(i) <> Null Then
         m_nLLIndex = 0
         m_nSlot = i: Exit For
      End If
   Next

   If (m_nSlot = -1) Then
      m_nEOF = True: Return True
   End If
   
   m_hList(m_nSlot)->GetByIndex(m_nLLIndex)

   Return m_nEOF
End Function


''
''
Function clsHashTable.MoveNext() As Integer
   Dim nNextList As Integer = -1
   m_nEOF = False
   
   ' Determine if we are finished iterating the current linked list. If we
   ' are finished then try to move to the next linked list until we reach
   ' the end of the hash table.
   m_nLLIndex = m_nLLIndex + 1
   If m_hList(m_nSlot)->GetByIndex(m_nLLIndex) Then
      Return m_nEOF
   End If
   
   ' Try to get the next linked list
   For i As Integer = m_nSlot + 1 To Ubound(m_hList)
      If m_hList(i) <> Null Then
         m_nLLIndex = 0
         nNextList  = i
         m_nSlot = i: Exit For
      End If
   Next

   If (nNextList = -1) Then
      m_nEOF = True: Return True
   End If
   
   m_hList(m_nSlot)->GetByIndex(m_nLLIndex)

   Return m_nEOF

End Function


''
''
Function clsHashTable.Debug( ByRef sFilename As Const String = "_debug.txt" ) As Integer

   Dim nHighSlot  As Integer   ' slot with most keys 
   Dim nHighCount As Integer   ' #items in the high slot
   Dim nGrowBy    As Integer
   Dim st         As String
   Dim f          As Integer         
   Dim crlf       As String = Chr(13,10)
   
   For i As Integer = LBound(m_hList) To Ubound(m_hList)
      If (i Mod 50) = 0 Then
         ? "Reading slot "; i; " of "; Ubound(m_hList)  
      End If
      
      st += "Slot: " & i
      If m_hList(i) = Null Then
         st += "  <NULL>" & crlf
         Continue For 
      Else
         st += "  (Count:" & m_hList(i)->Count & ")" & crlf
         If m_hList(i)->Count >= nHighCount Then
            nHighCount = m_hList(i)->Count
            nHighSlot  = i
         End If   
      End If
      
      nGrowBy = m_hList(i)->GrowBy
      
      For y As Integer = 0 To m_hList(i)->Count - 1
         st += "   Index: " & y & "  Key: " & m_hList(i)->GetKeyString(y) & "  Data: " & m_hList(i)->GetDataString(y) & crlf
      Next      
      st += crlf
   Next
   
   st = "HASHTABLE DEBUG FILE"            & crlf & _
        "TableSize     = " & m_nTableSize & " slots" & crlf & _
        "Total Count   = " & this.Count   & " items" & crlf & _
        "Highest Slot# = " & nHighSlot    & " (" & nHighCount & " items)" & crlf & _ 
        "List GrowBy   = " & nGrowBy      & crlf & _
        crlf & st

   f = Freefile
   Open sFilename For Output As #f
   Print #f, st
   Close #f

   Function = 0
End Function

[anonymous1337]

I haven't reviewed your code in great detail, so forgive me for asking a trivial question... In practice, is it valuable to have a hash table of void *s?

[vdecampo]

I haven't reviewed your code in great detail, so forgive me for asking a trivial question... In practice, is it valuable to have a hash table of void *s?

Voids would allow to have tables of structs or classes or any arbitrary object. I personally think it would be useful.

-Vince

[MOD]

You could also use some macro hacks to allow a "templated version" like I do in mdTypes.

[anonymous1337]

I haven't reviewed your code in great detail, so forgive me for asking a trivial question... In practice, is it valuable to have a hash table of void *s?

Voids would allow to have tables of structs or classes or any arbitrary object. I personally think it would be useful.

-Vince

I haven't had to build a complex system in a non-GC language, so I hadn't considered that it is entirely possible (although with additional complications) to separately allocate and manage your resources, and also add pointers or references to those objects into a hash table.

I see how this could be a useful, fundamental component in building a larger system. It wouldn't even have to be typed... But you would have to know the type of object you are working with at some point when referencing, unless you like copying data a lot...

[vdecampo]

I haven't had to build a complex system in a non-GC language, so I hadn't considered that it is entirely possible (although with additional complications) to separately allocate and manage your resources, and also add pointers or references to those objects into a hash table.

I see how this could be a useful, fundamental component in building a larger system. It wouldn't even have to be typed... But you would have to know the type of object you are working with at some point when referencing, unless you like copying data a lot...

True, but with FB Inheritance you could have a base type that stored the actual type of the child. This would allow de-referencing of lists with multiple types (albeit inherited from a common base type). It comes very close to .NET in that respect.

-Vince

[Roland Chastain]

Hello!

Something looks strange to me in the keyed linked list test program :

Code: Select all

If cList.GetByKey("5") Then
   ? " FOUND Key: "; cList.GetKeyString(i), "Data: "; cList.GetDataString(i)  
Else
   ? " KEY NOT FOUND"
End If

The value of i is undefined here, isn't it?

[fxm]

At this level, the 'i' value is the exit value of the previous 'For' loop where it is used as iterator.
So in this precise case, i = (cList.Count - 1) + 1 = cList.Count
It is true that it is not very safe to use this exit value because the exit value of a 'For' loop iterator is not part of specification.

[PaulSquires]

Thanks Roland, yes you are correct that I had made a mistake there. I updated the code so that after doing a search you simply need to call the GetKeyString and GetDataString methods without specifying ann index parameter.

Code: Select all

? "Get using Key = 5";
If cList.GetByKey("5") Then
   ' if we needed to manipulate the node data directly then we would
   ' call the GetNode property. In this case, we do not need to.
   'node = cList.GetNode(i)
   ? " FOUND Key: "; cList.GetKeyString, "Data: "; cList.GetDataString  
Else
   ? " KEY NOT FOUND"
End If

[Roland Chastain]

Great! Thank you for the new code.

[fxm]

In example of first post:
'Dim node As clsListNode'
is useless.