1/* Test of sequential list data type implementation. 2 Copyright (C) 2006-2007 Free Software Foundation, Inc. 3 Written by Bruno Haible <bruno@clisp.org>, 2007. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17 18#include <config.h> 19 20#include "gl_array_list.h" 21 22#include <stdio.h> 23#include <stdlib.h> 24 25#include "progname.h" 26 27static const char *objects[15] = 28 { 29 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o" 30 }; 31 32#define SIZEOF(array) (sizeof (array) / sizeof (array[0])) 33#define ASSERT(expr) \ 34 do \ 35 { \ 36 if (!(expr)) \ 37 { \ 38 fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \ 39 abort (); \ 40 } \ 41 } \ 42 while (0) 43#define RANDOM(n) (rand () % (n)) 44#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))] 45 46static void 47check_equals (gl_list_t list1, gl_list_t list2) 48{ 49 size_t n, i; 50 51 n = gl_list_size (list1); 52 ASSERT (n == gl_list_size (list2)); 53 for (i = 0; i < n; i++) 54 { 55 ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i)); 56 } 57} 58 59int 60main (int argc, char *argv[]) 61{ 62 gl_list_t list1, list2; 63 64 set_program_name (argv[0]); 65 66 /* Allow the user to provide a non-default random seed on the command line. */ 67 if (argc > 1) 68 srand (atoi (argv[1])); 69 70 { 71 size_t initial_size = RANDOM (50); 72 const void **contents = 73 (const void **) malloc (initial_size * sizeof (const void *)); 74 size_t i; 75 unsigned int repeat; 76 77 for (i = 0; i < initial_size; i++) 78 contents[i] = RANDOM_OBJECT (); 79 80 /* Create list1. */ 81 list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, 82 initial_size, contents); 83 /* Create list2. */ 84 list2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true); 85 for (i = 0; i < initial_size; i++) 86 gl_list_add_last (list2, contents[i]); 87 88 check_equals (list1, list2); 89 90 for (repeat = 0; repeat < 10000; repeat++) 91 { 92 unsigned int operation = RANDOM (16); 93 switch (operation) 94 { 95 case 0: 96 if (gl_list_size (list1) > 0) 97 { 98 size_t index = RANDOM (gl_list_size (list1)); 99 const char *obj = RANDOM_OBJECT (); 100 gl_list_node_t node1, node2; 101 102 node1 = gl_list_set_at (list1, index, obj); 103 ASSERT (gl_list_get_at (list1, index) == obj); 104 ASSERT (gl_list_node_value (list1, node1) == obj); 105 106 node2 = gl_list_set_at (list2, index, obj); 107 ASSERT (gl_list_get_at (list2, index) == obj); 108 ASSERT (gl_list_node_value (list2, node2) == obj); 109 110 if (index > 0) 111 { 112 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1)) 113 == gl_list_get_at (list1, index - 1)); 114 } 115 if (index + 1 < gl_list_size (list1)) 116 { 117 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1)) 118 == gl_list_get_at (list1, index + 1)); 119 } 120 } 121 break; 122 case 1: 123 { 124 const char *obj = RANDOM_OBJECT (); 125 gl_list_node_t node1, node2; 126 node1 = gl_list_search (list1, obj); 127 node2 = gl_list_search (list2, obj); 128 if (node1 == NULL) 129 { 130 ASSERT (node2 == NULL); 131 } 132 else 133 { 134 ASSERT (node2 != NULL); 135 ASSERT (gl_list_node_value (list1, node1) == obj); 136 ASSERT (gl_list_node_value (list2, node2) == obj); 137 } 138 } 139 break; 140 case 2: 141 { 142 const char *obj = RANDOM_OBJECT (); 143 size_t index1, index2; 144 index1 = gl_list_indexof (list1, obj); 145 index2 = gl_list_indexof (list2, obj); 146 if (index1 == (size_t)(-1)) 147 { 148 ASSERT (index2 == (size_t)(-1)); 149 } 150 else 151 { 152 ASSERT (index2 != (size_t)(-1)); 153 ASSERT (gl_list_get_at (list1, index1) == obj); 154 ASSERT (gl_list_get_at (list2, index2) == obj); 155 ASSERT (index2 == index1); 156 } 157 } 158 break; 159 case 3: /* add 1 element */ 160 { 161 const char *obj = RANDOM_OBJECT (); 162 gl_list_node_t node1, node2; 163 node1 = gl_list_add_first (list1, obj); 164 node2 = gl_list_add_first (list2, obj); 165 ASSERT (gl_list_node_value (list1, node1) == obj); 166 ASSERT (gl_list_node_value (list2, node2) == obj); 167 ASSERT (gl_list_get_at (list1, 0) == obj); 168 ASSERT (gl_list_get_at (list2, 0) == obj); 169 } 170 break; 171 case 4: /* add 1 element */ 172 { 173 const char *obj = RANDOM_OBJECT (); 174 gl_list_node_t node1, node2; 175 node1 = gl_list_add_last (list1, obj); 176 node2 = gl_list_add_last (list2, obj); 177 ASSERT (gl_list_node_value (list1, node1) == obj); 178 ASSERT (gl_list_node_value (list2, node2) == obj); 179 ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj); 180 ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj); 181 } 182 break; 183 case 5: /* add 3 elements */ 184 { 185 const char *obj0 = RANDOM_OBJECT (); 186 const char *obj1 = RANDOM_OBJECT (); 187 const char *obj2 = RANDOM_OBJECT (); 188 gl_list_node_t node1, node2; 189 node1 = gl_list_add_first (list1, obj2); 190 node1 = gl_list_add_before (list1, node1, obj0); 191 node1 = gl_list_add_after (list1, node1, obj1); 192 node2 = gl_list_add_first (list2, obj2); 193 node2 = gl_list_add_before (list2, node2, obj0); 194 node2 = gl_list_add_after (list2, node2, obj1); 195 ASSERT (gl_list_node_value (list1, node1) == obj1); 196 ASSERT (gl_list_node_value (list2, node2) == obj1); 197 ASSERT (gl_list_get_at (list1, 0) == obj0); 198 ASSERT (gl_list_get_at (list1, 1) == obj1); 199 ASSERT (gl_list_get_at (list1, 2) == obj2); 200 ASSERT (gl_list_get_at (list2, 0) == obj0); 201 ASSERT (gl_list_get_at (list2, 1) == obj1); 202 ASSERT (gl_list_get_at (list2, 2) == obj2); 203 } 204 break; 205 case 6: /* add 1 element */ 206 { 207 size_t index = RANDOM (gl_list_size (list1) + 1); 208 const char *obj = RANDOM_OBJECT (); 209 gl_list_node_t node1, node2; 210 node1 = gl_list_add_at (list1, index, obj); 211 node2 = gl_list_add_at (list2, index, obj); 212 ASSERT (gl_list_get_at (list1, index) == obj); 213 ASSERT (gl_list_node_value (list1, node1) == obj); 214 ASSERT (gl_list_get_at (list2, index) == obj); 215 ASSERT (gl_list_node_value (list2, node2) == obj); 216 if (index > 0) 217 { 218 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1)) 219 == gl_list_get_at (list1, index - 1)); 220 } 221 if (index + 1 < gl_list_size (list1)) 222 { 223 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1)) 224 == gl_list_get_at (list1, index + 1)); 225 } 226 } 227 break; 228 case 7: case 8: /* remove 1 element */ 229 if (gl_list_size (list1) > 0) 230 { 231 size_t n = gl_list_size (list1); 232 const char *obj = gl_list_get_at (list1, RANDOM (n)); 233 gl_list_node_t node1, node2; 234 node1 = gl_list_search (list1, obj); 235 node2 = gl_list_search (list2, obj); 236 ASSERT (node1 != NULL); 237 ASSERT (node2 != NULL); 238 ASSERT (gl_list_remove_node (list1, node1)); 239 ASSERT (gl_list_remove_node (list2, node2)); 240 ASSERT (gl_list_size (list1) == n - 1); 241 } 242 break; 243 case 9: case 10: /* remove 1 element */ 244 if (gl_list_size (list1) > 0) 245 { 246 size_t n = gl_list_size (list1); 247 size_t index = RANDOM (n); 248 ASSERT (gl_list_remove_at (list1, index)); 249 ASSERT (gl_list_remove_at (list2, index)); 250 ASSERT (gl_list_size (list1) == n - 1); 251 } 252 break; 253 case 11: case 12: /* remove 1 element */ 254 if (gl_list_size (list1) > 0) 255 { 256 size_t n = gl_list_size (list1); 257 const char *obj = gl_list_get_at (list1, RANDOM (n)); 258 ASSERT (gl_list_remove (list1, obj)); 259 ASSERT (gl_list_remove (list2, obj)); 260 ASSERT (gl_list_size (list1) == n - 1); 261 } 262 break; 263 case 13: 264 if (gl_list_size (list1) > 0) 265 { 266 size_t n = gl_list_size (list1); 267 const char *obj = "xyzzy"; 268 ASSERT (!gl_list_remove (list1, obj)); 269 ASSERT (!gl_list_remove (list2, obj)); 270 ASSERT (gl_list_size (list1) == n); 271 } 272 break; 273 case 14: 274 { 275 size_t n = gl_list_size (list1); 276 gl_list_iterator_t iter1, iter2; 277 const void *elt; 278 iter1 = gl_list_iterator (list1); 279 iter2 = gl_list_iterator (list2); 280 for (i = 0; i < n; i++) 281 { 282 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL)); 283 ASSERT (gl_list_get_at (list1, i) == elt); 284 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL)); 285 ASSERT (gl_list_get_at (list2, i) == elt); 286 } 287 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL)); 288 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL)); 289 gl_list_iterator_free (&iter1); 290 gl_list_iterator_free (&iter2); 291 } 292 break; 293 case 15: 294 { 295 size_t end = RANDOM (gl_list_size (list1) + 1); 296 size_t start = RANDOM (end + 1); 297 gl_list_iterator_t iter1, iter2; 298 const void *elt; 299 iter1 = gl_list_iterator_from_to (list1, start, end); 300 iter2 = gl_list_iterator_from_to (list2, start, end); 301 for (i = start; i < end; i++) 302 { 303 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL)); 304 ASSERT (gl_list_get_at (list1, i) == elt); 305 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL)); 306 ASSERT (gl_list_get_at (list2, i) == elt); 307 } 308 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL)); 309 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL)); 310 gl_list_iterator_free (&iter1); 311 gl_list_iterator_free (&iter2); 312 } 313 break; 314 } 315 check_equals (list1, list2); 316 } 317 318 gl_list_free (list1); 319 gl_list_free (list2); 320 free (contents); 321 } 322 323 return 0; 324} 325