test/list.c

   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 #ifdef HAVE_DIX_CONFIG_H
  25 #include <dix-config.h>
  26 #endif
  27
  28 #include <X11/Xlib.h>
  29 #include <list.h>
  30 #include <string.h>
  31 #include <assert.h>
  32 #include <stdlib.h>
  33
  34 struct parent {
  35     int a;
  36     struct xorg_list children;
  37     int b;
  38 };
  39
  40 struct child {
  41     int foo;
  42     int bar;
  43     struct xorg_list node;
  44 };
  45
  46 static void
  47 test_xorg_list_init(void)
  48 {
  49     struct parent parent, tmp;
  50
  51     memset(&parent, 0, sizeof(parent));
  52     parent.a = 0xa5a5a5;
  53     parent.b = ~0xa5a5a5;
  54
  55     tmp = parent;
  56
  57     xorg_list_init(&parent.children);
  58
  59     /* test we haven't touched anything else. */
  60     assert(parent.a == tmp.a);
  61     assert(parent.b == tmp.b);
  62
  63     assert(xorg_list_is_empty(&parent.children));
  64 }
  65
  66 static void
  67 test_xorg_list_add(void)
  68 {
  69     struct parent parent = { 0 };
  70     struct child child[3];
  71     struct child *c;
  72
  73     xorg_list_init(&parent.children);
  74
  75     xorg_list_add(&child[0].node, &parent.children);
  76     assert(!xorg_list_is_empty(&parent.children));
  77
  78     c = xorg_list_first_entry(&parent.children, struct child, node);
  79
  80     assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
  81
  82     /* note: xorg_list_add prepends */
  83     xorg_list_add(&child[1].node, &parent.children);
  84     c = xorg_list_first_entry(&parent.children, struct child, node);
  85
  86     assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
  87
  88     xorg_list_add(&child[2].node, &parent.children);
  89     c = xorg_list_first_entry(&parent.children, struct child, node);
  90
  91     assert(memcmp(c, &child[2], sizeof(struct child)) == 0);
  92 };
  93
  94 static void
  95 test_xorg_list_append(void)
  96 {
  97     struct parent parent = { 0 };
  98     struct child child[3];
  99     struct child *c;
 100     int i;
 101
 102     xorg_list_init(&parent.children);
 103
 104     xorg_list_append(&child[0].node, &parent.children);
 105     assert(!xorg_list_is_empty(&parent.children));
 106
 107     c = xorg_list_first_entry(&parent.children, struct child, node);
 108
 109     assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
 110     c = xorg_list_last_entry(&parent.children, struct child, node);
 111
 112     assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
 113
 114     xorg_list_append(&child[1].node, &parent.children);
 115     c = xorg_list_first_entry(&parent.children, struct child, node);
 116
 117     assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
 118     c = xorg_list_last_entry(&parent.children, struct child, node);
 119
 120     assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
 121
 122     xorg_list_append(&child[2].node, &parent.children);
 123     c = xorg_list_first_entry(&parent.children, struct child, node);
 124
 125     assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
 126     c = xorg_list_last_entry(&parent.children, struct child, node);
 127
 128     assert(memcmp(c, &child[2], sizeof(struct child)) == 0);
 129
 130     i = 0;
 131     xorg_list_for_each_entry(c, &parent.children, node) {
 132         assert(memcmp(c, &child[i++], sizeof(struct child)) == 0);
 133     }
 134 };
 135
 136 static void
 137 test_xorg_list_del(void)
 138 {
 139     struct parent parent = { 0 };
 140     struct child child[2];
 141     struct child *c;
 142
 143     xorg_list_init(&parent.children);
 144
 145     xorg_list_add(&child[0].node, &parent.children);
 146     assert(!xorg_list_is_empty(&parent.children));
 147
 148     xorg_list_del(&parent.children);
 149     assert(xorg_list_is_empty(&parent.children));
 150
 151     xorg_list_add(&child[0].node, &parent.children);
 152     xorg_list_del(&child[0].node);
 153     assert(xorg_list_is_empty(&parent.children));
 154
 155     xorg_list_add(&child[0].node, &parent.children);
 156     xorg_list_add(&child[1].node, &parent.children);
 157
 158     c = xorg_list_first_entry(&parent.children, struct child, node);
 159
 160     assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
 161
 162     /* delete first node */
 163     xorg_list_del(&child[1].node);
 164     assert(!xorg_list_is_empty(&parent.children));
 165     assert(xorg_list_is_empty(&child[1].node));
 166     c = xorg_list_first_entry(&parent.children, struct child, node);
 167
 168     assert(memcmp(c, &child[0], sizeof(struct child)) == 0);
 169
 170     /* delete last node */
 171     xorg_list_add(&child[1].node, &parent.children);
 172     xorg_list_del(&child[0].node);
 173     c = xorg_list_first_entry(&parent.children, struct child, node);
 174
 175     assert(memcmp(c, &child[1], sizeof(struct child)) == 0);
 176
 177     /* delete list head */
 178     xorg_list_add(&child[0].node, &parent.children);
 179     xorg_list_del(&parent.children);
 180     assert(xorg_list_is_empty(&parent.children));
 181     assert(!xorg_list_is_empty(&child[0].node));
 182     assert(!xorg_list_is_empty(&child[1].node));
 183 }
 184
 185 static void
 186 test_xorg_list_for_each(void)
 187 {
 188     struct parent parent = { 0 };
 189     struct child child[3];
 190     struct child *c;
 191     int i = 0;
 192
 193     xorg_list_init(&parent.children);
 194
 195     xorg_list_add(&child[2].node, &parent.children);
 196     xorg_list_add(&child[1].node, &parent.children);
 197     xorg_list_add(&child[0].node, &parent.children);
 198
 199     xorg_list_for_each_entry(c, &parent.children, node) {
 200         assert(memcmp(c, &child[i], sizeof(struct child)) == 0);
 201         i++;
 202     }
 203
 204     /* foreach on empty list */
 205     xorg_list_del(&parent.children);
 206     assert(xorg_list_is_empty(&parent.children));
 207
 208     xorg_list_for_each_entry(c, &parent.children, node) {
 209         assert(0);              /* we must not get here */
 210     }
 211 }
 212
 213 struct foo {
 214     char a;
 215     struct foo *next;
 216     char b;
 217 };
 218
 219 static void
 220 test_nt_list_init(void)
 221 {
 222     struct foo foo;
 223
 224     foo.a = 10;
 225     foo.b = 20;
 226     nt_list_init(&foo, next);
 227
 228     assert(foo.a == 10);
 229     assert(foo.b == 20);
 230     assert(foo.next == NULL);
 231     assert(nt_list_next(&foo, next) == NULL);
 232 }
 233
 234 static void
 235 test_nt_list_append(void)
 236 {
 237     int i;
 238     struct foo *foo = calloc(10, sizeof(struct foo));
 239     struct foo *item;
 240
 241     for (item = foo, i = 1; i <= 10; i++, item++) {
 242         item->a = i;
 243         item->b = i * 2;
 244         nt_list_init(item, next);
 245
 246         if (item != foo)
 247             nt_list_append(item, foo, struct foo, next);
 248     }
 249
 250     /* Test using nt_list_next */
 251     for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) {
 252         assert(item->a = i);
 253         assert(item->b = i * 2);
 254     }
 255
 256     /* Test using nt_list_for_each_entry */
 257     i = 1;
 258     nt_list_for_each_entry(item, foo, next) {
 259         assert(item->a = i);
 260         assert(item->b = i * 2);
 261         i++;
 262     }
 263     assert(i == 11);
 264 }
 265
 266 static void
 267 test_nt_list_insert(void)
 268 {
 269     int i;
 270     struct foo *foo = calloc(10, sizeof(struct foo));
 271     struct foo *item;
 272
 273     foo->a = 10;
 274     foo->b = 20;
 275     nt_list_init(foo, next);
 276
 277     for (item = &foo[1], i = 9; i > 0; i--, item++) {
 278         item->a = i;
 279         item->b = i * 2;
 280         nt_list_init(item, next);
 281         nt_list_insert(item, foo, struct foo, next);
 282     }
 283
 284     /* Test using nt_list_next */
 285     for (item = foo, i = 10; i > 0; i--, item = nt_list_next(item, next)) {
 286         assert(item->a = i);
 287         assert(item->b = i * 2);
 288     }
 289
 290     /* Test using nt_list_for_each_entry */
 291     i = 1;
 292     nt_list_for_each_entry(item, foo, next) {
 293         assert(item->a = i);
 294         assert(item->b = i * 2);
 295         i++;
 296     }
 297     assert(i == 11);
 298 }
 299
 300 static void
 301 test_nt_list_delete(void)
 302 {
 303     int i = 1;
 304     struct foo *list = calloc(10, sizeof(struct foo));
 305     struct foo *foo = list;
 306     struct foo *item, *tmp;
 307     struct foo *empty_list = foo;
 308
 309     nt_list_init(empty_list, next);
 310     nt_list_del(empty_list, empty_list, struct foo, next);
 311
 312     assert(!empty_list);
 313
 314     for (item = foo, i = 1; i <= 10; i++, item++) {
 315         item->a = i;
 316         item->b = i * 2;
 317         nt_list_init(item, next);
 318
 319         if (item != foo)
 320             nt_list_append(item, foo, struct foo, next);
 321     }
 322
 323     i = 0;
 324     nt_list_for_each_entry(item, foo, next) {
 325         i++;
 326     }
 327     assert(i == 10);
 328
 329     /* delete last item */
 330     nt_list_del(&foo[9], foo, struct foo, next);
 331
 332     i = 0;
 333     nt_list_for_each_entry(item, foo, next) {
 334         assert(item->a != 10);  /* element 10 is gone now */
 335         i++;
 336     }
 337     assert(i == 9);             /* 9 elements left */
 338
 339     /* delete second item */
 340     nt_list_del(foo->next, foo, struct foo, next);
 341
 342     assert(foo->next->a == 3);
 343
 344     i = 0;
 345     nt_list_for_each_entry(item, foo, next) {
 346         assert(item->a != 10);  /* element 10 is gone now */
 347         assert(item->a != 2);   /* element 2 is gone now */
 348         i++;
 349     }
 350     assert(i == 8);             /* 9 elements left */
 351
 352     item = foo;
 353     /* delete first item */
 354     nt_list_del(foo, foo, struct foo, next);
 355
 356     assert(item != foo);
 357     assert(item->next == NULL);
 358     assert(foo->a == 3);
 359     assert(foo->next->a == 4);
 360
 361     nt_list_for_each_entry_safe(item, tmp, foo, next) {
 362         nt_list_del(item, foo, struct foo, next);
 363     }
 364
 365     assert(!foo);
 366     assert(!item);
 367
 368     free(list);
 369 }
 370
 371 int
 372 main(int argc, char **argv)
 373 {
 374     test_xorg_list_init();
 375     test_xorg_list_add();
 376     test_xorg_list_append();
 377     test_xorg_list_del();
 378     test_xorg_list_for_each();
 379
 380     test_nt_list_init();
 381     test_nt_list_append();
 382     test_nt_list_insert();
 383     test_nt_list_delete();
 384
 385     return 0;
 386 }