OpenEuphoria

2. Re[2]: Standard toolkit

• Posted by akusaya at gmx.net Jul 03, 2005
• 668 views

>> A lot of routines are still missing. I think these routines need to be
>> included in the standard library project:
>> - copy/rename/move/delete/rmdir functions, USING WIN32 API and LINUX
>>   SYSTEM CALLS instead of system("del " & filename,0) which I hate very
>>   much (personally) since it's not reliable
>> - *simple* hash map/set, like hash_set(key, value),
>>   hash_get(key, default_value), hash_find(key), etc
>> - date/time library, like datetime.e by CyrekSoft

J> Derek Parnell and Jiri Babor both have hash libraries in the archive.

Thank you for your suggestion.

I looked at Derek Parnell's, but it seems to complicated and big.
So I used Jiri Babor's, modified it so any object can be used as key
(consistent to EDB principles), and reduced the number of functions to
5 (new, get, set, find, delete)

The resulting is as follows (will soon submit it to archive).

As usual, please give suggestions (especially the hash_hash function
seems not too optimized)




---------------------------------------------------------------------
--# Hash Tables, by Jiri Babor, modified by me
---------------------------------------------------------------------

--  htables.e : hash tables : version 1.00
--  jiri babor
--  jbabor at paradise.net.nz
--  03-Jan-04

-- Modified to support any objects as key, and simpler operations

sequence hash_s, hash_t
integer hash_index1, hash_index2          -- bucket index, collision index
atom rotate_left, rotate_left_param, hash_t_rol_1
integer hash_initted
hash_initted = 0

function rol(atom x)
    poke4(rotate_left_param, x)
    call(rotate_left)
    return peek4s(rotate_left_param)
end function

procedure hash_init()
    -- 32-bit left rotation : modified Tommy Carlie's code - thanks!
    rotate_left = allocate(13)
    rotate_left_param = rotate_left + 1
    
    poke(rotate_left, {
        #B8,#00,#00,#00,#00,                -- 0: mov eax, dword param (2)
        #D1,#C0,                            -- 5: rol eax, 1
        #A3,#00,#00,#00,#00,                -- 7: mov [@param]
        #C3})                               -- C: ret
    poke4(rotate_left+8, rotate_left_param) -- @param
    
    -- create an array of 256 32-bit random integer such that any
    -- bit column contains exactly 128 zeros and 128 ones
    hash_s = repeat(0,32)
    hash_t = repeat(0,128) & repeat(1,128)
    set_rand(24341)
    for i = 1 to 32 do
        hash_s[i] = shuffle(hash_t)
    end for
    
    -- exchange rows and columns : turn sequence s 90 degrees clockwise
    hash_t = repeat(repeat(0,32),256) -- init output sequence
    for r=1 to 32 do
        for c=1 to 256 do
            hash_t[c][32-r+1] = hash_s[r][c]
        end for
    end for
    
    -- turn bit sequences into 32-bit integers
    for i = 1 to 256 do
        hash_t[i] = bits_to_int(hash_t[i])
    end for
    
    hash_t_rol_1 = rol(hash_t[1])
end procedure

function hash_hash(object key)
    atom h
    object tmp
    integer n
    
    if atom(key) then
        if integer(key) then
            if key >= 0 and key <= 255 then
                h = xor_bits(hash_t_rol_1, hash_t[key+1])
            else
                if key < 0 then
                    key += 4294967296
                end if
                key = int_to_bytes(key)
                
                h = hash_t[4]
                for i = 1 to 4 do
                    h = xor_bits(rol(h), hash_t[key[i]+1])
                end for
            end if
        else
            key = atom_to_float64(key)
            h = hash_t[8]
            for i = 1 to 8 do
                h = xor_bits(rol(h), hash_t[key[i]+1])
            end for
        end if
    else
        n = and_bits(length(key), #FF)
        h = hash_t[n+1]
        for i = 1 to n do
            tmp = hash_hash(key[i])
            if tmp < 0 then
                tmp += 4294967296
            end if
            tmp = int_to_bytes(tmp)
            
            h = xor_bits(rol(h), hash_t[tmp[1]+1])
            h = xor_bits(rol(h), hash_t[tmp[2]+1])
            h = xor_bits(rol(h), hash_t[tmp[3]+1])
            h = xor_bits(rol(h), hash_t[tmp[4]+1])
        end for
    end if
    return h
end function


-- hash_new(atom number_of_buckets)
-- Creates a new hash table, with /number_of_buckets buckets.
-- If /number_of_buckets is not power of 2, 
-- the nearest larger power of 2 will be used.
-- Returns an empty HashTable.
global function hash_new(atom number_of_buckets)
    if not hash_initted then
        hash_init()
        hash_initted = 1
    end if
    
    if number_of_buckets > 4294967296 then
        number_of_buckets = 4294967296
    elsif number_of_buckets <= 1 then
        number_of_buckets = 2
    end if

    if and_bits(number_of_buckets,number_of_buckets-1) then
        for i = 3 to 32 do
            if number_of_buckets <= power(2, i) then
                number_of_buckets = power(2, i)
                exit
            end if
        end for
    end if
    
    return repeat({{}}, number_of_buckets)
end function

-- hash_find(HashTable table, object key)
-- Lets you know whether /key is exists on the /table.
-- Returns 0 if not exists, non-zero if exists
global function hash_find(sequence table, object key)
    sequence t

    hash_index1 = and_bits(hash_hash(key),length(table)-1)+1
    t = table[hash_index1]
    hash_index2 = find(key, t[length(t)])
    return hash_index2
end function

-- hash_get(HashTable table, object key, object default)
-- Returns the value of the /key.
-- If the /key cannot be found, /default is returned.
global function hash_get(sequence table, object key, object default)
    sequence t
    
    hash_index1 = and_bits(hash_hash(key),length(table)-1)+1
    t = table[hash_index1]
    hash_index2 = find(key, t[length(t)])
    
    if hash_index2 then
        return t[hash_index2]
    else
        return default
    end if
end function

-- hash_set(HashTable table, object key, object value)
-- If the /key is not on the /table, the /key and /value is stored in the
-- /table. If the /key already exists, the existing value will be updated.
-- Returns the modified HashTable.
global function hash_set(sequence table, object key, object value)
    sequence t

    hash_index1 = and_bits(hash_hash(key), length(table)-1) + 1
    t = table[hash_index1]
    hash_index2 = find(key, t[length(t)])

    if not hash_index2 then
        hash_index2 = length(t)
        t = append(t, append(t[hash_index2],key))
    end if
    
    t[hash_index2] = value
    table[hash_index1] = t
    
    return table
end function

-- hash_delete(HashTable table, object key)
-- Deletes the /key and corresponding value.
-- If the /key cannot be found, the /table is not modified.
-- Returns the (un)modified HashTable.
global function hash_delete(sequence table, object key)
    sequence t
    integer n

    hash_index1 = and_bits(hash_hash(key),length(table)-1) + 1
    t = table[hash_index1]
    n = length(t)
    hash_index2 = find(key, t[n])
    if hash_index2 then
        t[n] = t[n][1..hash_index2-1] & t[n][hash_index2+1..n-1]
        t = t[1..hash_index2-1] & t[hash_index2+1..n]
    end if
    table[hash_index1] = t

    return table
end function