diff options
| -rw-r--r-- | ChangeLog | 3 | ||||
| -rw-r--r-- | src/common/container.h | 74 | ||||
| -rw-r--r-- | src/or/networkstatus.c | 106 | ||||
| -rw-r--r-- | src/or/test.c | 45 |
4 files changed, 153 insertions, 75 deletions
@@ -56,7 +56,8 @@ Changes in version 0.2.1.1-alpha - 2008-??-?? - Refactor code using connection_ap_handshake_attach_circuit() to allow that function to mark connections for close. Part of a fix for bug 617. Bugfix on 0.2.0.1-alpha. - + - Add a macro to implement the common pattern of iterating through + two parallel lists in lockstep. Changes in version 0.2.0.23-rc - 2008-03-24 o Major bugfixes: diff --git a/src/common/container.h b/src/common/container.h index 6daef6e833..866cb1b8a9 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -215,6 +215,80 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join, --var ## _sl_len; \ STMT_END +/* Helper: Given two lists of items, possibly of different types, such that + * both lists are sorted on some common field (as determened by a comparison + * expression <b>cmpexpr</b>), and such that one list (<b>sl1</b>) has no + * duplicates on the common field, loop through the lists in lockstep, and + * execute <b>unmatched_var2</b> on items in var2 that do not appear in + * var1. + * + * WARNING: It isn't safe to add remove elements from either list while the + * loop is in progress. + * + * Example use: + * SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs, + * routerinfo_list, routerinfo_t *, ri, + * memcmp(rs->identity_digest, ri->identity_digest, 20), + * log_info(LD_GENERAL,"No match for %s", ri->nickname)) { + * log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs); + * } SMARTLIST_FOREACH_JOIN_END(rs, ri); + **/ +/* The example above unpacks (approximately) to: + * int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list); + * int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list); + * int rs_ri_cmp; + * routerstatus_t *rs; + * routerinfo_t *ri; + * for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) { + * ri = smartlist_get(routerinfo_list, ri_sl_idx); + * while (rs_sl_idx < rs_sl_len) { + * rs = smartlist_get(routerstatus_list, rs_sl_idx); + * rs_ri_cmp = memcmp(rs->identity_digest, ri->identity_digest, 20); + * if (rs_ri_cmp > 0) { + * break; + * } else if (rs_ri_cmp == 0) { + * goto matched_ri; + * } else { + * ++rs_sl_idx; + * } + * } + * log_info(LD_GENERAL,"No match for %s", ri->nickname); + * continue; + * matched_ri: { + * log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs); + * } + * } + */ +#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, \ + cmpexpr, unmatched_var2) \ + STMT_BEGIN \ + int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used; \ + int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used; \ + int var1 ## _ ## var2 ## _cmp; \ + type1 var1; \ + type2 var2; \ + for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) { \ + var2 = (sl2)->list[var2##_sl_idx]; \ + while (var1##_sl_idx < var1##_sl_len) { \ + var1 = (sl1)->list[var1##_sl_idx]; \ + var1##_##var2##_cmp = (cmpexpr); \ + if (var1##_##var2##_cmp > 0) { \ + break; \ + } else if (var1##_##var2##_cmp == 0) { \ + goto matched_##var2; \ + } else { \ + ++var1##_sl_idx; \ + } \ + } \ + /* Ran out of v1, or no match for var2. */ \ + unmatched_var2; \ + continue; \ + matched_##var2: ; \ + +#define SMARTLIST_FOREACH_JOIN_END(var1, var2) \ + } \ + STMT_END + #define DECLARE_MAP_FNS(maptype, keytype, prefix) \ typedef struct maptype maptype; \ typedef struct prefix##entry_t *prefix##iter_t; \ diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index 4ed4993b51..2aa0fb496a 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -1289,35 +1289,23 @@ static void notify_control_networkstatus_changed(const networkstatus_t *old_c, const networkstatus_t *new_c) { - int idx = 0; - int old_remain = old_c && smartlist_len(old_c->routerstatus_list); - const routerstatus_t *rs_old = NULL; smartlist_t *changed; if (old_c == new_c) return; + if (!old_c) { + control_event_networkstatus_changed(new_c->routerstatus_list); + return; + } changed = smartlist_create(); - if (old_remain) - rs_old = smartlist_get(old_c->routerstatus_list, idx); - /* XXXX021 candidate for a foreach_matched macro. */ - SMARTLIST_FOREACH(new_c->routerstatus_list, routerstatus_t *, rs_new, - { - if (!old_remain) { + SMARTLIST_FOREACH_JOIN(old_c->routerstatus_list, routerstatus_t *, rs_old, + new_c->routerstatus_list, routerstatus_t *, rs_new, + memcmp(rs_old->identity_digest, + rs_new->identity_digest, DIGEST_LEN), + smartlist_add(changed, rs_new)) { + if (routerstatus_has_changed(rs_old, rs_new)) smartlist_add(changed, rs_new); - } else { - int r; - while ((r = memcmp(rs_old->identity_digest, rs_new->identity_digest, - DIGEST_LEN)) < 0) { - if (++idx == smartlist_len(old_c->routerstatus_list)) { - old_remain = 0; - break; - } - rs_old = smartlist_get(old_c->routerstatus_list, idx); - } - if (r || (!r && routerstatus_has_changed(rs_old, rs_new))) - smartlist_add(changed, rs_new); - } - }); + } SMARTLIST_FOREACH_JOIN_END(rs_old, rs_new); control_event_networkstatus_changed(changed); smartlist_free(changed); @@ -1329,28 +1317,16 @@ static void networkstatus_copy_old_consensus_info(networkstatus_t *new_c, const networkstatus_t *old_c) { - int idx = 0; - const routerstatus_t *rs_old; if (old_c == new_c) return; - if (!smartlist_len(old_c->routerstatus_list)) + if (!old_c || !smartlist_len(old_c->routerstatus_list)) return; - rs_old = smartlist_get(old_c->routerstatus_list, idx); - /* XXXX021 candidate for a FOREACH_MATCHED macro. */ - SMARTLIST_FOREACH(new_c->routerstatus_list, routerstatus_t *, rs_new, - { - int r; - while ((r = memcmp(rs_old->identity_digest, rs_new->identity_digest, - DIGEST_LEN))<0) { - if (++idx == smartlist_len(old_c->routerstatus_list)) - goto done; - rs_old = smartlist_get(old_c->routerstatus_list, idx); - } - if (r>0) - continue; - tor_assert(r==0); - + SMARTLIST_FOREACH_JOIN(old_c->routerstatus_list, routerstatus_t *, rs_old, + new_c->routerstatus_list, routerstatus_t *, rs_new, + memcmp(rs_old->identity_digest, + rs_new->identity_digest, DIGEST_LEN), + STMT_NIL) { /* Okay, so we're looking at the same identity. */ rs_new->name_lookup_warned = rs_old->name_lookup_warned; rs_new->last_dir_503_at = rs_old->last_dir_503_at; @@ -1360,10 +1336,7 @@ networkstatus_copy_old_consensus_info(networkstatus_t *new_c, /* And the same descriptor too! */ memcpy(&rs_new->dl_status, &rs_old->dl_status,sizeof(download_status_t)); } - }); - - done: - return; + } SMARTLIST_FOREACH_JOIN_END(rs_old, rs_new); } /** Try to replace the current cached v3 networkstatus with the one in @@ -1709,44 +1682,29 @@ routers_update_status_from_consensus_networkstatus(smartlist_t *routers, int reset_failures) { trusted_dir_server_t *ds; - routerstatus_t *rs; or_options_t *options = get_options(); int authdir = authdir_mode_v2(options) || authdir_mode_v3(options); int namingdir = authdir && options->NamingAuthoritativeDir; networkstatus_t *ns = current_consensus; - int idx; if (!ns || !smartlist_len(ns->routerstatus_list)) return; routers_sort_by_identity(routers); - /* Now routers and ns->routerstatus_list are both in ascending order - * of identity digest. */ - idx = 0; - rs = smartlist_get(ns->routerstatus_list, idx); - /* Candidate for a FOREACH_MATCHED macro.XXX021 */ - SMARTLIST_FOREACH(routers, routerinfo_t *, router, + SMARTLIST_FOREACH_JOIN(ns->routerstatus_list, routerstatus_t *, rs, + routers, routerinfo_t *, router, + memcmp(rs->identity_digest, + router->cache_info.identity_digest, DIGEST_LEN), { - const char *digest = router->cache_info.identity_digest; - int r; - while ((r = memcmp(rs->identity_digest, digest, DIGEST_LEN))<0) { - if (++idx == smartlist_len(ns->routerstatus_list)) { - /* We're out of routerstatuses. Bail. */ - goto done; - } - rs = smartlist_get(ns->routerstatus_list, idx); - } - if (r>0) { - /* We have no routerstatus for this router. Clear flags and skip it. */ - if (!namingdir) - router->is_named = 0; - if (!authdir) { - if (router->purpose == ROUTER_PURPOSE_GENERAL) - router_clear_status_flags(router); - } - continue; + /* We have no routerstatus for this router. Clear flags and skip it. */ + if (!namingdir) + router->is_named = 0; + if (!authdir) { + if (router->purpose == ROUTER_PURPOSE_GENERAL) + router_clear_status_flags(router); } - tor_assert(r==0); + }) { + const char *digest = router->cache_info.identity_digest; ds = router_get_trusteddirserver_by_digest(digest); @@ -1756,6 +1714,7 @@ routers_update_status_from_consensus_networkstatus(smartlist_t *routers, else router->is_named = 0; } + /*XXXX021 this should always be true! */ if (!memcmp(router->cache_info.signed_descriptor_digest, rs->descriptor_digest, DIGEST_LEN)) { if (ns->valid_until > router->cache_info.last_listed_as_valid_until) @@ -1780,9 +1739,8 @@ routers_update_status_from_consensus_networkstatus(smartlist_t *routers, if (reset_failures) { download_status_reset(&rs->dl_status); } - }); + } SMARTLIST_FOREACH_JOIN_END(rs, router); - done: router_dir_info_changed(); } diff --git a/src/or/test.c b/src/or/test.c index c8f00b316f..c421523a3f 100644 --- a/src/or/test.c +++ b/src/or/test.c @@ -1837,6 +1837,51 @@ test_util_smartlist(void) smartlist_clear(sl); } + { + smartlist_t *sl2 = smartlist_create(), *sl3 = smartlist_create(), + *sl4 = smartlist_create(); + /* unique, sorted. */ + smartlist_split_string(sl, + "Abashments Ambush Anchorman Bacon Banks Borscht " + "Bunks Inhumane Insurance Knish Know Manners " + "Maraschinos Stamina Sunbonnets Unicorns Wombats", + " ", 0, 0); + /* non-unique, sorted. */ + smartlist_split_string(sl2, + "Ambush Anchorman Anchorman Anemias Anemias Bacon " + "Crossbowmen Inhumane Insurance Knish Know Manners " + "Manners Maraschinos Wombats Wombats Work", + " ", 0, 0); + SMARTLIST_FOREACH_JOIN(sl, char *, cp1, + sl2, char *, cp2, + strcmp(cp1,cp2), + smartlist_add(sl3, cp2)) { + test_streq(cp1, cp2); + smartlist_add(sl4, cp1); + } SMARTLIST_FOREACH_JOIN_END(cp1, cp2); + + SMARTLIST_FOREACH(sl3, const char *, cp, + test_assert(smartlist_isin(sl2, cp) && + !smartlist_string_isin(sl, cp))); + SMARTLIST_FOREACH(sl4, const char *, cp, + test_assert(smartlist_isin(sl, cp) && + smartlist_string_isin(sl2, cp))); + cp = smartlist_join_strings(sl3, ",", 0, NULL); + test_streq(cp, "Anemias,Anemias,Crossbowmen,Work"); + tor_free(cp); + cp = smartlist_join_strings(sl4, ",", 0, NULL); + test_streq(cp, "Ambush,Anchorman,Anchorman,Bacon,Inhumane,Insurance," + "Knish,Know,Manners,Manners,Maraschinos,Wombats,Wombats"); + tor_free(cp); + + smartlist_free(sl4); + smartlist_free(sl3); + SMARTLIST_FOREACH(sl2, char *, cp, tor_free(cp)); + smartlist_free(sl2); + SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp)); + smartlist_clear(sl); + } + smartlist_free(sl); } |