Whamcloud - gitweb
LU-4647 nodemap: add mapping functionality
[fs/lustre-release.git] / lustre / ptlrpc / nodemap_rbtree.c
1 /*
2  * GPL HEADER START
3  *
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
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.
9  *
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).
15  *
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
19  *
20  * GPL HEADER END
21  */
22 /*
23  * Copyright (C) 2013, Trustees of Indiana University
24  * Author: Joshua Walgenbach <jjw@iu.edu>
25  */
26
27 #include <lustre_net.h>
28 #include <linux/rbtree.h>
29 #include "nodemap_internal.h"
30
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.
36  *
37  * I didn't write this other than to change the
38  * function names to prevent collisions later.
39  */
40
41 static struct rb_node *nm_rb_left_deepest_node(const struct rb_node *node);
42
43 static struct rb_node *nm_rb_left_deepest_node(const struct rb_node *node)
44 {
45         while (true) {
46                 if (node->rb_left)
47                         node = node->rb_left;
48                 else if (node->rb_right)
49                         node = node->rb_right;
50                 else
51                         return (struct rb_node *) node;
52         }
53 }
54
55 struct rb_node *nm_rb_next_postorder(const struct rb_node *node)
56 {
57         const struct rb_node *parent;
58         if (!node)
59                 return NULL;
60         parent = rb_parent(node);
61
62         if (parent && node == parent->rb_left && parent->rb_right)
63                 return nm_rb_left_deepest_node(parent->rb_right);
64         else
65                 return (struct rb_node *) parent;
66 }
67
68 struct rb_node *nm_rb_first_postorder(const struct rb_root *root)
69 {
70         if (!root->rb_node)
71                 return NULL;
72
73         return nm_rb_left_deepest_node(root->rb_node);
74 }