Read tree

19.0.0 released Nov 08, 2023

Read tree

Purpose: Search a tree.

read-tree <tree> \
    ( key <key> | lesser <key> | greater <key> | \
        lesser-equal <key> | greater-equal <key> | \
        min-key | max-key ) \
    [ value [ define ] <value> ] \
    [ update-value <update value> [ process-value ] ] \
    [ old-key [ define ] <old key> ] \
    [ status [ define ] <status> ] \
    [ new-cursor [ define ] <cursor> ]

read-tree will search <tree> (created with new-tree) for a node with the key that is:

an exact key <key> ("key" clause)
lesser than <key> ("lesser" clause)
greater than <key> ("greater" clause)
lesser or equal than <key> ("lesser-equal" clause)
greater or equal than <key> ("greater-equal" clause)
a minimum key in the tree ("min-key" clause)
a maximum key in the tree ("max-key" clause)

The <status> in optional "status" clause will be VV_OKAY if a key conforming to one of these criteria is found, and VV_ERR_EXIST if not. <status> can be created with optional "define".

If a key is found, the value associated with the key can be obtained with optional "value" clause in <value>, which can be a pointer to any type; an existing key used to originally insert this value into the tree can be obtained with optional "old-key" clause in string <old key>. If a key is not found, both <value> and <old key> are unchanged. <value> and <old key> can be created with optional "define".

You can update the value associated with a found key by using optional "update-value" clause by specifying <update value> pointer to any type. This update is performed after an optional <value> has been retrieved, allowing you to obtain the previous value in the same statement. If the tree is created with "process-scope" clause, then <update value> must be Vely allocated memory; otherwise, <update value> must be a global C variable and "process-value" must be used to specify that (see scope discussion in new-tree for more).

If you'd like to iterate the ordered list of keys in a tree, create a <cursor> by using optional "new-cursor" clause, in which case <cursor> will be positioned on a found tree node. A cursor is a pointer to type "vely_tree_cursor". See use-cursor for more on using cursors. Cursors are useful in range searches; typically you'd find a key that is an upper or lower bound of a range and then keep iterating to a lesser or greater value until the opposite bound is found. Vely trees are by default constructed so that such iterations are O(1) in complexity, meaning each is a single tree node access (see new-tree). Note that <cursor> can be created with optional "define".

Examples

In this example, a million key/value pairs are inserted into a tree, and then each of them is searched for and then displayed back (see write-tree for more on inserting into a tree). The data is simply a numerical value of a key increased by 7:

%% /tree-example

    out-header default

    new-tree define mytree key-as "positive integer" // create new tree

    int i;
    for (i = 0; i < 1000000; i ++ ) {
        num-string i to define key
        num-string i+7 to define data

        write-tree mytree key (key) value data // insert key/data to the tree
    }

    for (i = 0; i < 1000000; i ++ ) {
        num-string i to define key

        // search tree for each key previously inserted
        read-tree mytree key (key) status define st value define data
        if (st != VV_OKAY){
            @Could not find key <<p-out key>>
        } else {
            @Found data <<p-out data>> associated with key <<p-out key>>
        }
        delete-mem key
    }
%%