list.c (10105B)
1 /** 2 * Copyright © 2011 Red Hat, Inc. 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24 /* Test relies on assert() */ 25 #undef NDEBUG 26 27 #ifdef HAVE_DIX_CONFIG_H 28 #include <dix-config.h> 29 #endif 30 31 #include <X11/Xlib.h> 32 #include <list.h> 33 #include <string.h> 34 #include <assert.h> 35 #include <stdlib.h> 36 37 #include "tests-common.h" 38 39 struct parent { 40 int a; 41 struct xorg_list children; 42 int b; 43 }; 44 45 struct child { 46 int foo; 47 int bar; 48 struct xorg_list node; 49 }; 50 51 static void 52 test_xorg_list_init(void) 53 { 54 struct parent parent, tmp; 55 56 memset(&parent, 0, sizeof(parent)); 57 parent.a = 0xa5a5a5; 58 parent.b = ~0xa5a5a5; 59 60 tmp = parent; 61 62 xorg_list_init(&parent.children); 63 64 /* test we haven't touched anything else. */ 65 assert(parent.a == tmp.a); 66 assert(parent.b == tmp.b); 67 68 assert(xorg_list_is_empty(&parent.children)); 69 } 70 71 static void 72 test_xorg_list_add(void) 73 { 74 struct parent parent = { 0 }; 75 struct child child[3]; 76 struct child *c; 77 78 xorg_list_init(&parent.children); 79 80 xorg_list_add(&child[0].node, &parent.children); 81 assert(!xorg_list_is_empty(&parent.children)); 82 83 c = xorg_list_first_entry(&parent.children, struct child, node); 84 85 assert(memcmp(c, &child[0], sizeof(struct child)) == 0); 86 87 /* note: xorg_list_add prepends */ 88 xorg_list_add(&child[1].node, &parent.children); 89 c = xorg_list_first_entry(&parent.children, struct child, node); 90 91 assert(memcmp(c, &child[1], sizeof(struct child)) == 0); 92 93 xorg_list_add(&child[2].node, &parent.children); 94 c = xorg_list_first_entry(&parent.children, struct child, node); 95 96 assert(memcmp(c, &child[2], sizeof(struct child)) == 0); 97 }; 98 99 static void 100 test_xorg_list_append(void) 101 { 102 struct parent parent = { 0 }; 103 struct child child[3]; 104 struct child *c; 105 int i; 106 107 xorg_list_init(&parent.children); 108 109 xorg_list_append(&child[0].node, &parent.children); 110 assert(!xorg_list_is_empty(&parent.children)); 111 112 c = xorg_list_first_entry(&parent.children, struct child, node); 113 114 assert(memcmp(c, &child[0], sizeof(struct child)) == 0); 115 c = xorg_list_last_entry(&parent.children, struct child, node); 116 117 assert(memcmp(c, &child[0], sizeof(struct child)) == 0); 118 119 xorg_list_append(&child[1].node, &parent.children); 120 c = xorg_list_first_entry(&parent.children, struct child, node); 121 122 assert(memcmp(c, &child[0], sizeof(struct child)) == 0); 123 c = xorg_list_last_entry(&parent.children, struct child, node); 124 125 assert(memcmp(c, &child[1], sizeof(struct child)) == 0); 126 127 xorg_list_append(&child[2].node, &parent.children); 128 c = xorg_list_first_entry(&parent.children, struct child, node); 129 130 assert(memcmp(c, &child[0], sizeof(struct child)) == 0); 131 c = xorg_list_last_entry(&parent.children, struct child, node); 132 133 assert(memcmp(c, &child[2], sizeof(struct child)) == 0); 134 135 i = 0; 136 xorg_list_for_each_entry(c, &parent.children, node) { 137 assert(memcmp(c, &child[i++], sizeof(struct child)) == 0); 138 } 139 }; 140 141 static void 142 test_xorg_list_del(void) 143 { 144 struct parent parent = { 0 }; 145 struct child child[2]; 146 struct child *c; 147 148 xorg_list_init(&parent.children); 149 150 xorg_list_add(&child[0].node, &parent.children); 151 assert(!xorg_list_is_empty(&parent.children)); 152 153 xorg_list_del(&parent.children); 154 assert(xorg_list_is_empty(&parent.children)); 155 156 xorg_list_add(&child[0].node, &parent.children); 157 xorg_list_del(&child[0].node); 158 assert(xorg_list_is_empty(&parent.children)); 159 160 xorg_list_add(&child[0].node, &parent.children); 161 xorg_list_add(&child[1].node, &parent.children); 162 163 c = xorg_list_first_entry(&parent.children, struct child, node); 164 165 assert(memcmp(c, &child[1], sizeof(struct child)) == 0); 166 167 /* delete first node */ 168 xorg_list_del(&child[1].node); 169 assert(!xorg_list_is_empty(&parent.children)); 170 assert(xorg_list_is_empty(&child[1].node)); 171 c = xorg_list_first_entry(&parent.children, struct child, node); 172 173 assert(memcmp(c, &child[0], sizeof(struct child)) == 0); 174 175 /* delete last node */ 176 xorg_list_add(&child[1].node, &parent.children); 177 xorg_list_del(&child[0].node); 178 c = xorg_list_first_entry(&parent.children, struct child, node); 179 180 assert(memcmp(c, &child[1], sizeof(struct child)) == 0); 181 182 /* delete list head */ 183 xorg_list_add(&child[0].node, &parent.children); 184 xorg_list_del(&parent.children); 185 assert(xorg_list_is_empty(&parent.children)); 186 assert(!xorg_list_is_empty(&child[0].node)); 187 assert(!xorg_list_is_empty(&child[1].node)); 188 } 189 190 static void 191 test_xorg_list_for_each(void) 192 { 193 struct parent parent = { 0 }; 194 struct child child[3]; 195 struct child *c; 196 int i = 0; 197 198 xorg_list_init(&parent.children); 199 200 xorg_list_add(&child[2].node, &parent.children); 201 xorg_list_add(&child[1].node, &parent.children); 202 xorg_list_add(&child[0].node, &parent.children); 203 204 xorg_list_for_each_entry(c, &parent.children, node) { 205 assert(memcmp(c, &child[i], sizeof(struct child)) == 0); 206 i++; 207 } 208 209 /* foreach on empty list */ 210 xorg_list_del(&parent.children); 211 assert(xorg_list_is_empty(&parent.children)); 212 213 xorg_list_for_each_entry(c, &parent.children, node) { 214 assert(0); /* we must not get here */ 215 } 216 } 217 218 struct foo { 219 char a; 220 struct foo *next; 221 char b; 222 }; 223 224 static void 225 test_nt_list_init(void) 226 { 227 struct foo foo; 228 229 foo.a = 10; 230 foo.b = 20; 231 nt_list_init(&foo, next); 232 233 assert(foo.a == 10); 234 assert(foo.b == 20); 235 assert(foo.next == NULL); 236 assert(nt_list_next(&foo, next) == NULL); 237 } 238 239 static void 240 test_nt_list_append(void) 241 { 242 int i; 243 struct foo *foo = calloc(10, sizeof(struct foo)); 244 struct foo *item; 245 246 for (item = foo, i = 1; i <= 10; i++, item++) { 247 item->a = i; 248 item->b = i * 2; 249 nt_list_init(item, next); 250 251 if (item != foo) 252 nt_list_append(item, foo, struct foo, next); 253 } 254 255 /* Test using nt_list_next */ 256 for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) { 257 assert(item->a == i); 258 assert(item->b == i * 2); 259 } 260 261 /* Test using nt_list_for_each_entry */ 262 i = 1; 263 nt_list_for_each_entry(item, foo, next) { 264 assert(item->a == i); 265 assert(item->b == i * 2); 266 i++; 267 } 268 assert(i == 11); 269 } 270 271 static void 272 test_nt_list_insert(void) 273 { 274 int i; 275 struct foo *foo = calloc(10, sizeof(struct foo)); 276 struct foo *item; 277 278 foo->a = 1; 279 foo->b = 2; 280 nt_list_init(foo, next); 281 282 for (item = &foo[1], i = 10; i > 1; i--, item++) { 283 item->a = i; 284 item->b = i * 2; 285 nt_list_init(item, next); 286 nt_list_insert(item, foo, struct foo, next); 287 } 288 289 /* Test using nt_list_next */ 290 for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) { 291 assert(item->a == i); 292 assert(item->b == i * 2); 293 } 294 295 /* Test using nt_list_for_each_entry */ 296 i = 1; 297 nt_list_for_each_entry(item, foo, next) { 298 assert(item->a == i); 299 assert(item->b == i * 2); 300 i++; 301 } 302 assert(i == 11); 303 } 304 305 static void 306 test_nt_list_delete(void) 307 { 308 int i = 1; 309 struct foo *list = calloc(10, sizeof(struct foo)); 310 struct foo *foo = list; 311 struct foo *item, *tmp; 312 struct foo *empty_list = foo; 313 314 nt_list_init(empty_list, next); 315 nt_list_del(empty_list, empty_list, struct foo, next); 316 317 assert(!empty_list); 318 319 for (item = foo, i = 1; i <= 10; i++, item++) { 320 item->a = i; 321 item->b = i * 2; 322 nt_list_init(item, next); 323 324 if (item != foo) 325 nt_list_append(item, foo, struct foo, next); 326 } 327 328 i = 0; 329 nt_list_for_each_entry(item, foo, next) { 330 i++; 331 } 332 assert(i == 10); 333 334 /* delete last item */ 335 nt_list_del(&foo[9], foo, struct foo, next); 336 337 i = 0; 338 nt_list_for_each_entry(item, foo, next) { 339 assert(item->a != 10); /* element 10 is gone now */ 340 i++; 341 } 342 assert(i == 9); /* 9 elements left */ 343 344 /* delete second item */ 345 nt_list_del(foo->next, foo, struct foo, next); 346 347 assert(foo->next->a == 3); 348 349 i = 0; 350 nt_list_for_each_entry(item, foo, next) { 351 assert(item->a != 10); /* element 10 is gone now */ 352 assert(item->a != 2); /* element 2 is gone now */ 353 i++; 354 } 355 assert(i == 8); /* 9 elements left */ 356 357 item = foo; 358 /* delete first item */ 359 nt_list_del(foo, foo, struct foo, next); 360 361 assert(item != foo); 362 assert(item->next == NULL); 363 assert(foo->a == 3); 364 assert(foo->next->a == 4); 365 366 nt_list_for_each_entry_safe(item, tmp, foo, next) { 367 nt_list_del(item, foo, struct foo, next); 368 } 369 370 assert(!foo); 371 assert(!item); 372 373 free(list); 374 } 375 376 int 377 list_test(void) 378 { 379 test_xorg_list_init(); 380 test_xorg_list_add(); 381 test_xorg_list_append(); 382 test_xorg_list_del(); 383 test_xorg_list_for_each(); 384 385 test_nt_list_init(); 386 test_nt_list_append(); 387 test_nt_list_insert(); 388 test_nt_list_delete(); 389 390 return 0; 391 }