This source file includes following definitions.
- string_equals
- string_hash
- cmp_pairs_in_array
- check_equals
- check_all
- main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20 #include "gl_array_map.h"
21
22 #include <limits.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "gl_xlist.h"
27 #include "gl_array_list.h"
28 #include "macros.h"
29
30 static const char *objects[30] =
31 {
32 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
33 "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
34 };
35
36 #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
37
38 static bool
39 string_equals (const void *x1, const void *x2)
40 {
41 const char *s1 = x1;
42 const char *s2 = x2;
43 return strcmp (s1, s2) == 0;
44 }
45
46
47
48
49 static size_t
50 string_hash (const void *x)
51 {
52 const char *s = x;
53 size_t h = 0;
54
55 for (; *s; s++)
56 h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
57
58 return h;
59 }
60
61 #define RANDOM(n) (rand () % (n))
62 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
63
64 struct pair
65 {
66 const void *key;
67 const void *value;
68 };
69
70 static int
71 cmp_pairs_in_array (const void *pairptr1, const void *pairptr2)
72 {
73 const void *key1 = ((struct pair const *)pairptr1)->key;
74 const void *key2 = ((struct pair const *)pairptr2)->key;
75 return strcmp ((const char *) key1, (const char *) key2);
76 }
77
78 static void
79 check_equals (gl_map_t map1, gl_list_t keys, gl_list_t values)
80 {
81 size_t n = gl_map_size (map1);
82 struct pair *pairs_of_map1 = XNMALLOC (n, struct pair);
83
84 gl_map_iterator_t iter1;
85 const void *key1;
86 const void *value1;
87 size_t i;
88
89 ASSERT (gl_list_size (keys) == n);
90 ASSERT (gl_list_size (values) == n);
91 iter1 = gl_map_iterator (map1);
92 for (i = 0; i < n; i++)
93 {
94 ASSERT (gl_map_iterator_next (&iter1, &key1, &value1));
95 pairs_of_map1[i].key = key1;
96 pairs_of_map1[i].value = value1;
97 }
98 ASSERT (!gl_map_iterator_next (&iter1, &key1, &value1));
99 gl_map_iterator_free (&iter1);
100
101 if (n > 0)
102 qsort (pairs_of_map1, n, sizeof (struct pair), cmp_pairs_in_array);
103 for (i = 0; i < n; i++)
104 {
105 ASSERT (pairs_of_map1[i].key == gl_list_get_at (keys, i));
106 ASSERT (pairs_of_map1[i].value == gl_list_get_at (values, i));
107 }
108 free (pairs_of_map1);
109 }
110
111 static void
112 check_all (gl_map_t map1, gl_list_t keys, gl_list_t values)
113 {
114 check_equals (map1, keys, values);
115 }
116
117 int
118 main (int argc, char *argv[])
119 {
120 gl_map_t map1;
121 gl_list_t keys;
122 gl_list_t values;
123
124
125 if (argc > 1)
126 srand (atoi (argv[1]));
127
128 {
129 size_t initial_size = RANDOM (20);
130 size_t i;
131 unsigned int repeat;
132
133
134 map1 = gl_map_nx_create_empty (GL_ARRAY_MAP,
135 string_equals, string_hash, NULL, NULL);
136 ASSERT (map1 != NULL);
137
138
139 keys = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, false);
140 values = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, false);
141
142 check_all (map1, keys, values);
143
144
145 for (i = 0; i < initial_size; i++)
146 {
147 const char *key = RANDOM_OBJECT ();
148 const char *value = RANDOM_OBJECT ();
149 bool added = gl_map_nx_put (map1, key, value);
150 size_t index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
151 ASSERT (added == (index == (size_t)(-1)));
152 if (added)
153 {
154 gl_sortedlist_add (keys, (gl_listelement_compar_fn)strcmp, key);
155 index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
156 gl_list_add_at (values, index, value);
157 }
158 else
159 gl_list_set_at (values, index, value);
160 check_all (map1, keys, values);
161 }
162
163 for (repeat = 0; repeat < 100000; repeat++)
164 {
165 unsigned int operation = RANDOM (3);
166 switch (operation)
167 {
168 case 0:
169 {
170 const char *key = RANDOM_OBJECT ();
171 const void *ret = gl_map_get (map1, key);
172 size_t index =
173 gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
174 ASSERT (ret
175 == (index != (size_t)(-1) ? gl_list_get_at (values, index) : NULL));
176 }
177 break;
178 case 1:
179 {
180 const char *key = RANDOM_OBJECT ();
181 const char *value = RANDOM_OBJECT ();
182 bool added = gl_map_nx_put (map1, key, value);
183 size_t index =
184 gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
185 ASSERT (added == (index == (size_t)(-1)));
186 if (added)
187 {
188 gl_sortedlist_add (keys, (gl_listelement_compar_fn)strcmp, key);
189 index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
190 gl_list_add_at (values, index, value);
191 }
192 else
193 gl_list_set_at (values, index, value);
194 }
195 break;
196 case 2:
197 {
198 const char *key = RANDOM_OBJECT ();
199 bool removed = gl_map_remove (map1, key);
200 size_t index =
201 gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
202 ASSERT (removed == (index != (size_t)(-1)));
203 if (removed)
204 {
205 gl_list_remove_at (keys, index);
206 gl_list_remove_at (values, index);
207 }
208 }
209 break;
210 }
211 check_all (map1, keys, values);
212 }
213
214 gl_map_free (map1);
215 gl_list_free (keys);
216 gl_list_free (values);
217 }
218
219 return 0;
220 }