Next: , Previous: , Up: Built-in functions   [Contents][Index]

#### n-ary tree functions

n-ary trees are used quite frequently in communication patterns because they require only logarithmic time (in the number of tasks) for a message to propagate from the root to a leaf. coNCePTuaL supports n-ary trees in the form of the `TREE_PARENT` and `TREE_CHILD` functions.

`TREE_PARENT` takes a task number and an optional tree fan-out (n) and returns the task’s parent in an n-ary tree. n defaults to ‘2’, i.e., a binary tree. Taking the `TREE_PARENT` of any task less than 1 returns the value ‘-1’.

Function: TREE_CHILD (task_ID, child [, fan-out])

`TREE_CHILD` takes a task number, a child number (0 <= i < N), and an optional tree fan-out (n), which again defaults to ‘2’. It returns the task number corresponding to the given task’s childth child.

The following illustrations show how tasks are numbered in, respectively, a 2-ary and a 3-ary tree:

As shown by the 2-ary tree, task 1’s children are task 3 and task 4. Therefore, ‘TREE_PARENT(3)’ and ‘TREE_PARENT(4)’ are both ‘1’; ‘TREE_CHILD(1, 0)’ is ‘3’; and, ‘TREE_CHILD(1, 1)’ is ‘4’. In a 3-ary tree, each task has three children. Hence, the following expressions hold:

• TREE_PARENT(7, 3)’ ⇒ ‘2
• TREE_PARENT(8, 3)’ ⇒ ‘2
• TREE_PARENT(9, 3)’ ⇒ ‘2
• TREE_CHILD(2, 0, 3)’ ⇒ ‘7
• TREE_CHILD(2, 1, 3)’ ⇒ ‘8
• TREE_CHILD(2, 2, 3)’ ⇒ ‘9

Next: , Previous: , Up: Built-in functions   [Contents][Index]

Scott Pakin, pakin@lanl.gov