embox

1
/**
2
 * @file
3
 * @brief Implementation of methods in util/tree.h
4
 *
5
 * @date Oct 8, 2011
6
 * @author Avdyukhin Dmitry
7
 */
8

9
#include <assert.h>
10
#include <stddef.h>
11

12
#include <lib/libds/dlist.h>
13
#include <lib/libds/tree.h>
14

15
struct tree_link *tree_postorder_next(struct tree_link *link) {
16
	if (link == NULL) {
17
		return NULL;
18
	}
19
	/* This node is a root. */
20
	if (link->par == NULL) {
21
		return NULL;
22
	}
23
	/* Search for the next element in brother list. */
24
	if (&link->list_link != (dlist_last_or_null(&link->par->children))) {
25
		/* It's not a last element in list. */
26
		/* TODO dirty hack. XXX O(n) time. */
27
		return tree_postorder_begin(
28
		    dlist_entry(link->list_link.next, struct tree_link, list_link));
29
	}
30
	else {
31
		/* Next link is a parent */
32
		return link->par;
33
	}
34
}
35

36
struct tree_link *tree_postorder_begin(struct tree_link *tree) {
37
	if (tree == NULL) {
38
		return NULL;
39
	}
40
	while (!dlist_empty(&tree->children)) {
41
		tree = dlist_entry(dlist_first(&tree->children), struct tree_link,
42
		    list_link);
43
	}
44
	return tree;
45
}
46

47
struct tree_link *tree_postorder_end(struct tree_link *tree) {
48
	return tree_postorder_next(tree);
49
}
50