1 /*
2 * Copyright 2012-2015 Samy Al Bahra.
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 AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27 #include <assert.h>
28 #include <stdlib.h>
29 #include <stdio.h>
30 #include <pthread.h>
31 #include <ck_queue.h>
32 #include "../../common.h"
33
34 struct test {
35 int value;
36 CK_STAILQ_ENTRY(test) list_entry;
37 };
38 static CK_STAILQ_HEAD(test_list, test) head = CK_STAILQ_HEAD_INITIALIZER(head);
39
40 static int goal;
41
42 static void
test_foreach(void)43 test_foreach(void)
44 {
45 struct test *n, *next, *safe;
46 int i, s = 0, j = 0, k = 0;
47
48 for (i = goal; i != 0; i = goal) {
49 s = 0;
50
51 CK_STAILQ_FOREACH(n, &head, list_entry) {
52 j++;
53 if (s == 0)
54 s = n->value;
55 else
56 s = s - 1;
57
58 if (n->value != s) {
59 ck_error("\nExpected %d, but got %d.\n",
60 s, n->value);
61 }
62
63 next = CK_STAILQ_NEXT(n, list_entry);
64 if (next != NULL && next->value != s - 1) {
65 ck_error("\nExpected %d, but got %d.\n",
66 s, next->value);
67 }
68
69 i--;
70 }
71
72 if (i == 0)
73 break;
74
75 s = 0;
76 CK_STAILQ_FOREACH_SAFE(n, &head, list_entry, safe) {
77 k++;
78
79 if (s == 0)
80 s = n->value;
81 else
82 s = s - 1;
83
84 if (n->value != s) {
85 ck_error("\nExpected %d, but got %d.\n",
86 s, n->value);
87 }
88
89 next = CK_STAILQ_NEXT(n, list_entry);
90 if (next != NULL && next->value != s - 1) {
91 ck_error("\nExpected %d, but got %d.\n",
92 s, next->value);
93 }
94
95 i--;
96 }
97
98 if (i == 0 || CK_STAILQ_EMPTY(&head) == true)
99 break;
100 }
101
102 fprintf(stderr, "(%d, %d) ", j, k);
103 return;
104 }
105
106 static void *
execute(void * c)107 execute(void *c)
108 {
109
110 (void)c;
111 test_foreach();
112 return NULL;
113 }
114
115 int
main(int argc,char * argv[])116 main(int argc, char *argv[])
117 {
118 pthread_t *thread;
119 struct test *n, a, b;
120 struct test_list target;
121 int n_threads, i;
122
123 if (argc != 3) {
124 ck_error("Usage: %s <number of threads> <number of list entries>\n", argv[0]);
125 }
126
127 n_threads = atoi(argv[1]);
128 if (n_threads < 1) {
129 ck_error("ERROR: Number of threads must be >= 1.\n");
130 }
131
132 thread = malloc(sizeof(pthread_t) * n_threads);
133 assert(thread != NULL);
134
135 goal = atoi(argv[2]);
136 if (goal < 4) {
137 ck_error("ERROR: Number of entries must be >= 4.\n");
138 }
139
140 fprintf(stderr, "Beginning serial test...");
141 CK_STAILQ_INIT(&head);
142
143 for (i = 1; i <= goal; i++) {
144 n = malloc(sizeof *n);
145 assert(n != NULL);
146 n->value = i;
147 CK_STAILQ_INSERT_HEAD(&head, n, list_entry);
148 }
149
150 test_foreach();
151
152 for (i = 1; i <= goal; i++) {
153 n = CK_STAILQ_FIRST(&head);
154 CK_STAILQ_REMOVE(&head, n, test, list_entry);
155 free(n);
156 }
157
158 if (CK_STAILQ_EMPTY(&head) == false) {
159 ck_error("List is not empty after bulk removal.\n");
160 }
161
162 for (i = 1; i <= goal; i++) {
163 n = malloc(sizeof *n);
164 assert(n != NULL);
165 n->value = goal - i;
166 CK_STAILQ_INSERT_TAIL(&head, n, list_entry);
167 }
168
169 test_foreach();
170
171 for (i = 1; i <= goal; i++) {
172 n = CK_STAILQ_FIRST(&head);
173 CK_STAILQ_REMOVE(&head, n, test, list_entry);
174 free(n);
175 }
176
177 if (CK_STAILQ_EMPTY(&head) == false) {
178 ck_error("List is not empty after bulk removal.\n");
179 }
180
181 CK_STAILQ_INSERT_HEAD(&head, &a, list_entry);
182 CK_STAILQ_INSERT_HEAD(&head, &b, list_entry);
183 CK_STAILQ_REMOVE(&head, &a, test, list_entry);
184 if (CK_STAILQ_FIRST(&head) != &b)
185 ck_error("List is in invalid state.\n");
186 CK_STAILQ_REMOVE(&head, &b, test, list_entry);
187
188 if (CK_STAILQ_EMPTY(&head) == false) {
189 ck_error("List is not empty after bulk removal.\n");
190 }
191
192 CK_STAILQ_INSERT_HEAD(&head, &a, list_entry);
193 CK_STAILQ_INSERT_AFTER(&head, &a, &b, list_entry);
194
195 if (CK_STAILQ_NEXT(&b, list_entry) != NULL)
196 ck_error("Inserted item after last, it should not have no next.\n");
197
198 CK_STAILQ_INIT(&head);
199
200 CK_STAILQ_INSERT_HEAD(&head, &a, list_entry);
201 if (CK_STAILQ_NEXT(&a, list_entry) != NULL)
202 ck_error("Inserted item as last, but it contains next pointer.\n");
203
204 CK_STAILQ_INIT(&head);
205 fprintf(stderr, "done (success)\n");
206
207 fprintf(stderr, "Beginning parallel traversal...");
208
209 n = malloc(sizeof *n);
210 assert(n != NULL);
211 n->value = 1;
212 CK_STAILQ_INSERT_HEAD(&head, n, list_entry);
213
214 for (i = 0; i < n_threads; i++) {
215 int r = pthread_create(&thread[i], NULL, execute, NULL);
216 assert(r == 0);
217 }
218
219 for (i = 2; i <= goal; i++) {
220 volatile int j;
221
222 n = malloc(sizeof *n);
223 assert(n != NULL);
224 n->value = i;
225 CK_STAILQ_INSERT_HEAD(&head, n, list_entry);
226 for (j = 0; j <= 1000; j++);
227 }
228
229 for (i = 0; i < n_threads; i++)
230 pthread_join(thread[i], NULL);
231
232 for (i = 0; i < n_threads; i++) {
233 int r = pthread_create(&thread[i], NULL, execute, NULL);
234 assert(r == 0);
235 }
236
237 CK_STAILQ_MOVE(&target, &head, list_entry);
238
239 for (i = 1; i <= goal; i++) {
240 volatile int j;
241
242 if (CK_STAILQ_EMPTY(&target) == false) {
243 struct test *r = CK_STAILQ_FIRST(&target);
244 CK_STAILQ_REMOVE(&target, r, test, list_entry);
245 }
246
247 for (j = 0; j <= 1000; j++);
248 }
249
250 for (i = 0; i < n_threads; i++)
251 pthread_join(thread[i], NULL);
252
253 fprintf(stderr, "done (success)\n");
254 return (0);
255 }
256
257