- (djm) Sync sys/tree.h with OpenBSD -current. Rename tree.h and

[openssh.git] / openbsd-compat / sys-tree.h

diff --git a/openbsd-compat/tree.h b/openbsd-compat/sys-tree.h
similarity index 97%
rename from openbsd-compat/tree.h
rename to openbsd-compat/sys-tree.h
index 30b4a8561ce3a19921d24c4aedd6c42a3582833b..0a58710c94dc5c23bdcd6e011d25aaaf5e67ab92 100644 (file)
--- a/openbsd-compat/tree.h
+++ b/openbsd-compat/sys-tree.h
@@ -1,3 +1,4 @@
+/*     $OpenBSD: tree.h,v 1.6 2002/06/11 22:09:52 provos Exp $ */
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  * All rights reserved.
@@ -113,8 +114,47 @@ struct {                                                           \
 #define SPLAY_PROTOTYPE(name, type, field, cmp)                                \
 void name##_SPLAY(struct name *, struct type *);                       \
 void name##_SPLAY_MINMAX(struct name *, int);                          \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *);                \
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *);                \
                                                                        \
-static __inline void                                                   \
+/* Finds the node with the same key as elm */                          \
+static __inline struct type *                                          \
+name##_SPLAY_FIND(struct name *head, struct type *elm)                 \
+{                                                                      \
+       if (SPLAY_EMPTY(head))                                          \
+               return(NULL);                                           \
+       name##_SPLAY(head, elm);                                        \
+       if ((cmp)(elm, (head)->sph_root) == 0)                          \
+               return (head->sph_root);                                \
+       return (NULL);                                                  \
+}                                                                      \
+                                                                       \
+static __inline struct type *                                          \
+name##_SPLAY_NEXT(struct name *head, struct type *elm)                 \
+{                                                                      \
+       name##_SPLAY(head, elm);                                        \
+       if (SPLAY_RIGHT(elm, field) != NULL) {                          \
+               elm = SPLAY_RIGHT(elm, field);                          \
+               while (SPLAY_LEFT(elm, field) != NULL) {                \
+                       elm = SPLAY_LEFT(elm, field);                   \
+               }                                                       \
+       } else                                                          \
+               elm = NULL;                                             \
+       return (elm);                                                   \
+}                                                                      \
+                                                                       \
+static __inline struct type *                                          \
+name##_SPLAY_MIN_MAX(struct name *head, int val)                       \
+{                                                                      \
+       name##_SPLAY_MINMAX(head, val);                                 \
+        return (SPLAY_ROOT(head));                                     \
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp)                         \
+struct type *                                                          \
 name##_SPLAY_INSERT(struct name *head, struct type *elm)               \
 {                                                                      \
     if (SPLAY_EMPTY(head)) {                                           \
@@ -132,17 +172,18 @@ name##_SPLAY_INSERT(struct name *head, struct type *elm)          \
                    SPLAY_LEFT(elm, field) = (head)->sph_root;          \
                    SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
            } else                                                      \
-                   return;                                             \
+                   return ((head)->sph_root);                          \
     }                                                                  \
     (head)->sph_root = (elm);                                          \
+    return (NULL);                                                     \
 }                                                                      \
                                                                        \
-static __inline void                                                   \
+struct type *                                                          \
 name##_SPLAY_REMOVE(struct name *head, struct type *elm)               \
 {                                                                      \
        struct type *__tmp;                                             \
        if (SPLAY_EMPTY(head))                                          \
-               return;                                                 \
+               return (NULL);                                          \
        name##_SPLAY(head, elm);                                        \
        if ((cmp)(elm, (head)->sph_root) == 0) {                        \
                if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
@@ -153,47 +194,13 @@ name##_SPLAY_REMOVE(struct name *head, struct type *elm)          \
                        name##_SPLAY(head, elm);                        \
                        SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
                }                                                       \
+               return (elm);                                           \
        }                                                               \
-}                                                                      \
-                                                                       \
-/* Finds the node with the same key as elm */                          \
-static __inline struct type *                                          \
-name##_SPLAY_FIND(struct name *head, struct type *elm)                 \
-{                                                                      \
-       if (SPLAY_EMPTY(head))                                          \
-               return(NULL);                                           \
-       name##_SPLAY(head, elm);                                        \
-       if ((cmp)(elm, (head)->sph_root) == 0)                          \
-               return (head->sph_root);                                \
        return (NULL);                                                  \
 }                                                                      \
                                                                        \
-static __inline struct type *                                          \
-name##_SPLAY_NEXT(struct name *head, struct type *elm)                 \
-{                                                                      \
-       name##_SPLAY(head, elm);                                        \
-       if (SPLAY_RIGHT(elm, field) != NULL) {                          \
-               elm = SPLAY_RIGHT(elm, field);                          \
-               while (SPLAY_LEFT(elm, field) != NULL) {                \
-                       elm = SPLAY_LEFT(elm, field);                   \
-               }                                                       \
-       } else                                                          \
-               elm = NULL;                                             \
-       return (elm);                                                   \
-}                                                                      \
-                                                                       \
-static __inline struct type *                                          \
-name##_SPLAY_MIN_MAX(struct name *head, int val)                       \
-{                                                                      \
-       name##_SPLAY_MINMAX(head, val);                                 \
-        return (SPLAY_ROOT(head));                                     \
-}
-
-/* Main splay operation.
- * Moves node close to the key of elm to top
- */
-#define SPLAY_GENERATE(name, type, field, cmp)                         \
-void name##_SPLAY(struct name *head, struct type *elm)                 \
+void                                                                   \
+name##_SPLAY(struct name *head, struct type *elm)                      \
 {                                                                      \
        struct type __node, *__left, *__right, *__tmp;                  \
        int __comp;                                                     \
@@ -367,7 +374,7 @@ struct {                                                            \
 #define RB_PROTOTYPE(name, type, field, cmp)                           \
 void name##_RB_INSERT_COLOR(struct name *, struct type *);     \
 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
-void name##_RB_REMOVE(struct name *, struct type *);                   \
+struct type *name##_RB_REMOVE(struct name *, struct type *);           \
 struct type *name##_RB_INSERT(struct name *, struct type *);           \
 struct type *name##_RB_FIND(struct name *, struct type *);             \
 struct type *name##_RB_NEXT(struct name *, struct type *);             \
@@ -498,17 +505,17 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
                RB_COLOR(elm, field) = RB_BLACK;                        \
 }                                                                      \
                                                                        \
-void                                                                   \
+struct type *                                                          \
 name##_RB_REMOVE(struct name *head, struct type *elm)                  \
 {                                                                      \
-       struct type *child, *parent;                                    \
+       struct type *child, *parent, *old = elm;                        \
        int color;                                                      \
        if (RB_LEFT(elm, field) == NULL)                                \
                child = RB_RIGHT(elm, field);                           \
        else if (RB_RIGHT(elm, field) == NULL)                          \
                child = RB_LEFT(elm, field);                            \
        else {                                                          \
-               struct type *old = elm, *left;                          \
+               struct type *left;                                      \
                elm = RB_RIGHT(elm, field);                             \
                while ((left = RB_LEFT(elm, field)))                    \
                        elm = left;                                     \
@@ -562,6 +569,7 @@ name##_RB_REMOVE(struct name *head, struct type *elm)                       \
 color:                                                                 \
        if (color == RB_BLACK)                                          \
                name##_RB_REMOVE_COLOR(head, parent, child);            \
+       return (old);                                                   \
 }                                                                      \
                                                                        \
 /* Inserts a node into the RB tree */                                  \