njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 1 | |
| 2 | #include <assert.h> |
| 3 | #include <stdio.h> |
| 4 | #include <stdlib.h> |
| 5 | #include <string.h> |
| 6 | |
| 7 | #include "pub_core_basics.h" |
| 8 | #include "pub_core_libcbase.h" |
| 9 | #include "pub_core_libcassert.h" |
| 10 | #include "pub_core_libcprint.h" |
| 11 | |
| 12 | // I need this to avoid some signedness warnings, not sure why |
sewardj | b1e123a | 2005-08-19 09:07:34 +0000 | [diff] [blame] | 13 | // #define Char char |
| 14 | // jrs 19 Aug 2005: m_oset.c relies on Char being a signed char. |
| 15 | // It appears that plain 'char' on ppc32 is unsigned and so the |
| 16 | // above #define screws up the AVL tree balancing logic and |
| 17 | // leads to segfaults. Commenting it out and using the standard |
| 18 | // definition of Char from pub_core_basics.h seems a good solution |
| 19 | // as that has the same signedness on all platforms. |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 20 | |
| 21 | // Crudely redirect various VG_(foo)() functions to their libc equivalents. |
| 22 | #undef vg_assert |
| 23 | #define vg_assert(e) assert(e) |
| 24 | #undef vg_assert2 |
| 25 | #define vg_assert2(e, fmt, args...) assert(e) |
| 26 | |
| 27 | #define vgPlain_printf printf |
| 28 | #define vgPlain_memset memset |
| 29 | #define vgPlain_memcpy memcpy |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 30 | |
| 31 | #include "coregrind/m_oset.c" |
| 32 | |
| 33 | #define NN 1000 // Size of OSets being created |
| 34 | |
sewardj | 3d8dcf8 | 2006-10-17 01:25:13 +0000 | [diff] [blame] | 35 | |
| 36 | /* Consistent random number generator, so it produces the |
| 37 | same results on all platforms. */ |
| 38 | |
| 39 | #define random error_do_not_use_libc_random |
| 40 | |
| 41 | static UInt seed = 0; |
| 42 | static UInt myrandom( void ) |
| 43 | { |
| 44 | seed = (1103515245 * seed + 12345); |
| 45 | return seed; |
| 46 | } |
| 47 | |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 48 | static void* allocate_node(HChar* cc, SizeT szB) |
bart | 672a82d | 2008-05-04 08:10:24 +0000 | [diff] [blame] | 49 | { return malloc(szB); } |
| 50 | |
| 51 | static void free_node(void* p) |
| 52 | { return free(p); } |
sewardj | 3d8dcf8 | 2006-10-17 01:25:13 +0000 | [diff] [blame] | 53 | |
| 54 | |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 55 | //--------------------------------------------------------------------------- |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 56 | // Word example |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 57 | //--------------------------------------------------------------------------- |
| 58 | |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 59 | // This example shows that an element can be a single value (in this |
| 60 | // case a Word), in which case the element is also the key. |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 61 | |
| 62 | __attribute__((unused)) |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 63 | static Char *wordToStr(void *p) |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 64 | { |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 65 | static char buf[32]; |
| 66 | sprintf(buf, "%ld", *(Word*)p); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 67 | return buf; |
| 68 | } |
| 69 | |
| 70 | __attribute__((unused)) |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 71 | static Word wordCmp(void* vkey, void* velem) |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 72 | { |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 73 | return *(Word*)vkey - *(Word*)velem; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 74 | } |
| 75 | |
| 76 | void example1(void) |
| 77 | { |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 78 | Int i, n; |
| 79 | Word v, prev; |
| 80 | Word* vs[NN]; |
| 81 | Word *pv; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 82 | |
| 83 | // Create a static OSet of Ints. This one uses fast (built-in) |
| 84 | // comparisons. |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 85 | OSet* oset = VG_(OSetGen_Create)(0, |
bart | 672a82d | 2008-05-04 08:10:24 +0000 | [diff] [blame] | 86 | NULL, |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 87 | allocate_node, "oset_test.1", free_node); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 88 | |
| 89 | // Try some operations on an empty OSet to ensure they don't screw up. |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 90 | vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); |
| 91 | vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); |
| 92 | vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); |
| 93 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
| 94 | vg_assert( 0 == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 95 | |
| 96 | // Create some elements, with gaps (they're all even) but no dups, |
| 97 | // and shuffle them randomly. |
| 98 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 99 | vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Word)); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 100 | *(vs[i]) = 2*i; |
| 101 | } |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 102 | seed = 0; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 103 | for (i = 0; i < NN; i++) { |
sewardj | 3d8dcf8 | 2006-10-17 01:25:13 +0000 | [diff] [blame] | 104 | Word r1 = myrandom() % NN; |
| 105 | Word r2 = myrandom() % NN; |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 106 | Word* tmp= vs[r1]; |
| 107 | vs[r1] = vs[r2]; |
| 108 | vs[r2] = tmp; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 109 | } |
| 110 | |
| 111 | // Insert the elements |
| 112 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 113 | VG_(OSetGen_Insert)(oset, vs[i]); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 114 | } |
| 115 | |
| 116 | // Check the size |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 117 | vg_assert( NN == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 118 | |
| 119 | // Check we can find all the elements we inserted |
| 120 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 121 | assert( VG_(OSetGen_Contains)(oset, vs[i]) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 122 | } |
| 123 | |
| 124 | // Check we cannot find elements we did not insert, below, within (odd |
| 125 | // numbers), and above the inserted elements. |
| 126 | v = -1; |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 127 | assert( ! VG_(OSetGen_Contains)(oset, &v) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 128 | for (i = 0; i < NN; i++) { |
| 129 | v = *(vs[i]) + 1; |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 130 | assert( ! VG_(OSetGen_Contains)(oset, &v) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 131 | } |
| 132 | v = NN*2; |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 133 | assert( ! VG_(OSetGen_Contains)(oset, &v) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 134 | |
| 135 | // Check we can find all the elements we inserted, and the right values |
| 136 | // are returned. |
| 137 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 138 | assert( vs[i] == VG_(OSetGen_Lookup)(oset, vs[i]) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 139 | } |
| 140 | |
| 141 | // Check that we can iterate over the OSet elements in sorted order, and |
| 142 | // there is the right number of them. |
| 143 | n = 0; |
| 144 | pv = NULL; |
| 145 | prev = -1; |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 146 | VG_(OSetGen_ResetIter)(oset); |
| 147 | while ( (pv = VG_(OSetGen_Next)(oset)) ) { |
sewardj | 6792df3 | 2006-01-07 22:33:45 +0000 | [diff] [blame] | 148 | Word curr = *pv; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 149 | assert(prev < curr); |
| 150 | prev = curr; |
| 151 | n++; |
| 152 | } |
| 153 | assert(NN == n); |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 154 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
| 155 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 156 | |
| 157 | // Check that we can remove half of the elements, and that their values |
| 158 | // are as expected. |
| 159 | for (i = 0; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 160 | assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 161 | assert( pv == vs[i] ); |
| 162 | } |
| 163 | |
| 164 | // Check the size |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 165 | vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 166 | |
| 167 | // Check we can find the remaining elements (with the right values). |
| 168 | for (i = 1; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 169 | assert( pv = VG_(OSetGen_LookupWithCmp)(oset, vs[i], NULL) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 170 | assert( pv == vs[i] ); |
| 171 | } |
| 172 | |
| 173 | // Check we cannot find any of the elements we removed. |
| 174 | for (i = 0; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 175 | assert( ! VG_(OSetGen_Contains)(oset, vs[i]) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 176 | } |
| 177 | |
| 178 | // Check that we can remove the remaining half of the elements, and that |
| 179 | // their values are as expected. |
| 180 | for (i = 1; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 181 | assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 182 | assert( pv == vs[i] ); |
| 183 | } |
| 184 | |
| 185 | // Try some more operations on the empty OSet to ensure they don't screw up. |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 186 | vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); |
| 187 | vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); |
| 188 | vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); |
| 189 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
| 190 | vg_assert( 0 == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 191 | |
| 192 | // Free a few elements |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 193 | VG_(OSetGen_FreeNode)(oset, vs[0]); |
| 194 | VG_(OSetGen_FreeNode)(oset, vs[1]); |
| 195 | VG_(OSetGen_FreeNode)(oset, vs[2]); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 196 | |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 197 | // Re-insert remaining elements, to give OSetGen_Destroy something to |
| 198 | // work with. |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 199 | for (i = 3; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 200 | VG_(OSetGen_Insert)(oset, vs[i]); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 201 | } |
| 202 | |
| 203 | // Print the list |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 204 | OSet_Print(oset, "oset1", wordToStr); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 205 | |
| 206 | // Destroy the OSet |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 207 | VG_(OSetGen_Destroy)(oset); |
| 208 | } |
| 209 | |
| 210 | |
| 211 | void example1b(void) |
| 212 | { |
| 213 | Int i, n; |
| 214 | Word v = 0, prev; |
| 215 | Word vs[NN]; |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 216 | |
| 217 | // Create a static OSet of Ints. This one uses fast (built-in) |
| 218 | // comparisons. |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 219 | OSet* oset = VG_(OSetWord_Create)(allocate_node, "oset_test.2", free_node); |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 220 | |
| 221 | // Try some operations on an empty OSet to ensure they don't screw up. |
| 222 | vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); |
| 223 | vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); |
| 224 | vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); |
| 225 | vg_assert( 0 == VG_(OSetWord_Size)(oset) ); |
| 226 | |
| 227 | // Create some elements, with gaps (they're all even) but no dups, |
| 228 | // and shuffle them randomly. |
| 229 | for (i = 0; i < NN; i++) { |
| 230 | vs[i] = 2*i; |
| 231 | } |
| 232 | seed = 0; |
| 233 | for (i = 0; i < NN; i++) { |
| 234 | Word r1 = myrandom() % NN; |
| 235 | Word r2 = myrandom() % NN; |
| 236 | Word tmp = vs[r1]; |
| 237 | vs[r1] = vs[r2]; |
| 238 | vs[r2] = tmp; |
| 239 | } |
| 240 | |
| 241 | // Insert the elements |
| 242 | for (i = 0; i < NN; i++) { |
| 243 | VG_(OSetWord_Insert)(oset, vs[i]); |
| 244 | } |
| 245 | |
| 246 | // Check the size |
| 247 | vg_assert( NN == VG_(OSetWord_Size)(oset) ); |
| 248 | |
| 249 | // Check we can find all the elements we inserted |
| 250 | for (i = 0; i < NN; i++) { |
| 251 | assert( VG_(OSetWord_Contains)(oset, vs[i]) ); |
| 252 | } |
| 253 | |
| 254 | // Check we cannot find elements we did not insert, below, within (odd |
| 255 | // numbers), and above the inserted elements. |
| 256 | v = -1; |
| 257 | assert( ! VG_(OSetWord_Contains)(oset, v) ); |
| 258 | for (i = 0; i < NN; i++) { |
| 259 | v = vs[i] + 1; |
| 260 | assert( ! VG_(OSetWord_Contains)(oset, v) ); |
| 261 | } |
| 262 | v = NN*2; |
| 263 | assert( ! VG_(OSetWord_Contains)(oset, v) ); |
| 264 | |
| 265 | // Check we can find all the elements we inserted. |
| 266 | for (i = 0; i < NN; i++) { |
| 267 | assert( VG_(OSetWord_Contains)(oset, vs[i]) ); |
| 268 | } |
| 269 | |
| 270 | // Check that we can iterate over the OSet elements in sorted order, and |
| 271 | // there is the right number of them. |
| 272 | n = 0; |
| 273 | prev = -1; |
| 274 | VG_(OSetWord_ResetIter)(oset); |
| 275 | while ( VG_(OSetWord_Next)(oset, &v) ) { |
| 276 | Word curr = v; |
| 277 | assert(prev < curr); |
| 278 | prev = curr; |
| 279 | n++; |
| 280 | } |
| 281 | assert(NN == n); |
| 282 | vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); |
| 283 | vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); |
| 284 | |
| 285 | // Check that we can remove half of the elements. |
| 286 | for (i = 0; i < NN; i += 2) { |
| 287 | assert( VG_(OSetWord_Remove)(oset, vs[i]) ); |
| 288 | } |
| 289 | |
| 290 | // Check the size |
| 291 | vg_assert( NN/2 == VG_(OSetWord_Size)(oset) ); |
| 292 | |
| 293 | // Check we can find the remaining elements (with the right values). |
| 294 | for (i = 1; i < NN; i += 2) { |
| 295 | assert( VG_(OSetWord_Contains)(oset, vs[i]) ); |
| 296 | } |
| 297 | |
| 298 | // Check we cannot find any of the elements we removed. |
| 299 | for (i = 0; i < NN; i += 2) { |
| 300 | assert( ! VG_(OSetWord_Contains)(oset, vs[i]) ); |
| 301 | } |
| 302 | |
| 303 | // Check that we can remove the remaining half of the elements. |
| 304 | for (i = 1; i < NN; i += 2) { |
| 305 | assert( VG_(OSetWord_Remove)(oset, vs[i]) ); |
| 306 | } |
| 307 | |
| 308 | // Try some more operations on the empty OSet to ensure they don't screw up. |
| 309 | vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); |
| 310 | vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); |
| 311 | vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); |
| 312 | vg_assert( 0 == VG_(OSetWord_Size)(oset) ); |
| 313 | |
| 314 | // Re-insert remaining elements, to give OSetWord_Destroy something to |
| 315 | // work with. |
| 316 | for (i = 3; i < NN; i++) { |
| 317 | VG_(OSetWord_Insert)(oset, vs[i]); |
| 318 | } |
| 319 | |
| 320 | // Print the list |
| 321 | OSet_Print(oset, "oset1b", wordToStr); |
| 322 | |
| 323 | // Destroy the OSet |
| 324 | VG_(OSetWord_Destroy)(oset); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 325 | } |
| 326 | |
| 327 | |
| 328 | //--------------------------------------------------------------------------- |
| 329 | // Struct example |
| 330 | //--------------------------------------------------------------------------- |
| 331 | |
| 332 | // This element shows that a key can be in the middle of the element, and |
| 333 | // be of arbitrary size and even span multiple (contiguous) fields. It |
| 334 | // also demonstrates how an OSet can be used to implement a list of |
| 335 | // non-overlapping intervals. |
| 336 | |
| 337 | typedef struct { |
| 338 | Int b1; |
| 339 | Addr first; |
| 340 | Addr last; |
| 341 | Int b2; |
| 342 | } |
| 343 | Block; |
| 344 | |
| 345 | __attribute__((unused)) |
| 346 | static Char *blockToStr(void *p) |
| 347 | { |
| 348 | static char buf[32]; |
| 349 | Block* b = (Block*)p; |
| 350 | sprintf(buf, "<(%d) %lu..%lu (%d)>", b->b1, b->first, b->last, b->b2); |
| 351 | return buf; |
| 352 | } |
| 353 | |
tom | 1d090eb | 2008-01-04 23:58:32 +0000 | [diff] [blame] | 354 | static Word blockCmp(const void* vkey, const void* velem) |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 355 | { |
tom | 1d090eb | 2008-01-04 23:58:32 +0000 | [diff] [blame] | 356 | Addr key = *(const Addr*)vkey; |
| 357 | const Block* elem = (const Block*)velem; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 358 | |
| 359 | assert(elem->first <= elem->last); |
| 360 | if (key < elem->first) return -1; |
| 361 | if (key > elem->last) return 1; |
| 362 | return 0; |
| 363 | } |
| 364 | |
| 365 | void example2(void) |
| 366 | { |
| 367 | Int i, n; |
| 368 | Addr a; |
| 369 | Block* vs[NN]; |
| 370 | Block v, prev; |
| 371 | Block *pv; |
| 372 | |
| 373 | // Create a dynamic OSet of Blocks. This one uses slow (custom) |
| 374 | // comparisons. |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 375 | OSet* oset = VG_(OSetGen_Create)(offsetof(Block, first), |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 376 | blockCmp, |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 377 | allocate_node, "oset_test.3", free_node); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 378 | |
| 379 | // Try some operations on an empty OSet to ensure they don't screw up. |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 380 | vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); |
| 381 | vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); |
| 382 | vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); |
| 383 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
| 384 | vg_assert( 0 == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 385 | |
| 386 | // Create some inputs, with gaps -- intervals are 1..3, 11..13, ... -- but |
| 387 | // no dups, and shuffle them randomly. |
| 388 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 389 | vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Block)); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 390 | vs[i]->b1 = i; |
| 391 | vs[i]->first = i*10 + 1; |
| 392 | vs[i]->last = vs[i]->first + 2; |
| 393 | vs[i]->b2 = i+1; |
| 394 | } |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 395 | seed = 0; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 396 | for (i = 0; i < NN; i++) { |
sewardj | 3d8dcf8 | 2006-10-17 01:25:13 +0000 | [diff] [blame] | 397 | Int r1 = myrandom() % NN; |
| 398 | Int r2 = myrandom() % NN; |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 399 | Block* tmp = vs[r1]; |
| 400 | vs[r1] = vs[r2]; |
| 401 | vs[r2] = tmp; |
| 402 | } |
| 403 | |
| 404 | // Insert the elements |
| 405 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 406 | VG_(OSetGen_Insert)(oset, vs[i]); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 407 | } |
| 408 | |
| 409 | // Check the size |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 410 | vg_assert( NN == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 411 | |
| 412 | // Check we can find all the elements we inserted, within the full range |
| 413 | // of each Block. |
| 414 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 415 | a = vs[i]->first + 0; assert( VG_(OSetGen_Contains)(oset, &a) ); |
| 416 | a = vs[i]->first + 1; assert( VG_(OSetGen_Contains)(oset, &a) ); |
| 417 | a = vs[i]->first + 2; assert( VG_(OSetGen_Contains)(oset, &a) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 418 | } |
| 419 | |
| 420 | // Check we cannot find elements we did not insert, below and above the |
| 421 | // ranges of the inserted elements. |
| 422 | a = 0; |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 423 | assert( ! VG_(OSetGen_Contains)(oset, &a) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 424 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 425 | a = vs[i]->first - 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); |
| 426 | a = vs[i]->first + 3; assert( ! VG_(OSetGen_Contains)(oset, &a) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 427 | } |
| 428 | |
| 429 | // Check we can find all the elements we inserted, and the right values |
| 430 | // are returned. |
| 431 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 432 | a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); |
| 433 | a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); |
| 434 | a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); |
| 435 | assert( vs[i] == VG_(OSetGen_LookupWithCmp)(oset, &a, blockCmp) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 436 | } |
| 437 | |
| 438 | // Check that we can iterate over the OSet elements in sorted order, and |
| 439 | // there is the right number of them. |
| 440 | n = 0; |
| 441 | pv = NULL; |
| 442 | prev.last = 0; |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 443 | VG_(OSetGen_ResetIter)(oset); |
| 444 | while ( (pv = VG_(OSetGen_Next)(oset)) ) { |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 445 | Block curr = *pv; |
| 446 | assert(prev.last < curr.first); |
| 447 | prev = curr; |
| 448 | n++; |
| 449 | } |
| 450 | assert(NN == n); |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 451 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
| 452 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 453 | |
| 454 | // Check that we can remove half of the elements, and that their values |
| 455 | // are as expected. |
| 456 | for (i = 0; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 457 | a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 458 | } |
| 459 | |
| 460 | // Check the size |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 461 | vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 462 | |
| 463 | // Check we can find the remaining elements (with the right values). |
| 464 | for (i = 1; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 465 | a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); |
| 466 | a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); |
| 467 | a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 468 | } |
| 469 | |
| 470 | // Check we cannot find any of the elements we removed. |
| 471 | for (i = 0; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 472 | a = vs[i]->first + 0; assert( ! VG_(OSetGen_Contains)(oset, &a) ); |
| 473 | a = vs[i]->first + 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); |
| 474 | a = vs[i]->first + 2; assert( ! VG_(OSetGen_Contains)(oset, &a) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 475 | } |
| 476 | |
| 477 | // Check that we can remove the remaining half of the elements, and that |
| 478 | // their values are as expected. |
| 479 | for (i = 1; i < NN; i += 2) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 480 | a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 481 | } |
| 482 | |
| 483 | // Try some more operations on the empty OSet to ensure they don't screw up. |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 484 | vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); |
| 485 | vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); |
| 486 | vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); |
| 487 | vg_assert( ! VG_(OSetGen_Next)(oset) ); |
| 488 | vg_assert( 0 == VG_(OSetGen_Size)(oset) ); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 489 | |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 490 | // Re-insert all elements, to give OSetGen_Destroy something to work with. |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 491 | for (i = 0; i < NN; i++) { |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 492 | VG_(OSetGen_Insert)(oset, vs[i]); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 493 | } |
| 494 | |
| 495 | // Destroy the OSet |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 496 | VG_(OSetGen_Destroy)(oset); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 497 | } |
| 498 | |
| 499 | //----------------------------------------------------------------------- |
| 500 | // main() |
| 501 | //----------------------------------------------------------------------- |
| 502 | |
| 503 | int main(void) |
| 504 | { |
| 505 | example1(); |
njn | e2a9ad3 | 2007-09-17 05:30:48 +0000 | [diff] [blame] | 506 | example1b(); |
njn | 7b880bc | 2005-08-14 22:43:53 +0000 | [diff] [blame] | 507 | example2(); |
| 508 | return 0; |
| 509 | } |