Is there an easy way to adapt it to strings and random-sized structures? I have not used PB pointers very much. (I have used them more for data sections and procedures than strings or structures...)
Yes you just need to set the value of the trie with a pointer to some structure
Code: Select all
Structure UserData ;some structure you want to use to store with the trie
i.i
s.s
EndStructure
Global *puserdat.userdata
*puserdat = AllocateMemory(SizeOf(userdata)) ;make a new userdata item
*puserdat\i = a
*puserdat\s = Str(a)
Trie\Set(a,*puserdat) ;set the trie value with the pointer to the data
*puserdat = trie\get(a) ;get a userdata item
If *puserdat
Debug *puserdat\s
EndIf
Additionally you'll need the trie walk procedure so you can have the trie free the memory of your userdata
Regarding the speed it should be fairly close to a map but there are numerous factors to consider
which effect the performance of both.
The amendment with example
Code: Select all
EnableExplicit
DeclareModule TrieModule
; Mar 13, 2014: From BitModule, but reduced to minimal Trie features
;TrieModule
;Author Idle 17/11/13
;PB 5.20
;v1.3.4
;Description
;
;BitTrie ;builds a bit Trie key size determines the maximum number of items to add, eg 8=256 entries 16= 65596 entries ...
;stores an integer value with the key
Prototype BitTrieCB(value.i)
Interface IBitTrie ;bit Trie
Set(key,value)
Get(key)
Walk(*cb.bitTrieCB)
ByteCount()
Free()
EndInterface
Declare New_BitTrie(size=64) ;expected number of items
EndDeclareModule
; ------
; ------
Module TrieModule
Structure BitBufInfo
Size.q
Bytesused.q
Position.q
Misc.l
EndStructure
Structure BitBuffer
*vt
inf.bitbufinfo
*buf
EndStructure
Structure node
inext.i[2]
value.i
EndStructure
Structure BitTrie Extends bitBuffer
avail.i
EndStructure
Procedure New_BitTrie(size=64)
Protected *this.BitTrie
*this = AllocateMemory(SizeOf(bittrie))
*this\vt = ?vt_BitTrie
*this\inf\size = Size*SizeOf(node)
*this\inf\Bytesused = *this\inf\size
*this\inf\Position=SizeOf(node)
;*this\inf\misc = Round(Log(size) / Log(2),#PB_Round_Up) -1 ;not needed v1.3.3
*this\buf = AllocateMemory(*this\inf\Size)
*this\avail = *this\inf\size-SizeOf(node)
ProcedureReturn *this
EndProcedure
; ------
Procedure BitTrie_Add(*this.bittrie,key.i,val.i)
Protected *node.node,idx,a,lp
CompilerIf SizeOf(Integer) = 8
!bsr qword rax , qword [p.v_key]
!mov [p.v_lp] , rax
CompilerElse
!bsr dword eax , dword [p.v_key]
!mov [p.v_lp] , eax
CompilerEndIf
*node = *this\buf
For a = lp To 0 Step -1
idx = (key >> a) & 1
EnableExplicit
DeclareModule TrieModule
; Mar 13, 2014: From BitModule, but reduced to minimal Trie features
;TrieModule
;Author Idle 17/11/13
;PB 5.20
;v1.3.4
;Description
;
;BitTrie ;builds a bit Trie key size determines the maximum number of items to add, eg 8=256 entries 16= 65596 entries ...
;stores an integer value with the key
Prototype BitTrieCB(value.i)
Interface IBitTrie ;bit Trie
Set(key,value)
Get(key)
Walk(*cb.bitTrieCB)
ByteCount()
Free()
EndInterface
Declare New_BitTrie(size=64) ;expected number of items
EndDeclareModule
; ------
; ------
Module TrieModule
Structure BitBufInfo
Size.q
Bytesused.q
Position.q
Misc.l
EndStructure
Structure BitBuffer
*vt
inf.bitbufinfo
*buf
EndStructure
Structure node
inext.i[2]
value.i
EndStructure
Structure BitTrie Extends bitBuffer
avail.i
EndStructure
Procedure New_BitTrie(size=64)
Protected *this.BitTrie
*this = AllocateMemory(SizeOf(bittrie))
*this\vt = ?vt_BitTrie
*this\inf\size = Size*SizeOf(node)
*this\inf\Bytesused = *this\inf\size
*this\inf\Position=SizeOf(node)
;*this\inf\misc = Round(Log(size) / Log(2),#PB_Round_Up) -1 ;not needed v1.3.3
*this\buf = AllocateMemory(*this\inf\Size)
*this\avail = *this\inf\size-SizeOf(node)
ProcedureReturn *this
EndProcedure
; ------
Procedure BitTrie_Add(*this.bittrie,key.i,val.i)
Protected *node.node,idx,a,lp
CompilerIf SizeOf(Integer) = 8
!bsr qword rax , qword [p.v_key]
!mov [p.v_lp] , rax
CompilerElse
!bsr dword eax , dword [p.v_key]
!mov [p.v_lp] , eax
CompilerEndIf
*node = *this\buf
For a = lp To 0 Step -1
idx = (key >> a) & 1
If *node\inext[idx]
tpos = *node\inext[idx]
*node = *this\buf + *node\inext[idx]
ElseIf *this\avail > 0
*node\inext[idx] = *this\inf\Position
tpos =*this\inf\Position
*node = *this\buf +*this\inf\Position
*this\avail - SizeOf(node)
*this\inf\Position+SizeOf(node)
*this\inf\Bytesused = *this\inf\Position
Else
*this\avail = 64*SizeOf(node)
*this\inf\size + *this\avail
*this\buf = ReAllocateMemory(*this\buf,*this\inf\size)
*node = *this\buf+ tpos
*node\inext[idx] = *this\inf\Position
*node = *this\buf +*this\inf\Position
*this\avail - SizeOf(node)
*this\inf\Position+SizeOf(node)
*this\inf\Bytesused = *this\inf\Position
EndIf
Next
*node\value = val
EndProcedure
; ------
Procedure BitTrie_Get(*this.bittrie,key.i)
Protected *node.node,value,a,idx,lp
CompilerIf SizeOf(Integer) = 8
!bsr qword rax , qword [p.v_key]
!mov [p.v_lp] , rax
CompilerElse
!bsr dword eax , dword [p.v_key]
!mov [p.v_lp] , eax
CompilerEndIf
*node = *this\buf
For a = lp To 0 Step -1
idx = (key>>a) & 1
If *node
If *node\inext[idx]
*node = *this\buf + *node\inext[idx]
Else
Break
EndIf
Else
ProcedureReturn 0
EndIf
Next
ProcedureReturn *node\value
EndProcedure
; ------
Procedure BitTrie_Walk(*this.bitTrie,*cb.bitTrieCB)
Protected *node.node,*stack.Integer, spos,pos
*stack = AllocateMemory(*this\inf\size)
pos = SizeOf(node)
*node = *this\buf +pos
If *cb
spos = 0
While pos < *this\inf\Bytesused
*node = *this\buf +pos
If *node\value
*cb(*node\value)
EndIf
pos + SizeOf(node)
Wend
EndIf
EndProcedure
Procedure BitBuffer_GetByteCount(*this.bitbuffer)
If *this
ProcedureReturn *this\inf\BytesUsed
EndIf
EndProcedure
; ------
Procedure BitBuffer_Free(*this.bitbuffer)
If *this
FreeMemory(*this\buf)
FreeMemory(*this)
EndIf
EndProcedure
; ------
DataSection
vt_BitTrie: ; Interface IBitTrie:
Data.i @BitTrie_Add() ; Set(key,value)
Data.i @BitTrie_Get() ; Get(key)
Data.i @BitTrie_Walk()
Data.i @BitBuffer_GetByteCount() ; ByteCount()
Data.i @BitBuffer_Free() ; Free()
EndDataSection
EndModule
Structure UserData ;some structure you want to use to store with the trie
i.i
s.s
EndStructure
Procedure cbwalk(*puserdat.userdata) ;use the walk callback to free the userdata
Debug *puserdat\s
FreeMemory(*puserdat)
EndProcedure
Global trie.TrieModule::IBitTrie
Global *puserdat.userdata
Global a
trie = TrieModule::New_BitTrie(2048) ;create the trie with the amount of nodes you want
For a = 1 To 2048
*puserdat = AllocateMemory(SizeOf(userdata)) ;make a new userdata item
*puserdat\i = a ;set it
*puserdat\s = Str(a)
Trie\Set(a,*puserdat) ;add the userdata to the trie
Next
For a = 1 To 2048 Step 8
*puserdat = trie\get(a) ;get a userdata item
If *puserdat
Debug *puserdat\s
EndIf
Next
Debug "=================================="
trie\Walk(@cbwalk()) ;walk the trie to free the userdata
trie\Free() ;free the trie
If *node\inext[idx]
tpos = *node\inext[idx]
*node = *this\buf + *node\inext[idx]
ElseIf *this\avail > 0
*node\inext[idx] = *this\inf\Position
tpos =*this\inf\Position
*node = *this\buf +*this\inf\Position
*this\avail - SizeOf(node)
*this\inf\Position+SizeOf(node)
*this\inf\Bytesused = *this\inf\Position
Else
*this\avail = 64*SizeOf(node)
*this\inf\size + *this\avail
*this\buf = ReAllocateMemory(*this\buf,*this\inf\size)
*node = *this\buf+ tpos
*node\inext[idx] = *this\inf\Position
*node = *this\buf +*this\inf\Position
*this\avail - SizeOf(node)
*this\inf\Position+SizeOf(node)
*this\inf\Bytesused = *this\inf\Position
EndIf
Next
*node\value = val
EndProcedure
; ------
Procedure BitTrie_Get(*this.bittrie,key.i)
Protected *node.node,value,a,idx,lp
CompilerIf SizeOf(Integer) = 8
!bsr qword rax , qword [p.v_key]
!mov [p.v_lp] , rax
CompilerElse
!bsr dword eax , dword [p.v_key]
!mov [p.v_lp] , eax
CompilerEndIf
*node = *this\buf
For a = lp To 0 Step -1
idx = (key>>a) & 1
If *node
If *node\inext[idx]
*node = *this\buf + *node\inext[idx]
Else
Break
EndIf
Else
ProcedureReturn 0
EndIf
Next
ProcedureReturn *node\value
EndProcedure
; ------
Procedure BitTrie_Walk(*this.bitTrie,*cb.bitTrieCB)
Protected *node.node,*stack.Integer, spos,pos
*stack = AllocateMemory(*this\inf\size)
pos = SizeOf(node)
*node = *this\buf +pos
If *cb
spos = 0
While pos < *this\inf\Bytesused
*node = *this\buf +pos
If *node\value
*cb(*node\value)
EndIf
pos + SizeOf(node)
Wend
EndIf
EndProcedure
Procedure BitBuffer_GetByteCount(*this.bitbuffer)
If *this
ProcedureReturn *this\inf\BytesUsed
EndIf
EndProcedure
; ------
Procedure BitBuffer_Free(*this.bitbuffer)
If *this
FreeMemory(*this\buf)
FreeMemory(*this)
EndIf
EndProcedure
; ------
DataSection
vt_BitTrie: ; Interface IBitTrie:
Data.i @BitTrie_Add() ; Set(key,value)
Data.i @BitTrie_Get() ; Get(key)
Data.i @BitTrie_Walk()
Data.i @BitBuffer_GetByteCount() ; ByteCount()
Data.i @BitBuffer_Free() ; Free()
EndDataSection
EndModule
Structure UserData ;some structure you want to use to store with the trie
i.i
s.s
EndStructure
Procedure cbwalk(*puserdat.userdata) ;use the walk callback to free the userdata
Debug *puserdat\s
FreeMemory(*puserdat)
EndProcedure
Global trie.TrieModule::IBitTrie
Global *puserdat.userdata
Global a
trie = TrieModule::New_BitTrie(2048) ;create the trie with the amount of nodes you want
For a = 1 To 2048
*puserdat = AllocateMemory(SizeOf(userdata)) ;make a new userdata item
*puserdat\i = a ;set it
*puserdat\s = Str(a)
Trie\Set(a,*puserdat) ;add the userdata to the trie
Next
For a = 1 To 2048 Step 8
*puserdat = trie\get(a) ;get a userdata item
If *puserdat
Debug *puserdat\s
EndIf
Next
Debug "=================================="
trie\Walk(@cbwalk()) ;walk the trie to free the userdata
trie\Free() ;free the trie