C Standard Library Extensions  1.2.3
cxtree.h
1 /*
2  * This file is part of the ESO C Extension Library
3  * Copyright (C) 2001-2017 European Southern Observatory
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 2 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18  */
19 
20 #ifndef CX_TREE_H
21 #define CX_TREE_H
22 
23 #include <cxmemory.h>
24 
25 CX_BEGIN_DECLS
26 
27 typedef struct _cx_tnode_ *cx_tree_iterator;
28 typedef const struct _cx_tnode_ *cx_tree_const_iterator;
29 
30 typedef struct _cx_tree_ cx_tree;
31 
72 typedef cxbool (*cx_tree_compare_func)(cxcptr, cxcptr);
73 
74 /*
75  * Create, copy and destroy operations
76  */
77 
78 cx_tree *cx_tree_new(cx_tree_compare_func, cx_free_func, cx_free_func);
79 void cx_tree_delete(cx_tree *);
80 
81 /*
82  * Nonmodifying operations
83  */
84 
85 cxsize cx_tree_size(const cx_tree *);
86 cxbool cx_tree_empty(const cx_tree *);
87 cxsize cx_tree_max_size(const cx_tree *);
88 cx_tree_compare_func cx_tree_key_comp(const cx_tree *);
89 
90 /*
91  * Special search operations
92  */
93 
94 cxsize cx_tree_count(const cx_tree *, cxcptr);
95 cx_tree_iterator cx_tree_find(const cx_tree *, cxcptr);
96 cx_tree_iterator cx_tree_lower_bound(const cx_tree *, cxcptr);
97 cx_tree_iterator cx_tree_upper_bound(const cx_tree *, cxcptr);
98 void cx_tree_equal_range(const cx_tree *, cxcptr, cx_tree_iterator *,
99  cx_tree_iterator *);
100 
101 /*
102  * Assignment operations
103  */
104 
105 void cx_tree_swap(cx_tree *, cx_tree *);
106 cxptr cx_tree_assign(cx_tree *, cx_tree_iterator, cxcptr);
107 
108 /*
109  * Element access
110  */
111 
112 cxptr cx_tree_get_key(const cx_tree *, cx_tree_const_iterator);
113 cxptr cx_tree_get_value(const cx_tree *, cx_tree_const_iterator);
114 
115 /*
116  * Iterator functions
117  */
118 
119 cx_tree_iterator cx_tree_begin(const cx_tree *);
120 cx_tree_iterator cx_tree_end(const cx_tree *);
121 cx_tree_iterator cx_tree_next(const cx_tree *, cx_tree_const_iterator);
122 cx_tree_iterator cx_tree_previous(const cx_tree *, cx_tree_const_iterator);
123 
124 
125 /*
126  * Inserting and removing elements
127  */
128 
129 cx_tree_iterator cx_tree_insert_unique(cx_tree *, cxcptr, cxcptr);
130 cx_tree_iterator cx_tree_insert_equal(cx_tree *, cxcptr, cxcptr);
131 void cx_tree_erase_position(cx_tree *, cx_tree_iterator);
132 void cx_tree_erase_range(cx_tree *, cx_tree_iterator, cx_tree_iterator);
133 cxsize cx_tree_erase(cx_tree *, cxcptr);
134 void cx_tree_clear(cx_tree *);
135 
136 /*
137  * Debugging
138  */
139 
140 cxbool cx_tree_verify(const cx_tree *);
141 
142 CX_END_DECLS
143 
144 #endif /* CX_TREE_H */
cx_tree_compare_func
cxbool(* cx_tree_compare_func)(cxcptr, cxcptr)
The tree's key comparison operator function.
Definition: cxtree.h:72
cx_tree_count
cxsize cx_tree_count(const cx_tree *tree, cxcptr key)
Get the number of elements matching a key.
Definition: cxtree.c:1616
cx_tree_end
cx_tree_iterator cx_tree_end(const cx_tree *tree)
Get an iterator for the position after the last pair in the tree.
Definition: cxtree.c:1056
cx_tree_upper_bound
cx_tree_iterator cx_tree_upper_bound(const cx_tree *tree, cxcptr key)
Find the end of a subsequence.
Definition: cxtree.c:1557
cx_tree_equal_range
void cx_tree_equal_range(const cx_tree *tree, cxcptr key, cx_tree_iterator *begin, cx_tree_iterator *end)
Find a subsequence matching a given key.
Definition: cxtree.c:1588
cx_tree_find
cx_tree_iterator cx_tree_find(const cx_tree *tree, cxcptr key)
Locate an element in the tree.
Definition: cxtree.c:1499
cx_tree_next
cx_tree_iterator cx_tree_next(const cx_tree *tree, cx_tree_const_iterator position)
Get an iterator for the next pair in the tree.
Definition: cxtree.c:1083
cx_tree_get_value
cxptr cx_tree_get_value(const cx_tree *tree, cx_tree_const_iterator position)
Get the data from a given iterator position.
Definition: cxtree.c:1468
cx_tree_insert_equal
cx_tree_iterator cx_tree_insert_equal(cx_tree *tree, cxcptr key, cxcptr data)
Insert data into a tree.
Definition: cxtree.c:1688
cx_tree_lower_bound
cx_tree_iterator cx_tree_lower_bound(const cx_tree *tree, cxcptr key)
Find the beginning of a subsequence.
Definition: cxtree.c:1528
cx_tree_erase_position
void cx_tree_erase_position(cx_tree *tree, cx_tree_iterator position)
Erase an element from a tree.
Definition: cxtree.c:1715
cx_malloc
cxptr cx_malloc(cxsize nbytes)
Allocate nbytes bytes.
Definition: cxmemory.c:280
cx_tree_clear
void cx_tree_clear(cx_tree *tree)
Remove all pairs from a tree.
Definition: cxtree.c:1148
cx_tree_erase
cxsize cx_tree_erase(cx_tree *tree, cxcptr key)
Erase all elements from a tree matching the provided key.
Definition: cxtree.c:1785
cx_tree_new
cx_tree * cx_tree_new(cx_tree_compare_func compare, cx_free_func key_destroy, cx_free_func value_destroy)
Create a new tree without any elements.
Definition: cxtree.c:1212
cx_tree_previous
cx_tree_iterator cx_tree_previous(const cx_tree *tree, cx_tree_const_iterator position)
Get an iterator for the previous pair in the tree.
Definition: cxtree.c:1117
cx_tree_begin
cx_tree_iterator cx_tree_begin(const cx_tree *tree)
Get an iterator to the first pair in the tree.
Definition: cxtree.c:1030
cx_free
void cx_free(cxptr memory)
Memory block deallocation.
Definition: cxmemory.c:486
cx_tree_key_comp
cx_tree_compare_func cx_tree_key_comp(const cx_tree *tree)
Get the key comparison function.
Definition: cxtree.c:1326
cx_tree_max_size
cxsize cx_tree_max_size(const cx_tree *tree)
Get the maximum number of pairs possible.
Definition: cxtree.c:1299
cx_tree_insert_unique
cx_tree_iterator cx_tree_insert_unique(cx_tree *tree, cxcptr key, cxcptr data)
Attempt to insert data into a tree.
Definition: cxtree.c:1661
cx_tree_erase_range
void cx_tree_erase_range(cx_tree *tree, cx_tree_iterator begin, cx_tree_iterator end)
Erase a range of elements from a tree.
Definition: cxtree.c:1749
cx_tree_verify
cxbool cx_tree_verify(const cx_tree *tree)
Validate a tree.
Definition: cxtree.c:1825
cx_tree_assign
cxptr cx_tree_assign(cx_tree *tree, cx_tree_iterator position, cxcptr data)
Assign data to an iterator position.
Definition: cxtree.c:1404
cx_tree_delete
void cx_tree_delete(cx_tree *tree)
Destroy a tree and all its elements.
Definition: cxtree.c:1250
cx_tree_get_key
cxptr cx_tree_get_key(const cx_tree *tree, cx_tree_const_iterator position)
Get the key from a given iterator position.
Definition: cxtree.c:1441
cx_tree_swap
void cx_tree_swap(cx_tree *tree1, cx_tree *tree2)
Swap the contents of two trees.
Definition: cxtree.c:1352
cx_tree_empty
cxbool cx_tree_empty(const cx_tree *tree)
Check whether a tree is empty.
Definition: cxtree.c:1176
cx_tree_size
cxsize cx_tree_size(const cx_tree *tree)
Get the actual number of pairs in the tree.
Definition: cxtree.c:1276