PureBasic Forums - English

Code: Select all

;bitwise Trie wilbert, idle

Structure TrieNode   ; 4 * 4 bytes
  n.l[4]
EndStructure

Structure Trie
  *vt.l  
  nodes.TrieNode[256] ; offset 0
  firstMem.l          ; offset 4096
  currentMem.l        ; offset 4100
  memCount.l          ; offset 4104
  freeNodes.l         ; offset 4108
  nextNode.l          ; offset 4112
EndStructure

Structure TrieMem
  m.TrieNode[1023]    ; offset 0
  nextMem.l           ; offset 16368
EndStructure

Declare Trie_clear(*this.Trie)
Declare Trie_Free(*this.Trie)
Declare Trie_New() 
Declare Trie_SetValue(*this.Trie,key.l,value.l)
Declare.l Trie_GetValue(*this.Trie,key.l) 
Declare.s Trie_GetMemSize(*this.Trie) 

Interface Trie_Class 
  Clear()
  Free()
  Set(Key.l,value.l)
  Get(Key.l)
  GetSize.s()
EndInterface 

DataSection: vt_Trie: 
   Data.i @Trie_Clear()
   Data.i @Trie_Free()
   Data.i @Trie_SetValue()
   Data.i @Trie_GetValue()
   Data.i @Trie_GetMemSize()
EndDataSection
 

Procedure Trie_Clear(*this.Trie)
  Protected *mem.TrieMem, *nextMem.TrieMem, idx.l
  If *this
    *mem = *this\firstMem
    While *mem
      *nextMem = *mem\nextMem
      FreeMemory(*mem)
      *mem = *nextMem
    Wend
    FillMemory(*this\nodes[0], 4096)
    *this\firstMem = AllocateMemory(SizeOf(TrieMem))
    *this\currentMem = *this\firstMem
    *this\memCount = 1
    *this\freeNodes = 1023
    *this\nextNode = *this\currentMem
  EndIf 
EndProcedure

Procedure Trie_Free(*this.Trie)
  Protected *mem.TrieMem, *nextMem.TrieMem, idx.l
  If *this 
  *mem = *this\firstMem
  While *mem
    *nextMem = *mem\nextMem
     FreeMemory(*mem)
    *mem = *nextMem
  Wend
  FreeMemory(*this)
  EndIf 
  ProcedureReturn 0
EndProcedure

Procedure Trie_New()
  Protected *this.Trie
  *this = AllocateMemory(SizeOf(Trie))
  If *this
    *this\vt = ?vt_Trie 
     Trie_Clear(*this)
  EndIf  
  ProcedureReturn *this 
EndProcedure

Procedure.s Trie_GetMemSize(*this.Trie)
  Protected sz.s,size.i
  If *this
    size = SizeOf(Trie) + *this\memCount * SizeOf(TrieMem)
    If size < 1024
      sz = Str(size) + " bytes"
    ElseIf size < 1048576
      sz = Str(size/1024) + " kb"
    Else
      sz = Str(size/1048576) + " mb"
    EndIf
  EndIf 
  ProcedureReturn sz
EndProcedure

Procedure Trie_SetValue(*this.Trie, key.l, value.l)
   EnableASM
   MOV edx, *this
  MOV ecx, key
  !cmp edx, 0 
  !je lexit
  !add edx, 4
  !push ebx
  !push esi
  !rol ecx, 12
  !mov esi, ecx
  !and esi, 0xffc
  !add esi, edx
  !mov bl, 11
  !trie_set_loop:
  !mov eax, [esi]
  !and eax, eax                 ; check for zero pointer
  !jnz trie_set_cont
  ; ** allocate **
  !mov eax, [edx + 4112]        ; eax = *this\nextNode
  !mov [esi], eax
  !add dword [edx + 4112], 16   ; *this\nextNode + 16
  !dec dword [edx + 4108]       ; *this\freeNodes - 1
  !jnz trie_set_cont
  !push ecx
  !push edx
  CompilerSelect #PB_Compiler_OS
    CompilerCase #PB_OS_Windows 
      !push dword 16372
      !call _PB_AllocateMemory@4
    CompilerCase #PB_OS_Linux
      !PUSH   dword 16372
      !CALL   PB_AllocateMemory
       !add esp, 4
    CompilerCase #PB_OS_MacOS
      !sub esp, 4
      !push dword 16372
      !call _PB_AllocateMemory
      !add esp, 8
 CompilerEndSelect
  !pop edx
  !mov ecx, [edx + 4100]        ; ecx = *this\currentMem
  !mov [ecx + 16368], eax       ; set nextMem
  !mov [edx + 4100], eax        ; set currentMem
  !mov [edx + 4112], eax        ; set nextNode
  !inc dword [edx + 4104]       ; memCount + 1
  !mov dword [edx + 4108], 1023 ; freeNodes = 1023
  !pop ecx
  !mov eax, [esi]
  ; ** continue **
  !trie_set_cont:
  !rol ecx, 2
  !mov esi, ecx
  !and esi, 0xc
  !add esi, eax
  !dec bl
  !jnz trie_set_loop
  !mov eax, esi
  !pop esi
  !pop ebx
  MOV edx, value
  MOV [eax], edx
  DisableASM
  !jmp lexit1
  !lexit:
  !xor eax,eax
  !lexit1:
EndProcedure

Procedure.l Trie_GetValue(*this.Trie, key.l)
  EnableASM
  MOV edx, *this
  MOV ecx, key
  !cmp edx, 0 
  !je lexit2
  !add edx, 4
  !push esi
  !rol ecx, 12
  !mov esi, ecx
  !and esi, 0xffc
  !add esi, edx
  !mov dl, 12
  !trie_get_loop:
  !mov eax, [esi]
  !and eax, eax       ; check for zero pointer
  !jz trie_get_exit
  !rol ecx, 2         ; next 2 bits
  !mov esi, ecx
  !and esi, 0xc
  !add esi, eax
  !dec dl
  !jnz trie_get_loop
  !trie_get_exit:
  !pop esi
  DisableASM
  !jmp lexit3
  !lexit2:
  !xor eax,eax
  !lexit3:
  ProcedureReturn
EndProcedure


Global mt.Trie_Class = Trie_New()

Global size = 1024*1024
Global NewMap mp(size) 

start = ElapsedMilliseconds()
For a = 0 To size
  mt\Set(a,size-a)
Next

stop = ElapsedMilliseconds()
Trie_Add = stop-start

start = ElapsedMilliseconds()
For a = 0 To size
  mp(Str(a))=size-a; this line results in a crash on OS X when compiling without debug
Next
stop = ElapsedMilliseconds()
Map_add = Stop-start 

start = ElapsedMilliseconds()
For a = 0 To size
  x = mt\Get(a)
Next

stop = ElapsedMilliseconds()
Trie_time = stop-start

start = ElapsedMilliseconds()
For a = 0 To size
  x = mp(Str(a))
Next

stop = ElapsedMilliseconds()
map_time = stop-start

MessageRequester("Times","Trie Add = " + Str(Trie_Add) + " Trie Look = "+ Str(Trie_time)+#CRLF$+" Map Add= "+ Str(Map_add) + " Map look= " + Str(map_time))

mem.s = mt\GetSize()
MessageRequester("",mem)

mt\Free()

Code: Select all

 
numeration 
  #salloon
  #hacthback 
  #stationwaggon
  #van
EndEnumeration

Structure cars 
  type.i
  color.i
  id.i
EndStructure 

Global NewList listCars.cars()  ;create a list of cars that you want random access to 
Global myTrie.Trie_Class = Trie_New()  ;create a Trie 

For a = 1 To 100   
  AddElement(listCars()) ;add items To the List 
  listCars()\color =a 
  listCars()\type = a % 4  
  listCars()\id = a*10000
  myTrie\Set(a*10000,@listCars()) ;add the index (key) to the Trie along with the address of the list element  
 Next 

 For a = 1 To 100  
  car = (Random(99)+1)*10000  ;pick a random car to look up 
  ChangeCurrentElement(listCars(),myTrie\Get(car)) ;change the list element to the item returned from the trie 
 Debug "look up car " + Str(car)
 Debug listCars()\color
 Debug listCars()\id 
 Select listCars()\type
   Case #salloon
     Debug "salloon"
   Case #hacthback
     Debug "hatchback"
   Case #stationwaggon
     Debug "Station Waggon"
   Case #van 
     Debug "van"
 EndSelect
Next  

myTrie\free()