source: rtems/cpukit/score/src/rbtreeiterate.c @ 4fc370e

4.115
Last change on this file since 4fc370e was f53aa8d, checked in by Gedare Bloom <gedare@…>, on 05/03/12 at 16:43:29

rbtree: API changes. Remove rbtree control node from RBTree_Next.

The implementation of RBTree_Next was using an awkward construction to detect
and avoid accessing the false root of the red-black tree. To deal with the
false root, RBTree_Next was comparing node parents with the control node.
Instead the false root can be detected by checking if the grandparent of a
node exists; the grandparent of the tree's true root is NULL by definition
so the root of the tree is found while walking up the tree by checking for
the non-existence of a grandparent.

This change propagates into the predecessor/successor and iterate functions.

  • Property mode set to 100644
File size: 976 bytes
Line 
1/**
2 * @file
3 *
4 * @ingroup ScoreRBTree
5 *
6 * @brief _RBTree_Iterate_unprotected() implementation.
7 */
8
9/*
10 * Copyright (c) 2012 embedded brains GmbH.  All rights reserved.
11 *
12 *  embedded brains GmbH
13 *  Obere Lagerstr. 30
14 *  82178 Puchheim
15 *  Germany
16 *  <rtems@embedded-brains.de>
17 *
18 * The license and distribution terms for this file may be
19 * found in the file LICENSE in this distribution or at
20 * http://www.rtems.com/license/LICENSE.
21 */
22
23#if HAVE_CONFIG_H
24  #include "config.h"
25#endif
26
27#include <rtems/score/rbtree.h>
28
29void _RBTree_Iterate_unprotected(
30  const RBTree_Control *rbtree,
31  RBTree_Direction dir,
32  RBTree_Visitor visitor,
33  void *visitor_arg
34)
35{
36  RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
37  const RBTree_Node *current = _RBTree_First( rbtree, opp_dir );
38  bool stop = false;
39
40  while ( !stop && current != NULL ) {
41    stop = (*visitor)( current, dir, visitor_arg );
42
43    current = _RBTree_Next_unprotected( current, dir );
44  }
45}
Note: See TracBrowser for help on using the repository browser.