Pointer trees

This page has been automatically translated using the Google Translate API services. We are working on improving texts. Thank you for your understanding and patience.

Header

#include <core/treept.h>

Functions

Just as we saw with ArrPt and SetPt, the TreePt type are N-ary trees (see Trees) where each node stores a pointer to the object instead of the complete object (Figure 1). Therefore, everything seen in Trees applies (root creation, depth-first traversal, navigating between nodes, copy, serialization...), replacing each function with its treept_* equivalent. The particularities to keep in mind are the same ones we already saw between Arrays/Pointer arrays and Sets/Pointer sets:

• You have to create and free dynamic memory for each object.
• The value NULL can be stored in any node.
• It is safer if other parts of the application keep pointers to the objects stored in the tree.
• It is the only option to work with opaque objects.

1. Create pointer trees

• Use treept_create to create an empty tree.
• Use treept_root_new to create the root node.
• Use treept_node_insert to add child nodes.
• Use DeclPt to declare pointer types to struct.

The main difference with respect to Trees lies in the fact that both treept_root_new and treept_node_insert receive as a parameter the pointer to the already created object, instead of returning an indeterminate memory area to initialize afterward (Listing 1).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

typedef struct _category_t Category;
struct _category_t
{
    String *name;
};

DeclPt(Category);

static Category *i_create(const char_t *name)
{
    Category *cat = heap_new(Category);
    cat->name = str_c(name);
    return cat;
}

static void i_destroy(Category **cat)
{
    str_destroy(&(*cat)->name);
    heap_delete(cat, Category);
}

TreePt(Category) *categories = treept_create(Category);
NodePt(Category) *root = treept_root_new(categories, i_create("Electronics"), Category);
NodePt(Category) *computers = treept_node_insert(root, 0, i_create("Computers"), Category);
treept_node_insert(computers, 0, i_create("Laptops"), Category);
treept_node_insert(root, 1, i_create("Audio and Video"), Category);
...
treept_destroy(&categories, i_destroy, Category);

The rest of the operations (depth-first traversal, navigating between nodes, copy, serialization or deletion) work exactly the same as in Trees, replacing treest_node_data with treept_node_data, which in this case returns the pointer stored in the node (which can be NULL).

treept_create ()

Create an empty pointer tree, without a root node.

TreePt(type)*
treept_create(type);

Return

The new tree.

Remarks

See Create pointer trees.

treept_copy ()

Create a complete copy of a pointer tree.

TreePt(type)*
treept_copy(const TreePt(type) *tree,
            FPtr_copy func_copy,
            type);

Return

The copy of the original tree.

Remarks

The copy function must create a dynamic object and allocate memory for the internal fields that require it. If we pass NULL, the original pointers will be copied, which can pose an integrity risk since the same object could be destroyed twice if we are not careful.

treept_read ()

Create a pointer tree by reading its contents from a Streams.

TreePt(type)*
treept_read(Stream *stream,
            FPtr_read func_read,
            type);

Return

The tree readed.

treept_read_ex ()

Create a pointer tree by reading its contents from a Streams. The read function accepts data from the user.

TreePt(type)*
treept_read_ex(Stream *stream,
               FPtr_read_ex func_read,
               dtype *data,
               type,
               dtype);

Return

The tree readed.

treept_destroy ()

Destroy a tree and all its nodes.

void
treept_destroy(TreePt(type) **tree,
               FPtr_destroy func_destroy,
               type);

treept_destopt ()

Destroy a tree and all its nodes, as long as the tree object is not NULL.

void
treept_destopt(TreePt(type) **tree,
               FPtr_destroy func_destroy,
               type);

treept_clear ()

Delete all the nodes of the tree, including the root, leaving it empty without destroying the container.

void
treept_clear(TreePt(type) *tree,
             FPtr_destroy func_destroy,
             type);

treept_write ()

Write a pointer tree in a Streams.

void
treept_write(Stream *stream,
             const TreePt(type) *tree,
             FPtr_write func_write,
             type);

treept_write_ex ()

Write a pointer tree in a Streams. The write function accepts user data.

void
treept_write_ex(Stream *stream,
                const TreePt(type) *tree,
                FPtr_write_ex func_write,
                const dtype *data,
                type,
                dtype);

treept_esize ()

Get the size in bytes stored in each node, that is, the size of a pointer.

uint32_t
treept_esize(const TreePt(type) *tree,
             type);

Return

Size in bytes.

treept_mem ()

Get the total memory, in bytes, occupied by the tree structure (nodes and pointers, not counting the memory of the referenced objects).

uint32_t
treept_mem(const TreePt(type) *tree,
           type);

Return

Memory in bytes.

treept_root_get ()

Get the root node of the tree.

NodePt(type)*
treept_root_get(TreePt(type) *tree,
                type);

Return

The root node, or NULL if the tree is empty.

Remarks

See Create pointer trees.

treept_root_get_const ()

Const version of treept_root_get.

const NodePt(type)*
treept_root_get_const(const TreePt(type) *tree,
                      type);

Return

The root node.

treept_root_new ()

Create the root node of an empty tree.

NodePt(type)*
treept_root_new(TreePt(type) *tree,
                type *ptr,
                type);

Return

The new root node.

Remarks

It can only be invoked once per tree. Use treept_node_insert to add descendants to it. See Create pointer trees.

treept_dfs_first ()

Set the internal iterator to the first node of the depth-first traversal (the root).

NodePt(type)*
treept_dfs_first(TreePt(type) *tree,
                 type);

Return

The first node, or NULL if the tree is empty.

treept_dfs_first_const ()

Const version of treept_dfs_first.

const NodePt(type)*
treept_dfs_first_const(const TreePt(type) *tree,
                       type);

Return

The first node.

treept_dfs_last ()

Set the internal iterator to the last node of the depth-first traversal (the deepest descendant of the root's last child).

NodePt(type)*
treept_dfs_last(TreePt(type) *tree,
                type);

Return

The last node, or NULL if the tree is empty.

treept_dfs_last_const ()

Const version of treept_dfs_last.

const NodePt(type)*
treept_dfs_last_const(const TreePt(type) *tree,
                      type);

Return

The last node.

treept_next ()

Advance the internal iterator to the next node of the depth-first traversal.

NodePt(type)*
treept_next(TreePt(type) *tree,
            type);

Return

The next node, or NULL if the traversal has finished.

treept_next_const ()

Const version of treept_next.

const NodePt(type)*
treept_next_const(const TreePt(type) *tree,
                  type);

Return

The next node.

treept_prev ()

Move the internal iterator back to the previous node of the depth-first traversal.

NodePt(type)*
treept_prev(TreePt(type) *tree,
            type);

Return

The previous node, or NULL if the traversal has finished.

treept_prev_const ()

Const version of treept_prev.

const NodePt(type)*
treept_prev_const(const TreePt(type) *tree,
                  type);

Return

The previous node.

treept_dfs_stop ()

Cancel a traversal in progress before reaching its end, releasing the tree's internal iterator.

void
treept_dfs_stop(TreePt(type) *tree,
                type);

treept_node_size ()

Get the number of direct children of a node.

uint32_t
treept_node_size(const NodePt(type) *node,
                 type);

Return

Number of children.

treept_node_depth ()

Get the depth of a node, that is, its distance to the root.

uint32_t
treept_node_depth(const NodePt(type) *node,
                  type);

Return

The depth. The root has depth 0.

treept_node_index ()

Get the position of a node among its parent's children.

uint32_t
treept_node_index(const NodePt(type) *node,
                  type);

Return

The node's index.

treept_node_parent ()

Get the parent node.

NodePt(type)*
treept_node_parent(NodePt(type) *node,
                   type);

Return

The parent node, or NULL if node is the root.

treept_node_parent_const ()

Const version of treept_node_parent.

const NodePt(type)*
treept_node_parent_const(const NodePt(type) *node,
                         type);

Return

The parent node.

treept_node_get ()

Get the child located at position pos.

NodePt(type)*
treept_node_get(NodePt(type) *node,
                const uint32_t pos,
                type);

Return

The child node.

treept_node_get_const ()

Const version of treept_node_get.

const NodePt(type)*
treept_node_get_const(const NodePt(type) *node,
                      const uint32_t pos,
                      type);

Return

The child node.

treept_node_insert ()

Insert a new child node at position pos.

NodePt(type)*
treept_node_insert(NodePt(type) *node,
                   const uint32_t pos,
                   type *ptr,
                   type);

Return

The new node.

Remarks

See Create pointer trees.

treept_node_delete ()

Delete a child node and the entire subtree that hangs from it.

void
treept_node_delete(NodePt(type) *node,
                   const uint32_t pos,
                   FPtr_destroy func_destroy,
                   type);

treept_node_data ()

Get the pointer to the object stored in a node.

type*
treept_node_data(NodePt(type) *node,
                 type);

Return

The stored pointer, which can be NULL.

treept_node_data_const ()

Const version of treept_node_data.

const type*
treept_node_data_const(const NodePt(type) *node,
                       type);

Return

The stored pointer.

treept_foreach ()

Traverse all the nodes of the tree depth-first. Use treept_end to close the loop.

void
treept_foreach(type *elem,
               TreePt(type) *tree,
               type);

treept_foreach_const ()

Const version of treept_foreach.

void
treept_foreach_const(const type *elem,
                     const TreePt(type) *tree,
                     type);

treept_forback ()

Traverse all the nodes of the tree in reverse order of the depth-first traversal. Use treept_end to close the loop.

void
treept_forback(type *elem,
               TreePt(type) *tree,
               type);

treept_forback_const ()

Const version of treept_forback.

void
treept_forback_const(const type *elem,
                     const TreePt(type) *tree,
                     type);

treept_end ()

Close the loop opened by treept_foreach, treept_foreach_const, treept_forback or treept_forback_const.

void
treept_end(void);