Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/trunk]: src/bin/systrace A local copy of <sys/tree.h> is unnecessary.



details:   https://anonhg.NetBSD.org/src/rev/d598c14a44f0
branches:  trunk
changeset: 534591:d598c14a44f0
user:      soren <soren%NetBSD.org@localhost>
date:      Tue Jul 30 06:09:56 2002 +0000

description:
A local copy of <sys/tree.h> is unnecessary.

diffstat:

 bin/systrace/tree.h |  669 ----------------------------------------------------
 1 files changed, 0 insertions(+), 669 deletions(-)

diffs (truncated from 673 to 300 lines):

diff -r 9a8ca22c5ccd -r d598c14a44f0 bin/systrace/tree.h
--- a/bin/systrace/tree.h       Tue Jul 30 06:09:10 2002 +0000
+++ /dev/null   Thu Jan 01 00:00:00 1970 +0000
@@ -1,669 +0,0 @@
-/*     $NetBSD: tree.h,v 1.1 2002/06/17 16:29:11 christos Exp $        */
-/*     $OpenBSD: tree.h,v 1.4 2002/03/26 02:47:28 hugh Exp $   */
-/*
- * Copyright 2002 Niels Provos <provos%citi.umich.edu@localhost>
- * 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.
- */
-
-#ifndef        _SYS_TREE_H_
-#define        _SYS_TREE_H_
-
-/*
- * 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);
- *
- * A red-black tree is a binary search tree with the node color as an
- * extra attribute.  It fulfills a set of conditions:
- *     - every search path from the root to a leaf consists of the
- *       same number of black nodes,
- *     - each red node (except for the root) has a black parent,
- *     - each leaf node is black.
- *
- * Every operation on a red-black tree is bounded as O(lg n).
- * 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 (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 (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 (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 (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 (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 (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);                          \
-                                                                       \
-static __inline void                                                   \
-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 = (elm);                                          \
-}                                                                      \
-                                                                       \
-static __inline void                                                   \
-name##_SPLAY_REMOVE(struct name *head, struct type *elm)               \
-{                                                                      \
-       struct type *__tmp;                                             \
-       if (SPLAY_EMPTY(head))                                          \
-               return;                                                 \
-       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;   \
-               }                                                       \
-       }                                                               \
-}                                                                      \
-                                                                       \
-/* 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)                 \
-{                                                                      \
-       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))) {               \
-               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-back tree */
-#define RB_HEAD(name, type)                                            \
-struct name {                                                          \
-       struct type *rbh_root; /* root of the tree */                   \
-}
-
-#define RB_INITIALIZER(root)                                           \
-       { NULL }
-
-#define RB_INIT(root) do {                                             \
-       (root)->rbh_root = NULL;                                        \
-} while (0)



Home | Main Index | Thread Index | Old Index