equal
deleted
inserted
replaced
17 * information: Portions Copyright [yyyy] [name of copyright owner] |
17 * information: Portions Copyright [yyyy] [name of copyright owner] |
18 * |
18 * |
19 * CDDL HEADER END |
19 * CDDL HEADER END |
20 */ |
20 */ |
21 /* |
21 /* |
22 * Copyright 2008 Sun Microsystems, Inc. All rights reserved. |
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved. |
23 * Use is subject to license terms. |
23 * Use is subject to license terms. |
24 */ |
24 */ |
25 |
|
26 #pragma ident "%Z%%M% %I% %E% SMI" |
|
27 |
|
28 |
25 |
29 /* |
26 /* |
30 * AVL - generic AVL tree implementation for kernel use |
27 * AVL - generic AVL tree implementation for kernel use |
31 * |
28 * |
32 * A complete description of AVL trees can be found in many CS textbooks. |
29 * A complete description of AVL trees can be found in many CS textbooks. |
241 * NULL: the value is not in the AVL tree |
238 * NULL: the value is not in the AVL tree |
242 * *where (if not NULL) is set to indicate the insertion point |
239 * *where (if not NULL) is set to indicate the insertion point |
243 * "void *" of the found tree node |
240 * "void *" of the found tree node |
244 */ |
241 */ |
245 void * |
242 void * |
246 avl_find(avl_tree_t *tree, void *value, avl_index_t *where) |
243 avl_find(avl_tree_t *tree, const void *value, avl_index_t *where) |
247 { |
244 { |
248 avl_node_t *node; |
245 avl_node_t *node; |
249 avl_node_t *prev = NULL; |
246 avl_node_t *prev = NULL; |
250 int child = 0; |
247 int child = 0; |
251 int diff; |
248 int diff; |