diff options
| -rw-r--r-- | doc/TODO | 2 | ||||
| -rw-r--r-- | src/common/container.c | 39 | ||||
| -rw-r--r-- | src/common/container.h | 5 | ||||
| -rw-r--r-- | src/or/router.c | 11 | ||||
| -rw-r--r-- | src/or/routerparse.c | 44 |
5 files changed, 60 insertions, 41 deletions
@@ -284,7 +284,7 @@ Minor items for 0.1.2.x as time permits: - stop writing identity key / fingerprint / etc every restart - stop caching directory stuff -- and disable mmap? - more? - - smartlist_uniq(): We have at least 3 places that check a smartlist for + o smartlist_uniq(): We have at least 3 places that check a smartlist for duplicates and then removes them: networkstatus_parse_from_string(), sort_version_list(), and router_rebuild_descriptor(). This should probably get its own function that takes a comparator and a delete function. diff --git a/src/common/container.c b/src/common/container.c index c5529058f3..64ad420633 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -429,6 +429,29 @@ smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)) (int (*)(const void *,const void*))compare); } +/** Given a sorted smartlist <b>sl</b> and the comparison function used to + * sort it, remove all duplicate members. If free_fn is provided, calls + * free_fn on each duplicate. Otherwise, frees them with tor_free(), which + * may not be what you want.. Preserves order. + */ +void +smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *a)) +{ + int i; + for (i=1; i < sl->num_used; ++i) { + if (compare((const void **)&(sl->list[i-1]), + (const void **)&(sl->list[i])) == 0) { + if (free_fn) + free_fn(sl->list[i]); + else + tor_free(sl->list[i]); + smartlist_del_keeporder(sl, i--); + } + } +} + /** Assuming the members of <b>sl</b> are in order, return a pointer to the * member which matches <b>key</b>. Ordering and matching are defined by a * <b>compare</b> function, which returns 0 on a match; less than 0 if key is @@ -462,6 +485,14 @@ smartlist_sort_strings(smartlist_t *sl) smartlist_sort(sl, _compare_string_ptrs); } +/** Remove duplicate strings from a sorted list, and free them with tor_free(). + */ +void +smartlist_uniq_strings(smartlist_t *sl) +{ + smartlist_uniq(sl, _compare_string_ptrs, NULL); +} + #define LEFT_CHILD(i) ( ((i)+1)*2 - 1) #define RIGHT_CHILD(i) ( ((i)+1)*2 ) #define PARENT(i) ( ((i)+1)/2 - 1) @@ -557,6 +588,14 @@ smartlist_sort_digests(smartlist_t *sl) smartlist_sort(sl, _compare_digests); } +/** Remove duplicate digests from a sorted list, and free them with tor_free(). + */ +void +smartlist_uniq_digests(smartlist_t *sl) +{ + smartlist_uniq(sl, _compare_digests, NULL); +} + #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \ typedef struct prefix ## entry_t { \ HT_ENTRY(prefix ## entry_t) node; \ diff --git a/src/common/container.h b/src/common/container.h index a4cac610d7..5f0417cf4d 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -74,8 +74,13 @@ void smartlist_del_keeporder(smartlist_t *sl, int idx); void smartlist_insert(smartlist_t *sl, int idx, void *val); void smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)); +void smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *elt)); void smartlist_sort_strings(smartlist_t *sl); void smartlist_sort_digests(smartlist_t *sl); +void smartlist_uniq_strings(smartlist_t *sl); +void smartlist_uniq_digests(smartlist_t *sl); void *smartlist_bsearch(smartlist_t *sl, const void *key, int (*compare)(const void *key, const void **member)) ATTR_PURE; diff --git a/src/or/router.c b/src/or/router.c index 24c8278367..032069c480 100644 --- a/src/or/router.c +++ b/src/or/router.c @@ -804,7 +804,6 @@ router_rebuild_descriptor(int force) if (authdir_mode(options)) ri->is_valid = ri->is_named = 1; /* believe in yourself */ if (options->MyFamily) { - int i; smartlist_t *family; if (!warned_nonexistent_family) warned_nonexistent_family = smartlist_create(); @@ -844,15 +843,7 @@ router_rebuild_descriptor(int force) /* remove duplicates from the list */ smartlist_sort_strings(ri->declared_family); - for (i = 1; i < smartlist_len(ri->declared_family); ++i) { - const char *a, *b; - a = smartlist_get(ri->declared_family, i-1); - b = smartlist_get(ri->declared_family, i); - if (!strcmp(a,b)) { - tor_free(smartlist_get(ri->declared_family, i)); - smartlist_del_keeporder(ri->declared_family, i--); - } - } + smartlist_uniq_strings(ri->declared_family); smartlist_free(family); } diff --git a/src/or/routerparse.c b/src/or/routerparse.c index 69b1738a6b..ce564a5115 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -1075,6 +1075,15 @@ _compare_routerstatus_entries(const void **_a, const void **_b) return memcmp(a->identity_digest, b->identity_digest, DIGEST_LEN); } +static void +_free_duplicate_routerstatus_entry(void *e) +{ + log_warn(LD_DIR, + "Network-status has two entries for the same router. " + "Dropping one."); + routerstatus_free(e); +} + /** Given a versioned (v2 or later) network-status object in <b>s</b>, try to * parse it and return the result. Return NULL on failure. Check the * signature of the network status, but do not (yet) check the signing key for @@ -1217,20 +1226,8 @@ networkstatus_parse_from_string(const char *s) smartlist_add(ns->entries, rs); } smartlist_sort(ns->entries, _compare_routerstatus_entries); - - /* Kill duplicate entries. */ - for (i=0; i < smartlist_len(ns->entries)-1; ++i) { - routerstatus_t *rs1 = smartlist_get(ns->entries, i); - routerstatus_t *rs2 = smartlist_get(ns->entries, i+1); - if (!memcmp(rs1->identity_digest, - rs2->identity_digest, DIGEST_LEN)) { - log_warn(LD_DIR, - "Network-status has two entries for the same router. " - "Dropping one."); - smartlist_del_keeporder(ns->entries, i--); - routerstatus_free(rs1); - } - } + smartlist_uniq(ns->entries, _compare_routerstatus_entries, + _free_duplicate_routerstatus_entry); if (tokenize_string(s, NULL, tokens, NETSTATUS)) { log_warn(LD_DIR, "Error tokenizing network-status footer."); @@ -1922,22 +1919,9 @@ _compare_tor_version_str_ptr(const void **_a, const void **_b) void sort_version_list(smartlist_t *versions, int remove_duplicates) { - int i; - smartlist_sort(versions, _compare_tor_version_str_ptr); - if (!remove_duplicates) - return; - - for (i = 1; i < smartlist_len(versions); ++i) { - const void *a, *b; - a = smartlist_get(versions, i-1); - b = smartlist_get(versions, i); - /* use version_cmp so we catch multiple representations of the same - * version */ - if (_compare_tor_version_str_ptr(&a,&b) == 0) { - tor_free(smartlist_get(versions, i)); - smartlist_del_keeporder(versions, i--); - } - } + + if (remove_duplicates) + smartlist_uniq(versions, _compare_tor_version_str_ptr, NULL); } |