container.c File Reference

Implements a smartlist (a resizable array) along with helper functions to use smartlists. Also includes hash table implementations of a string-to-void* map, and of a digest-to-void* map. More...

#include "compat.h"
#include "util.h"
#include "log.h"
#include "container.h"
#include "crypto.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "ht.h"

Defines

#define SMARTLIST_DEFAULT_CAPACITY   16
#define LEFT_CHILD(i)   ( 2*(i) + 1 )
#define RIGHT_CHILD(i)   ( 2*(i) + 2 )
#define PARENT(i)   ( ((i)-1) / 2 )
#define IDXP(p)   ((int*)STRUCT_VAR_P(p, idx_field_offset))
#define UPDATE_IDX(i)
#define IDX_OF_ITEM(p)   (*IDXP(p))
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)
#define OPTIMIZED_DIGESTMAP_SET
#define IMPLEMENT_ORDER_FUNC(funcname, elt_t)

Functions

smartlist_t * smartlist_create (void)
void smartlist_free (smartlist_t *sl)
void smartlist_clear (smartlist_t *sl)
static INLINE void smartlist_ensure_capacity (smartlist_t *sl, int size)
void smartlist_add (smartlist_t *sl, void *element)
void smartlist_add_all (smartlist_t *s1, const smartlist_t *s2)
void smartlist_remove (smartlist_t *sl, const void *element)
void * smartlist_pop_last (smartlist_t *sl)
void smartlist_reverse (smartlist_t *sl)
void smartlist_string_remove (smartlist_t *sl, const char *element)
int smartlist_isin (const smartlist_t *sl, const void *element)
int smartlist_string_isin (const smartlist_t *sl, const char *element)
int smartlist_string_pos (const smartlist_t *sl, const char *element)
int smartlist_string_isin_case (const smartlist_t *sl, const char *element)
int smartlist_string_num_isin (const smartlist_t *sl, int num)
int smartlist_digest_isin (const smartlist_t *sl, const char *element)
int smartlist_overlap (const smartlist_t *sl1, const smartlist_t *sl2)
void smartlist_intersect (smartlist_t *sl1, const smartlist_t *sl2)
void smartlist_subtract (smartlist_t *sl1, const smartlist_t *sl2)
void smartlist_del (smartlist_t *sl, int idx)
void smartlist_del_keeporder (smartlist_t *sl, int idx)
void smartlist_insert (smartlist_t *sl, int idx, void *val)
int smartlist_split_string (smartlist_t *sl, const char *str, const char *sep, int flags, int max)
char * smartlist_join_strings (smartlist_t *sl, const char *join, int terminate, size_t *len_out)
char * smartlist_join_strings2 (smartlist_t *sl, const char *join, size_t join_len, int terminate, size_t *len_out)
void smartlist_sort (smartlist_t *sl, int(*compare)(const void **a, const void **b))
void * smartlist_get_most_frequent (const 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 *a))
void * smartlist_bsearch (smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member))
int smartlist_bsearch_idx (const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member), int *found_out)
static int _compare_string_ptrs (const void **_a, const void **_b)
void smartlist_sort_strings (smartlist_t *sl)
char * smartlist_get_most_frequent_string (smartlist_t *sl)
void smartlist_uniq_strings (smartlist_t *sl)
static INLINE void smartlist_heapify (smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset, int idx)
void smartlist_pqueue_add (smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset, void *item)
void * smartlist_pqueue_pop (smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset)
void smartlist_pqueue_remove (smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset, void *item)
void smartlist_pqueue_assert_ok (smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset)
static int _compare_digests (const void **_a, const void **_b)
void smartlist_sort_digests (smartlist_t *sl)
void smartlist_uniq_digests (smartlist_t *sl)
static int _compare_digests256 (const void **_a, const void **_b)
void smartlist_sort_digests256 (smartlist_t *sl)
char * smartlist_get_most_frequent_digest256 (smartlist_t *sl)
void smartlist_uniq_digests256 (smartlist_t *sl)
 DEFINE_MAP_STRUCTS (strmap_t, char *key, strmap_)
 DEFINE_MAP_STRUCTS (digestmap_t, char key[DIGEST_LEN], digestmap_)
static INLINE int strmap_entries_eq (const strmap_entry_t *a, const strmap_entry_t *b)
static INLINE unsigned int strmap_entry_hash (const strmap_entry_t *a)
static INLINE int digestmap_entries_eq (const digestmap_entry_t *a, const digestmap_entry_t *b)
static INLINE unsigned int digestmap_entry_hash (const digestmap_entry_t *a)
 HT_PROTOTYPE (HT_GENERATE(strmap_impl, HT_GENERATE(strmap_entry_t, HT_GENERATE(node, HT_GENERATE(strmap_entry_hash, HT_GENERATE(strmap_entries_eq)
digestmap_t * digestmap_new (void)
void * strmap_set (strmap_t *map, const char *key, void *val)
void * digestmap_set (digestmap_t *map, const char *key, void *val)
void * strmap_get (const strmap_t *map, const char *key)
void * digestmap_get (const digestmap_t *map, const char *key)
void * strmap_remove (strmap_t *map, const char *key)
void * digestmap_remove (digestmap_t *map, const char *key)
void * strmap_set_lc (strmap_t *map, const char *key, void *val)
void * strmap_get_lc (const strmap_t *map, const char *key)
void * strmap_remove_lc (strmap_t *map, const char *key)
strmap_iter_t * strmap_iter_init (strmap_t *map)
digestmap_iter_t * digestmap_iter_init (digestmap_t *map)
strmap_iter_t * strmap_iter_next (strmap_t *map, strmap_iter_t *iter)
digestmap_iter_t * digestmap_iter_next (digestmap_t *map, digestmap_iter_t *iter)
strmap_iter_t * strmap_iter_next_rmv (strmap_t *map, strmap_iter_t *iter)
digestmap_iter_t * digestmap_iter_next_rmv (digestmap_t *map, digestmap_iter_t *iter)
void strmap_iter_get (strmap_iter_t *iter, const char **keyp, void **valp)
void digestmap_iter_get (digestmap_iter_t *iter, const char **keyp, void **valp)
int strmap_iter_done (strmap_iter_t *iter)
int digestmap_iter_done (digestmap_iter_t *iter)
void strmap_free (strmap_t *map, void(*free_val)(void *))
void digestmap_free (digestmap_t *map, void(*free_val)(void *))
void strmap_assert_ok (const strmap_t *map)
void digestmap_assert_ok (const digestmap_t *map)
int strmap_isempty (const strmap_t *map)
int digestmap_isempty (const digestmap_t *map)
int strmap_size (const strmap_t *map)
int digestmap_size (const digestmap_t *map)
digestset_t * digestset_new (int max_elements)
void digestset_free (digestset_t *set)

Detailed Description

Implements a smartlist (a resizable array) along with helper functions to use smartlists. Also includes hash table implementations of a string-to-void* map, and of a digest-to-void* map.

Define Documentation

#define DEFINE_MAP_STRUCTS ( maptype,
keydecl,
prefix   ) 

Value:

typedef struct prefix ## entry_t {                      \
    HT_ENTRY(prefix ## entry_t) node;                     \
    void *val;                                            \
    keydecl;                                              \
  } prefix ## entry_t;                                    \
  struct maptype {                                        \
    HT_HEAD(prefix ## impl, prefix ## entry_t) head;      \
  }
Helper: Declare an entry type and a map type to implement a mapping using ht.h. The map type will be called maptype. The key part of each entry is declared using the C declaration keydecl. All functions and types associated with the map get prefixed with prefix

#define IMPLEMENT_ORDER_FUNC ( funcname,
elt_t   ) 

Value:

static int                                                    \
  _cmp_ ## elt_t(const void *_a, const void *_b)                \
  {                                                             \
    const elt_t *a = _a, *b = _b;                               \
    if (*a<*b)                                                  \
      return -1;                                                \
    else if (*a>*b)                                             \
      return 1;                                                 \
    else                                                        \
      return 0;                                                 \
  }                                                             \
  elt_t                                                         \
  funcname(elt_t *array, int n_elements, int nth)               \
  {                                                             \
    tor_assert(nth >= 0);                                       \
    tor_assert(nth < n_elements);                               \
    qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t);     \
    return array[nth];                                          \
  }
Declare a function called funcname that acts as a find_nth_FOO function for an array of type elt_t*.

NOTE: The implementation kind of sucks: It's O(n log n), whereas finding the kth element of an n-element list can be done in O(n). Then again, this implementation is not in critical path, and it is obviously correct.

#define SMARTLIST_DEFAULT_CAPACITY   16

All newly allocated smartlists have this capacity.

Referenced by smartlist_create().

#define UPDATE_IDX ( i   ) 

Value:

do {                            \
    void *updated = sl->list[i];                       \
    *IDXP(updated) = i;                                \
  } while (0)

Function Documentation

static int _compare_digests ( const void **  _a,
const void **  _b 
) [static]

Helper: compare two DIGEST_LEN digests.

References DIGEST_LEN.

Referenced by smartlist_sort_digests(), and smartlist_uniq_digests().

static int _compare_digests256 ( const void **  _a,
const void **  _b 
) [static]

Helper: compare two DIGEST256_LEN digests.

References DIGEST256_LEN.

Referenced by smartlist_get_most_frequent_digest256(), smartlist_sort_digests256(), and smartlist_uniq_digests256().

static int _compare_string_ptrs ( const void **  _a,
const void **  _b 
) [static]

Helper: compare two const char **s.

Referenced by smartlist_get_most_frequent_string(), smartlist_sort_strings(), and smartlist_uniq_strings().

void digestmap_assert_ok ( const digestmap_t *  map  ) 

Fail with an assertion error if anything has gone wrong with the internal representation of map.

References tor_assert.

static INLINE int digestmap_entries_eq ( const digestmap_entry_t *  a,
const digestmap_entry_t *  b 
) [static]

Helper: compare digestmap_entry_t objects by key value.

References DIGEST_LEN.

static INLINE unsigned int digestmap_entry_hash ( const digestmap_entry_t *  a  )  [static]

Helper: return a hash value for a digest_map_t.

Referenced by digestmap_set().

void digestmap_free ( digestmap_t *  map,
void(*)(void *)  free_val 
)

Remove all entries from map, and deallocate storage for those entries. If free_val is provided, it is invoked on every value in map.

References tor_assert, and tor_free.

Referenced by dirserv_free_all(), dirserv_free_fingerprint_list(), download_status_map_update_from_v2_networkstatus(), entry_guards_compute_status(), entry_guards_parse_state(), free_or_history(), networkstatus_free_all(), networkstatus_vote_free(), rend_cache_free_all(), rend_service_free(), rep_hist_free_all(), routerlist_free_all(), routerset_free(), and update_extrainfo_downloads().

void* digestmap_get ( const digestmap_t *  map,
const char *  key 
)

Like strmap_get() above but for digestmaps.

References DIGEST_LEN, and tor_assert.

Referenced by add_fingerprint_to_dir(), authority_cert_dl_failed(), authority_cert_get_by_digests(), authority_cert_get_newest_by_id(), authority_certs_fetch_missing(), connection_or_get_for_extend(), connection_or_remove_from_identity_map(), dirserv_get_networkstatus_v2(), dirserv_get_nickname_by_digest(), dirserv_get_status_impl(), dirserv_set_cached_networkstatus_v2(), download_status_map_update_from_v2_networkstatus(), entry_guards_compute_status(), entry_guards_parse_state(), extrainfo_parse_entry_from_string(), get_cert_list(), get_link_history(), get_or_history(), lookup_cached_dir_by_fp(), rend_cache_lookup_v2_desc_as_dir(), rend_cache_store_v2_desc_as_dir(), rend_service_introduce(), router_get_dl_status_by_descriptor_digest(), routerset_contains(), signed_descs_update_status_from_consensus_networkstatus(), update_extrainfo_downloads(), and update_router_descriptor_cache_downloads_v2().

int digestmap_isempty ( const digestmap_t *  map  ) 

Return true iff map has no entries.

Referenced by rep_hist_dump_stats().

int digestmap_iter_done ( digestmap_iter_t *  iter  ) 

Return true iff iter has advanced past the last entry of map.

Referenced by dirserv_get_networkstatus_v2_fingerprints(), dirserv_set_cached_networkstatus_v2(), rend_cache_clean_v2_descs_as_dir(), rep_hist_downrate_old_runs(), rep_hist_dump_stats(), rep_hist_record_mtbf_data(), and rep_history_clean().

void digestmap_iter_get ( digestmap_iter_t *  iter,
const char **  keyp,
void **  valp 
)

Set *keyp and *valp to the current entry pointed to by iter.

References tor_assert.

Referenced by dirserv_get_networkstatus_v2_fingerprints(), dirserv_set_cached_networkstatus_v2(), rend_cache_clean_v2_descs_as_dir(), rep_hist_downrate_old_runs(), rep_hist_dump_stats(), rep_hist_record_mtbf_data(), and rep_history_clean().

digestmap_iter_t* digestmap_iter_init ( digestmap_t *  map  ) 

Start iterating through map. See strmap_iter_init() for example.

References tor_assert.

Referenced by dirserv_get_networkstatus_v2_fingerprints(), dirserv_set_cached_networkstatus_v2(), rend_cache_clean_v2_descs_as_dir(), rep_hist_downrate_old_runs(), rep_hist_dump_stats(), rep_hist_record_mtbf_data(), and rep_history_clean().

digestmap_iter_t* digestmap_iter_next ( digestmap_t *  map,
digestmap_iter_t *  iter 
)

Advance the iterator iter for map a single step to the next entry, and return its new value.

References tor_assert.

Referenced by dirserv_get_networkstatus_v2_fingerprints(), dirserv_set_cached_networkstatus_v2(), rend_cache_clean_v2_descs_as_dir(), rep_hist_downrate_old_runs(), rep_hist_dump_stats(), rep_hist_record_mtbf_data(), and rep_history_clean().

digestmap_iter_t* digestmap_iter_next_rmv ( digestmap_t *  map,
digestmap_iter_t *  iter 
)

Advance the iterator iter a single step to the next entry, removing the current entry, and return its new value.

References tor_assert, and tor_free.

Referenced by rend_cache_clean_v2_descs_as_dir(), and rep_history_clean().

digestmap_t* digestmap_new ( void   ) 

Constructor to create a new empty map from digests to void*'s.

Referenced by authdir_config_new(), authority_certs_fetch_missing(), connection_or_set_identity_digest(), dirserv_get_networkstatus_v2(), dirserv_get_networkstatus_v2_fingerprints(), dirserv_set_cached_networkstatus_v2(), download_status_map_update_from_v2_networkstatus(), dump_distinct_digest_count(), entry_guards_compute_status(), entry_guards_parse_state(), get_cert_list(), get_or_history(), get_possible_sybil_list(), rend_cache_init(), rend_service_introduce(), rep_hist_downrate_old_runs(), rep_hist_init(), router_get_consensus_status_by_descriptor_digest(), router_parse_entry_from_string(), routerset_new(), update_consensus_router_descriptor_downloads(), update_extrainfo_downloads(), and update_router_descriptor_cache_downloads_v2().

void* digestmap_remove ( digestmap_t *  map,
const char *  key 
)

Like strmap_remove() above but for digestmaps.

References DIGEST_LEN, tor_assert, and tor_free.

Referenced by connection_or_remove_from_identity_map(), dirserv_set_cached_networkstatus_v2(), and download_status_map_update_from_v2_networkstatus().

void* digestmap_set ( digestmap_t *  map,
const char *  key,
void *  val 
)

Like strmap_set() above but for digestmaps.

References DIGEST_LEN, digestmap_entry_hash(), and tor_assert.

Referenced by add_fingerprint_to_dir(), connection_or_remove_from_identity_map(), connection_or_set_identity_digest(), dirserv_set_cached_networkstatus_v2(), download_status_map_update_from_v2_networkstatus(), entry_guards_compute_status(), entry_guards_parse_state(), get_cert_list(), get_link_history(), get_or_history(), get_possible_sybil_list(), rend_cache_store_v2_desc_as_dir(), rend_service_introduce(), router_get_consensus_status_by_descriptor_digest(), router_parse_entry_from_string(), and routerset_parse().

int digestmap_size ( const digestmap_t *  map  ) 

Return the number of items in map.

Referenced by dirserv_get_networkstatus_v2_fingerprints(), dirserv_get_status_impl(), dirserv_set_cached_networkstatus_v2(), and dump_distinct_digest_count().

void digestset_free ( digestset_t *  set  ) 

Free all storage held in set.

References tor_free.

Referenced by routerlist_remove_old_routers().

digestset_t* digestset_new ( int  max_elements  ) 

Return a newly allocated digestset_t, optimized to hold a total of max_elements digests with a reasonably low false positive weight.

References tor_log2().

Referenced by routerlist_remove_old_routers().

HT_PROTOTYPE ( HT_GENERATE(  strmap_impl,
HT_GENERATE(  strmap_entry_t,
HT_GENERATE(  node,
HT_GENERATE(  strmap_entry_hash,
HT_GENERATE(  strmap_entries_eq 
)

Constructor to create a new empty map from strings to void*'s.

void smartlist_add ( smartlist_t *  sl,
void *  element 
)

Append element to the end of the list.

References smartlist_t::list, smartlist_t::num_used, and smartlist_ensure_capacity().

Referenced by add_an_entry_guard(), add_connection_to_closeable_list(), add_nickname_list_to_smartlist(), add_predicted_port(), add_trusted_dir_server(), add_wildcarded_test_address(), addressmap_get_mappings(), append_bytes_to_file(), authority_cert_get_all(), authority_certs_fetch_missing(), authority_type_to_string(), bridge_add_from_config(), choose_good_entry_server(), choose_good_exit_server_general(), choose_good_middle_server(), choose_random_entry(), circuit_get_all_pending_on_or_conn(), circuit_get_unhandled_ports(), circuit_list_path_impl(), circuit_set_state(), client_check_address_changed(), config_dump(), connection_add(), connection_dir_client_reached_eof(), connection_start_reading_from_linked_conn(), control_event_descriptors_changed(), control_event_networkstatus_changed_helper(), control_event_networkstatus_changed_single(), control_setconf_helper(), decode_hashed_passwords(), dir_split_resource_into_fingerprint_pairs(), directory_get_consensus_url(), directory_handle_command_get(), directory_post_to_hs_dir(), dirserv_add_descriptor(), dirserv_get_networkstatus_v2(), dirserv_get_networkstatus_v2_fingerprints(), dirserv_get_routerdesc_fingerprints(), dirserv_get_routerdescs(), dirvote_add_signatures(), dirvote_compute_consensuses(), dirvote_compute_params(), dirvote_fetch_missing_votes(), entry_guards_parse_state(), entry_guards_prepend_from_config(), find_all_exitpolicy(), geoip_add_entry(), geoip_get_client_history(), geoip_get_dirreq_history(), geoip_get_request_history(), geoip_load_file(), get_detached_signatures_from_pending_consensuses(), get_frequent_members(), getinfo_helper_config(), getinfo_helper_dir(), getinfo_helper_entry_guards(), getinfo_helper_events(), getinfo_helper_networkstatus(), handle_control_extendcircuit(), handle_control_getconf(), handle_control_getinfo(), handle_control_mapaddress(), handle_control_protocolinfo(), handle_control_resolve(), hid_serv_get_responsible_directories(), list_getinfo_options(), list_server_status_v1(), list_v3_auth_ids(), log_credential_status(), log_entry_guards(), make_consensus_method_list(), microdesc_cache_rebuild(), microdescs_parse_from_string(), networkstatus_add_detached_signatures(), networkstatus_check_consensus_signature(), networkstatus_compute_consensus(), networkstatus_format_signatures(), networkstatus_get_detached_signatures(), networkstatus_getinfo_by_purpose(), networkstatus_parse_detached_signatures(), networkstatus_parse_vote_from_string(), networkstatus_v2_parse_from_string(), notify_control_networkstatus_changed(), options_init_logs(), options_validate(), parse_addr_policy(), policies_set_router_exitpolicy_to_reject_all(), policy_expand_private(), policy_summarize(), policy_summary_create(), relay_send_command_from_edge(), rend_add_service(), rend_config_services(), rend_encode_v2_descriptors(), rend_encrypt_v2_intro_points_basic(), rend_parse_introduction_points(), rend_parse_service_descriptor(), rend_service_set_connection_addr_port(), rend_service_update_descriptor(), rend_services_introduce(), rep_hist_buffer_stats_add_circ(), rep_hist_buffer_stats_write(), rep_hist_get_router_stability_doc(), retry_listeners(), router_add_exit_policy(), router_add_running_routers_to_smartlist(), router_choose_random_node(), router_load_routers_from_string(), router_load_single_router(), router_parse_entry_from_string(), router_parse_list_from_string(), router_pick_directory_server_impl(), router_pick_trusteddirserver_impl(), router_rebuild_descriptor(), router_rebuild_store(), router_set_networkstatus_v2(), routerlist_add_family(), routerlist_add_network_family(), routerlist_insert(), routerlist_insert_old(), routerlist_remove(), routerlist_replace(), routerset_get_all_routers(), routerset_parse(), routersets_get_disjunction(), smartlist_insert(), smartlist_pqueue_add(), smartlist_split_string(), tokenize_string(), tor_listdir(), tor_tls_client_is_using_v2_ciphers(), trusted_dirs_flush_certs_to_disk(), trusted_dirs_load_certs_from_string(), update_consensus_router_descriptor_downloads(), update_extrainfo_downloads(), upload_service_descriptor(), wildcard_increment_answer(), wrap_string(), and write_bytes_to_file().

void smartlist_add_all ( smartlist_t *  s1,
const smartlist_t *  s2 
)

Append each element from S2 to the end of S1.

References smartlist_t::list, smartlist_t::num_used, smartlist_ensure_capacity(), and tor_assert.

Referenced by compute_consensus_method(), dir_split_resource_into_fingerprint_pairs(), dir_split_resource_into_fingerprints(), dirvote_clear_votes(), dirvote_compute_params(), get_possible_sybil_list(), handle_control_authenticate(), networkstatus_compute_consensus(), parse_addr_policy(), rend_config_services(), and routerset_parse().

void* smartlist_bsearch ( smartlist_t *  sl,
const void *  key,
int(*)(const void *key, const void **member)  compare 
)

Assuming the members of sl are in order, return a pointer to the member that matches key. Ordering and matching are defined by a compare function that returns 0 on a match; less than 0 if key is less than member, and greater than 0 if key is greater then member.

References smartlist_bsearch_idx().

Referenced by geoip_get_country_by_ip(), measured_bw_line_apply(), networkstatus_v2_find_entry(), networkstatus_vote_find_entry(), and router_get_consensus_status_by_id().

int smartlist_bsearch_idx ( const smartlist_t *  sl,
const void *  key,
int(*)(const void *key, const void **member)  compare,
int *  found_out 
)

Assuming the members of sl are in order, return the index of the member that matches key. If no member matches, return the index of the first member greater than key, or smartlist_len(sl) if no member is greater than key. Set found_out to true on a match, to false otherwise. Ordering and matching are defined by a compare function that returns 0 on a match; less than 0 if key is less than member, and greater than 0 if key is greater then member.

References smartlist_t::list, and tor_assert.

Referenced by networkstatus_vote_find_entry_idx(), and smartlist_bsearch().

void smartlist_clear ( smartlist_t *  sl  ) 

Remove all elements from the list.

References smartlist_t::num_used.

Referenced by choose_good_exit_server_general(), choose_random_entry(), clear_bridge_list(), clear_trusted_dir_servers(), client_check_address_changed(), compute_consensus_method(), config_assign_value(), config_register_addressmaps(), connection_or_unlink_all_active_circs(), directory_post_to_hs_dir(), dirserv_add_multiple_descriptors(), dirvote_clear_votes(), dirvote_compute_consensuses(), dns_reset_correctness_checks(), handle_control_mapaddress(), microdescs_parse_from_string(), networkstatus_v2_parse_from_string(), options_init_logs(), options_validate(), parse_addr_policy(), rend_config_services(), rend_encode_v2_descriptors(), rend_parse_client_keys(), rend_parse_introduction_points(), rend_parse_service_authorization(), rend_services_introduce(), rep_hist_buffer_stats_write(), router_load_routers_from_string(), router_parse_directory(), router_reset_warnings(), routerlist_reset_warnings(), routerstatus_parse_entry_from_string(), and upload_service_descriptor().

smartlist_t* smartlist_create ( void   ) 

Allocate and return an empty smartlist.

References smartlist_t::capacity, smartlist_t::list, smartlist_t::num_used, and SMARTLIST_DEFAULT_CAPACITY.

Referenced by accounting_parse_options(), add_nickname_list_to_smartlist(), add_trusted_dir_server(), add_wildcarded_test_address(), append_bytes_to_file(), authority_cert_parse_from_string(), authority_certs_fetch_missing(), authority_type_to_string(), bridge_add_from_config(), bridges_retry_helper(), check_nickname_list(), choose_good_entry_server(), choose_good_exit_server_general(), choose_good_middle_server(), choose_random_entry(), circuit_build_times_parse_state(), circuit_count_pending_on_or_conn(), circuit_get_unhandled_ports(), circuit_list_path_impl(), circuit_n_conn_done(), circuit_set_state(), clear_bridge_list(), clear_trusted_dir_servers(), client_check_address_changed(), client_likes_consensus(), compute_consensus_method(), compute_consensus_versions_list(), config_assign_value(), config_dump(), config_register_addressmaps(), connection_dir_client_reached_eof(), connection_dir_download_cert_failed(), connection_dir_download_networkstatus_failed(), control_event_descriptors_changed(), control_event_networkstatus_changed_helper(), control_event_networkstatus_changed_single(), control_setconf_helper(), decode_hashed_passwords(), detached_get_signatures(), dir_split_resource_into_fingerprint_pairs(), dir_split_resource_into_fingerprints(), directory_get_consensus_url(), directory_get_from_hs_dir(), directory_handle_command_get(), directory_post_to_hs_dir(), dirserv_add_descriptor(), dirserv_add_multiple_descriptors(), dirserv_get_networkstatus_v2(), dirserv_get_routerdescs(), dirvote_add_signatures(), dirvote_add_vote(), dirvote_clear_votes(), dirvote_compute_consensuses(), dirvote_compute_params(), dirvote_fetch_missing_votes(), entry_guards_parse_state(), entry_guards_prepend_from_config(), entry_guards_update_state(), extrainfo_parse_entry_from_string(), find_all_exitpolicy(), format_versions_list(), geoip_get_client_history(), geoip_get_dirreq_history(), geoip_get_request_history(), geoip_load_file(), geoip_note_client_seen(), geoip_parse_entry(), get_cert_list(), get_connection_array(), get_detached_signatures_from_pending_consensuses(), get_possible_sybil_list(), getargs_helper(), getinfo_helper_config(), getinfo_helper_dir(), getinfo_helper_entry_guards(), getinfo_helper_events(), getinfo_helper_networkstatus(), handle_control_authenticate(), handle_control_extendcircuit(), handle_control_getconf(), handle_control_getinfo(), handle_control_mapaddress(), handle_control_postdescriptor(), handle_control_protocolinfo(), handle_control_resolve(), handle_control_setevents(), handle_control_usefeature(), hid_serv_responsible_for_desc_id(), list_getinfo_options(), list_pending_downloads(), list_server_status_v1(), list_torrc_options(), list_v3_auth_ids(), log_credential_status(), log_entry_guards(), make_consensus_method_list(), microdesc_cache_rebuild(), microdescs_parse_from_string(), networkstatus_check_consensus_signature(), networkstatus_compute_consensus(), networkstatus_format_signatures(), networkstatus_get_detached_signatures(), networkstatus_get_v2_list(), networkstatus_getinfo_by_purpose(), networkstatus_parse_detached_signatures(), networkstatus_parse_vote_from_string(), networkstatus_v2_parse_from_string(), notify_control_networkstatus_changed(), options_act_reversible(), options_init_logs(), options_validate(), or_connection_new(), parse_addr_policy(), parse_bridge_line(), parse_dir_server_line(), parse_http_response(), parse_log_severity_config(), parse_port_config(), policies_set_router_exitpolicy_to_reject_all(), policy_expand_private(), policy_summarize(), policy_summary_create(), predicted_ports_init(), relay_send_command_from_edge(), rend_add_service(), rend_cache_store_v2_desc_as_client(), rend_config_services(), rend_encrypt_v2_intro_points_basic(), rend_parse_client_keys(), rend_parse_introduction_points(), rend_parse_service_authorization(), rend_parse_service_descriptor(), rend_parse_v2_service_descriptor(), rend_service_set_connection_addr_port(), rend_service_update_descriptor(), rend_services_introduce(), rep_hist_buffer_stats_add_circ(), rep_hist_buffer_stats_write(), rep_hist_get_router_stability_doc(), rep_hist_load_mtbf_data(), rep_hist_update_state(), retry_listeners(), router_add_exit_policy(), router_choose_random_node(), router_get_consensus_status_by_nickname(), router_get_routerlist(), router_get_trusted_dir_servers(), router_load_extrainfo_from_string(), router_load_routers_from_string(), router_load_single_router(), router_nickname_is_in_list(), router_parse_directory(), router_parse_entry_from_string(), router_parse_runningrouters(), router_pick_directory_server_impl(), router_pick_trusteddirserver_impl(), router_rebuild_descriptor(), router_rebuild_store(), router_reload_v2_networkstatus(), router_set_networkstatus_v2(), routerlist_reset_warnings(), routers_update_status_from_consensus_networkstatus(), routerset_get_all_routers(), routerset_new(), routerset_parse(), set_expiry(), tor_init(), tor_listdir(), tor_tls_client_is_using_v2_ciphers(), tor_version_is_obsolete(), trusted_dirs_flush_certs_to_disk(), update_consensus_router_descriptor_downloads(), update_extrainfo_downloads(), update_router_descriptor_cache_downloads_v2(), upload_service_descriptor(), wildcard_increment_answer(), and write_bytes_to_file().

void smartlist_del ( smartlist_t *  sl,
int  idx 
)

Remove the idxth element of sl; if idx is not the last element, swap the last element of sl into the idxth space. Return the old value of the idxth element.

References smartlist_t::list, smartlist_t::num_used, and tor_assert.

Referenced by circuit_remove_handled_ports(), connection_remove(), exit_policy_remove_redundancies(), networkstatus_v2_list_clean(), rend_client_get_random_intro(), rend_client_remove_intro_point(), rend_services_introduce(), rep_hist_get_predicted_ports(), routerlist_remove(), and routerlist_remove_old().

void smartlist_del_keeporder ( smartlist_t *  sl,
int  idx 
)

Remove the idxth element of sl; if idx is not the last element, moving all subsequent elements back one space. Return the old value of the idxth element.

References smartlist_t::list, smartlist_t::num_used, and tor_assert.

Referenced by dir_split_resource_into_fingerprints(), exit_policy_remove_redundancies(), parse_bridge_line(), parse_dir_server_line(), remove_dead_entry_guards(), remove_obsolete_entry_guards(), and smartlist_uniq().

int smartlist_digest_isin ( const smartlist_t *  sl,
const char *  element 
)

Return true iff sl has some element E such that !memcmp(E,element,DIGEST_LEN)

References DIGEST_LEN, smartlist_t::list, and smartlist_t::num_used.

Referenced by authority_certs_fetch_missing(), directory_post_to_hs_dir(), and entry_guards_prepend_from_config().

static INLINE void smartlist_ensure_capacity ( smartlist_t *  sl,
int  size 
) [static]

Make sure that sl can hold at least size entries.

References smartlist_t::capacity, smartlist_t::list, and tor_assert.

Referenced by smartlist_add(), smartlist_add_all(), and smartlist_insert().

void smartlist_free ( smartlist_t *  sl  ) 

Deallocate a smartlist. Does not release storage associated with the list's elements.

References smartlist_t::list, and tor_free.

Referenced by _connection_free(), accounting_parse_options(), add_nickname_list_to_smartlist(), addr_policy_list_free(), append_bytes_to_file(), authority_cert_parse_from_string(), authority_type_to_string(), check_nickname_list(), choose_good_exit_server_general(), choose_good_middle_server(), choose_random_entry(), circuit_all_predicted_ports_handled(), circuit_build_times_parse_state(), circuit_count_pending_on_or_conn(), circuit_free_all(), circuit_list_path_impl(), circuit_n_conn_done(), clear_geoip_db(), client_likes_consensus(), compute_consensus_method(), compute_consensus_versions_list(), config_dump(), config_register_addressmaps(), connection_dir_client_reached_eof(), connection_dir_download_cert_failed(), connection_dir_download_networkstatus_failed(), connection_dirserv_add_microdescs_to_outbuf(), connection_dirserv_add_networkstatus_bytes_to_outbuf(), connection_dirserv_add_servers_to_outbuf(), connection_free_all(), control_event_descriptors_changed(), control_event_networkstatus_changed_helper(), control_event_networkstatus_changed_single(), control_setconf_helper(), decode_hashed_passwords(), dir_split_resource_into_fingerprint_pairs(), dir_split_resource_into_fingerprints(), directory_get_consensus_url(), directory_get_from_hs_dir(), directory_handle_command_get(), directory_post_to_hs_dir(), dirserv_add_descriptor(), dirserv_add_multiple_descriptors(), dirserv_get_networkstatus_v2(), dirserv_get_routerdescs(), dirvote_compute_consensuses(), dirvote_compute_params(), dirvote_create_microdescriptor(), dirvote_free_all(), dns_free_all(), entry_guards_free_all(), entry_guards_parse_state(), extrainfo_parse_entry_from_string(), format_versions_list(), geoip_get_client_history(), geoip_get_dirreq_history(), geoip_get_request_history(), geoip_load_file(), get_detached_signatures_from_pending_consensuses(), getargs_helper(), getinfo_helper_config(), getinfo_helper_dir(), getinfo_helper_entry_guards(), getinfo_helper_events(), getinfo_helper_networkstatus(), handle_control_attachstream(), handle_control_authenticate(), handle_control_closecircuit(), handle_control_closestream(), handle_control_extendcircuit(), handle_control_getconf(), handle_control_getinfo(), handle_control_mapaddress(), handle_control_postdescriptor(), handle_control_protocolinfo(), handle_control_redirectstream(), handle_control_resolve(), handle_control_setcircuitpurpose(), handle_control_setevents(), handle_control_usefeature(), hid_serv_responsible_for_desc_id(), list_getinfo_options(), list_server_status_v1(), list_torrc_options(), list_v3_auth_ids(), log_credential_status(), log_entry_guards(), make_consensus_method_list(), microdesc_cache_rebuild(), microdesc_cache_reload(), microdesc_free(), microdescs_add_to_cache(), microdescs_parse_from_string(), networkstatus_check_consensus_signature(), networkstatus_compute_consensus(), networkstatus_format_signatures(), networkstatus_free_all(), networkstatus_get_detached_signatures(), networkstatus_parse_vote_from_string(), networkstatus_v2_free(), networkstatus_v2_parse_from_string(), networkstatus_vote_free(), notify_control_networkstatus_changed(), ns_detached_signatures_free(), option_clear(), options_act_reversible(), options_init_logs(), options_validate(), parse_addr_policy(), parse_bridge_line(), parse_dir_server_line(), parse_http_response(), parse_log_severity_config(), parse_port_config(), policy_summarize(), predicted_ports_free(), relay_send_command_from_edge(), rend_config_services(), rend_encrypt_v2_intro_points_basic(), rend_parse_client_keys(), rend_parse_introduction_points(), rend_parse_service_authorization(), rend_parse_v2_service_descriptor(), rend_service_descriptor_free(), rend_service_free(), rend_service_free_all(), rep_hist_buffer_stats_write(), rep_hist_get_router_stability_doc(), rep_hist_load_mtbf_data(), rep_hist_update_state(), router_free_all(), router_get_consensus_status_by_nickname(), router_load_extrainfo_from_string(), router_load_routers_from_string(), router_load_single_router(), router_nickname_is_in_list(), router_parse_directory(), router_parse_entry_from_string(), router_parse_runningrouters(), router_pick_directory_server_impl(), router_pick_trusteddirserver_impl(), router_rebuild_descriptor(), router_reload_v2_networkstatus(), routerinfo_free(), routerlist_free(), routerlist_free_all(), routerset_free(), routerset_parse(), tor_free_all(), tor_tls_client_is_using_v2_ciphers(), tor_version_is_obsolete(), update_extrainfo_downloads(), upload_service_descriptor(), and write_bytes_to_file().

void* smartlist_get_most_frequent ( const smartlist_t *  sl,
int(*)(const void **a, const void **b)  compare 
)

Given a smartlist sl sorted with the function compare, return the most frequent member in the list. Break ties in favor of later elements. If the list is empty, return NULL.

References smartlist_t::list, and smartlist_t::num_used.

Referenced by smartlist_get_most_frequent_digest256(), and smartlist_get_most_frequent_string().

char* smartlist_get_most_frequent_digest256 ( smartlist_t *  sl  ) 

Return the most frequent member of the sorted list of DIGEST256_LEN digests in sl

References _compare_digests256(), and smartlist_get_most_frequent().

char* smartlist_get_most_frequent_string ( smartlist_t *  sl  ) 

Return the most frequent string in the sorted list sl

References _compare_string_ptrs(), and smartlist_get_most_frequent().

static INLINE void smartlist_heapify ( smartlist_t *  sl,
int(*)(const void *a, const void *b)  compare,
int  idx_field_offset,
int  idx 
) [static]

Helper. sl may have at most one violation of the heap property: the item at idx may be greater than one or both of its children. Restore the heap property.

References smartlist_t::list, and smartlist_t::num_used.

Referenced by smartlist_pqueue_pop(), and smartlist_pqueue_remove().

void smartlist_insert ( smartlist_t *  sl,
int  idx,
void *  val 
)

Insert the value val as the new idxth element of sl, moving all items previously at idx or later forward one space.

References smartlist_t::list, smartlist_t::num_used, smartlist_add(), smartlist_ensure_capacity(), and tor_assert.

Referenced by add_an_entry_guard(), and policy_summary_split().

void smartlist_intersect ( smartlist_t *  sl1,
const smartlist_t *  sl2 
)

Remove every element E of sl1 such that !smartlist_isin(sl2,E). Does not preserve the order of sl1.

References smartlist_t::list, smartlist_t::num_used, and smartlist_isin().

int smartlist_isin ( const smartlist_t *  sl,
const void *  element 
)

Return true iff some element E of sl has E==element.

References smartlist_t::list, and smartlist_t::num_used.

Referenced by add_connection_to_closeable_list(), assert_circuit_ok(), choose_random_entry(), connection_in_array(), connection_is_on_closeable_list(), connection_start_reading_from_linked_conn(), connection_stop_reading_from_linked_conn(), smartlist_intersect(), and smartlist_overlap().

char* smartlist_join_strings ( smartlist_t *  sl,
const char *  join,
int  terminate,
size_t *  len_out 
)

Allocate and return a new string containing the concatenation of the elements of sl, in order, separated by join. If terminate is true, also terminate the string with join. If len_out is not NULL, set len_out to the length of the returned string. Requires that every element of sl is NUL-terminated string.

References smartlist_join_strings2().

Referenced by authority_type_to_string(), circuit_list_path_impl(), compute_consensus_versions_list(), config_dump(), control_event_descriptors_changed(), control_event_networkstatus_changed_helper(), control_setconf_helper(), directory_get_consensus_url(), directory_handle_command_get(), dirvote_compute_params(), dirvote_create_microdescriptor(), format_networkstatus_vote(), format_versions_list(), geoip_get_client_history(), geoip_get_request_history(), get_assigned_option(), getinfo_helper_config(), getinfo_helper_dir(), getinfo_helper_entry_guards(), getinfo_helper_events(), getinfo_helper_networkstatus(), handle_control_getconf(), handle_control_mapaddress(), handle_control_protocolinfo(), list_getinfo_options(), list_server_status_v1(), list_v3_auth_ids(), log_credential_status(), log_entry_guards(), make_consensus_method_list(), networkstatus_compute_consensus(), networkstatus_format_signatures(), networkstatus_get_detached_signatures(), options_validate(), parse_bridge_line(), parse_dir_server_line(), policy_summarize(), relay_send_command_from_edge(), rep_hist_buffer_stats_write(), rep_hist_get_router_stability_doc(), router_dump_router_to_string(), router_load_routers_from_string(), router_set_networkstatus_v2(), routerset_to_string(), and tor_tls_client_is_using_v2_ciphers().

char* smartlist_join_strings2 ( smartlist_t *  sl,
const char *  join,
size_t  join_len,
int  terminate,
size_t *  len_out 
)

As smartlist_join_strings, but instead of separating/terminated with a NUL-terminated string join, uses the join_len-byte sequence at join. (Useful for generating a sequence of NUL-terminated strings.)

References smartlist_t::list, smartlist_t::num_used, and tor_assert.

Referenced by smartlist_join_strings().

int smartlist_overlap ( const smartlist_t *  sl1,
const smartlist_t *  sl2 
)

Return true iff some element E of sl2 has smartlist_isin(sl1,E).

References smartlist_t::list, smartlist_t::num_used, and smartlist_isin().

void* smartlist_pop_last ( smartlist_t *  sl  ) 

If sl is nonempty, remove and return the final element. Otherwise, return NULL.

References smartlist_t::list, smartlist_t::num_used, and tor_assert.

Referenced by connection_dirserv_add_microdescs_to_outbuf(), connection_dirserv_add_networkstatus_bytes_to_outbuf(), and connection_dirserv_add_servers_to_outbuf().

void smartlist_pqueue_add ( smartlist_t *  sl,
int(*)(const void *a, const void *b)  compare,
int  idx_field_offset,
void *  item 
)

Insert item into the heap stored in sl, where order is determined by compare and the offset of the item in the heap is stored in an int-typed field at position idx_field_offset within item.

References smartlist_t::list, smartlist_t::num_used, and smartlist_add().

Referenced by add_cell_ewma_to_conn(), and set_expiry().

void smartlist_pqueue_assert_ok ( smartlist_t *  sl,
int(*)(const void *a, const void *b)  compare,
int  idx_field_offset 
)

Assert that the heap property is correctly maintained by the heap stored in sl, where order is determined by compare.

References smartlist_t::list, smartlist_t::num_used, and tor_assert.

void* smartlist_pqueue_pop ( smartlist_t *  sl,
int(*)(const void *a, const void *b)  compare,
int  idx_field_offset 
)

Remove and return the top-priority item from the heap stored in sl, where order is determined by compare and the item's position is stored at position idx_field_offset within the item. sl must not be empty.

References smartlist_t::list, smartlist_t::num_used, smartlist_heapify(), and tor_assert.

Referenced by pop_first_cell_ewma_from_conn(), and purge_expired_resolves().

void smartlist_pqueue_remove ( smartlist_t *  sl,
int(*)(const void *a, const void *b)  compare,
int  idx_field_offset,
void *  item 
)

Remove the item item from the heap stored in sl, where order is determined by compare and the item's position is stored at position idx_field_offset within the item. sl must not be empty.

References smartlist_t::list, smartlist_t::num_used, smartlist_heapify(), and tor_assert.

Referenced by remove_cell_ewma_from_conn().

void smartlist_remove ( smartlist_t *  sl,
const void *  element 
)

Remove all elements E from sl such that E==element. Preserve the order of any elements before E, but elements after E can be rearranged.

References smartlist_t::list, and smartlist_t::num_used.

Referenced by _circuit_mark_for_close(), circuit_set_state(), connection_stop_reading_from_linked_conn(), connection_unlink(), networkstatus_add_detached_signatures(), and smartlist_subtract().

void smartlist_reverse ( smartlist_t *  sl  ) 

Reverse the order of the items in sl.

References smartlist_t::list, smartlist_t::num_used, and tor_assert.

void smartlist_sort ( smartlist_t *  sl,
int(*)(const void **a, const void **b)  compare 
)

Sort the members of sl into an order defined by the ordering function compare, which returns less then 0 if a precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.

References smartlist_t::list, and smartlist_t::num_used.

Referenced by compute_consensus_method(), compute_routerstatus_consensus(), dir_split_resource_into_fingerprint_pairs(), directory_get_consensus_url(), dirserv_read_measured_bandwidths(), geoip_get_client_history(), geoip_get_request_history(), geoip_load_file(), get_possible_sybil_list(), networkstatus_compute_consensus(), networkstatus_v2_parse_from_string(), rep_hist_buffer_stats_write(), router_rebuild_store(), routerlist_remove_old_routers(), routers_sort_by_identity(), smartlist_sort_digests(), smartlist_sort_digests256(), smartlist_sort_strings(), and sort_version_list().

void smartlist_sort_digests ( smartlist_t *  sl  ) 

Sort the list of DIGEST_LEN-byte digests into ascending order.

References _compare_digests(), and smartlist_sort().

Referenced by dir_split_resource_into_fingerprints(), dirserv_get_networkstatus_v2_fingerprints(), launch_router_descriptor_downloads(), and rend_encrypt_v2_intro_points_basic().

void smartlist_sort_digests256 ( smartlist_t *  sl  ) 

Sort the list of DIGEST256_LEN-byte digests into ascending order.

References _compare_digests256(), and smartlist_sort().

Referenced by dir_split_resource_into_fingerprints().

void smartlist_sort_strings ( smartlist_t *  sl  ) 

Sort a smartlist sl containing strings into lexically ascending order.

References _compare_string_ptrs(), and smartlist_sort().

Referenced by dir_split_resource_into_fingerprints(), dirvote_compute_params(), list_getinfo_options(), networkstatus_compute_consensus(), rend_config_services(), and router_rebuild_descriptor().

int smartlist_split_string ( smartlist_t *  sl,
const char *  str,
const char *  sep,
int  flags,
int  max 
)

Split a string str along all occurrences of sep, adding the split strings, in order, to sl.

If flags&SPLIT_SKIP_SPACE is true, remove initial and trailing space from each entry. If flags&SPLIT_IGNORE_BLANK is true, remove any entries of length 0. If flags&SPLIT_STRIP_SPACE is true, strip spaces from each split string.

If max>0, divide the string into no more than max pieces. If sep is NULL, split on any sequence of horizontal space.

References smartlist_add(), tor_assert, and tor_strstrip().

Referenced by accounting_parse_options(), add_nickname_list_to_smartlist(), check_nickname_list(), circuit_build_times_parse_state(), config_assign_value(), config_register_addressmaps(), dir_split_resource_into_fingerprint_pairs(), dir_split_resource_into_fingerprints(), entry_guards_parse_state(), format_versions_list(), getargs_helper(), handle_control_extendcircuit(), handle_control_getconf(), handle_control_getinfo(), handle_control_mapaddress(), handle_control_postdescriptor(), handle_control_protocolinfo(), handle_control_resolve(), handle_control_setevents(), handle_control_usefeature(), networkstatus_compute_consensus(), options_init_logs(), parse_addr_policy(), parse_bridge_line(), parse_dir_server_line(), parse_http_response(), parse_log_severity_config(), parse_port_config(), rend_config_services(), rend_parse_service_authorization(), rend_parse_v2_service_descriptor(), rep_hist_load_mtbf_data(), rep_hist_update_state(), router_nickname_is_in_list(), router_rebuild_descriptor(), routerset_parse(), and tor_version_is_obsolete().

int smartlist_string_isin ( const smartlist_t *  sl,
const char *  element 
)

Return true iff sl has some element E such that !strcmp(E,element)

References smartlist_t::list, and smartlist_t::num_used.

Referenced by add_nickname_list_to_smartlist(), answer_is_wildcarded(), dirvote_compute_consensuses(), router_load_routers_from_string(), router_rebuild_descriptor(), router_set_networkstatus_v2(), smartlist_string_num_isin(), and wildcard_increment_answer().

int smartlist_string_isin_case ( const smartlist_t *  sl,
const char *  element 
)

Return true iff sl has some element E such that !strcasecmp(E,element)

References smartlist_t::list, and smartlist_t::num_used.

Referenced by add_wildcarded_test_address(), and is_test_address().

int smartlist_string_num_isin ( const smartlist_t *  sl,
int  num 
)

Return true iff sl has some element E such that E is equal to the decimal encoding of num.

References smartlist_string_isin(), and tor_snprintf().

Referenced by circuit_all_predicted_ports_handled(), circuit_get_open_circ_or_launch(), circuit_stream_is_being_handled(), consider_plaintext_ports(), and rend_service_requires_uptime().

int smartlist_string_pos ( const smartlist_t *  sl,
const char *  element 
)

If element is equal to an element of sl, return that element's index. Otherwise, return -1.

References smartlist_t::list, and smartlist_t::num_used.

Referenced by networkstatus_compute_consensus(), and routerstatus_parse_entry_from_string().

void smartlist_string_remove ( smartlist_t *  sl,
const char *  element 
)

If there are any strings in sl equal to element, remove and free them. Does not preserve order.

References smartlist_t::list, smartlist_t::num_used, tor_assert, and tor_free.

Referenced by router_load_extrainfo_from_string(), router_load_routers_from_string(), router_rebuild_descriptor(), and router_set_networkstatus_v2().

void smartlist_subtract ( smartlist_t *  sl1,
const smartlist_t *  sl2 
)

Remove every element E of sl1 such that smartlist_isin(sl2,E). Does not preserve the order of sl1.

References smartlist_t::list, smartlist_t::num_used, and smartlist_remove().

void smartlist_uniq ( smartlist_t *  sl,
int(*)(const void **a, const void **b)  compare,
void(*)(void *a)  free_fn 
)

Given a sorted smartlist sl and the comparison function used to sort it, remove all duplicate members. If free_fn is provided, calls free_fn on each duplicate. Otherwise, just removes them. Preserves order.

References smartlist_t::list, smartlist_t::num_used, and smartlist_del_keeporder().

Referenced by compute_consensus_method(), dir_split_resource_into_fingerprint_pairs(), networkstatus_v2_parse_from_string(), smartlist_uniq_digests(), smartlist_uniq_digests256(), smartlist_uniq_strings(), and sort_version_list().

void smartlist_uniq_digests ( smartlist_t *  sl  ) 

Remove duplicate digests from a sorted list, and free them with tor_free().

References _compare_digests(), _tor_free(), and smartlist_uniq().

Referenced by dir_split_resource_into_fingerprints().

void smartlist_uniq_digests256 ( smartlist_t *  sl  ) 

Remove duplicate 256-bit digests from a sorted list, and free them with tor_free().

References _compare_digests256(), _tor_free(), and smartlist_uniq().

Referenced by dir_split_resource_into_fingerprints().

void smartlist_uniq_strings ( smartlist_t *  sl  ) 

Remove duplicate strings from a sorted list, and free them with tor_free().

References _compare_string_ptrs(), _tor_free(), and smartlist_uniq().

Referenced by dir_split_resource_into_fingerprints(), networkstatus_compute_consensus(), rend_config_services(), and router_rebuild_descriptor().

void strmap_assert_ok ( const strmap_t *  map  ) 

Fail with an assertion error if anything has gone wrong with the internal representation of map.

References tor_assert.

static INLINE int strmap_entries_eq ( const strmap_entry_t *  a,
const strmap_entry_t *  b 
) [static]

Helper: compare strmap_entry_t objects by key value.

static INLINE unsigned int strmap_entry_hash ( const strmap_entry_t *  a  )  [static]

Helper: return a hash value for a strmap_entry_t.

void strmap_free ( strmap_t *  map,
void(*)(void *)  free_val 
)

Remove all entries from map, and deallocate storage for those entries. If free_val is provided, it is invoked on every value in map.

References tor_assert, and tor_free.

Referenced by addressmap_free_all(), clear_geoip_db(), dirserv_free_all(), dirserv_free_fingerprint_list(), dns_reset_correctness_checks(), networkstatus_free_all(), ns_detached_signatures_free(), rend_cache_free_all(), rend_parse_service_authorization(), rend_service_authorization_free_all(), rend_service_load_keys(), routerset_free(), and routerstatus_list_update_named_server_map().

void* strmap_get ( const strmap_t *  map,
const char *  key 
)

Return the current value associated with key, or NULL if no value is set.

References tor_assert.

Referenced by addressmap_get_virtual_address(), addressmap_register(), addressmap_register_virtual_address(), addressmap_rewrite(), addressmap_rewrite_reverse(), addressmap_virtaddress_remove(), client_dns_clear_failures(), client_dns_incr_failures(), detached_get_digests(), detached_get_signatures(), dirserv_get_consensus(), dirvote_add_signatures_to_pending_consensus(), lookup_cached_dir_by_fp(), networkstatus_add_detached_signatures(), rend_client_lookup_service_authorization(), rend_parse_client_keys(), rend_parse_service_authorization(), rend_service_load_keys(), strmap_get_lc(), and wildcard_increment_answer().

void* strmap_get_lc ( const strmap_t *  map,
const char *  key 
)

Same as strmap_get, but first converts key to lowercase.

References strmap_get(), tor_free, and tor_strlower().

Referenced by add_fingerprint_to_dir(), addressmap_have_mapping(), dirserv_get_name_status(), geoip_add_entry(), geoip_get_country(), lookup_last_hid_serv_request(), networkstatus_compute_consensus(), networkstatus_get_router_digest_by_nickname(), networkstatus_nickname_is_unnamed(), rend_cache_lookup_entry(), rend_cache_store(), rend_cache_store_v2_desc_as_client(), router_get_consensus_status_by_nickname(), and routerset_contains().

int strmap_isempty ( const strmap_t *  map  ) 

Return true iff map has no entries.

int strmap_iter_done ( strmap_iter_t *  iter  ) 

Return true iff iter has advanced past the last entry of map.

Referenced by addressmap_get_mappings(), directory_clean_last_hid_serv_requests(), and rend_cache_clean().

void strmap_iter_get ( strmap_iter_t *  iter,
const char **  keyp,
void **  valp 
)

Set *keyp and *valp to the current entry pointed to by iter.

References tor_assert.

Referenced by addressmap_get_mappings(), directory_clean_last_hid_serv_requests(), and rend_cache_clean().

strmap_iter_t* strmap_iter_init ( strmap_t *  map  ) 

return an iterator pointer to the front of a map.

Iterator example:

 // uppercase values in "map", removing empty values.

 strmap_iter_t *iter;
 const char *key;
 void *val;
 char *cp;

 for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) {
    strmap_iter_get(iter, &key, &val);
    cp = (char*)val;
    if (!*cp) {
       iter = strmap_iter_next_rmv(map,iter);
       free(val);
    } else {
       for (;*cp;cp++) *cp = TOR_TOUPPER(*cp);
       iter = strmap_iter_next(map,iter);
    }
 }

References tor_assert.

Referenced by addressmap_get_mappings(), directory_clean_last_hid_serv_requests(), and rend_cache_clean().

strmap_iter_t* strmap_iter_next ( strmap_t *  map,
strmap_iter_t *  iter 
)

Advance the iterator iter for map a single step to the next entry, and return its new value.

References tor_assert.

Referenced by addressmap_get_mappings(), directory_clean_last_hid_serv_requests(), and rend_cache_clean().

strmap_iter_t* strmap_iter_next_rmv ( strmap_t *  map,
strmap_iter_t *  iter 
)

Advance the iterator iter a single step to the next entry, removing the current entry, and return its new value.

References tor_assert, and tor_free.

Referenced by addressmap_get_mappings(), directory_clean_last_hid_serv_requests(), and rend_cache_clean().

void* strmap_remove ( strmap_t *  map,
const char *  key 
)

Remove the value currently associated with key from the map. Return the value if one was set, or NULL if there was no entry for key.

Note: you must free any storage associated with the returned value.

References tor_assert, and tor_free.

Referenced by addressmap_register(), addressmap_virtaddress_remove(), and strmap_remove_lc().

void* strmap_remove_lc ( strmap_t *  map,
const char *  key 
)

Same as strmap_remove, but first converts key to lowercase

References strmap_remove(), tor_free, and tor_strlower().

void* strmap_set ( strmap_t *  map,
const char *  key,
void *  val 
)

Set the current value for key to val. Returns the previous value for key if one was set, or NULL if one was not.

This function makes a copy of key if necessary, but not of val.

References tor_assert.

Referenced by addressmap_register(), addressmap_register_virtual_address(), client_dns_incr_failures(), detached_get_digests(), detached_get_signatures(), dirserv_set_cached_consensus_networkstatus(), lookup_last_hid_serv_request(), rend_parse_client_keys(), rend_parse_service_authorization(), strmap_set_lc(), and wildcard_increment_answer().

void* strmap_set_lc ( strmap_t *  map,
const char *  key,
void *  val 
)

Same as strmap_set, but first converts key to lowercase.

References strmap_set(), tor_free, and tor_strlower().

Referenced by add_fingerprint_to_dir(), geoip_add_entry(), networkstatus_compute_consensus(), rend_cache_store(), rend_cache_store_v2_desc_as_client(), routerset_parse(), and routerstatus_list_update_named_server_map().

int strmap_size ( const strmap_t *  map  ) 

Return the number of items in map.

Referenced by dirserv_get_status_impl(), evdns_wildcard_check_callback(), rend_cache_size(), rend_parse_client_keys(), and rend_service_load_keys().

Generated on Tue May 25 00:30:41 2010 for tor by  doxygen 1.5.6