summaryrefslogtreecommitdiff
path: root/cesar/lib/aatree.h
blob: 8e0c8475e642a1dbadb11d1104fd70ce236342a2 (plain)
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#ifndef lib_aatree_h
#define lib_aatree_h
/* Cesar project {{{
 *
 * Copyright (C) 2007 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \file    lib/aatree.h
 * \brief   Arne Andersson Trees.
 * \ingroup lib
 */

/* Set node. */
struct set_node_t
{
    /** Pointer to parent node. */
    set_node_t *father;
    /** Pointer to left and right children. */
    set_node_t *left, *right;
    /** Node level. */
    uint level;
};
/* Forward declaration in lib/set.h. */

BEGIN_DECLS

/**
 * Initialise a set.
 * \param  set  the set
 * \param  less  the "is lesser than" comparison function
 */
void
set_init (set_t *set, set_node_less_t less);

/**
 * Initialise a set node.
 * \param  node  the node to initialise
 */
void
set_node_init (set_node_t *node);

/**
 * Find a node inside a set.
 * \param  set  the set to look into
 * \param  node  node to compare with nodes inside the set
 * \return  the found node or NULL if none found
 *
 * The \a node parameter just have to contains enough data to be used with the
 * comparison function.
 */
set_node_t *
set_find (set_t *set, set_node_t *node);

/**
 * Insert a node.
 * \param  set  the set
 * \param  node  node to insert
 * \return  true if successful (not in the set yet)
 */
bool
set_insert (set_t *set, set_node_t *node);

/**
 * Remove a node from the set.
 * \param  set  the set
 * \param  node  the node to remove
 *
 * The node must be inside the set.
 */
void
set_remove (set_t *set, set_node_t *node);

/**
 * Return the first node.
 * \param  set  the set
 * \return  the minimum node
 */
set_node_t *
set_begin (set_t *set);

/**
 * Return the node after the last one.
 * \param  set  the set
 * \return  past the last node
 */
extern inline set_node_t *
set_end (set_t *set)
{
    return NULL;
}

/**
 * Return the next node.
 * \param  set  the set
 * \param  node  current node
 * \return  the following node
 */
set_node_t *
set_next (set_t *set, set_node_t *node);

/**
 * Return whether the set is empty.
 * \param  set  the set
 * \return  true if empty
 */
extern inline bool
set_empty (set_t *set)
{
    return set->root->level == 0;
}

/**
 * Return whether a node is in any set.
 * \param  node  initialised node
 * \return  true if the node is in a set
 */
extern inline bool
set_node_in_any_set (set_node_t *node)
{
    return node->level != 0;
}

/**
 * Swap nodes of to compatibles sets.
 * \param  a  first set
 * \param  b  second set
 */
void
set_swap (set_t *a, set_t *b);

END_DECLS

#endif /* lib_aatree_h */