1/* 2 * Copyright © 2013 Intel Corporation 3 * 4 * This library is free software: you can redistribute it and/or modify 5 * it under the terms of the GNU Lesser General Public License as published by 6 * the Free Software Foundation, either version 2.1 of the License, or 7 * (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU Lesser General Public License for more details. 13 * 14 * You should have received a copy of the GNU Lesser General Public License 15 * along with this library. If not, see <http://www.gnu.org/licenses/>. 16 * 17 * Authors: 18 * Simon McVittie <simon.mcvittie@collabora.co.uk> 19 */ 20 21using Gee; 22using Folks; 23 24/* An object with no equality pseudo-operator. */ 25public class DirectEq : Object 26{ 27 public uint u; 28 29 public DirectEq (uint u) 30 { 31 this.u = u; 32 } 33} 34 35/* An object with an equality pseudo-operator. */ 36public class UInt : Object 37{ 38 public uint u; 39 40 public UInt (uint u) 41 { 42 this.u = u; 43 } 44 45 public static uint hash_static (UInt that) 46 { 47 return that.u; 48 } 49 50 public static bool equals_static (UInt left, UInt right) 51 { 52 return left.u == right.u; 53 } 54} 55 56public class SmallSetTests : Folks.TestCase 57{ 58 public SmallSetTests () 59 { 60 base ("SmallSet"); 61 this.add_test ("objects_hash", () => this.test_objects (true)); 62 this.add_test ("objects", () => this.test_objects (false)); 63 this.add_test ("iter_hash", () => this.test_iter (true)); 64 this.add_test ("iter", () => this.test_iter (false)); 65 this.add_test ("readonly_hash", () => this.test_readonly (true)); 66 this.add_test ("readonly", () => this.test_readonly (false)); 67 this.add_test ("direct_hash", () => this.test_direct (true)); 68 this.add_test ("direct", () => this.test_direct (false)); 69 this.add_test ("string_hash", () => this.test_strings (true)); 70 this.add_test ("string", () => this.test_strings (false)); 71 this.add_test ("cheating", this.test_cheating); 72 } 73 74 public void test_objects (bool use_hash) 75 { 76 var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static); 77 var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static); 78 79 Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>); 80 81 assert (objects != null); 82 assert (!objects.read_only); 83 assert (objects.size == 0); 84 assert (objects.is_empty); 85 86 objects.add (new UInt (10000)); 87 objects.add (new UInt (1)); 88 objects.add (new UInt (10)); 89 objects.add (new UInt (100)); 90 objects.add (new UInt (1000)); 91 92 assert (objects != null); 93 assert (!objects.read_only); 94 assert (!objects.is_empty); 95 assert (objects.size == 5); 96 97 uint sum = 0; 98 bool res = objects.foreach ((obj) => 99 { 100 sum += obj.u; 101 return true; 102 }); 103 104 /* FIXME: this used to be wrong in HashSet (GNOME #696710). 105 * Do this unconditionally when we depend on a Gee with that fixed */ 106 if (!use_hash) 107 assert (res == true); 108 109 assert (sum == 11111); 110 111 sum = 0; 112 res = objects.foreach ((obj) => 113 { 114 sum += obj.u; 115 return false; 116 }); 117 assert (res == false); 118 assert (sum == 1 || sum == 10 || sum == 100 || sum == 1000 || 119 sum == 10000); 120 121 var ten = new UInt (10); 122 123 objects.foreach ((obj) => 124 { 125 /* It is not the same object as the one in the set... */ 126 assert (ten != obj); 127 return true; 128 }); 129 130 /* ... but it is equal, and that'll do */ 131 assert (objects.contains (ten)); 132 /* Vala syntactic sugar */ 133 assert (ten in objects); 134 /* It's a set. Attempts to add a duplicate are ignored. */ 135 res = objects.add (ten); 136 assert (res == false); 137 assert (objects.size == 5); 138 objects.foreach ((obj) => 139 { 140 assert (ten != obj); 141 return true; 142 }); 143 144 objects.remove (ten); 145 146 /* Vala syntactic sugar: behind the scenes, this uses an iterator */ 147 sum = 0; 148 foreach (var obj in objects) 149 sum += obj.u; 150 assert (sum == 11101); 151 152 /* Put it back. */ 153 res = objects.add (ten); 154 assert (res == true); 155 156 sum = 0; 157 foreach (var obj in objects) 158 sum += obj.u; 159 assert (sum == 11111); 160 161 objects.clear (); 162 assert (objects.size == 0); 163 assert (objects.is_empty); 164 foreach (var obj in objects) 165 assert_not_reached (); 166 } 167 168 public void test_iter (bool use_hash) 169 { 170 var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static); 171 var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static); 172 173 Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>); 174 175 var iter = objects.iterator (); /* points before 0 - invalid */ 176 assert (!iter.valid); 177 assert (!iter.read_only); 178 assert (!iter.has_next ()); 179 bool res = iter.next (); /* fails, remains pointing before 0 */ 180 assert (!res); 181 assert (!iter.valid); 182 assert (!iter.has_next ()); 183 184 objects.add (new UInt (1)); 185 objects.add (new UInt (10)); 186 objects.add (new UInt (100)); 187 objects.add (new UInt (1000)); 188 objects.add (new UInt (10000)); 189 assert (objects.size == 5); 190 191 iter = objects.iterator (); /* points before 0 - invalid */ 192 193 assert (!iter.valid); 194 assert (!iter.read_only); 195 196 assert (iter.has_next ()); 197 res = iter.next (); /* points to 0 */ 198 assert (res); 199 assert (iter.valid); 200 assert (iter.has_next ()); 201 202 iter.next (); /* points to 1 */ 203 iter.next (); /* points to 2 */ 204 iter.next (); /* points to 3 */ 205 assert (iter.valid); 206 assert (iter.has_next ()); 207 iter.next (); /* points to 4 */ 208 assert (iter.valid); 209 assert (!iter.has_next ()); 210 res = iter.next (); /* fails, remains pointing to 4 */ 211 assert (!res); 212 assert (iter.valid); /* still valid */ 213 assert (!iter.has_next ()); 214 215 iter = objects.iterator (); 216 uint sum = 0; 217 /* If the iterator has not been started then iter.foreach starts from 218 * the beginning, skipping any prior items. */ 219 iter.foreach ((obj) => 220 { 221 sum += obj.u; 222 return true; 223 }); 224 assert (sum == 11111); 225 226 sum = 0; 227 iter = objects.iterator (); 228 res = iter.foreach ((obj) => 229 { 230 sum += obj.u; 231 return false; 232 }); 233 assert (res == false); 234 assert (sum == 1 || sum == 10 || sum == 100 || sum == 1000 || 235 sum == 10000); 236 237 sum = 0; 238 iter = objects.iterator (); 239 iter.next (); 240 sum += iter.get ().u; 241 iter.next (); 242 sum += iter.get ().u; 243 iter.next (); 244 /* If iter.valid then iter.foreach starts from the current item, 245 * skipping any prior items. We already added the ones we expect to 246 * have skipped. */ 247 iter.foreach ((obj) => 248 { 249 sum += obj.u; 250 return true; 251 }); 252 assert (sum == 11111); 253 254 sum = 0; 255 iter = objects.iterator (); 256 iter.next (); 257 iter.next (); 258 iter.next (); 259 iter.next (); 260 iter.next (); 261 iter.foreach ((obj) => 262 { 263 /* only run for the current == last item */ 264 sum += 1; 265 return true; 266 }); 267 assert (sum == 1); 268 269 /* Remove the first element. */ 270 sum = 0; 271 iter = objects.iterator (); 272 iter.next (); 273 assert (iter.valid); 274 var removed = iter.get (); 275 iter.remove (); 276 sum += removed.u; 277 assert (!iter.valid); 278 while (iter.next ()) 279 sum += iter.get ().u; 280 assert (sum == 11111); 281 /* Put it back. */ 282 objects.add (removed); 283 284 /* Remove a middle element. */ 285 sum = 0; 286 iter = objects.iterator (); 287 iter.next (); 288 sum += iter.get ().u; 289 iter.next (); 290 sum += iter.get ().u; 291 iter.next (); 292 assert (iter.valid); 293 removed = iter.get (); 294 iter.remove (); 295 sum += removed.u; 296 assert (!iter.valid); 297 while (iter.next ()) 298 sum += iter.get ().u; 299 assert (sum == 11111); 300 /* Put it back. */ 301 objects.add (removed); 302 303 /* Remove the last element. */ 304 sum = 0; 305 iter = objects.iterator (); 306 iter.next (); 307 iter.next (); 308 iter.next (); 309 iter.next (); 310 iter.next (); 311 assert (iter.valid); 312 assert (!iter.has_next ()); 313 removed = iter.get (); 314 iter.remove (); 315 sum += removed.u; 316 assert (!iter.valid); 317 assert (!iter.has_next ()); 318 foreach (var obj in objects) 319 sum += obj.u; 320 assert (sum == 11111); 321 /* Put it back. */ 322 objects.add (removed); 323 } 324 325 public void test_readonly (bool use_hash) 326 { 327 var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static); 328 var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static); 329 330 Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>); 331 332 var ro = objects.read_only_view; 333 assert (ro != null); 334 assert (ro != objects); 335 assert (ro.read_only); 336 assert (ro.size == 0); 337 338 objects.add (new UInt (23)); 339 assert (objects.size == 1); 340 assert (ro.size == 1); 341 342 uint u = 0; 343 ro.foreach ((obj) => 344 { 345 assert (u == 0); 346 u = obj.u; 347 return true; 348 }); 349 assert (u == 23); 350 351 var iter = ro.iterator (); 352 assert (iter.read_only); 353 u = 0; 354 iter.foreach ((obj) => 355 { 356 assert (u == 0); 357 u = obj.u; 358 return true; 359 }); 360 assert (u == 23); 361 362 /* These are implementation details */ 363 if (!use_hash) 364 { 365 /* A new read-only view of an object is not the same thing yet */ 366 var ro2 = objects.read_only_view; 367 assert (ro != ro2); 368 369 /* The read-only view of a read-only view is itself */ 370 ro2 = ro.read_only_view; 371 assert (ro == ro2); 372 } 373 } 374 375 public void test_direct (bool use_hash) 376 { 377 var small = new SmallSet<DirectEq> (); 378 var hash = new HashSet<DirectEq> (); 379 380 Set<DirectEq> objects = (use_hash ? 381 hash as Set<DirectEq> : small as Set<DirectEq>); 382 383 objects.add (new DirectEq (23)); 384 objects.add (new DirectEq (23)); 385 var fortytwo = new DirectEq (42); 386 objects.add (fortytwo); 387 objects.add (fortytwo); 388 assert (objects.size == 3); 389 390 uint sum = 0; 391 foreach (var obj in objects) 392 sum += obj.u; 393 assert (sum == 23 + 23 + 42); 394 } 395 396 public void test_strings (bool use_hash) 397 { 398 var small = new SmallSet<string> (); 399 var hash = new HashSet<string> ((Gee.HashDataFunc) str_hash, 400 (Gee.EqualDataFunc) str_equal); 401 402 Set<string> strings = (use_hash ? 403 hash as Set<string> : small as Set<string>); 404 405 strings.add ("cheese"); 406 strings.add ("cheese"); 407 strings.add ("ham"); 408 assert (strings.size == 2); 409 } 410 411 public void test_cheating () 412 { 413 var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static); 414 var set_ = (!) (small as Set<UInt>); 415 416 small.add (new UInt (1)); 417 small.add (new UInt (10)); 418 small.add (new UInt (100)); 419 small.add (new UInt (1000)); 420 small.add (new UInt (10000)); 421 422 int i = 0; 423 set_.iterator ().foreach ((obj) => 424 { 425 /* Fast-path: get() provides indexed access */ 426 assert (small[i] == obj); 427 i++; 428 return true; 429 }); 430 assert (i == 5); 431 432 /* Slow iteration: we don't know, syntactically, that set_ is a 433 * SmallSet, so we'll use the iterator */ 434 uint sum = 0; 435 foreach (var obj in set_) 436 sum += obj.u; 437 assert (sum == 11111); 438 439 /* Fast iteration: we do know, syntactically, that small is a 440 * SmallSet, so we'll use indexed access */ 441 sum = 0; 442 foreach (unowned UInt obj in small) 443 sum += obj.u; 444 assert (sum == 11111); 445 } 446} 447 448public int main (string[] args) 449{ 450 Test.init (ref args); 451 452 var tests = new SmallSetTests (); 453 tests.register (); 454 Test.run (); 455 tests.final_tear_down (); 456 457 return 0; 458} 459