Higher-level functions for the "smartlist" resizeable array abstraction. More...

#include "lib/container/smartlist.h"
#include "lib/err/torerr.h"
#include "lib/malloc/malloc.h"
#include "lib/defs/digest_sizes.h"
#include "lib/ctime/di_ops.h"
#include "lib/string/compat_ctype.h"
#include "lib/string/compat_string.h"
#include "lib/string/util_string.h"
#include "lib/string/printf.h"
#include "lib/log/util_bug.h"
#include <stdlib.h>
#include <string.h>

Macros

#define	MAX_PARENT_IDX ((INT_MAX - 2) / 2)

#define	IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX)

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

Functions
void	smartlist_add_asprintf (struct smartlist_t sl, const char pattern,...)

void	smartlist_add_vasprintf (struct smartlist_t sl, const char pattern, va_list args)

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_string_pos (const smartlist_t sl, const char element)

int	smartlist_pos (const smartlist_t sl, const void element)

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_ints_eq (const smartlist_t sl1, const smartlist_t sl2)

int	smartlist_ptrs_eq (const smartlist_t s1, const smartlist_t s2)

int	smartlist_contains_digest (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)

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), int *count_out)

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

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)

static int	compare_string_ptrs_ (const void _a, const void _b)

void	smartlist_sort_strings (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)

void	smartlist_uniq_strings (smartlist_t *sl)

static int	compare_ptrs_ (const void _a, const void _b)

void	smartlist_sort_pointers (smartlist_t *sl)

static void	smartlist_heapify (smartlist_t sl, int(compare)(const void a, const void b), ptrdiff_t idx_field_offset, int idx)

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

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

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

void	smartlist_pqueue_assert_ok (smartlist_t sl, int(compare)(const void a, const void b), ptrdiff_t 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)

const uint8_t *	smartlist_get_most_frequent_digest256 (smartlist_t *sl)

void	smartlist_uniq_digests256 (smartlist_t *sl)

Detailed Description

Higher-level functions for the "smartlist" resizeable array abstraction.

The functions declared here use higher-level functionality than those in smartlist_core.c, and handle things like smartlists of different types, sorting, searching, heap-structured smartlists, and other convenience functions.

Definition in file smartlist.c.

Macro Definition Documentation

◆ IDX_MAY_HAVE_CHILDREN

#define IDX_MAY_HAVE_CHILDREN ( i ) ((i) <= MAX_PARENT_IDX)

Definition at line 651 of file smartlist.c.

◆ IDX_OF_ITEM

#define IDX_OF_ITEM ( p ) (*IDXP(p))

Definition at line 672 of file smartlist.c.

◆ IDXP

#define IDXP ( p ) ((int*)STRUCT_VAR_P(p, idx_field_offset))

Helper macros for heaps: Given a local variable idx_field_offset set to the offset of an integer index within the heap element structure, IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to where p's index is stored. Given additionally a local smartlist sl, UPDATE_IDX(i) sets the index of the element at i to the correct value (that is, to i).

Definition at line 665 of file smartlist.c.

◆ LEFT_CHILD

#define LEFT_CHILD ( i ) ( 2*(i) + 1 )

Definition at line 652 of file smartlist.c.

◆ MAX_PARENT_IDX

#define MAX_PARENT_IDX ((INT_MAX - 2) / 2)

Functions to manipulate heap indices to find a node's parent and children.

For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x] = 2*x + 1. But this is C, so we have to adjust a little.

Definition at line 648 of file smartlist.c.

◆ PARENT

#define PARENT ( i ) ( ((i)-1) / 2 )

Definition at line 654 of file smartlist.c.

◆ RIGHT_CHILD

#define RIGHT_CHILD ( i ) ( 2*(i) + 2 )

Definition at line 653 of file smartlist.c.

◆ UPDATE_IDX

#define UPDATE_IDX ( i )

Value:

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

Definition at line 667 of file smartlist.c.

Function Documentation

◆ compare_digests256_()

static int compare_digests256_	(	const void **	_a,
		const void **	_b
	)

static

Helper: compare two DIGEST256_LEN digests.

Definition at line 839 of file smartlist.c.

Referenced by smartlist_sort_digests256(), and smartlist_uniq_digests256().

◆ compare_digests_()

static int compare_digests_	(	const void **	_a,
		const void **	_b
	)

static

Helper: compare two DIGEST_LEN digests.

Definition at line 817 of file smartlist.c.

Referenced by smartlist_sort_digests(), and smartlist_uniq_digests().

◆ compare_ptrs_()

static int compare_ptrs_	(	const void **	_a,
		const void **	_b
	)

static

Helper: compare two pointers.

Definition at line 581 of file smartlist.c.

Referenced by smartlist_sort_pointers().

◆ compare_string_ptrs_()

static int compare_string_ptrs_	(	const void **	_a,
		const void **	_b
	)

static

Helper: compare two const char **s.

Definition at line 541 of file smartlist.c.

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

◆ smartlist_add_asprintf()

void smartlist_add_asprintf	(	struct smartlist_t *	sl,
		const char *	pattern,
			...
	)

Append the string produced by tor_asprintf(pattern, ...) to sl.

Definition at line 36 of file smartlist.c.

Referenced by circuit_list_path_impl(), control_event_conf_changed(), control_ports_write_to_file(), encode_client_auth_cred_for_control_port(), encode_intro_point(), entry_connection_describe_status_for_controller(), format_cell_stats(), get_bindaddr_for_server_proxy(), get_outer_encrypted_layer_plaintext(), get_transport_options_for_server_proxy(), get_transport_proxy_ports(), handle_control_mapaddress(), list_getinfo_options(), make_consensus_method_list(), process_set_environment(), proto_entry_encode_into(), and write_short_policy().

◆ smartlist_add_vasprintf()

void smartlist_add_vasprintf	(	struct smartlist_t *	sl,
		const char *	pattern,
		va_list	args
	)

va_list-based backend of smartlist_add_asprintf.

Definition at line 46 of file smartlist.c.

Referenced by smartlist_add_asprintf().

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

Referenced by connection_half_edge_find_stream_id(), geoip_get_country_by_ipv4(), geoip_get_country_by_ipv6(), 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.

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.

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

Referenced by circuit_stream_is_being_handled(), consider_plaintext_ports(), and hs_service_requires_uptime_circ().

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

Referenced by add_transport_to_proxy(), answer_is_wildcarded(), get_my_declared_family(), metrics_store_entry_has_label(), metrics_store_find_entry_with_label(), 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.

Referenced by add_wildcarded_test_address(), addr_is_in_cc_list(), 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.

Referenced by smartlist_get_most_frequent_srv(), and 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.

◆ smartlist_heapify()

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

inlinestatic

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.

Definition at line 679 of file smartlist.c.

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

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

Referenced by control_event_conf_changed(), encode_client_auth_cred_for_control_port(), entry_connection_describe_status_for_controller(), extrainfo_dump_to_string(), format_cell_stats(), get_authmethods(), 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.

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.

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

◆ smartlist_pqueue_add()

void smartlist_pqueue_add	(	smartlist_t *	sl,
		int()(const void a, const void *b)	compare,
		ptrdiff_t	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.

Referenced by add_cell_ewma(), scheduler_channel_has_waiting_cells(), 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,
		ptrdiff_t	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.

◆ smartlist_pqueue_pop()

void * smartlist_pqueue_pop	(	smartlist_t *	sl,
		int()(const void a, const void *b)	compare,
		ptrdiff_t	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.

Referenced by pop_first_cell_ewma().

◆ smartlist_pqueue_remove()

void smartlist_pqueue_remove	(	smartlist_t *	sl,
		int()(const void a, const void *b)	compare,
		ptrdiff_t	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 remove_cell_ewma(), and scheduler_channel_doesnt_want_writes().

◆ 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 smartlist_reverse ( smartlist_t * sl )

Reverse the order of the items in sl.

Definition at line 59 of file smartlist.c.

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

Referenced by compute_routerstatus_consensus(), config_mgr_freeze(), consdiffmgr_ensure_space_for_files(), dirserv_spool_sort(), routers_sort_by_identity(), smartlist_sort_digests(), smartlist_sort_digests256(), smartlist_sort_pointers(), smartlist_sort_strings(), sort_and_find_most_recent(), 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.

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.

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

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

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.

Referenced by remove_flag().

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

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

◆ smartlist_uniq()

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.

Definition at line 390 of file smartlist.c.

Referenced by smartlist_uniq_digests(), smartlist_uniq_digests256(), smartlist_uniq_strings(), and sort_version_list().

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

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

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

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ IDX_MAY_HAVE_CHILDREN

◆ IDX_OF_ITEM

◆ IDXP

◆ LEFT_CHILD

◆ MAX_PARENT_IDX

◆ PARENT

◆ RIGHT_CHILD

◆ UPDATE_IDX

Function Documentation

◆ compare_digests256_()

◆ compare_digests_()

◆ compare_ptrs_()

◆ compare_string_ptrs_()

◆ smartlist_add_asprintf()

◆ smartlist_add_vasprintf()

◆ smartlist_bsearch()

◆ smartlist_bsearch_idx()

◆ smartlist_contains_digest()

◆ smartlist_contains_int_as_string()

◆ smartlist_contains_string()

◆ smartlist_contains_string_case()

◆ smartlist_get_most_frequent_()

◆ smartlist_get_most_frequent_digest256()

◆ smartlist_get_most_frequent_string()

◆ smartlist_get_most_frequent_string_()

◆ smartlist_heapify()

◆ smartlist_intersect()

◆ smartlist_ints_eq()

◆ smartlist_join_strings()

◆ smartlist_join_strings2()

◆ smartlist_overlap()

◆ smartlist_pos()

◆ smartlist_pqueue_add()

◆ smartlist_pqueue_assert_ok()

◆ smartlist_pqueue_pop()

◆ smartlist_pqueue_remove()

◆ smartlist_ptrs_eq()

◆ smartlist_reverse()

◆ smartlist_sort()

◆ smartlist_sort_digests()

◆ smartlist_sort_digests256()

◆ smartlist_sort_pointers()

◆ smartlist_sort_strings()

◆ smartlist_string_pos()

◆ smartlist_string_remove()

◆ smartlist_strings_eq()

◆ smartlist_subtract()

◆ smartlist_uniq()

◆ smartlist_uniq_digests()

◆ smartlist_uniq_digests256()

◆ smartlist_uniq_strings()