00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2003--2009 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUCON_RBTREE_H 00019 #define CUCON_RBTREE_H 00020 00021 #include <cucon/fwd.h> 00022 #include <cu/clos.h> 00023 #include <cu/util.h> 00024 #include <stdio.h> 00025 00026 CU_BEGIN_DECLARATIONS 00027 /** \defgroup cucon_rbtree_h cucon/rbtree.h: Red-Black Trees 00028 ** @{ \ingroup cucon_maps_and_sets_mod 00029 ** 00030 ** \note This is a somewhat unstable low-level API used to define more 00031 ** friendly APIs like \ref cucon_rbset_h and \ref cucon_rbmap_h, so you 00032 ** probably want to use those instead. 00033 ** 00034 ** This is usual algorithm, but without back-links on the nodes to allow 00035 ** purely constructive updates if desired. The comparison predicate is passed 00036 ** explicitely to functions which use them. This makes it possible to define 00037 ** both sets and maps in terms of these trees, and it is also a way to allow 00038 ** keys to be stored directly on the slots. 00039 ** 00040 ** \see cucon_rbset_h 00041 ** \see cucon_rbmap_h 00042 **/ 00043 00044 /** A node of a red-black tree. */ 00045 struct cucon_rbnode 00046 { 00047 size_t is_black; /* size_t due to root-node packing, see bottom of file. */ 00048 struct cucon_rbnode *left; 00049 struct cucon_rbnode *right; 00050 /* variable size value */ 00051 }; 00052 00053 /** Return a pointer to the slot of \a node. */ 00054 CU_SINLINE void *cucon_rbnode_mem(cucon_rbnode_t node) 00055 { return CU_ALIGNED_MARG_END(cucon_rbnode_t, node); } 00056 00057 /** Retrun the slot of \a node assuming it is a pointer. */ 00058 CU_SINLINE void *cucon_rbnode_ptr(cucon_rbnode_t node) 00059 { return *(void **)cucon_rbnode_mem(node); } 00060 00061 /** The left subtree of \a node. */ 00062 CU_SINLINE cucon_rbnode_t 00063 cucon_rbnode_left(cucon_rbnode_t node) { return node->left; } 00064 00065 /** The right subtree of \a node. */ 00066 CU_SINLINE cucon_rbnode_t 00067 cucon_rbnode_right(cucon_rbnode_t node) { return node->right; } 00068 00069 /** The red-black tree structure. */ 00070 struct cucon_rbtree 00071 { 00072 struct cucon_rbnode *root; 00073 }; 00074 00075 /** Construct an empty tree. */ 00076 void cucon_rbtree_init(cucon_rbtree_t tree); 00077 00078 /** Return an empty tree. */ 00079 cucon_rbtree_t cucon_rbtree_new(void); 00080 00081 /** Construct a clone of \a src. Cloned trees must be modified with \c _ctive 00082 ** functions only, to avoid interference. */ 00083 void cucon_rbtree_cct_copy_ctive(cucon_rbtree_t tree, cucon_rbtree_t src); 00084 00085 /** Return a clone of \a src. Cloned trees must be modified with \c _ctive 00086 ** functions only, to avoid interference. */ 00087 cucon_rbtree_t cucon_rbtree_new_copy_ctive(cucon_rbtree_t src); 00088 00089 /** A node copier closure. */ 00090 CU_DOXY_FAKED 00091 typedef cu_clop(cucon_rbnode_copier_t, cucon_rbnode_t, cucon_rbnode_t) 00092 CU_DOXY_ENDFAKED(typedef __see_below__ cucon_rbnode_copier_t); 00093 00094 /** Make \a dst a deep copy of \a src, where \a node_new_copy\c (node) shall 00095 ** return a new copy of \c node, using \c cucon_rbnode_new_copy and filling in 00096 ** the slot. */ 00097 void cucon_rbtree_cct_copy_node(cucon_rbtree_t dst, cucon_rbtree_t src, 00098 cucon_rbnode_copier_t node_new_copy); 00099 00100 /** Return a deep copy of \a src, given that <code>\a node_new_copy(\e 00101 ** node)</code> returns a copy of \e node, using \ref cucon_rbnode_new_copy 00102 ** and filling in the slot. */ 00103 cucon_rbtree_t cucon_rbtree_new_copy_node(cucon_rbtree_t src, 00104 cucon_rbnode_copier_t node_new_copy); 00105 00106 /** Construct \a dst as a deep copy of \a src, assuming the slots are 00107 ** pointers. */ 00108 void cucon_rbtree_cct_copy_ptr(cucon_rbtree_t dst, cucon_rbtree_t src); 00109 00110 /** Return a deep copy of \a src, assuming the slots are pointers. */ 00111 cucon_rbtree_t cucon_rbtree_new_copy_ptr(cucon_rbtree_t src); 00112 00113 /** Create a copy of \a src, but with an uninitialised value slot of \a 00114 ** slot_size bytes. */ 00115 cucon_rbnode_t cucon_rbnode_new_copy(cucon_rbnode_t src, size_t slot_size); 00116 00117 /** Insert all elements of \a src into \a dst, assuming slots are pointers. */ 00118 void cucon_rbtree_merge2p(cucon_rbtree_t dst, cucon_rbtree_t src, 00119 cu_clop(cmp, int, void *, void *)); 00120 00121 /** Constructively insert all elements of \a src into \a dst, assuming slots 00122 ** are pointers. */ 00123 void cucon_rbtree_cmerge2p(cucon_rbtree_t dst, cucon_rbtree_t src, 00124 cu_clop(cmp, int, void *, void *)); 00125 00126 /** Return number of elements in the tree. */ 00127 CU_SINLINE size_t 00128 cucon_rbtree_size(cucon_rbtree_t tree) 00129 { 00130 return tree->root? tree->root->is_black : 0; 00131 } 00132 00133 /** True iff \a tree is empty. */ 00134 CU_SINLINE cu_bool_t 00135 cucon_rbtree_is_empty(cucon_rbtree_t tree) { return tree->root == NULL; } 00136 00137 /** The root node of \a tree. */ 00138 CU_SINLINE cucon_rbnode_t 00139 cucon_rbtree_root(cucon_rbtree_t tree) { return tree->root; } 00140 00141 /** Insert into \a tree an element which compares according to \a cmp1 where a 00142 ** negative, zero and positive return value means than the key is less than, 00143 ** equal to and greater than \a other_key, respectively. If \a cmp1 maps an 00144 ** existing element to 0, then <code>*\a slot</code> is set to point to its 00145 ** value slot, and false is returned. Otherwise, a new node is created with 00146 ** value of \a slot_size bytes at an address stored in \c *\a slot and true is 00147 ** returned. In the latter case, you should construct an object at \c *\a 00148 ** slot for which \a cmp1 gives 0. */ 00149 cu_bool_t 00150 cucon_rbtree_insert1m_mem(cucon_rbtree_t tree, 00151 cu_clop(cmp1, int, void *other_key), 00152 size_t slot_size, cu_ptr_ptr_t slot); 00153 00154 /** A contructive version of \ref cucon_rbtree_insert1m_mem. */ 00155 cu_bool_t 00156 cucon_rbtree_cinsert1m_mem(cucon_rbtree_t tree, 00157 cu_clop(cmp1, int, void *), 00158 cucon_rbnode_copier_t node_new_copy, 00159 size_t slot_size, cu_ptr_ptr_t slot); 00160 00161 /** Insert \a key into \a tree if not present, assuming the keys are stored in 00162 ** a leading pointer-valued field of the slots. Nodes are allocated with \a 00163 ** node_size bytes with cucon_rbnode_t at offset \a node_offset. An allocated 00164 ** or present node with key equal to \a key is stored at <code>*\a 00165 ** node_out</code>. If insertion was done, returns true, in which case only 00166 ** the key part of the returned slot is initialised. */ 00167 cu_bool_t 00168 cucon_rbtree_insert2p_node(cucon_rbtree_t tree, 00169 cu_clop(cmp2, int, void *, void *), void *key, 00170 size_t node_size, size_t node_offset, 00171 cucon_rbnode_t *node_out); 00172 00173 /* FIXME. Bad API. */ 00174 cu_bool_t 00175 cucon_rbtree_insert2p_ptr(cucon_rbtree_t tree, 00176 cu_clop(cmp2, int, void *, void *), 00177 cu_ptr_ptr_t ptr_io); 00178 cu_bool_t 00179 cucon_rbtree_cinsert2p_ptr(cucon_rbtree_t tree, 00180 cu_clop(cmp2, int, void *, void *), 00181 cu_ptr_ptr_t ptr_io); 00182 00183 /** If \a tree has a mapping for \a key set <code>*\a slot_o</code> to its 00184 ** mapping and return false, else create a new mapping with key initialised to 00185 ** \a key, set <code>*\a slot_o</code> to its slot, and return true. 00186 ** 00187 ** \pre The slots of \a tree are \a slot_size bytes which can be copied with 00188 ** \c memcpy, and starts with a \a key_size bytes key which can be compared 00189 ** with memcmp. (“imem” for “immediate memory”.) */ 00190 cu_bool_t 00191 cucon_rbtree_insert_imem_ctive(cucon_rbtree_t tree, 00192 size_t key_size, void *key, 00193 size_t slot_size, cu_ptr_ptr_t slot_o); 00194 00195 /** This function applies when slots of \a tree start with pointers to their 00196 ** keys. If \a tree contains a node with a key equal to \a key according to 00197 ** \a cmp2, then erase it from \a tree and return it, else return \c NULL. */ 00198 cucon_rbnode_t 00199 cucon_rbtree_erase2p(cucon_rbtree_t tree, 00200 cu_clop(cmp2, int, void *, void *), void *key); 00201 00202 /** Erase from \a tree the element which compares 0 according to \a cmp1 and 00203 ** return it's slot, or return \c NULL if not found. */ 00204 void *cucon_rbtree_erase1m(cucon_rbtree_t tree, cu_clop(cmp1, int, void *)); 00205 00206 /** This function applies when slots of \a tree start with pointers to their 00207 ** keys. Return the node from \a tree with a key equal to \a key according to 00208 ** \a cmp2, or \c NULL if none. */ 00209 cucon_rbnode_t 00210 cucon_rbtree_find2p_node(cucon_rbtree_t tree, 00211 cu_clop(cmp2, int, void *, void *), void *key); 00212 00213 /** Return a pointer to the slot of the node where \a cmp1 returns 0, or \c 00214 ** NULL if not found. */ 00215 void *cucon_rbtree_find1m_mem(cucon_rbtree_t tree, 00216 cu_clop(cmp1, int, void *)); 00217 00218 /** Return the slot, assuming it is a pointer, of the node where \a cmp2 00219 ** returns 0, or \c NULL if not found. */ 00220 void *cucon_rbtree_find2p_ptr(cucon_rbtree_t tree, 00221 cu_clop(cmp2, int, void *, void *), void *key); 00222 00223 void 00224 cucon_rbtree_nearest2p(cucon_rbtree_t tree, 00225 cu_clop(cmp2, int, void *, void *), void *key, 00226 cucon_rbnode_t *below_out, 00227 cucon_rbnode_t *equal_out, 00228 cucon_rbnode_t *above_out); 00229 00230 /** Applies \a cb to the pointers to slots of \a tree in order. */ 00231 void cucon_rbtree_iter_mem(cucon_rbtree_t tree, cu_clop(cb, void, void *val)); 00232 00233 /** Applies \a cb to pointers stored in the slots of \a tree in order. */ 00234 void cucon_rbtree_iter_ptr(cucon_rbtree_t tree, cu_clop(cb, void, void *val)); 00235 00236 /** Applies \a cb to the pointers to slots of \a tree in reverse order. */ 00237 void cucon_rbtree_rev_iter_mem(cucon_rbtree_t tree, cu_clop(cb, void, void *)); 00238 00239 /** Applies \a cb to pointers stored in the slots of \a tree in reverse 00240 ** order. */ 00241 void cucon_rbtree_rev_iter_ptr(cucon_rbtree_t tree, cu_clop(cb, void, void *)); 00242 00243 /** Applies \a cb on each value of \a tree in order, exiting immediately with 00244 ** false as soon as \a cb returns false, otherwise returns true. */ 00245 cu_bool_t cucon_rbtree_conj_mem(cucon_rbtree_t tree, 00246 cu_clop(cb, cu_bool_t, void *value)); 00247 00248 /** Applies \a cb on each pointer stored in the value slots of \a tree in 00249 ** order, exiting immediately with false as soon as \c cb returns false, 00250 ** otherwise returns true. */ 00251 cu_bool_t cucon_rbtree_conj_ptr(cucon_rbtree_t tree, 00252 cu_clop(cb, cu_bool_t, void *value)); 00253 00254 /** Applies \a cb on each value of \a tree in reverse order, exiting 00255 ** immediately with false as soon as \a cb returns false, otherwise returns 00256 ** true. */ 00257 cu_bool_t cucon_rbtree_rev_conj_mem(cucon_rbtree_t tree, 00258 cu_clop(cb, cu_bool_t, void *value)); 00259 00260 /** Applies \a cb on each pointer stored in the value slots of \a tree in 00261 ** reverse order, exiting immediately with false as soon as \c cb returns 00262 ** false, otherwise returns true. */ 00263 cu_bool_t cucon_rbtree_rev_conj_ptr(cucon_rbtree_t tree, 00264 cu_clop(cb, cu_bool_t, void *value)); 00265 00266 /** Debug dump of \a tree an graphviz format. */ 00267 void cucon_rbtree_dump_as_graphviz(cucon_rbtree_t tree, 00268 cu_clop(print_label, void, void *, FILE *), 00269 FILE *out); 00270 00271 /** @} */ 00272 CU_END_DECLARATIONS 00273 00274 #endif