This is a hash table (original written by Matt Laurenson [Defoc8], I added a lot of stuff to it):
Rem
HASHTABLE OBJECT
- M.Laurenson/Defoc8 2006
EndRem
Rem
Defoc would appreciate if you credited him if you
used this. No credit is to go to me.
-Noel
EndRem
SuperStrict
Import Brl.Blitz
Import Brl.LinkedList
Import "hash.c"
Extern "C"
Function __c_hash:Int(key$z, length:Int, initval:Int)="Hash"
EndExtern
Global HashKey:Int(name:String) = gHashKey
Function gHashKey%( name:String )
Local i:Int = __c_hash( name, name.Length, 0 )
If i = 0 Then Return 1 ' Unfortunately, I cannot allow the use of a zero key
Return i
End Function
Type gHashTable
'private:
Field table:TList[]
'protected:
Method _rement(key:Int)
For Local entry:gHashEntry = EachIn table[key Shr 24]
If entry.key = key
entry.node.Remove( )
Return
EndIf
Next
End Method
Method _addent(key:Int,n:String,o:Object)
Local entry:gHashEntry = New gHashEntry
entry.key = key
entry.obj = o
entry.name = n
entry.node = table[key Shr 24].AddLast(entry)
End Method
Method _getent:Object(key:Int)
If table[key Shr 24].Count( ) = 0 Then Return Null
For Local entry:gHashEntry = EachIn table[key Shr 24]
If entry.key = key
Return entry.obj
EndIf
Next
Return Null
End Method
'public:
Method New()
table=New TList[256]
For Local n:Int = 0 To 255
table[n] = New TList
Next
End Method
Method SetEntry( name:String, obj:Object )
Local key:Int = HashKey( name )
Local o:Object = _getent(key)
If o And o <> obj Then _rement(key)
_addent(key,name,obj)
End Method
Method InsertEntry(name:String,obj:Object)
Local key:Int = HashKey( name )
_addent(key,name,obj)
End Method
Method RemoveEntry(name:String)
Local key:Int = HashKey( name )
_rement(key)
End Method
Method GetEntry:Object(name:String)
Local key:Int = HashKey( name )
Return _getent(key)
End Method
Method Flush()
For Local n:Int = 0 To 255
table[n].Clear( )
Next
End Method
Method GetEntryCount%(index:Int)
Return table[index].Count( )
End Method
Method ToArray:Object[]( iters%=0 )
Local amnt%=0
For Local i:Int = 0 To 255
amnt :+ table[i].Count( )
Next
Local obj:Object[amnt]
Local c%=0
For Local i:Int = 0 To 255
For Local n:gHashEntry = EachIn table[i]
If iters > 0 Then
obj[c] = n
Else
obj[c] = n.obj
EndIf
c:+1
Next
Next
Return obj
End Method
Method ObjectEnumerator:gHashTableEnum( )
Local e:gHashTableEnum = New gHashTableEnum
e.arr = ToArray( )
Return e
End Method
End Type
Type gHashTableEnum
Field idx%=0
Field arr:Object[]
Method HasNext%( )
If idx < arr.Length Then Return True
Return False
End Method
Method NextObject:Object( )
idx :+ 1
Return arr[idx-1]
End Method
End Type
Type gHashEntry
Field key:Int
Field name:String
Field obj:Object
Field node:TLink
End TypeThis is hash.c:
/*
Code by Bob Jenkins, December 1996, Public Domain. Plus some minor,
minor tweaks by Noel Cower. Nothing that affects the implementation.
You can use this free for any purpose. It has no warranty.
*/
#define mix(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3); \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
int Hash( k, length, initval )
register const unsigned char *k; /* the key */
register int length; /* the length of the key */
register int initval; /* the previous hash, or an arbitrary value */
{
register int a,b,c,len;
/* Set up the internal state */
len = length;
a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
c = initval; /* the previous hash value */
/*---------------------------------------- handle most of the key */
while (len >= 12)
{
a += (k[0] +((int)k[1]<<8) +((int)k[2]<<16) +((int)k[3]<<24));
b += (k[4] +((int)k[5]<<8) +((int)k[6]<<16) +((int)k[7]<<24));
c += (k[8] +((int)k[9]<<8) +((int)k[10]<<16)+((int)k[11]<<24));
mix(a,b,c);
k += 12; len -= 12;
}
/*------------------------------------- handle the last 11 bytes */
c += length;
switch(len) /* all the case statements fall through */
{
case 11: c+=((int)k[10]<<24);
case 10: c+=((int)k[9]<<16);
case 9 : c+=((int)k[8]<<8);
/* the first byte of c is reserved for the length */
case 8 : b+=((int)k[7]<<24);
case 7 : b+=((int)k[6]<<16);
case 6 : b+=((int)k[5]<<8);
case 5 : b+=k[4];
case 4 : a+=((int)k[3]<<24);
case 3 : a+=((int)k[2]<<16);
case 2 : a+=((int)k[1]<<8);
case 1 : a+=k[0];
/* case 0: nothing left to add */
}
mix(a,b,c);
/*-------------------------------------------- report the result */
return c;
}
This is how I use it in my engine:
Private
Global _objtable:gHashTable = New gHashTable
Public
' Returns handle/key
' Standard convention for registering objects in Indigo is that you name them like "Class::Name", or "Class::SubClass::Name"
' For objects that may have duplicate names, you should have a) an index and b) append the date, time, and millisecs to the Name section
Function RegisterObject%( name$, obj:Object )
Local key:Int = gHashKey( name )
Assert _objtable._getent( key )=Null,"Object with name ~q"+name+"~q already exists"
_objtable._addent( key, name, obj )
Return key
End Function
Function GetObjectByHandle:Object( handle% )
Return _objtable._getent( handle )
End Function
Function GetObjectByName:Object( name$ )
Local key:Int = gHashKey( name )
Return _objtable._getent( key )
End Function
' If you want to avoid rehashing the key, pass Null/"" as name and pass the key to handle
Function UnregisterObject( name$, handle%=0 )
' Since BlitzMax only checks name.Length=0 if name <> Null, the following is actually safe
If name <> Null And name.Length > 0 Then
handle = gHashKey( name )
EndIf
_objtable._rement( handle )
End Function
Function GetGlobalObjectTable:gHashTable( )
Return _objtable
End Function
Function FlushObjectTable( )
_objtable.Flush( )
End FunctionAs pointed out by Suco-X, a map would work as well, but I think in this case a hash table would be faster.