source: rtems/cpukit/score/src/rbtreefind.c @ 469dc47

5
Last change on this file since 469dc47 was e9fbaa3b, checked in by Sebastian Huber <sebastian.huber@…>, on 08/21/15 at 03:59:49

rbtree: Replace implementation

Use the BSD <sys/tree.h> implementation since it is faster, more
flexible and uses less storage. See https://github.com/sebhub/rb-bench.

  • Property mode set to 100644
File size: 1.1 KB
Line 
1/**
2 * @file
3 *
4 * @brief Find the control structure of the tree containing the given node
5 * @ingroup ScoreRBTree
6 */
7
8/*
9 *  Copyright (c) 2010 Gedare Bloom.
10 *
11 *  The license and distribution terms for this file may be
12 *  found in the file LICENSE in this distribution or at
13 *  http://www.rtems.org/license/LICENSE.
14 */
15
16#if HAVE_CONFIG_H
17#include "config.h"
18#endif
19
20#include <rtems/score/rbtreeimpl.h>
21
22RBTree_Node *_RBTree_Find(
23  const RBTree_Control *the_rbtree,
24  const RBTree_Node    *the_node,
25  RBTree_Compare        compare,
26  bool                  is_unique
27)
28{
29  RBTree_Node *iter_node = _RBTree_Root( the_rbtree );
30  RBTree_Node *found = NULL;
31
32  while ( iter_node != NULL ) {
33    RBTree_Compare_result compare_result = ( *compare )( the_node, iter_node );
34
35    if ( _RBTree_Is_equal( compare_result ) ) {
36      found = iter_node;
37
38      if ( is_unique )
39        break;
40    }
41
42    if ( _RBTree_Is_greater( compare_result ) ) {
43      iter_node = _RBTree_Right( iter_node );
44    } else {
45      iter_node = _RBTree_Left( iter_node );
46    }
47  }
48
49  return found;
50}
Note: See TracBrowser for help on using the repository browser.