Merge pull request #13659 from donaldsharp/increase_mgmt_time

[mirror_frr.git] / lib / typerb.c

diff --git a/lib/typerb.c b/lib/typerb.c
index 092faa4cc9a51d0373a9334ee126e108a21c1ec7..af04307ca6ffd20d36ec05c0b6db4f7f712a126a 100644 (file)
--- a/lib/typerb.c
+++ b/lib/typerb.c
@@ -1,50 +1,19 @@
+// SPDX-License-Identifier: ISC AND BSD-2-Clause
 /* RB-tree */
 
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
- * All rights reserved.
- *
- * 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 AUTHOR ``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 AUTHOR 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.
  */
 
 /*
  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
 
+#include <string.h>
 #include "typerb.h"
 
 #define RB_BLACK       0
@@ -330,6 +299,7 @@ color:
                rbe_remove_color(rbt, parent, child);
 
        rbt->count--;
+       memset(old, 0, sizeof(*old));
        return (old);
 }
 
@@ -466,6 +436,28 @@ struct rb_entry *typed_rb_next(const struct rb_entry *rbe_const)
        return rbe;
 }
 
+struct rb_entry *typed_rb_prev(const struct rb_entry *rbe_const)
+{
+       struct rb_entry *rbe = (struct rb_entry *)rbe_const;
+
+       if (RBE_LEFT(rbe)) {
+               rbe = RBE_LEFT(rbe);
+               while (RBE_RIGHT(rbe))
+                       rbe = RBE_RIGHT(rbe);
+       } else {
+               if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
+                       rbe = RBE_PARENT(rbe);
+               else {
+                       while (RBE_PARENT(rbe)
+                              && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
+                               rbe = RBE_PARENT(rbe);
+                       rbe = RBE_PARENT(rbe);
+               }
+       }
+
+       return rbe;
+}
+
 struct rb_entry *typed_rb_min(const struct rbt_tree *rbt)
 {
        struct rb_entry *rbe = RBH_ROOT(rbt);
@@ -478,3 +470,24 @@ struct rb_entry *typed_rb_min(const struct rbt_tree *rbt)
 
        return parent;
 }
+
+struct rb_entry *typed_rb_max(const struct rbt_tree *rbt)
+{
+       struct rb_entry *rbe = RBH_ROOT(rbt);
+       struct rb_entry *parent = NULL;
+
+       while (rbe != NULL) {
+               parent = rbe;
+               rbe = RBE_RIGHT(rbe);
+       }
+
+       return parent;
+}
+
+bool typed_rb_member(const struct typed_rb_root *rbt,
+                    const struct typed_rb_entry *rbe)
+{
+       while (rbe->rbt_parent)
+               rbe = rbe->rbt_parent;
+       return rbe == rbt->rbt_root;
+}