WORD/LONG ~ Key/Value ~ Tree
Chop Tree: comments
This is a small binary tree.
Key = 0 to 65,535
unique Keys
Long Value may not be NULL
- way faster than hash
- traverse Keys in order
- store/restore to string
ZIP: Chop2Tree_DLL-1.zip
Chop Tree: comments
This is a small binary tree.
Key = 0 to 65,535
unique Keys
Long Value may not be NULL
- way faster than hash
- traverse Keys in order
- store/restore to string
ZIP: Chop2Tree_DLL-1.zip
Code:
'pb 5/9 (4/8 should be OK) 'Two Chop Binary Tree (number Trie or Radix tree) 'WORD/LONG ~ Key/Value store ' Key = 0 to 65535 ' Key must be unique ' Value = any LONG except ZERO ' stored Value may NOT be NULL !!! ' ' memory use: (50,000 Word/Long pairs: 6 bytes) = 4 bytes per pair (including tree structure) ' uses less memory than an arrays of same size ' (if Keys are in somewhat of a sequence) ' ' Speed: faster than hash ' basically; it's a double Byte array lookup ' value = rootArr( childArr() ) ' ' the Keys aren't stored in the tree, only their path ' a Key is in tree if its path isn't NULL; we can still GetKey() ' ' Store/Restore from string ' ' - faster than hash ' - fast Set(), Remove() ' - don't have to worry about hash count ' - traverse tree in Key order ' - if Keys are in close sequence, tree acts as a compression algorithm ' ' name: "Two Chop" ' we chop the WORD key into two Bytes ' one Byte stored in root node ' next Byte stored in root's child ' the whole tree is only two nodes deep ' it's a Byte array of Byte arrays ' BUT: ' the adjustable range concept allows us the keep the tree as small as possible ' 'NOTE: this code implements a new breakthrough innovation for Trie/Radix nodes. ' It uses an adjustable range child node structure in each node. ' Each node's children array adjust to the widest range necessary; node.low, node.high ' The child node array expands and contracts as Keys are added/deleted. ' This post serves ar prior-art to the concept and may NOT be patented without my ppermission. ' (don't want to loose the right to use my own code) ' 'free; use at your own risk ' may NOT be used for sale as a lone product without permission Declare Function Chop2Tree_Alloc Lib "Chop2Tree_DLL-1.dll" () As Long 'allocate new instance - return handle Declare Sub Chop2Tree_Free Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) 'close tree - free all resources Declare Sub Chop2Tree_Clear Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) 'delete all data Declare Function Chop2Tree_Count Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) As Long 'get Key/Value count Declare Sub Chop2Tree_Set Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word, ByVal value As Long, ByVal replaceValue As Byte) 'add Key/Value to tree ' if Key exist and replaceValue = True then old value replaced with new value 'NOTE: Value can't be zero (zero Key OK) Declare Function Chop2Tree_Get Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word) As Long 'get Key's Value Declare Function Chop2Tree_FastGet Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word) As Long 'get Key's Value - no pointer are bounds checking ' warning!!! ' tree handle has to be good ' and Key has to be in tree ' otherwise, bad things will happen Declare Function Chop2Tree_Contains Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word) As Long 'True/False if Key in tree Declare Sub Chop2Tree_Remove Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word) 'remove Key/Value from tree Declare Function Chop2Tree_Store Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) As String 'store tree in string (persist) Declare Function Chop2Tree_StoreValidate Lib "Chop2Tree_DLL-1.dll" (ByRef storedTree As String) As Long 'validate storage string ' string has front and back DWord validation hash cookies Declare Sub Chop2Tree_Restore Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByRef storedTree As String) 'restore tree from string saved with Trie_Store() ' tree's current contents cleared '---------------------------------------------------------- ' ' Cursor Functions ' '---------------------------------------------------------- Declare Function Chop2Cursor_Alloc Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) As Long 'allocate new cursor - return handle Declare Sub Chop2Cursor_Free Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) 'free cursor Declare Function Chop2Cursor_GoFirst Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Long 'move to first Key in tree ' True/False Declare Function Chop2Cursor_GoNext Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Long 'move to next Key in tree ' True/False Declare Function Chop2Cursor_GoGetKey Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Word 'get Key at current position Declare Function Chop2Cursor_GoGetValue Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Long 'get Value at current position Declare Sub Chop2Cursor_GoSetValue Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long, ByVal value As Long) 'change Value at current position
Comment