diff options
author | Colin Watson <cjwatson@debian.org> | 2005-05-30 21:44:32 +0000 |
---|---|---|
committer | Colin Watson <cjwatson@debian.org> | 2005-05-30 21:44:32 +0000 |
commit | a55bd782aa819b7f5ae716de000f19f4f531850e (patch) | |
tree | 12638b19bc0ed9c8d48541d460693ab0fbb58e89 /openbsd-compat | |
parent | fe9489f7e522f780f3fa5c2f28208124d193398c (diff) | |
parent | 5d05471f6657646d1d6500c7c43134462c407ee6 (diff) |
Import OpenSSH 4.1p1.
Diffstat (limited to 'openbsd-compat')
31 files changed, 1889 insertions, 0 deletions
diff --git a/openbsd-compat/basename.h b/openbsd-compat/basename.h new file mode 100644 index 000000000..a8bd6c17c --- /dev/null +++ b/openbsd-compat/basename.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: basename.h,v 1.3 2003/02/25 03:32:16 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BASENAME_H | ||
4 | #define _BASENAME_H | ||
5 | #include "config.h" | ||
6 | |||
7 | #if !defined(HAVE_BASENAME) | ||
8 | |||
9 | char *basename(const char *path); | ||
10 | |||
11 | #endif /* !defined(HAVE_BASENAME) */ | ||
12 | #endif /* _BASENAME_H */ | ||
diff --git a/openbsd-compat/bindresvport.h b/openbsd-compat/bindresvport.h new file mode 100644 index 000000000..b42f46983 --- /dev/null +++ b/openbsd-compat/bindresvport.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: bindresvport.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_BINDRESVPORT_H | ||
4 | #define _BSD_BINDRESVPORT_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_BINDRESVPORT_SA | ||
9 | int bindresvport_sa(int sd, struct sockaddr *sa); | ||
10 | #endif /* !HAVE_BINDRESVPORT_SA */ | ||
11 | |||
12 | #endif /* _BSD_BINDRESVPORT_H */ | ||
diff --git a/openbsd-compat/bsd-arc4random.h b/openbsd-compat/bsd-arc4random.h new file mode 100644 index 000000000..7af757b2d --- /dev/null +++ b/openbsd-compat/bsd-arc4random.h | |||
@@ -0,0 +1,37 @@ | |||
1 | /* | ||
2 | * Copyright (c) 1999-2000 Damien Miller. All rights reserved. | ||
3 | * | ||
4 | * Redistribution and use in source and binary forms, with or without | ||
5 | * modification, are permitted provided that the following conditions | ||
6 | * are met: | ||
7 | * 1. Redistributions of source code must retain the above copyright | ||
8 | * notice, this list of conditions and the following disclaimer. | ||
9 | * 2. Redistributions in binary form must reproduce the above copyright | ||
10 | * notice, this list of conditions and the following disclaimer in the | ||
11 | * documentation and/or other materials provided with the distribution. | ||
12 | * | ||
13 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | ||
14 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | ||
15 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | ||
16 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
17 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
18 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
19 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
20 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
21 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | ||
22 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
23 | */ | ||
24 | |||
25 | /* $Id: bsd-arc4random.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
26 | |||
27 | #ifndef _BSD_ARC4RANDOM_H | ||
28 | #define _BSD_ARC4RANDOM_H | ||
29 | |||
30 | #include "config.h" | ||
31 | |||
32 | #ifndef HAVE_ARC4RANDOM | ||
33 | unsigned int arc4random(void); | ||
34 | void arc4random_stir(void); | ||
35 | #endif /* !HAVE_ARC4RANDOM */ | ||
36 | |||
37 | #endif /* _BSD_ARC4RANDOM_H */ | ||
diff --git a/openbsd-compat/bsd-getpeereid.h b/openbsd-compat/bsd-getpeereid.h new file mode 100644 index 000000000..2e9f077f9 --- /dev/null +++ b/openbsd-compat/bsd-getpeereid.h | |||
@@ -0,0 +1,14 @@ | |||
1 | /* $Id: bsd-getpeereid.h,v 1.1 2002/09/12 00:33:02 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_GETPEEREID_H | ||
4 | #define _BSD_GETPEEREID_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #include <sys/types.h> /* For uid_t, gid_t */ | ||
9 | |||
10 | #ifndef HAVE_GETPEEREID | ||
11 | int getpeereid(int , uid_t *, gid_t *); | ||
12 | #endif /* HAVE_GETPEEREID */ | ||
13 | |||
14 | #endif /* _BSD_GETPEEREID_H */ | ||
diff --git a/openbsd-compat/bsd-snprintf.h b/openbsd-compat/bsd-snprintf.h new file mode 100644 index 000000000..002b764e3 --- /dev/null +++ b/openbsd-compat/bsd-snprintf.h | |||
@@ -0,0 +1,19 @@ | |||
1 | /* $Id: bsd-snprintf.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_SNPRINTF_H | ||
4 | #define _BSD_SNPRINTF_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #include <sys/types.h> /* For size_t */ | ||
9 | |||
10 | #ifndef HAVE_SNPRINTF | ||
11 | int snprintf(char *str, size_t count, const char *fmt, ...); | ||
12 | #endif /* !HAVE_SNPRINTF */ | ||
13 | |||
14 | #ifndef HAVE_VSNPRINTF | ||
15 | int vsnprintf(char *str, size_t count, const char *fmt, va_list args); | ||
16 | #endif /* !HAVE_SNPRINTF */ | ||
17 | |||
18 | |||
19 | #endif /* _BSD_SNPRINTF_H */ | ||
diff --git a/openbsd-compat/daemon.h b/openbsd-compat/daemon.h new file mode 100644 index 000000000..95a077359 --- /dev/null +++ b/openbsd-compat/daemon.h | |||
@@ -0,0 +1,11 @@ | |||
1 | /* $Id: daemon.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_DAEMON_H | ||
4 | #define _BSD_DAEMON_H | ||
5 | |||
6 | #include "config.h" | ||
7 | #ifndef HAVE_DAEMON | ||
8 | int daemon(int nochdir, int noclose); | ||
9 | #endif /* !HAVE_DAEMON */ | ||
10 | |||
11 | #endif /* _BSD_DAEMON_H */ | ||
diff --git a/openbsd-compat/dirname.h b/openbsd-compat/dirname.h new file mode 100644 index 000000000..1d61dd06c --- /dev/null +++ b/openbsd-compat/dirname.h | |||
@@ -0,0 +1,5 @@ | |||
1 | #ifndef HAVE_DIRNAME | ||
2 | |||
3 | char *dirname(const char *path); | ||
4 | |||
5 | #endif | ||
diff --git a/openbsd-compat/fake-gai-errnos.h b/openbsd-compat/fake-gai-errnos.h new file mode 100644 index 000000000..5edc31b59 --- /dev/null +++ b/openbsd-compat/fake-gai-errnos.h | |||
@@ -0,0 +1,14 @@ | |||
1 | /* | ||
2 | * fake library for ssh | ||
3 | * | ||
4 | * This file is included in getaddrinfo.c and getnameinfo.c. | ||
5 | * See getaddrinfo.c and getnameinfo.c. | ||
6 | */ | ||
7 | |||
8 | /* $Id: fake-gai-errnos.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
9 | |||
10 | /* for old netdb.h */ | ||
11 | #ifndef EAI_NODATA | ||
12 | #define EAI_NODATA 1 | ||
13 | #define EAI_MEMORY 2 | ||
14 | #endif | ||
diff --git a/openbsd-compat/fake-getaddrinfo.c b/openbsd-compat/fake-getaddrinfo.c new file mode 100644 index 000000000..e63bda970 --- /dev/null +++ b/openbsd-compat/fake-getaddrinfo.c | |||
@@ -0,0 +1,135 @@ | |||
1 | /* | ||
2 | * fake library for ssh | ||
3 | * | ||
4 | * This file includes getaddrinfo(), freeaddrinfo() and gai_strerror(). | ||
5 | * These funtions are defined in rfc2133. | ||
6 | * | ||
7 | * But these functions are not implemented correctly. The minimum subset | ||
8 | * is implemented for ssh use only. For exapmle, this routine assumes | ||
9 | * that ai_family is AF_INET. Don't use it for another purpose. | ||
10 | */ | ||
11 | |||
12 | #include "includes.h" | ||
13 | #include "ssh.h" | ||
14 | |||
15 | RCSID("$Id: fake-getaddrinfo.c,v 1.5 2003/03/24 02:35:59 djm Exp $"); | ||
16 | |||
17 | #ifndef HAVE_GAI_STRERROR | ||
18 | char *gai_strerror(int ecode) | ||
19 | { | ||
20 | switch (ecode) { | ||
21 | case EAI_NODATA: | ||
22 | return "no address associated with hostname."; | ||
23 | case EAI_MEMORY: | ||
24 | return "memory allocation failure."; | ||
25 | default: | ||
26 | return "unknown error."; | ||
27 | } | ||
28 | } | ||
29 | #endif /* !HAVE_GAI_STRERROR */ | ||
30 | |||
31 | #ifndef HAVE_FREEADDRINFO | ||
32 | void freeaddrinfo(struct addrinfo *ai) | ||
33 | { | ||
34 | struct addrinfo *next; | ||
35 | |||
36 | do { | ||
37 | next = ai->ai_next; | ||
38 | free(ai); | ||
39 | } while (NULL != (ai = next)); | ||
40 | } | ||
41 | #endif /* !HAVE_FREEADDRINFO */ | ||
42 | |||
43 | #ifndef HAVE_GETADDRINFO | ||
44 | static struct addrinfo *malloc_ai(int port, u_long addr) | ||
45 | { | ||
46 | struct addrinfo *ai; | ||
47 | |||
48 | ai = malloc(sizeof(struct addrinfo) + sizeof(struct sockaddr_in)); | ||
49 | if (ai == NULL) | ||
50 | return(NULL); | ||
51 | |||
52 | memset(ai, 0, sizeof(struct addrinfo) + sizeof(struct sockaddr_in)); | ||
53 | |||
54 | ai->ai_addr = (struct sockaddr *)(ai + 1); | ||
55 | /* XXX -- ssh doesn't use sa_len */ | ||
56 | ai->ai_addrlen = sizeof(struct sockaddr_in); | ||
57 | ai->ai_addr->sa_family = ai->ai_family = AF_INET; | ||
58 | |||
59 | ((struct sockaddr_in *)(ai)->ai_addr)->sin_port = port; | ||
60 | ((struct sockaddr_in *)(ai)->ai_addr)->sin_addr.s_addr = addr; | ||
61 | |||
62 | return(ai); | ||
63 | } | ||
64 | |||
65 | int getaddrinfo(const char *hostname, const char *servname, | ||
66 | const struct addrinfo *hints, struct addrinfo **res) | ||
67 | { | ||
68 | struct addrinfo *cur, *prev = NULL; | ||
69 | struct hostent *hp; | ||
70 | struct servent *sp; | ||
71 | struct in_addr in; | ||
72 | int i; | ||
73 | long int port; | ||
74 | u_long addr; | ||
75 | |||
76 | port = 0; | ||
77 | if (servname != NULL) { | ||
78 | char *cp; | ||
79 | |||
80 | port = strtol(servname, &cp, 10); | ||
81 | if (port > 0 && port <= 65535 && *cp == '\0') | ||
82 | port = htons(port); | ||
83 | else if ((sp = getservbyname(servname, NULL)) != NULL) | ||
84 | port = sp->s_port; | ||
85 | else | ||
86 | port = 0; | ||
87 | } | ||
88 | |||
89 | if (hints && hints->ai_flags & AI_PASSIVE) { | ||
90 | addr = htonl(0x00000000); | ||
91 | if (hostname && inet_aton(hostname, &in) != 0) | ||
92 | addr = in.s_addr; | ||
93 | if (NULL != (*res = malloc_ai(port, addr))) | ||
94 | return 0; | ||
95 | else | ||
96 | return EAI_MEMORY; | ||
97 | } | ||
98 | |||
99 | if (!hostname) { | ||
100 | if (NULL != (*res = malloc_ai(port, htonl(0x7f000001)))) | ||
101 | return 0; | ||
102 | else | ||
103 | return EAI_MEMORY; | ||
104 | } | ||
105 | |||
106 | if (inet_aton(hostname, &in)) { | ||
107 | if (NULL != (*res = malloc_ai(port, in.s_addr))) | ||
108 | return 0; | ||
109 | else | ||
110 | return EAI_MEMORY; | ||
111 | } | ||
112 | |||
113 | hp = gethostbyname(hostname); | ||
114 | if (hp && hp->h_name && hp->h_name[0] && hp->h_addr_list[0]) { | ||
115 | for (i = 0; hp->h_addr_list[i]; i++) { | ||
116 | cur = malloc_ai(port, ((struct in_addr *)hp->h_addr_list[i])->s_addr); | ||
117 | if (cur == NULL) { | ||
118 | if (*res) | ||
119 | freeaddrinfo(*res); | ||
120 | return EAI_MEMORY; | ||
121 | } | ||
122 | |||
123 | if (prev) | ||
124 | prev->ai_next = cur; | ||
125 | else | ||
126 | *res = cur; | ||
127 | |||
128 | prev = cur; | ||
129 | } | ||
130 | return 0; | ||
131 | } | ||
132 | |||
133 | return EAI_NODATA; | ||
134 | } | ||
135 | #endif /* !HAVE_GETADDRINFO */ | ||
diff --git a/openbsd-compat/fake-getaddrinfo.h b/openbsd-compat/fake-getaddrinfo.h new file mode 100644 index 000000000..6943378e9 --- /dev/null +++ b/openbsd-compat/fake-getaddrinfo.h | |||
@@ -0,0 +1,47 @@ | |||
1 | /* $Id: fake-getaddrinfo.h,v 1.4 2003/02/24 01:35:09 djm Exp $ */ | ||
2 | |||
3 | #ifndef _FAKE_GETADDRINFO_H | ||
4 | #define _FAKE_GETADDRINFO_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #include "fake-gai-errnos.h" | ||
9 | |||
10 | #ifndef AI_PASSIVE | ||
11 | # define AI_PASSIVE 1 | ||
12 | # define AI_CANONNAME 2 | ||
13 | #endif | ||
14 | |||
15 | #ifndef NI_NUMERICHOST | ||
16 | # define NI_NUMERICHOST 2 | ||
17 | # define NI_NAMEREQD 4 | ||
18 | # define NI_NUMERICSERV 8 | ||
19 | #endif | ||
20 | |||
21 | #ifndef HAVE_STRUCT_ADDRINFO | ||
22 | struct addrinfo { | ||
23 | int ai_flags; /* AI_PASSIVE, AI_CANONNAME */ | ||
24 | int ai_family; /* PF_xxx */ | ||
25 | int ai_socktype; /* SOCK_xxx */ | ||
26 | int ai_protocol; /* 0 or IPPROTO_xxx for IPv4 and IPv6 */ | ||
27 | size_t ai_addrlen; /* length of ai_addr */ | ||
28 | char *ai_canonname; /* canonical name for hostname */ | ||
29 | struct sockaddr *ai_addr; /* binary address */ | ||
30 | struct addrinfo *ai_next; /* next structure in linked list */ | ||
31 | }; | ||
32 | #endif /* !HAVE_STRUCT_ADDRINFO */ | ||
33 | |||
34 | #ifndef HAVE_GETADDRINFO | ||
35 | int getaddrinfo(const char *hostname, const char *servname, | ||
36 | const struct addrinfo *hints, struct addrinfo **res); | ||
37 | #endif /* !HAVE_GETADDRINFO */ | ||
38 | |||
39 | #ifndef HAVE_GAI_STRERROR | ||
40 | char *gai_strerror(int ecode); | ||
41 | #endif /* !HAVE_GAI_STRERROR */ | ||
42 | |||
43 | #ifndef HAVE_FREEADDRINFO | ||
44 | void freeaddrinfo(struct addrinfo *ai); | ||
45 | #endif /* !HAVE_FREEADDRINFO */ | ||
46 | |||
47 | #endif /* _FAKE_GETADDRINFO_H */ | ||
diff --git a/openbsd-compat/fake-getnameinfo.c b/openbsd-compat/fake-getnameinfo.c new file mode 100644 index 000000000..e255ed333 --- /dev/null +++ b/openbsd-compat/fake-getnameinfo.c | |||
@@ -0,0 +1,55 @@ | |||
1 | /* | ||
2 | * fake library for ssh | ||
3 | * | ||
4 | * This file includes getnameinfo(). | ||
5 | * These funtions are defined in rfc2133. | ||
6 | * | ||
7 | * But these functions are not implemented correctly. The minimum subset | ||
8 | * is implemented for ssh use only. For exapmle, this routine assumes | ||
9 | * that ai_family is AF_INET. Don't use it for another purpose. | ||
10 | */ | ||
11 | |||
12 | #include "includes.h" | ||
13 | #include "ssh.h" | ||
14 | |||
15 | RCSID("$Id: fake-getnameinfo.c,v 1.2 2001/02/09 01:55:36 djm Exp $"); | ||
16 | |||
17 | #ifndef HAVE_GETNAMEINFO | ||
18 | int getnameinfo(const struct sockaddr *sa, size_t salen, char *host, | ||
19 | size_t hostlen, char *serv, size_t servlen, int flags) | ||
20 | { | ||
21 | struct sockaddr_in *sin = (struct sockaddr_in *)sa; | ||
22 | struct hostent *hp; | ||
23 | char tmpserv[16]; | ||
24 | |||
25 | if (serv) { | ||
26 | snprintf(tmpserv, sizeof(tmpserv), "%d", ntohs(sin->sin_port)); | ||
27 | if (strlen(tmpserv) >= servlen) | ||
28 | return EAI_MEMORY; | ||
29 | else | ||
30 | strcpy(serv, tmpserv); | ||
31 | } | ||
32 | |||
33 | if (host) { | ||
34 | if (flags & NI_NUMERICHOST) { | ||
35 | if (strlen(inet_ntoa(sin->sin_addr)) >= hostlen) | ||
36 | return EAI_MEMORY; | ||
37 | |||
38 | strcpy(host, inet_ntoa(sin->sin_addr)); | ||
39 | return 0; | ||
40 | } else { | ||
41 | hp = gethostbyaddr((char *)&sin->sin_addr, | ||
42 | sizeof(struct in_addr), AF_INET); | ||
43 | if (hp == NULL) | ||
44 | return EAI_NODATA; | ||
45 | |||
46 | if (strlen(hp->h_name) >= hostlen) | ||
47 | return EAI_MEMORY; | ||
48 | |||
49 | strcpy(host, hp->h_name); | ||
50 | return 0; | ||
51 | } | ||
52 | } | ||
53 | return 0; | ||
54 | } | ||
55 | #endif /* !HAVE_GETNAMEINFO */ | ||
diff --git a/openbsd-compat/fake-getnameinfo.h b/openbsd-compat/fake-getnameinfo.h new file mode 100644 index 000000000..c9b7908aa --- /dev/null +++ b/openbsd-compat/fake-getnameinfo.h | |||
@@ -0,0 +1,20 @@ | |||
1 | /* $Id: fake-getnameinfo.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _FAKE_GETNAMEINFO_H | ||
4 | #define _FAKE_GETNAMEINFO_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_GETNAMEINFO | ||
9 | int getnameinfo(const struct sockaddr *sa, size_t salen, char *host, | ||
10 | size_t hostlen, char *serv, size_t servlen, int flags); | ||
11 | #endif /* !HAVE_GETNAMEINFO */ | ||
12 | |||
13 | #ifndef NI_MAXSERV | ||
14 | # define NI_MAXSERV 32 | ||
15 | #endif /* !NI_MAXSERV */ | ||
16 | #ifndef NI_MAXHOST | ||
17 | # define NI_MAXHOST 1025 | ||
18 | #endif /* !NI_MAXHOST */ | ||
19 | |||
20 | #endif /* _FAKE_GETNAMEINFO_H */ | ||
diff --git a/openbsd-compat/fake-queue.h b/openbsd-compat/fake-queue.h new file mode 100644 index 000000000..176fe3174 --- /dev/null +++ b/openbsd-compat/fake-queue.h | |||
@@ -0,0 +1,584 @@ | |||
1 | /* $OpenBSD: queue.h,v 1.22 2001/06/23 04:39:35 angelos Exp $ */ | ||
2 | /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ | ||
3 | |||
4 | /* | ||
5 | * Copyright (c) 1991, 1993 | ||
6 | * The Regents of the University of California. All rights reserved. | ||
7 | * | ||
8 | * Redistribution and use in source and binary forms, with or without | ||
9 | * modification, are permitted provided that the following conditions | ||
10 | * are met: | ||
11 | * 1. Redistributions of source code must retain the above copyright | ||
12 | * notice, this list of conditions and the following disclaimer. | ||
13 | * 2. Redistributions in binary form must reproduce the above copyright | ||
14 | * notice, this list of conditions and the following disclaimer in the | ||
15 | * documentation and/or other materials provided with the distribution. | ||
16 | * 3. All advertising materials mentioning features or use of this software | ||
17 | * must display the following acknowledgement: | ||
18 | * This product includes software developed by the University of | ||
19 | * California, Berkeley and its contributors. | ||
20 | * 4. Neither the name of the University nor the names of its contributors | ||
21 | * may be used to endorse or promote products derived from this software | ||
22 | * without specific prior written permission. | ||
23 | * | ||
24 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | ||
25 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
26 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
27 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | ||
28 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
29 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | ||
30 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
31 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
32 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | ||
33 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||
34 | * SUCH DAMAGE. | ||
35 | * | ||
36 | * @(#)queue.h 8.5 (Berkeley) 8/20/94 | ||
37 | */ | ||
38 | |||
39 | #ifndef _FAKE_QUEUE_H_ | ||
40 | #define _FAKE_QUEUE_H_ | ||
41 | |||
42 | /* | ||
43 | * Ignore all <sys/queue.h> since older platforms have broken/incomplete | ||
44 | * <sys/queue.h> that are too hard to work around. | ||
45 | */ | ||
46 | #undef SLIST_HEAD | ||
47 | #undef SLIST_HEAD_INITIALIZER | ||
48 | #undef SLIST_ENTRY | ||
49 | #undef SLIST_FIRST | ||
50 | #undef SLIST_END | ||
51 | #undef SLIST_EMPTY | ||
52 | #undef SLIST_NEXT | ||
53 | #undef SLIST_FOREACH | ||
54 | #undef SLIST_INIT | ||
55 | #undef SLIST_INSERT_AFTER | ||
56 | #undef SLIST_INSERT_HEAD | ||
57 | #undef SLIST_REMOVE_HEAD | ||
58 | #undef SLIST_REMOVE | ||
59 | #undef LIST_HEAD | ||
60 | #undef LIST_HEAD_INITIALIZER | ||
61 | #undef LIST_ENTRY | ||
62 | #undef LIST_FIRST | ||
63 | #undef LIST_END | ||
64 | #undef LIST_EMPTY | ||
65 | #undef LIST_NEXT | ||
66 | #undef LIST_FOREACH | ||
67 | #undef LIST_INIT | ||
68 | #undef LIST_INSERT_AFTER | ||
69 | #undef LIST_INSERT_BEFORE | ||
70 | #undef LIST_INSERT_HEAD | ||
71 | #undef LIST_REMOVE | ||
72 | #undef LIST_REPLACE | ||
73 | #undef SIMPLEQ_HEAD | ||
74 | #undef SIMPLEQ_HEAD_INITIALIZER | ||
75 | #undef SIMPLEQ_ENTRY | ||
76 | #undef SIMPLEQ_FIRST | ||
77 | #undef SIMPLEQ_END | ||
78 | #undef SIMPLEQ_EMPTY | ||
79 | #undef SIMPLEQ_NEXT | ||
80 | #undef SIMPLEQ_FOREACH | ||
81 | #undef SIMPLEQ_INIT | ||
82 | #undef SIMPLEQ_INSERT_HEAD | ||
83 | #undef SIMPLEQ_INSERT_TAIL | ||
84 | #undef SIMPLEQ_INSERT_AFTER | ||
85 | #undef SIMPLEQ_REMOVE_HEAD | ||
86 | #undef TAILQ_HEAD | ||
87 | #undef TAILQ_HEAD_INITIALIZER | ||
88 | #undef TAILQ_ENTRY | ||
89 | #undef TAILQ_FIRST | ||
90 | #undef TAILQ_END | ||
91 | #undef TAILQ_NEXT | ||
92 | #undef TAILQ_LAST | ||
93 | #undef TAILQ_PREV | ||
94 | #undef TAILQ_EMPTY | ||
95 | #undef TAILQ_FOREACH | ||
96 | #undef TAILQ_FOREACH_REVERSE | ||
97 | #undef TAILQ_INIT | ||
98 | #undef TAILQ_INSERT_HEAD | ||
99 | #undef TAILQ_INSERT_TAIL | ||
100 | #undef TAILQ_INSERT_AFTER | ||
101 | #undef TAILQ_INSERT_BEFORE | ||
102 | #undef TAILQ_REMOVE | ||
103 | #undef TAILQ_REPLACE | ||
104 | #undef CIRCLEQ_HEAD | ||
105 | #undef CIRCLEQ_HEAD_INITIALIZER | ||
106 | #undef CIRCLEQ_ENTRY | ||
107 | #undef CIRCLEQ_FIRST | ||
108 | #undef CIRCLEQ_LAST | ||
109 | #undef CIRCLEQ_END | ||
110 | #undef CIRCLEQ_NEXT | ||
111 | #undef CIRCLEQ_PREV | ||
112 | #undef CIRCLEQ_EMPTY | ||
113 | #undef CIRCLEQ_FOREACH | ||
114 | #undef CIRCLEQ_FOREACH_REVERSE | ||
115 | #undef CIRCLEQ_INIT | ||
116 | #undef CIRCLEQ_INSERT_AFTER | ||
117 | #undef CIRCLEQ_INSERT_BEFORE | ||
118 | #undef CIRCLEQ_INSERT_HEAD | ||
119 | #undef CIRCLEQ_INSERT_TAIL | ||
120 | #undef CIRCLEQ_REMOVE | ||
121 | #undef CIRCLEQ_REPLACE | ||
122 | |||
123 | /* | ||
124 | * This file defines five types of data structures: singly-linked lists, | ||
125 | * lists, simple queues, tail queues, and circular queues. | ||
126 | * | ||
127 | * | ||
128 | * A singly-linked list is headed by a single forward pointer. The elements | ||
129 | * are singly linked for minimum space and pointer manipulation overhead at | ||
130 | * the expense of O(n) removal for arbitrary elements. New elements can be | ||
131 | * added to the list after an existing element or at the head of the list. | ||
132 | * Elements being removed from the head of the list should use the explicit | ||
133 | * macro for this purpose for optimum efficiency. A singly-linked list may | ||
134 | * only be traversed in the forward direction. Singly-linked lists are ideal | ||
135 | * for applications with large datasets and few or no removals or for | ||
136 | * implementing a LIFO queue. | ||
137 | * | ||
138 | * A list is headed by a single forward pointer (or an array of forward | ||
139 | * pointers for a hash table header). The elements are doubly linked | ||
140 | * so that an arbitrary element can be removed without a need to | ||
141 | * traverse the list. New elements can be added to the list before | ||
142 | * or after an existing element or at the head of the list. A list | ||
143 | * may only be traversed in the forward direction. | ||
144 | * | ||
145 | * A simple queue is headed by a pair of pointers, one the head of the | ||
146 | * list and the other to the tail of the list. The elements are singly | ||
147 | * linked to save space, so elements can only be removed from the | ||
148 | * head of the list. New elements can be added to the list before or after | ||
149 | * an existing element, at the head of the list, or at the end of the | ||
150 | * list. A simple queue may only be traversed in the forward direction. | ||
151 | * | ||
152 | * A tail queue is headed by a pair of pointers, one to the head of the | ||
153 | * list and the other to the tail of the list. The elements are doubly | ||
154 | * linked so that an arbitrary element can be removed without a need to | ||
155 | * traverse the list. New elements can be added to the list before or | ||
156 | * after an existing element, at the head of the list, or at the end of | ||
157 | * the list. A tail queue may be traversed in either direction. | ||
158 | * | ||
159 | * A circle queue is headed by a pair of pointers, one to the head of the | ||
160 | * list and the other to the tail of the list. The elements are doubly | ||
161 | * linked so that an arbitrary element can be removed without a need to | ||
162 | * traverse the list. New elements can be added to the list before or after | ||
163 | * an existing element, at the head of the list, or at the end of the list. | ||
164 | * A circle queue may be traversed in either direction, but has a more | ||
165 | * complex end of list detection. | ||
166 | * | ||
167 | * For details on the use of these macros, see the queue(3) manual page. | ||
168 | */ | ||
169 | |||
170 | /* | ||
171 | * Singly-linked List definitions. | ||
172 | */ | ||
173 | #define SLIST_HEAD(name, type) \ | ||
174 | struct name { \ | ||
175 | struct type *slh_first; /* first element */ \ | ||
176 | } | ||
177 | |||
178 | #define SLIST_HEAD_INITIALIZER(head) \ | ||
179 | { NULL } | ||
180 | |||
181 | #define SLIST_ENTRY(type) \ | ||
182 | struct { \ | ||
183 | struct type *sle_next; /* next element */ \ | ||
184 | } | ||
185 | |||
186 | /* | ||
187 | * Singly-linked List access methods. | ||
188 | */ | ||
189 | #define SLIST_FIRST(head) ((head)->slh_first) | ||
190 | #define SLIST_END(head) NULL | ||
191 | #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) | ||
192 | #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) | ||
193 | |||
194 | #define SLIST_FOREACH(var, head, field) \ | ||
195 | for((var) = SLIST_FIRST(head); \ | ||
196 | (var) != SLIST_END(head); \ | ||
197 | (var) = SLIST_NEXT(var, field)) | ||
198 | |||
199 | /* | ||
200 | * Singly-linked List functions. | ||
201 | */ | ||
202 | #define SLIST_INIT(head) { \ | ||
203 | SLIST_FIRST(head) = SLIST_END(head); \ | ||
204 | } | ||
205 | |||
206 | #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ | ||
207 | (elm)->field.sle_next = (slistelm)->field.sle_next; \ | ||
208 | (slistelm)->field.sle_next = (elm); \ | ||
209 | } while (0) | ||
210 | |||
211 | #define SLIST_INSERT_HEAD(head, elm, field) do { \ | ||
212 | (elm)->field.sle_next = (head)->slh_first; \ | ||
213 | (head)->slh_first = (elm); \ | ||
214 | } while (0) | ||
215 | |||
216 | #define SLIST_REMOVE_HEAD(head, field) do { \ | ||
217 | (head)->slh_first = (head)->slh_first->field.sle_next; \ | ||
218 | } while (0) | ||
219 | |||
220 | #define SLIST_REMOVE(head, elm, type, field) do { \ | ||
221 | if ((head)->slh_first == (elm)) { \ | ||
222 | SLIST_REMOVE_HEAD((head), field); \ | ||
223 | } \ | ||
224 | else { \ | ||
225 | struct type *curelm = (head)->slh_first; \ | ||
226 | while( curelm->field.sle_next != (elm) ) \ | ||
227 | curelm = curelm->field.sle_next; \ | ||
228 | curelm->field.sle_next = \ | ||
229 | curelm->field.sle_next->field.sle_next; \ | ||
230 | } \ | ||
231 | } while (0) | ||
232 | |||
233 | /* | ||
234 | * List definitions. | ||
235 | */ | ||
236 | #define LIST_HEAD(name, type) \ | ||
237 | struct name { \ | ||
238 | struct type *lh_first; /* first element */ \ | ||
239 | } | ||
240 | |||
241 | #define LIST_HEAD_INITIALIZER(head) \ | ||
242 | { NULL } | ||
243 | |||
244 | #define LIST_ENTRY(type) \ | ||
245 | struct { \ | ||
246 | struct type *le_next; /* next element */ \ | ||
247 | struct type **le_prev; /* address of previous next element */ \ | ||
248 | } | ||
249 | |||
250 | /* | ||
251 | * List access methods | ||
252 | */ | ||
253 | #define LIST_FIRST(head) ((head)->lh_first) | ||
254 | #define LIST_END(head) NULL | ||
255 | #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) | ||
256 | #define LIST_NEXT(elm, field) ((elm)->field.le_next) | ||
257 | |||
258 | #define LIST_FOREACH(var, head, field) \ | ||
259 | for((var) = LIST_FIRST(head); \ | ||
260 | (var)!= LIST_END(head); \ | ||
261 | (var) = LIST_NEXT(var, field)) | ||
262 | |||
263 | /* | ||
264 | * List functions. | ||
265 | */ | ||
266 | #define LIST_INIT(head) do { \ | ||
267 | LIST_FIRST(head) = LIST_END(head); \ | ||
268 | } while (0) | ||
269 | |||
270 | #define LIST_INSERT_AFTER(listelm, elm, field) do { \ | ||
271 | if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ | ||
272 | (listelm)->field.le_next->field.le_prev = \ | ||
273 | &(elm)->field.le_next; \ | ||
274 | (listelm)->field.le_next = (elm); \ | ||
275 | (elm)->field.le_prev = &(listelm)->field.le_next; \ | ||
276 | } while (0) | ||
277 | |||
278 | #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ | ||
279 | (elm)->field.le_prev = (listelm)->field.le_prev; \ | ||
280 | (elm)->field.le_next = (listelm); \ | ||
281 | *(listelm)->field.le_prev = (elm); \ | ||
282 | (listelm)->field.le_prev = &(elm)->field.le_next; \ | ||
283 | } while (0) | ||
284 | |||
285 | #define LIST_INSERT_HEAD(head, elm, field) do { \ | ||
286 | if (((elm)->field.le_next = (head)->lh_first) != NULL) \ | ||
287 | (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ | ||
288 | (head)->lh_first = (elm); \ | ||
289 | (elm)->field.le_prev = &(head)->lh_first; \ | ||
290 | } while (0) | ||
291 | |||
292 | #define LIST_REMOVE(elm, field) do { \ | ||
293 | if ((elm)->field.le_next != NULL) \ | ||
294 | (elm)->field.le_next->field.le_prev = \ | ||
295 | (elm)->field.le_prev; \ | ||
296 | *(elm)->field.le_prev = (elm)->field.le_next; \ | ||
297 | } while (0) | ||
298 | |||
299 | #define LIST_REPLACE(elm, elm2, field) do { \ | ||
300 | if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ | ||
301 | (elm2)->field.le_next->field.le_prev = \ | ||
302 | &(elm2)->field.le_next; \ | ||
303 | (elm2)->field.le_prev = (elm)->field.le_prev; \ | ||
304 | *(elm2)->field.le_prev = (elm2); \ | ||
305 | } while (0) | ||
306 | |||
307 | /* | ||
308 | * Simple queue definitions. | ||
309 | */ | ||
310 | #define SIMPLEQ_HEAD(name, type) \ | ||
311 | struct name { \ | ||
312 | struct type *sqh_first; /* first element */ \ | ||
313 | struct type **sqh_last; /* addr of last next element */ \ | ||
314 | } | ||
315 | |||
316 | #define SIMPLEQ_HEAD_INITIALIZER(head) \ | ||
317 | { NULL, &(head).sqh_first } | ||
318 | |||
319 | #define SIMPLEQ_ENTRY(type) \ | ||
320 | struct { \ | ||
321 | struct type *sqe_next; /* next element */ \ | ||
322 | } | ||
323 | |||
324 | /* | ||
325 | * Simple queue access methods. | ||
326 | */ | ||
327 | #define SIMPLEQ_FIRST(head) ((head)->sqh_first) | ||
328 | #define SIMPLEQ_END(head) NULL | ||
329 | #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) | ||
330 | #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) | ||
331 | |||
332 | #define SIMPLEQ_FOREACH(var, head, field) \ | ||
333 | for((var) = SIMPLEQ_FIRST(head); \ | ||
334 | (var) != SIMPLEQ_END(head); \ | ||
335 | (var) = SIMPLEQ_NEXT(var, field)) | ||
336 | |||
337 | /* | ||
338 | * Simple queue functions. | ||
339 | */ | ||
340 | #define SIMPLEQ_INIT(head) do { \ | ||
341 | (head)->sqh_first = NULL; \ | ||
342 | (head)->sqh_last = &(head)->sqh_first; \ | ||
343 | } while (0) | ||
344 | |||
345 | #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ | ||
346 | if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ | ||
347 | (head)->sqh_last = &(elm)->field.sqe_next; \ | ||
348 | (head)->sqh_first = (elm); \ | ||
349 | } while (0) | ||
350 | |||
351 | #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ | ||
352 | (elm)->field.sqe_next = NULL; \ | ||
353 | *(head)->sqh_last = (elm); \ | ||
354 | (head)->sqh_last = &(elm)->field.sqe_next; \ | ||
355 | } while (0) | ||
356 | |||
357 | #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ | ||
358 | if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ | ||
359 | (head)->sqh_last = &(elm)->field.sqe_next; \ | ||
360 | (listelm)->field.sqe_next = (elm); \ | ||
361 | } while (0) | ||
362 | |||
363 | #define SIMPLEQ_REMOVE_HEAD(head, elm, field) do { \ | ||
364 | if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) \ | ||
365 | (head)->sqh_last = &(head)->sqh_first; \ | ||
366 | } while (0) | ||
367 | |||
368 | /* | ||
369 | * Tail queue definitions. | ||
370 | */ | ||
371 | #define TAILQ_HEAD(name, type) \ | ||
372 | struct name { \ | ||
373 | struct type *tqh_first; /* first element */ \ | ||
374 | struct type **tqh_last; /* addr of last next element */ \ | ||
375 | } | ||
376 | |||
377 | #define TAILQ_HEAD_INITIALIZER(head) \ | ||
378 | { NULL, &(head).tqh_first } | ||
379 | |||
380 | #define TAILQ_ENTRY(type) \ | ||
381 | struct { \ | ||
382 | struct type *tqe_next; /* next element */ \ | ||
383 | struct type **tqe_prev; /* address of previous next element */ \ | ||
384 | } | ||
385 | |||
386 | /* | ||
387 | * tail queue access methods | ||
388 | */ | ||
389 | #define TAILQ_FIRST(head) ((head)->tqh_first) | ||
390 | #define TAILQ_END(head) NULL | ||
391 | #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) | ||
392 | #define TAILQ_LAST(head, headname) \ | ||
393 | (*(((struct headname *)((head)->tqh_last))->tqh_last)) | ||
394 | /* XXX */ | ||
395 | #define TAILQ_PREV(elm, headname, field) \ | ||
396 | (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) | ||
397 | #define TAILQ_EMPTY(head) \ | ||
398 | (TAILQ_FIRST(head) == TAILQ_END(head)) | ||
399 | |||
400 | #define TAILQ_FOREACH(var, head, field) \ | ||
401 | for((var) = TAILQ_FIRST(head); \ | ||
402 | (var) != TAILQ_END(head); \ | ||
403 | (var) = TAILQ_NEXT(var, field)) | ||
404 | |||
405 | #define TAILQ_FOREACH_REVERSE(var, head, field, headname) \ | ||
406 | for((var) = TAILQ_LAST(head, headname); \ | ||
407 | (var) != TAILQ_END(head); \ | ||
408 | (var) = TAILQ_PREV(var, headname, field)) | ||
409 | |||
410 | /* | ||
411 | * Tail queue functions. | ||
412 | */ | ||
413 | #define TAILQ_INIT(head) do { \ | ||
414 | (head)->tqh_first = NULL; \ | ||
415 | (head)->tqh_last = &(head)->tqh_first; \ | ||
416 | } while (0) | ||
417 | |||
418 | #define TAILQ_INSERT_HEAD(head, elm, field) do { \ | ||
419 | if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ | ||
420 | (head)->tqh_first->field.tqe_prev = \ | ||
421 | &(elm)->field.tqe_next; \ | ||
422 | else \ | ||
423 | (head)->tqh_last = &(elm)->field.tqe_next; \ | ||
424 | (head)->tqh_first = (elm); \ | ||
425 | (elm)->field.tqe_prev = &(head)->tqh_first; \ | ||
426 | } while (0) | ||
427 | |||
428 | #define TAILQ_INSERT_TAIL(head, elm, field) do { \ | ||
429 | (elm)->field.tqe_next = NULL; \ | ||
430 | (elm)->field.tqe_prev = (head)->tqh_last; \ | ||
431 | *(head)->tqh_last = (elm); \ | ||
432 | (head)->tqh_last = &(elm)->field.tqe_next; \ | ||
433 | } while (0) | ||
434 | |||
435 | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ | ||
436 | if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ | ||
437 | (elm)->field.tqe_next->field.tqe_prev = \ | ||
438 | &(elm)->field.tqe_next; \ | ||
439 | else \ | ||
440 | (head)->tqh_last = &(elm)->field.tqe_next; \ | ||
441 | (listelm)->field.tqe_next = (elm); \ | ||
442 | (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ | ||
443 | } while (0) | ||
444 | |||
445 | #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ | ||
446 | (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ | ||
447 | (elm)->field.tqe_next = (listelm); \ | ||
448 | *(listelm)->field.tqe_prev = (elm); \ | ||
449 | (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ | ||
450 | } while (0) | ||
451 | |||
452 | #define TAILQ_REMOVE(head, elm, field) do { \ | ||
453 | if (((elm)->field.tqe_next) != NULL) \ | ||
454 | (elm)->field.tqe_next->field.tqe_prev = \ | ||
455 | (elm)->field.tqe_prev; \ | ||
456 | else \ | ||
457 | (head)->tqh_last = (elm)->field.tqe_prev; \ | ||
458 | *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ | ||
459 | } while (0) | ||
460 | |||
461 | #define TAILQ_REPLACE(head, elm, elm2, field) do { \ | ||
462 | if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ | ||
463 | (elm2)->field.tqe_next->field.tqe_prev = \ | ||
464 | &(elm2)->field.tqe_next; \ | ||
465 | else \ | ||
466 | (head)->tqh_last = &(elm2)->field.tqe_next; \ | ||
467 | (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ | ||
468 | *(elm2)->field.tqe_prev = (elm2); \ | ||
469 | } while (0) | ||
470 | |||
471 | /* | ||
472 | * Circular queue definitions. | ||
473 | */ | ||
474 | #define CIRCLEQ_HEAD(name, type) \ | ||
475 | struct name { \ | ||
476 | struct type *cqh_first; /* first element */ \ | ||
477 | struct type *cqh_last; /* last element */ \ | ||
478 | } | ||
479 | |||
480 | #define CIRCLEQ_HEAD_INITIALIZER(head) \ | ||
481 | { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } | ||
482 | |||
483 | #define CIRCLEQ_ENTRY(type) \ | ||
484 | struct { \ | ||
485 | struct type *cqe_next; /* next element */ \ | ||
486 | struct type *cqe_prev; /* previous element */ \ | ||
487 | } | ||
488 | |||
489 | /* | ||
490 | * Circular queue access methods | ||
491 | */ | ||
492 | #define CIRCLEQ_FIRST(head) ((head)->cqh_first) | ||
493 | #define CIRCLEQ_LAST(head) ((head)->cqh_last) | ||
494 | #define CIRCLEQ_END(head) ((void *)(head)) | ||
495 | #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) | ||
496 | #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) | ||
497 | #define CIRCLEQ_EMPTY(head) \ | ||
498 | (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) | ||
499 | |||
500 | #define CIRCLEQ_FOREACH(var, head, field) \ | ||
501 | for((var) = CIRCLEQ_FIRST(head); \ | ||
502 | (var) != CIRCLEQ_END(head); \ | ||
503 | (var) = CIRCLEQ_NEXT(var, field)) | ||
504 | |||
505 | #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ | ||
506 | for((var) = CIRCLEQ_LAST(head); \ | ||
507 | (var) != CIRCLEQ_END(head); \ | ||
508 | (var) = CIRCLEQ_PREV(var, field)) | ||
509 | |||
510 | /* | ||
511 | * Circular queue functions. | ||
512 | */ | ||
513 | #define CIRCLEQ_INIT(head) do { \ | ||
514 | (head)->cqh_first = CIRCLEQ_END(head); \ | ||
515 | (head)->cqh_last = CIRCLEQ_END(head); \ | ||
516 | } while (0) | ||
517 | |||
518 | #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ | ||
519 | (elm)->field.cqe_next = (listelm)->field.cqe_next; \ | ||
520 | (elm)->field.cqe_prev = (listelm); \ | ||
521 | if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ | ||
522 | (head)->cqh_last = (elm); \ | ||
523 | else \ | ||
524 | (listelm)->field.cqe_next->field.cqe_prev = (elm); \ | ||
525 | (listelm)->field.cqe_next = (elm); \ | ||
526 | } while (0) | ||
527 | |||
528 | #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ | ||
529 | (elm)->field.cqe_next = (listelm); \ | ||
530 | (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ | ||
531 | if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ | ||
532 | (head)->cqh_first = (elm); \ | ||
533 | else \ | ||
534 | (listelm)->field.cqe_prev->field.cqe_next = (elm); \ | ||
535 | (listelm)->field.cqe_prev = (elm); \ | ||
536 | } while (0) | ||
537 | |||
538 | #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ | ||
539 | (elm)->field.cqe_next = (head)->cqh_first; \ | ||
540 | (elm)->field.cqe_prev = CIRCLEQ_END(head); \ | ||
541 | if ((head)->cqh_last == CIRCLEQ_END(head)) \ | ||
542 | (head)->cqh_last = (elm); \ | ||
543 | else \ | ||
544 | (head)->cqh_first->field.cqe_prev = (elm); \ | ||
545 | (head)->cqh_first = (elm); \ | ||
546 | } while (0) | ||
547 | |||
548 | #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ | ||
549 | (elm)->field.cqe_next = CIRCLEQ_END(head); \ | ||
550 | (elm)->field.cqe_prev = (head)->cqh_last; \ | ||
551 | if ((head)->cqh_first == CIRCLEQ_END(head)) \ | ||
552 | (head)->cqh_first = (elm); \ | ||
553 | else \ | ||
554 | (head)->cqh_last->field.cqe_next = (elm); \ | ||
555 | (head)->cqh_last = (elm); \ | ||
556 | } while (0) | ||
557 | |||
558 | #define CIRCLEQ_REMOVE(head, elm, field) do { \ | ||
559 | if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ | ||
560 | (head)->cqh_last = (elm)->field.cqe_prev; \ | ||
561 | else \ | ||
562 | (elm)->field.cqe_next->field.cqe_prev = \ | ||
563 | (elm)->field.cqe_prev; \ | ||
564 | if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ | ||
565 | (head)->cqh_first = (elm)->field.cqe_next; \ | ||
566 | else \ | ||
567 | (elm)->field.cqe_prev->field.cqe_next = \ | ||
568 | (elm)->field.cqe_next; \ | ||
569 | } while (0) | ||
570 | |||
571 | #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ | ||
572 | if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ | ||
573 | CIRCLEQ_END(head)) \ | ||
574 | (head).cqh_last = (elm2); \ | ||
575 | else \ | ||
576 | (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ | ||
577 | if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ | ||
578 | CIRCLEQ_END(head)) \ | ||
579 | (head).cqh_first = (elm2); \ | ||
580 | else \ | ||
581 | (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ | ||
582 | } while (0) | ||
583 | |||
584 | #endif /* !_FAKE_QUEUE_H_ */ | ||
diff --git a/openbsd-compat/fake-socket.h b/openbsd-compat/fake-socket.h new file mode 100644 index 000000000..f364797fa --- /dev/null +++ b/openbsd-compat/fake-socket.h | |||
@@ -0,0 +1,47 @@ | |||
1 | /* $Id: fake-socket.h,v 1.3 2002/04/12 03:35:40 tim Exp $ */ | ||
2 | |||
3 | #ifndef _FAKE_SOCKET_H | ||
4 | #define _FAKE_SOCKET_H | ||
5 | |||
6 | #include "includes.h" | ||
7 | #include "sys/types.h" | ||
8 | |||
9 | #ifndef HAVE_STRUCT_SOCKADDR_STORAGE | ||
10 | # define _SS_MAXSIZE 128 /* Implementation specific max size */ | ||
11 | # define _SS_PADSIZE (_SS_MAXSIZE - sizeof (struct sockaddr)) | ||
12 | |||
13 | struct sockaddr_storage { | ||
14 | struct sockaddr ss_sa; | ||
15 | char __ss_pad2[_SS_PADSIZE]; | ||
16 | }; | ||
17 | # define ss_family ss_sa.sa_family | ||
18 | #endif /* !HAVE_STRUCT_SOCKADDR_STORAGE */ | ||
19 | |||
20 | #ifndef IN6_IS_ADDR_LOOPBACK | ||
21 | # define IN6_IS_ADDR_LOOPBACK(a) \ | ||
22 | (((u_int32_t *) (a))[0] == 0 && ((u_int32_t *) (a))[1] == 0 && \ | ||
23 | ((u_int32_t *) (a))[2] == 0 && ((u_int32_t *) (a))[3] == htonl (1)) | ||
24 | #endif /* !IN6_IS_ADDR_LOOPBACK */ | ||
25 | |||
26 | #ifndef HAVE_STRUCT_IN6_ADDR | ||
27 | struct in6_addr { | ||
28 | u_int8_t s6_addr[16]; | ||
29 | }; | ||
30 | #endif /* !HAVE_STRUCT_IN6_ADDR */ | ||
31 | |||
32 | #ifndef HAVE_STRUCT_SOCKADDR_IN6 | ||
33 | struct sockaddr_in6 { | ||
34 | unsigned short sin6_family; | ||
35 | u_int16_t sin6_port; | ||
36 | u_int32_t sin6_flowinfo; | ||
37 | struct in6_addr sin6_addr; | ||
38 | }; | ||
39 | #endif /* !HAVE_STRUCT_SOCKADDR_IN6 */ | ||
40 | |||
41 | #ifndef AF_INET6 | ||
42 | /* Define it to something that should never appear */ | ||
43 | #define AF_INET6 AF_MAX | ||
44 | #endif | ||
45 | |||
46 | #endif /* !_FAKE_SOCKET_H */ | ||
47 | |||
diff --git a/openbsd-compat/getcwd.h b/openbsd-compat/getcwd.h new file mode 100644 index 000000000..1137b3ed5 --- /dev/null +++ b/openbsd-compat/getcwd.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: getcwd.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_GETCWD_H | ||
4 | #define _BSD_GETCWD_H | ||
5 | #include "config.h" | ||
6 | |||
7 | #if !defined(HAVE_GETCWD) | ||
8 | |||
9 | char *getcwd(char *pt, size_t size); | ||
10 | |||
11 | #endif /* !defined(HAVE_GETCWD) */ | ||
12 | #endif /* _BSD_GETCWD_H */ | ||
diff --git a/openbsd-compat/getgrouplist.h b/openbsd-compat/getgrouplist.h new file mode 100644 index 000000000..27a9703f2 --- /dev/null +++ b/openbsd-compat/getgrouplist.h | |||
@@ -0,0 +1,16 @@ | |||
1 | /* $Id: getgrouplist.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_GETGROUPLIST_H | ||
4 | #define _BSD_GETGROUPLIST_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_GETGROUPLIST | ||
9 | |||
10 | #include <grp.h> | ||
11 | |||
12 | int getgrouplist(const char *, gid_t, gid_t *, int *); | ||
13 | |||
14 | #endif | ||
15 | |||
16 | #endif | ||
diff --git a/openbsd-compat/getopt.h b/openbsd-compat/getopt.h new file mode 100644 index 000000000..9abdae8e9 --- /dev/null +++ b/openbsd-compat/getopt.h | |||
@@ -0,0 +1,14 @@ | |||
1 | /* $Id: getopt.h,v 1.4 2001/09/18 05:05:21 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSDGETOPT_H | ||
4 | #define _BSDGETOPT_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #if !defined(HAVE_GETOPT) || !defined(HAVE_GETOPT_OPTRESET) | ||
9 | |||
10 | int BSDgetopt(int argc, char * const *argv, const char *opts); | ||
11 | |||
12 | #endif | ||
13 | |||
14 | #endif /* _BSDGETOPT_H */ | ||
diff --git a/openbsd-compat/inet_aton.h b/openbsd-compat/inet_aton.h new file mode 100644 index 000000000..9b59cb908 --- /dev/null +++ b/openbsd-compat/inet_aton.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: inet_aton.h,v 1.4 2001/07/16 02:07:51 tim Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_INET_ATON_H | ||
4 | #define _BSD_INET_ATON_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_INET_ATON | ||
9 | int inet_aton(const char *cp, struct in_addr *addr); | ||
10 | #endif /* HAVE_INET_ATON */ | ||
11 | |||
12 | #endif /* _BSD_INET_ATON_H */ | ||
diff --git a/openbsd-compat/inet_ntoa.h b/openbsd-compat/inet_ntoa.h new file mode 100644 index 000000000..85bc3d6fe --- /dev/null +++ b/openbsd-compat/inet_ntoa.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: inet_ntoa.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_INET_NTOA_H | ||
4 | #define _BSD_INET_NTOA_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #if defined(BROKEN_INET_NTOA) || !defined(HAVE_INET_NTOA) | ||
9 | char *inet_ntoa(struct in_addr in); | ||
10 | #endif /* defined(BROKEN_INET_NTOA) || !defined(HAVE_INET_NTOA) */ | ||
11 | |||
12 | #endif /* _BSD_INET_NTOA_H */ | ||
diff --git a/openbsd-compat/inet_ntop.h b/openbsd-compat/inet_ntop.h new file mode 100644 index 000000000..c774df95c --- /dev/null +++ b/openbsd-compat/inet_ntop.h | |||
@@ -0,0 +1,13 @@ | |||
1 | /* $Id: inet_ntop.h,v 1.4 2001/08/09 00:56:53 mouring Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_INET_NTOP_H | ||
4 | #define _BSD_INET_NTOP_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_INET_NTOP | ||
9 | const char * | ||
10 | inet_ntop(int af, const void *src, char *dst, size_t size); | ||
11 | #endif /* !HAVE_INET_NTOP */ | ||
12 | |||
13 | #endif /* _BSD_INET_NTOP_H */ | ||
diff --git a/openbsd-compat/mktemp.h b/openbsd-compat/mktemp.h new file mode 100644 index 000000000..505ca6a1f --- /dev/null +++ b/openbsd-compat/mktemp.h | |||
@@ -0,0 +1,13 @@ | |||
1 | /* $Id: mktemp.h,v 1.3 2003/01/07 04:18:33 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_MKTEMP_H | ||
4 | #define _BSD_MKTEMP_H | ||
5 | |||
6 | #include "config.h" | ||
7 | #if !defined(HAVE_MKDTEMP) || defined(HAVE_STRICT_MKSTEMP) | ||
8 | int mkstemps(char *path, int slen); | ||
9 | int mkstemp(char *path); | ||
10 | char *mkdtemp(char *path); | ||
11 | #endif /* !defined(HAVE_MKDTEMP) || defined(HAVE_STRICT_MKSTEMP) */ | ||
12 | |||
13 | #endif /* _BSD_MKTEMP_H */ | ||
diff --git a/openbsd-compat/realpath.h b/openbsd-compat/realpath.h new file mode 100644 index 000000000..25e4075d7 --- /dev/null +++ b/openbsd-compat/realpath.h | |||
@@ -0,0 +1,13 @@ | |||
1 | /* $Id: realpath.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_REALPATH_H | ||
4 | #define _BSD_REALPATH_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #if !defined(HAVE_REALPATH) || defined(BROKEN_REALPATH) | ||
9 | |||
10 | char *realpath(const char *path, char *resolved); | ||
11 | |||
12 | #endif /* !defined(HAVE_REALPATH) || defined(BROKEN_REALPATH) */ | ||
13 | #endif /* _BSD_REALPATH_H */ | ||
diff --git a/openbsd-compat/rresvport.h b/openbsd-compat/rresvport.h new file mode 100644 index 000000000..a52e4515b --- /dev/null +++ b/openbsd-compat/rresvport.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: rresvport.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_RRESVPORT_H | ||
4 | #define _BSD_RRESVPORT_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_RRESVPORT_AF | ||
9 | int rresvport_af(int *alport, sa_family_t af); | ||
10 | #endif /* !HAVE_RRESVPORT_AF */ | ||
11 | |||
12 | #endif /* _BSD_RRESVPORT_H */ | ||
diff --git a/openbsd-compat/setenv.h b/openbsd-compat/setenv.h new file mode 100644 index 000000000..77256d802 --- /dev/null +++ b/openbsd-compat/setenv.h | |||
@@ -0,0 +1,14 @@ | |||
1 | /* $Id: setenv.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_SETENV_H | ||
4 | #define _BSD_SETENV_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_SETENV | ||
9 | |||
10 | int setenv(register const char *name, register const char *value, int rewrite); | ||
11 | |||
12 | #endif /* !HAVE_SETENV */ | ||
13 | |||
14 | #endif /* _BSD_SETENV_H */ | ||
diff --git a/openbsd-compat/setproctitle.h b/openbsd-compat/setproctitle.h new file mode 100644 index 000000000..48d26c6ea --- /dev/null +++ b/openbsd-compat/setproctitle.h | |||
@@ -0,0 +1,13 @@ | |||
1 | /* $Id: setproctitle.h,v 1.3 2003/01/09 22:53:13 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_SETPROCTITLE_H | ||
4 | #define _BSD_SETPROCTITLE_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_SETPROCTITLE | ||
9 | void setproctitle(const char *fmt, ...); | ||
10 | void compat_init_setproctitle(int argc, char *argv[]); | ||
11 | #endif | ||
12 | |||
13 | #endif /* _BSD_SETPROCTITLE_H */ | ||
diff --git a/openbsd-compat/strlcat.h b/openbsd-compat/strlcat.h new file mode 100644 index 000000000..753668563 --- /dev/null +++ b/openbsd-compat/strlcat.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: strlcat.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_STRLCAT_H | ||
4 | #define _BSD_STRLCAT_H | ||
5 | |||
6 | #include "config.h" | ||
7 | #ifndef HAVE_STRLCAT | ||
8 | #include <sys/types.h> | ||
9 | size_t strlcat(char *dst, const char *src, size_t siz); | ||
10 | #endif /* !HAVE_STRLCAT */ | ||
11 | |||
12 | #endif /* _BSD_STRLCAT_H */ | ||
diff --git a/openbsd-compat/strlcpy.h b/openbsd-compat/strlcpy.h new file mode 100644 index 000000000..3b137670d --- /dev/null +++ b/openbsd-compat/strlcpy.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: strlcpy.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_STRLCPY_H | ||
4 | #define _BSD_STRLCPY_H | ||
5 | |||
6 | #include "config.h" | ||
7 | #ifndef HAVE_STRLCPY | ||
8 | #include <sys/types.h> | ||
9 | size_t strlcpy(char *dst, const char *src, size_t siz); | ||
10 | #endif /* !HAVE_STRLCPY */ | ||
11 | |||
12 | #endif /* _BSD_STRLCPY_H */ | ||
diff --git a/openbsd-compat/strmode.h b/openbsd-compat/strmode.h new file mode 100644 index 000000000..64f7c8aae --- /dev/null +++ b/openbsd-compat/strmode.h | |||
@@ -0,0 +1,7 @@ | |||
1 | /* $Id: strmode.h,v 1.3 2001/06/09 02:22:17 mouring Exp $ */ | ||
2 | |||
3 | #ifndef HAVE_STRMODE | ||
4 | |||
5 | void strmode(register mode_t mode, register char *p); | ||
6 | |||
7 | #endif | ||
diff --git a/openbsd-compat/strsep.h b/openbsd-compat/strsep.h new file mode 100644 index 000000000..6ed810ac1 --- /dev/null +++ b/openbsd-compat/strsep.h | |||
@@ -0,0 +1,12 @@ | |||
1 | /* $Id: strsep.h,v 1.2 2001/02/09 01:55:36 djm Exp $ */ | ||
2 | |||
3 | #ifndef _BSD_STRSEP_H | ||
4 | #define _BSD_STRSEP_H | ||
5 | |||
6 | #include "config.h" | ||
7 | |||
8 | #ifndef HAVE_STRSEP | ||
9 | char *strsep(char **stringp, const char *delim); | ||
10 | #endif /* HAVE_STRSEP */ | ||
11 | |||
12 | #endif /* _BSD_STRSEP_H */ | ||
diff --git a/openbsd-compat/tree.h b/openbsd-compat/tree.h new file mode 100644 index 000000000..30b4a8561 --- /dev/null +++ b/openbsd-compat/tree.h | |||
@@ -0,0 +1,667 @@ | |||
1 | /* | ||
2 | * Copyright 2002 Niels Provos <provos@citi.umich.edu> | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * Redistribution and use in source and binary forms, with or without | ||
6 | * modification, are permitted provided that the following conditions | ||
7 | * are met: | ||
8 | * 1. Redistributions of source code must retain the above copyright | ||
9 | * notice, this list of conditions and the following disclaimer. | ||
10 | * 2. Redistributions in binary form must reproduce the above copyright | ||
11 | * notice, this list of conditions and the following disclaimer in the | ||
12 | * documentation and/or other materials provided with the distribution. | ||
13 | * | ||
14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | ||
15 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | ||
16 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | ||
17 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
18 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
19 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
20 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
21 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | ||
23 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
24 | */ | ||
25 | |||
26 | #ifndef _SYS_TREE_H_ | ||
27 | #define _SYS_TREE_H_ | ||
28 | |||
29 | /* | ||
30 | * This file defines data structures for different types of trees: | ||
31 | * splay trees and red-black trees. | ||
32 | * | ||
33 | * A splay tree is a self-organizing data structure. Every operation | ||
34 | * on the tree causes a splay to happen. The splay moves the requested | ||
35 | * node to the root of the tree and partly rebalances it. | ||
36 | * | ||
37 | * This has the benefit that request locality causes faster lookups as | ||
38 | * the requested nodes move to the top of the tree. On the other hand, | ||
39 | * every lookup causes memory writes. | ||
40 | * | ||
41 | * The Balance Theorem bounds the total access time for m operations | ||
42 | * and n inserts on an initially empty tree as O((m + n)lg n). The | ||
43 | * amortized cost for a sequence of m accesses to a splay tree is O(lg n); | ||
44 | * | ||
45 | * A red-black tree is a binary search tree with the node color as an | ||
46 | * extra attribute. It fulfills a set of conditions: | ||
47 | * - every search path from the root to a leaf consists of the | ||
48 | * same number of black nodes, | ||
49 | * - each red node (except for the root) has a black parent, | ||
50 | * - each leaf node is black. | ||
51 | * | ||
52 | * Every operation on a red-black tree is bounded as O(lg n). | ||
53 | * The maximum height of a red-black tree is 2lg (n+1). | ||
54 | */ | ||
55 | |||
56 | #define SPLAY_HEAD(name, type) \ | ||
57 | struct name { \ | ||
58 | struct type *sph_root; /* root of the tree */ \ | ||
59 | } | ||
60 | |||
61 | #define SPLAY_INITIALIZER(root) \ | ||
62 | { NULL } | ||
63 | |||
64 | #define SPLAY_INIT(root) do { \ | ||
65 | (root)->sph_root = NULL; \ | ||
66 | } while (0) | ||
67 | |||
68 | #define SPLAY_ENTRY(type) \ | ||
69 | struct { \ | ||
70 | struct type *spe_left; /* left element */ \ | ||
71 | struct type *spe_right; /* right element */ \ | ||
72 | } | ||
73 | |||
74 | #define SPLAY_LEFT(elm, field) (elm)->field.spe_left | ||
75 | #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right | ||
76 | #define SPLAY_ROOT(head) (head)->sph_root | ||
77 | #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) | ||
78 | |||
79 | /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ | ||
80 | #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ | ||
81 | SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ | ||
82 | SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | ||
83 | (head)->sph_root = tmp; \ | ||
84 | } while (0) | ||
85 | |||
86 | #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ | ||
87 | SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ | ||
88 | SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | ||
89 | (head)->sph_root = tmp; \ | ||
90 | } while (0) | ||
91 | |||
92 | #define SPLAY_LINKLEFT(head, tmp, field) do { \ | ||
93 | SPLAY_LEFT(tmp, field) = (head)->sph_root; \ | ||
94 | tmp = (head)->sph_root; \ | ||
95 | (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ | ||
96 | } while (0) | ||
97 | |||
98 | #define SPLAY_LINKRIGHT(head, tmp, field) do { \ | ||
99 | SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ | ||
100 | tmp = (head)->sph_root; \ | ||
101 | (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ | ||
102 | } while (0) | ||
103 | |||
104 | #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ | ||
105 | SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ | ||
106 | SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ | ||
107 | SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ | ||
108 | SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ | ||
109 | } while (0) | ||
110 | |||
111 | /* Generates prototypes and inline functions */ | ||
112 | |||
113 | #define SPLAY_PROTOTYPE(name, type, field, cmp) \ | ||
114 | void name##_SPLAY(struct name *, struct type *); \ | ||
115 | void name##_SPLAY_MINMAX(struct name *, int); \ | ||
116 | \ | ||
117 | static __inline void \ | ||
118 | name##_SPLAY_INSERT(struct name *head, struct type *elm) \ | ||
119 | { \ | ||
120 | if (SPLAY_EMPTY(head)) { \ | ||
121 | SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ | ||
122 | } else { \ | ||
123 | int __comp; \ | ||
124 | name##_SPLAY(head, elm); \ | ||
125 | __comp = (cmp)(elm, (head)->sph_root); \ | ||
126 | if(__comp < 0) { \ | ||
127 | SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ | ||
128 | SPLAY_RIGHT(elm, field) = (head)->sph_root; \ | ||
129 | SPLAY_LEFT((head)->sph_root, field) = NULL; \ | ||
130 | } else if (__comp > 0) { \ | ||
131 | SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ | ||
132 | SPLAY_LEFT(elm, field) = (head)->sph_root; \ | ||
133 | SPLAY_RIGHT((head)->sph_root, field) = NULL; \ | ||
134 | } else \ | ||
135 | return; \ | ||
136 | } \ | ||
137 | (head)->sph_root = (elm); \ | ||
138 | } \ | ||
139 | \ | ||
140 | static __inline void \ | ||
141 | name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ | ||
142 | { \ | ||
143 | struct type *__tmp; \ | ||
144 | if (SPLAY_EMPTY(head)) \ | ||
145 | return; \ | ||
146 | name##_SPLAY(head, elm); \ | ||
147 | if ((cmp)(elm, (head)->sph_root) == 0) { \ | ||
148 | if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ | ||
149 | (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ | ||
150 | } else { \ | ||
151 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | ||
152 | (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ | ||
153 | name##_SPLAY(head, elm); \ | ||
154 | SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ | ||
155 | } \ | ||
156 | } \ | ||
157 | } \ | ||
158 | \ | ||
159 | /* Finds the node with the same key as elm */ \ | ||
160 | static __inline struct type * \ | ||
161 | name##_SPLAY_FIND(struct name *head, struct type *elm) \ | ||
162 | { \ | ||
163 | if (SPLAY_EMPTY(head)) \ | ||
164 | return(NULL); \ | ||
165 | name##_SPLAY(head, elm); \ | ||
166 | if ((cmp)(elm, (head)->sph_root) == 0) \ | ||
167 | return (head->sph_root); \ | ||
168 | return (NULL); \ | ||
169 | } \ | ||
170 | \ | ||
171 | static __inline struct type * \ | ||
172 | name##_SPLAY_NEXT(struct name *head, struct type *elm) \ | ||
173 | { \ | ||
174 | name##_SPLAY(head, elm); \ | ||
175 | if (SPLAY_RIGHT(elm, field) != NULL) { \ | ||
176 | elm = SPLAY_RIGHT(elm, field); \ | ||
177 | while (SPLAY_LEFT(elm, field) != NULL) { \ | ||
178 | elm = SPLAY_LEFT(elm, field); \ | ||
179 | } \ | ||
180 | } else \ | ||
181 | elm = NULL; \ | ||
182 | return (elm); \ | ||
183 | } \ | ||
184 | \ | ||
185 | static __inline struct type * \ | ||
186 | name##_SPLAY_MIN_MAX(struct name *head, int val) \ | ||
187 | { \ | ||
188 | name##_SPLAY_MINMAX(head, val); \ | ||
189 | return (SPLAY_ROOT(head)); \ | ||
190 | } | ||
191 | |||
192 | /* Main splay operation. | ||
193 | * Moves node close to the key of elm to top | ||
194 | */ | ||
195 | #define SPLAY_GENERATE(name, type, field, cmp) \ | ||
196 | void name##_SPLAY(struct name *head, struct type *elm) \ | ||
197 | { \ | ||
198 | struct type __node, *__left, *__right, *__tmp; \ | ||
199 | int __comp; \ | ||
200 | \ | ||
201 | SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | ||
202 | __left = __right = &__node; \ | ||
203 | \ | ||
204 | while ((__comp = (cmp)(elm, (head)->sph_root))) { \ | ||
205 | if (__comp < 0) { \ | ||
206 | __tmp = SPLAY_LEFT((head)->sph_root, field); \ | ||
207 | if (__tmp == NULL) \ | ||
208 | break; \ | ||
209 | if ((cmp)(elm, __tmp) < 0){ \ | ||
210 | SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | ||
211 | if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | ||
212 | break; \ | ||
213 | } \ | ||
214 | SPLAY_LINKLEFT(head, __right, field); \ | ||
215 | } else if (__comp > 0) { \ | ||
216 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | ||
217 | if (__tmp == NULL) \ | ||
218 | break; \ | ||
219 | if ((cmp)(elm, __tmp) > 0){ \ | ||
220 | SPLAY_ROTATE_LEFT(head, __tmp, field); \ | ||
221 | if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | ||
222 | break; \ | ||
223 | } \ | ||
224 | SPLAY_LINKRIGHT(head, __left, field); \ | ||
225 | } \ | ||
226 | } \ | ||
227 | SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | ||
228 | } \ | ||
229 | \ | ||
230 | /* Splay with either the minimum or the maximum element \ | ||
231 | * Used to find minimum or maximum element in tree. \ | ||
232 | */ \ | ||
233 | void name##_SPLAY_MINMAX(struct name *head, int __comp) \ | ||
234 | { \ | ||
235 | struct type __node, *__left, *__right, *__tmp; \ | ||
236 | \ | ||
237 | SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ | ||
238 | __left = __right = &__node; \ | ||
239 | \ | ||
240 | while (1) { \ | ||
241 | if (__comp < 0) { \ | ||
242 | __tmp = SPLAY_LEFT((head)->sph_root, field); \ | ||
243 | if (__tmp == NULL) \ | ||
244 | break; \ | ||
245 | if (__comp < 0){ \ | ||
246 | SPLAY_ROTATE_RIGHT(head, __tmp, field); \ | ||
247 | if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ | ||
248 | break; \ | ||
249 | } \ | ||
250 | SPLAY_LINKLEFT(head, __right, field); \ | ||
251 | } else if (__comp > 0) { \ | ||
252 | __tmp = SPLAY_RIGHT((head)->sph_root, field); \ | ||
253 | if (__tmp == NULL) \ | ||
254 | break; \ | ||
255 | if (__comp > 0) { \ | ||
256 | SPLAY_ROTATE_LEFT(head, __tmp, field); \ | ||
257 | if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ | ||
258 | break; \ | ||
259 | } \ | ||
260 | SPLAY_LINKRIGHT(head, __left, field); \ | ||
261 | } \ | ||
262 | } \ | ||
263 | SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ | ||
264 | } | ||
265 | |||
266 | #define SPLAY_NEGINF -1 | ||
267 | #define SPLAY_INF 1 | ||
268 | |||
269 | #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) | ||
270 | #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) | ||
271 | #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) | ||
272 | #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) | ||
273 | #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ | ||
274 | : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) | ||
275 | #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ | ||
276 | : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) | ||
277 | |||
278 | #define SPLAY_FOREACH(x, name, head) \ | ||
279 | for ((x) = SPLAY_MIN(name, head); \ | ||
280 | (x) != NULL; \ | ||
281 | (x) = SPLAY_NEXT(name, head, x)) | ||
282 | |||
283 | /* Macros that define a red-back tree */ | ||
284 | #define RB_HEAD(name, type) \ | ||
285 | struct name { \ | ||
286 | struct type *rbh_root; /* root of the tree */ \ | ||
287 | } | ||
288 | |||
289 | #define RB_INITIALIZER(root) \ | ||
290 | { NULL } | ||
291 | |||
292 | #define RB_INIT(root) do { \ | ||
293 | (root)->rbh_root = NULL; \ | ||
294 | } while (0) | ||
295 | |||
296 | #define RB_BLACK 0 | ||
297 | #define RB_RED 1 | ||
298 | #define RB_ENTRY(type) \ | ||
299 | struct { \ | ||
300 | struct type *rbe_left; /* left element */ \ | ||
301 | struct type *rbe_right; /* right element */ \ | ||
302 | struct type *rbe_parent; /* parent element */ \ | ||
303 | int rbe_color; /* node color */ \ | ||
304 | } | ||
305 | |||
306 | #define RB_LEFT(elm, field) (elm)->field.rbe_left | ||
307 | #define RB_RIGHT(elm, field) (elm)->field.rbe_right | ||
308 | #define RB_PARENT(elm, field) (elm)->field.rbe_parent | ||
309 | #define RB_COLOR(elm, field) (elm)->field.rbe_color | ||
310 | #define RB_ROOT(head) (head)->rbh_root | ||
311 | #define RB_EMPTY(head) (RB_ROOT(head) == NULL) | ||
312 | |||
313 | #define RB_SET(elm, parent, field) do { \ | ||
314 | RB_PARENT(elm, field) = parent; \ | ||
315 | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | ||
316 | RB_COLOR(elm, field) = RB_RED; \ | ||
317 | } while (0) | ||
318 | |||
319 | #define RB_SET_BLACKRED(black, red, field) do { \ | ||
320 | RB_COLOR(black, field) = RB_BLACK; \ | ||
321 | RB_COLOR(red, field) = RB_RED; \ | ||
322 | } while (0) | ||
323 | |||
324 | #ifndef RB_AUGMENT | ||
325 | #define RB_AUGMENT(x) | ||
326 | #endif | ||
327 | |||
328 | #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | ||
329 | (tmp) = RB_RIGHT(elm, field); \ | ||
330 | if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ | ||
331 | RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ | ||
332 | } \ | ||
333 | RB_AUGMENT(elm); \ | ||
334 | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ | ||
335 | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | ||
336 | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | ||
337 | else \ | ||
338 | RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | ||
339 | RB_AUGMENT(RB_PARENT(elm, field)); \ | ||
340 | } else \ | ||
341 | (head)->rbh_root = (tmp); \ | ||
342 | RB_LEFT(tmp, field) = (elm); \ | ||
343 | RB_PARENT(elm, field) = (tmp); \ | ||
344 | RB_AUGMENT(tmp); \ | ||
345 | } while (0) | ||
346 | |||
347 | #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ | ||
348 | (tmp) = RB_LEFT(elm, field); \ | ||
349 | if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ | ||
350 | RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ | ||
351 | } \ | ||
352 | RB_AUGMENT(elm); \ | ||
353 | if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ | ||
354 | if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ | ||
355 | RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ | ||
356 | else \ | ||
357 | RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ | ||
358 | RB_AUGMENT(RB_PARENT(elm, field)); \ | ||
359 | } else \ | ||
360 | (head)->rbh_root = (tmp); \ | ||
361 | RB_RIGHT(tmp, field) = (elm); \ | ||
362 | RB_PARENT(elm, field) = (tmp); \ | ||
363 | RB_AUGMENT(tmp); \ | ||
364 | } while (0) | ||
365 | |||
366 | /* Generates prototypes and inline functions */ | ||
367 | #define RB_PROTOTYPE(name, type, field, cmp) \ | ||
368 | void name##_RB_INSERT_COLOR(struct name *, struct type *); \ | ||
369 | void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ | ||
370 | void name##_RB_REMOVE(struct name *, struct type *); \ | ||
371 | struct type *name##_RB_INSERT(struct name *, struct type *); \ | ||
372 | struct type *name##_RB_FIND(struct name *, struct type *); \ | ||
373 | struct type *name##_RB_NEXT(struct name *, struct type *); \ | ||
374 | struct type *name##_RB_MINMAX(struct name *, int); \ | ||
375 | \ | ||
376 | |||
377 | /* Main rb operation. | ||
378 | * Moves node close to the key of elm to top | ||
379 | */ | ||
380 | #define RB_GENERATE(name, type, field, cmp) \ | ||
381 | void \ | ||
382 | name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | ||
383 | { \ | ||
384 | struct type *parent, *gparent, *tmp; \ | ||
385 | while ((parent = RB_PARENT(elm, field)) && \ | ||
386 | RB_COLOR(parent, field) == RB_RED) { \ | ||
387 | gparent = RB_PARENT(parent, field); \ | ||
388 | if (parent == RB_LEFT(gparent, field)) { \ | ||
389 | tmp = RB_RIGHT(gparent, field); \ | ||
390 | if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | ||
391 | RB_COLOR(tmp, field) = RB_BLACK; \ | ||
392 | RB_SET_BLACKRED(parent, gparent, field);\ | ||
393 | elm = gparent; \ | ||
394 | continue; \ | ||
395 | } \ | ||
396 | if (RB_RIGHT(parent, field) == elm) { \ | ||
397 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | ||
398 | tmp = parent; \ | ||
399 | parent = elm; \ | ||
400 | elm = tmp; \ | ||
401 | } \ | ||
402 | RB_SET_BLACKRED(parent, gparent, field); \ | ||
403 | RB_ROTATE_RIGHT(head, gparent, tmp, field); \ | ||
404 | } else { \ | ||
405 | tmp = RB_LEFT(gparent, field); \ | ||
406 | if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ | ||
407 | RB_COLOR(tmp, field) = RB_BLACK; \ | ||
408 | RB_SET_BLACKRED(parent, gparent, field);\ | ||
409 | elm = gparent; \ | ||
410 | continue; \ | ||
411 | } \ | ||
412 | if (RB_LEFT(parent, field) == elm) { \ | ||
413 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | ||
414 | tmp = parent; \ | ||
415 | parent = elm; \ | ||
416 | elm = tmp; \ | ||
417 | } \ | ||
418 | RB_SET_BLACKRED(parent, gparent, field); \ | ||
419 | RB_ROTATE_LEFT(head, gparent, tmp, field); \ | ||
420 | } \ | ||
421 | } \ | ||
422 | RB_COLOR(head->rbh_root, field) = RB_BLACK; \ | ||
423 | } \ | ||
424 | \ | ||
425 | void \ | ||
426 | name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ | ||
427 | { \ | ||
428 | struct type *tmp; \ | ||
429 | while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ | ||
430 | elm != RB_ROOT(head)) { \ | ||
431 | if (RB_LEFT(parent, field) == elm) { \ | ||
432 | tmp = RB_RIGHT(parent, field); \ | ||
433 | if (RB_COLOR(tmp, field) == RB_RED) { \ | ||
434 | RB_SET_BLACKRED(tmp, parent, field); \ | ||
435 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | ||
436 | tmp = RB_RIGHT(parent, field); \ | ||
437 | } \ | ||
438 | if ((RB_LEFT(tmp, field) == NULL || \ | ||
439 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | ||
440 | (RB_RIGHT(tmp, field) == NULL || \ | ||
441 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | ||
442 | RB_COLOR(tmp, field) = RB_RED; \ | ||
443 | elm = parent; \ | ||
444 | parent = RB_PARENT(elm, field); \ | ||
445 | } else { \ | ||
446 | if (RB_RIGHT(tmp, field) == NULL || \ | ||
447 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ | ||
448 | struct type *oleft; \ | ||
449 | if ((oleft = RB_LEFT(tmp, field)))\ | ||
450 | RB_COLOR(oleft, field) = RB_BLACK;\ | ||
451 | RB_COLOR(tmp, field) = RB_RED; \ | ||
452 | RB_ROTATE_RIGHT(head, tmp, oleft, field);\ | ||
453 | tmp = RB_RIGHT(parent, field); \ | ||
454 | } \ | ||
455 | RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | ||
456 | RB_COLOR(parent, field) = RB_BLACK; \ | ||
457 | if (RB_RIGHT(tmp, field)) \ | ||
458 | RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ | ||
459 | RB_ROTATE_LEFT(head, parent, tmp, field);\ | ||
460 | elm = RB_ROOT(head); \ | ||
461 | break; \ | ||
462 | } \ | ||
463 | } else { \ | ||
464 | tmp = RB_LEFT(parent, field); \ | ||
465 | if (RB_COLOR(tmp, field) == RB_RED) { \ | ||
466 | RB_SET_BLACKRED(tmp, parent, field); \ | ||
467 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | ||
468 | tmp = RB_LEFT(parent, field); \ | ||
469 | } \ | ||
470 | if ((RB_LEFT(tmp, field) == NULL || \ | ||
471 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ | ||
472 | (RB_RIGHT(tmp, field) == NULL || \ | ||
473 | RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ | ||
474 | RB_COLOR(tmp, field) = RB_RED; \ | ||
475 | elm = parent; \ | ||
476 | parent = RB_PARENT(elm, field); \ | ||
477 | } else { \ | ||
478 | if (RB_LEFT(tmp, field) == NULL || \ | ||
479 | RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ | ||
480 | struct type *oright; \ | ||
481 | if ((oright = RB_RIGHT(tmp, field)))\ | ||
482 | RB_COLOR(oright, field) = RB_BLACK;\ | ||
483 | RB_COLOR(tmp, field) = RB_RED; \ | ||
484 | RB_ROTATE_LEFT(head, tmp, oright, field);\ | ||
485 | tmp = RB_LEFT(parent, field); \ | ||
486 | } \ | ||
487 | RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ | ||
488 | RB_COLOR(parent, field) = RB_BLACK; \ | ||
489 | if (RB_LEFT(tmp, field)) \ | ||
490 | RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ | ||
491 | RB_ROTATE_RIGHT(head, parent, tmp, field);\ | ||
492 | elm = RB_ROOT(head); \ | ||
493 | break; \ | ||
494 | } \ | ||
495 | } \ | ||
496 | } \ | ||
497 | if (elm) \ | ||
498 | RB_COLOR(elm, field) = RB_BLACK; \ | ||
499 | } \ | ||
500 | \ | ||
501 | void \ | ||
502 | name##_RB_REMOVE(struct name *head, struct type *elm) \ | ||
503 | { \ | ||
504 | struct type *child, *parent; \ | ||
505 | int color; \ | ||
506 | if (RB_LEFT(elm, field) == NULL) \ | ||
507 | child = RB_RIGHT(elm, field); \ | ||
508 | else if (RB_RIGHT(elm, field) == NULL) \ | ||
509 | child = RB_LEFT(elm, field); \ | ||
510 | else { \ | ||
511 | struct type *old = elm, *left; \ | ||
512 | elm = RB_RIGHT(elm, field); \ | ||
513 | while ((left = RB_LEFT(elm, field))) \ | ||
514 | elm = left; \ | ||
515 | child = RB_RIGHT(elm, field); \ | ||
516 | parent = RB_PARENT(elm, field); \ | ||
517 | color = RB_COLOR(elm, field); \ | ||
518 | if (child) \ | ||
519 | RB_PARENT(child, field) = parent; \ | ||
520 | if (parent) { \ | ||
521 | if (RB_LEFT(parent, field) == elm) \ | ||
522 | RB_LEFT(parent, field) = child; \ | ||
523 | else \ | ||
524 | RB_RIGHT(parent, field) = child; \ | ||
525 | RB_AUGMENT(parent); \ | ||
526 | } else \ | ||
527 | RB_ROOT(head) = child; \ | ||
528 | if (RB_PARENT(elm, field) == old) \ | ||
529 | parent = elm; \ | ||
530 | (elm)->field = (old)->field; \ | ||
531 | if (RB_PARENT(old, field)) { \ | ||
532 | if (RB_LEFT(RB_PARENT(old, field), field) == old)\ | ||
533 | RB_LEFT(RB_PARENT(old, field), field) = elm;\ | ||
534 | else \ | ||
535 | RB_RIGHT(RB_PARENT(old, field), field) = elm;\ | ||
536 | RB_AUGMENT(RB_PARENT(old, field)); \ | ||
537 | } else \ | ||
538 | RB_ROOT(head) = elm; \ | ||
539 | RB_PARENT(RB_LEFT(old, field), field) = elm; \ | ||
540 | if (RB_RIGHT(old, field)) \ | ||
541 | RB_PARENT(RB_RIGHT(old, field), field) = elm; \ | ||
542 | if (parent) { \ | ||
543 | left = parent; \ | ||
544 | do { \ | ||
545 | RB_AUGMENT(left); \ | ||
546 | } while ((left = RB_PARENT(left, field))); \ | ||
547 | } \ | ||
548 | goto color; \ | ||
549 | } \ | ||
550 | parent = RB_PARENT(elm, field); \ | ||
551 | color = RB_COLOR(elm, field); \ | ||
552 | if (child) \ | ||
553 | RB_PARENT(child, field) = parent; \ | ||
554 | if (parent) { \ | ||
555 | if (RB_LEFT(parent, field) == elm) \ | ||
556 | RB_LEFT(parent, field) = child; \ | ||
557 | else \ | ||
558 | RB_RIGHT(parent, field) = child; \ | ||
559 | RB_AUGMENT(parent); \ | ||
560 | } else \ | ||
561 | RB_ROOT(head) = child; \ | ||
562 | color: \ | ||
563 | if (color == RB_BLACK) \ | ||
564 | name##_RB_REMOVE_COLOR(head, parent, child); \ | ||
565 | } \ | ||
566 | \ | ||
567 | /* Inserts a node into the RB tree */ \ | ||
568 | struct type * \ | ||
569 | name##_RB_INSERT(struct name *head, struct type *elm) \ | ||
570 | { \ | ||
571 | struct type *tmp; \ | ||
572 | struct type *parent = NULL; \ | ||
573 | int comp = 0; \ | ||
574 | tmp = RB_ROOT(head); \ | ||
575 | while (tmp) { \ | ||
576 | parent = tmp; \ | ||
577 | comp = (cmp)(elm, parent); \ | ||
578 | if (comp < 0) \ | ||
579 | tmp = RB_LEFT(tmp, field); \ | ||
580 | else if (comp > 0) \ | ||
581 | tmp = RB_RIGHT(tmp, field); \ | ||
582 | else \ | ||
583 | return (tmp); \ | ||
584 | } \ | ||
585 | RB_SET(elm, parent, field); \ | ||
586 | if (parent != NULL) { \ | ||
587 | if (comp < 0) \ | ||
588 | RB_LEFT(parent, field) = elm; \ | ||
589 | else \ | ||
590 | RB_RIGHT(parent, field) = elm; \ | ||
591 | RB_AUGMENT(parent); \ | ||
592 | } else \ | ||
593 | RB_ROOT(head) = elm; \ | ||
594 | name##_RB_INSERT_COLOR(head, elm); \ | ||
595 | return (NULL); \ | ||
596 | } \ | ||
597 | \ | ||
598 | /* Finds the node with the same key as elm */ \ | ||
599 | struct type * \ | ||
600 | name##_RB_FIND(struct name *head, struct type *elm) \ | ||
601 | { \ | ||
602 | struct type *tmp = RB_ROOT(head); \ | ||
603 | int comp; \ | ||
604 | while (tmp) { \ | ||
605 | comp = cmp(elm, tmp); \ | ||
606 | if (comp < 0) \ | ||
607 | tmp = RB_LEFT(tmp, field); \ | ||
608 | else if (comp > 0) \ | ||
609 | tmp = RB_RIGHT(tmp, field); \ | ||
610 | else \ | ||
611 | return (tmp); \ | ||
612 | } \ | ||
613 | return (NULL); \ | ||
614 | } \ | ||
615 | \ | ||
616 | struct type * \ | ||
617 | name##_RB_NEXT(struct name *head, struct type *elm) \ | ||
618 | { \ | ||
619 | if (RB_RIGHT(elm, field)) { \ | ||
620 | elm = RB_RIGHT(elm, field); \ | ||
621 | while (RB_LEFT(elm, field)) \ | ||
622 | elm = RB_LEFT(elm, field); \ | ||
623 | } else { \ | ||
624 | if (RB_PARENT(elm, field) && \ | ||
625 | (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ | ||
626 | elm = RB_PARENT(elm, field); \ | ||
627 | else { \ | ||
628 | while (RB_PARENT(elm, field) && \ | ||
629 | (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ | ||
630 | elm = RB_PARENT(elm, field); \ | ||
631 | elm = RB_PARENT(elm, field); \ | ||
632 | } \ | ||
633 | } \ | ||
634 | return (elm); \ | ||
635 | } \ | ||
636 | \ | ||
637 | struct type * \ | ||
638 | name##_RB_MINMAX(struct name *head, int val) \ | ||
639 | { \ | ||
640 | struct type *tmp = RB_ROOT(head); \ | ||
641 | struct type *parent = NULL; \ | ||
642 | while (tmp) { \ | ||
643 | parent = tmp; \ | ||
644 | if (val < 0) \ | ||
645 | tmp = RB_LEFT(tmp, field); \ | ||
646 | else \ | ||
647 | tmp = RB_RIGHT(tmp, field); \ | ||
648 | } \ | ||
649 | return (parent); \ | ||
650 | } | ||
651 | |||
652 | #define RB_NEGINF -1 | ||
653 | #define RB_INF 1 | ||
654 | |||
655 | #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) | ||
656 | #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) | ||
657 | #define RB_FIND(name, x, y) name##_RB_FIND(x, y) | ||
658 | #define RB_NEXT(name, x, y) name##_RB_NEXT(x, y) | ||
659 | #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) | ||
660 | #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) | ||
661 | |||
662 | #define RB_FOREACH(x, name, head) \ | ||
663 | for ((x) = RB_MIN(name, head); \ | ||
664 | (x) != NULL; \ | ||
665 | (x) = name##_RB_NEXT(head, x)) | ||
666 | |||
667 | #endif /* _SYS_TREE_H_ */ | ||
diff --git a/openbsd-compat/xmmap.h b/openbsd-compat/xmmap.h new file mode 100644 index 000000000..c0fa04aca --- /dev/null +++ b/openbsd-compat/xmmap.h | |||
@@ -0,0 +1,23 @@ | |||
1 | /* | ||
2 | * Redistribution and use in source and binary forms, with or without | ||
3 | * modification, are permitted provided that the following conditions | ||
4 | * are met: | ||
5 | * 1. Redistributions of source code must retain the above copyright | ||
6 | * notice, this list of conditions and the following disclaimer. | ||
7 | * 2. Redistributions in binary form must reproduce the above copyright | ||
8 | * notice, this list of conditions and the following disclaimer in the | ||
9 | * documentation and/or other materials provided with the distribution. | ||
10 | * | ||
11 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | ||
12 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | ||
13 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | ||
14 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
15 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
16 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
17 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
18 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
19 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | ||
20 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
21 | */ | ||
22 | |||
23 | void *xmmap(size_t size); | ||