4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.gnu.org/licenses/gpl-2.0.html
23 * Copyright (C) 2013, Trustees of Indiana University
24 * Author: Joshua Walgenbach <jjw@iu.edu>
27 #include <lustre_net.h>
28 #include <linux/rbtree.h>
29 #include "nodemap_internal.h"
31 /* This code is from a patch submitted by
32 * Cody P Schafer <cody@linux.vnet.ibm.com> linux kernel
33 * rbtree. When the supported kernel catches up to
34 * the kernel where it is landed. To remove the
35 * entire tree, it has to be done in postorder.
37 * I didn't write this other than to change the
38 * function names to prevent collisions later.
41 static struct rb_node *nm_rb_left_deepest_node(const struct rb_node *node);
43 static struct rb_node *nm_rb_left_deepest_node(const struct rb_node *node)
48 else if (node->rb_right)
49 node = node->rb_right;
51 return (struct rb_node *) node;
55 struct rb_node *nm_rb_next_postorder(const struct rb_node *node)
57 const struct rb_node *parent;
60 parent = rb_parent(node);
62 if (parent && node == parent->rb_left && parent->rb_right)
63 return nm_rb_left_deepest_node(parent->rb_right);
65 return (struct rb_node *) parent;
68 struct rb_node *nm_rb_first_postorder(const struct rb_root *root)
73 return nm_rb_left_deepest_node(root->rb_node);