1 files changed, 2 insertions, 249 deletions

diff --git a/src/common/tree.h b/src/common/tree.h
index a6b636646..4a295f894 100644
--- a/src/common/tree.h
+++ b/src/common/tree.h
@@ -27,33 +27,10 @@
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-#ifndef _SYS_TREE_H_
-#define _SYS_TREE_H_
-
-/* FreeBSD <sys/cdefs.h> has a lot of defines we don't really want. */
-/* tree.h only actually uses __inline and __unused, so we'll just define those. */
-
-/* #include <sys/cdefs.h> */
-
-#ifndef __inline
-#define __inline inline
-#endif
+#pragma once
 
 /*
- * This file defines data structures for different types of trees:
- * splay trees and red-black trees.
- *
- * A splay tree is a self-organizing data structure.  Every operation
- * on the tree causes a splay to happen.  The splay moves the requested
- * node to the root of the tree and partly rebalances it.
- *
- * This has the benefit that request locality causes faster lookups as
- * the requested nodes move to the top of the tree.  On the other hand,
- * every lookup causes memory writes.
- *
- * The Balance Theorem bounds the total access time for m operations
- * and n inserts on an initially empty tree as O((m + n)lg n).  The
- * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ * This file defines data structures for red-black trees.
  *
  * A red-black tree is a binary search tree with the node color as an
  * extra attribute.  It fulfills a set of conditions:
@@ -66,228 +43,6 @@
  * The maximum height of a red-black tree is 2lg (n+1).
  */
 
-#define SPLAY_HEAD(name, type)                                                                     \
-    struct name {                                                                                  \
-        struct type* sph_root; /* root of the tree */                                              \
-    }
-
-#define SPLAY_INITIALIZER(root)                                                                    \
-    { NULL }
-
-#define SPLAY_INIT(root)                                                                           \
-    do {                                                                                           \
-        (root)->sph_root = NULL;                                                                   \
-    } while (/*CONSTCOND*/ 0)
-
-#define SPLAY_ENTRY(type)                                                                          \
-    struct {                                                                                       \
-        struct type* spe_left;  /* left element */                                                 \
-        struct type* spe_right; /* right element */                                                \
-    }
-
-#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
-#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
-#define SPLAY_ROOT(head) (head)->sph_root
-#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
-
-/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
-#define SPLAY_ROTATE_RIGHT(head, tmp, field)                                                       \
-    do {                                                                                           \
-        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);                             \
-        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                                                \
-        (head)->sph_root = tmp;                                                                    \
-    } while (/*CONSTCOND*/ 0)
-
-#define SPLAY_ROTATE_LEFT(head, tmp, field)                                                        \
-    do {                                                                                           \
-        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);                             \
-        SPLAY_LEFT(tmp, field) = (head)->sph_root;                                                 \
-        (head)->sph_root = tmp;                                                                    \
-    } while (/*CONSTCOND*/ 0)
-
-#define SPLAY_LINKLEFT(head, tmp, field)                                                           \
-    do {                                                                                           \
-        SPLAY_LEFT(tmp, field) = (head)->sph_root;                                                 \
-        tmp = (head)->sph_root;                                                                    \
-        (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);                                    \
-    } while (/*CONSTCOND*/ 0)
-
-#define SPLAY_LINKRIGHT(head, tmp, field)                                                          \
-    do {                                                                                           \
-        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                                                \
-        tmp = (head)->sph_root;                                                                    \
-        (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);                                   \
-    } while (/*CONSTCOND*/ 0)
-
-#define SPLAY_ASSEMBLE(head, node, left, right, field)                                             \
-    do {                                                                                           \
-        SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);                            \
-        SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);                           \
-        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);                            \
-        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);                            \
-    } while (/*CONSTCOND*/ 0)
-
-/* Generates prototypes and inline functions */
-
-#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*);                                  \
-                                                                                                   \
-    /* 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)) {                                                                   \
-            SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;                               \
-        } else {                                                                                   \
-            int __comp;                                                                            \
-            name##_SPLAY(head, elm);                                                               \
-            __comp = (cmp)(elm, (head)->sph_root);                                                 \
-            if (__comp < 0) {                                                                      \
-                SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);                      \
-                SPLAY_RIGHT(elm, field) = (head)->sph_root;                                        \
-                SPLAY_LEFT((head)->sph_root, field) = NULL;                                        \
-            } else if (__comp > 0) {                                                               \
-                SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);                    \
-                SPLAY_LEFT(elm, field) = (head)->sph_root;                                         \
-                SPLAY_RIGHT((head)->sph_root, field) = NULL;                                       \
-            } else                                                                                 \
-                return ((head)->sph_root);                                                         \
-        }                                                                                          \
-        (head)->sph_root = (elm);                                                                  \
-        return (NULL);                                                                             \
-    }                                                                                              \
-                                                                                                   \
-    struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) {                        \
-        struct type* __tmp;                                                                        \
-        if (SPLAY_EMPTY(head))                                                                     \
-            return (NULL);                                                                         \
-        name##_SPLAY(head, elm);                                                                   \
-        if ((cmp)(elm, (head)->sph_root) == 0) {                                                   \
-            if (SPLAY_LEFT((head)->sph_root, field) == NULL) {                                     \
-                (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);                           \
-            } else {                                                                               \
-                __tmp = SPLAY_RIGHT((head)->sph_root, field);                                      \
-                (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);                            \
-                name##_SPLAY(head, elm);                                                           \
-                SPLAY_RIGHT((head)->sph_root, field) = __tmp;                                      \
-            }                                                                                      \
-            return (elm);                                                                          \
-        }                                                                                          \
-        return (NULL);                                                                             \
-    }                                                                                              \
-                                                                                                   \
-    void name##_SPLAY(struct name* head, struct type* elm) {                                       \
-        struct type __node, *__left, *__right, *__tmp;                                             \
-        int __comp;                                                                                \
-                                                                                                   \
-        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;                           \
-        __left = __right = &__node;                                                                \
-                                                                                                   \
-        while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {                                     \
-            if (__comp < 0) {                                                                      \
-                __tmp = SPLAY_LEFT((head)->sph_root, field);                                       \
-                if (__tmp == NULL)                                                                 \
-                    break;                                                                         \
-                if ((cmp)(elm, __tmp) < 0) {                                                       \
-                    SPLAY_ROTATE_RIGHT(head, __tmp, field);                                        \
-                    if (SPLAY_LEFT((head)->sph_root, field) == NULL)                               \
-                        break;                                                                     \
-                }                                                                                  \
-                SPLAY_LINKLEFT(head, __right, field);                                              \
-            } else if (__comp > 0) {                                                               \
-                __tmp = SPLAY_RIGHT((head)->sph_root, field);                                      \
-                if (__tmp == NULL)                                                                 \
-                    break;                                                                         \
-                if ((cmp)(elm, __tmp) > 0) {                                                       \
-                    SPLAY_ROTATE_LEFT(head, __tmp, field);                                         \
-                    if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                              \
-                        break;                                                                     \
-                }                                                                                  \
-                SPLAY_LINKRIGHT(head, __left, field);                                              \
-            }                                                                                      \
-        }                                                                                          \
-        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                                     \
-    }                                                                                              \
-                                                                                                   \
-    /* Splay with either the minimum or the maximum element                                        \
-     * Used to find minimum or maximum element in tree.                                            \
-     */                                                                                            \
-    void name##_SPLAY_MINMAX(struct name* head, int __comp) {                                      \
-        struct type __node, *__left, *__right, *__tmp;                                             \
-                                                                                                   \
-        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;                           \
-        __left = __right = &__node;                                                                \
-                                                                                                   \
-        while (1) {                                                                                \
-            if (__comp < 0) {                                                                      \
-                __tmp = SPLAY_LEFT((head)->sph_root, field);                                       \
-                if (__tmp == NULL)                                                                 \
-                    break;                                                                         \
-                if (__comp < 0) {                                                                  \
-                    SPLAY_ROTATE_RIGHT(head, __tmp, field);                                        \
-                    if (SPLAY_LEFT((head)->sph_root, field) == NULL)                               \
-                        break;                                                                     \
-                }                                                                                  \
-                SPLAY_LINKLEFT(head, __right, field);                                              \
-            } else if (__comp > 0) {                                                               \
-                __tmp = SPLAY_RIGHT((head)->sph_root, field);                                      \
-                if (__tmp == NULL)                                                                 \
-                    break;                                                                         \
-                if (__comp > 0) {                                                                  \
-                    SPLAY_ROTATE_LEFT(head, __tmp, field);                                         \
-                    if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                              \
-                        break;                                                                     \
-                }                                                                                  \
-                SPLAY_LINKRIGHT(head, __left, field);                                              \
-            }                                                                                      \
-        }                                                                                          \
-        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                                     \
-    }
-
-#define SPLAY_NEGINF -1
-#define SPLAY_INF 1
-
-#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
-#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
-#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
-#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
-#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
-#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
-
-#define SPLAY_FOREACH(x, name, head)                                                               \
-    for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x))
-
 /* Macros that define a red-black tree */
 #define RB_HEAD(name, type)                                                                        \
     struct name {                                                                                  \
@@ -818,5 +573,3 @@
 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                                                  \
     for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);        \
          (x) = (y))
-
-#endif /* _SYS_TREE_H_ */