annotate compat/tree.h @ 3:2b9244d20ecf

Add awk script to pretty print pwsdump output
author Guido Berhoerster <guido+libpws@berhoerster.name>
date Fri, 03 Apr 2015 14:57:57 +0200
parents d541e748cfd8
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
1 /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
2 /*
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
3 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
4 * All rights reserved.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
5 *
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
8 * are met:
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
11 * 2. Redistributions in binary form must reproduce the above copyright
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
12 * notice, this list of conditions and the following disclaimer in the
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
13 * documentation and/or other materials provided with the distribution.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
14 *
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
25 */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
26
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
27 #ifndef _SYS_TREE_H_
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
28 #define _SYS_TREE_H_
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
29
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
30 /*
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
31 * This file defines data structures for different types of trees:
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
32 * splay trees and red-black trees.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
33 *
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
34 * A splay tree is a self-organizing data structure. Every operation
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
35 * on the tree causes a splay to happen. The splay moves the requested
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
36 * node to the root of the tree and partly rebalances it.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
37 *
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
38 * This has the benefit that request locality causes faster lookups as
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
39 * the requested nodes move to the top of the tree. On the other hand,
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
40 * every lookup causes memory writes.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
41 *
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
42 * The Balance Theorem bounds the total access time for m operations
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
43 * and n inserts on an initially empty tree as O((m + n)lg n). The
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
44 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
45 *
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
46 * A red-black tree is a binary search tree with the node color as an
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
47 * extra attribute. It fulfills a set of conditions:
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
48 * - every search path from the root to a leaf consists of the
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
49 * same number of black nodes,
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
50 * - each red node (except for the root) has a black parent,
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
51 * - each leaf node is black.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
52 *
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
53 * Every operation on a red-black tree is bounded as O(lg n).
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
54 * The maximum height of a red-black tree is 2lg (n+1).
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
55 */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
56
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
57 #define SPLAY_HEAD(name, type) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
58 struct name { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
59 struct type *sph_root; /* root of the tree */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
60 }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
61
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
62 #define SPLAY_INITIALIZER(root) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
63 { NULL }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
64
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
65 #define SPLAY_INIT(root) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
66 (root)->sph_root = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
67 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
68
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
69 #define SPLAY_ENTRY(type) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
70 struct { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
71 struct type *spe_left; /* left element */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
72 struct type *spe_right; /* right element */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
73 }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
74
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
75 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
76 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
77 #define SPLAY_ROOT(head) (head)->sph_root
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
78 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
79
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
80 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
82 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
83 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
84 (head)->sph_root = tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
85 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
86
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
88 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
89 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
90 (head)->sph_root = tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
91 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
92
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
93 #define SPLAY_LINKLEFT(head, tmp, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
95 tmp = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
96 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
97 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
98
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
99 #define SPLAY_LINKRIGHT(head, tmp, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
100 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
101 tmp = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
102 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
103 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
104
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
106 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
107 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
108 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
109 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
110 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
111
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
112 /* Generates prototypes and inline functions */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
113
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
114 #define SPLAY_PROTOTYPE(name, type, field, cmp) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
115 void name##_SPLAY(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
116 void name##_SPLAY_MINMAX(struct name *, int); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
117 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
119 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
120 /* Finds the node with the same key as elm */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
121 static __inline struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
122 name##_SPLAY_FIND(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
123 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
124 if (SPLAY_EMPTY(head)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
125 return(NULL); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
126 name##_SPLAY(head, elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
127 if ((cmp)(elm, (head)->sph_root) == 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
128 return (head->sph_root); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
129 return (NULL); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
130 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
131 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
132 static __inline struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
133 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
134 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
135 name##_SPLAY(head, elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
136 if (SPLAY_RIGHT(elm, field) != NULL) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
137 elm = SPLAY_RIGHT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
138 while (SPLAY_LEFT(elm, field) != NULL) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
139 elm = SPLAY_LEFT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
140 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
141 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
142 elm = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
143 return (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
144 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
145 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
146 static __inline struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
147 name##_SPLAY_MIN_MAX(struct name *head, int val) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
148 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
149 name##_SPLAY_MINMAX(head, val); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
150 return (SPLAY_ROOT(head)); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
151 }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
152
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
153 /* Main splay operation.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
154 * Moves node close to the key of elm to top
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
155 */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
156 #define SPLAY_GENERATE(name, type, field, cmp) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
157 struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
158 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
159 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
160 if (SPLAY_EMPTY(head)) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
161 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
162 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
163 int __comp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
164 name##_SPLAY(head, elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
165 __comp = (cmp)(elm, (head)->sph_root); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
166 if(__comp < 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
167 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
168 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
169 SPLAY_LEFT((head)->sph_root, field) = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
170 } else if (__comp > 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
171 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
172 SPLAY_LEFT(elm, field) = (head)->sph_root; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
173 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
174 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
175 return ((head)->sph_root); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
176 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
177 (head)->sph_root = (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
178 return (NULL); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
179 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
180 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
181 struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
182 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
183 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
184 struct type *__tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
185 if (SPLAY_EMPTY(head)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
186 return (NULL); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
187 name##_SPLAY(head, elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
188 if ((cmp)(elm, (head)->sph_root) == 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
189 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
190 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
191 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
192 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
193 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
194 name##_SPLAY(head, elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
195 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
196 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
197 return (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
198 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
199 return (NULL); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
200 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
201 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
202 void \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
203 name##_SPLAY(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
204 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
205 struct type __node, *__left, *__right, *__tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
206 int __comp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
207 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
208 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
209 __left = __right = &__node; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
210 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
211 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
212 if (__comp < 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
213 __tmp = SPLAY_LEFT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
214 if (__tmp == NULL) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
215 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
216 if ((cmp)(elm, __tmp) < 0){ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
217 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
218 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
219 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
220 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
221 SPLAY_LINKLEFT(head, __right, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
222 } else if (__comp > 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
223 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
224 if (__tmp == NULL) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
225 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
226 if ((cmp)(elm, __tmp) > 0){ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
227 SPLAY_ROTATE_LEFT(head, __tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
228 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
229 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
230 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
231 SPLAY_LINKRIGHT(head, __left, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
232 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
233 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
234 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
235 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
236 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
237 /* Splay with either the minimum or the maximum element \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
238 * Used to find minimum or maximum element in tree. \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
239 */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
241 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
242 struct type __node, *__left, *__right, *__tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
243 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
244 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
245 __left = __right = &__node; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
246 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
247 while (1) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
248 if (__comp < 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
249 __tmp = SPLAY_LEFT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
250 if (__tmp == NULL) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
251 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
252 if (__comp < 0){ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
253 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
254 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
255 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
256 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
257 SPLAY_LINKLEFT(head, __right, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
258 } else if (__comp > 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
259 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
260 if (__tmp == NULL) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
261 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
262 if (__comp > 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
263 SPLAY_ROTATE_LEFT(head, __tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
264 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
265 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
266 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
267 SPLAY_LINKRIGHT(head, __left, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
268 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
269 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
270 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
271 }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
272
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
273 #define SPLAY_NEGINF -1
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
274 #define SPLAY_INF 1
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
275
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
276 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
277 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
278 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
279 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
280 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
281 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
282 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
283 : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
284
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
285 #define SPLAY_FOREACH(x, name, head) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
286 for ((x) = SPLAY_MIN(name, head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
287 (x) != NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
288 (x) = SPLAY_NEXT(name, head, x))
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
289
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
290 /* Macros that define a red-black tree */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
291 #define RB_HEAD(name, type) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
292 struct name { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
293 struct type *rbh_root; /* root of the tree */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
294 }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
295
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
296 #define RB_INITIALIZER(root) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
297 { NULL }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
298
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
299 #define RB_INIT(root) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
300 (root)->rbh_root = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
301 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
302
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
303 #define RB_BLACK 0
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
304 #define RB_RED 1
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
305 #define RB_ENTRY(type) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
306 struct { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
307 struct type *rbe_left; /* left element */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
308 struct type *rbe_right; /* right element */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
309 struct type *rbe_parent; /* parent element */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
310 int rbe_color; /* node color */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
311 }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
312
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
313 #define RB_LEFT(elm, field) (elm)->field.rbe_left
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
314 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
315 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
316 #define RB_COLOR(elm, field) (elm)->field.rbe_color
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
317 #define RB_ROOT(head) (head)->rbh_root
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
318 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
319
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
320 #define RB_SET(elm, parent, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
321 RB_PARENT(elm, field) = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
322 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
323 RB_COLOR(elm, field) = RB_RED; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
324 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
325
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
326 #define RB_SET_BLACKRED(black, red, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
327 RB_COLOR(black, field) = RB_BLACK; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
328 RB_COLOR(red, field) = RB_RED; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
329 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
330
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
331 #ifndef RB_AUGMENT
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
332 #define RB_AUGMENT(x) do {} while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
333 #endif
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
334
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
336 (tmp) = RB_RIGHT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
337 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
338 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
339 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
340 RB_AUGMENT(elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
341 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
342 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
343 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
344 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
345 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
346 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
347 (head)->rbh_root = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
348 RB_LEFT(tmp, field) = (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
349 RB_PARENT(elm, field) = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
350 RB_AUGMENT(tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
351 if ((RB_PARENT(tmp, field))) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
352 RB_AUGMENT(RB_PARENT(tmp, field)); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
353 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
354
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
356 (tmp) = RB_LEFT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
357 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
358 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
359 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
360 RB_AUGMENT(elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
361 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
362 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
363 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
364 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
365 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
366 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
367 (head)->rbh_root = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
368 RB_RIGHT(tmp, field) = (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
369 RB_PARENT(elm, field) = (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
370 RB_AUGMENT(tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
371 if ((RB_PARENT(tmp, field))) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
372 RB_AUGMENT(RB_PARENT(tmp, field)); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
373 } while (0)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
374
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
375 /* Generates prototypes and inline functions */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
376 #define RB_PROTOTYPE(name, type, field, cmp) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
377 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
378 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
380 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
381 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
382 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
383 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
384 attr struct type *name##_RB_INSERT(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
385 attr struct type *name##_RB_FIND(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
386 attr struct type *name##_RB_NFIND(struct name *, struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
387 attr struct type *name##_RB_NEXT(struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
388 attr struct type *name##_RB_PREV(struct type *); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
389 attr struct type *name##_RB_MINMAX(struct name *, int); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
390 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
391
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
392 /* Main rb operation.
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
393 * Moves node close to the key of elm to top
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
394 */
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
395 #define RB_GENERATE(name, type, field, cmp) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
396 RB_GENERATE_INTERNAL(name, type, field, cmp,)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
397 #define RB_GENERATE_STATIC(name, type, field, cmp) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
398 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
399 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
400 attr void \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
401 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
402 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
403 struct type *parent, *gparent, *tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
404 while ((parent = RB_PARENT(elm, field)) && \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
405 RB_COLOR(parent, field) == RB_RED) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
406 gparent = RB_PARENT(parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
407 if (parent == RB_LEFT(gparent, field)) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
408 tmp = RB_RIGHT(gparent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
409 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
410 RB_COLOR(tmp, field) = RB_BLACK; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
411 RB_SET_BLACKRED(parent, gparent, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
412 elm = gparent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
413 continue; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
414 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
415 if (RB_RIGHT(parent, field) == elm) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
416 RB_ROTATE_LEFT(head, parent, tmp, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
417 tmp = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
418 parent = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
419 elm = tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
420 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
421 RB_SET_BLACKRED(parent, gparent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
422 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
423 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
424 tmp = RB_LEFT(gparent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
425 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
426 RB_COLOR(tmp, field) = RB_BLACK; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
427 RB_SET_BLACKRED(parent, gparent, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
428 elm = gparent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
429 continue; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
430 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
431 if (RB_LEFT(parent, field) == elm) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
432 RB_ROTATE_RIGHT(head, parent, tmp, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
433 tmp = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
434 parent = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
435 elm = tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
436 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
437 RB_SET_BLACKRED(parent, gparent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
438 RB_ROTATE_LEFT(head, gparent, tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
439 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
440 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
441 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
442 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
443 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
444 attr void \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
445 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
446 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
447 struct type *tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
448 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
449 elm != RB_ROOT(head)) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
450 if (RB_LEFT(parent, field) == elm) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
451 tmp = RB_RIGHT(parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
452 if (RB_COLOR(tmp, field) == RB_RED) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
453 RB_SET_BLACKRED(tmp, parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
454 RB_ROTATE_LEFT(head, parent, tmp, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
455 tmp = RB_RIGHT(parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
456 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
457 if ((RB_LEFT(tmp, field) == NULL || \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
458 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
459 (RB_RIGHT(tmp, field) == NULL || \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
460 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
461 RB_COLOR(tmp, field) = RB_RED; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
462 elm = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
463 parent = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
464 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
465 if (RB_RIGHT(tmp, field) == NULL || \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
466 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
467 struct type *oleft; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
468 if ((oleft = RB_LEFT(tmp, field)))\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
469 RB_COLOR(oleft, field) = RB_BLACK;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
470 RB_COLOR(tmp, field) = RB_RED; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
471 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
472 tmp = RB_RIGHT(parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
473 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
474 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
475 RB_COLOR(parent, field) = RB_BLACK; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
476 if (RB_RIGHT(tmp, field)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
477 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
478 RB_ROTATE_LEFT(head, parent, tmp, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
479 elm = RB_ROOT(head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
480 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
481 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
482 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
483 tmp = RB_LEFT(parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
484 if (RB_COLOR(tmp, field) == RB_RED) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
485 RB_SET_BLACKRED(tmp, parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
486 RB_ROTATE_RIGHT(head, parent, tmp, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
487 tmp = RB_LEFT(parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
488 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
489 if ((RB_LEFT(tmp, field) == NULL || \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
490 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
491 (RB_RIGHT(tmp, field) == NULL || \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
492 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
493 RB_COLOR(tmp, field) = RB_RED; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
494 elm = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
495 parent = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
496 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
497 if (RB_LEFT(tmp, field) == NULL || \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
498 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
499 struct type *oright; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
500 if ((oright = RB_RIGHT(tmp, field)))\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
501 RB_COLOR(oright, field) = RB_BLACK;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
502 RB_COLOR(tmp, field) = RB_RED; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
503 RB_ROTATE_LEFT(head, tmp, oright, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
504 tmp = RB_LEFT(parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
505 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
506 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
507 RB_COLOR(parent, field) = RB_BLACK; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
508 if (RB_LEFT(tmp, field)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
509 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
510 RB_ROTATE_RIGHT(head, parent, tmp, field);\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
511 elm = RB_ROOT(head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
512 break; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
513 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
514 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
515 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
516 if (elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
517 RB_COLOR(elm, field) = RB_BLACK; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
518 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
519 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
520 attr struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
521 name##_RB_REMOVE(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
522 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
523 struct type *child, *parent, *old = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
524 int color; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
525 if (RB_LEFT(elm, field) == NULL) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
526 child = RB_RIGHT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
527 else if (RB_RIGHT(elm, field) == NULL) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
528 child = RB_LEFT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
529 else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
530 struct type *left; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
531 elm = RB_RIGHT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
532 while ((left = RB_LEFT(elm, field))) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
533 elm = left; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
534 child = RB_RIGHT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
535 parent = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
536 color = RB_COLOR(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
537 if (child) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
538 RB_PARENT(child, field) = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
539 if (parent) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
540 if (RB_LEFT(parent, field) == elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
541 RB_LEFT(parent, field) = child; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
542 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
543 RB_RIGHT(parent, field) = child; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
544 RB_AUGMENT(parent); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
545 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
546 RB_ROOT(head) = child; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
547 if (RB_PARENT(elm, field) == old) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
548 parent = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
549 (elm)->field = (old)->field; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
550 if (RB_PARENT(old, field)) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
551 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
552 RB_LEFT(RB_PARENT(old, field), field) = elm;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
553 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
554 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
555 RB_AUGMENT(RB_PARENT(old, field)); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
556 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
557 RB_ROOT(head) = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
558 RB_PARENT(RB_LEFT(old, field), field) = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
559 if (RB_RIGHT(old, field)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
560 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
561 if (parent) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
562 left = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
563 do { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
564 RB_AUGMENT(left); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
565 } while ((left = RB_PARENT(left, field))); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
566 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
567 goto color; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
568 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
569 parent = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
570 color = RB_COLOR(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
571 if (child) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
572 RB_PARENT(child, field) = parent; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
573 if (parent) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
574 if (RB_LEFT(parent, field) == elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
575 RB_LEFT(parent, field) = child; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
576 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
577 RB_RIGHT(parent, field) = child; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
578 RB_AUGMENT(parent); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
579 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
580 RB_ROOT(head) = child; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
581 color: \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
582 if (color == RB_BLACK) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
583 name##_RB_REMOVE_COLOR(head, parent, child); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
584 return (old); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
585 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
586 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
587 /* Inserts a node into the RB tree */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
588 attr struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
589 name##_RB_INSERT(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
590 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
591 struct type *tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
592 struct type *parent = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
593 int comp = 0; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
594 tmp = RB_ROOT(head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
595 while (tmp) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
596 parent = tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
597 comp = (cmp)(elm, parent); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
598 if (comp < 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
599 tmp = RB_LEFT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
600 else if (comp > 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
601 tmp = RB_RIGHT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
602 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
603 return (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
604 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
605 RB_SET(elm, parent, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
606 if (parent != NULL) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
607 if (comp < 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
608 RB_LEFT(parent, field) = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
609 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
610 RB_RIGHT(parent, field) = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
611 RB_AUGMENT(parent); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
612 } else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
613 RB_ROOT(head) = elm; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
614 name##_RB_INSERT_COLOR(head, elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
615 return (NULL); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
616 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
617 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
618 /* Finds the node with the same key as elm */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
619 attr struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
620 name##_RB_FIND(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
621 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
622 struct type *tmp = RB_ROOT(head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
623 int comp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
624 while (tmp) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
625 comp = cmp(elm, tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
626 if (comp < 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
627 tmp = RB_LEFT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
628 else if (comp > 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
629 tmp = RB_RIGHT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
630 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
631 return (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
632 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
633 return (NULL); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
634 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
635 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
636 /* Finds the first node greater than or equal to the search key */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
637 attr struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
638 name##_RB_NFIND(struct name *head, struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
639 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
640 struct type *tmp = RB_ROOT(head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
641 struct type *res = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
642 int comp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
643 while (tmp) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
644 comp = cmp(elm, tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
645 if (comp < 0) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
646 res = tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
647 tmp = RB_LEFT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
648 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
649 else if (comp > 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
650 tmp = RB_RIGHT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
651 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
652 return (tmp); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
653 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
654 return (res); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
655 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
656 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
657 /* ARGSUSED */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
658 attr struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
659 name##_RB_NEXT(struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
660 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
661 if (RB_RIGHT(elm, field)) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
662 elm = RB_RIGHT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
663 while (RB_LEFT(elm, field)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
664 elm = RB_LEFT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
665 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
666 if (RB_PARENT(elm, field) && \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
667 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
668 elm = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
669 else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
670 while (RB_PARENT(elm, field) && \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
671 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
672 elm = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
673 elm = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
674 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
675 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
676 return (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
677 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
678 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
679 /* ARGSUSED */ \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
680 attr struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
681 name##_RB_PREV(struct type *elm) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
682 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
683 if (RB_LEFT(elm, field)) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
684 elm = RB_LEFT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
685 while (RB_RIGHT(elm, field)) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
686 elm = RB_RIGHT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
687 } else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
688 if (RB_PARENT(elm, field) && \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
689 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
690 elm = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
691 else { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
692 while (RB_PARENT(elm, field) && \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
693 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
694 elm = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
695 elm = RB_PARENT(elm, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
696 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
697 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
698 return (elm); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
699 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
700 \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
701 attr struct type * \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
702 name##_RB_MINMAX(struct name *head, int val) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
703 { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
704 struct type *tmp = RB_ROOT(head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
705 struct type *parent = NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
706 while (tmp) { \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
707 parent = tmp; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
708 if (val < 0) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
709 tmp = RB_LEFT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
710 else \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
711 tmp = RB_RIGHT(tmp, field); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
712 } \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
713 return (parent); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
714 }
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
715
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
716 #define RB_NEGINF -1
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
717 #define RB_INF 1
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
718
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
719 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
720 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
721 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
722 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
723 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
724 #define RB_PREV(name, x, y) name##_RB_PREV(y)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
725 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
726 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
727
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
728 #define RB_FOREACH(x, name, head) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
729 for ((x) = RB_MIN(name, head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
730 (x) != NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
731 (x) = name##_RB_NEXT(x))
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
732
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
733 #define RB_FOREACH_SAFE(x, name, head, y) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
734 for ((x) = RB_MIN(name, head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
735 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
736 (x) = (y))
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
737
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
738 #define RB_FOREACH_REVERSE(x, name, head) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
739 for ((x) = RB_MAX(name, head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
740 (x) != NULL; \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
741 (x) = name##_RB_PREV(x))
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
742
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
743 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
744 for ((x) = RB_MAX(name, head); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
745 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
746 (x) = (y))
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
747
d541e748cfd8 Initial revision
Guido Berhoerster <guido+libpws@berhoerster.name>
parents:
diff changeset
748 #endif /* _SYS_TREE_H_ */