NumericKeyMap module (map with numeric key)

[wilbert]

A 'simple' map with an integer value for key.

Code: Select all

;-TOP Module NumericKeyMap

; Comment: Module NumericKeyMap is a map with a numeric key
; Author : Wilbert
; Version: v1.02
; Create : 12/20/2019
; Update : 12/21/2019
; Link   : https://www.purebasic.fr/english/viewtopic.php?f=12&t=74238

DeclareModule NumericKeyMap
  
  ;- Prototypes
  
  Prototype.i ProtoAllocElement()
  Prototype   ProtoFreeElement(*Element)
  
  
  ;- Structures
  
  Structure NKMapElement
    *NextElement.NKMapElement
    Key.i
    Value.i
  EndStructure
  
  Structure NKMap
    RShift.i
    *AllocElement.ProtoAllocElement
    *FreeElement.ProtoFreeElement
    *Element.NKMapElement
    *PrevElement.NKMapElement
    *Buckets.NKMapElement[0]
  EndStructure
  
  
  ;- Procedure declarations
  
  Declare   NKMap_Clear (*Map.NKMap)
  Declare.i NKMap_Create (NrBuckets = 1024, *AllocElement = #Null, *FreeElement = #Null)
  Declare.i NKMap_FindElement (*Map.NKMap, Key)
  Declare   NKMap_Free (*Map.NKMap)
  Declare.i NKMap_GetValue (*Map.NKMap, Key)
  Declare.i NKMap_NextElement (*Map.NKMap, *PtrElement.Integer)
  Declare   NKMap_RemoveElement (*Map.NKMap, Key)
  Declare   NKMap_Reset (*Map.NKMap)
  Declare.i NKMap_SetValue (*Map.NKMap, Key, Value = 0)
  
EndDeclareModule


Module NumericKeyMap
  
  DisableDebugger
  EnableExplicit
  
  
  ;- Private macros
  
  Macro NKMap_Get(n)
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov r9, 11400714819323198549
      !mov rdx, [p.p_Map]           ; *Map
      !mov rax, [p.v_Key]           ; Key
      !mov ecx, [rdx]               ; RShift
      !imul rax, r9
      !shr rax, cl
      CompilerIf n >= 1
        !lea rax, [rdx + rax*8 + 40]  ; *Bucket
        !mov rdx, [p.v_Key]           ; Key
        !.l0:
        !mov rcx, rax
        !mov rax, [rcx]
        !test rax, rax                ; *Element #Null check
        !jz .l1
        !cmp rdx, [rax + 8]           ; cmp Key, *Element\Key
        !jb .l0
        !je .l1
        !xor eax, eax
        !.l1:
        !mov rdx, [p.p_Map]
        !mov [rdx + 24], rax          ; set *Map\Element
        !mov [rdx + 32], rcx          ; set *Map\PrevElement
      CompilerEndIf
      CompilerIf n >= 2
        !test rax, rax
        !jz .l2
        !mov rax, [rax + 16]
        !.l2:
      CompilerEndIf
    CompilerElse
      !mov edx, [p.p_Map]           ; *Map
      !mov eax, [p.v_Key]           ; Key
      !mov ecx, [edx]               ; RShift
      !imul eax, 2654435761
      !shr eax, cl
      CompilerIf n >= 1      
        !lea eax, [edx + eax*4 + 20]  ; *Bucket
        !mov edx, [p.v_Key]           ; Key
        !.l0:
        !mov ecx, eax
        !mov eax, [ecx]
        !test eax, eax                ; *Element #Null check
        !jz .l1
        !cmp edx, [eax + 4]           ; cmp Key, *Element\Key
        !jb .l0
        !je .l1
        !xor eax, eax
        !.l1:
        !mov edx, [p.p_Map]
        !mov [edx + 12], eax          ; set *Map\Element
        !mov [edx + 16], ecx          ; set *Map\PrevElement
      CompilerEndIf
      CompilerIf n >= 2
        !test eax, eax
        !jz .l2
        !mov eax, [eax + 8]
        !.l2:
      CompilerEndIf
    CompilerEndIf    
  EndMacro
  
  
  ;- Private procedures
  
  Procedure.i NKMap_Bucket(*Map.NKMap, Key)
    NKMap_Get(0)
    ProcedureReturn
  EndProcedure
  
  
  ;- Public procedures
  
  Procedure.i NKMap_FindElement(*Map.NKMap, Key)
    ; Return a pointer to the found element or
    ; #Null when the element wasn't found.
    NKMap_Get(1)
    ProcedureReturn
  EndProcedure
  
  
  Procedure.i NKMap_GetValue(*Map.NKMap, Key)
    ; Return the value of the element with the specified key.
    NKMap_Get(2)
    ProcedureReturn
  EndProcedure
  
  
  Procedure.i NKMap_Create(NrBuckets = 1024, *AllocElement = #Null, *FreeElement = #Null)
    ; Create a new map with the specified number of buckets.
    ; The number of buckets should be a power of 2.
    ; AllocElement and FreeElement are callback pointers to allocate
    ; and free a custom element.
    
    Protected.NKMap *Map
    Protected.l Shift, n = 1
    If NrBuckets < 16
      NrBuckets = 16
    ElseIf NrBuckets > 16777216
      NrBuckets = 16777216
    EndIf
    While n < NrBuckets
      n << 1 : Shift + 1
    Wend
    NrBuckets = 1 << Shift
    *Map = AllocateMemory((NrBuckets + 5) * SizeOf(Integer))
    If *Map
      *Map\RShift = SizeOf(Integer)<<3 - Shift
      *Map\AllocElement = *AllocElement
      *Map\FreeElement = *FreeElement
    EndIf
    ProcedureReturn *Map
  EndProcedure
  
  
  Procedure NKMap_Clear(*Map.NKMap)
    ; Remove all map items but leave the map structure
    ; itself available for further use.
    
    Protected.NKMapElement *Element, *NextElement
    Protected.l NrBuckets, Bucket
    *Map\Element = #Null
    NrBuckets = 1 << (SizeOf(Integer)<<3 - *Map\RShift)
    While Bucket < NrBuckets
      *Element = *Map\Buckets[Bucket]
      *Map\Buckets[Bucket] = #Null
      If *Map\FreeElement    
        While *Element
          *NextElement = *Element\NextElement
          *Map\FreeElement(*Element)
          *Element = *NextElement
        Wend
      Else    
        While *Element
          *NextElement = *Element\NextElement
          FreeMemory(*Element)
          *Element = *NextElement
        Wend
      EndIf
      Bucket + 1
    Wend
  EndProcedure
  
  
  Procedure NKMap_Free(*Map.NKMap)
    ; Free the map completely.
    ; The map can no longer be used after calling this.
    
    NKMap_Clear(*Map)
    FreeMemory(*Map)
  EndProcedure
  
  
  Procedure.i NKMap_NextElement(*Map.NKMap, *PtrElement.Integer)
    ; Return the next map element.
    
    Protected.NKMapElement *Element
    Protected.l NrBuckets, Bucket  
    *Element = *Map\Element
    If *Element
      If *Element\NextElement
        ; return next element in current bucket
        *Element = *Element\NextElement
        *Map\Element = *Element
        If *PtrElement
          *PtrElement\i = *Element
        EndIf
        ProcedureReturn #True
      Else
        ; find next bucket number
        Bucket = NKMap_Bucket(*Map, *Element\Key) + 1
      EndIf
    EndIf
    NrBuckets = 1 << (SizeOf(Integer)<<3 - *Map\RShift)      
    While Bucket < NrBuckets And *Map\Buckets[Bucket] = #Null
      Bucket + 1
    Wend
    If Bucket < NrBuckets
      *Element = *Map\Buckets[Bucket]
      *Map\Element = *Element
      If *PtrElement
        *PtrElement\i = *Element
      EndIf
      ProcedureReturn #True
    Else
      ; end of map has been reached
      ProcedureReturn #False
    EndIf
  EndProcedure  
  
  
  Procedure NKMap_RemoveElement(*Map.NKMap, Key)
    ; Remove the element with the specified key.
    
    Protected.NKMapElement *Element 
    *Element = NKMap_FindElement(*Map, Key)
    If *Element
      *Map\PrevElement\NextElement = *Element\NextElement
      *Map\Element = #Null
      If *Map\FreeElement    
        *Map\FreeElement(*Element)
      Else
        FreeMemory(*Element)
      EndIf
    EndIf
  EndProcedure
  
  
  Procedure NKMap_Reset(*Map.NKMap)
    ; Reset the current map element
    
    *Map\Element = #Null
  EndProcedure
  
  
  Procedure.i NKMap_SetValue(*Map.NKMap, Key, Value = 0)
    ; Set the value for the map element with the specified key.
    ; If the element doesn't exist, it will be created.
    ; The element is also returned from the procedure.
    
    Protected.NKMapElement *Element
    *Element = NKMap_FindElement(*Map, Key)
    If *Element = #Null
      If *Map\AllocElement
        *Element = *Map\AllocElement()
      Else
        *Element = AllocateMemory(SizeOf(NKMapElement), #PB_Memory_NoClear)
      EndIf
      *Element\Key = Key
      *Element\NextElement = *Map\PrevElement\NextElement
      *Map\PrevElement\NextElement = *Element
    EndIf
    *Element\Value = Value
    ProcedureReturn *Element
  EndProcedure
  
EndModule

[wilbert]

Example 1

Code: Select all

UseModule NumericKeyMap

; Create a map with 256 buckets
*NKMap = NKMap_Create(256)

; Set some values
NKMap_SetValue(*NKMap, 20, 100)
NKMap_SetValue(*NKMap, 21, 150)
NKMap_SetValue(*NKMap, 12, 2100)
NKMap_SetValue(*NKMap, 197, 355)

; Remove one of them
NKMap_RemoveElement(*NKMap, 21)

; Show the remaining ones
NKMap_Reset(*NKMap)
While NKMap_NextElement(*NKMap, @*Element.NKMapElement)
  Debug "Key:"+ *Element\Key + " Value:" + *Element\Value
Wend

Example 2
This example shows the ability to extend the NKMapElement structure.
In this case you have to provide procedures to allocate and free a map element.
NKMap_SetValue can be used to create an element if it didn't exist yet.

Code: Select all

UseModule NumericKeyMap

Structure CustomElement Extends NKMapElement
  Name.s
  Size.d
EndStructure

Procedure.i AllocateElement()
  ProcedureReturn AllocateStructure(CustomElement)
EndProcedure

Procedure FreeElement(*Element.CustomElement)
  FreeStructure(*Element)
EndProcedure

*NKMap = NKMap_Create(1024, @AllocateElement(), @FreeElement())

*CustomElement.CustomElement = NKMap_SetValue(*NKMap, 10)
*CustomElement\Name = "Element one"
*CustomElement\Size = 12.5

*CustomElement = NKMap_SetValue(*NKMap, 100, 50)
*CustomElement\Name = "Element two"
*CustomElement\Size = 127.35

NKMap_Reset(*NKMap)
While NKMap_NextElement(*NKMap, @*CustomElement)
  Debug "Key:"+ *CustomElement\Key + " Name:" + *CustomElement\Name
Wend

[Bitblazer]

You probably want to change the name, i instantly thought about an interface to the popular NMAP tool.

[wilbert]

You probably want to change the name, i instantly thought about an interface to the popular NMAP tool.

I didn't know about that tool.
I changed the name. Hopefully it isn't confusing anymore.

[Kwai chang caine]

All your codes is always wonder, for me
So much wonder, sometime i not understand even the title or the function, it's the reason why i not dare answer after try them
But i have understand now
It's works fine here, thanks a lot, that can be usefull in the case where i search to have result with a real number, without passing by str()
Thanks for sharing

[mk-soft]

Very good, Thanks

[box_80]

Thank you, I think I can find good use of this.

[davido]

@wilbert,

Very useful. Thank you for sharing.

Is there any strategy in choosing the number of buckets?
Or is, more the merrier, as it were?!

[infratec]

Hi, hi,

the NKM_ prefix is not needed if you use a module.
It is only needed if you build it as a normal pbi.

That is the reason for a module: a separated namespace.
You'll come never into trouble with same names of an other code part.

[skywalk]

Yes, but I appreciate the ready made effort to create as separate "nkm_.pbi".

[wilbert]

Thanks for the feedback

Is there any strategy in choosing the number of buckets?
Or is, more the merrier, as it were?!

It depends on how much memory you think is acceptable for the map object itself.
More buckets means faster access to the map elements but a bigger map object.
It doesn't make sense to have thousands of map elements with only 16 buckets.
The opposite of course it also true. It doesn't make sense to have 16384 buckets if you are only going to store 100 elements.

the NKM_ prefix is not needed if you use a module.
It is only needed if you build it as a normal pbi.

That is the reason for a module: a separated namespace.
You'll come never into trouble with same names of an other code part.

I don't know how most people use modules.
You are right if you use them with ::
If you use UseModule there might still be conflicts for the exposed procedure names without a prefix.
For me the main reason why I prefer a module is because of the ability to keep certain variables, macros and procedures private.
Another reason is that statements like DisableDebugger, EnableExplicit etc. only affect the code inside the module.

Do you think most users use :: with modules ?

[wilbert]

I posted a small update of the module.

Instead of adding a new item at the end of a bucket, the item is now inserted to keep the items inside a bucket sorted.
When there are only one or two elements inside each bucket, it doesn't really make a difference.
When there are a lot of items in each bucket, it can now easier detect that a key doesn't exist (it doesn't always have to search to the end of the bucket).

[mk-soft]

Its now very fast

Please change Header

Code: Select all

;-TOP Module NumericKeyMap

; Comment: Module NumericKeyMap is a map with a numeric key
; Author : Wilbert
; Version: v1.02
; Create : 12/20/2019
; Update : 12/21/2019
; Link   : https://www.purebasic.fr/english/viewtopic.php?f=12&t=74238

Code: Select all

#Example = 3

CompilerIf #Example = 3
  
  ;-Example 3
  
  UseModule NumericKeyMap
  
  ; Create a map with 256 buckets
  *NKMap = NKMap_Create(512)
  
  time = ElapsedMilliseconds()
  ; Set some values
  For i = 100001 To 310000
    NKMap_SetValue(*NKMap, i, i)
  Next
  time = ElapsedMilliseconds() - time
  
  NewMap Num.i()
  
  time2 = ElapsedMilliseconds()
  For i = 100001 To 310000
    Num(Str(i)) = i
  Next
  
  time2 = ElapsedMilliseconds() - time2
  
  MessageRequester("Create Map Elements", "T1: " + time + " T2: " + time2)
  
  time = ElapsedMilliseconds()
  For i = 100001 To 310000 Step 20
    v1 = NKMap_GetValue(*NKMap, i)
  Next
  time = ElapsedMilliseconds() - time
  
  time2 = ElapsedMilliseconds()
  For i = 100001 To 310000 Step 20
    v1 = Num(Str(i))
  Next
  time2 = ElapsedMilliseconds() - time2
  
  MessageRequester("Get Map Elements", "T1: " + time + " T2: " +time2)
  
CompilerEndIf

[wilbert]

Its now very fast

Please change Header

Thanks for testing

I changed the header.

[Joris]

Thank you very much Wilbert.