Tor 0.4.9.1-alpha-dev
Functions
smartlist.c File Reference

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>

Go to the source code of this file.

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)
#define IDXP(p)
Definition: smartlist.c:665

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

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

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