summaryrefslogtreecommitdiff
path: root/openbsd-compat
diff options
context:
space:
mode:
authorColin Watson <cjwatson@debian.org>2020-10-20 14:12:31 +0100
committerColin Watson <cjwatson@debian.org>2020-10-20 14:12:31 +0100
commite371906fbbbbc11b0dced8fd4e0d258eb489d7c1 (patch)
tree4d0d8d2afd52572deb7910e29ff5a334b2bcf702 /openbsd-compat
parente429009cde648a41479cd1b60ce972760a2bdabc (diff)
parent3728919292c05983372954d27426f7d966813139 (diff)
New upstream release (8.4p1)
Diffstat (limited to 'openbsd-compat')
-rw-r--r--openbsd-compat/bcrypt_pbkdf.c4
-rw-r--r--openbsd-compat/memmem.c216
-rw-r--r--openbsd-compat/port-net.c7
-rw-r--r--openbsd-compat/sys-queue.h375
4 files changed, 349 insertions, 253 deletions
diff --git a/openbsd-compat/bcrypt_pbkdf.c b/openbsd-compat/bcrypt_pbkdf.c
index 785234563..62728d38f 100644
--- a/openbsd-compat/bcrypt_pbkdf.c
+++ b/openbsd-compat/bcrypt_pbkdf.c
@@ -15,6 +15,8 @@
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */ 16 */
17 17
18/* OPENBSD ORIGINAL: lib/libutil/bcrypt_pbkdf.c */
19
18#include "includes.h" 20#include "includes.h"
19 21
20#ifndef HAVE_BCRYPT_PBKDF 22#ifndef HAVE_BCRYPT_PBKDF
@@ -91,7 +93,7 @@ bcrypt_hash(u_int8_t *sha2pass, u_int8_t *sha2salt, u_int8_t *out)
91 cdata[i] = Blowfish_stream2word(ciphertext, sizeof(ciphertext), 93 cdata[i] = Blowfish_stream2word(ciphertext, sizeof(ciphertext),
92 &j); 94 &j);
93 for (i = 0; i < 64; i++) 95 for (i = 0; i < 64; i++)
94 blf_enc(&state, cdata, sizeof(cdata) / sizeof(uint64_t)); 96 blf_enc(&state, cdata, sizeof(cdata) / (sizeof(uint64_t)));
95 97
96 /* copy out */ 98 /* copy out */
97 for (i = 0; i < BCRYPT_WORDS; i++) { 99 for (i = 0; i < BCRYPT_WORDS; i++) {
diff --git a/openbsd-compat/memmem.c b/openbsd-compat/memmem.c
index 3e5e6b5e6..ac1243eb0 100644
--- a/openbsd-compat/memmem.c
+++ b/openbsd-compat/memmem.c
@@ -1,30 +1,26 @@
1/* $OpenBSD: memmem.c,v 1.4 2015/08/31 02:53:57 guenther Exp $ */ 1/* $OpenBSD: memmem.c,v 1.5 2020/04/16 12:39:28 claudio Exp $ */
2/*- 2
3 * Copyright (c) 2005 Pascal Gloor <pascal.gloor@spale.com> 3/*
4 * Copyright (c) 2005-2020 Rich Felker, et al.
4 * 5 *
5 * Redistribution and use in source and binary forms, with or without 6 * Permission is hereby granted, free of charge, to any person obtaining
6 * modification, are permitted provided that the following conditions 7 * a copy of this software and associated documentation files (the
7 * are met: 8 * "Software"), to deal in the Software without restriction, including
8 * 1. Redistributions of source code must retain the above copyright 9 * without limitation the rights to use, copy, modify, merge, publish,
9 * notice, this list of conditions and the following disclaimer. 10 * distribute, sublicense, and/or sell copies of the Software, and to
10 * 2. Redistributions in binary form must reproduce the above copyright 11 * permit persons to whom the Software is furnished to do so, subject to
11 * notice, this list of conditions and the following disclaimer in the 12 * the following conditions:
12 * documentation and/or other materials provided with the distribution.
13 * 3. The name of the author may not be used to endorse or promote
14 * products derived from this software without specific prior written
15 * permission.
16 * 13 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 14 * The above copyright notice and this permission notice shall be
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * included in all copies or substantial portions of the Software.
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16 *
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 20 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 21 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 22 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 23 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 * SUCH DAMAGE.
28 */ 24 */
29 25
30#include "includes.h" 26#include "includes.h"
@@ -32,38 +28,164 @@
32#ifndef HAVE_MEMMEM 28#ifndef HAVE_MEMMEM
33 29
34#include <string.h> 30#include <string.h>
31#ifdef HAVE_STDINT_H
32#include <stdint.h>
33#endif
34
35static char *
36twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
37{
38 uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1];
39 for (h+=2, k-=2; k; k--, hw = hw<<8 | *h++)
40 if (hw == nw) return (char *)h-2;
41 return hw == nw ? (char *)h-2 : 0;
42}
43
44static char *
45threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
46{
47 uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8;
48 uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8;
49 for (h+=3, k-=3; k; k--, hw = (hw|*h++)<<8)
50 if (hw == nw) return (char *)h-3;
51 return hw == nw ? (char *)h-3 : 0;
52}
53
54static char *
55fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
56{
57 uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3];
58 uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3];
59 for (h+=4, k-=4; k; k--, hw = hw<<8 | *h++)
60 if (hw == nw) return (char *)h-4;
61 return hw == nw ? (char *)h-4 : 0;
62}
63
64#define MAX(a,b) ((a)>(b)?(a):(b))
65#define MIN(a,b) ((a)<(b)?(a):(b))
66
67#define BITOP(a,b,op) \
68 ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a))))
35 69
36/* 70/*
37 * Find the first occurrence of the byte string s in byte string l. 71 * Maxime Crochemore and Dominique Perrin, Two-way string-matching,
72 * Journal of the ACM, 38(3):651-675, July 1991.
38 */ 73 */
39 74static char *
40void * 75twoway_memmem(const unsigned char *h, const unsigned char *z,
41memmem(const void *l, size_t l_len, const void *s, size_t s_len) 76 const unsigned char *n, size_t l)
42{ 77{
43 const char *cur, *last; 78 size_t i, ip, jp, k, p, ms, p0, mem, mem0;
44 const char *cl = l; 79 size_t byteset[32 / sizeof(size_t)] = { 0 };
45 const char *cs = s; 80 size_t shift[256];
81
82 /* Computing length of needle and fill shift table */
83 for (i=0; i<l; i++)
84 BITOP(byteset, n[i], |=), shift[n[i]] = i+1;
85
86 /* Compute maximal suffix */
87 ip = -1; jp = 0; k = p = 1;
88 while (jp+k<l) {
89 if (n[ip+k] == n[jp+k]) {
90 if (k == p) {
91 jp += p;
92 k = 1;
93 } else k++;
94 } else if (n[ip+k] > n[jp+k]) {
95 jp += k;
96 k = 1;
97 p = jp - ip;
98 } else {
99 ip = jp++;
100 k = p = 1;
101 }
102 }
103 ms = ip;
104 p0 = p;
105
106 /* And with the opposite comparison */
107 ip = -1; jp = 0; k = p = 1;
108 while (jp+k<l) {
109 if (n[ip+k] == n[jp+k]) {
110 if (k == p) {
111 jp += p;
112 k = 1;
113 } else k++;
114 } else if (n[ip+k] < n[jp+k]) {
115 jp += k;
116 k = 1;
117 p = jp - ip;
118 } else {
119 ip = jp++;
120 k = p = 1;
121 }
122 }
123 if (ip+1 > ms+1) ms = ip;
124 else p = p0;
46 125
47 /* a zero length needle should just return the haystack */ 126 /* Periodic needle? */
48 if (s_len == 0) 127 if (memcmp(n, n+p, ms+1)) {
49 return (void *)cl; 128 mem0 = 0;
129 p = MAX(ms, l-ms-1) + 1;
130 } else mem0 = l-p;
131 mem = 0;
50 132
51 /* "s" must be smaller or equal to "l" */ 133 /* Search loop */
52 if (l_len < s_len) 134 for (;;) {
53 return NULL; 135 /* If remainder of haystack is shorter than needle, done */
136 if (z-h < l) return 0;
137
138 /* Check last byte first; advance by shift on mismatch */
139 if (BITOP(byteset, h[l-1], &)) {
140 k = l-shift[h[l-1]];
141 if (k) {
142 if (k < mem) k = mem;
143 h += k;
144 mem = 0;
145 continue;
146 }
147 } else {
148 h += l;
149 mem = 0;
150 continue;
151 }
152
153 /* Compare right half */
154 for (k=MAX(ms+1,mem); k<l && n[k] == h[k]; k++);
155 if (k < l) {
156 h += k-ms;
157 mem = 0;
158 continue;
159 }
160 /* Compare left half */
161 for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--);
162 if (k <= mem) return (char *)h;
163 h += p;
164 mem = mem0;
165 }
166}
167
168void *
169memmem(const void *h0, size_t k, const void *n0, size_t l)
170{
171 const unsigned char *h = h0, *n = n0;
54 172
55 /* special case where s_len == 1 */ 173 /* Return immediately on empty needle */
56 if (s_len == 1) 174 if (!l) return (void *)h;
57 return memchr(l, *cs, l_len);
58 175
59 /* the last position where its possible to find "s" in "l" */ 176 /* Return immediately when needle is longer than haystack */
60 last = cl + l_len - s_len; 177 if (k<l) return 0;
61 178
62 for (cur = cl; cur <= last; cur++) 179 /* Use faster algorithms for short needles */
63 if (cur[0] == cs[0] && memcmp(cur, cs, s_len) == 0) 180 h = memchr(h0, *n, k);
64 return (void *)cur; 181 if (!h || l==1) return (void *)h;
182 k -= h - (const unsigned char *)h0;
183 if (k<l) return 0;
184 if (l==2) return twobyte_memmem(h, k, n);
185 if (l==3) return threebyte_memmem(h, k, n);
186 if (l==4) return fourbyte_memmem(h, k, n);
65 187
66 return NULL; 188 return twoway_memmem(h, h+k, n, l);
67} 189}
68DEF_WEAK(memmem); 190DEF_WEAK(memmem);
69#endif /* HAVE_MEMMEM */ 191#endif /* HAVE_MEMMEM */
diff --git a/openbsd-compat/port-net.c b/openbsd-compat/port-net.c
index 617bffceb..d7d8c6fa1 100644
--- a/openbsd-compat/port-net.c
+++ b/openbsd-compat/port-net.c
@@ -209,8 +209,11 @@ sys_tun_open(int tun, int mode, char **ifname)
209{ 209{
210 struct ifreq ifr; 210 struct ifreq ifr;
211 char name[100]; 211 char name[100];
212 int fd = -1, sock, flag; 212 int fd = -1, sock;
213 const char *tunbase = "tun"; 213 const char *tunbase = "tun";
214#if defined(TUNSIFHEAD) && !defined(SSH_TUN_PREPEND_AF)
215 int flag;
216#endif
214 217
215 if (ifname != NULL) 218 if (ifname != NULL)
216 *ifname = NULL; 219 *ifname = NULL;
@@ -247,8 +250,8 @@ sys_tun_open(int tun, int mode, char **ifname)
247 } 250 }
248 251
249 /* Turn on tunnel headers */ 252 /* Turn on tunnel headers */
250 flag = 1;
251#if defined(TUNSIFHEAD) && !defined(SSH_TUN_PREPEND_AF) 253#if defined(TUNSIFHEAD) && !defined(SSH_TUN_PREPEND_AF)
254 flag = 1;
252 if (mode != SSH_TUNMODE_ETHERNET && 255 if (mode != SSH_TUNMODE_ETHERNET &&
253 ioctl(fd, TUNSIFHEAD, &flag) == -1) { 256 ioctl(fd, TUNSIFHEAD, &flag) == -1) {
254 debug("%s: ioctl(%d, TUNSIFHEAD, 1): %s", __func__, fd, 257 debug("%s: ioctl(%d, TUNSIFHEAD, 1): %s", __func__, fd,
diff --git a/openbsd-compat/sys-queue.h b/openbsd-compat/sys-queue.h
index 5108f394c..816c15cd4 100644
--- a/openbsd-compat/sys-queue.h
+++ b/openbsd-compat/sys-queue.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */ 1/* $OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $ */
2/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ 2/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3 3
4/* 4/*
@@ -41,94 +41,97 @@
41 * Require for OS/X and other platforms that have old/broken/incomplete 41 * Require for OS/X and other platforms that have old/broken/incomplete
42 * <sys/queue.h>. 42 * <sys/queue.h>.
43 */ 43 */
44#undef SLIST_HEAD 44#undef CIRCLEQ_EMPTY
45#undef SLIST_HEAD_INITIALIZER 45#undef CIRCLEQ_END
46#undef SLIST_ENTRY 46#undef CIRCLEQ_ENTRY
47#undef SLIST_FOREACH_PREVPTR 47#undef CIRCLEQ_FIRST
48#undef SLIST_FOREACH_SAFE 48#undef CIRCLEQ_FOREACH
49#undef SLIST_FIRST 49#undef CIRCLEQ_FOREACH_REVERSE
50#undef SLIST_END 50#undef CIRCLEQ_HEAD
51#undef SLIST_EMPTY 51#undef CIRCLEQ_HEAD_INITIALIZER
52#undef SLIST_NEXT 52#undef CIRCLEQ_INIT
53#undef SLIST_FOREACH 53#undef CIRCLEQ_INSERT_AFTER
54#undef SLIST_INIT 54#undef CIRCLEQ_INSERT_BEFORE
55#undef SLIST_INSERT_AFTER 55#undef CIRCLEQ_INSERT_HEAD
56#undef SLIST_INSERT_HEAD 56#undef CIRCLEQ_INSERT_TAIL
57#undef SLIST_REMOVE_HEAD 57#undef CIRCLEQ_LAST
58#undef SLIST_REMOVE_AFTER 58#undef CIRCLEQ_NEXT
59#undef SLIST_REMOVE 59#undef CIRCLEQ_PREV
60#undef SLIST_REMOVE_NEXT 60#undef CIRCLEQ_REMOVE
61#undef LIST_HEAD 61#undef CIRCLEQ_REPLACE
62#undef LIST_HEAD_INITIALIZER 62#undef LIST_EMPTY
63#undef LIST_END
63#undef LIST_ENTRY 64#undef LIST_ENTRY
64#undef LIST_FIRST 65#undef LIST_FIRST
65#undef LIST_END
66#undef LIST_EMPTY
67#undef LIST_NEXT
68#undef LIST_FOREACH 66#undef LIST_FOREACH
69#undef LIST_FOREACH_SAFE 67#undef LIST_FOREACH_SAFE
68#undef LIST_HEAD
69#undef LIST_HEAD_INITIALIZER
70#undef LIST_INIT 70#undef LIST_INIT
71#undef LIST_INSERT_AFTER 71#undef LIST_INSERT_AFTER
72#undef LIST_INSERT_BEFORE 72#undef LIST_INSERT_BEFORE
73#undef LIST_INSERT_HEAD 73#undef LIST_INSERT_HEAD
74#undef LIST_NEXT
74#undef LIST_REMOVE 75#undef LIST_REMOVE
75#undef LIST_REPLACE 76#undef LIST_REPLACE
76#undef SIMPLEQ_HEAD 77#undef SIMPLEQ_CONCAT
77#undef SIMPLEQ_HEAD_INITIALIZER 78#undef SIMPLEQ_EMPTY
79#undef SIMPLEQ_END
78#undef SIMPLEQ_ENTRY 80#undef SIMPLEQ_ENTRY
79#undef SIMPLEQ_FIRST 81#undef SIMPLEQ_FIRST
80#undef SIMPLEQ_END
81#undef SIMPLEQ_EMPTY
82#undef SIMPLEQ_NEXT
83#undef SIMPLEQ_FOREACH 82#undef SIMPLEQ_FOREACH
84#undef SIMPLEQ_FOREACH_SAFE 83#undef SIMPLEQ_FOREACH_SAFE
84#undef SIMPLEQ_HEAD
85#undef SIMPLEQ_HEAD_INITIALIZER
85#undef SIMPLEQ_INIT 86#undef SIMPLEQ_INIT
87#undef SIMPLEQ_INSERT_AFTER
86#undef SIMPLEQ_INSERT_HEAD 88#undef SIMPLEQ_INSERT_HEAD
87#undef SIMPLEQ_INSERT_TAIL 89#undef SIMPLEQ_INSERT_TAIL
88#undef SIMPLEQ_INSERT_AFTER 90#undef SIMPLEQ_NEXT
91#undef SIMPLEQ_REMOVE_AFTER
89#undef SIMPLEQ_REMOVE_HEAD 92#undef SIMPLEQ_REMOVE_HEAD
90#undef TAILQ_HEAD 93#undef SLIST_EMPTY
91#undef TAILQ_HEAD_INITIALIZER 94#undef SLIST_END
95#undef SLIST_ENTRY
96#undef SLIST_FIRST
97#undef SLIST_FOREACH
98#undef SLIST_FOREACH_PREVPTR
99#undef SLIST_FOREACH_SAFE
100#undef SLIST_HEAD
101#undef SLIST_HEAD_INITIALIZER
102#undef SLIST_INIT
103#undef SLIST_INSERT_AFTER
104#undef SLIST_INSERT_HEAD
105#undef SLIST_NEXT
106#undef SLIST_REMOVE
107#undef SLIST_REMOVE_AFTER
108#undef SLIST_REMOVE_HEAD
109#undef SLIST_REMOVE_NEXT
110#undef TAILQ_CONCAT
111#undef TAILQ_EMPTY
112#undef TAILQ_END
92#undef TAILQ_ENTRY 113#undef TAILQ_ENTRY
93#undef TAILQ_FIRST 114#undef TAILQ_FIRST
94#undef TAILQ_END
95#undef TAILQ_NEXT
96#undef TAILQ_LAST
97#undef TAILQ_PREV
98#undef TAILQ_EMPTY
99#undef TAILQ_FOREACH 115#undef TAILQ_FOREACH
100#undef TAILQ_FOREACH_REVERSE 116#undef TAILQ_FOREACH_REVERSE
101#undef TAILQ_FOREACH_SAFE
102#undef TAILQ_FOREACH_REVERSE_SAFE 117#undef TAILQ_FOREACH_REVERSE_SAFE
118#undef TAILQ_FOREACH_SAFE
119#undef TAILQ_HEAD
120#undef TAILQ_HEAD_INITIALIZER
103#undef TAILQ_INIT 121#undef TAILQ_INIT
104#undef TAILQ_INSERT_HEAD
105#undef TAILQ_INSERT_TAIL
106#undef TAILQ_INSERT_AFTER 122#undef TAILQ_INSERT_AFTER
107#undef TAILQ_INSERT_BEFORE 123#undef TAILQ_INSERT_BEFORE
124#undef TAILQ_INSERT_HEAD
125#undef TAILQ_INSERT_TAIL
126#undef TAILQ_LAST
127#undef TAILQ_NEXT
128#undef TAILQ_PREV
108#undef TAILQ_REMOVE 129#undef TAILQ_REMOVE
109#undef TAILQ_REPLACE 130#undef TAILQ_REPLACE
110#undef CIRCLEQ_HEAD
111#undef CIRCLEQ_HEAD_INITIALIZER
112#undef CIRCLEQ_ENTRY
113#undef CIRCLEQ_FIRST
114#undef CIRCLEQ_LAST
115#undef CIRCLEQ_END
116#undef CIRCLEQ_NEXT
117#undef CIRCLEQ_PREV
118#undef CIRCLEQ_EMPTY
119#undef CIRCLEQ_FOREACH
120#undef CIRCLEQ_FOREACH_REVERSE
121#undef CIRCLEQ_INIT
122#undef CIRCLEQ_INSERT_AFTER
123#undef CIRCLEQ_INSERT_BEFORE
124#undef CIRCLEQ_INSERT_HEAD
125#undef CIRCLEQ_INSERT_TAIL
126#undef CIRCLEQ_REMOVE
127#undef CIRCLEQ_REPLACE
128 131
129/* 132/*
130 * This file defines five types of data structures: singly-linked lists, 133 * This file defines five types of data structures: singly-linked lists,
131 * lists, simple queues, tail queues, and circular queues. 134 * lists, simple queues, tail queues and XOR simple queues.
132 * 135 *
133 * 136 *
134 * A singly-linked list is headed by a single forward pointer. The elements 137 * A singly-linked list is headed by a single forward pointer. The elements
@@ -148,7 +151,7 @@
148 * or after an existing element or at the head of the list. A list 151 * or after an existing element or at the head of the list. A list
149 * may only be traversed in the forward direction. 152 * may only be traversed in the forward direction.
150 * 153 *
151 * A simple queue is headed by a pair of pointers, one the head of the 154 * A simple queue is headed by a pair of pointers, one to the head of the
152 * list and the other to the tail of the list. The elements are singly 155 * list and the other to the tail of the list. The elements are singly
153 * linked to save space, so elements can only be removed from the 156 * linked to save space, so elements can only be removed from the
154 * head of the list. New elements can be added to the list before or after 157 * head of the list. New elements can be added to the list before or after
@@ -162,19 +165,17 @@
162 * after an existing element, at the head of the list, or at the end of 165 * after an existing element, at the head of the list, or at the end of
163 * the list. A tail queue may be traversed in either direction. 166 * the list. A tail queue may be traversed in either direction.
164 * 167 *
165 * A circle queue is headed by a pair of pointers, one to the head of the 168 * An XOR simple queue is used in the same way as a regular simple queue.
166 * list and the other to the tail of the list. The elements are doubly 169 * The difference is that the head structure also includes a "cookie" that
167 * linked so that an arbitrary element can be removed without a need to 170 * is XOR'd with the queue pointer (first, last or next) to generate the
168 * traverse the list. New elements can be added to the list before or after 171 * real pointer value.
169 * an existing element, at the head of the list, or at the end of the list.
170 * A circle queue may be traversed in either direction, but has a more
171 * complex end of list detection.
172 * 172 *
173 * For details on the use of these macros, see the queue(3) manual page. 173 * For details on the use of these macros, see the queue(3) manual page.
174 */ 174 */
175 175
176#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) 176#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
177#define _Q_INVALIDATE(a) (a) = ((void *)-1) 177#define _Q_INVALID ((void *)-1)
178#define _Q_INVALIDATE(a) (a) = _Q_INVALID
178#else 179#else
179#define _Q_INVALIDATE(a) 180#define _Q_INVALIDATE(a)
180#endif 181#endif
@@ -186,15 +187,15 @@
186struct name { \ 187struct name { \
187 struct type *slh_first; /* first element */ \ 188 struct type *slh_first; /* first element */ \
188} 189}
189 190
190#define SLIST_HEAD_INITIALIZER(head) \ 191#define SLIST_HEAD_INITIALIZER(head) \
191 { NULL } 192 { NULL }
192 193
193#define SLIST_ENTRY(type) \ 194#define SLIST_ENTRY(type) \
194struct { \ 195struct { \
195 struct type *sle_next; /* next element */ \ 196 struct type *sle_next; /* next element */ \
196} 197}
197 198
198/* 199/*
199 * Singly-linked List access methods. 200 * Singly-linked List access methods.
200 */ 201 */
@@ -248,8 +249,8 @@ struct { \
248 curelm = curelm->field.sle_next; \ 249 curelm = curelm->field.sle_next; \
249 curelm->field.sle_next = \ 250 curelm->field.sle_next = \
250 curelm->field.sle_next->field.sle_next; \ 251 curelm->field.sle_next->field.sle_next; \
251 _Q_INVALIDATE((elm)->field.sle_next); \
252 } \ 252 } \
253 _Q_INVALIDATE((elm)->field.sle_next); \
253} while (0) 254} while (0)
254 255
255/* 256/*
@@ -270,7 +271,7 @@ struct { \
270} 271}
271 272
272/* 273/*
273 * List access methods 274 * List access methods.
274 */ 275 */
275#define LIST_FIRST(head) ((head)->lh_first) 276#define LIST_FIRST(head) ((head)->lh_first)
276#define LIST_END(head) NULL 277#define LIST_END(head) NULL
@@ -407,6 +408,94 @@ struct { \
407 (head)->sqh_last = &(elm)->field.sqe_next; \ 408 (head)->sqh_last = &(elm)->field.sqe_next; \
408} while (0) 409} while (0)
409 410
411#define SIMPLEQ_CONCAT(head1, head2) do { \
412 if (!SIMPLEQ_EMPTY((head2))) { \
413 *(head1)->sqh_last = (head2)->sqh_first; \
414 (head1)->sqh_last = (head2)->sqh_last; \
415 SIMPLEQ_INIT((head2)); \
416 } \
417} while (0)
418
419/*
420 * XOR Simple queue definitions.
421 */
422#define XSIMPLEQ_HEAD(name, type) \
423struct name { \
424 struct type *sqx_first; /* first element */ \
425 struct type **sqx_last; /* addr of last next element */ \
426 unsigned long sqx_cookie; \
427}
428
429#define XSIMPLEQ_ENTRY(type) \
430struct { \
431 struct type *sqx_next; /* next element */ \
432}
433
434/*
435 * XOR Simple queue access methods.
436 */
437#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
438 (unsigned long)(ptr)))
439#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
440#define XSIMPLEQ_END(head) NULL
441#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
442#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
443
444
445#define XSIMPLEQ_FOREACH(var, head, field) \
446 for ((var) = XSIMPLEQ_FIRST(head); \
447 (var) != XSIMPLEQ_END(head); \
448 (var) = XSIMPLEQ_NEXT(head, var, field))
449
450#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
451 for ((var) = XSIMPLEQ_FIRST(head); \
452 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
453 (var) = (tvar))
454
455/*
456 * XOR Simple queue functions.
457 */
458#define XSIMPLEQ_INIT(head) do { \
459 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
460 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
461 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
462} while (0)
463
464#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
465 if (((elm)->field.sqx_next = (head)->sqx_first) == \
466 XSIMPLEQ_XOR(head, NULL)) \
467 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
468 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
469} while (0)
470
471#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
472 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
473 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
474 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
475} while (0)
476
477#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
478 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
479 XSIMPLEQ_XOR(head, NULL)) \
480 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
481 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
482} while (0)
483
484#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
485 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
486 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
487 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
488} while (0)
489
490#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
491 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
492 (elm)->field.sqx_next)->field.sqx_next) \
493 == XSIMPLEQ_XOR(head, NULL)) \
494 (head)->sqx_last = \
495 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
496} while (0)
497
498
410/* 499/*
411 * Tail queue definitions. 500 * Tail queue definitions.
412 */ 501 */
@@ -425,8 +514,8 @@ struct { \
425 struct type **tqe_prev; /* address of previous next element */ \ 514 struct type **tqe_prev; /* address of previous next element */ \
426} 515}
427 516
428/* 517/*
429 * tail queue access methods 518 * Tail queue access methods.
430 */ 519 */
431#define TAILQ_FIRST(head) ((head)->tqh_first) 520#define TAILQ_FIRST(head) ((head)->tqh_first)
432#define TAILQ_END(head) NULL 521#define TAILQ_END(head) NULL
@@ -527,133 +616,13 @@ struct { \
527 _Q_INVALIDATE((elm)->field.tqe_next); \ 616 _Q_INVALIDATE((elm)->field.tqe_next); \
528} while (0) 617} while (0)
529 618
530/* 619#define TAILQ_CONCAT(head1, head2, field) do { \
531 * Circular queue definitions. 620 if (!TAILQ_EMPTY(head2)) { \
532 */ 621 *(head1)->tqh_last = (head2)->tqh_first; \
533#define CIRCLEQ_HEAD(name, type) \ 622 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
534struct name { \ 623 (head1)->tqh_last = (head2)->tqh_last; \
535 struct type *cqh_first; /* first element */ \ 624 TAILQ_INIT((head2)); \
536 struct type *cqh_last; /* last element */ \ 625 } \
537}
538
539#define CIRCLEQ_HEAD_INITIALIZER(head) \
540 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
541
542#define CIRCLEQ_ENTRY(type) \
543struct { \
544 struct type *cqe_next; /* next element */ \
545 struct type *cqe_prev; /* previous element */ \
546}
547
548/*
549 * Circular queue access methods
550 */
551#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
552#define CIRCLEQ_LAST(head) ((head)->cqh_last)
553#define CIRCLEQ_END(head) ((void *)(head))
554#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
555#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
556#define CIRCLEQ_EMPTY(head) \
557 (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
558
559#define CIRCLEQ_FOREACH(var, head, field) \
560 for((var) = CIRCLEQ_FIRST(head); \
561 (var) != CIRCLEQ_END(head); \
562 (var) = CIRCLEQ_NEXT(var, field))
563
564#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
565 for ((var) = CIRCLEQ_FIRST(head); \
566 (var) != CIRCLEQ_END(head) && \
567 ((tvar) = CIRCLEQ_NEXT(var, field), 1); \
568 (var) = (tvar))
569
570#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
571 for((var) = CIRCLEQ_LAST(head); \
572 (var) != CIRCLEQ_END(head); \
573 (var) = CIRCLEQ_PREV(var, field))
574
575#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
576 for ((var) = CIRCLEQ_LAST(head, headname); \
577 (var) != CIRCLEQ_END(head) && \
578 ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \
579 (var) = (tvar))
580
581/*
582 * Circular queue functions.
583 */
584#define CIRCLEQ_INIT(head) do { \
585 (head)->cqh_first = CIRCLEQ_END(head); \
586 (head)->cqh_last = CIRCLEQ_END(head); \
587} while (0)
588
589#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
590 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
591 (elm)->field.cqe_prev = (listelm); \
592 if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
593 (head)->cqh_last = (elm); \
594 else \
595 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
596 (listelm)->field.cqe_next = (elm); \
597} while (0)
598
599#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
600 (elm)->field.cqe_next = (listelm); \
601 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
602 if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
603 (head)->cqh_first = (elm); \
604 else \
605 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
606 (listelm)->field.cqe_prev = (elm); \
607} while (0)
608
609#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
610 (elm)->field.cqe_next = (head)->cqh_first; \
611 (elm)->field.cqe_prev = CIRCLEQ_END(head); \
612 if ((head)->cqh_last == CIRCLEQ_END(head)) \
613 (head)->cqh_last = (elm); \
614 else \
615 (head)->cqh_first->field.cqe_prev = (elm); \
616 (head)->cqh_first = (elm); \
617} while (0)
618
619#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
620 (elm)->field.cqe_next = CIRCLEQ_END(head); \
621 (elm)->field.cqe_prev = (head)->cqh_last; \
622 if ((head)->cqh_first == CIRCLEQ_END(head)) \
623 (head)->cqh_first = (elm); \
624 else \
625 (head)->cqh_last->field.cqe_next = (elm); \
626 (head)->cqh_last = (elm); \
627} while (0)
628
629#define CIRCLEQ_REMOVE(head, elm, field) do { \
630 if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
631 (head)->cqh_last = (elm)->field.cqe_prev; \
632 else \
633 (elm)->field.cqe_next->field.cqe_prev = \
634 (elm)->field.cqe_prev; \
635 if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
636 (head)->cqh_first = (elm)->field.cqe_next; \
637 else \
638 (elm)->field.cqe_prev->field.cqe_next = \
639 (elm)->field.cqe_next; \
640 _Q_INVALIDATE((elm)->field.cqe_prev); \
641 _Q_INVALIDATE((elm)->field.cqe_next); \
642} while (0)
643
644#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
645 if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
646 CIRCLEQ_END(head)) \
647 (head).cqh_last = (elm2); \
648 else \
649 (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
650 if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
651 CIRCLEQ_END(head)) \
652 (head).cqh_first = (elm2); \
653 else \
654 (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
655 _Q_INVALIDATE((elm)->field.cqe_prev); \
656 _Q_INVALIDATE((elm)->field.cqe_next); \
657} while (0) 626} while (0)
658 627
659#endif /* !_FAKE_QUEUE_H_ */ 628#endif /* !_SYS_QUEUE_H_ */
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-18 12:57:13 +0000