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-2011, The Tor Project, Inc. */
   4 /* See LICENSE for licensing information */
   5
   6 #include "orconfig.h"
   7 #include "or.h"
   8 #include "test.h"
   9
  10 /** Helper: return a tristate based on comparing the strings in *<b>a</b> and
  11  * *<b>b</b>. */
  12 static int
  13 _compare_strs(const void **a, const void **b)
  14 {
  15   const char *s1 = *a, *s2 = *b;
  16   return strcmp(s1, s2);
  17 }
  18
  19 /** Helper: return a tristate based on comparing the strings in *<b>a</b> and
  20  * *<b>b</b>, excluding a's first character, and ignoring case. */
  21 static int
  22 _compare_without_first_ch(const void *a, const void **b)
  23 {
  24   const char *s1 = a, *s2 = *b;
  25   return strcasecmp(s1+1, s2);
  26 }
  27
  28 /** Run unit tests for basic dynamic-sized array functionality. */
  29 static void
  30 test_container_smartlist_basic(void)
  31 {
  32   smartlist_t *sl;
  33
  34   /* XXXX test sort_digests, uniq_strings, uniq_digests */
  35
  36   /* Test smartlist add, del_keeporder, insert, get. */
  37   sl = smartlist_create();
  38   smartlist_add(sl, (void*)1);
  39   smartlist_add(sl, (void*)2);
  40   smartlist_add(sl, (void*)3);
  41   smartlist_add(sl, (void*)4);
  42   smartlist_del_keeporder(sl, 1);
  43   smartlist_insert(sl, 1, (void*)22);
  44   smartlist_insert(sl, 0, (void*)0);
  45   smartlist_insert(sl, 5, (void*)555);
  46   test_eq_ptr((void*)0,   smartlist_get(sl,0));
  47   test_eq_ptr((void*)1,   smartlist_get(sl,1));
  48   test_eq_ptr((void*)22,  smartlist_get(sl,2));
  49   test_eq_ptr((void*)3,   smartlist_get(sl,3));
  50   test_eq_ptr((void*)4,   smartlist_get(sl,4));
  51   test_eq_ptr((void*)555, smartlist_get(sl,5));
  52   /* Try deleting in the middle. */
  53   smartlist_del(sl, 1);
  54   test_eq_ptr((void*)555, smartlist_get(sl, 1));
  55   /* Try deleting at the end. */
  56   smartlist_del(sl, 4);
  57   test_eq(4, smartlist_len(sl));
  58
  59   /* test isin. */
  60   test_assert(smartlist_isin(sl, (void*)3));
  61   test_assert(!smartlist_isin(sl, (void*)99));
  62
  63  done:
  64   smartlist_free(sl);
  65 }
  66
  67 /** Run unit tests for smartlist-of-strings functionality. */
  68 static void
  69 test_container_smartlist_strings(void)
  70 {
  71   smartlist_t *sl = smartlist_create();
  72   char *cp=NULL, *cp_alloc=NULL;
  73   size_t sz;
  74
  75   /* Test split and join */
  76   test_eq(0, smartlist_len(sl));
  77   smartlist_split_string(sl, "abc", ":", 0, 0);
  78   test_eq(1, smartlist_len(sl));
  79   test_streq("abc", smartlist_get(sl, 0));
  80   smartlist_split_string(sl, "a::bc::", "::", 0, 0);
  81   test_eq(4, smartlist_len(sl));
  82   test_streq("a", smartlist_get(sl, 1));
  83   test_streq("bc", smartlist_get(sl, 2));
  84   test_streq("", smartlist_get(sl, 3));
  85   cp_alloc = smartlist_join_strings(sl, "", 0, NULL);
  86   test_streq(cp_alloc, "abcabc");
  87   tor_free(cp_alloc);
  88   cp_alloc = smartlist_join_strings(sl, "!", 0, NULL);
  89   test_streq(cp_alloc, "abc!a!bc!");
  90   tor_free(cp_alloc);
  91   cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
  92   test_streq(cp_alloc, "abcXYaXYbcXY");
  93   tor_free(cp_alloc);
  94   cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
  95   test_streq(cp_alloc, "abcXYaXYbcXYXY");
  96   tor_free(cp_alloc);
  97   cp_alloc = smartlist_join_strings(sl, "", 1, NULL);
  98   test_streq(cp_alloc, "abcabc");
  99   tor_free(cp_alloc);
 100
 101   smartlist_split_string(sl, "/def/  /ghijk", "/", 0, 0);
 102   test_eq(8, smartlist_len(sl));
 103   test_streq("", smartlist_get(sl, 4));
 104   test_streq("def", smartlist_get(sl, 5));
 105   test_streq("  ", smartlist_get(sl, 6));
 106   test_streq("ghijk", smartlist_get(sl, 7));
 107   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 108   smartlist_clear(sl);
 109
 110   smartlist_split_string(sl, "a,bbd,cdef", ",", SPLIT_SKIP_SPACE, 0);
 111   test_eq(3, smartlist_len(sl));
 112   test_streq("a", smartlist_get(sl,0));
 113   test_streq("bbd", smartlist_get(sl,1));
 114   test_streq("cdef", smartlist_get(sl,2));
 115   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
 116                          SPLIT_SKIP_SPACE, 0);
 117   test_eq(8, smartlist_len(sl));
 118   test_streq("z", smartlist_get(sl,3));
 119   test_streq("zhasd", smartlist_get(sl,4));
 120   test_streq("", smartlist_get(sl,5));
 121   test_streq("bnud", smartlist_get(sl,6));
 122   test_streq("", smartlist_get(sl,7));
 123
 124   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 125   smartlist_clear(sl);
 126
 127   smartlist_split_string(sl, " ab\tc \td ef  ", NULL,
 128                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 129   test_eq(4, smartlist_len(sl));
 130   test_streq("ab", smartlist_get(sl,0));
 131   test_streq("c", smartlist_get(sl,1));
 132   test_streq("d", smartlist_get(sl,2));
 133   test_streq("ef", smartlist_get(sl,3));
 134   smartlist_split_string(sl, "ghi\tj", NULL,
 135                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 136   test_eq(6, smartlist_len(sl));
 137   test_streq("ghi", smartlist_get(sl,4));
 138   test_streq("j", smartlist_get(sl,5));
 139
 140   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 141   smartlist_clear(sl);
 142
 143   cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
 144   test_streq(cp_alloc, "");
 145   tor_free(cp_alloc);
 146   cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
 147   test_streq(cp_alloc, "XY");
 148   tor_free(cp_alloc);
 149
 150   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
 151                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 152   test_eq(3, smartlist_len(sl));
 153   test_streq("z", smartlist_get(sl, 0));
 154   test_streq("zhasd", smartlist_get(sl, 1));
 155   test_streq("bnud", smartlist_get(sl, 2));
 156   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
 157                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 2);
 158   test_eq(5, smartlist_len(sl));
 159   test_streq("z", smartlist_get(sl, 3));
 160   test_streq("zhasd <>  <> bnud<>", smartlist_get(sl, 4));
 161   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 162   smartlist_clear(sl);
 163
 164   smartlist_split_string(sl, "abcd\n", "\n",
 165                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 166   test_eq(1, smartlist_len(sl));
 167   test_streq("abcd", smartlist_get(sl, 0));
 168   smartlist_split_string(sl, "efgh", "\n",
 169                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 170   test_eq(2, smartlist_len(sl));
 171   test_streq("efgh", smartlist_get(sl, 1));
 172
 173   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 174   smartlist_clear(sl);
 175
 176   /* Test swapping, shuffling, and sorting. */
 177   smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0);
 178   test_eq(7, smartlist_len(sl));
 179   smartlist_sort(sl, _compare_strs);
 180   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 181   test_streq(cp_alloc,"and,arma,by,nickm,onion,router,the");
 182   tor_free(cp_alloc);
 183   smartlist_swap(sl, 1, 5);
 184   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 185   test_streq(cp_alloc,"and,router,by,nickm,onion,arma,the");
 186   tor_free(cp_alloc);
 187   smartlist_shuffle(sl);
 188   test_eq(7, smartlist_len(sl));
 189   test_assert(smartlist_string_isin(sl, "and"));
 190   test_assert(smartlist_string_isin(sl, "router"));
 191   test_assert(smartlist_string_isin(sl, "by"));
 192   test_assert(smartlist_string_isin(sl, "nickm"));
 193   test_assert(smartlist_string_isin(sl, "onion"));
 194   test_assert(smartlist_string_isin(sl, "arma"));
 195   test_assert(smartlist_string_isin(sl, "the"));
 196
 197   /* Test bsearch. */
 198   smartlist_sort(sl, _compare_strs);
 199   test_streq("nickm", smartlist_bsearch(sl, "zNicKM",
 200                                         _compare_without_first_ch));
 201   test_streq("and", smartlist_bsearch(sl, " AND", _compare_without_first_ch));
 202   test_eq_ptr(NULL, smartlist_bsearch(sl, " ANz", _compare_without_first_ch));
 203
 204   /* Test bsearch_idx */
 205   {
 206     int f;
 207     test_eq(0, smartlist_bsearch_idx(sl," aaa",_compare_without_first_ch,&f));
 208     test_eq(f, 0);
 209     test_eq(0, smartlist_bsearch_idx(sl," and",_compare_without_first_ch,&f));
 210     test_eq(f, 1);
 211     test_eq(1, smartlist_bsearch_idx(sl," arm",_compare_without_first_ch,&f));
 212     test_eq(f, 0);
 213     test_eq(1, smartlist_bsearch_idx(sl," arma",_compare_without_first_ch,&f));
 214     test_eq(f, 1);
 215     test_eq(2, smartlist_bsearch_idx(sl," armb",_compare_without_first_ch,&f));
 216     test_eq(f, 0);
 217     test_eq(7, smartlist_bsearch_idx(sl," zzzz",_compare_without_first_ch,&f));
 218     test_eq(f, 0);
 219   }
 220
 221   /* Test reverse() and pop_last() */
 222   smartlist_reverse(sl);
 223   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 224   test_streq(cp_alloc,"the,router,onion,nickm,by,arma,and");
 225   tor_free(cp_alloc);
 226   cp_alloc = smartlist_pop_last(sl);
 227   test_streq(cp_alloc, "and");
 228   tor_free(cp_alloc);
 229   test_eq(smartlist_len(sl), 6);
 230   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 231   smartlist_clear(sl);
 232   cp_alloc = smartlist_pop_last(sl);
 233   test_eq(cp_alloc, NULL);
 234
 235   /* Test uniq() */
 236   smartlist_split_string(sl,
 237                      "50,noon,radar,a,man,a,plan,a,canal,panama,radar,noon,50",
 238                      ",", 0, 0);
 239   smartlist_sort(sl, _compare_strs);
 240   smartlist_uniq(sl, _compare_strs, _tor_free);
 241   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 242   test_streq(cp_alloc, "50,a,canal,man,noon,panama,plan,radar");
 243   tor_free(cp_alloc);
 244
 245   /* Test string_isin and isin_case and num_isin */
 246   test_assert(smartlist_string_isin(sl, "noon"));
 247   test_assert(!smartlist_string_isin(sl, "noonoon"));
 248   test_assert(smartlist_string_isin_case(sl, "nOOn"));
 249   test_assert(!smartlist_string_isin_case(sl, "nooNooN"));
 250   test_assert(smartlist_string_num_isin(sl, 50));
 251   test_assert(!smartlist_string_num_isin(sl, 60));
 252
 253   /* Test smartlist_choose */
 254   {
 255     int i;
 256     int allsame = 1;
 257     int allin = 1;
 258     void *first = smartlist_choose(sl);
 259     test_assert(smartlist_isin(sl, first));
 260     for (i = 0; i < 100; ++i) {
 261       void *second = smartlist_choose(sl);
 262       if (second != first)
 263         allsame = 0;
 264       if (!smartlist_isin(sl, second))
 265         allin = 0;
 266     }
 267     test_assert(!allsame);
 268     test_assert(allin);
 269   }
 270   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 271   smartlist_clear(sl);
 272
 273   /* Test string_remove and remove and join_strings2 */
 274   smartlist_split_string(sl,
 275                     "Some say the Earth will end in ice and some in fire",
 276                     " ", 0, 0);
 277   cp = smartlist_get(sl, 4);
 278   test_streq(cp, "will");
 279   smartlist_add(sl, cp);
 280   smartlist_remove(sl, cp);
 281   tor_free(cp);
 282   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
 283   test_streq(cp_alloc, "Some,say,the,Earth,fire,end,in,ice,and,some,in");
 284   tor_free(cp_alloc);
 285   smartlist_string_remove(sl, "in");
 286   cp_alloc = smartlist_join_strings2(sl, "+XX", 1, 0, &sz);
 287   test_streq(cp_alloc, "Some+say+the+Earth+fire+end+some+ice+and");
 288   test_eq((int)sz, 40);
 289
 290  done:
 291
 292   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 293   smartlist_free(sl);
 294   tor_free(cp_alloc);
 295 }
 296
 297 /** Run unit tests for smartlist set manipulation functions. */
 298 static void
 299 test_container_smartlist_overlap(void)
 300 {
 301   smartlist_t *sl = smartlist_create();
 302   smartlist_t *ints = smartlist_create();
 303   smartlist_t *odds = smartlist_create();
 304   smartlist_t *evens = smartlist_create();
 305   smartlist_t *primes = smartlist_create();
 306   int i;
 307   for (i=1; i < 10; i += 2)
 308     smartlist_add(odds, (void*)(uintptr_t)i);
 309   for (i=0; i < 10; i += 2)
 310     smartlist_add(evens, (void*)(uintptr_t)i);
 311
 312   /* add_all */
 313   smartlist_add_all(ints, odds);
 314   smartlist_add_all(ints, evens);
 315   test_eq(smartlist_len(ints), 10);
 316
 317   smartlist_add(primes, (void*)2);
 318   smartlist_add(primes, (void*)3);
 319   smartlist_add(primes, (void*)5);
 320   smartlist_add(primes, (void*)7);
 321
 322   /* overlap */
 323   test_assert(smartlist_overlap(ints, odds));
 324   test_assert(smartlist_overlap(odds, primes));
 325   test_assert(smartlist_overlap(evens, primes));
 326   test_assert(!smartlist_overlap(odds, evens));
 327
 328   /* intersect */
 329   smartlist_add_all(sl, odds);
 330   smartlist_intersect(sl, primes);
 331   test_eq(smartlist_len(sl), 3);
 332   test_assert(smartlist_isin(sl, (void*)3));
 333   test_assert(smartlist_isin(sl, (void*)5));
 334   test_assert(smartlist_isin(sl, (void*)7));
 335
 336   /* subtract */
 337   smartlist_add_all(sl, primes);
 338   smartlist_subtract(sl, odds);
 339   test_eq(smartlist_len(sl), 1);
 340   test_assert(smartlist_isin(sl, (void*)2));
 341
 342  done:
 343   smartlist_free(odds);
 344   smartlist_free(evens);
 345   smartlist_free(ints);
 346   smartlist_free(primes);
 347   smartlist_free(sl);
 348 }
 349
 350 /** Run unit tests for smartlist-of-digests functions. */
 351 static void
 352 test_container_smartlist_digests(void)
 353 {
 354   smartlist_t *sl = smartlist_create();
 355
 356   /* digest_isin. */
 357   smartlist_add(sl, tor_memdup("AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN));
 358   smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
 359   smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
 360   test_eq(0, smartlist_digest_isin(NULL, "AAAAAAAAAAAAAAAAAAAA"));
 361   test_assert(smartlist_digest_isin(sl, "AAAAAAAAAAAAAAAAAAAA"));
 362   test_assert(smartlist_digest_isin(sl, "\00090AAB2AAAAaasdAAAAA"));
 363   test_eq(0, smartlist_digest_isin(sl, "\00090AAB2AAABaasdAAAAA"));
 364
 365   /* sort digests */
 366   smartlist_sort_digests(sl);
 367   test_memeq(smartlist_get(sl, 0), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
 368   test_memeq(smartlist_get(sl, 1), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
 369   test_memeq(smartlist_get(sl, 2), "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
 370   test_eq(3, smartlist_len(sl));
 371
 372   /* uniq_digests */
 373   smartlist_uniq_digests(sl);
 374   test_eq(2, smartlist_len(sl));
 375   test_memeq(smartlist_get(sl, 0), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
 376   test_memeq(smartlist_get(sl, 1), "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
 377
 378  done:
 379   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 380   smartlist_free(sl);
 381 }
 382
 383 /** Run unit tests for concatenate-a-smartlist-of-strings functions. */
 384 static void
 385 test_container_smartlist_join(void)
 386 {
 387   smartlist_t *sl = smartlist_create();
 388   smartlist_t *sl2 = smartlist_create(), *sl3 = smartlist_create(),
 389     *sl4 = smartlist_create();
 390   char *joined=NULL;
 391   /* unique, sorted. */
 392   smartlist_split_string(sl,
 393                          "Abashments Ambush Anchorman Bacon Banks Borscht "
 394                          "Bunks Inhumane Insurance Knish Know Manners "
 395                          "Maraschinos Stamina Sunbonnets Unicorns Wombats",
 396                          " ", 0, 0);
 397   /* non-unique, sorted. */
 398   smartlist_split_string(sl2,
 399                          "Ambush Anchorman Anchorman Anemias Anemias Bacon "
 400                          "Crossbowmen Inhumane Insurance Knish Know Manners "
 401                          "Manners Maraschinos Wombats Wombats Work",
 402                          " ", 0, 0);
 403   SMARTLIST_FOREACH_JOIN(sl, char *, cp1,
 404                          sl2, char *, cp2,
 405                          strcmp(cp1,cp2),
 406                          smartlist_add(sl3, cp2)) {
 407     test_streq(cp1, cp2);
 408     smartlist_add(sl4, cp1);
 409   } SMARTLIST_FOREACH_JOIN_END(cp1, cp2);
 410
 411   SMARTLIST_FOREACH(sl3, const char *, cp,
 412                     test_assert(smartlist_isin(sl2, cp) &&
 413                                 !smartlist_string_isin(sl, cp)));
 414   SMARTLIST_FOREACH(sl4, const char *, cp,
 415                     test_assert(smartlist_isin(sl, cp) &&
 416                                 smartlist_string_isin(sl2, cp)));
 417   joined = smartlist_join_strings(sl3, ",", 0, NULL);
 418   test_streq(joined, "Anemias,Anemias,Crossbowmen,Work");
 419   tor_free(joined);
 420   joined = smartlist_join_strings(sl4, ",", 0, NULL);
 421   test_streq(joined, "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance,"
 422              "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats");
 423   tor_free(joined);
 424
 425  done:
 426   smartlist_free(sl4);
 427   smartlist_free(sl3);
 428   SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp));
 429   smartlist_free(sl2);
 430   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 431   smartlist_free(sl);
 432   tor_free(joined);
 433 }
 434
 435 /** Run unit tests for bitarray code */
 436 static void
 437 test_container_bitarray(void)
 438 {
 439   bitarray_t *ba = NULL;
 440   int i, j, ok=1;
 441
 442   ba = bitarray_init_zero(1);
 443   test_assert(ba);
 444   test_assert(! bitarray_is_set(ba, 0));
 445   bitarray_set(ba, 0);
 446   test_assert(bitarray_is_set(ba, 0));
 447   bitarray_clear(ba, 0);
 448   test_assert(! bitarray_is_set(ba, 0));
 449   bitarray_free(ba);
 450
 451   ba = bitarray_init_zero(1023);
 452   for (i = 1; i < 64; ) {
 453     for (j = 0; j < 1023; ++j) {
 454       if (j % i)
 455         bitarray_set(ba, j);
 456       else
 457         bitarray_clear(ba, j);
 458     }
 459     for (j = 0; j < 1023; ++j) {
 460       if (!bool_eq(bitarray_is_set(ba, j), j%i))
 461         ok = 0;
 462     }
 463     test_assert(ok);
 464     if (i < 7)
 465       ++i;
 466     else if (i == 28)
 467       i = 32;
 468     else
 469       i += 7;
 470   }
 471
 472  done:
 473   if (ba)
 474     bitarray_free(ba);
 475 }
 476
 477 /** Run unit tests for digest set code (implemented as a hashtable or as a
 478  * bloom filter) */
 479 static void
 480 test_container_digestset(void)
 481 {
 482   smartlist_t *included = smartlist_create();
 483   char d[DIGEST_LEN];
 484   int i;
 485   int ok = 1;
 486   int false_positives = 0;
 487   digestset_t *set = NULL;
 488
 489   for (i = 0; i < 1000; ++i) {
 490     crypto_rand(d, DIGEST_LEN);
 491     smartlist_add(included, tor_memdup(d, DIGEST_LEN));
 492   }
 493   set = digestset_new(1000);
 494   SMARTLIST_FOREACH(included, const char *, cp,
 495                     if (digestset_isin(set, cp))
 496                       ok = 0);
 497   test_assert(ok);
 498   SMARTLIST_FOREACH(included, const char *, cp,
 499                     digestset_add(set, cp));
 500   SMARTLIST_FOREACH(included, const char *, cp,
 501                     if (!digestset_isin(set, cp))
 502                       ok = 0);
 503   test_assert(ok);
 504   for (i = 0; i < 1000; ++i) {
 505     crypto_rand(d, DIGEST_LEN);
 506     if (digestset_isin(set, d))
 507       ++false_positives;
 508   }
 509   test_assert(false_positives < 50); /* Should be far lower. */
 510
 511  done:
 512   if (set)
 513     digestset_free(set);
 514   SMARTLIST_FOREACH(included, char *, cp, tor_free(cp));
 515   smartlist_free(included);
 516 }
 517
 518 typedef struct pq_entry_t {
 519   const char *val;
 520   int idx;
 521 } pq_entry_t;
 522
 523 /** Helper: return a tristate based on comparing two pq_entry_t values. */
 524 static int
 525 _compare_strings_for_pqueue(const void *p1, const void *p2)
 526 {
 527   const pq_entry_t *e1=p1, *e2=p2;
 528   return strcmp(e1->val, e2->val);
 529 }
 530
 531 /** Run unit tests for heap-based priority queue functions. */
 532 static void
 533 test_container_pqueue(void)
 534 {
 535   smartlist_t *sl = smartlist_create();
 536   int (*cmp)(const void *, const void*);
 537   const int offset = STRUCT_OFFSET(pq_entry_t, idx);
 538 #define ENTRY(s) pq_entry_t s = { #s, -1 }
 539   ENTRY(cows);
 540   ENTRY(zebras);
 541   ENTRY(fish);
 542   ENTRY(frogs);
 543   ENTRY(apples);
 544   ENTRY(squid);
 545   ENTRY(daschunds);
 546   ENTRY(eggplants);
 547   ENTRY(weissbier);
 548   ENTRY(lobsters);
 549   ENTRY(roquefort);
 550   ENTRY(chinchillas);
 551   ENTRY(fireflies);
 552
 553 #define OK() smartlist_pqueue_assert_ok(sl, cmp, offset)
 554
 555   cmp = _compare_strings_for_pqueue;
 556   smartlist_pqueue_add(sl, cmp, offset, &cows);
 557   smartlist_pqueue_add(sl, cmp, offset, &zebras);
 558   smartlist_pqueue_add(sl, cmp, offset, &fish);
 559   smartlist_pqueue_add(sl, cmp, offset, &frogs);
 560   smartlist_pqueue_add(sl, cmp, offset, &apples);
 561   smartlist_pqueue_add(sl, cmp, offset, &squid);
 562   smartlist_pqueue_add(sl, cmp, offset, &daschunds);
 563   smartlist_pqueue_add(sl, cmp, offset, &eggplants);
 564   smartlist_pqueue_add(sl, cmp, offset, &weissbier);
 565   smartlist_pqueue_add(sl, cmp, offset, &lobsters);
 566   smartlist_pqueue_add(sl, cmp, offset, &roquefort);
 567
 568   OK();
 569
 570   test_eq(smartlist_len(sl), 11);
 571   test_eq_ptr(smartlist_get(sl, 0), &apples);
 572   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &apples);
 573   test_eq(smartlist_len(sl), 10);
 574   OK();
 575   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &cows);
 576   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &daschunds);
 577   smartlist_pqueue_add(sl, cmp, offset, &chinchillas);
 578   OK();
 579   smartlist_pqueue_add(sl, cmp, offset, &fireflies);
 580   OK();
 581   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &chinchillas);
 582   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &eggplants);
 583   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fireflies);
 584   OK();
 585   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fish);
 586   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &frogs);
 587   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &lobsters);
 588   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &roquefort);
 589   OK();
 590   test_eq(smartlist_len(sl), 3);
 591   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &squid);
 592   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &weissbier);
 593   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &zebras);
 594   test_eq(smartlist_len(sl), 0);
 595   OK();
 596
 597   /* Now test remove. */
 598   smartlist_pqueue_add(sl, cmp, offset, &cows);
 599   smartlist_pqueue_add(sl, cmp, offset, &fish);
 600   smartlist_pqueue_add(sl, cmp, offset, &frogs);
 601   smartlist_pqueue_add(sl, cmp, offset, &apples);
 602   smartlist_pqueue_add(sl, cmp, offset, &squid);
 603   smartlist_pqueue_add(sl, cmp, offset, &zebras);
 604   test_eq(smartlist_len(sl), 6);
 605   OK();
 606   smartlist_pqueue_remove(sl, cmp, offset, &zebras);
 607   test_eq(smartlist_len(sl), 5);
 608   OK();
 609   smartlist_pqueue_remove(sl, cmp, offset, &cows);
 610   test_eq(smartlist_len(sl), 4);
 611   OK();
 612   smartlist_pqueue_remove(sl, cmp, offset, &apples);
 613   test_eq(smartlist_len(sl), 3);
 614   OK();
 615   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fish);
 616   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &frogs);
 617   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &squid);
 618   test_eq(smartlist_len(sl), 0);
 619   OK();
 620
 621 #undef OK
 622
 623  done:
 624
 625   smartlist_free(sl);
 626 }
 627
 628 /** Run unit tests for string-to-void* map functions */
 629 static void
 630 test_container_strmap(void)
 631 {
 632   strmap_t *map;
 633   strmap_iter_t *iter;
 634   const char *k;
 635   void *v;
 636   char *visited = NULL;
 637   smartlist_t *found_keys = NULL;
 638
 639   map = strmap_new();
 640   test_assert(map);
 641   test_eq(strmap_size(map), 0);
 642   test_assert(strmap_isempty(map));
 643   v = strmap_set(map, "K1", (void*)99);
 644   test_eq(v, NULL);
 645   test_assert(!strmap_isempty(map));
 646   v = strmap_set(map, "K2", (void*)101);
 647   test_eq(v, NULL);
 648   v = strmap_set(map, "K1", (void*)100);
 649   test_eq(v, (void*)99);
 650   test_eq_ptr(strmap_get(map,"K1"), (void*)100);
 651   test_eq_ptr(strmap_get(map,"K2"), (void*)101);
 652   test_eq_ptr(strmap_get(map,"K-not-there"), NULL);
 653   strmap_assert_ok(map);
 654
 655   v = strmap_remove(map,"K2");
 656   strmap_assert_ok(map);
 657   test_eq_ptr(v, (void*)101);
 658   test_eq_ptr(strmap_get(map,"K2"), NULL);
 659   test_eq_ptr(strmap_remove(map,"K2"), NULL);
 660
 661   strmap_set(map, "K2", (void*)101);
 662   strmap_set(map, "K3", (void*)102);
 663   strmap_set(map, "K4", (void*)103);
 664   test_eq(strmap_size(map), 4);
 665   strmap_assert_ok(map);
 666   strmap_set(map, "K5", (void*)104);
 667   strmap_set(map, "K6", (void*)105);
 668   strmap_assert_ok(map);
 669
 670   /* Test iterator. */
 671   iter = strmap_iter_init(map);
 672   found_keys = smartlist_create();
 673   while (!strmap_iter_done(iter)) {
 674     strmap_iter_get(iter,&k,&v);
 675     smartlist_add(found_keys, tor_strdup(k));
 676     test_eq_ptr(v, strmap_get(map, k));
 677
 678     if (!strcmp(k, "K2")) {
 679       iter = strmap_iter_next_rmv(map,iter);
 680     } else {
 681       iter = strmap_iter_next(map,iter);
 682     }
 683   }
 684
 685   /* Make sure we removed K2, but not the others. */
 686   test_eq_ptr(strmap_get(map, "K2"), NULL);
 687   test_eq_ptr(strmap_get(map, "K5"), (void*)104);
 688   /* Make sure we visited everyone once */
 689   smartlist_sort_strings(found_keys);
 690   visited = smartlist_join_strings(found_keys, ":", 0, NULL);
 691   test_streq(visited, "K1:K2:K3:K4:K5:K6");
 692
 693   strmap_assert_ok(map);
 694   /* Clean up after ourselves. */
 695   strmap_free(map, NULL);
 696   map = NULL;
 697
 698   /* Now try some lc functions. */
 699   map = strmap_new();
 700   strmap_set_lc(map,"Ab.C", (void*)1);
 701   test_eq_ptr(strmap_get(map,"ab.c"), (void*)1);
 702   strmap_assert_ok(map);
 703   test_eq_ptr(strmap_get_lc(map,"AB.C"), (void*)1);
 704   test_eq_ptr(strmap_get(map,"AB.C"), NULL);
 705   test_eq_ptr(strmap_remove_lc(map,"aB.C"), (void*)1);
 706   strmap_assert_ok(map);
 707   test_eq_ptr(strmap_get_lc(map,"AB.C"), NULL);
 708
 709  done:
 710   if (map)
 711     strmap_free(map,NULL);
 712   if (found_keys) {
 713     SMARTLIST_FOREACH(found_keys, char *, cp, tor_free(cp));
 714     smartlist_free(found_keys);
 715   }
 716   tor_free(visited);
 717 }
 718
 719 /** Run unit tests for getting the median of a list. */
 720 static void
 721 test_container_order_functions(void)
 722 {
 723   int lst[25], n = 0;
 724   //  int a=12,b=24,c=25,d=60,e=77;
 725
 726 #define median() median_int(lst, n)
 727
 728   lst[n++] = 12;
 729   test_eq(12, median()); /* 12 */
 730   lst[n++] = 77;
 731   //smartlist_shuffle(sl);
 732   test_eq(12, median()); /* 12, 77 */
 733   lst[n++] = 77;
 734   //smartlist_shuffle(sl);
 735   test_eq(77, median()); /* 12, 77, 77 */
 736   lst[n++] = 24;
 737   test_eq(24, median()); /* 12,24,77,77 */
 738   lst[n++] = 60;
 739   lst[n++] = 12;
 740   lst[n++] = 25;
 741   //smartlist_shuffle(sl);
 742   test_eq(25, median()); /* 12,12,24,25,60,77,77 */
 743 #undef median
 744
 745  done:
 746   ;
 747 }
 748
 749 #define CONTAINER_LEGACY(name)                                          \
 750   { #name, legacy_test_helper, 0, &legacy_setup, test_container_ ## name }
 751
 752 struct testcase_t container_tests[] = {
 753   CONTAINER_LEGACY(smartlist_basic),
 754   CONTAINER_LEGACY(smartlist_strings),
 755   CONTAINER_LEGACY(smartlist_overlap),
 756   CONTAINER_LEGACY(smartlist_digests),
 757   CONTAINER_LEGACY(smartlist_join),
 758   CONTAINER_LEGACY(bitarray),
 759   CONTAINER_LEGACY(digestset),
 760   CONTAINER_LEGACY(strmap),
 761   CONTAINER_LEGACY(pqueue),
 762   CONTAINER_LEGACY(order_functions),
 763   END_OF_TESTCASES
 764 };
 765