release/src/router/tor/src/test/test_containers.c

   1 /* Copyright (c) 2001-2004, Roger Dingledine.
   2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   3  * Copyright (c) 2007-2013, The Tor Project, Inc. */
   4 /* See LICENSE for licensing information */
   5
   6 #include "orconfig.h"
   7 #include "or.h"
   8 #include "fp_pair.h"
   9 #include "test.h"
  10
  11 /** Helper: return a tristate based on comparing the strings in *<b>a</b> and
  12  * *<b>b</b>. */
  13 static int
  14 compare_strs_(const void **a, const void **b)
  15 {
  16   const char *s1 = *a, *s2 = *b;
  17   return strcmp(s1, s2);
  18 }
  19
  20 /** Helper: return a tristate based on comparing the strings in <b>a</b> and
  21  * *<b>b</b>. */
  22 static int
  23 compare_strs_for_bsearch_(const void *a, const void **b)
  24 {
  25   const char *s1 = a, *s2 = *b;
  26   return strcmp(s1, s2);
  27 }
  28
  29 /** Helper: return a tristate based on comparing the strings in *<b>a</b> and
  30  * *<b>b</b>, excluding a's first character, and ignoring case. */
  31 static int
  32 compare_without_first_ch_(const void *a, const void **b)
  33 {
  34   const char *s1 = a, *s2 = *b;
  35   return strcasecmp(s1+1, s2);
  36 }
  37
  38 /** Run unit tests for basic dynamic-sized array functionality. */
  39 static void
  40 test_container_smartlist_basic(void)
  41 {
  42   smartlist_t *sl;
  43
  44   /* XXXX test sort_digests, uniq_strings, uniq_digests */
  45
  46   /* Test smartlist add, del_keeporder, insert, get. */
  47   sl = smartlist_new();
  48   smartlist_add(sl, (void*)1);
  49   smartlist_add(sl, (void*)2);
  50   smartlist_add(sl, (void*)3);
  51   smartlist_add(sl, (void*)4);
  52   smartlist_del_keeporder(sl, 1);
  53   smartlist_insert(sl, 1, (void*)22);
  54   smartlist_insert(sl, 0, (void*)0);
  55   smartlist_insert(sl, 5, (void*)555);
  56   test_eq_ptr((void*)0,   smartlist_get(sl,0));
  57   test_eq_ptr((void*)1,   smartlist_get(sl,1));
  58   test_eq_ptr((void*)22,  smartlist_get(sl,2));
  59   test_eq_ptr((void*)3,   smartlist_get(sl,3));
  60   test_eq_ptr((void*)4,   smartlist_get(sl,4));
  61   test_eq_ptr((void*)555, smartlist_get(sl,5));
  62   /* Try deleting in the middle. */
  63   smartlist_del(sl, 1);
  64   test_eq_ptr((void*)555, smartlist_get(sl, 1));
  65   /* Try deleting at the end. */
  66   smartlist_del(sl, 4);
  67   test_eq(4, smartlist_len(sl));
  68
  69   /* test isin. */
  70   test_assert(smartlist_contains(sl, (void*)3));
  71   test_assert(!smartlist_contains(sl, (void*)99));
  72
  73  done:
  74   smartlist_free(sl);
  75 }
  76
  77 /** Run unit tests for smartlist-of-strings functionality. */
  78 static void
  79 test_container_smartlist_strings(void)
  80 {
  81   smartlist_t *sl = smartlist_new();
  82   char *cp=NULL, *cp_alloc=NULL;
  83   size_t sz;
  84
  85   /* Test split and join */
  86   test_eq(0, smartlist_len(sl));
  87   smartlist_split_string(sl, "abc", ":", 0, 0);
  88   test_eq(1, smartlist_len(sl));
  89   test_streq("abc", smartlist_get(sl, 0));
  90   smartlist_split_string(sl, "a::bc::", "::", 0, 0);
  91   test_eq(4, smartlist_len(sl));
  92   test_streq("a", smartlist_get(sl, 1));
  93   test_streq("bc", smartlist_get(sl, 2));
  94   test_streq("", smartlist_get(sl, 3));
  95   cp_alloc = smartlist_join_strings(sl, "", 0, NULL);
  96   test_streq(cp_alloc, "abcabc");
  97   tor_free(cp_alloc);
  98   cp_alloc = smartlist_join_strings(sl, "!", 0, NULL);
  99   test_streq(cp_alloc, "abc!a!bc!");
 100   tor_free(cp_alloc);
 101   cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
 102   test_streq(cp_alloc, "abcXYaXYbcXY");
 103   tor_free(cp_alloc);
 104   cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
 105   test_streq(cp_alloc, "abcXYaXYbcXYXY");
 106   tor_free(cp_alloc);
 107   cp_alloc = smartlist_join_strings(sl, "", 1, NULL);
 108   test_streq(cp_alloc, "abcabc");
 109   tor_free(cp_alloc);
 110
 111   smartlist_split_string(sl, "/def/  /ghijk", "/", 0, 0);
 112   test_eq(8, smartlist_len(sl));
 113   test_streq("", smartlist_get(sl, 4));
 114   test_streq("def", smartlist_get(sl, 5));
 115   test_streq("  ", smartlist_get(sl, 6));
 116   test_streq("ghijk", smartlist_get(sl, 7));
 117   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 118   smartlist_clear(sl);
 119
 120   smartlist_split_string(sl, "a,bbd,cdef", ",", SPLIT_SKIP_SPACE, 0);
 121   test_eq(3, smartlist_len(sl));
 122   test_streq("a", smartlist_get(sl,0));
 123   test_streq("bbd", smartlist_get(sl,1));
 124   test_streq("cdef", smartlist_get(sl,2));
 125   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
 126                          SPLIT_SKIP_SPACE, 0);
 127   test_eq(8, smartlist_len(sl));
 128   test_streq("z", smartlist_get(sl,3));
 129   test_streq("zhasd", smartlist_get(sl,4));
 130   test_streq("", smartlist_get(sl,5));
 131   test_streq("bnud", smartlist_get(sl,6));
 132   test_streq("", smartlist_get(sl,7));
 133
 134   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 135   smartlist_clear(sl);
 136
 137   smartlist_split_string(sl, " ab\tc \td ef  ", NULL,
 138                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 139   test_eq(4, smartlist_len(sl));
 140   test_streq("ab", smartlist_get(sl,0));
 141   test_streq("c", smartlist_get(sl,1));
 142   test_streq("d", smartlist_get(sl,2));
 143   test_streq("ef", smartlist_get(sl,3));
 144   smartlist_split_string(sl, "ghi\tj", NULL,
 145                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 146   test_eq(6, smartlist_len(sl));
 147   test_streq("ghi", smartlist_get(sl,4));
 148   test_streq("j", smartlist_get(sl,5));
 149
 150   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 151   smartlist_clear(sl);
 152
 153   cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
 154   test_streq(cp_alloc, "");
 155   tor_free(cp_alloc);
 156   cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
 157   test_streq(cp_alloc, "XY");
 158   tor_free(cp_alloc);
 159
 160   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
 161                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 162   test_eq(3, smartlist_len(sl));
 163   test_streq("z", smartlist_get(sl, 0));
 164   test_streq("zhasd", smartlist_get(sl, 1));
 165   test_streq("bnud", smartlist_get(sl, 2));
 166   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
 167                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 2);
 168   test_eq(5, smartlist_len(sl));
 169   test_streq("z", smartlist_get(sl, 3));
 170   test_streq("zhasd <>  <> bnud<>", smartlist_get(sl, 4));
 171   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 172   smartlist_clear(sl);
 173
 174   smartlist_split_string(sl, "abcd\n", "\n",
 175                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 176   test_eq(1, smartlist_len(sl));
 177   test_streq("abcd", smartlist_get(sl, 0));
 178   smartlist_split_string(sl, "efgh", "\n",
 179                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 180   test_eq(2, smartlist_len(sl));
 181   test_streq("efgh", smartlist_get(sl, 1));
 182
 183   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 184   smartlist_clear(sl);
 185
 186   /* Test swapping, shuffling, and sorting. */
 187   smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0);
 188   test_eq(7, smartlist_len(sl));
 189   smartlist_sort(sl, compare_strs_);
 190   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 191   test_streq(cp_alloc,"and,arma,by,nickm,onion,router,the");
 192   tor_free(cp_alloc);
 193   smartlist_swap(sl, 1, 5);
 194   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 195   test_streq(cp_alloc,"and,router,by,nickm,onion,arma,the");
 196   tor_free(cp_alloc);
 197   smartlist_shuffle(sl);
 198   test_eq(7, smartlist_len(sl));
 199   test_assert(smartlist_contains_string(sl, "and"));
 200   test_assert(smartlist_contains_string(sl, "router"));
 201   test_assert(smartlist_contains_string(sl, "by"));
 202   test_assert(smartlist_contains_string(sl, "nickm"));
 203   test_assert(smartlist_contains_string(sl, "onion"));
 204   test_assert(smartlist_contains_string(sl, "arma"));
 205   test_assert(smartlist_contains_string(sl, "the"));
 206
 207   /* Test bsearch. */
 208   smartlist_sort(sl, compare_strs_);
 209   test_streq("nickm", smartlist_bsearch(sl, "zNicKM",
 210                                         compare_without_first_ch_));
 211   test_streq("and", smartlist_bsearch(sl, " AND", compare_without_first_ch_));
 212   test_eq_ptr(NULL, smartlist_bsearch(sl, " ANz", compare_without_first_ch_));
 213
 214   /* Test bsearch_idx */
 215   {
 216     int f;
 217     smartlist_t *tmp = NULL;
 218
 219     test_eq(0, smartlist_bsearch_idx(sl," aaa",compare_without_first_ch_,&f));
 220     test_eq(f, 0);
 221     test_eq(0, smartlist_bsearch_idx(sl," and",compare_without_first_ch_,&f));
 222     test_eq(f, 1);
 223     test_eq(1, smartlist_bsearch_idx(sl," arm",compare_without_first_ch_,&f));
 224     test_eq(f, 0);
 225     test_eq(1, smartlist_bsearch_idx(sl," arma",compare_without_first_ch_,&f));
 226     test_eq(f, 1);
 227     test_eq(2, smartlist_bsearch_idx(sl," armb",compare_without_first_ch_,&f));
 228     test_eq(f, 0);
 229     test_eq(7, smartlist_bsearch_idx(sl," zzzz",compare_without_first_ch_,&f));
 230     test_eq(f, 0);
 231
 232     /* Test trivial cases for list of length 0 or 1 */
 233     tmp = smartlist_new();
 234     test_eq(0, smartlist_bsearch_idx(tmp, "foo",
 235                                      compare_strs_for_bsearch_, &f));
 236     test_eq(f, 0);
 237     smartlist_insert(tmp, 0, (void *)("bar"));
 238     test_eq(1, smartlist_bsearch_idx(tmp, "foo",
 239                                      compare_strs_for_bsearch_, &f));
 240     test_eq(f, 0);
 241     test_eq(0, smartlist_bsearch_idx(tmp, "aaa",
 242                                      compare_strs_for_bsearch_, &f));
 243     test_eq(f, 0);
 244     test_eq(0, smartlist_bsearch_idx(tmp, "bar",
 245                                      compare_strs_for_bsearch_, &f));
 246     test_eq(f, 1);
 247     /* ... and one for length 2 */
 248     smartlist_insert(tmp, 1, (void *)("foo"));
 249     test_eq(1, smartlist_bsearch_idx(tmp, "foo",
 250                                      compare_strs_for_bsearch_, &f));
 251     test_eq(f, 1);
 252     test_eq(2, smartlist_bsearch_idx(tmp, "goo",
 253                                      compare_strs_for_bsearch_, &f));
 254     test_eq(f, 0);
 255     smartlist_free(tmp);
 256   }
 257
 258   /* Test reverse() and pop_last() */
 259   smartlist_reverse(sl);
 260   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 261   test_streq(cp_alloc,"the,router,onion,nickm,by,arma,and");
 262   tor_free(cp_alloc);
 263   cp_alloc = smartlist_pop_last(sl);
 264   test_streq(cp_alloc, "and");
 265   tor_free(cp_alloc);
 266   test_eq(smartlist_len(sl), 6);
 267   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 268   smartlist_clear(sl);
 269   cp_alloc = smartlist_pop_last(sl);
 270   test_eq_ptr(cp_alloc, NULL);
 271
 272   /* Test uniq() */
 273   smartlist_split_string(sl,
 274                      "50,noon,radar,a,man,a,plan,a,canal,panama,radar,noon,50",
 275                      ",", 0, 0);
 276   smartlist_sort(sl, compare_strs_);
 277   smartlist_uniq(sl, compare_strs_, tor_free_);
 278   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 279   test_streq(cp_alloc, "50,a,canal,man,noon,panama,plan,radar");
 280   tor_free(cp_alloc);
 281
 282   /* Test contains_string, contains_string_case and contains_int_as_string */
 283   test_assert(smartlist_contains_string(sl, "noon"));
 284   test_assert(!smartlist_contains_string(sl, "noonoon"));
 285   test_assert(smartlist_contains_string_case(sl, "nOOn"));
 286   test_assert(!smartlist_contains_string_case(sl, "nooNooN"));
 287   test_assert(smartlist_contains_int_as_string(sl, 50));
 288   test_assert(!smartlist_contains_int_as_string(sl, 60));
 289
 290   /* Test smartlist_choose */
 291   {
 292     int i;
 293     int allsame = 1;
 294     int allin = 1;
 295     void *first = smartlist_choose(sl);
 296     test_assert(smartlist_contains(sl, first));
 297     for (i = 0; i < 100; ++i) {
 298       void *second = smartlist_choose(sl);
 299       if (second != first)
 300         allsame = 0;
 301       if (!smartlist_contains(sl, second))
 302         allin = 0;
 303     }
 304     test_assert(!allsame);
 305     test_assert(allin);
 306   }
 307   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 308   smartlist_clear(sl);
 309
 310   /* Test string_remove and remove and join_strings2 */
 311   smartlist_split_string(sl,
 312                     "Some say the Earth will end in ice and some in fire",
 313                     " ", 0, 0);
 314   cp = smartlist_get(sl, 4);
 315   test_streq(cp, "will");
 316   smartlist_add(sl, cp);
 317   smartlist_remove(sl, cp);
 318   tor_free(cp);
 319   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 320   test_streq(cp_alloc, "Some,say,the,Earth,fire,end,in,ice,and,some,in");
 321   tor_free(cp_alloc);
 322   smartlist_string_remove(sl, "in");
 323   cp_alloc = smartlist_join_strings2(sl, "+XX", 1, 0, &sz);
 324   test_streq(cp_alloc, "Some+say+the+Earth+fire+end+some+ice+and");
 325   test_eq((int)sz, 40);
 326
 327  done:
 328
 329   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 330   smartlist_free(sl);
 331   tor_free(cp_alloc);
 332 }
 333
 334 /** Run unit tests for smartlist set manipulation functions. */
 335 static void
 336 test_container_smartlist_overlap(void)
 337 {
 338   smartlist_t *sl = smartlist_new();
 339   smartlist_t *ints = smartlist_new();
 340   smartlist_t *odds = smartlist_new();
 341   smartlist_t *evens = smartlist_new();
 342   smartlist_t *primes = smartlist_new();
 343   int i;
 344   for (i=1; i < 10; i += 2)
 345     smartlist_add(odds, (void*)(uintptr_t)i);
 346   for (i=0; i < 10; i += 2)
 347     smartlist_add(evens, (void*)(uintptr_t)i);
 348
 349   /* add_all */
 350   smartlist_add_all(ints, odds);
 351   smartlist_add_all(ints, evens);
 352   test_eq(smartlist_len(ints), 10);
 353
 354   smartlist_add(primes, (void*)2);
 355   smartlist_add(primes, (void*)3);
 356   smartlist_add(primes, (void*)5);
 357   smartlist_add(primes, (void*)7);
 358
 359   /* overlap */
 360   test_assert(smartlist_overlap(ints, odds));
 361   test_assert(smartlist_overlap(odds, primes));
 362   test_assert(smartlist_overlap(evens, primes));
 363   test_assert(!smartlist_overlap(odds, evens));
 364
 365   /* intersect */
 366   smartlist_add_all(sl, odds);
 367   smartlist_intersect(sl, primes);
 368   test_eq(smartlist_len(sl), 3);
 369   test_assert(smartlist_contains(sl, (void*)3));
 370   test_assert(smartlist_contains(sl, (void*)5));
 371   test_assert(smartlist_contains(sl, (void*)7));
 372
 373   /* subtract */
 374   smartlist_add_all(sl, primes);
 375   smartlist_subtract(sl, odds);
 376   test_eq(smartlist_len(sl), 1);
 377   test_assert(smartlist_contains(sl, (void*)2));
 378
 379  done:
 380   smartlist_free(odds);
 381   smartlist_free(evens);
 382   smartlist_free(ints);
 383   smartlist_free(primes);
 384   smartlist_free(sl);
 385 }
 386
 387 /** Run unit tests for smartlist-of-digests functions. */
 388 static void
 389 test_container_smartlist_digests(void)
 390 {
 391   smartlist_t *sl = smartlist_new();
 392
 393   /* contains_digest */
 394   smartlist_add(sl, tor_memdup("AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN));
 395   smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
 396   smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
 397   test_eq(0, smartlist_contains_digest(NULL, "AAAAAAAAAAAAAAAAAAAA"));
 398   test_assert(smartlist_contains_digest(sl, "AAAAAAAAAAAAAAAAAAAA"));
 399   test_assert(smartlist_contains_digest(sl, "\00090AAB2AAAAaasdAAAAA"));
 400   test_eq(0, smartlist_contains_digest(sl, "\00090AAB2AAABaasdAAAAA"));
 401
 402   /* sort digests */
 403   smartlist_sort_digests(sl);
 404   test_memeq(smartlist_get(sl, 0), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
 405   test_memeq(smartlist_get(sl, 1), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
 406   test_memeq(smartlist_get(sl, 2), "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
 407   test_eq(3, smartlist_len(sl));
 408
 409   /* uniq_digests */
 410   smartlist_uniq_digests(sl);
 411   test_eq(2, smartlist_len(sl));
 412   test_memeq(smartlist_get(sl, 0), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
 413   test_memeq(smartlist_get(sl, 1), "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
 414
 415  done:
 416   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 417   smartlist_free(sl);
 418 }
 419
 420 /** Run unit tests for concatenate-a-smartlist-of-strings functions. */
 421 static void
 422 test_container_smartlist_join(void)
 423 {
 424   smartlist_t *sl = smartlist_new();
 425   smartlist_t *sl2 = smartlist_new(), *sl3 = smartlist_new(),
 426     *sl4 = smartlist_new();
 427   char *joined=NULL;
 428   /* unique, sorted. */
 429   smartlist_split_string(sl,
 430                          "Abashments Ambush Anchorman Bacon Banks Borscht "
 431                          "Bunks Inhumane Insurance Knish Know Manners "
 432                          "Maraschinos Stamina Sunbonnets Unicorns Wombats",
 433                          " ", 0, 0);
 434   /* non-unique, sorted. */
 435   smartlist_split_string(sl2,
 436                          "Ambush Anchorman Anchorman Anemias Anemias Bacon "
 437                          "Crossbowmen Inhumane Insurance Knish Know Manners "
 438                          "Manners Maraschinos Wombats Wombats Work",
 439                          " ", 0, 0);
 440   SMARTLIST_FOREACH_JOIN(sl, char *, cp1,
 441                          sl2, char *, cp2,
 442                          strcmp(cp1,cp2),
 443                          smartlist_add(sl3, cp2)) {
 444     test_streq(cp1, cp2);
 445     smartlist_add(sl4, cp1);
 446   } SMARTLIST_FOREACH_JOIN_END(cp1, cp2);
 447
 448   SMARTLIST_FOREACH(sl3, const char *, cp,
 449                     test_assert(smartlist_contains(sl2, cp) &&
 450                                 !smartlist_contains_string(sl, cp)));
 451   SMARTLIST_FOREACH(sl4, const char *, cp,
 452                     test_assert(smartlist_contains(sl, cp) &&
 453                                 smartlist_contains_string(sl2, cp)));
 454   joined = smartlist_join_strings(sl3, ",", 0, NULL);
 455   test_streq(joined, "Anemias,Anemias,Crossbowmen,Work");
 456   tor_free(joined);
 457   joined = smartlist_join_strings(sl4, ",", 0, NULL);
 458   test_streq(joined, "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance,"
 459              "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats");
 460   tor_free(joined);
 461
 462  done:
 463   smartlist_free(sl4);
 464   smartlist_free(sl3);
 465   SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp));
 466   smartlist_free(sl2);
 467   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 468   smartlist_free(sl);
 469   tor_free(joined);
 470 }
 471
 472 static void
 473 test_container_smartlist_ints_eq(void *arg)
 474 {
 475   smartlist_t *sl1 = NULL, *sl2 = NULL;
 476   int x;
 477   (void)arg;
 478
 479   tt_assert(smartlist_ints_eq(NULL, NULL));
 480
 481   sl1 = smartlist_new();
 482   tt_assert(!smartlist_ints_eq(sl1, NULL));
 483   tt_assert(!smartlist_ints_eq(NULL, sl1));
 484
 485   sl2 = smartlist_new();
 486   tt_assert(smartlist_ints_eq(sl1, sl2));
 487
 488   x = 5;
 489   smartlist_add(sl1, tor_memdup(&x, sizeof(int)));
 490   smartlist_add(sl2, tor_memdup(&x, sizeof(int)));
 491   x = 90;
 492   smartlist_add(sl1, tor_memdup(&x, sizeof(int)));
 493   smartlist_add(sl2, tor_memdup(&x, sizeof(int)));
 494   tt_assert(smartlist_ints_eq(sl1, sl2));
 495
 496   x = -50;
 497   smartlist_add(sl1, tor_memdup(&x, sizeof(int)));
 498   tt_assert(! smartlist_ints_eq(sl1, sl2));
 499   tt_assert(! smartlist_ints_eq(sl2, sl1));
 500   smartlist_add(sl2, tor_memdup(&x, sizeof(int)));
 501   tt_assert(smartlist_ints_eq(sl1, sl2));
 502
 503   *(int*)smartlist_get(sl1, 1) = 101010;
 504   tt_assert(! smartlist_ints_eq(sl2, sl1));
 505   *(int*)smartlist_get(sl2, 1) = 101010;
 506   tt_assert(smartlist_ints_eq(sl1, sl2));
 507
 508  done:
 509   if (sl1)
 510     SMARTLIST_FOREACH(sl1, int *, ip, tor_free(ip));
 511   if (sl2)
 512     SMARTLIST_FOREACH(sl2, int *, ip, tor_free(ip));
 513   smartlist_free(sl1);
 514   smartlist_free(sl2);
 515 }
 516
 517 /** Run unit tests for bitarray code */
 518 static void
 519 test_container_bitarray(void)
 520 {
 521   bitarray_t *ba = NULL;
 522   int i, j, ok=1;
 523
 524   ba = bitarray_init_zero(1);
 525   test_assert(ba);
 526   test_assert(! bitarray_is_set(ba, 0));
 527   bitarray_set(ba, 0);
 528   test_assert(bitarray_is_set(ba, 0));
 529   bitarray_clear(ba, 0);
 530   test_assert(! bitarray_is_set(ba, 0));
 531   bitarray_free(ba);
 532
 533   ba = bitarray_init_zero(1023);
 534   for (i = 1; i < 64; ) {
 535     for (j = 0; j < 1023; ++j) {
 536       if (j % i)
 537         bitarray_set(ba, j);
 538       else
 539         bitarray_clear(ba, j);
 540     }
 541     for (j = 0; j < 1023; ++j) {
 542       if (!bool_eq(bitarray_is_set(ba, j), j%i))
 543         ok = 0;
 544     }
 545     test_assert(ok);
 546     if (i < 7)
 547       ++i;
 548     else if (i == 28)
 549       i = 32;
 550     else
 551       i += 7;
 552   }
 553
 554  done:
 555   if (ba)
 556     bitarray_free(ba);
 557 }
 558
 559 /** Run unit tests for digest set code (implemented as a hashtable or as a
 560  * bloom filter) */
 561 static void
 562 test_container_digestset(void)
 563 {
 564   smartlist_t *included = smartlist_new();
 565   char d[DIGEST_LEN];
 566   int i;
 567   int ok = 1;
 568   int false_positives = 0;
 569   digestset_t *set = NULL;
 570
 571   for (i = 0; i < 1000; ++i) {
 572     crypto_rand(d, DIGEST_LEN);
 573     smartlist_add(included, tor_memdup(d, DIGEST_LEN));
 574   }
 575   set = digestset_new(1000);
 576   SMARTLIST_FOREACH(included, const char *, cp,
 577                     if (digestset_contains(set, cp))
 578                       ok = 0);
 579   test_assert(ok);
 580   SMARTLIST_FOREACH(included, const char *, cp,
 581                     digestset_add(set, cp));
 582   SMARTLIST_FOREACH(included, const char *, cp,
 583                     if (!digestset_contains(set, cp))
 584                       ok = 0);
 585   test_assert(ok);
 586   for (i = 0; i < 1000; ++i) {
 587     crypto_rand(d, DIGEST_LEN);
 588     if (digestset_contains(set, d))
 589       ++false_positives;
 590   }
 591   test_assert(false_positives < 50); /* Should be far lower. */
 592
 593  done:
 594   if (set)
 595     digestset_free(set);
 596   SMARTLIST_FOREACH(included, char *, cp, tor_free(cp));
 597   smartlist_free(included);
 598 }
 599
 600 typedef struct pq_entry_t {
 601   const char *val;
 602   int idx;
 603 } pq_entry_t;
 604
 605 /** Helper: return a tristate based on comparing two pq_entry_t values. */
 606 static int
 607 compare_strings_for_pqueue_(const void *p1, const void *p2)
 608 {
 609   const pq_entry_t *e1=p1, *e2=p2;
 610   return strcmp(e1->val, e2->val);
 611 }
 612
 613 /** Run unit tests for heap-based priority queue functions. */
 614 static void
 615 test_container_pqueue(void)
 616 {
 617   smartlist_t *sl = smartlist_new();
 618   int (*cmp)(const void *, const void*);
 619   const int offset = STRUCT_OFFSET(pq_entry_t, idx);
 620 #define ENTRY(s) pq_entry_t s = { #s, -1 }
 621   ENTRY(cows);
 622   ENTRY(zebras);
 623   ENTRY(fish);
 624   ENTRY(frogs);
 625   ENTRY(apples);
 626   ENTRY(squid);
 627   ENTRY(daschunds);
 628   ENTRY(eggplants);
 629   ENTRY(weissbier);
 630   ENTRY(lobsters);
 631   ENTRY(roquefort);
 632   ENTRY(chinchillas);
 633   ENTRY(fireflies);
 634
 635 #define OK() smartlist_pqueue_assert_ok(sl, cmp, offset)
 636
 637   cmp = compare_strings_for_pqueue_;
 638   smartlist_pqueue_add(sl, cmp, offset, &cows);
 639   smartlist_pqueue_add(sl, cmp, offset, &zebras);
 640   smartlist_pqueue_add(sl, cmp, offset, &fish);
 641   smartlist_pqueue_add(sl, cmp, offset, &frogs);
 642   smartlist_pqueue_add(sl, cmp, offset, &apples);
 643   smartlist_pqueue_add(sl, cmp, offset, &squid);
 644   smartlist_pqueue_add(sl, cmp, offset, &daschunds);
 645   smartlist_pqueue_add(sl, cmp, offset, &eggplants);
 646   smartlist_pqueue_add(sl, cmp, offset, &weissbier);
 647   smartlist_pqueue_add(sl, cmp, offset, &lobsters);
 648   smartlist_pqueue_add(sl, cmp, offset, &roquefort);
 649
 650   OK();
 651
 652   test_eq(smartlist_len(sl), 11);
 653   test_eq_ptr(smartlist_get(sl, 0), &apples);
 654   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &apples);
 655   test_eq(smartlist_len(sl), 10);
 656   OK();
 657   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &cows);
 658   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &daschunds);
 659   smartlist_pqueue_add(sl, cmp, offset, &chinchillas);
 660   OK();
 661   smartlist_pqueue_add(sl, cmp, offset, &fireflies);
 662   OK();
 663   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &chinchillas);
 664   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &eggplants);
 665   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fireflies);
 666   OK();
 667   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fish);
 668   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &frogs);
 669   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &lobsters);
 670   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &roquefort);
 671   OK();
 672   test_eq(smartlist_len(sl), 3);
 673   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &squid);
 674   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &weissbier);
 675   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &zebras);
 676   test_eq(smartlist_len(sl), 0);
 677   OK();
 678
 679   /* Now test remove. */
 680   smartlist_pqueue_add(sl, cmp, offset, &cows);
 681   smartlist_pqueue_add(sl, cmp, offset, &fish);
 682   smartlist_pqueue_add(sl, cmp, offset, &frogs);
 683   smartlist_pqueue_add(sl, cmp, offset, &apples);
 684   smartlist_pqueue_add(sl, cmp, offset, &squid);
 685   smartlist_pqueue_add(sl, cmp, offset, &zebras);
 686   test_eq(smartlist_len(sl), 6);
 687   OK();
 688   smartlist_pqueue_remove(sl, cmp, offset, &zebras);
 689   test_eq(smartlist_len(sl), 5);
 690   OK();
 691   smartlist_pqueue_remove(sl, cmp, offset, &cows);
 692   test_eq(smartlist_len(sl), 4);
 693   OK();
 694   smartlist_pqueue_remove(sl, cmp, offset, &apples);
 695   test_eq(smartlist_len(sl), 3);
 696   OK();
 697   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fish);
 698   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &frogs);
 699   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &squid);
 700   test_eq(smartlist_len(sl), 0);
 701   OK();
 702
 703 #undef OK
 704
 705  done:
 706
 707   smartlist_free(sl);
 708 }
 709
 710 /** Run unit tests for string-to-void* map functions */
 711 static void
 712 test_container_strmap(void)
 713 {
 714   strmap_t *map;
 715   strmap_iter_t *iter;
 716   const char *k;
 717   void *v;
 718   char *visited = NULL;
 719   smartlist_t *found_keys = NULL;
 720
 721   map = strmap_new();
 722   test_assert(map);
 723   test_eq(strmap_size(map), 0);
 724   test_assert(strmap_isempty(map));
 725   v = strmap_set(map, "K1", (void*)99);
 726   test_eq_ptr(v, NULL);
 727   test_assert(!strmap_isempty(map));
 728   v = strmap_set(map, "K2", (void*)101);
 729   test_eq_ptr(v, NULL);
 730   v = strmap_set(map, "K1", (void*)100);
 731   test_eq_ptr(v, (void*)99);
 732   test_eq_ptr(strmap_get(map,"K1"), (void*)100);
 733   test_eq_ptr(strmap_get(map,"K2"), (void*)101);
 734   test_eq_ptr(strmap_get(map,"K-not-there"), NULL);
 735   strmap_assert_ok(map);
 736
 737   v = strmap_remove(map,"K2");
 738   strmap_assert_ok(map);
 739   test_eq_ptr(v, (void*)101);
 740   test_eq_ptr(strmap_get(map,"K2"), NULL);
 741   test_eq_ptr(strmap_remove(map,"K2"), NULL);
 742
 743   strmap_set(map, "K2", (void*)101);
 744   strmap_set(map, "K3", (void*)102);
 745   strmap_set(map, "K4", (void*)103);
 746   test_eq(strmap_size(map), 4);
 747   strmap_assert_ok(map);
 748   strmap_set(map, "K5", (void*)104);
 749   strmap_set(map, "K6", (void*)105);
 750   strmap_assert_ok(map);
 751
 752   /* Test iterator. */
 753   iter = strmap_iter_init(map);
 754   found_keys = smartlist_new();
 755   while (!strmap_iter_done(iter)) {
 756     strmap_iter_get(iter,&k,&v);
 757     smartlist_add(found_keys, tor_strdup(k));
 758     test_eq_ptr(v, strmap_get(map, k));
 759
 760     if (!strcmp(k, "K2")) {
 761       iter = strmap_iter_next_rmv(map,iter);
 762     } else {
 763       iter = strmap_iter_next(map,iter);
 764     }
 765   }
 766
 767   /* Make sure we removed K2, but not the others. */
 768   test_eq_ptr(strmap_get(map, "K2"), NULL);
 769   test_eq_ptr(strmap_get(map, "K5"), (void*)104);
 770   /* Make sure we visited everyone once */
 771   smartlist_sort_strings(found_keys);
 772   visited = smartlist_join_strings(found_keys, ":", 0, NULL);
 773   test_streq(visited, "K1:K2:K3:K4:K5:K6");
 774
 775   strmap_assert_ok(map);
 776   /* Clean up after ourselves. */
 777   strmap_free(map, NULL);
 778   map = NULL;
 779
 780   /* Now try some lc functions. */
 781   map = strmap_new();
 782   strmap_set_lc(map,"Ab.C", (void*)1);
 783   test_eq_ptr(strmap_get(map,"ab.c"), (void*)1);
 784   strmap_assert_ok(map);
 785   test_eq_ptr(strmap_get_lc(map,"AB.C"), (void*)1);
 786   test_eq_ptr(strmap_get(map,"AB.C"), NULL);
 787   test_eq_ptr(strmap_remove_lc(map,"aB.C"), (void*)1);
 788   strmap_assert_ok(map);
 789   test_eq_ptr(strmap_get_lc(map,"AB.C"), NULL);
 790
 791  done:
 792   if (map)
 793     strmap_free(map,NULL);
 794   if (found_keys) {
 795     SMARTLIST_FOREACH(found_keys, char *, cp, tor_free(cp));
 796     smartlist_free(found_keys);
 797   }
 798   tor_free(visited);
 799 }
 800
 801 /** Run unit tests for getting the median of a list. */
 802 static void
 803 test_container_order_functions(void)
 804 {
 805   int lst[25], n = 0;
 806   //  int a=12,b=24,c=25,d=60,e=77;
 807
 808 #define median() median_int(lst, n)
 809
 810   lst[n++] = 12;
 811   test_eq(12, median()); /* 12 */
 812   lst[n++] = 77;
 813   //smartlist_shuffle(sl);
 814   test_eq(12, median()); /* 12, 77 */
 815   lst[n++] = 77;
 816   //smartlist_shuffle(sl);
 817   test_eq(77, median()); /* 12, 77, 77 */
 818   lst[n++] = 24;
 819   test_eq(24, median()); /* 12,24,77,77 */
 820   lst[n++] = 60;
 821   lst[n++] = 12;
 822   lst[n++] = 25;
 823   //smartlist_shuffle(sl);
 824   test_eq(25, median()); /* 12,12,24,25,60,77,77 */
 825 #undef median
 826
 827  done:
 828   ;
 829 }
 830
 831 static void
 832 test_container_di_map(void *arg)
 833 {
 834   di_digest256_map_t *map = NULL;
 835   const uint8_t key1[] = "In view of the fact that it was ";
 836   const uint8_t key2[] = "superficially convincing, being ";
 837   const uint8_t key3[] = "properly enciphered in a one-tim";
 838   const uint8_t key4[] = "e cipher scheduled for use today";
 839   char *v1 = tor_strdup(", it came close to causing a disaster...");
 840   char *v2 = tor_strdup("I regret to have to advise you that the mission");
 841   char *v3 = tor_strdup("was actually initiated...");
 842   /* -- John Brunner, _The Shockwave Rider_ */
 843
 844   (void)arg;
 845
 846   /* Try searching on an empty map. */
 847   tt_ptr_op(NULL, ==, dimap_search(map, key1, NULL));
 848   tt_ptr_op(NULL, ==, dimap_search(map, key2, NULL));
 849   tt_ptr_op(v3, ==, dimap_search(map, key2, v3));
 850   dimap_free(map, NULL);
 851   map = NULL;
 852
 853   /* Add a single entry. */
 854   dimap_add_entry(&map, key1, v1);
 855   tt_ptr_op(NULL, ==, dimap_search(map, key2, NULL));
 856   tt_ptr_op(v3, ==, dimap_search(map, key2, v3));
 857   tt_ptr_op(v1, ==, dimap_search(map, key1, NULL));
 858
 859   /* Now try it with three entries in the map. */
 860   dimap_add_entry(&map, key2, v2);
 861   dimap_add_entry(&map, key3, v3);
 862   tt_ptr_op(v1, ==, dimap_search(map, key1, NULL));
 863   tt_ptr_op(v2, ==, dimap_search(map, key2, NULL));
 864   tt_ptr_op(v3, ==, dimap_search(map, key3, NULL));
 865   tt_ptr_op(NULL, ==, dimap_search(map, key4, NULL));
 866   tt_ptr_op(v1, ==, dimap_search(map, key4, v1));
 867
 868  done:
 869   tor_free(v1);
 870   tor_free(v2);
 871   tor_free(v3);
 872   dimap_free(map, NULL);
 873 }
 874
 875 /** Run unit tests for fp_pair-to-void* map functions */
 876 static void
 877 test_container_fp_pair_map(void)
 878 {
 879   fp_pair_map_t *map;
 880   fp_pair_t fp1, fp2, fp3, fp4, fp5, fp6;
 881   void *v;
 882   fp_pair_map_iter_t *iter;
 883   fp_pair_t k;
 884
 885   map = fp_pair_map_new();
 886   test_assert(map);
 887   test_eq(fp_pair_map_size(map), 0);
 888   test_assert(fp_pair_map_isempty(map));
 889
 890   memset(fp1.first, 0x11, DIGEST_LEN);
 891   memset(fp1.second, 0x12, DIGEST_LEN);
 892   memset(fp2.first, 0x21, DIGEST_LEN);
 893   memset(fp2.second, 0x22, DIGEST_LEN);
 894   memset(fp3.first, 0x31, DIGEST_LEN);
 895   memset(fp3.second, 0x32, DIGEST_LEN);
 896   memset(fp4.first, 0x41, DIGEST_LEN);
 897   memset(fp4.second, 0x42, DIGEST_LEN);
 898   memset(fp5.first, 0x51, DIGEST_LEN);
 899   memset(fp5.second, 0x52, DIGEST_LEN);
 900   memset(fp6.first, 0x61, DIGEST_LEN);
 901   memset(fp6.second, 0x62, DIGEST_LEN);
 902
 903   v = fp_pair_map_set(map, &fp1, (void*)99);
 904   tt_ptr_op(v, ==, NULL);
 905   test_assert(!fp_pair_map_isempty(map));
 906   v = fp_pair_map_set(map, &fp2, (void*)101);
 907   tt_ptr_op(v, ==, NULL);
 908   v = fp_pair_map_set(map, &fp1, (void*)100);
 909   tt_ptr_op(v, ==, (void*)99);
 910   test_eq_ptr(fp_pair_map_get(map, &fp1), (void*)100);
 911   test_eq_ptr(fp_pair_map_get(map, &fp2), (void*)101);
 912   test_eq_ptr(fp_pair_map_get(map, &fp3), NULL);
 913   fp_pair_map_assert_ok(map);
 914
 915   v = fp_pair_map_remove(map, &fp2);
 916   fp_pair_map_assert_ok(map);
 917   test_eq_ptr(v, (void*)101);
 918   test_eq_ptr(fp_pair_map_get(map, &fp2), NULL);
 919   test_eq_ptr(fp_pair_map_remove(map, &fp2), NULL);
 920
 921   fp_pair_map_set(map, &fp2, (void*)101);
 922   fp_pair_map_set(map, &fp3, (void*)102);
 923   fp_pair_map_set(map, &fp4, (void*)103);
 924   test_eq(fp_pair_map_size(map), 4);
 925   fp_pair_map_assert_ok(map);
 926   fp_pair_map_set(map, &fp5, (void*)104);
 927   fp_pair_map_set(map, &fp6, (void*)105);
 928   fp_pair_map_assert_ok(map);
 929
 930   /* Test iterator. */
 931   iter = fp_pair_map_iter_init(map);
 932   while (!fp_pair_map_iter_done(iter)) {
 933     fp_pair_map_iter_get(iter, &k, &v);
 934     test_eq_ptr(v, fp_pair_map_get(map, &k));
 935
 936     if (tor_memeq(&fp2, &k, sizeof(fp2))) {
 937       iter = fp_pair_map_iter_next_rmv(map, iter);
 938     } else {
 939       iter = fp_pair_map_iter_next(map, iter);
 940     }
 941   }
 942
 943   /* Make sure we removed fp2, but not the others. */
 944   test_eq_ptr(fp_pair_map_get(map, &fp2), NULL);
 945   test_eq_ptr(fp_pair_map_get(map, &fp5), (void*)104);
 946
 947   fp_pair_map_assert_ok(map);
 948   /* Clean up after ourselves. */
 949   fp_pair_map_free(map, NULL);
 950   map = NULL;
 951
 952  done:
 953   if (map)
 954     fp_pair_map_free(map, NULL);
 955 }
 956
 957 #define CONTAINER_LEGACY(name)                                          \
 958   { #name, legacy_test_helper, 0, &legacy_setup, test_container_ ## name }
 959
 960 #define CONTAINER(name, flags)                                          \
 961   { #name, test_container_ ## name, (flags), NULL, NULL }
 962
 963 struct testcase_t container_tests[] = {
 964   CONTAINER_LEGACY(smartlist_basic),
 965   CONTAINER_LEGACY(smartlist_strings),
 966   CONTAINER_LEGACY(smartlist_overlap),
 967   CONTAINER_LEGACY(smartlist_digests),
 968   CONTAINER_LEGACY(smartlist_join),
 969   CONTAINER(smartlist_ints_eq, 0),
 970   CONTAINER_LEGACY(bitarray),
 971   CONTAINER_LEGACY(digestset),
 972   CONTAINER_LEGACY(strmap),
 973   CONTAINER_LEGACY(pqueue),
 974   CONTAINER_LEGACY(order_functions),
 975   CONTAINER(di_map, 0),
 976   CONTAINER_LEGACY(fp_pair_map),
 977   END_OF_TESTCASES
 978 };
 979