sys-tree.h revision 7c478bd95313f5f23a4c958a745db2134aa03244
/* $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.
*
* 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
*
* 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
#pragma ident "%Z%%M% %I% %E% SMI"
#ifdef __cplusplus
extern "C" {
#endif
/*
* 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).
*/
struct name { \
}
#define SPLAY_INITIALIZER(root) \
{ NULL }
#define SPLAY_INIT(root) do { \
} while (0)
#define SPLAY_ENTRY(type) \
struct { \
}
/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
} while (0)
} while (0)
} while (0)
} while (0)
} while (0)
/* Generates prototypes and inline functions */
\
/* Finds the node with the same key as elm */ \
{ \
if (SPLAY_EMPTY(head)) \
return(NULL); \
return (NULL); \
} \
\
{ \
} \
} else \
return (elm); \
} \
\
{ \
return (SPLAY_ROOT(head)); \
}
/* Main splay operation.
* Moves node close to the key of elm to top
*/
struct type * \
{ \
if (SPLAY_EMPTY(head)) { \
} else { \
int __comp; \
if(__comp < 0) { \
} else if (__comp > 0) { \
} else \
} \
return (NULL); \
} \
\
struct type * \
{ \
if (SPLAY_EMPTY(head)) \
return (NULL); \
} else { \
} \
return (elm); \
} \
return (NULL); \
} \
\
void \
{ \
int __comp; \
\
\
if (__comp < 0) { \
break; \
break; \
} \
} else if (__comp > 0) { \
break; \
break; \
} \
} \
} \
} \
\
/* Splay with either the minimum or the maximum element \
* Used to find minimum or maximum element in tree. \
*/ \
{ \
\
\
while (1) { \
if (__comp < 0) { \
break; \
if (__comp < 0){ \
break; \
} \
} else if (__comp > 0) { \
break; \
if (__comp > 0) { \
break; \
} \
} \
} \
}
#define SPLAY_NEGINF -1
#define SPLAY_INF 1
(x) != NULL; \
/* Macros that define a red-back tree */
struct name { \
}
#define RB_INITIALIZER(root) \
{ NULL }
} while (0)
#define RB_BLACK 0
#define RB_RED 1
struct { \
int rbe_color; /* node color */ \
}
} while (0)
} while (0)
#ifndef RB_AUGMENT
#define RB_AUGMENT(x)
#endif
} \
RB_AUGMENT(elm); \
else \
} else \
RB_AUGMENT(tmp); \
} while (0)
} \
RB_AUGMENT(elm); \
else \
} else \
RB_AUGMENT(tmp); \
} while (0)
/* Generates prototypes and inline functions */
\
/* Main rb operation.
* Moves node close to the key of elm to top
*/
void \
{ \
continue; \
} \
} \
} else { \
continue; \
} \
} \
} \
} \
} \
\
void \
{ \
} \
} else { \
} \
break; \
} \
} else { \
} \
} else { \
} \
break; \
} \
} \
} \
if (elm) \
} \
\
struct type * \
{ \
int color; \
else { \
if (child) \
if (parent) { \
else \
RB_AUGMENT(parent); \
} else \
else \
} else \
if (parent) { \
do { \
RB_AUGMENT(left); \
} \
goto color; \
} \
if (child) \
if (parent) { \
else \
RB_AUGMENT(parent); \
} else \
color: \
return (old); \
} \
\
/* Inserts a node into the RB tree */ \
struct type * \
{ \
int comp = 0; \
while (tmp) { \
if (comp < 0) \
else if (comp > 0) \
else \
return (tmp); \
} \
if (comp < 0) \
else \
RB_AUGMENT(parent); \
} else \
return (NULL); \
} \
\
/* Finds the node with the same key as elm */ \
struct type * \
{ \
int comp; \
while (tmp) { \
if (comp < 0) \
else if (comp > 0) \
else \
return (tmp); \
} \
return (NULL); \
} \
\
struct type * \
{ \
} else { \
else { \
} \
} \
return (elm); \
} \
\
struct type * \
{ \
while (tmp) { \
if (val < 0) \
else \
} \
return (parent); \
}
#define RB_NEGINF -1
#define RB_INF 1
(x) != NULL; \
#ifdef __cplusplus
}
#endif
#endif /* _SYS_TREE_H */