[UDF] Tree - a named-node tree in flat arrays

[Numeric1]

Why I wrote this: the topic "Very simple tree data structure"
asks for exactly the two things this UDF tries to hold together - a tree that stays
simple to use, and one that is actually fast. Nothing here is taken from that code, it
is a separate implementation; I only reused the question. So this post is my answer to
the need posed in that thread, and the topic is where the discussion started.

Tree UDF is a tree data structure for AutoIt 3.3.16+. Every relation - parent, first
child, next sibling, depth, child count, payload - is one integer array read indexed by
the node id. There is no object, no DllCall, no UDT, no recursion in the hot paths, and
one instance per script.

What it gives you:

- Create a tree, add children to any node, add a whole "home\carol\docs" path in one call
- Read parent, child, sibling, depth, path, child count, subtree size
- Find a node by name without scanning the tree
- Move a subtree, delete a node with three different promises about its children
  (refuse / promote the children / delete the whole subtree)
- Walk in preorder through a callback, validate the whole structure.

32 public functions, every one documented in the file....
 The error codes as named constants ($TREE_E_*).
Remove is not left out: Tree_Remove covers refusing a non-empty node, promoting its
children, or dropping the whole subtree.   

#include "Tree.au3"

Tree_Create("company", 4096)          ; 4096 = how many nodes you expect
Local $iSales = Tree_Add(Tree_Root(), "", "sales")
Tree_Add($iSales, "alice", "alice")
Tree_AddPath("sales\paris\contracts", "\", 1240)

Local $i = Tree_Find("alice")
ConsoleWrite(Tree_Name(Tree_Parent($i)) & " / depth " & Tree_Depth($i) & @CRLF)

Local $aKids[1]
Local $n = Tree_Children($iSales, $aKids)   ; fills a 1-based array

The two things that decide whether it is fast are in the header: declare the capacity you
expect, because growing copies every array, and rebuild the derived preorder index once at
the end of a batch instead of after every change. Tree_IsClean() tells you where you stand.
For loops that touch every node, the $g_aTr* globals are public and documented as the fast
path - around a raw array read, the API call itself is most of the cost.

Honest limits, all of them named in the file and in the PDF: one tree instance per script;
not re-entrant, so a Tree_Walk callback must stay read-only; ids are recycled on delete, so
a stored id is only trustworthy until the next delete; names are case sensitive; payloads
containing a tab or a line break are flattened by the text export.

expandcollapse popup

; Tree_Example - a worked example of the Tree UDF.
#AutoIt3Wrapper_UseX64=n
#include "Tree.au3"

Opt("MustDeclareVars", 1)
Opt("TrayIconHide", 1)

; ==================================================================
; Tree_Example.au3 - the whole public surface in one readable pass.
;   AutoIt3.exe Tree_Example.au3
; Every number printed by section 7 is a measurement, not a claim; see
; Tree_Bench.log for the head-to-head.
; ==================================================================

; The walk callback has to be a top-level function. Returning < 0 stops.
Func _Show($iNode)
    Local $d = $g_aTrDepth[$iNode], $s = "", $k
    For $k = 1 To $d
        $s &= "  "
    Next
    Local $sName = $g_aTrName[$iNode]
    ConsoleWrite($s & $iNode & " " & ($sName <> "" ? $sName : "-") & " = " & $g_aTrData[$iNode] & @CRLF)
    Return 0
EndFunc   ;==>_Show

; --- 1. create and add named children -----------------------------------
Tree_Create("srv")
Local $app = Tree_Add(Tree_Root(), "apache 2.4", "app")
Local $log = Tree_Add(Tree_Root(), "/var/log", "log")
Tree_Add($log, "app.log", "app_log")
Tree_Add($log, "sys.log", "sys_log")
Tree_Add($app, "httpd.conf", "cfg")
ConsoleWrite("1  nodes after build: " & Tree_Count() & @CRLF)

; --- 2. one call for a whole path ---------------------------------------
Local $doc = Tree_AddPath("home\carol\docs", "\", "report.txt")
ConsoleWrite("2  AddPath -> id " & $doc & ", exact=" & @extended & ", depth=" & Tree_Depth($doc) & @CRLF)

; --- 3. lookup by name is a Map read, not a scan ------------------------
Local $f = Tree_Find("app_log")
ConsoleWrite("3  Find(app_log) -> " & $f & ", parent " & Tree_Parent($f) & ", name of parent " & Tree_Name(Tree_Parent($f)) & @CRLF)

; --- 4. children, siblings, ancestry -------------------------------------
; Both Tree_Children and Tree_PathTo fill a 1-based array and return the count.
Local $aKid[1]
Local $nKid = Tree_Children($log, $aKid)
ConsoleWrite("4  log has " & $nKid & " children: ")
For $k = 1 To $nKid
    ConsoleWrite($aKid[$k] & "(" & Tree_Name($aKid[$k]) & ") ")
Next
Local $c = Tree_FirstChild($log)
ConsoleWrite(@CRLF & "   sibling chain: ")
While $c <> 0
    ConsoleWrite($c & " ")
    $c = $g_aTrNext[$c]
WEnd
ConsoleWrite(@CRLF & "   app_log under app? " & Tree_IsAncestor($app, $f) & " / cfg under app? " & Tree_IsAncestor($app, Tree_Find("cfg")) & @CRLF)

; --- 5. the whole tree, preorder, through a callback ---------------------
ConsoleWrite("5  walk:" & @CRLF)
Tree_Walk("_Show", Tree_Root())

; --- 6. move a subtree, then ask about size ------------------------------
Tree_Move($f, $doc)
Tree_Rebuild()
ConsoleWrite("6  after move: docs subtree = " & Tree_SubtreeSize($doc) & " nodes, index clean = " & Tree_IsClean() & @CRLF)
Local $nPath = Tree_PathTo($doc, $aKid)
ConsoleWrite("   path to docs: " & $nPath & " steps, root first = " & $aKid[1] & ", node last = " & $aKid[$nPath] & @CRLF)

; --- 7. the hot loop reads the globals, not the API ----------------------
Local $t = TimerInit(), $iSum = 0, $iN = 200000
For $k = 1 To $iN
    $iSum += $g_aTrParent[1 + Mod($k, $g_iTrCount)]
Next
Local $tRaw = TimerDiff($t)
$t = TimerInit()
For $k = 1 To $iN
    $iSum += Tree_Parent(1 + Mod($k, $g_iTrCount))
Next
Local $tApi = TimerDiff($t)
ConsoleWrite("7  " & $iN & " parent reads: raw arrays " & Round($tRaw, 1) & " ms (" & Int($tRaw * 1000 / $iN) & " us), API " & Round($tApi, 1) & " ms (" & Int($tApi * 1000 / $iN) & " us) - sum " & $iSum & @CRLF)

; --- 8. remove, the lazy name index, and a text round trip ---------------
Local $killed = Tree_Remove($log, 2)
ConsoleWrite("8  removed " & $killed & " nodes, live now " & Tree_Count() & ", stale keys " & Tree_NameStale() & @CRLF)
ConsoleWrite("   Find(log) after delete -> " & Tree_Find("log") & " (error " & @error & ")" & @CRLF)
ConsoleWrite("   CompactNames -> " & Tree_CompactNames() & " live names, validate = " & Tree_Validate() & @CRLF)
Tree_Export(@ScriptDir & "\Tree_Example.tree")
Tree_Create("empty")
Local $nBack = Tree_Import(@ScriptDir & "\Tree_Example.tree")
ConsoleWrite("   import back: " & $nBack & " nodes added to the root, live " & Tree_Count() & ", Find(cfg) = " & Tree_Find("cfg") & @CRLF)

Attached:

 Tree.au3   

 

Tree_Quick_Start.pdf

Edited 5 minutes ago by Numeric1