tor  0.4.0.1-alpha
Macros | Functions
smartlist.h File Reference
#include <stdarg.h>
#include "lib/smartlist_core/smartlist_core.h"
#include "lib/smartlist_core/smartlist_foreach.h"
#include "lib/smartlist_core/smartlist_split.h"

Go to the source code of this file.

Macros

#define smartlist_get_most_frequent(sl, compare)   smartlist_get_most_frequent_((sl), (compare), NULL)
 
#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, cmpexpr, unmatched_var2)
 
#define SMARTLIST_FOREACH_JOIN_END(var1, var2)
 

Functions

void smartlist_add_asprintf (struct smartlist_t *sl, const char *pattern,...) CHECK_PRINTF(2
 
void void smartlist_add_vasprintf (struct smartlist_t *sl, const char *pattern, va_list args) CHECK_PRINTF(2
 
void void void smartlist_reverse (smartlist_t *sl)
 
void smartlist_string_remove (smartlist_t *sl, const char *element)
 
int smartlist_contains_string (const smartlist_t *sl, const char *element)
 
int smartlist_pos (const smartlist_t *sl, const void *element)
 
int smartlist_string_pos (const smartlist_t *, const char *elt)
 
int smartlist_contains_string_case (const smartlist_t *sl, const char *element)
 
int smartlist_contains_int_as_string (const smartlist_t *sl, int num)
 
int smartlist_strings_eq (const smartlist_t *sl1, const smartlist_t *sl2)
 
int smartlist_contains_digest (const smartlist_t *sl, const char *element)
 
int smartlist_ints_eq (const smartlist_t *sl1, const smartlist_t *sl2)
 
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)
 
int smartlist_ptrs_eq (const smartlist_t *s1, const smartlist_t *s2)
 
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), int *count_out)
 
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_sort_digests256 (smartlist_t *sl)
 
void smartlist_sort_pointers (smartlist_t *sl)
 
const char * smartlist_get_most_frequent_string (smartlist_t *sl)
 
const char * smartlist_get_most_frequent_string_ (smartlist_t *sl, int *count_out)
 
const uint8_t * smartlist_get_most_frequent_digest256 (smartlist_t *sl)
 
void smartlist_uniq_strings (smartlist_t *sl)
 
void smartlist_uniq_digests (smartlist_t *sl)
 
void smartlist_uniq_digests256 (smartlist_t *sl)
 
void * smartlist_bsearch (const 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)
 
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)
 
char * smartlist_join_strings (smartlist_t *sl, const char *join, int terminate, size_t *len_out) ATTR_MALLOC
 
char * smartlist_join_strings2 (smartlist_t *sl, const char *join, size_t join_len, int terminate, size_t *len_out) ATTR_MALLOC
 

Detailed Description

Header for smartlist.c.

Definition in file smartlist.h.

Macro Definition Documentation

◆ SMARTLIST_FOREACH_JOIN

#define SMARTLIST_FOREACH_JOIN (   sl1,
  type1,
  var1,
  sl2,
  type2,
  var2,
  cmpexpr,
  unmatched_var2 
)
Value:
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: ; \

Definition at line 138 of file smartlist.h.

◆ SMARTLIST_FOREACH_JOIN_END

#define SMARTLIST_FOREACH_JOIN_END (   var1,
  var2 
)
Value:
} \
STMT_END

Definition at line 164 of file smartlist.h.

Function Documentation

◆ smartlist_bsearch()

void* smartlist_bsearch ( const 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.

Definition at line 411 of file smartlist.c.

References smartlist_bsearch_idx().

Referenced by connection_half_edge_find_stream_id(), geoip_get_country_by_ipv4(), measured_bw_line_apply(), networkstatus_vote_find_mutable_entry(), and router_get_mutable_consensus_status_by_id().

◆ smartlist_bsearch_idx()

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.

Definition at line 428 of file smartlist.c.

References tor_assert().

Referenced by connection_half_edge_is_valid_end(), networkstatus_vote_find_entry_idx(), and smartlist_bsearch().

◆ smartlist_contains_digest()

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

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

Definition at line 223 of file smartlist.c.

References DIGEST_LEN, smartlist_t::list, and tor_memeq().

◆ smartlist_contains_int_as_string()

int smartlist_contains_int_as_string ( 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.

Definition at line 147 of file smartlist.c.

References smartlist_contains_string(), and tor_snprintf().

Referenced by circuit_stream_is_being_handled(), and consider_plaintext_ports().

◆ smartlist_contains_string()

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

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

Definition at line 93 of file smartlist.c.

References smartlist_t::list.

Referenced by add_transport_to_proxy(), answer_is_wildcarded(), microdesc_relay_is_outdated_dirserver(), and smartlist_contains_int_as_string().

◆ smartlist_contains_string_case()

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

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

Definition at line 133 of file smartlist.c.

References smartlist_t::list.

Referenced by add_wildcarded_test_address(), and is_test_address().

◆ smartlist_get_most_frequent_()

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

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. If count_out is non-null, set it to the count of the most frequent member.

Definition at line 348 of file smartlist.c.

References smartlist_t::list.

Referenced by smartlist_get_most_frequent_string_().

◆ smartlist_get_most_frequent_digest256()

const uint8_t* smartlist_get_most_frequent_digest256 ( smartlist_t sl)

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

Definition at line 854 of file smartlist.c.

◆ smartlist_get_most_frequent_string()

const char* smartlist_get_most_frequent_string ( smartlist_t sl)

Return the most frequent string in the sorted list sl

Definition at line 556 of file smartlist.c.

◆ smartlist_get_most_frequent_string_()

const char* smartlist_get_most_frequent_string_ ( smartlist_t sl,
int *  count_out 
)

Return the most frequent string in the sorted list sl. If count_out is provided, set count_out to the number of times that string appears.

Definition at line 566 of file smartlist.c.

References compare_string_ptrs_(), and smartlist_get_most_frequent_().

◆ smartlist_intersect()

void smartlist_intersect ( smartlist_t sl1,
const smartlist_t sl2 
)

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

Definition at line 249 of file smartlist.c.

References smartlist_t::list, and smartlist_contains().

◆ smartlist_ints_eq()

int smartlist_ints_eq ( const smartlist_t sl1,
const smartlist_t sl2 
)

Return true iff the two lists contain the same int pointer values in the same order, or if they are both NULL.

Definition at line 176 of file smartlist.c.

◆ smartlist_join_strings()

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.

Definition at line 279 of file smartlist.c.

References smartlist_join_strings2().

Referenced by format_cell_stats(), kvline_encode(), list_getinfo_options(), make_consensus_method_list(), and write_short_policy().

◆ smartlist_join_strings2()

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.)

Definition at line 291 of file smartlist.c.

References smartlist_t::list, and tor_assert().

Referenced by smartlist_join_strings().

◆ smartlist_overlap()

int smartlist_overlap ( const smartlist_t sl1,
const smartlist_t sl2 
)

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

Definition at line 236 of file smartlist.c.

References smartlist_t::list, and smartlist_contains().

◆ smartlist_pos()

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

If element is the same pointer as an element of sl, return that element's index. Otherwise, return -1.

Definition at line 119 of file smartlist.c.

References smartlist_t::list.

◆ smartlist_pqueue_add()

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.

Definition at line 726 of file smartlist.c.

References smartlist_add().

Referenced by add_cell_ewma(), MOCK_IMPL(), scheduler_channel_wants_writes(), and set_expiry().

◆ smartlist_pqueue_assert_ok()

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.

Definition at line 803 of file smartlist.c.

References smartlist_t::list, and tor_assert().

◆ smartlist_pqueue_pop()

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.

Definition at line 755 of file smartlist.c.

References IDXP, smartlist_t::list, and tor_assert().

Referenced by pop_first_cell_ewma().

◆ smartlist_pqueue_remove()

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.

Definition at line 779 of file smartlist.c.

Referenced by MOCK_IMPL(), and remove_cell_ewma().

◆ smartlist_ptrs_eq()

int smartlist_ptrs_eq ( const smartlist_t s1,
const smartlist_t s2 
)

Return true if there is shallow equality between smartlists - i.e. all indices correspond to exactly same object (pointer values are matching). Otherwise, return false.

Definition at line 198 of file smartlist.c.

◆ smartlist_reverse()

void void void smartlist_reverse ( smartlist_t sl)

Reverse the order of the items in sl.

Definition at line 59 of file smartlist.c.

References smartlist_t::list, and tor_assert().

◆ smartlist_sort()

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.

Definition at line 334 of file smartlist.c.

References smartlist_t::list.

Referenced by compute_routerstatus_consensus(), dirserv_spool_sort(), get_possible_sybil_list(), routers_sort_by_identity(), smartlist_sort_digests(), smartlist_sort_digests256(), smartlist_sort_pointers(), smartlist_sort_strings(), sort_version_list(), and trusted_dirs_remove_old_certs().

◆ smartlist_sort_digests()

void smartlist_sort_digests ( smartlist_t sl)

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

Definition at line 824 of file smartlist.c.

References compare_digests_(), and smartlist_sort().

Referenced by dircollator_collate().

◆ smartlist_sort_digests256()

void smartlist_sort_digests256 ( smartlist_t sl)

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

Definition at line 846 of file smartlist.c.

References compare_digests256_(), and smartlist_sort().

◆ smartlist_sort_pointers()

void smartlist_sort_pointers ( smartlist_t sl)

Sort sl in ascending order of the pointers it contains.

Definition at line 594 of file smartlist.c.

References compare_ptrs_(), and smartlist_sort().

◆ smartlist_sort_strings()

void smartlist_sort_strings ( smartlist_t sl)

Sort a smartlist sl containing strings into lexically ascending order.

Definition at line 549 of file smartlist.c.

References compare_string_ptrs_(), and smartlist_sort().

Referenced by list_getinfo_options().

◆ smartlist_string_pos()

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.

Definition at line 106 of file smartlist.c.

References smartlist_t::list.

◆ smartlist_string_remove()

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.

Definition at line 74 of file smartlist.c.

References smartlist_t::list, tor_assert(), and tor_free.

◆ smartlist_strings_eq()

int smartlist_strings_eq ( const smartlist_t sl1,
const smartlist_t sl2 
)

Return true iff the two lists contain the same strings in the same order, or if they are both NULL.

Definition at line 157 of file smartlist.c.

◆ smartlist_subtract()

void smartlist_subtract ( smartlist_t sl1,
const smartlist_t sl2 
)

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

Definition at line 264 of file smartlist.c.

References smartlist_t::list, and smartlist_remove().

◆ smartlist_uniq_digests()

void smartlist_uniq_digests ( smartlist_t sl)

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

Definition at line 832 of file smartlist.c.

References compare_digests_(), smartlist_uniq(), and tor_free_().

◆ smartlist_uniq_digests256()

void smartlist_uniq_digests256 ( smartlist_t sl)

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

Definition at line 863 of file smartlist.c.

References compare_digests256_(), smartlist_uniq(), and tor_free_().

◆ smartlist_uniq_strings()

void smartlist_uniq_strings ( smartlist_t sl)

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

Definition at line 574 of file smartlist.c.

References compare_string_ptrs_(), smartlist_uniq(), and tor_free_().