Annotation of embedaddon/bird2/lib/lists_test.c, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD Library -- Linked Lists Tests
! 3: *
! 4: * (c) 2015 CZ.NIC z.s.p.o.
! 5: *
! 6: * Can be freely distributed and used under the terms of the GNU GPL.
! 7: */
! 8:
! 9: #include "test/birdtest.h"
! 10: #include "lib/lists.h"
! 11:
! 12: #define MAX_NUM 1000
! 13:
! 14: static node nodes[MAX_NUM];
! 15: static list l;
! 16:
! 17: static void
! 18: show_list(void)
! 19: {
! 20: bt_debug("\n");
! 21: bt_debug("list.null is at %p and point to %p\n", &l.null, l.null);
! 22: bt_debug("list.head is at %p and point to %p\n", &l.head, l.head);
! 23: bt_debug("list.tail is at %p and point to %p\n", &l.tail, l.tail);
! 24:
! 25: int i;
! 26: for (i = 0; i < MAX_NUM; i++)
! 27: {
! 28: bt_debug("n[%3i] is at %p\n", i, &nodes[i]);
! 29: bt_debug(" prev is at %p and point to %p\n", &(nodes[i].prev), nodes[i].prev);
! 30: bt_debug(" next is at %p and point to %p\n", &(nodes[i].next), nodes[i].next);
! 31: }
! 32: }
! 33:
! 34: static int
! 35: is_filled_list_well_linked(void)
! 36: {
! 37: int i;
! 38: bt_assert(l.head == &nodes[0]);
! 39: bt_assert(l.tail == &nodes[MAX_NUM-1]);
! 40: bt_assert((void *) nodes[0].prev == (void *) &l.head);
! 41: bt_assert((void *) nodes[MAX_NUM-1].next == (void *) &l.null);
! 42:
! 43: for (i = 0; i < MAX_NUM; i++)
! 44: {
! 45: if (i < (MAX_NUM-1))
! 46: bt_assert(nodes[i].next == &nodes[i+1]);
! 47:
! 48: if (i > 0)
! 49: bt_assert(nodes[i].prev == &nodes[i-1]);
! 50: }
! 51:
! 52: return 1;
! 53: }
! 54:
! 55: static int
! 56: is_empty_list_well_unlinked(void)
! 57: {
! 58: int i;
! 59:
! 60: bt_assert(l.head == NODE &l.null);
! 61: bt_assert(l.tail == NODE &l.head);
! 62: bt_assert(EMPTY_LIST(l));
! 63:
! 64: for (i = 0; i < MAX_NUM; i++)
! 65: {
! 66: bt_assert(nodes[i].next == NULL);
! 67: bt_assert(nodes[i].prev == NULL);
! 68: }
! 69:
! 70: return 1;
! 71: }
! 72:
! 73: static void
! 74: init_list__(list *l, struct node nodes[])
! 75: {
! 76: init_list(l);
! 77:
! 78: int i;
! 79: for (i = 0; i < MAX_NUM; i++)
! 80: {
! 81: nodes[i].next = NULL;
! 82: nodes[i].prev = NULL;
! 83: }
! 84: }
! 85:
! 86: static void
! 87: init_list_(void)
! 88: {
! 89: init_list__(&l, (node *) nodes);
! 90: }
! 91:
! 92: static int
! 93: t_add_tail(void)
! 94: {
! 95: int i;
! 96:
! 97: init_list_();
! 98: for (i = 0; i < MAX_NUM; i++)
! 99: {
! 100: add_tail(&l, &nodes[i]);
! 101: bt_debug(".");
! 102: bt_assert(l.tail == &nodes[i]);
! 103: bt_assert(l.head == &nodes[0]);
! 104: bt_assert((void *) nodes[i].next == (void *) &l.null);
! 105: if (i > 0)
! 106: {
! 107: bt_assert(nodes[i-1].next == &nodes[i]);
! 108: bt_assert(nodes[i].prev == &nodes[i-1]);
! 109: }
! 110: }
! 111: show_list();
! 112: bt_assert(is_filled_list_well_linked());
! 113:
! 114: return 1;
! 115: }
! 116:
! 117: static int
! 118: t_add_head(void)
! 119: {
! 120: int i;
! 121:
! 122: init_list_();
! 123: for (i = MAX_NUM-1; i >= 0; i--)
! 124: {
! 125: add_head(&l, &nodes[i]);
! 126: bt_debug(".");
! 127: bt_assert(l.head == &nodes[i]);
! 128: bt_assert(l.tail == &nodes[MAX_NUM-1]);
! 129: if (i < MAX_NUM-1)
! 130: {
! 131: bt_assert(nodes[i+1].prev == &nodes[i]);
! 132: bt_assert(nodes[i].next == &nodes[i+1]);
! 133: }
! 134: }
! 135: show_list();
! 136: bt_assert(is_filled_list_well_linked());
! 137:
! 138: return 1;
! 139: }
! 140:
! 141: static void
! 142: insert_node_(node *n, node *after)
! 143: {
! 144: insert_node(n, after);
! 145: bt_debug(".");
! 146: }
! 147:
! 148: static int
! 149: t_insert_node(void)
! 150: {
! 151: int i;
! 152:
! 153: init_list_();
! 154:
! 155: // add first node
! 156: insert_node_(&nodes[0], NODE &l.head);
! 157:
! 158: // add odd nodes
! 159: for (i = 2; i < MAX_NUM; i+=2)
! 160: insert_node_(&nodes[i], &nodes[i-2]);
! 161:
! 162: // add even nodes
! 163: for (i = 1; i < MAX_NUM; i+=2)
! 164: insert_node_(&nodes[i], &nodes[i-1]);
! 165:
! 166: bt_debug("\n");
! 167: bt_assert(is_filled_list_well_linked());
! 168:
! 169: return 1;
! 170: }
! 171:
! 172: static void
! 173: fill_list2(list *l, node nodes[])
! 174: {
! 175: int i;
! 176: for (i = 0; i < MAX_NUM; i++)
! 177: add_tail(l, &nodes[i]);
! 178: }
! 179:
! 180: static void
! 181: fill_list(void)
! 182: {
! 183: fill_list2(&l, (node *) nodes);
! 184: }
! 185:
! 186: static int
! 187: t_remove_node(void)
! 188: {
! 189: int i;
! 190:
! 191: init_list_();
! 192:
! 193: /* Fill & Remove & Check */
! 194: fill_list();
! 195: for (i = 0; i < MAX_NUM; i++)
! 196: rem_node(&nodes[i]);
! 197: bt_assert(is_empty_list_well_unlinked());
! 198:
! 199: /* Fill & Remove the half of nodes & Check & Remove the rest nodes & Check */
! 200: fill_list();
! 201: for (i = 0; i < MAX_NUM; i+=2)
! 202: rem_node(&nodes[i]);
! 203:
! 204: int tail_node_index = (MAX_NUM % 2) ? MAX_NUM - 2 : MAX_NUM - 1;
! 205: bt_assert(l.head == &nodes[1]);
! 206: bt_assert(l.tail == &nodes[tail_node_index]);
! 207: bt_assert(nodes[tail_node_index].next == NODE &l.null);
! 208:
! 209: for (i = 1; i < MAX_NUM; i+=2)
! 210: {
! 211: if (i > 1)
! 212: bt_assert(nodes[i].prev == &nodes[i-2]);
! 213: if (i < tail_node_index)
! 214: bt_assert(nodes[i].next == &nodes[i+2]);
! 215: }
! 216:
! 217: for (i = 1; i < MAX_NUM; i+=2)
! 218: rem_node(&nodes[i]);
! 219: bt_assert(is_empty_list_well_unlinked());
! 220:
! 221: return 1;
! 222: }
! 223:
! 224: static int
! 225: t_replace_node(void)
! 226: {
! 227: node head, inside, tail;
! 228:
! 229: init_list_();
! 230: fill_list();
! 231:
! 232: replace_node(&nodes[0], &head);
! 233: bt_assert(l.head == &head);
! 234: bt_assert(head.prev == NODE &l.head);
! 235: bt_assert(head.next == &nodes[1]);
! 236: bt_assert(nodes[1].prev == &head);
! 237:
! 238: replace_node(&nodes[MAX_NUM/2], &inside);
! 239: bt_assert(nodes[MAX_NUM/2-1].next == &inside);
! 240: bt_assert(nodes[MAX_NUM/2+1].prev == &inside);
! 241: bt_assert(inside.prev == &nodes[MAX_NUM/2-1]);
! 242: bt_assert(inside.next == &nodes[MAX_NUM/2+1]);
! 243:
! 244: replace_node(&nodes[MAX_NUM-1], &tail);
! 245: bt_assert(l.tail == &tail);
! 246: bt_assert(tail.prev == &nodes[MAX_NUM-2]);
! 247: bt_assert(tail.next == NODE &l.null);
! 248: bt_assert(nodes[MAX_NUM-2].next == &tail);
! 249:
! 250: return 1;
! 251: }
! 252:
! 253: static int
! 254: t_add_tail_list(void)
! 255: {
! 256: node nodes2[MAX_NUM];
! 257: list l2;
! 258:
! 259: init_list__(&l, (node *) nodes);
! 260: fill_list2(&l, (node *) nodes);
! 261:
! 262: init_list__(&l2, (node *) nodes2);
! 263: fill_list2(&l2, (node *) nodes2);
! 264:
! 265: add_tail_list(&l, &l2);
! 266:
! 267: bt_assert(nodes[MAX_NUM-1].next == &nodes2[0]);
! 268: bt_assert(nodes2[0].prev == &nodes[MAX_NUM-1]);
! 269: bt_assert(l.tail == &nodes2[MAX_NUM-1]);
! 270:
! 271: return 1;
! 272: }
! 273:
! 274: int
! 275: main(int argc, char *argv[])
! 276: {
! 277: bt_init(argc, argv);
! 278:
! 279: bt_test_suite(t_add_tail, "Adding nodes to tail of list");
! 280: bt_test_suite(t_add_head, "Adding nodes to head of list");
! 281: bt_test_suite(t_insert_node, "Inserting nodes to list");
! 282: bt_test_suite(t_remove_node, "Removing nodes from list");
! 283: bt_test_suite(t_replace_node, "Replacing nodes in list");
! 284: bt_test_suite(t_add_tail_list, "At the tail of a list adding the another list");
! 285:
! 286: return bt_exit_value();
! 287: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>