Back to index

tor  0.2.3.18-rc
test_containers.c
Go to the documentation of this file.
00001 /* Copyright (c) 2001-2004, Roger Dingledine.
00002  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
00003  * Copyright (c) 2007-2012, The Tor Project, Inc. */
00004 /* See LICENSE for licensing information */
00005 
00006 #include "orconfig.h"
00007 #include "or.h"
00008 #include "test.h"
00009 
00012 static int
00013 _compare_strs(const void **a, const void **b)
00014 {
00015   const char *s1 = *a, *s2 = *b;
00016   return strcmp(s1, s2);
00017 }
00018 
00021 static int
00022 _compare_without_first_ch(const void *a, const void **b)
00023 {
00024   const char *s1 = a, *s2 = *b;
00025   return strcasecmp(s1+1, s2);
00026 }
00027 
00029 static void
00030 test_container_smartlist_basic(void)
00031 {
00032   smartlist_t *sl;
00033 
00034   /* XXXX test sort_digests, uniq_strings, uniq_digests */
00035 
00036   /* Test smartlist add, del_keeporder, insert, get. */
00037   sl = smartlist_new();
00038   smartlist_add(sl, (void*)1);
00039   smartlist_add(sl, (void*)2);
00040   smartlist_add(sl, (void*)3);
00041   smartlist_add(sl, (void*)4);
00042   smartlist_del_keeporder(sl, 1);
00043   smartlist_insert(sl, 1, (void*)22);
00044   smartlist_insert(sl, 0, (void*)0);
00045   smartlist_insert(sl, 5, (void*)555);
00046   test_eq_ptr((void*)0,   smartlist_get(sl,0));
00047   test_eq_ptr((void*)1,   smartlist_get(sl,1));
00048   test_eq_ptr((void*)22,  smartlist_get(sl,2));
00049   test_eq_ptr((void*)3,   smartlist_get(sl,3));
00050   test_eq_ptr((void*)4,   smartlist_get(sl,4));
00051   test_eq_ptr((void*)555, smartlist_get(sl,5));
00052   /* Try deleting in the middle. */
00053   smartlist_del(sl, 1);
00054   test_eq_ptr((void*)555, smartlist_get(sl, 1));
00055   /* Try deleting at the end. */
00056   smartlist_del(sl, 4);
00057   test_eq(4, smartlist_len(sl));
00058 
00059   /* test isin. */
00060   test_assert(smartlist_isin(sl, (void*)3));
00061   test_assert(!smartlist_isin(sl, (void*)99));
00062 
00063  done:
00064   smartlist_free(sl);
00065 }
00066 
00068 static void
00069 test_container_smartlist_strings(void)
00070 {
00071   smartlist_t *sl = smartlist_new();
00072   char *cp=NULL, *cp_alloc=NULL;
00073   size_t sz;
00074 
00075   /* Test split and join */
00076   test_eq(0, smartlist_len(sl));
00077   smartlist_split_string(sl, "abc", ":", 0, 0);
00078   test_eq(1, smartlist_len(sl));
00079   test_streq("abc", smartlist_get(sl, 0));
00080   smartlist_split_string(sl, "a::bc::", "::", 0, 0);
00081   test_eq(4, smartlist_len(sl));
00082   test_streq("a", smartlist_get(sl, 1));
00083   test_streq("bc", smartlist_get(sl, 2));
00084   test_streq("", smartlist_get(sl, 3));
00085   cp_alloc = smartlist_join_strings(sl, "", 0, NULL);
00086   test_streq(cp_alloc, "abcabc");
00087   tor_free(cp_alloc);
00088   cp_alloc = smartlist_join_strings(sl, "!", 0, NULL);
00089   test_streq(cp_alloc, "abc!a!bc!");
00090   tor_free(cp_alloc);
00091   cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
00092   test_streq(cp_alloc, "abcXYaXYbcXY");
00093   tor_free(cp_alloc);
00094   cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
00095   test_streq(cp_alloc, "abcXYaXYbcXYXY");
00096   tor_free(cp_alloc);
00097   cp_alloc = smartlist_join_strings(sl, "", 1, NULL);
00098   test_streq(cp_alloc, "abcabc");
00099   tor_free(cp_alloc);
00100 
00101   smartlist_split_string(sl, "/def/  /ghijk", "/", 0, 0);
00102   test_eq(8, smartlist_len(sl));
00103   test_streq("", smartlist_get(sl, 4));
00104   test_streq("def", smartlist_get(sl, 5));
00105   test_streq("  ", smartlist_get(sl, 6));
00106   test_streq("ghijk", smartlist_get(sl, 7));
00107   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00108   smartlist_clear(sl);
00109 
00110   smartlist_split_string(sl, "a,bbd,cdef", ",", SPLIT_SKIP_SPACE, 0);
00111   test_eq(3, smartlist_len(sl));
00112   test_streq("a", smartlist_get(sl,0));
00113   test_streq("bbd", smartlist_get(sl,1));
00114   test_streq("cdef", smartlist_get(sl,2));
00115   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
00116                          SPLIT_SKIP_SPACE, 0);
00117   test_eq(8, smartlist_len(sl));
00118   test_streq("z", smartlist_get(sl,3));
00119   test_streq("zhasd", smartlist_get(sl,4));
00120   test_streq("", smartlist_get(sl,5));
00121   test_streq("bnud", smartlist_get(sl,6));
00122   test_streq("", smartlist_get(sl,7));
00123 
00124   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00125   smartlist_clear(sl);
00126 
00127   smartlist_split_string(sl, " ab\tc \td ef  ", NULL,
00128                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
00129   test_eq(4, smartlist_len(sl));
00130   test_streq("ab", smartlist_get(sl,0));
00131   test_streq("c", smartlist_get(sl,1));
00132   test_streq("d", smartlist_get(sl,2));
00133   test_streq("ef", smartlist_get(sl,3));
00134   smartlist_split_string(sl, "ghi\tj", NULL,
00135                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
00136   test_eq(6, smartlist_len(sl));
00137   test_streq("ghi", smartlist_get(sl,4));
00138   test_streq("j", smartlist_get(sl,5));
00139 
00140   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00141   smartlist_clear(sl);
00142 
00143   cp_alloc = smartlist_join_strings(sl, "XY", 0, NULL);
00144   test_streq(cp_alloc, "");
00145   tor_free(cp_alloc);
00146   cp_alloc = smartlist_join_strings(sl, "XY", 1, NULL);
00147   test_streq(cp_alloc, "XY");
00148   tor_free(cp_alloc);
00149 
00150   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
00151                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
00152   test_eq(3, smartlist_len(sl));
00153   test_streq("z", smartlist_get(sl, 0));
00154   test_streq("zhasd", smartlist_get(sl, 1));
00155   test_streq("bnud", smartlist_get(sl, 2));
00156   smartlist_split_string(sl, " z <> zhasd <>  <> bnud<>   ", "<>",
00157                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 2);
00158   test_eq(5, smartlist_len(sl));
00159   test_streq("z", smartlist_get(sl, 3));
00160   test_streq("zhasd <>  <> bnud<>", smartlist_get(sl, 4));
00161   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00162   smartlist_clear(sl);
00163 
00164   smartlist_split_string(sl, "abcd\n", "\n",
00165                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
00166   test_eq(1, smartlist_len(sl));
00167   test_streq("abcd", smartlist_get(sl, 0));
00168   smartlist_split_string(sl, "efgh", "\n",
00169                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
00170   test_eq(2, smartlist_len(sl));
00171   test_streq("efgh", smartlist_get(sl, 1));
00172 
00173   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00174   smartlist_clear(sl);
00175 
00176   /* Test swapping, shuffling, and sorting. */
00177   smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0);
00178   test_eq(7, smartlist_len(sl));
00179   smartlist_sort(sl, _compare_strs);
00180   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
00181   test_streq(cp_alloc,"and,arma,by,nickm,onion,router,the");
00182   tor_free(cp_alloc);
00183   smartlist_swap(sl, 1, 5);
00184   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
00185   test_streq(cp_alloc,"and,router,by,nickm,onion,arma,the");
00186   tor_free(cp_alloc);
00187   smartlist_shuffle(sl);
00188   test_eq(7, smartlist_len(sl));
00189   test_assert(smartlist_string_isin(sl, "and"));
00190   test_assert(smartlist_string_isin(sl, "router"));
00191   test_assert(smartlist_string_isin(sl, "by"));
00192   test_assert(smartlist_string_isin(sl, "nickm"));
00193   test_assert(smartlist_string_isin(sl, "onion"));
00194   test_assert(smartlist_string_isin(sl, "arma"));
00195   test_assert(smartlist_string_isin(sl, "the"));
00196 
00197   /* Test bsearch. */
00198   smartlist_sort(sl, _compare_strs);
00199   test_streq("nickm", smartlist_bsearch(sl, "zNicKM",
00200                                         _compare_without_first_ch));
00201   test_streq("and", smartlist_bsearch(sl, " AND", _compare_without_first_ch));
00202   test_eq_ptr(NULL, smartlist_bsearch(sl, " ANz", _compare_without_first_ch));
00203 
00204   /* Test bsearch_idx */
00205   {
00206     int f;
00207     test_eq(0, smartlist_bsearch_idx(sl," aaa",_compare_without_first_ch,&f));
00208     test_eq(f, 0);
00209     test_eq(0, smartlist_bsearch_idx(sl," and",_compare_without_first_ch,&f));
00210     test_eq(f, 1);
00211     test_eq(1, smartlist_bsearch_idx(sl," arm",_compare_without_first_ch,&f));
00212     test_eq(f, 0);
00213     test_eq(1, smartlist_bsearch_idx(sl," arma",_compare_without_first_ch,&f));
00214     test_eq(f, 1);
00215     test_eq(2, smartlist_bsearch_idx(sl," armb",_compare_without_first_ch,&f));
00216     test_eq(f, 0);
00217     test_eq(7, smartlist_bsearch_idx(sl," zzzz",_compare_without_first_ch,&f));
00218     test_eq(f, 0);
00219   }
00220 
00221   /* Test reverse() and pop_last() */
00222   smartlist_reverse(sl);
00223   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
00224   test_streq(cp_alloc,"the,router,onion,nickm,by,arma,and");
00225   tor_free(cp_alloc);
00226   cp_alloc = smartlist_pop_last(sl);
00227   test_streq(cp_alloc, "and");
00228   tor_free(cp_alloc);
00229   test_eq(smartlist_len(sl), 6);
00230   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00231   smartlist_clear(sl);
00232   cp_alloc = smartlist_pop_last(sl);
00233   test_eq(cp_alloc, NULL);
00234 
00235   /* Test uniq() */
00236   smartlist_split_string(sl,
00237                      "50,noon,radar,a,man,a,plan,a,canal,panama,radar,noon,50",
00238                      ",", 0, 0);
00239   smartlist_sort(sl, _compare_strs);
00240   smartlist_uniq(sl, _compare_strs, _tor_free);
00241   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
00242   test_streq(cp_alloc, "50,a,canal,man,noon,panama,plan,radar");
00243   tor_free(cp_alloc);
00244 
00245   /* Test string_isin and isin_case and num_isin */
00246   test_assert(smartlist_string_isin(sl, "noon"));
00247   test_assert(!smartlist_string_isin(sl, "noonoon"));
00248   test_assert(smartlist_string_isin_case(sl, "nOOn"));
00249   test_assert(!smartlist_string_isin_case(sl, "nooNooN"));
00250   test_assert(smartlist_string_num_isin(sl, 50));
00251   test_assert(!smartlist_string_num_isin(sl, 60));
00252 
00253   /* Test smartlist_choose */
00254   {
00255     int i;
00256     int allsame = 1;
00257     int allin = 1;
00258     void *first = smartlist_choose(sl);
00259     test_assert(smartlist_isin(sl, first));
00260     for (i = 0; i < 100; ++i) {
00261       void *second = smartlist_choose(sl);
00262       if (second != first)
00263         allsame = 0;
00264       if (!smartlist_isin(sl, second))
00265         allin = 0;
00266     }
00267     test_assert(!allsame);
00268     test_assert(allin);
00269   }
00270   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00271   smartlist_clear(sl);
00272 
00273   /* Test string_remove and remove and join_strings2 */
00274   smartlist_split_string(sl,
00275                     "Some say the Earth will end in ice and some in fire",
00276                     " ", 0, 0);
00277   cp = smartlist_get(sl, 4);
00278   test_streq(cp, "will");
00279   smartlist_add(sl, cp);
00280   smartlist_remove(sl, cp);
00281   tor_free(cp);
00282   cp_alloc = smartlist_join_strings(sl, ",", 0, NULL);
00283   test_streq(cp_alloc, "Some,say,the,Earth,fire,end,in,ice,and,some,in");
00284   tor_free(cp_alloc);
00285   smartlist_string_remove(sl, "in");
00286   cp_alloc = smartlist_join_strings2(sl, "+XX", 1, 0, &sz);
00287   test_streq(cp_alloc, "Some+say+the+Earth+fire+end+some+ice+and");
00288   test_eq((int)sz, 40);
00289 
00290  done:
00291 
00292   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00293   smartlist_free(sl);
00294   tor_free(cp_alloc);
00295 }
00296 
00298 static void
00299 test_container_smartlist_overlap(void)
00300 {
00301   smartlist_t *sl = smartlist_new();
00302   smartlist_t *ints = smartlist_new();
00303   smartlist_t *odds = smartlist_new();
00304   smartlist_t *evens = smartlist_new();
00305   smartlist_t *primes = smartlist_new();
00306   int i;
00307   for (i=1; i < 10; i += 2)
00308     smartlist_add(odds, (void*)(uintptr_t)i);
00309   for (i=0; i < 10; i += 2)
00310     smartlist_add(evens, (void*)(uintptr_t)i);
00311 
00312   /* add_all */
00313   smartlist_add_all(ints, odds);
00314   smartlist_add_all(ints, evens);
00315   test_eq(smartlist_len(ints), 10);
00316 
00317   smartlist_add(primes, (void*)2);
00318   smartlist_add(primes, (void*)3);
00319   smartlist_add(primes, (void*)5);
00320   smartlist_add(primes, (void*)7);
00321 
00322   /* overlap */
00323   test_assert(smartlist_overlap(ints, odds));
00324   test_assert(smartlist_overlap(odds, primes));
00325   test_assert(smartlist_overlap(evens, primes));
00326   test_assert(!smartlist_overlap(odds, evens));
00327 
00328   /* intersect */
00329   smartlist_add_all(sl, odds);
00330   smartlist_intersect(sl, primes);
00331   test_eq(smartlist_len(sl), 3);
00332   test_assert(smartlist_isin(sl, (void*)3));
00333   test_assert(smartlist_isin(sl, (void*)5));
00334   test_assert(smartlist_isin(sl, (void*)7));
00335 
00336   /* subtract */
00337   smartlist_add_all(sl, primes);
00338   smartlist_subtract(sl, odds);
00339   test_eq(smartlist_len(sl), 1);
00340   test_assert(smartlist_isin(sl, (void*)2));
00341 
00342  done:
00343   smartlist_free(odds);
00344   smartlist_free(evens);
00345   smartlist_free(ints);
00346   smartlist_free(primes);
00347   smartlist_free(sl);
00348 }
00349 
00351 static void
00352 test_container_smartlist_digests(void)
00353 {
00354   smartlist_t *sl = smartlist_new();
00355 
00356   /* digest_isin. */
00357   smartlist_add(sl, tor_memdup("AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN));
00358   smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
00359   smartlist_add(sl, tor_memdup("\00090AAB2AAAAaasdAAAAA", DIGEST_LEN));
00360   test_eq(0, smartlist_digest_isin(NULL, "AAAAAAAAAAAAAAAAAAAA"));
00361   test_assert(smartlist_digest_isin(sl, "AAAAAAAAAAAAAAAAAAAA"));
00362   test_assert(smartlist_digest_isin(sl, "\00090AAB2AAAAaasdAAAAA"));
00363   test_eq(0, smartlist_digest_isin(sl, "\00090AAB2AAABaasdAAAAA"));
00364 
00365   /* sort digests */
00366   smartlist_sort_digests(sl);
00367   test_memeq(smartlist_get(sl, 0), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
00368   test_memeq(smartlist_get(sl, 1), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
00369   test_memeq(smartlist_get(sl, 2), "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
00370   test_eq(3, smartlist_len(sl));
00371 
00372   /* uniq_digests */
00373   smartlist_uniq_digests(sl);
00374   test_eq(2, smartlist_len(sl));
00375   test_memeq(smartlist_get(sl, 0), "\00090AAB2AAAAaasdAAAAA", DIGEST_LEN);
00376   test_memeq(smartlist_get(sl, 1), "AAAAAAAAAAAAAAAAAAAA", DIGEST_LEN);
00377 
00378  done:
00379   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00380   smartlist_free(sl);
00381 }
00382 
00384 static void
00385 test_container_smartlist_join(void)
00386 {
00387   smartlist_t *sl = smartlist_new();
00388   smartlist_t *sl2 = smartlist_new(), *sl3 = smartlist_new(),
00389     *sl4 = smartlist_new();
00390   char *joined=NULL;
00391   /* unique, sorted. */
00392   smartlist_split_string(sl,
00393                          "Abashments Ambush Anchorman Bacon Banks Borscht "
00394                          "Bunks Inhumane Insurance Knish Know Manners "
00395                          "Maraschinos Stamina Sunbonnets Unicorns Wombats",
00396                          " ", 0, 0);
00397   /* non-unique, sorted. */
00398   smartlist_split_string(sl2,
00399                          "Ambush Anchorman Anchorman Anemias Anemias Bacon "
00400                          "Crossbowmen Inhumane Insurance Knish Know Manners "
00401                          "Manners Maraschinos Wombats Wombats Work",
00402                          " ", 0, 0);
00403   SMARTLIST_FOREACH_JOIN(sl, char *, cp1,
00404                          sl2, char *, cp2,
00405                          strcmp(cp1,cp2),
00406                          smartlist_add(sl3, cp2)) {
00407     test_streq(cp1, cp2);
00408     smartlist_add(sl4, cp1);
00409   } SMARTLIST_FOREACH_JOIN_END(cp1, cp2);
00410 
00411   SMARTLIST_FOREACH(sl3, const char *, cp,
00412                     test_assert(smartlist_isin(sl2, cp) &&
00413                                 !smartlist_string_isin(sl, cp)));
00414   SMARTLIST_FOREACH(sl4, const char *, cp,
00415                     test_assert(smartlist_isin(sl, cp) &&
00416                                 smartlist_string_isin(sl2, cp)));
00417   joined = smartlist_join_strings(sl3, ",", 0, NULL);
00418   test_streq(joined, "Anemias,Anemias,Crossbowmen,Work");
00419   tor_free(joined);
00420   joined = smartlist_join_strings(sl4, ",", 0, NULL);
00421   test_streq(joined, "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance,"
00422              "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats");
00423   tor_free(joined);
00424 
00425  done:
00426   smartlist_free(sl4);
00427   smartlist_free(sl3);
00428   SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp));
00429   smartlist_free(sl2);
00430   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
00431   smartlist_free(sl);
00432   tor_free(joined);
00433 }
00434 
00436 static void
00437 test_container_bitarray(void)
00438 {
00439   bitarray_t *ba = NULL;
00440   int i, j, ok=1;
00441 
00442   ba = bitarray_init_zero(1);
00443   test_assert(ba);
00444   test_assert(! bitarray_is_set(ba, 0));
00445   bitarray_set(ba, 0);
00446   test_assert(bitarray_is_set(ba, 0));
00447   bitarray_clear(ba, 0);
00448   test_assert(! bitarray_is_set(ba, 0));
00449   bitarray_free(ba);
00450 
00451   ba = bitarray_init_zero(1023);
00452   for (i = 1; i < 64; ) {
00453     for (j = 0; j < 1023; ++j) {
00454       if (j % i)
00455         bitarray_set(ba, j);
00456       else
00457         bitarray_clear(ba, j);
00458     }
00459     for (j = 0; j < 1023; ++j) {
00460       if (!bool_eq(bitarray_is_set(ba, j), j%i))
00461         ok = 0;
00462     }
00463     test_assert(ok);
00464     if (i < 7)
00465       ++i;
00466     else if (i == 28)
00467       i = 32;
00468     else
00469       i += 7;
00470   }
00471 
00472  done:
00473   if (ba)
00474     bitarray_free(ba);
00475 }
00476 
00479 static void
00480 test_container_digestset(void)
00481 {
00482   smartlist_t *included = smartlist_new();
00483   char d[DIGEST_LEN];
00484   int i;
00485   int ok = 1;
00486   int false_positives = 0;
00487   digestset_t *set = NULL;
00488 
00489   for (i = 0; i < 1000; ++i) {
00490     crypto_rand(d, DIGEST_LEN);
00491     smartlist_add(included, tor_memdup(d, DIGEST_LEN));
00492   }
00493   set = digestset_new(1000);
00494   SMARTLIST_FOREACH(included, const char *, cp,
00495                     if (digestset_isin(set, cp))
00496                       ok = 0);
00497   test_assert(ok);
00498   SMARTLIST_FOREACH(included, const char *, cp,
00499                     digestset_add(set, cp));
00500   SMARTLIST_FOREACH(included, const char *, cp,
00501                     if (!digestset_isin(set, cp))
00502                       ok = 0);
00503   test_assert(ok);
00504   for (i = 0; i < 1000; ++i) {
00505     crypto_rand(d, DIGEST_LEN);
00506     if (digestset_isin(set, d))
00507       ++false_positives;
00508   }
00509   test_assert(false_positives < 50); /* Should be far lower. */
00510 
00511  done:
00512   if (set)
00513     digestset_free(set);
00514   SMARTLIST_FOREACH(included, char *, cp, tor_free(cp));
00515   smartlist_free(included);
00516 }
00517 
00518 typedef struct pq_entry_t {
00519   const char *val;
00520   int idx;
00521 } pq_entry_t;
00522 
00524 static int
00525 _compare_strings_for_pqueue(const void *p1, const void *p2)
00526 {
00527   const pq_entry_t *e1=p1, *e2=p2;
00528   return strcmp(e1->val, e2->val);
00529 }
00530 
00532 static void
00533 test_container_pqueue(void)
00534 {
00535   smartlist_t *sl = smartlist_new();
00536   int (*cmp)(const void *, const void*);
00537   const int offset = STRUCT_OFFSET(pq_entry_t, idx);
00538 #define ENTRY(s) pq_entry_t s = { #s, -1 }
00539   ENTRY(cows);
00540   ENTRY(zebras);
00541   ENTRY(fish);
00542   ENTRY(frogs);
00543   ENTRY(apples);
00544   ENTRY(squid);
00545   ENTRY(daschunds);
00546   ENTRY(eggplants);
00547   ENTRY(weissbier);
00548   ENTRY(lobsters);
00549   ENTRY(roquefort);
00550   ENTRY(chinchillas);
00551   ENTRY(fireflies);
00552 
00553 #define OK() smartlist_pqueue_assert_ok(sl, cmp, offset)
00554 
00555   cmp = _compare_strings_for_pqueue;
00556   smartlist_pqueue_add(sl, cmp, offset, &cows);
00557   smartlist_pqueue_add(sl, cmp, offset, &zebras);
00558   smartlist_pqueue_add(sl, cmp, offset, &fish);
00559   smartlist_pqueue_add(sl, cmp, offset, &frogs);
00560   smartlist_pqueue_add(sl, cmp, offset, &apples);
00561   smartlist_pqueue_add(sl, cmp, offset, &squid);
00562   smartlist_pqueue_add(sl, cmp, offset, &daschunds);
00563   smartlist_pqueue_add(sl, cmp, offset, &eggplants);
00564   smartlist_pqueue_add(sl, cmp, offset, &weissbier);
00565   smartlist_pqueue_add(sl, cmp, offset, &lobsters);
00566   smartlist_pqueue_add(sl, cmp, offset, &roquefort);
00567 
00568   OK();
00569 
00570   test_eq(smartlist_len(sl), 11);
00571   test_eq_ptr(smartlist_get(sl, 0), &apples);
00572   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &apples);
00573   test_eq(smartlist_len(sl), 10);
00574   OK();
00575   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &cows);
00576   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &daschunds);
00577   smartlist_pqueue_add(sl, cmp, offset, &chinchillas);
00578   OK();
00579   smartlist_pqueue_add(sl, cmp, offset, &fireflies);
00580   OK();
00581   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &chinchillas);
00582   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &eggplants);
00583   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fireflies);
00584   OK();
00585   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fish);
00586   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &frogs);
00587   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &lobsters);
00588   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &roquefort);
00589   OK();
00590   test_eq(smartlist_len(sl), 3);
00591   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &squid);
00592   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &weissbier);
00593   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &zebras);
00594   test_eq(smartlist_len(sl), 0);
00595   OK();
00596 
00597   /* Now test remove. */
00598   smartlist_pqueue_add(sl, cmp, offset, &cows);
00599   smartlist_pqueue_add(sl, cmp, offset, &fish);
00600   smartlist_pqueue_add(sl, cmp, offset, &frogs);
00601   smartlist_pqueue_add(sl, cmp, offset, &apples);
00602   smartlist_pqueue_add(sl, cmp, offset, &squid);
00603   smartlist_pqueue_add(sl, cmp, offset, &zebras);
00604   test_eq(smartlist_len(sl), 6);
00605   OK();
00606   smartlist_pqueue_remove(sl, cmp, offset, &zebras);
00607   test_eq(smartlist_len(sl), 5);
00608   OK();
00609   smartlist_pqueue_remove(sl, cmp, offset, &cows);
00610   test_eq(smartlist_len(sl), 4);
00611   OK();
00612   smartlist_pqueue_remove(sl, cmp, offset, &apples);
00613   test_eq(smartlist_len(sl), 3);
00614   OK();
00615   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &fish);
00616   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &frogs);
00617   test_eq_ptr(smartlist_pqueue_pop(sl, cmp, offset), &squid);
00618   test_eq(smartlist_len(sl), 0);
00619   OK();
00620 
00621 #undef OK
00622 
00623  done:
00624 
00625   smartlist_free(sl);
00626 }
00627 
00629 static void
00630 test_container_strmap(void)
00631 {
00632   strmap_t *map;
00633   strmap_iter_t *iter;
00634   const char *k;
00635   void *v;
00636   char *visited = NULL;
00637   smartlist_t *found_keys = NULL;
00638 
00639   map = strmap_new();
00640   test_assert(map);
00641   test_eq(strmap_size(map), 0);
00642   test_assert(strmap_isempty(map));
00643   v = strmap_set(map, "K1", (void*)99);
00644   test_eq(v, NULL);
00645   test_assert(!strmap_isempty(map));
00646   v = strmap_set(map, "K2", (void*)101);
00647   test_eq(v, NULL);
00648   v = strmap_set(map, "K1", (void*)100);
00649   test_eq(v, (void*)99);
00650   test_eq_ptr(strmap_get(map,"K1"), (void*)100);
00651   test_eq_ptr(strmap_get(map,"K2"), (void*)101);
00652   test_eq_ptr(strmap_get(map,"K-not-there"), NULL);
00653   strmap_assert_ok(map);
00654 
00655   v = strmap_remove(map,"K2");
00656   strmap_assert_ok(map);
00657   test_eq_ptr(v, (void*)101);
00658   test_eq_ptr(strmap_get(map,"K2"), NULL);
00659   test_eq_ptr(strmap_remove(map,"K2"), NULL);
00660 
00661   strmap_set(map, "K2", (void*)101);
00662   strmap_set(map, "K3", (void*)102);
00663   strmap_set(map, "K4", (void*)103);
00664   test_eq(strmap_size(map), 4);
00665   strmap_assert_ok(map);
00666   strmap_set(map, "K5", (void*)104);
00667   strmap_set(map, "K6", (void*)105);
00668   strmap_assert_ok(map);
00669 
00670   /* Test iterator. */
00671   iter = strmap_iter_init(map);
00672   found_keys = smartlist_new();
00673   while (!strmap_iter_done(iter)) {
00674     strmap_iter_get(iter,&k,&v);
00675     smartlist_add(found_keys, tor_strdup(k));
00676     test_eq_ptr(v, strmap_get(map, k));
00677 
00678     if (!strcmp(k, "K2")) {
00679       iter = strmap_iter_next_rmv(map,iter);
00680     } else {
00681       iter = strmap_iter_next(map,iter);
00682     }
00683   }
00684 
00685   /* Make sure we removed K2, but not the others. */
00686   test_eq_ptr(strmap_get(map, "K2"), NULL);
00687   test_eq_ptr(strmap_get(map, "K5"), (void*)104);
00688   /* Make sure we visited everyone once */
00689   smartlist_sort_strings(found_keys);
00690   visited = smartlist_join_strings(found_keys, ":", 0, NULL);
00691   test_streq(visited, "K1:K2:K3:K4:K5:K6");
00692 
00693   strmap_assert_ok(map);
00694   /* Clean up after ourselves. */
00695   strmap_free(map, NULL);
00696   map = NULL;
00697 
00698   /* Now try some lc functions. */
00699   map = strmap_new();
00700   strmap_set_lc(map,"Ab.C", (void*)1);
00701   test_eq_ptr(strmap_get(map,"ab.c"), (void*)1);
00702   strmap_assert_ok(map);
00703   test_eq_ptr(strmap_get_lc(map,"AB.C"), (void*)1);
00704   test_eq_ptr(strmap_get(map,"AB.C"), NULL);
00705   test_eq_ptr(strmap_remove_lc(map,"aB.C"), (void*)1);
00706   strmap_assert_ok(map);
00707   test_eq_ptr(strmap_get_lc(map,"AB.C"), NULL);
00708 
00709  done:
00710   if (map)
00711     strmap_free(map,NULL);
00712   if (found_keys) {
00713     SMARTLIST_FOREACH(found_keys, char *, cp, tor_free(cp));
00714     smartlist_free(found_keys);
00715   }
00716   tor_free(visited);
00717 }
00718 
00720 static void
00721 test_container_order_functions(void)
00722 {
00723   int lst[25], n = 0;
00724   //  int a=12,b=24,c=25,d=60,e=77;
00725 
00726 #define median() median_int(lst, n)
00727 
00728   lst[n++] = 12;
00729   test_eq(12, median()); /* 12 */
00730   lst[n++] = 77;
00731   //smartlist_shuffle(sl);
00732   test_eq(12, median()); /* 12, 77 */
00733   lst[n++] = 77;
00734   //smartlist_shuffle(sl);
00735   test_eq(77, median()); /* 12, 77, 77 */
00736   lst[n++] = 24;
00737   test_eq(24, median()); /* 12,24,77,77 */
00738   lst[n++] = 60;
00739   lst[n++] = 12;
00740   lst[n++] = 25;
00741   //smartlist_shuffle(sl);
00742   test_eq(25, median()); /* 12,12,24,25,60,77,77 */
00743 #undef median
00744 
00745  done:
00746   ;
00747 }
00748 
00749 #define CONTAINER_LEGACY(name)                                          \
00750   { #name, legacy_test_helper, 0, &legacy_setup, test_container_ ## name }
00751 
00752 struct testcase_t container_tests[] = {
00753   CONTAINER_LEGACY(smartlist_basic),
00754   CONTAINER_LEGACY(smartlist_strings),
00755   CONTAINER_LEGACY(smartlist_overlap),
00756   CONTAINER_LEGACY(smartlist_digests),
00757   CONTAINER_LEGACY(smartlist_join),
00758   CONTAINER_LEGACY(bitarray),
00759   CONTAINER_LEGACY(digestset),
00760   CONTAINER_LEGACY(strmap),
00761   CONTAINER_LEGACY(pqueue),
00762   CONTAINER_LEGACY(order_functions),
00763   END_OF_TESTCASES
00764 };
00765