diff options
Diffstat (limited to 'tools/gdb/python/rbtrees.py')
-rw-r--r-- | tools/gdb/python/rbtrees.py | 163 |
1 files changed, 163 insertions, 0 deletions
diff --git a/tools/gdb/python/rbtrees.py b/tools/gdb/python/rbtrees.py new file mode 100644 index 0000000..2e4c9e7 --- /dev/null +++ b/tools/gdb/python/rbtrees.py @@ -0,0 +1,163 @@ +# RTEMS Tools Project (http://www.rtems.org/) +# Copyright 2010-2015 Chris Johns (chrisj@rtems.org) +# All rights reserved. +# +# This file is part of the RTEMS Tools package in 'rtems-tools'. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions are met: +# +# 1. Redistributions of source code must retain the above copyright notice, +# this list of conditions and the following disclaimer. +# +# 2. Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE +# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +# POSSIBILITY OF SUCH DAMAGE. +# + +# +# RTEMS Red/Black Tree Support +# + +import gdb + +rbt_left = 0 +rbt_right = 1 + +def opp_dir(dir_): + if dir_ == rbt_left: + return rbt_right + return rbt_left + + +class node: + """Manage the RBTree_Node_struct.""" + + def __init__(self, node_ptr): + self.node_ptr = node_ptr + self.node_val = None + if node_ptr != 0: + print '}}}}' + self.node_val = node_ptr.dereference() + + def __str__(self): + return self.to_string() + + def null(self): + if not self.node_val: + return True + return False + + def pointer(self): + return self.node_ptr + + def parent(self): + if not self.null(): + return self.node_val['parent'] + return None + + def child(self): + if not self.null(): + return self.node_val['child'] + return None + + def left(self): + if not self.null(): + return self.node_val['child'][rbt_left] + return None + + def right(self): + if not self.null(): + return self.node_val['child'][rbt_right] + return None + + def next(self, dir_): + next_ = None + if not self.null(): + current = self.child(color, dir_) + if current is not None: + while current is not None: + cn = node(current) + current = cn.child(opp_dir(dir_)) + next_ = current + else: + # RBTree_Node *parent = node->parent; + # if ( parent->parent && node == parent->child[ opp_dir ] ) { + # + # node->parent + if self.parent(): + # pn = *(node->parent) or pn = *parent + pn = node(self.parent()) + if pn.parent() and (self.pointer() == pn.child(opp_dir(dir_))): + next_ = self.parent() + else: + nn = self + while pn.parent(): + if nn.pointer() != pn.child(dir_): + break + nn = pn + pn = node(pn.parent()) + if pn.parent(): + next_ = pn.pointer() + return next_ + + def predecessor(self): + return self.next(rbt_left) + + def successor(self): + return self.next(rbt_right) + + def color(self): + if not self.null(): + return self.node_val['color'] + return None + + def cast(self, typename): + if not self.null(): + nodetype = gdb.lookup_type(typename) + return self.node_val.cast(nodetype) + return None + + def off_tree(self): + if parent.null(): + return True + return False + + def to_string(self): + if self.null(): + return 'NULL' + print ']]] here' + return 'Parent:%s Child:%s Color:%s' % (self.node_val['parent'], + self.node_val['child'], + self.node_val['color']) + +class control: + """Manage the RBTree_Control.""" + + def __init__(self, ctrl): + self.ctrl = ctrl + + def root(self): + """Return the root node of the RBT.""" + return node(self.ctrl['root']) + + def first(self, dir_): + """ Return the min or max nodes of this RBT.""" + return node(self.ctrl['first'][dir_]) + + def empty(self): + if self.root().null(): + return True + return False |