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 }