The Ultimate FB HashMap

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
Zamaster
Posts: 1024
Joined: Jun 20, 2005 21:40
Contact:

The Ultimate FB HashMap

Postby Zamaster » Feb 23, 2016 8:11

I know we've all done 96 of these, but are yours as overboard as this? I'm updating my personal FB libraries and wanted to redo my associated array via templated Hash map, so I did. Design choices: Key types are strictly long and zstring for now, and are not explicitly OOP constructs. Key types must have macros associated with them hard coded, this was done entirely for speed reasons. Assembly is used for the actual hashing, because lets face it FB ain't about to optimize any routines, fear not its x64 friendly.

Also, this table scales INSANELY well (adding a million items or one, insert/remove/seek times are the same): it never rehashes the whole table and rarely needs to allocate storage outside of the contiguous table block, in fact, a great deal of effort was put into making it cache friendly (like allocating fixed space for small strings). This table also favors (faster seek time) items stored more recently.

If you want to see how fast this thing is, add 100000 items with string keys and seek the whole table. While there are obviously faster ways to write a hash map, this implementation should provide a strong balance of not just speed, but density, scalability, and access consistency. No iterators, that's for a HashList.

Because I know how much everyone loves single file libs, just #include "hashmap.bi" , and be sure to define it somewhere at the top of your code (see the example). Don't worry about defining it multiple times in all needed files (poor C like template libraries have this problem), it has guards for that. Also its wrapped in a namespace called "dsm."

hashmap.bi

Code: Select all

#ifndef HASHMAP_BI
#define HASHMAP_BI

'from dsm\dsmstd.bi
namespace dsm

    enum bool
        false = 0
        true = 1
    end enum
    type char as ubyte
    #define NULL 0
    type size_t as ulong

end namespace

#define HASHMAP_CONTIGUOUS_BLOCK_N 4
#define HASHMAP_INITIAL_ROW_N 8
#define HASHMAP_SPLIT_RATIO 0.8
#define HASHMAP_COMPACT_RATIO 0.2

namespace dsm
    #macro HASHMAP_DELETION_LOGIC()
        for j = i to start - 1
            cur_row->slots(j) = cur_row->slots(j + 1)
        next j
        cur_row->size -= 1
        if cur_row->size = 0 then
            if last_row then
                last_row->next_block = cur_row->next_block
                deallocate(cur_row)
            else
                if cur_row->next_block then
                    *(cur_row) = *(cur_row->next_block)
                end if
            end if
        end if
        used_size -= 1
        if (cdbl(used_size) / (capacity * HASHMAP_CONTIGUOUS_BLOCK_N)) < _
            HASHMAP_COMPACT_RATIO then down_split_entry()
        return false
    #endmacro
    ' -------------------------- LONG ----------------------------
    #macro HASHMAP_long_STORAGE_DATA()
        key as long
    #endmacro
    #macro HASHMAP_long_DESTRUCT_LOGIC()
        ''
    #endmacro
    #macro HASHMAP_long_INSERTION_LOGIC()
        .key = _key
    #endmacro
    #macro HASHMAP_long_DELETION_LOGIC()
        if _key = cur_row->slots(i).key then
            HASHMAP_DELETION_LOGIC()
        end if
    #endmacro
    #macro HASHMAP_long_EXISTS_LOGIC()
        if _key = cur_row->slots(i).key then return true
    #endmacro
    #macro HASHMAP_long_RETRIEVE_LOGIC()
        if _key = cur_row->slots(i).key then
            _item = cur_row->slots(i).data_
            return true
        end if
    #endmacro
    #macro HASHMAP_long_RETRIEVE_R_LOGIC()
        if _key = cur_row->slots(i).key then
            return cur_row->slots(i).data_
        end if
    #endmacro   
    #macro HASHMAP_long_CALC_NEW_POS(_KEYTYPE_, _INDEX_)
        new_pos = hash_##_KEYTYPE_(this, cur_row->slots(_INDEX_).key)
    #endmacro
    #macro HASHMAP_DECLARE_HASH_WRAP_long(_KEYTYPE_, _TYPENAME_)
    function hash_wrap_long naked cdecl _
    ( _
        byref _table as HashMap_##_KEYTYPE_##_TYPENAME_, _
        _key as long _
    ) as size_t   
    #endmacro
    #macro HASHMAP_DEFINE_HASH_WRAP_long(_KEYTYPE_, _TYPENAME_)
    function HashMap_##_KEYTYPE_##_TYPENAME_.hash_wrap_long naked cdecl _
    ( _
        byref _table as HashMap_##_KEYTYPE_##_TYPENAME_, _
        _key as long _
    ) as size_t
        asm
        #ifdef __FB_64BIT__
                mov     rcx,                    &h890390f1daf308c
                mov     rax,                    qword ptr [rsp+16]
                shr     qword ptr [rsp+16],     32
                xor     rax,                    qword ptr [rsp+16]
                mul     rcx
        #ifndef HASHMAP_FAST
                mov     qword ptr [rsp+16],     rax
                shr     qword ptr [rsp+16],     32
                xor     rax,                    qword ptr [rsp+8]
                mul     rcx
        #endif
                mov     qword ptr [rsp+16],     rax
                shr     qword ptr [rsp+16],     32
                xor     rax,                    qword ptr [rsp+16]
                mov     rcx,                    qword ptr [rsp+8]
                mov     rdx,                    rax
                and     rax,                    qword ptr [rcx+40]
                cmp     rax,                    qword ptr [rcx+8]
                jl      dsm_hashmap_hashw_long_upperlevel_64
                ret
            dsm_hashmap_hashw_long_upperlevel_64:
                and     rdx,                    qword ptr [rcx+48]
                mov     rax,                    rdx
                ret
        #else
                mov     ecx,                    &h45D9F3B
                mov     eax,                    dword ptr [esp+8]
                shr     dword ptr [esp+8],      16
                xor     eax,                    dword ptr [esp+8]
                mul     ecx
        #ifndef HASHMAP_FAST
                mov     dword ptr [esp+8],      eax
                shr     dword ptr [esp+8],      16
                xor     eax,                    dword ptr [esp+8]
                mul     ecx
        #endif
                mov     dword ptr [esp+8],      eax
                shr     dword ptr [esp+8],      16
                xor     eax,                    dword ptr [esp+8]
                mov     ecx,                    dword ptr [esp+4]
                mov     edx,                    eax
                and     eax,                    dword ptr [ecx+20]
                cmp     eax,                    dword ptr [ecx+4]
                jl      dsm_hashmap_hashw_long_upperlevel_32
                ret
            dsm_hashmap_hashw_long_upperlevel_32:
                and     edx,                    dword ptr [ecx+24]
                mov     eax,                    edx
                ret
        #endif       
        end asm
    end function
    #endmacro
    #macro HASHMAP_DECLARE_HASH_long(_KEYTYPE_, _TYPENAME_)
    declare function hash_long naked cdecl _
    ( _
        _key as long _
    ) as size_t   
    #endmacro
    #macro HASHMAP_DEFINE_HASH_long(_KEYTYPE_, _TYPENAME_)
    function HashMap_##_KEYTYPE_##_TYPENAME_.hash_long naked cdecl _
    ( _
        _key as long _
    ) as size_t
        asm
        #ifdef __FB_64BIT__
                mov     rcx,                    &h890390f1daf308c
                mov     rax,                    qword ptr [rsp+8]
                shr     qword ptr [rsp+8],      32
                xor     rax,                    qword ptr [rsp+8]
                mul     rcx
        #ifndef HASHMAP_FAST
                mov     qword ptr [rsp+8],      rax
                shr     qword ptr [rsp+8],      32
                xor     rax,                    qword ptr [rsp+8]
                mul     rcx
        #endif
                mov     qword ptr [rsp+8],      rax
                shr     qword ptr [rsp+8],      32
                xor     rax,                    qword ptr [rsp+8]
                ret
        #else
                mov     ecx,                    &h45D9F3B
                mov     eax,                    dword ptr [esp+4]
                shr     dword ptr [esp+4],      16
                xor     eax,                    dword ptr [esp+4]
                mul     ecx
        #ifndef HASHMAP_FAST
                mov     dword ptr [esp+4],      eax
                shr     dword ptr [esp+4],      16
                xor     eax,                    dword ptr [esp+4]
                mul     ecx
        #endif
                mov     dword ptr [esp+4],      eax
                shr     dword ptr [esp+4],      16
                xor     eax,                    dword ptr [esp+4]
                ret
        #endif       
        end asm         
    end function
    #endmacro
    ' -------------------------- ZSTRING ----------------------------
    #define HASHMAP_zstring_BUFFER_N 32
    #macro HASHMAP_zstring_STORAGE_DATA()
        is_contiguous as bool
        union
            key_internal as zstring * HASHMAP_zstring_BUFFER_N
            key_external as zstring ptr
        end union
    #endmacro
    #macro HASHMAP_zstring_DESTRUCT_LOGIC()
        dim as integer j
        for j = 0 to cur_block->size - 1
            if cur_block->slots(j).is_contiguous = false then
                deallocate(cur_block->slots(j).key_external)
            end if
        next j   
    #endmacro
    #macro HASHMAP_zstring_INSERTION_LOGIC()
        dim as size_t key_length = len(_key)
        if key_length < HASHMAP_zstring_BUFFER_N then
            .key_internal = _key
            .is_contiguous = true
        else
            .key_external = allocate(key_length + 1)
            *(.key_external) = _key
            .is_contiguous = false 
        end if     
    #endmacro
    #macro HASHMAP_zstring_DELETION_LOGIC()
        if cur_row->slots(i).is_contiguous = false then
            if _key = *(cur_row->slots(i).key_external) then
                deallocate(cur_row->slots(i).key_external)
                HASHMAP_DELETION_LOGIC()
            end if
        else
            if _key = cur_row->slots(i).key_internal then
                HASHMAP_DELETION_LOGIC()
            end if             
        end if
    #endmacro
    #macro HASHMAP_zstring_EXISTS_LOGIC()
        if cur_row->slots(i).is_contiguous = true then
            if _key = cur_row->slots(i).key_internal then
                return true
            end if
        else
            if _key = *(cur_row->slots(i).key_external) then
                return true
            end if             
        end if
    #endmacro
    #macro HASHMAP_zstring_RETRIEVE_LOGIC()
        if cur_row->slots(i).is_contiguous = true then
            if _key = cur_row->slots(i).key_internal then
                _item = cur_row->slots(i).data_
                return true
            end if
        else
            if _key = *(cur_row->slots(i).key_external) then
                _item = cur_row->slots(i).data_
                return true
            end if             
        end if
    #endmacro 
    #macro HASHMAP_zstring_RETRIEVE_R_LOGIC()
        if cur_row->slots(i).is_contiguous = true then
            if _key = cur_row->slots(i).key_internal then
                return cur_row->slots(i).data_
            end if
        else
            if _key = *(cur_row->slots(i).key_external) then
                return cur_row->slots(i).data_
            end if             
        end if
    #endmacro   
    #macro HASHMAP_zstring_CALC_NEW_POS(_KEYTYPE_, _INDEX_)
        if cur_row->slots(_INDEX_).is_contiguous = true then
            new_pos = hash_##_KEYTYPE_ _
            ( _
                cur_row->slots(_INDEX_).key_internal _
            )
        else
            new_pos = hash_##_KEYTYPE_ _
            ( _
                *(cur_row->slots(_INDEX_).key_external) _
            )
        end if
    #endmacro
    #macro HASHMAP_DECLARE_HASH_WRAP_zstring(_KEYTYPE_, _TYPENAME_)
    declare function hash_wrap_zstring naked cdecl _
    ( _
        byref _table as HashMap_##_KEYTYPE_##_TYPENAME_, _
        _key as zstring _
    ) as size_t   
    #endmacro
    #macro HASHMAP_DEFINE_HASH_WRAP_zstring(_KEYTYPE_, _TYPENAME_)
    function HashMap_##_KEYTYPE_##_TYPENAME_.hash_wrap_zstring naked cdecl _
    ( _
        byref _table as HashMap_##_KEYTYPE_##_TYPENAME_, _
        _key as zstring _
    ) as size_t
        asm
        #ifdef __FB_64BIT__
                push    rbx
                mov     rax,                    14695981039346656037
                mov     rcx,                    1099511628211
                mov     rbx,                    dword ptr [esp+32]
            dsm_hashmap_hashw_zstring_loopstart_64:
                mov     dl,                     byte ptr [rbx]
                or      dl,                     dl
                jz      dsm_hashmap_hashw_zstring_return_64
                xor     al,                     dl         
                mul     rcx
                inc     rbx
                jmp     dsm_hashmap_hashw_zstring_loopstart_64
            dsm_hashmap_hashw_zstring_return_64:
                pop     rbx
                mov     rcx,                    qword ptr [rsp+8]
                mov     rdx,                    rax
                and     rax,                    qword ptr [rcx+40]
                cmp     rax,                    qword ptr [rcx+8]
                jl      dsm_hashmap_hashw_zstring_upperlevel_64
                ret
            dsm_hashmap_hashw_zstring_upperlevel_64:
                and     rdx,                    qword ptr [rcx+48]
                mov     rax,                    rdx
                ret                         
        #else   
                push    ebx
                mov     eax,                    2166136261
                mov     ecx,                    16777619
                mov     ebx,                    dword ptr [esp+16]
            dsm_hashmap_hashw_zstring_loopstart_32:
                mov     dl,                     byte ptr [ebx]
                or      dl,                     dl
                jz      dsm_hashmap_hashw_zstring_return_32
                xor     al,                     dl
                mul     ecx
                inc     ebx
                jmp     dsm_hashmap_hashw_zstring_loopstart_32
            dsm_hashmap_hashw_zstring_return_32:
                pop     ebx
                mov     ecx,                    dword ptr [esp+4]
                mov     edx,                    eax
                and     eax,                    dword ptr [ecx+20]
                cmp     eax,                    dword ptr [ecx+4]
                jl      dsm_hashmap_hashw_zstring_upperlevel_32
                ret
            dsm_hashmap_hashw_zstring_upperlevel_32:
                and     edx,                    dword ptr [ecx+24]
                mov     eax,                    edx
                ret
        #endif   
        end asm     
    end function
    #endmacro
    #macro HASHMAP_DECLARE_HASH_zstring(_KEYTYPE_, _TYPENAME_)
    declare function hash_zstring naked cdecl (_key as zstring) as size_t   
    #endmacro
    #macro HASHMAP_DEFINE_HASH_zstring(_KEYTYPE_, _TYPENAME_)
    function HashMap_##_KEYTYPE_##_TYPENAME_.hash_zstring naked cdecl _
    ( _
        _key as zstring _
    ) as size_t
        asm
        #ifdef __FB_64BIT__
                push    rbx
                mov     rax,                    14695981039346656037
                mov     rcx,                    1099511628211
                mov     rbx,                    dword ptr [esp+24]
            dsm_hashmap_hash_zstring_loopstart_64:
                mov     dl,                     byte ptr [rbx]
                or      dl,                     dl
                jz      dsm_hashmap_hash_zstring_return_64
                xor     al,                     dl         
                mul     rcx
                inc     rbx
                jmp     dsm_hashmap_hash_zstring_loopstart_64
            dsm_hashmap_hash_zstring_return_64:
                pop     rbx         
                ret
        #else   
                push    ebx
                mov     eax,                    2166136261
                mov     ecx,                    16777619
                mov     ebx,                    dword ptr [esp+12]
            dsm_hashmap_hash_zstring_loopstart_32:
                mov     dl,                     byte ptr [ebx]
                or      dl,                     dl
                jz      dsm_hashmap_hash_zstring_return_32
                xor     al,                     dl
                mul     ecx
                inc     ebx
                jmp     dsm_hashmap_hash_zstring_loopstart_32
            dsm_hashmap_hash_zstring_return_32:
                pop     ebx
                ret
        #endif   
        end asm       
    end function
    #endmacro
end namespace

#define HashMap(_KEYTYPE_, _TYPENAME_) HashMap_##_KEYTYPE_##_TYPENAME_

namespace dsm
    type HashMap_Initialization_Object
        public:
            declare constructor(_hashmap_construct as sub(),_
                                _hashmap_destruct as sub())
            declare destructor()
        private:
            as sub() hashmap_destruct
    end type
    constructor HashMap_Initialization_Object(_hashmap_construct as sub(),_
                                              _hashmap_destruct as sub())
        _hashmap_construct()
        hashmap_destruct = _hashmap_destruct
    end constructor
    destructor HashMap_Initialization_Object()
        hashmap_destruct()
    end destructor
end namespace

#define HASHMAP_ROWSIZE(_K_, _T_) sizeof(HashMap_##_K_##_T_##_Row)

#macro dsm_HashMap_define(_KEYTYPE_, _TYPENAME_)

#ifndef HASHMAP_INITIALIZED_##_KEYTYPE_##_TYPENAME_
#define HASHMAP_INITIALIZED_##_KEYTYPE_##_TYPENAME_

namespace dsm
   
    type HashMap_##_KEYTYPE_##_TYPENAME_##_key_pair
        HASHMAP_##_KEYTYPE_##_STORAGE_DATA()
        as _TYPENAME_ data_
    end type
    type HashMap_##_KEYTYPE_##_TYPENAME_##_Row
        as size_t size
        as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr next_block
        as HashMap_##_KEYTYPE_##_TYPENAME_##_key_pair _
            slots(0 to HASHMAP_CONTIGUOUS_BLOCK_N-1)
    end type
   
    type HashMap_##_KEYTYPE_##_TYPENAME_
       
        public:
           
            declare constructor()
            declare destructor()
   
            declare sub insert(_key as _KEYTYPE_, byref _item as _TYPENAME_)
            declare function remove(_key as _KEYTYPE_) as bool
            declare function exists(_key as _KEYTYPE_) as bool           
            declare function retrieve(_key as _KEYTYPE_, _
                                      byref _item as _TYPENAME_) as bool           
            declare function retrieve(_key as _KEYTYPE_) byref as _TYPENAME_   
               
            declare sub clear()
        protected:
            declare static sub static_construct()
            declare static sub static_destruct()
   
        private:
            static as HashMap_Initialization_Object init_object
           
            HASHMAP_DECLARE_HASH_WRAP_##_KEYTYPE_(_KEYTYPE_, _TYPENAME_)
            HASHMAP_DECLARE_HASH_##_KEYTYPE_(_KEYTYPE_, _TYPENAME_)
           
            declare sub init()
            declare sub clear_data()
            declare sub up_split_entry()
            declare sub down_split_entry()

            as char ptr data_
            as size_t split
            as size_t capacity
            as size_t used_size
            as size_t level
            as size_t level_wrap_mask
            as size_t level_wrap_mask_2x

            static as size_t row_size_adjust
            static as size_t row_shift_mul
    end type
    type HashMap_##_KEYTYPE_##_TYPENAME_##_Accessor extends _
        HashMap_##_KEYTYPE_##_TYPENAME_
        public:
            declare static sub construct_()
            declare static sub destruct_()
        private:
            as integer _placeholder_
    end type
    sub HashMap_##_KEYTYPE_##_TYPENAME_##_Accessor.construct_()
        static_construct()
    end sub
    sub HashMap_##_KEYTYPE_##_TYPENAME_##_Accessor.destruct_()
        static_destruct()
    end sub
   
    dim as HashMap_Initialization_Object _
        HashMap_##_KEYTYPE_##_TYPENAME_.init_object = _
        HashMap_Initialization_Object _
        ( _
            @HashMap_##_KEYTYPE_##_TYPENAME_##_Accessor.construct_, _
            @HashMap_##_KEYTYPE_##_TYPENAME_##_Accessor.destruct_ _
        )
       
    dim as size_t HashMap_##_KEYTYPE_##_TYPENAME_.row_size_adjust = 1
    dim as size_t HashMap_##_KEYTYPE_##_TYPENAME_.row_shift_mul = 0

    sub HashMap_##_KEYTYPE_##_TYPENAME_.static_construct()
        dim as size_t temp_size
        temp_size = sizeof(HashMap_##_KEYTYPE_##_TYPENAME_##_Row)
        do
            row_shift_mul += 1
            temp_size shr= 1
        loop while (temp_size <> 0)
        row_size_adjust shl= row_shift_mul
        if ((row_size_adjust shr 1) = sizeof( _
            HashMap_##_KEYTYPE_##_TYPENAME_##_Row)) then
           
            row_shift_mul -= 1
            row_size_adjust shr= 1
        end if
    end sub
   
    sub HashMap_##_KEYTYPE_##_TYPENAME_.static_destruct()
        ''
    end sub
   
    sub HashMap_##_KEYTYPE_##_TYPENAME_.init()
        split = 0
        level = HASHMAP_INITIAL_ROW_N
        level_wrap_mask = level - 1
        level_wrap_mask_2x = level shl 1 - 1
        used_size = 0
        capacity = HASHMAP_INITIAL_ROW_N   
    end sub
   
    constructor HashMap_##_KEYTYPE_##_TYPENAME_()
        init()
        data_ = callocate(row_size_adjust * capacity)
    end constructor
   
    sub HashMap_##_KEYTYPE_##_TYPENAME_.clear_data()
        dim as integer i
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_block
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr next_block
        dim as bool not_first_block
       
        for i = 0 to capacity - 1
            cur_block = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                             data_ + i shl row_shift_mul)
            not_first_block = false
            while(cur_block)
                next_block = cur_block->next_block
                HASHMAP_##_KEYTYPE_##_DESTRUCT_LOGIC()
                if not_first_block then deallocate(cur_block)
                not_first_block = true
                cur_block = next_block
            wend
        next i       
    end sub
   
    destructor HashMap_##_KEYTYPE_##_TYPENAME_()
        clear_data()
        deallocate(data_)
    end destructor
   
    HASHMAP_DEFINE_HASH_WRAP_##_KEYTYPE_(_KEYTYPE_, _TYPENAME_)
    HASHMAP_DEFINE_HASH_##_KEYTYPE_(_KEYTYPE_, _TYPENAME_)

    sub HashMap_##_KEYTYPE_##_TYPENAME_.insert _
    ( _
        _key as _KEYTYPE_, _
        byref _item as _TYPENAME_ _
    )
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_row
        cur_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                       data_ + hash_wrap_##_KEYTYPE_##(this, _key) shl _
                       row_shift_mul)
        while(cur_row->next_block)
            cur_row = cur_row->next_block
        wend
        if cur_row->size = HASHMAP_CONTIGUOUS_BLOCK_N then
            cur_row->next_block = callocate(HASHMAP_ROWSIZE(_KEYTYPE_, _
                                                            _TYPENAME_))
            cur_row = cur_row->next_block
        end if
        with cur_row->slots(cur_row->size)
            .data_ = _item
            HASHMAP_##_KEYTYPE_##_INSERTION_LOGIC()
        end with
        cur_row->size += 1
        used_size += 1
        if (cdbl(used_size) / (capacity * HASHMAP_CONTIGUOUS_BLOCK_N)) > _
            HASHMAP_SPLIT_RATIO then up_split_entry()
    end sub
   
   
    function HashMap_##_KEYTYPE_##_TYPENAME_.remove _
    ( _
        _key as _KEYTYPE_ _
    ) as bool
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_row
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr last_row
        dim as integer i
        dim as integer j
        dim as integer start
        cur_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                       data_ + hash_wrap_##_KEYTYPE_##(this, _key) shl _
                       row_shift_mul)
        last_row = NULL
        do
            start = cur_row->size - 1
            for i = start to 0 step -1
                HASHMAP_##_KEYTYPE_##_DELETION_LOGIC()
            next i
            last_row = cur_row
            cur_row = cur_row->next_block
        loop while (cur_row)
        return true
    end function
   
    function HashMap_##_KEYTYPE_##_TYPENAME_.exists _
    ( _
        _key as _KEYTYPE_ _
    ) as bool
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_row
        dim as integer i
        dim as integer start
        cur_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                       data_ + hash_wrap_##_KEYTYPE_##(this, _key) shl _
                       row_shift_mul)
        do
            start = cur_row->size - 1
            for i = start to 0 step -1
                HASHMAP_##_KEYTYPE_##_EXISTS_LOGIC()
            next i
            cur_row = cur_row->next_block
        loop while (cur_row)
        return false   
    end function

    function HashMap_##_KEYTYPE_##_TYPENAME_.retrieve _
    ( _
        _key as _KEYTYPE_, _
        byref _item as _TYPENAME_ _
    ) as bool
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_row
        dim as integer i
        dim as integer start
        cur_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                       data_ + hash_wrap_##_KEYTYPE_##(this, _key) shl _
                       row_shift_mul)
        do
            start = cur_row->size - 1
            for i = start to 0 step -1
                HASHMAP_##_KEYTYPE_##_RETRIEVE_LOGIC()
            next i
            cur_row = cur_row->next_block
        loop while (cur_row)
        return false                     
    end function
   
    function HashMap_##_KEYTYPE_##_TYPENAME_.retrieve _
    ( _
        _key as _KEYTYPE_ _
    ) byref as _TYPENAME_
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_row
        dim as integer i
        dim as integer start
        cur_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                       data_ + hash_wrap_##_KEYTYPE_##(this, _key) shl _
                       row_shift_mul)
        do
            start = cur_row->size - 1
            for i = start to 0 step -1
                HASHMAP_##_KEYTYPE_##_RETRIEVE_R_LOGIC()
            next i
            cur_row = cur_row->next_block
        loop while (cur_row)
    end function
   
    sub HashMap_##_KEYTYPE_##_TYPENAME_.clear()
        dim as integer i
        clear_data()
        init()
        deallocate(data_)
        data_ = callocate(row_size_adjust * capacity)
    end sub
   
    sub HashMap_##_KEYTYPE_##_TYPENAME_.up_split_entry()
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_row
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr next_row
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr last_row       
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_insert_row 
        dim as integer i
        dim as integer j
        dim as integer start
        dim as integer insert_i
        dim as size_t new_pos

        capacity += 1
        data_ = reallocate(data_, capacity * row_size_adjust)
        cur_insert_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                              data_ + (capacity - 1) shl row_shift_mul)
        cur_insert_row->size = 0
        cur_insert_row->next_block = NULL
        cur_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                       data_ + split shl row_shift_mul)
                       
        if cur_row->size > 0 then
            last_row = NULL
            do
                next_row = cur_row->next_block
                start = cur_row->size - 1
                i = cur_row->size - 1
                while(i >= 0)
                    HASHMAP_##_KEYTYPE_##_CALC_NEW_POS(_KEYTYPE_, i)
                    new_pos and= level_wrap_mask_2x
                    if new_pos <> split then
                        if cur_insert_row->size < _
                           HASHMAP_CONTIGUOUS_BLOCK_N then
                            cur_insert_row->size += 1
                            cur_insert_row->slots _
                            ( _
                                cur_insert_row->size - 1 _
                            ) = cur_row->slots(i)
                        else
                            cur_insert_row->next_block = callocate _
                            ( _
                                HASHMAP_ROWSIZE(_KEYTYPE_, _TYPENAME_) _
                            )
                            cur_insert_row = cur_insert_row->next_block
                            cur_insert_row->slots(0) = cur_row->slots(i)
                            cur_insert_row->size = 1
                        end if
                        for j = i to start - 1
                            cur_row->slots(j) = cur_row->slots(j + 1)
                        next j
                        cur_row->size -= 1
                        start -= 1
                    end if
                    i -= 1
                wend
                if cur_row->size = 0 then
                    if last_row = NULL then
                        if next_row then
                            *cur_row = *next_row
                            deallocate(next_row)
                        else
                            cur_row = next_row
                        end if
                    else
                        last_row->next_block = next_row
                        deallocate(cur_row)
                        cur_row = next_row
                    end if
                else
                    last_row = cur_row
                    cur_row = next_row     
                end if
            loop while cur_row
        end if
        split += 1
        if split >= level then
            level shl= 1
            split = 0
            level_wrap_mask = level - 1
            level_wrap_mask_2x = level shl 1 - 1
        end if
    end sub

    sub HashMap_##_KEYTYPE_##_TYPENAME_.down_split_entry() 
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_row
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr next_row
        dim as HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr cur_insert_row       
        dim as integer i
        dim as integer insert_i
        dim as integer start
        dim as size_t new_pos
        dim as bool not_first_block
       
        if capacity > HASHMAP_INITIAL_ROW_N then
            if split = 0 then
                level /= 2
                split = level - 1
                level_wrap_mask = level - 1
                level_wrap_mask_2x = level shl 1 - 1
            else
                split -= 1
            end if

            cur_row = cast(HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                           data_ + (capacity - 1) shl row_shift_mul)   
            if cur_row->size > 0 then
                not_first_block = false
                HASHMAP_##_KEYTYPE_##_CALC_NEW_POS(_KEYTYPE_, 0)
                new_pos and= level_wrap_mask
                cur_insert_row = cast _
                ( _
                    HashMap_##_KEYTYPE_##_TYPENAME_##_Row ptr, _
                    data_ + new_pos shl row_shift_mul _
                )
                do
                    next_row = cur_row->next_block
                    start = cur_row->size - 1
                    for i = start to 0 step -1
                        do
                            if cur_insert_row->size < _
                               HASHMAP_CONTIGUOUS_BLOCK_N then
                                cur_insert_row->size += 1
                                cur_insert_row->slots _
                                ( _
                                    cur_insert_row->size - 1 _
                                ) = cur_row->slots(i)
                                exit do
                            elseif cur_insert_row->next_block = NULL then
                                cur_insert_row->next_block = callocate _
                                ( _
                                    HASHMAP_ROWSIZE(_KEYTYPE_, _TYPENAME_) _
                                )
                                cur_insert_row = cur_insert_row->next_block
                                cur_insert_row->slots(0) = _
                                    cur_row->slots(i)
                                cur_insert_row->size = 1
                                exit do
                            else
                                cur_insert_row = cur_insert_row->next_block
                            end if
                        loop
                    next i
                    if not_first_block then deallocate(cur_row)
                    not_first_block = true
                    cur_row = next_row
                loop while (cur_row)
            end if
           
            capacity -= 1
            data_ = reallocate(data_, capacity * row_size_adjust)
           
        end if
       
    end sub
   
end namespace
#endif
#endmacro


#endif


main.bas

Code: Select all

#include "hashmap.bi"
#define TEST_HASHES 100000

dsm_HashMap_define(zstring, integer)

using dsm

dim as HashMap(zstring, integer) table
dim as integer i


function generateGarbageString() as string
    dim as integer rand_char
    dim as integer length
    dim as integer i
    dim as integer capitalize
    dim as string rand_string
    rand_string = ""
    length = int(rnd * 64) + 3
    capitalize = 1
    for i = 0 to length
        if int(rnd * 5) = 0 andAlso capitalize = 0 then
            rand_string += " "
            capitalize = 1
        else
            rand_char = int(rnd * (asc("z") - asc("a"))) + asc("a")
            if capitalize = 1 then
                rand_string += ucase(chr(rand_char))
            else
                rand_string += chr(rand_char)
            end if
            capitalize = 0
        end if
    next i
    return rand_string
end function

redim as string hash_code(0 to TEST_HASHES-1)

for i = 0 to TEST_HASHES-1
    hash_code(i) = generateGarbageString()
    table.insert(hash_code(i), i + 1)
    print i + 1, hash_code(i)
next i
print "inserted all!"
sleep
table.clear()
print "cleared all!"
sleep
for i = 0 to TEST_HASHES-1
    table.insert(hash_code(i), i + 1)
    print i + 1, hash_code(i)
next i
print "inserted all!"
sleep
dim as integer x
x = 0
for i = 0 to TEST_HASHES-1
    x += table.retrieve(hash_code(i))
next i
print x
print "sought all!"
sleep
for i = 0 to TEST_HASHES*0.5-1
    if table.remove(hash_code(i)) then
        print "failure! : "; i + 1; 
        print hash_code(i)
        sleep
    else
        print i + 1
    end if
next i
print "removed half!"
sleep
for i = 0 to TEST_HASHES*0.5-1
    table.insert(hash_code(i), i + 1)
    print i + 1, hash_code(i)
next i
print "inserted half!"
sleep
for i = 0 to TEST_HASHES-1
    if table.remove(hash_code(i)) then
        print "failure! : "; i + 1; 
        print hash_code(i)
        sleep
    else
        print i + 1
    end if
next i
print "removed all!"
sleep
end
MOD
Posts: 555
Joined: Jun 11, 2009 20:15

Re: The Ultimate FB HashMap

Postby MOD » Feb 23, 2016 19:21

mdTypes also provides some Map classes.

Simple example code:

Code: Select all

#Include Once "md/util/mdMap.bi"

mdMapDeclare(String, String)
Dim As mdMap(String, String) map

Dim As String temp
temp = map.put("key1", "value1")
temp = map.put("key2", "value2")
temp = map.put("key3", "value3")

Dim As mdSet(String) set = map.keySet()

Dim As String element
ForEach(String, element In set)
    Print "key: " & element & " - value: " & map.get(element)
NextEach

Sleep
Zamaster
Posts: 1024
Joined: Jun 20, 2005 21:40
Contact:

Re: The Ultimate FB HashMap

Postby Zamaster » Feb 23, 2016 20:42

Right right, I know there are tons of these lying around, I just thought mine was pretty quick :)

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 1 guest