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