libressl_d.compat.sys.tree source code

1 /*	$OpenBSD: tree.h,v 1.29 2017/07/30 19:27:20 deraadt Exp $	*/
2 /*
3  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26 module libressl_d.compat.sys.tree;
27 
28 
29 private static import core.stdc.config;
30 //#include <sys/_null.h>
31 
32 extern (C):
33 nothrow @nogc:
34 
35 /*
36  * This file defines data structures for different types of trees:
37  * splay trees and red-black trees.
38  *
39  * A splay tree is a self-organizing data structure.  Every operation
40  * on the tree causes a splay to happen.  The splay moves the requested
41  * node to the root of the tree and partly rebalances it.
42  *
43  * This has the benefit that request locality causes faster lookups as
44  * the requested nodes move to the top of the tree.  On the other hand,
45  * every lookup causes memory writes.
46  *
47  * The Balance Theorem bounds the total access time for m operations
48  * and n inserts on an initially empty tree as O((m + n)lg n).  The
49  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
50  *
51  * A red-black tree is a binary search tree with the node color as an
52  * extra attribute.  It fulfills a set of conditions:
53  *	- every search path from the root to a leaf consists of the
54  *	  same number of black nodes,
55  *	- each red node (except for the root) has a black parent,
56  *	- each leaf node is black.
57  *
58  * Every operation on a red-black tree is bounded as O(lg n).
59  * The maximum height of a red-black tree is 2lg (n+1).
60  */
61 
62 template SPLAY_HEAD(string name, string type)
63 {
64 	enum SPLAY_HEAD = "struct " ~ name ~ " { " ~ type ~ "* sph_root; /* root of the tree */ }";
65 }
66 
67 pragma(inline, true)
68 pure nothrow @safe @nogc @live
69 ROOT SPLAY_INITIALIZER(ROOT)(scope const ROOT* root)
70 	if (is(ROOT == struct))
71 
72 	do
73 	{
74 		return ROOT.init;
75 	}
76 
77 pragma(inline, true)
78 pure nothrow @trusted @nogc @live
79 void SPLAY_INIT(ROOT)(scope ROOT* root)
80 
81 	in
82 	{
83 		assert(root != null);
84 	}
85 
86 	do
87 	{
88 		root.sph_root = null;
89 	}
90 
91 template SPLAY_ENTRY(string type)
92 {
93 	enum SPLAY_ENTRY = "struct { " ~ type ~ "* spe_left; /* left element */ " ~ type ~ "* spe_right; /* right element */ }";
94 }
95 
96 //#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
97 //#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
98 //#define SPLAY_ROOT(head) (head)->sph_root
99 //#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
100 
101 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
102 //#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)
103 
104 //#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)
105 
106 //#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)
107 
108 //#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)
109 
110 //#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)
111 
112 /* Generates prototypes and inline functions */
113 
114 //#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 __unused __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 __unused __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 __unused __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { name##_SPLAY_MINMAX(head, val); return (SPLAY_ROOT(head)); }
115 
116 /* Main splay operation.
117  * Moves node close to the key of elm to top
118  */
119 //#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))) { 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); }
120 
121 enum SPLAY_NEGINF = -1;
122 enum SPLAY_INF = 1;
123 
124 //#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
125 //#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
126 //#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
127 //#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
128 //#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
129 //#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
130 
131 //#define SPLAY_FOREACH(x, name, head) for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x))
132 
133 /* Macros that define a red-black tree */
134 template RB_HEAD(string name, string type)
135 {
136 	enum RB_HEAD = "struct " ~ name ~ " { " ~ type ~ "* rbh_root; /* root of the tree */ }";
137 }
138 
139 pragma(inline, true)
140 pure nothrow @safe @nogc @live
141 ROOT RB_INITIALIZER(ROOT)(scope const ROOT* root)
142 	if (is(ROOT == struct))
143 
144 	do
145 	{
146 		return ROOT.init;
147 	}
148 
149 pragma(inline, true)
150 pure nothrow @trusted @nogc @live
151 void RB_INIT(ROOT)(scope ROOT* root)
152 
153 	in
154 	{
155 		assert(root != null);
156 	}
157 
158 	do
159 	{
160 		root.rbh_root = null;
161 	}
162 
163 enum RB_BLACK = 0;
164 enum RB_RED = 1;
165 
166 template RB_ENTRY(string type)
167 {
168 	enum RB_ENTRY = "struct { " ~ type ~ "* rbe_left; /* left element */ " ~ type ~ "* rbe_right; /* right element */ " ~ type ~ "* rbe_parent; /* parent element */ int rbe_color; /* node color */ }";
169 }
170 
171 //#define RB_LEFT(elm, field) (elm)->field.rbe_left
172 //#define RB_RIGHT(elm, field) (elm)->field.rbe_right
173 //#define RB_PARENT(elm, field) (elm)->field.rbe_parent
174 //#define RB_COLOR(elm, field) (elm)->field.rbe_color
175 //#define RB_ROOT(head) (head)->rbh_root
176 //#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
177 
178 //#define RB_SET(elm, parent, field) do { RB_PARENT(elm, field) = parent; RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; RB_COLOR(elm, field) = RB_RED; } while (0)
179 
180 //#define RB_SET_BLACKRED(black, red, field) do { RB_COLOR(black, field) = RB_BLACK; RB_COLOR(red, field) = RB_RED; } while (0)
181 
182 //#ifndef RB_AUGMENT
183 	//#define RB_AUGMENT(x) do { } while (0)
184 //#endif
185 
186 //#define RB_ROTATE_LEFT(head, elm, tmp, field) do { (tmp) = RB_RIGHT(elm, field); if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { RB_PARENT(RB_LEFT(tmp, field), field) = (elm); } RB_AUGMENT(elm); if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) RB_LEFT(RB_PARENT(elm, field), field) = (tmp); else RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); } else (head)->rbh_root = (tmp); RB_LEFT(tmp, field) = (elm); RB_PARENT(elm, field) = (tmp); RB_AUGMENT(tmp); if ((RB_PARENT(tmp, field))) RB_AUGMENT(RB_PARENT(tmp, field)); } while (0)
187 
188 //#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { (tmp) = RB_LEFT(elm, field); if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); } RB_AUGMENT(elm); if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) RB_LEFT(RB_PARENT(elm, field), field) = (tmp); else RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); } else (head)->rbh_root = (tmp); RB_RIGHT(tmp, field) = (elm); RB_PARENT(elm, field) = (tmp); RB_AUGMENT(tmp); if ((RB_PARENT(tmp, field))) RB_AUGMENT(RB_PARENT(tmp, field)); } while (0)
189 
190 /* Generates prototypes and inline functions */
191 //#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, )
192 //#define RB_PROTOTYPE_STATIC(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
193 //#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) attr void name##_RB_INSERT_COLOR(struct name*, struct type*); attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*); attr struct type* name##_RB_REMOVE(struct name*, struct type*); attr struct type* name##_RB_INSERT(struct name*, struct type*); attr struct type* name##_RB_FIND(struct name*, struct type*); attr struct type* name##_RB_NFIND(struct name*, struct type*); attr struct type* name##_RB_NEXT(struct type*); attr struct type* name##_RB_PREV(struct type*); attr struct type* name##_RB_MINMAX(struct name*, int);
194 
195 /* Main rb operation.
196  * Moves node close to the key of elm to top
197  */
198 //#define RB_GENERATE(name, type, field, cmp) RB_GENERATE_INTERNAL(name, type, field, cmp, )
199 //#define RB_GENERATE_STATIC(name, type, field, cmp) RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
200 //#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { struct type *parent, *gparent, *tmp; while ((parent = RB_PARENT(elm, field)) && RB_COLOR(parent, field) == RB_RED) { gparent = RB_PARENT(parent, field); if (parent == RB_LEFT(gparent, field)) { tmp = RB_RIGHT(gparent, field); if (tmp && RB_COLOR(tmp, field) == RB_RED) { RB_COLOR(tmp, field) = RB_BLACK; RB_SET_BLACKRED(parent, gparent, field); elm = gparent; continue; } if (RB_RIGHT(parent, field) == elm) { RB_ROTATE_LEFT(head, parent, tmp, field); tmp = parent; parent = elm; elm = tmp; } RB_SET_BLACKRED(parent, gparent, field); RB_ROTATE_RIGHT(head, gparent, tmp, field); } else { tmp = RB_LEFT(gparent, field); if (tmp && RB_COLOR(tmp, field) == RB_RED) { RB_COLOR(tmp, field) = RB_BLACK; RB_SET_BLACKRED(parent, gparent, field); elm = gparent; continue; } if (RB_LEFT(parent, field) == elm) { RB_ROTATE_RIGHT(head, parent, tmp, field); tmp = parent; parent = elm; elm = tmp; } RB_SET_BLACKRED(parent, gparent, field); RB_ROTATE_LEFT(head, gparent, tmp, field); } } RB_COLOR(head->rbh_root, field) = RB_BLACK; } attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { struct type* tmp; while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { if (RB_LEFT(parent, field) == elm) { tmp = RB_RIGHT(parent, field); if (RB_COLOR(tmp, field) == RB_RED) { RB_SET_BLACKRED(tmp, parent, field); RB_ROTATE_LEFT(head, parent, tmp, field); tmp = RB_RIGHT(parent, field); } if ((RB_LEFT(tmp, field) == NULL || RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && (RB_RIGHT(tmp, field) == NULL || RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { RB_COLOR(tmp, field) = RB_RED; elm = parent; parent = RB_PARENT(elm, field); } else { if (RB_RIGHT(tmp, field) == NULL || RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { struct type* oleft; if ((oleft = RB_LEFT(tmp, field))) RB_COLOR(oleft, field) = RB_BLACK; RB_COLOR(tmp, field) = RB_RED; RB_ROTATE_RIGHT(head, tmp, oleft, field); tmp = RB_RIGHT(parent, field); } RB_COLOR(tmp, field) = RB_COLOR(parent, field); RB_COLOR(parent, field) = RB_BLACK; if (RB_RIGHT(tmp, field)) RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; RB_ROTATE_LEFT(head, parent, tmp, field); elm = RB_ROOT(head); break; } } else { tmp = RB_LEFT(parent, field); if (RB_COLOR(tmp, field) == RB_RED) { RB_SET_BLACKRED(tmp, parent, field); RB_ROTATE_RIGHT(head, parent, tmp, field); tmp = RB_LEFT(parent, field); } if ((RB_LEFT(tmp, field) == NULL || RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && (RB_RIGHT(tmp, field) == NULL || RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { RB_COLOR(tmp, field) = RB_RED; elm = parent; parent = RB_PARENT(elm, field); } else { if (RB_LEFT(tmp, field) == NULL || RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { struct type* oright; if ((oright = RB_RIGHT(tmp, field))) RB_COLOR(oright, field) = RB_BLACK; RB_COLOR(tmp, field) = RB_RED; RB_ROTATE_LEFT(head, tmp, oright, field); tmp = RB_LEFT(parent, field); } RB_COLOR(tmp, field) = RB_COLOR(parent, field); RB_COLOR(parent, field) = RB_BLACK; if (RB_LEFT(tmp, field)) RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; RB_ROTATE_RIGHT(head, parent, tmp, field); elm = RB_ROOT(head); break; } } } if (elm) RB_COLOR(elm, field) = RB_BLACK; } attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { 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* left; elm = RB_RIGHT(elm, field); while ((left = RB_LEFT(elm, field))) elm = left; child = RB_RIGHT(elm, field); parent = RB_PARENT(elm, field); color = RB_COLOR(elm, field); if (child) RB_PARENT(child, field) = parent; if (parent) { if (RB_LEFT(parent, field) == elm) RB_LEFT(parent, field) = child; else RB_RIGHT(parent, field) = child; RB_AUGMENT(parent); } else RB_ROOT(head) = child; if (RB_PARENT(elm, field) == old) parent = elm; (elm)->field = (old)->field; if (RB_PARENT(old, field)) { if (RB_LEFT(RB_PARENT(old, field), field) == old) RB_LEFT(RB_PARENT(old, field), field) = elm; else RB_RIGHT(RB_PARENT(old, field), field) = elm; RB_AUGMENT(RB_PARENT(old, field)); } else RB_ROOT(head) = elm; RB_PARENT(RB_LEFT(old, field), field) = elm; if (RB_RIGHT(old, field)) RB_PARENT(RB_RIGHT(old, field), field) = elm; if (parent) { left = parent; do { RB_AUGMENT(left); } while ((left = RB_PARENT(left, field))); } goto color; } parent = RB_PARENT(elm, field); color = RB_COLOR(elm, field); if (child) RB_PARENT(child, field) = parent; if (parent) { if (RB_LEFT(parent, field) == elm) RB_LEFT(parent, field) = child; else RB_RIGHT(parent, field) = child; RB_AUGMENT(parent); } else RB_ROOT(head) = child; color: if (color == RB_BLACK) name##_RB_REMOVE_COLOR(head, parent, child); return (old); } /* Inserts a node into the RB tree */ attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { struct type* tmp; struct type* parent = NULL; int comp = 0; tmp = RB_ROOT(head); while (tmp) { parent = tmp; comp = (cmp)(elm, parent); if (comp < 0) tmp = RB_LEFT(tmp, field); else if (comp > 0) tmp = RB_RIGHT(tmp, field); else return (tmp); } RB_SET(elm, parent, field); if (parent != NULL) { if (comp < 0) RB_LEFT(parent, field) = elm; else RB_RIGHT(parent, field) = elm; RB_AUGMENT(parent); } else RB_ROOT(head) = elm; name##_RB_INSERT_COLOR(head, elm); return (NULL); } /* Finds the node with the same key as elm */ attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { struct type* tmp = RB_ROOT(head); int comp; while (tmp) { comp = cmp(elm, tmp); if (comp < 0) tmp = RB_LEFT(tmp, field); else if (comp > 0) tmp = RB_RIGHT(tmp, field); else return (tmp); } return (NULL); } /* Finds the first node greater than or equal to the search key */ attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { struct type* tmp = RB_ROOT(head); struct type* res = NULL; int comp; while (tmp) { comp = cmp(elm, tmp); if (comp < 0) { res = tmp; tmp = RB_LEFT(tmp, field); } else if (comp > 0) tmp = RB_RIGHT(tmp, field); else return (tmp); } return (res); } /* ARGSUSED */ attr struct type* name##_RB_NEXT(struct type* elm) { if (RB_RIGHT(elm, field)) { elm = RB_RIGHT(elm, field); while (RB_LEFT(elm, field)) elm = RB_LEFT(elm, field); } else { if (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) elm = RB_PARENT(elm, field); else { while (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) elm = RB_PARENT(elm, field); elm = RB_PARENT(elm, field); } } return (elm); } /* ARGSUSED */ attr struct type* name##_RB_PREV(struct type* elm) { if (RB_LEFT(elm, field)) { elm = RB_LEFT(elm, field); while (RB_RIGHT(elm, field)) elm = RB_RIGHT(elm, field); } else { if (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) elm = RB_PARENT(elm, field); else { while (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) elm = RB_PARENT(elm, field); elm = RB_PARENT(elm, field); } } return (elm); } attr struct type* name##_RB_MINMAX(struct name* head, int val) { struct type* tmp = RB_ROOT(head); struct type* parent = NULL; while (tmp) { parent = tmp; if (val < 0) tmp = RB_LEFT(tmp, field); else tmp = RB_RIGHT(tmp, field); } return (parent); }
201 
202 enum RB_NEGINF = -1;
203 enum RB_INF = 1;
204 
205 //#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
206 //#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
207 //#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
208 //#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
209 //#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
210 //#define RB_PREV(name, x, y) name##_RB_PREV(y)
211 //#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
212 //#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
213 
214 //#define RB_FOREACH(x, name, head) for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x))
215 
216 //#define RB_FOREACH_SAFE(x, name, head, y) for ((x) = RB_MIN(name, head); ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); (x) = (y))
217 
218 //#define RB_FOREACH_REVERSE(x, name, head) for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x))
219 
220 //#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); (x) = (y))
221 
222 /*
223  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
224  *
225  * Permission to use, copy, modify, and distribute this software for any
226  * purpose with or without fee is hereby granted, provided that the above
227  * copyright notice and this permission notice appear in all copies.
228  *
229  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
230  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
231  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
232  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
233  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
234  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
235  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
236  */
237 
238 struct rb_type
239 {
240 	int function(const (void)*, const (void)*) t_compare;
241 	void function(void*) t_augment;
242 
243 	/**
244 	 * offset of rb_entry in type
245 	 */
246 	uint t_offset;
247 }
248 
249 struct rb_tree
250 {
251 	.rb_entry* rbt_root;
252 }
253 
254 struct rb_entry
255 {
256 	.rb_entry* rbt_parent;
257 	.rb_entry* rbt_left;
258 	.rb_entry* rbt_right;
259 	uint rbt_color;
260 }
261 
262 template RBT_HEAD(string _name, string _type)
263 {
264 	enum RBT_HEAD = "struct " ~ _name ~ " { libressl_d.compat.sys.tree.rb_tree rbh_root; }";
265 }
266 
267 //#define RBT_ENTRY(_type) struct rb_entry
268 
269 pragma(inline, true)
270 pure nothrow @trusted @nogc @live
271 static void _rb_init(scope .rb_tree* rbt)
272 
273 	in
274 	{
275 		assert(rbt != null);
276 	}
277 
278 	do
279 	{
280 		rbt.rbt_root = null;
281 	}
282 
283 pragma(inline, true)
284 pure nothrow @trusted @nogc @live
285 static int _rb_empty(scope const .rb_tree* rbt)
286 
287 	in
288 	{
289 		assert(rbt != null);
290 	}
291 
292 	do
293 	{
294 		return rbt.rbt_root == null;
295 	}
296 
297 void* _rb_insert(const (.rb_type)*, .rb_tree*, void*);
298 void* _rb_remove(const (.rb_type)*, .rb_tree*, void*);
299 void* _rb_find(const (.rb_type)*, .rb_tree*, const (void)*);
300 void* _rb_nfind(const (.rb_type)*, .rb_tree*, const (void)*);
301 void* _rb_root(const (.rb_type)*, .rb_tree*);
302 void* _rb_min(const (.rb_type)*, .rb_tree*);
303 void* _rb_max(const (.rb_type)*, .rb_tree*);
304 void* _rb_next(const (.rb_type)*, void*);
305 void* _rb_prev(const (.rb_type)*, void*);
306 void* _rb_left(const (.rb_type)*, void*);
307 void* _rb_right(const (.rb_type)*, void*);
308 void* _rb_parent(const (.rb_type)*, void*);
309 void _rb_set_left(const (.rb_type)*, void*, void*);
310 void _rb_set_right(const (.rb_type)*, void*, void*);
311 void _rb_set_parent(const (.rb_type)*, void*, void*);
312 void _rb_poison(const (.rb_type)*, void*, core.stdc.config.c_ulong);
313 int _rb_check(const (.rb_type)*, void*, core.stdc.config.c_ulong);
314 
315 pragma(inline, true)
316 pure nothrow @safe @nogc @live
317 _HEAD RBT_INITIALIZER(_HEAD)(scope const _HAED* _head)
318 	if (is(_HAED == struct))
319 
320 	do
321 	{
322 		return _HAED.init;
323 	}
324 
325 //#define RBT_PROTOTYPE(_name, _type, _field, _cmp) extern __gshared const struct rb_type* const _name##_RBT_TYPE; __unused static inline void _name##_RBT_INIT(struct _name* head) { _rb_init(&head->rbh_root); } __unused static inline struct _type* _name##_RBT_INSERT(struct _name* head, struct _type* elm) { return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); } __unused static inline struct _type* _name##_RBT_REMOVE(struct _name* head, struct _type* elm) { return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); } __unused static inline struct _type* _name##_RBT_FIND(struct _name* head, const struct _type* key) { return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); } __unused static inline struct _type* _name##_RBT_NFIND(struct _name* head, const struct _type* key) { return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); } __unused static inline struct _type* _name##_RBT_ROOT(struct _name* head) { return _rb_root(_name##_RBT_TYPE, &head->rbh_root); } __unused static inline int _name##_RBT_EMPTY(struct _name* head) { return _rb_empty(&head->rbh_root); } __unused static inline struct _type* _name##_RBT_MIN(struct _name* head) { return _rb_min(_name##_RBT_TYPE, &head->rbh_root); } __unused static inline struct _type* _name##_RBT_MAX(struct _name* head) { return _rb_max(_name##_RBT_TYPE, &head->rbh_root); } __unused static inline struct _type* _name##_RBT_NEXT(struct _type* elm) { return _rb_next(_name##_RBT_TYPE, elm); } __unused static inline struct _type* _name##_RBT_PREV(struct _type* elm) { return _rb_prev(_name##_RBT_TYPE, elm); } __unused static inline struct _type* _name##_RBT_LEFT(struct _type* elm) { return _rb_left(_name##_RBT_TYPE, elm); } __unused static inline struct _type* _name##_RBT_RIGHT(struct _type* elm) { return _rb_right(_name##_RBT_TYPE, elm); } __unused static inline struct _type* _name##_RBT_PARENT(struct _type* elm) { return _rb_parent(_name##_RBT_TYPE, elm); } __unused static inline void _name##_RBT_SET_LEFT(struct _type* elm, struct _type* left) { return _rb_set_left(_name##_RBT_TYPE, elm, left); } __unused static inline void _name##_RBT_SET_RIGHT(struct _type* elm, struct _type* right) { return _rb_set_right(_name##_RBT_TYPE, elm, right); } __unused static inline void _name##_RBT_SET_PARENT(struct _type* elm, struct _type* parent) { return _rb_set_parent(_name##_RBT_TYPE, elm, parent); } __unused static inline void _name##_RBT_POISON(struct _type* elm, unsigned long poison) { return _rb_poison(_name##_RBT_TYPE, elm, poison); } __unused static inline int _name##_RBT_CHECK(struct _type* elm, unsigned long poison) { return _rb_check(_name##_RBT_TYPE, elm, poison); }
326 
327 //#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) static int _name##_RBT_COMPARE(const void* lptr, const void* rptr) { const struct _type *l = lptr, *r = rptr; return _cmp(l, r); } static const struct rb_type _name##_RBT_INFO = { _name##_RBT_COMPARE, _aug, offsetof(struct _type, _field), }; const struct rb_type* const _name##_RBT_TYPE = &_name##_RBT_INFO
328 
329 //#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) static void _name##_RBT_AUGMENT(void* ptr) { struct _type* p = ptr; return _aug(p); } RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT)
330 
331 //#define RBT_GENERATE(_name, _type, _field, _cmp) RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
332 
333 //#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head)
334 //#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm)
335 //#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm)
336 //#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key)
337 //#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key)
338 //#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head)
339 //#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head)
340 //#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head)
341 //#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head)
342 //#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm)
343 //#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm)
344 //#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm)
345 //#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm)
346 //#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm)
347 //#define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l)
348 //#define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r)
349 //#define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p)
350 //#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p)
351 //#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p)
352 
353 //#define RBT_FOREACH(_e, _name, _head) for ((_e) = RBT_MIN(_name, (_head)); (_e) != NULL; (_e) = RBT_NEXT(_name, (_e)))
354 
355 //#define RBT_FOREACH_SAFE(_e, _name, _head, _n) for ((_e) = RBT_MIN(_name, (_head)); (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); (_e) = (_n))
356 
357 //#define RBT_FOREACH_REVERSE(_e, _name, _head) for ((_e) = RBT_MAX(_name, (_head)); (_e) != NULL; (_e) = RBT_PREV(_name, (_e)))
358 
359 //#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) for ((_e) = RBT_MAX(_name, (_head)); (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); (_e) = (_n))