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 "torlog.h"
#include "container.h"
#include "crypto_digest.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "ht.h"

Include dependency graph for container.c:

Macros
#define	SMARTLIST_DEFAULT_CAPACITY   16
#define	MAX_CAPACITY   (int)((SIZE_MAX / (sizeof(void*))))
#define	DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)
#define	strmap_entry_free(ent)   FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent))
#define	digestmap_entry_free(ent)   FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent))
#define	digest256map_entry_free(ent)   FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent))
#define	IMPLEMENT_MAP_FNS(maptype, keytype, prefix)
#define	IMPLEMENT_ORDER_FUNC(funcname, elt_t)
#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
	MOCK_IMPL (smartlist_t *, smartlist_new,(void))
	MOCK_IMPL (void, smartlist_free_,(smartlist_t *sl))
void	smartlist_clear (smartlist_t *sl)
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_remove_keeporder (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_contains (const smartlist_t *sl, const void *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_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)
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), 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 (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_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)
void	smartlist_sort_pointers (smartlist_t *sl)
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)
void	smartlist_sort_digests (smartlist_t *sl)
void	smartlist_uniq_digests (smartlist_t *sl)
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)
	DEFINE_MAP_STRUCTS (strmap_t, char *key, strmap_)
	DEFINE_MAP_STRUCTS (digestmap_t, char key[DIGEST_LEN], digestmap_)
	DEFINE_MAP_STRUCTS (digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_)
	HT_PROTOTYPE (HT_GENERATE2(strmap_impl, HT_GENERATE2(strmap_entry_t, HT_GENERATE2(node, HT_GENERATE2(strmap_entry_hash, HT_GENERATE2(strmap_entries_eq)
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)
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.

Macro Definition Documentation

DEFINE_MAP_STRUCTS

#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

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

IMPLEMENT_MAP_FNS

#define IMPLEMENT_MAP_FNS	(		maptype,
			keytype,
			prefix
	)

Macro: implement all the functions for a map that are declared in container.h by the DECLARE_MAP_FNS() macro. You must additionally define a prefix_entry_free_() function to free entries (and their keys), a prefix_assign_tmp_key() function to temporarily set a stack-allocated entry to hold a key, and a prefix_assign_key() function to set a heap-allocated entry to hold a key.

IMPLEMENT_ORDER_FUNC

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

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.

SMARTLIST_DEFAULT_CAPACITY

#define SMARTLIST_DEFAULT_CAPACITY   16

All newly allocated smartlists have this capacity.

UPDATE_IDX

#define UPDATE_IDX

(

i

)

Value:

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

Function Documentation

digestset_free_()

void digestset_free_

(

digestset_t *

set

)

Free all storage held in set.

digestset_new()

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.

Here is the call graph for this function:

HT_PROTOTYPE()

HT_PROTOTYPE	(	HT_GENERATE2(	channel_idmap,
		HT_GENERATE2(	channel_idmap_entry_s,
		HT_GENERATE2(	node,
		HT_GENERATE2(	channel_idmap_hash,
		HT_GENERATE2(	channel_idmap_eq
	)

Indicate whether a given channel state is valid.

MOCK_IMPL() [1/2]

MOCK_IMPL	(	smartlist_t *	,
		smartlist_new	,
		(void)
	)

Allocate and return an empty smartlist.

MOCK_IMPL() [2/2]

MOCK_IMPL	(	void	,
		smartlist_free_	,
		(smartlist_t *sl)
	)

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

smartlist_add()

void smartlist_add	(	smartlist_t *	sl,
		void *	element
	)

Append element to the end of the list.

Here is the caller graph for this function:

smartlist_add_all()

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

Append each element from S2 to the end of S1.

Here is the caller graph for this function:

smartlist_bsearch()

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

smartlist_clear()

void smartlist_clear

(

smartlist_t *

sl

)

Remove all elements from the list.

Here is the caller graph for this function:

smartlist_contains()

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

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

Here is the caller graph for this function:

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)

Here is the call graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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)

Here is the caller graph for this function:

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)

Here is the caller graph for this function:

smartlist_del()

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.

Here is the caller graph for this function:

smartlist_del_keeporder()

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.

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

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

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

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.

Here is the call graph for this function:

smartlist_insert()

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.

Here is the call graph for this function:

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.

Here is the call graph for this function:

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.

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Here is the caller graph for this function:

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

Here is the call graph for this function:

smartlist_pop_last()

void* smartlist_pop_last

(

smartlist_t *

sl

)

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

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.

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

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.

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.

Here is the caller graph for this function:

smartlist_remove()

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.

Here is the caller graph for this function:

smartlist_remove_keeporder()

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

As smartlist_remove, but do not change the order of any elements not removed

smartlist_reverse()

void smartlist_reverse

(

smartlist_t *

sl

)

Reverse the order of the items in sl.

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.

Here is the caller graph for this function:

smartlist_sort_digests()

void smartlist_sort_digests

(

smartlist_t *

sl

)

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

Here is the call graph for this function:

smartlist_sort_digests256()

void smartlist_sort_digests256

(

smartlist_t *

sl

)

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

Here is the call graph for this function:

smartlist_sort_pointers()

void smartlist_sort_pointers

(

smartlist_t *

sl

)

Sort sl in ascending order of the pointers it contains.

Here is the call graph for this function:

smartlist_sort_strings()

void smartlist_sort_strings

(

smartlist_t *

sl

)

Sort a smartlist sl containing strings into lexically ascending order.

Here is the call graph for this function:

smartlist_split_string()

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, appending the (newly allocated) split strings, in order, to sl. Return the number of strings added 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.

Here is the caller graph for this function:

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.

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.

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.

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.

Here is the call graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

smartlist_uniq_digests()

void smartlist_uniq_digests

(

smartlist_t *

sl

)

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

Here is the call graph for this function:

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

Here is the call graph for this function:

smartlist_uniq_strings()

void smartlist_uniq_strings

(

smartlist_t *

sl

)

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

Here is the call graph for this function:

strmap_get_lc()

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

Same as strmap_get, but first converts key to lowercase.

Here is the caller graph for this function:

strmap_remove_lc()

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

Same as strmap_remove, but first converts key to lowercase

Here is the caller graph for this function:

strmap_set_lc()

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

Same as strmap_set, but first converts key to lowercase.

Here is the caller graph for this function: