/usr/include/yalecad/rbtree.h is in libycadgraywolf-dev 0.1.3-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 | /* -----------------------------------------------------------------
FILE: rbtree.h
DESCRIPTION:Tree include file for binary and red-black trees.
The same functionality as binary trees but better performance
for trees > 100 elements.
CONTENTS:
DATE: Mar 30, 1990
REVISIONS: Oct 8, 1990 - added prototypes and tree size.
Oct 22, 1990 - changed prototypes for rbtree_free.
Apr 19, 1991 - added Yrbtree_verify for debugging -RAW
Mon Aug 12 15:49:34 CDT 1991 - got rid of offset
argument to rbtree.
Sun Nov 3 12:55:27 EST 1991 - added missing function
definitions: Yrbtree_search_...
Fri Feb 7 16:29:58 EST 1992 - added Yrbtree_interval_size.
----------------------------------------------------------------- */
#ifndef RBTREE_H
#define RBTREE_H
#ifndef lint
static char YrbtreeId[] = "@(#) rbtree.h version 1.20 5/22/92" ;
#endif
#include <yalecad/base.h>
#ifndef YTREE_H_DEFS
typedef struct tree YTREEBOX ;
typedef struct tree *YTREEPTR ;
#endif
/* macro definition for tree structure see Yrbtree_init */
#define YRBTREE_INIT( tree_xz, compare_xz ) \
{ \
tree_xz = Yrbtree_init( compare_xz ) ; \
}
/* THE DEFINITIONS FOR SEARCH CLOSEST FUNCTIONALITY */
#define SEARCH_CLOSEST_NOP 0
#define SEARCH_CLOSEST_BELOW 1
#define SEARCH_CLOSEST_ABOVE 2
#define SEARCH_CLOSEST 3
/* ******************* BINARY TREE INCLUDE FILES ****************** */
extern YTREEPTR Yrbtree_init( P1(INT (*compare_func)() ) ) ;
/*
Arguments:
INT compare_func() ;
Function:
Initializes a binary tree. The user should supply a compare
comparison function similar to the one used by the UNIX
quicksort routine. The function compare_func is assumed to have
two arguments which are pointers to the arguments being compared.
The function should return an integer less than, equal to, or
greater than 0 according as the first argument is to be considered
less than, equal to , or greater than the second.
the distance in bytes that the key is offset from the beginning
of the data record. The function returns a pointer to the
tree data structure. Use the tree pointer returned by Yrbtree_init
for all routines to work on this tree. The comparison function
no longer needs to be unique. See Yrbtree_deleteCurrentEnumerate
and Yrbtree_deleteCurrentInterval for more details.
*/
extern VOIDPTR Yrbtree_search( P2(YTREEPTR tree, VOIDPTR key ) ) ;
/*
Arguments:
YTREEPTR tree ;
VOIDPTR key ;
Function:
Given a binary tree data structure, it return the a pointer
to the stored data object that matches the given key. It
returns NULL if no match is found. Sets the search marker
for subsequent search_suc and search_pred calls.
*/
extern VOIDPTR Yrbtree_min( P1(YTREEPTR tree) ) ;
/*
Arguments:
YTREEPTR tree ;
Function:
Given a binary tree data structure, it return the a pointer
to the minimum data object stored in the tree. It returns
NULL if nothing is in the tree. Sets the search marker for
subsequent search_suc and search_pred calls.
*/
extern VOIDPTR Yrbtree_max( P1(YTREEPTR tree ) ) ;
/*
Arguments:
YTREEPTR tree ;
Function:
Given a binary tree data structure, it return the a pointer
to the maximum data object stored in the tree. It returns
NULL if nothing is in the tree. Sets the search marker for
subsequent search_suc and search_pred calls.
*/
extern VOIDPTR Yrbtree_suc( P2(YTREEPTR tree, VOIDPTR key ) ) ;
/*
Arguments:
YTREEPTR tree ;
VOIDPTR key ;
Function:
Given a binary tree data structure, it return the a pointer
to the successor to the given key stored in the tree. It returns
NULL if nothing is in the tree or if no match to the key is found.
*/
extern VOID Yrbtree_insert( P2(YTREEPTR tree, VOIDPTR data ) ) ;
/*
Arguments:
YTREEPTR tree ;
VOIDPTR data ;
Function:
Insert an element into the tree. Data is a pointer to the users
record to be store in the tree. Each record must contain a key
to sort upon.
*/
extern VOIDPTR Yrbtree_enumerate( P2(YTREEPTR tree, BOOL startFlag) ) ;
/*
Arguments:
YTREEPTR tree ;
Function:
Enumerate all the data in a tree. First time call with startFlag
set to TRUE to get first element in tree starting at the minimum
element. For all subsequent calls, pass a FALSE argument to
get all the remaining members of the tree. Returns a pointer
to the user record. Returns NULL when all elements have been
requested or when no match can be found.
*/
extern VOID Yrbtree_enumeratePush( P1(YTREEPTR tree) ) ;
/*
Arguments:
YTREEPTR tree ;
Function:
Push the current enumeratation posistion pointer on to a
stack. This is useful if the user wishes to recursively
enumerate trees.
*/
extern VOID Yrbtree_enumeratePop( P1(YTREEPTR tree) ) ;
/*
Arguments:
YTREEPTR tree ;
Function:
Pop the current enumeratation posistion pointer off of the
stack. This is useful if the user wishes to recursively
enumerate trees.
*/
extern VOIDPTR Yrbtree_interval( P4(YTREEPTR tree, VOIDPTR low_key,
VOIDPTR high_key, BOOL startFlag ) ) ;
/*
Arguments:
YTREEPTR tree ;
VOIDPTR low_key, *high_key ;
BOOL startFlag;
Function:
Enumerate all the data in a tree between low_key and high_key.
First time call with startFlag=TRUE to get first element in
tree >= the low_key. For all subsequent calls, pass
startFlag=FALSE to get all the remaining members of the tree.
Returns NULL when element > high_key or no match can be found.
*/
extern INT Yrbtree_interval_size( P3(YTREEPTR tree,VOIDPTR low_key,
VOIDPTR high_key) ) ;
/*
Arguments:
YTREEPTR tree ;
VOIDPTR low_key, *high_key ;
Function:
Given an interval describe by the low and high keys, it returns the
number of elements in that interval.
*/
extern VOID Yrbtree_intervalPush( P1(YTREEPTR tree) ) ;
/*
Arguments:
YTREEPTR tree ;
Function:
Push the current interval posistion pointer on to a
stack. This is useful if the user wishes to recursively
enumerate trees.
*/
extern VOID Yrbtree_intervalPop( P1(YTREEPTR tree) ) ;
/*
Arguments:
YTREEPTR tree ;
Function:
Pop the current interval posistion pointer on to a
stack. This is useful if the user wishes to recursively
enumerate trees.
*/
extern VOID Yrbtree_interval_free( P4(YTREEPTR tree, VOIDPTR low_key,
VOIDPTR high_key, VOID (*userDelete)()) );
/*
Arguments:
YTREEPTR tree ;
VOIDPTR low_key, *high_key ;
BOOL startFlag;
Function:
Enumerate all the data in a tree between low_key and high_key.
All nodes between low_key and high_key are deleted from the tree.
The data can be freed by specifying the userDelete parameter.
See below for an example.
*/
extern BOOL Yrbtree_delete( P3(YTREEPTR tree, VOIDPTR key, VOID (*userDelete)() ) ) ;
/*
Arguments:
YTREEPTR tree ;
VOIDPTR key ;
Function:
Delete a node in the tree by using the key. If userDelete !=0,
the user delete function supplied is executed with the pointer of
the data stored at the tree node as its argument. For example,
when we need to delete the tree node we also need to free a field
of the data stored in addition to the data. If no user delete
function is supplied, only memory corresponding to the tree structure
is freed. .
.
.
Yrbtree_delete( my_tree, key, my_data_delete ) ;
.
.
.
VOID my_data_delete( data )
MY_DATA_TYPE *data ;
{
Ysafe_free( data->my_allocated_field ) ;
Ysafe_free( data ) ;
}
Returns 1 if successful, 0 otherwise.
*/
extern BOOL Yrbtree_deleteCurrentInterval(P2(YTREEPTR tree,VOID (*userDelete)()));
/*
Function:
While in an interval loop, deletes the current element. This allows
one to delete individual items that are not distinct with respect
to the comparison function. See the rbtree test program to see
how it is used.
*/
extern BOOL Yrbtree_deleteCurrentEnumerate(P2(YTREEPTR tree,VOID (*userDel)()));
/*
Function:
Like Yrbtree_deleteCurrentInterval, this routine is call from inside an
Yrbtree_enumerate loop. It will delete the current element and yet
allow the user to continue enumeration. This allows one to delete
individual items that are not distinct with respect to the comparison
function. See the rbtree test program to see how it is used.
*/
extern VOID Yrbtree_empty( P2(YTREEPTR tree, VOID (*userDelete)() ) ) ;
/*
Arguments:
YTREEPTR tree;
BOOL freeDataflag;
Function:
Removes all nodes in the tree. If userDelete != 0, node data
unallocated using userDelete function
*/
extern VOID Yrbtree_free( P2(YTREEPTR tree, VOID (*userDelete)() ) ) ;
/*
Arguments:
YTREEPTR tree;
BOOL freeDataflag;
Function:
Removes tree and all nodes in the tree. If userDelete != 0, node data
unallocated using userDelete function
*/
extern INT Yrbtree_size( P1(YTREEPTR tree) ) ;
/*
Function:
Find the total elements in the tree.
*/
extern INT(*Yrbtree_get_compare( P1(YTREEPTR tree) ))() ;
/*
Function:
Returns a pointer to the tree's comparison function.
*/
extern INT Yrbtree_verify( P1(YTREEPTR tree) ) ;
/*
Function:
Exercise tree pointers by walking through the tree.
Useful for dubugging.
The routine will fault or return a 0 if verification fails.
The routine will return a 1 if verification is successful.
*/
extern VOIDPTR Yrbtree_search_closest( P3(YTREEPTR tree,VOIDPTR key,INT func) ) ;
/*
Function:
Finds the closest match for a given key. Will return the exact
match if it exists. Returns NULL if no items exist in tree.
Sets the search marker for subsequent search_suc and search_pred
calls. Func is used to control the meaning of closest relative
to the comparison function. Ithas four values:
SEARCH_CLOSEST_NOP
SEARCH_CLOSEST
SEARCH_CLOSEST_BELOW
SEARCH_CLOSEST_ABOVE
SEARCH_CLOSEST_NOP should be specified when the comparison function
does not give an integer measure of the distance from a perfect match.
SEARCH_CLOSEST is the normal mode. It returns the closest element
to the key value based on the comparison functions return value.
SEARCH_CLOSEST_BELOW returns the element closest to the key which is
less than or equal to the given key.
SEARCH_CLOSEST_ABOVE returns the element closest to the key which is
greater than or equal to the given key.
*/
extern VOIDPTR Yrbtree_search_suc( P1(YTREEPTR tree) ) ;
/*
Function:
Returns the sucessor to current search object (set by the search
marker). Returns NULL if no such item exists. This routine
should only be called after the search marker has been set
by one of: Yrbtree_search_closest, Yrbtree_min, Yrbtree_max, or
Yrbtree_search.
*/
extern VOIDPTR Yrbtree_search_pred( P1(YTREEPTR tree) ) ;
/*
Function:
Returns the predecessor to current search object (set by the search
marker). Returns NULL if no such item exists. This routine
should only be called after the search marker has been set
by one of: Yrbtree_search_closest, Yrbtree_min, Yrbtree_max, or
Yrbtree_search.
*/
extern VOIDPTR Yrbtree_revlist( P2(YTREEPTR tree, BOOL startFlag) ) ;
/*
Function:
Enumerate the tree in reverse order.
*/
extern VOID Yrbtree_dump( P2(YTREEPTR tree, VOID (*print_key)() )) ;
/*
Function:
Dump the contents of a tree. Print keys takes one argument,
a key.
*/
extern VOID Yrbtree_resort( P2(YTREEPTR tree, INT (*compare_func)() )) ;
/*
Function:
Takes a tree and resorts the tree with a new comparison function.
All search markers are reset to NIL.
*/
extern YTREEPTR Yrbtree_copy( P2(YTREEPTR tree,INT (*compare_func)() ) );
/*
Function:
Make a copy of a tree sorted with the given comparison function.
Old tree remains allocated and all markers remain undisturbed.
*/
extern BOOL Yrbtree_insertIfUnique( P2(YTREEPTR tree, VOIDPTR data ) ) ;
/*
Arguments:
YTREEPTR tree ;
VOIDPTR data ;
Function:
Insert an element into the tree if it does exist in the tree.
Returns TRUE if added to tree; otherwise returns FALSE.
*/
#endif /* RBTREE_H */
|