HashTable.bi

Const HASH_BITS = (2^8)-1       'Number of bits in our hash
Const INVALID_OFFSET_VALUE = 0  'Value hashtable returns when there's no match
Const TOTAL_KEYWORDS = 16, MAX_CONFLICTS = 1  'Adjust this later if needed
'All keywords recognized by the compiler
Static Shared as zString ptr Keywords(TOTAL_KEYWORDS) = { _
    @"", _      'offset 0 is reserved for invalid hashes (lookup returns null)
    @"float", _
    @"string", _
    @"goto", _
    @"gosub", _
    @"return", _
    @"if", _
    @"let", _
    @"add", _
    @"sub", _
    @"mul", _
    @"div", _
    @"rnd", _
    @"round", _
    @"push", _
    @"pop", _
    @"sread" _ 'offset 16
}
Dim Shared as integer HashTable(HASH_BITS, MAX_CONFLICTS)

Sub InitHashTable
    Dim as integer KeywordNum = 0, KeyHash = 0
    do
        'Super simple hashing algorithm
        for iChar as integer = 0 to len(*Keywords(KeywordNum))-1
            KeyHash += Keywords(KeywordNum)[iChar]
        next iChar

        KeyHash AND= HASH_BITS  'Truncate hash to number of bits we need

        'Save hash into hash table
        Dim as integer CollisionSlot = 0
        Do
            'If max has collisions hit end on error
            if CollisionSlot > MAX_CONFLICTS then
                print "Error: Max collisions for internal keywords exceeded"
                MessageBox(null,!"Error: Max collisions for internal keywords exceeded\n"+_
                                 "If you see this error outside testing I really screwed up bad...", _
                            "Internal Error!", MB_ICONERROR)
                end
            end if

            'if free slot found save to table and hash next keyword
            if HashTable(KeyHash, CollisionSlot) = 0 then
                HashTable(KeyHash, CollisionSlot) = KeywordNum
                exit do
            end if
        Loop
    loop until KeywordNum < TOTAL_KEYWORDS
End Sub