It is currently Tue Mar 31, 2020 8:05 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 24 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 1:35 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
A 'simple' map with an integer value for key.

Code:
;-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

_________________
macOS 10.15 Catalina, PB 5.71 x64


Last edited by wilbert on Sat Dec 21, 2019 1:42 pm, edited 8 times in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: NMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 1:36 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
Example 1
Code:
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:
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

_________________
macOS 10.15 Catalina, PB 5.71 x64


Last edited by wilbert on Fri Dec 20, 2019 3:13 pm, edited 5 times in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: NMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 2:27 pm 
Offline
Enthusiast
Enthusiast

Joined: Mon Apr 10, 2017 6:17 pm
Posts: 314
Location: Germany
You probably want to change the name, i instantly thought about an interface to the popular NMAP tool.

_________________
webpage


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 3:12 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
Bitblazer wrote:
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. :wink:

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 8:03 pm 
Offline
Addict
Addict
User avatar

Joined: Sun Nov 05, 2006 11:42 pm
Posts: 4658
Location: Lyon - France
All your codes is always wonder, for me :shock:
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 :oops:
But i have understand now :D
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 8)

_________________
ImageThe happiness is a road...
Not a destination


Last edited by Kwai chang caine on Fri Dec 20, 2019 8:05 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 8:04 pm 
Online
Addict
Addict
User avatar

Joined: Fri May 12, 2006 6:51 pm
Posts: 2329
Location: Germany
Very good, Thanks :wink:

_________________
My Projects ThreadToGUI / OOP-BaseClass / OOP-BaseClassDispatch / EventDesigner V3
PB v3.30 / v5.70 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 8:35 pm 
Offline
User
User

Joined: Mon Sep 03, 2012 8:52 pm
Posts: 76
Thank you, I think I can find good use of this. :D


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 9:31 pm 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1750
Location: Uttoxeter, UK
@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?!

_________________
DE AA EB


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 10:47 pm 
Offline
Addict
Addict

Joined: Sun Sep 07, 2008 12:45 pm
Posts: 4585
Location: Germany
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Fri Dec 20, 2019 11:09 pm 
Offline
Addict
Addict
User avatar

Joined: Wed Dec 23, 2009 10:14 pm
Posts: 3232
Location: Boston, MA
Yes, but I appreciate the ready made effort to create as separate "nkm_.pbi".

_________________
The nice thing about standards is there are so many to choose from. ~ Andrew Tanenbaum


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Sat Dec 21, 2019 6:14 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
Thanks for the feedback :)

davido wrote:
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.


infratec wrote:
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 ?

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Sat Dec 21, 2019 8:26 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
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).

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Sat Dec 21, 2019 12:05 pm 
Online
Addict
Addict
User avatar

Joined: Fri May 12, 2006 6:51 pm
Posts: 2329
Location: Germany
Its now very fast :wink:

Please change Header
Code:
;-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:
#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


_________________
My Projects ThreadToGUI / OOP-BaseClass / OOP-BaseClassDispatch / EventDesigner V3
PB v3.30 / v5.70 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Sat Dec 21, 2019 1:43 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3606
Location: Netherlands
mk-soft wrote:
Its now very fast :wink:

Please change Header

Thanks for testing :)

I changed the header.

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: NumericKeyMap module (map with numeric key)
PostPosted: Sun Dec 22, 2019 9:45 am 
Offline
Enthusiast
Enthusiast

Joined: Fri Oct 16, 2009 10:12 am
Posts: 631
Location: BE
Thank you very much Wilbert.

_________________
Yeah I know, but keep in mind ... Leonardo da Vinci was also an autodidact.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 24 posts ]  Go to page 1, 2  Next

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye