Back to index

tor  0.2.3.19-rc
Defines | Functions
container.c File Reference

Implements a smartlist (a resizable array) along with helper functions to use smartlists. More...

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

Go to the source code of this file.

Defines

#define SMARTLIST_DEFAULT_CAPACITY   16
 All newly allocated smartlists have this capacity.
#define MAX_CAPACITY   (int)((SIZE_MAX / (sizeof(void*))))
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)
 Helper: Declare an entry type and a map type to implement a mapping using ht.h.
#define OPTIMIZED_DIGESTMAP_SET
#define IMPLEMENT_ORDER_FUNC(funcname, elt_t)
 Declare a function called funcname that acts as a find_nth_FOO function for an array of type elt_t*.
#define LEFT_CHILD(i)   ( 2*(i) + 1 )
 Functions to manipulate heap indices to find a node's parent and children.
#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

smartlist_tsmartlist_new (void)
 Allocate and return an empty smartlist.
void smartlist_free (smartlist_t *sl)
 Deallocate a smartlist.
void smartlist_clear (smartlist_t *sl)
 Remove all elements from the list.
static INLINE void smartlist_ensure_capacity (smartlist_t *sl, int size)
 Make sure that sl can hold at least size entries.
void smartlist_add (smartlist_t *sl, void *element)
 Append element to the end of the list.
void smartlist_add_all (smartlist_t *s1, const smartlist_t *s2)
 Append each element from S2 to the end of S1.
void smartlist_remove (smartlist_t *sl, const void *element)
 Remove all elements E from sl such that E==element.
void * smartlist_pop_last (smartlist_t *sl)
 If sl is nonempty, remove and return the final element.
void smartlist_reverse (smartlist_t *sl)
 Reverse the order of the items in sl.
void smartlist_string_remove (smartlist_t *sl, const char *element)
 If there are any strings in sl equal to element, remove and free them.
int smartlist_isin (const smartlist_t *sl, const void *element)
 Return true iff some element E of sl has E==element.
int smartlist_string_isin (const smartlist_t *sl, const char *element)
 Return true iff sl has some element E such that !strcmp(E,element)
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.
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)
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.
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.
int smartlist_digest_isin (const smartlist_t *sl, const char *element)
 Return true iff sl has some element E such that tor_memeq(E,element,DIGEST_LEN)
int smartlist_overlap (const smartlist_t *sl1, const smartlist_t *sl2)
 Return true iff some element E of sl2 has smartlist_isin(sl1,E).
void smartlist_intersect (smartlist_t *sl1, const smartlist_t *sl2)
 Remove every element E of sl1 such that !smartlist_isin(sl2,E).
void smartlist_subtract (smartlist_t *sl1, const smartlist_t *sl2)
 Remove every element E of sl1 such that smartlist_isin(sl2,E).
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.
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.
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.
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.
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.
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.
void smartlist_sort (smartlist_t *sl, int(*compare)(const void **a, const void **b))
 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.
void * smartlist_get_most_frequent (const smartlist_t *sl, int(*compare)(const void **a, const void **b))
 Given a smartlist sl sorted with the function compare, return the most frequent member in the list.
void smartlist_uniq (smartlist_t *sl, int(*compare)(const void **a, const void **b), void(*free_fn)(void *a))
 Given a sorted smartlist sl and the comparison function used to sort it, remove all duplicate members.
void * smartlist_bsearch (smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member))
 Assuming the members of sl are in order, return a pointer to the member that matches key.
int smartlist_bsearch_idx (const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member), int *found_out)
 Assuming the members of sl are in order, return the index of the member that matches key.
static int _compare_string_ptrs (const void **_a, const void **_b)
 Helper: compare two const char **s.
void smartlist_sort_strings (smartlist_t *sl)
 Sort a smartlist sl containing strings into lexically ascending order.
char * smartlist_get_most_frequent_string (smartlist_t *sl)
 Return the most frequent string in the sorted list sl
void smartlist_uniq_strings (smartlist_t *sl)
 Remove duplicate strings from a sorted list, and free them with tor_free().
static INLINE void smartlist_heapify (smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset, int idx)
 Helper.
void smartlist_pqueue_add (smartlist_t *sl, int(*compare)(const void *a, const void *b), 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.
void * smartlist_pqueue_pop (smartlist_t *sl, int(*compare)(const void *a, const void *b), 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.
void smartlist_pqueue_remove (smartlist_t *sl, int(*compare)(const void *a, const void *b), 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.
void smartlist_pqueue_assert_ok (smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset)
 Assert that the heap property is correctly maintained by the heap stored in sl, where order is determined by compare.
static int _compare_digests (const void **_a, const void **_b)
 Helper: compare two DIGEST_LEN digests.
void smartlist_sort_digests (smartlist_t *sl)
 Sort the list of DIGEST_LEN-byte digests into ascending order.
void smartlist_uniq_digests (smartlist_t *sl)
 Remove duplicate digests from a sorted list, and free them with tor_free().
static int _compare_digests256 (const void **_a, const void **_b)
 Helper: compare two DIGEST256_LEN digests.
void smartlist_sort_digests256 (smartlist_t *sl)
 Sort the list of DIGEST256_LEN-byte digests into ascending order.
char * smartlist_get_most_frequent_digest256 (smartlist_t *sl)
 Return the most frequent member of the sorted list of DIGEST256_LEN digests in sl
void smartlist_uniq_digests256 (smartlist_t *sl)
 Remove duplicate 256-bit digests from a sorted list, and free them with tor_free().
 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)
 Helper: compare strmap_entry_t objects by key value.
static INLINE unsigned int strmap_entry_hash (const strmap_entry_t *a)
 Helper: return a hash value for a strmap_entry_t.
static INLINE int digestmap_entries_eq (const digestmap_entry_t *a, const digestmap_entry_t *b)
 Helper: compare digestmap_entry_t objects by key value.
static INLINE unsigned int digestmap_entry_hash (const digestmap_entry_t *a)
 Helper: return a hash value for a digest_map_t.
 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.
digestmap_t * digestmap_new (void)
 Constructor to create a new empty map from digests to void*'s.
void * strmap_set (strmap_t *map, const char *key, void *val)
 Set the current value for key to val.
void * digestmap_set (digestmap_t *map, const char *key, void *val)
 Like strmap_set() above but for digestmaps.
void * strmap_get (const strmap_t *map, const char *key)
 Return the current value associated with key, or NULL if no value is set.
void * digestmap_get (const digestmap_t *map, const char *key)
 Like strmap_get() above but for digestmaps.
void * strmap_remove (strmap_t *map, const char *key)
 Remove the value currently associated with key from the map.
void * digestmap_remove (digestmap_t *map, const char *key)
 Like strmap_remove() above but for digestmaps.
void * strmap_set_lc (strmap_t *map, const char *key, void *val)
 Same as strmap_set, but first converts key to lowercase.
void * strmap_get_lc (const strmap_t *map, const char *key)
 Same as strmap_get, but first converts key to lowercase.
void * strmap_remove_lc (strmap_t *map, const char *key)
 Same as strmap_remove, but first converts key to lowercase.
strmap_iter_t * strmap_iter_init (strmap_t *map)
 return an iterator pointer to the front of a map.
digestmap_iter_t * digestmap_iter_init (digestmap_t *map)
 Start iterating through map.
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.
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.
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.
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.
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.
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.
int strmap_iter_done (strmap_iter_t *iter)
 Return true iff iter has advanced past the last entry of map.
int digestmap_iter_done (digestmap_iter_t *iter)
 Return true iff iter has advanced past the last entry of map.
void strmap_free (strmap_t *map, void(*free_val)(void *))
 Remove all entries from map, and deallocate storage for those entries.
void digestmap_free (digestmap_t *map, void(*free_val)(void *))
 Remove all entries from map, and deallocate storage for those entries.
void strmap_assert_ok (const strmap_t *map)
 Fail with an assertion error if anything has gone wrong with the internal representation of map.
void digestmap_assert_ok (const digestmap_t *map)
 Fail with an assertion error if anything has gone wrong with the internal representation of map.
int strmap_isempty (const strmap_t *map)
 Return true iff map has no entries.
int digestmap_isempty (const digestmap_t *map)
 Return true iff map has no entries.
int strmap_size (const strmap_t *map)
 Return the number of items in map.
int digestmap_size (const digestmap_t *map)
 Return the number of items in map.
digestset_tdigestset_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.
void digestset_free (digestset_t *set)
 Free all storage held in 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.

Definition in file container.c.


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

Definition at line 886 of file container.c.

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

Definition at line 698 of file container.c.

#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 691 of file container.c.

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

Definition at line 1401 of file container.c.

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

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 678 of file container.c.

#define MAX_CAPACITY   (int)((SIZE_MAX / (sizeof(void*))))

Definition at line 996 of file container.c.

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

Definition at line 680 of file container.c.

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

Definition at line 679 of file container.c.

#define SMARTLIST_DEFAULT_CAPACITY   16

All newly allocated smartlists have this capacity.

Definition at line 27 of file container.c.

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

Definition at line 693 of file container.c.


Function Documentation

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

Helper: compare two DIGEST_LEN digests.

Definition at line 831 of file container.c.

{
  return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Helper: compare two DIGEST256_LEN digests.

Definition at line 853 of file container.c.

{
  return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Helper: compare two const char **s.

Definition at line 605 of file container.c.

{
  return strcmp((const char*)*_a, (const char*)*_b);
}

Here is the caller graph for this function:

DEFINE_MAP_STRUCTS ( strmap_t  ,
char *  key,
strmap_   
)
DEFINE_MAP_STRUCTS ( digestmap_t  ,
char  key[DIGEST_LEN],
digestmap_   
)
void digestmap_assert_ok ( const digestmap_t *  map)

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

Definition at line 1362 of file container.c.

{
  tor_assert(!digestmap_impl_HT_REP_IS_BAD_(&map->head));
}
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.

Definition at line 915 of file container.c.

{
  return tor_memeq(a->key, b->key, DIGEST_LEN);
}

Here is the call graph for this function:

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

Helper: return a hash value for a digest_map_t.

Definition at line 922 of file container.c.

{
#if SIZEOF_INT != 8
  const uint32_t *p = (const uint32_t*)a->key;
  return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
#else
  const uint64_t *p = (const uint64_t*)a->key;
  return p[0] ^ p[1];
#endif
}

Here is the caller graph for this function:

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.

Definition at line 1335 of file container.c.

{
  digestmap_entry_t **ent, **next, *this;
  if (!map)
    return;
  for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) {
    this = *ent;
    next = HT_NEXT_RMV(digestmap_impl, &map->head, ent);
    if (free_val)
      free_val(this->val);
    tor_free(this);
  }
  tor_assert(HT_EMPTY(&map->head));
  HT_CLEAR(digestmap_impl, &map->head);
  tor_free(map);
}

Here is the caller graph for this function:

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

Like strmap_get() above but for digestmaps.

Definition at line 1071 of file container.c.

{
  digestmap_entry_t *resolve;
  digestmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  memcpy(&search.key, key, DIGEST_LEN);
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

Here is the caller graph for this function:

int digestmap_isempty ( const digestmap_t *  map)

Return true iff map has no entries.

Definition at line 1376 of file container.c.

{
  return HT_EMPTY(&map->head);
}

Here is the caller graph for this function:

int digestmap_iter_done ( digestmap_iter_t *  iter)

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

Definition at line 1301 of file container.c.

{
  return iter == NULL;
}

Here is the caller graph for this function:

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.

Definition at line 1280 of file container.c.

{
  tor_assert(iter);
  tor_assert(*iter);
  tor_assert(keyp);
  tor_assert(valp);
  *keyp = (*iter)->key;
  *valp = (*iter)->val;
}

Here is the caller graph for this function:

digestmap_iter_t* digestmap_iter_init ( digestmap_t *  map)

Start iterating through map.

See strmap_iter_init() for example.

Definition at line 1205 of file container.c.

{
  tor_assert(map);
  return HT_START(digestmap_impl, &map->head);
}

Here is the caller graph for this function:

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.

Definition at line 1224 of file container.c.

{
  tor_assert(map);
  tor_assert(iter);
  return HT_NEXT(digestmap_impl, &map->head, iter);
}

Here is the caller graph for this function:

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.

Definition at line 1252 of file container.c.

{
  digestmap_entry_t *rmv;
  tor_assert(map);
  tor_assert(iter);
  tor_assert(*iter);
  rmv = *iter;
  iter = HT_NEXT_RMV(digestmap_impl, &map->head, iter);
  tor_free(rmv);
  return iter;
}

Here is the caller graph for this function:

digestmap_t* digestmap_new ( void  )

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

Definition at line 957 of file container.c.

{
  digestmap_t *result;
  result = tor_malloc(sizeof(digestmap_t));
  HT_INIT(digestmap_impl, &result->head);
  return result;
}

Here is the caller graph for this function:

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

Like strmap_remove() above but for digestmaps.

Definition at line 1114 of file container.c.

{
  digestmap_entry_t *resolve;
  digestmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  memcpy(&search.key, key, DIGEST_LEN);
  resolve = HT_REMOVE(digestmap_impl, &map->head, &search);
  if (resolve) {
    oldval = resolve->val;
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

Here is the caller graph for this function:

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

Like strmap_set() above but for digestmaps.

Definition at line 1000 of file container.c.

{
#ifndef OPTIMIZED_DIGESTMAP_SET
  digestmap_entry_t *resolve;
#endif
  digestmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  memcpy(&search.key, key, DIGEST_LEN);
#ifndef OPTIMIZED_DIGESTMAP_SET
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
  if (resolve) {
    oldval = resolve->val;
    resolve->val = val;
    return oldval;
  } else {
    resolve = tor_malloc_zero(sizeof(digestmap_entry_t));
    memcpy(resolve->key, key, DIGEST_LEN);
    resolve->val = val;
    HT_INSERT(digestmap_impl, &map->head, resolve);
    return NULL;
  }
#else
  /* We spend up to 5% of our time in this function, so the code below is
   * meant to optimize the check/alloc/set cycle by avoiding the two trips to
   * the hash table that we do in the unoptimized code above.  (Each of
   * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.)
   */
  HT_FIND_OR_INSERT_(digestmap_impl, node, digestmap_entry_hash, &(map->head),
         digestmap_entry_t, &search, ptr,
         {
            /* we found an entry. */
            oldval = (*ptr)->val;
            (*ptr)->val = val;
            return oldval;
         },
         {
           /* We didn't find the entry. */
           digestmap_entry_t *newent =
             tor_malloc_zero(sizeof(digestmap_entry_t));
           memcpy(newent->key, key, DIGEST_LEN);
           newent->val = val;
           HT_FOI_INSERT_(node, &(map->head), &search, newent, ptr);
           return NULL;
         });
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

int digestmap_size ( const digestmap_t *  map)

Return the number of items in map.

Definition at line 1390 of file container.c.

{
  return HT_SIZE(&map->head);
}

Here is the caller graph for this function:

void digestset_free ( digestset_t set)

Free all storage held in set.

Definition at line 1453 of file container.c.

{
  if (!set)
    return;
  bitarray_free(set->ba);
  tor_free(set);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 1432 of file container.c.

{
  /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
   * is the number of hash functions per entry, m is the bits in the array,
   * and n is the number of elements inserted.  For us, k==4, n<=max_elements,
   * and m==n_bits= approximately max_elements*32.  This gives
   *   P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
   *
   * It would be more optimal in space vs false positives to get this false
   * positive rate by going for k==13, and m==18.5n, but we also want to
   * conserve CPU, and k==13 is pretty big.
   */
  int n_bits = 1u << (tor_log2(max_elements)+5);
  digestset_t *r = tor_malloc(sizeof(digestset_t));
  r->mask = n_bits - 1;
  r->ba = bitarray_init_zero(n_bits);
  return r;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 933 of file container.c.

{
  strmap_t *result;
  result = tor_malloc(sizeof(strmap_t));
  HT_INIT(strmap_impl, &result->head);
  return result;
}
void smartlist_add ( smartlist_t sl,
void *  element 
)

Append element to the end of the list.

Definition at line 86 of file container.c.

{
  smartlist_ensure_capacity(sl, sl->num_used+1);
  sl->list[sl->num_used++] = element;
}

Here is the call graph for this function:

void smartlist_add_all ( smartlist_t s1,
const smartlist_t s2 
)

Append each element from S2 to the end of S1.

Definition at line 94 of file container.c.

{
  int new_size = s1->num_used + s2->num_used;
  tor_assert(new_size >= s1->num_used); /* check for overflow. */
  smartlist_ensure_capacity(s1, new_size);
  memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
  s1->num_used = new_size;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 553 of file container.c.

{
  int found, idx;
  idx = smartlist_bsearch_idx(sl, key, compare, &found);
  return found ? smartlist_get(sl, idx) : NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 570 of file container.c.

{
  int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid;

  while (lo <= hi) {
    mid = (lo + hi) / 2;
    cmp = compare(key, (const void**) &(sl->list[mid]));
    if (cmp>0) { /* key > sl[mid] */
      lo = mid+1;
    } else if (cmp<0) { /* key < sl[mid] */
      hi = mid-1;
    } else { /* key == sl[mid] */
      *found_out = 1;
      return mid;
    }
  }
  /* lo > hi. */
  {
    tor_assert(lo >= 0);
    if (lo < smartlist_len(sl)) {
      cmp = compare(key, (const void**) &(sl->list[lo]));
      tor_assert(cmp < 0);
    } else if (smartlist_len(sl)) {
      cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1]));
      tor_assert(cmp > 0);
    }
  }
  *found_out = 0;
  return lo;
}

Here is the caller graph for this function:

void smartlist_clear ( smartlist_t sl)

Remove all elements from the list.

Definition at line 56 of file container.c.

{
  sl->num_used = 0;
}
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.

Definition at line 301 of file container.c.

{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx < sl->num_used);
  sl->list[idx] = sl->list[--sl->num_used];
}

Here is the caller graph for this function:

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.

Definition at line 314 of file container.c.

{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx < sl->num_used);
  --sl->num_used;
  if (idx < sl->num_used)
    memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
}

Here is the caller graph for this function:

int smartlist_digest_isin ( 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 250 of file container.c.

{
  int i;
  if (!sl) return 0;
  for (i=0; i < sl->num_used; i++)
    if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN))
      return 1;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Make sure that sl can hold at least size entries.

Definition at line 63 of file container.c.

{
#if SIZEOF_SIZE_T > SIZEOF_INT
#define MAX_CAPACITY (INT_MAX)
#else
#define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*))))
#endif
  if (size > sl->capacity) {
    int higher = sl->capacity;
    if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {
      tor_assert(size <= MAX_CAPACITY);
      higher = MAX_CAPACITY;
    } else {
      while (size > higher)
        higher *= 2;
    }
    sl->capacity = higher;
    sl->list = tor_realloc(sl->list, sizeof(void*)*((size_t)sl->capacity));
  }
}

Here is the caller graph for this function:

void smartlist_free ( smartlist_t sl)

Deallocate a smartlist.

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

Definition at line 45 of file container.c.

{
  if (!sl)
    return;
  tor_free(sl->list);
  tor_free(sl);
}
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.

Definition at line 496 of file container.c.

{
  const void *most_frequent = NULL;
  int most_frequent_count = 0;

  const void *cur = NULL;
  int i, count=0;

  if (!sl->num_used)
    return NULL;
  for (i = 0; i < sl->num_used; ++i) {
    const void *item = sl->list[i];
    if (cur && 0 == compare(&cur, &item)) {
      ++count;
    } else {
      if (cur && count >= most_frequent_count) {
        most_frequent = cur;
        most_frequent_count = count;
      }
      cur = item;
      count = 1;
    }
  }
  if (cur && count >= most_frequent_count) {
    most_frequent = cur;
    most_frequent_count = count;
  }
  return (void*)most_frequent;
}

Here is the caller graph for this function:

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

Definition at line 868 of file container.c.

Here is the call graph for this function:

Return the most frequent string in the sorted list sl

Definition at line 620 of file container.c.

Here is the call graph for this function:

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.

Definition at line 705 of file container.c.

{
  while (1) {
    int left_idx = LEFT_CHILD(idx);
    int best_idx;

    if (left_idx >= sl->num_used)
      return;
    if (compare(sl->list[idx],sl->list[left_idx]) < 0)
      best_idx = idx;
    else
      best_idx = left_idx;
    if (left_idx+1 < sl->num_used &&
        compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
      best_idx = left_idx + 1;

    if (best_idx == idx) {
      return;
    } else {
      void *tmp = sl->list[idx];
      sl->list[idx] = sl->list[best_idx];
      sl->list[best_idx] = tmp;
      UPDATE_IDX(idx);
      UPDATE_IDX(best_idx);

      idx = best_idx;
    }
  }
}

Here is the caller graph for this function:

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.

Definition at line 329 of file container.c.

{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx <= sl->num_used);
  if (idx == sl->num_used) {
    smartlist_add(sl, val);
  } else {
    smartlist_ensure_capacity(sl, sl->num_used+1);
    /* Move other elements away */
    if (idx < sl->num_used)
      memmove(sl->list + idx + 1, sl->list + idx,
              sizeof(void*)*(sl->num_used-idx));
    sl->num_used++;
    sl->list[idx] = val;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 276 of file container.c.

{
  int i;
  for (i=0; i < sl1->num_used; i++)
    if (!smartlist_isin(sl2, sl1->list[i])) {
      sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 166 of file container.c.

{
  int i;
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element)
      return 1;
  return 0;
}

Here is the caller graph for this function:

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 428 of file container.c.

{
  return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
}

Here is the call graph for this function:

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 440 of file container.c.

{
  int i;
  size_t n = 0;
  char *r = NULL, *dst, *src;

  tor_assert(sl);
  tor_assert(join);

  if (terminate)
    n = join_len;

  for (i = 0; i < sl->num_used; ++i) {
    n += strlen(sl->list[i]);
    if (i+1 < sl->num_used) /* avoid double-counting the last one */
      n += join_len;
  }
  dst = r = tor_malloc(n+1);
  for (i = 0; i < sl->num_used; ) {
    for (src = sl->list[i]; *src; )
      *dst++ = *src++;
    if (++i < sl->num_used) {
      memcpy(dst, join, join_len);
      dst += join_len;
    }
  }
  if (terminate) {
    memcpy(dst, join, join_len);
    dst += join_len;
  }
  *dst = '\0';

  if (len_out)
    *len_out = dst-r;
  return r;
}

Here is the caller graph for this function:

Allocate and return an empty smartlist.

Definition at line 32 of file container.c.

{
  smartlist_t *sl = tor_malloc(sizeof(smartlist_t));
  sl->num_used = 0;
  sl->capacity = SMARTLIST_DEFAULT_CAPACITY;
  sl->list = tor_malloc(sizeof(void *) * sl->capacity);
  return sl;
}
int smartlist_overlap ( const smartlist_t sl1,
const smartlist_t sl2 
)

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

Definition at line 263 of file container.c.

{
  int i;
  for (i=0; i < sl2->num_used; i++)
    if (smartlist_isin(sl1, sl2->list[i]))
      return 1;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Otherwise, return NULL.

Definition at line 123 of file container.c.

{
  tor_assert(sl);
  if (sl->num_used)
    return sl->list[--sl->num_used];
  else
    return NULL;
}

Here is the caller graph for this function:

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 744 of file container.c.

{
  int idx;
  smartlist_add(sl,item);
  UPDATE_IDX(sl->num_used-1);

  for (idx = sl->num_used - 1; idx; ) {
    int parent = PARENT(idx);
    if (compare(sl->list[idx], sl->list[parent]) < 0) {
      void *tmp = sl->list[parent];
      sl->list[parent] = sl->list[idx];
      sl->list[idx] = tmp;
      UPDATE_IDX(parent);
      UPDATE_IDX(idx);
      idx = parent;
    } else {
      return;
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 817 of file container.c.

{
  int i;
  for (i = sl->num_used - 1; i >= 0; --i) {
    if (i>0)
      tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
    tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
  }
}
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 773 of file container.c.

{
  void *top;
  tor_assert(sl->num_used);

  top = sl->list[0];
  *IDXP(top)=-1;
  if (--sl->num_used) {
    sl->list[0] = sl->list[sl->num_used];
    UPDATE_IDX(0);
    smartlist_heapify(sl, compare, idx_field_offset, 0);
  }
  return top;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 795 of file container.c.

{
  int idx = IDX_OF_ITEM(item);
  tor_assert(idx >= 0);
  tor_assert(sl->list[idx] == item);
  --sl->num_used;
  *IDXP(item) = -1;
  if (idx == sl->num_used) {
    return;
  } else {
    sl->list[idx] = sl->list[sl->num_used];
    UPDATE_IDX(idx);
    smartlist_heapify(sl, compare, idx_field_offset, idx);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 108 of file container.c.

{
  int i;
  if (element == NULL)
    return;
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element) {
      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
    }
}

Here is the caller graph for this function:

Reverse the order of the items in sl.

Definition at line 134 of file container.c.

{
  int i, j;
  void *tmp;
  tor_assert(sl);
  for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
    tmp = sl->list[i];
    sl->list[i] = sl->list[j];
    sl->list[j] = tmp;
  }
}

Here is the caller graph for this function:

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 483 of file container.c.

{
  if (!sl->num_used)
    return;
  qsort(sl->list, sl->num_used, sizeof(void*),
        (int (*)(const void *,const void*))compare);
}

Here is the caller graph for this function:

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

Definition at line 838 of file container.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 860 of file container.c.

Here is the call graph for this function:

Here is the caller graph for this function:

Sort a smartlist sl containing strings into lexically ascending order.

Definition at line 613 of file container.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 363 of file container.c.

{
  const char *cp, *end, *next;
  int n = 0;

  tor_assert(sl);
  tor_assert(str);

  cp = str;
  while (1) {
    if (flags&SPLIT_SKIP_SPACE) {
      while (TOR_ISSPACE(*cp)) ++cp;
    }

    if (max>0 && n == max-1) {
      end = strchr(cp,'\0');
    } else if (sep) {
      end = strstr(cp,sep);
      if (!end)
        end = strchr(cp,'\0');
    } else {
      for (end = cp; *end && *end != '\t' && *end != ' '; ++end)
        ;
    }

    tor_assert(end);

    if (!*end) {
      next = NULL;
    } else if (sep) {
      next = end+strlen(sep);
    } else {
      next = end+1;
      while (*next == '\t' || *next == ' ')
        ++next;
    }

    if (flags&SPLIT_SKIP_SPACE) {
      while (end > cp && TOR_ISSPACE(*(end-1)))
        --end;
    }
    if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) {
      char *string = tor_strndup(cp, end-cp);
      if (flags&SPLIT_STRIP_SPACE)
        tor_strstrip(string, " ");
      smartlist_add(sl, string);
      ++n;
    }
    if (!next)
      break;
    cp = next;
  }

  return n;
}

Here is the call graph for this function:

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

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

Definition at line 179 of file container.c.

{
  int i;
  if (!sl) return 0;
  for (i=0; i < sl->num_used; i++)
    if (strcmp((const char*)sl->list[i],element)==0)
      return 1;
  return 0;
}

Here is the caller graph for this function:

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)

Definition at line 206 of file container.c.

{
  int i;
  if (!sl) return 0;
  for (i=0; i < sl->num_used; i++)
    if (strcasecmp((const char*)sl->list[i],element)==0)
      return 1;
  return 0;
}

Here is the caller graph for this function:

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.

Definition at line 220 of file container.c.

{
  char buf[32]; /* long enough for 64-bit int, and then some. */
  tor_snprintf(buf,sizeof(buf),"%d", num);
  return smartlist_string_isin(sl, buf);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 192 of file container.c.

{
  int i;
  if (!sl) return -1;
  for (i=0; i < sl->num_used; i++)
    if (strcmp((const char*)sl->list[i],element)==0)
      return i;
  return -1;
}

Here is the caller graph for this function:

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 149 of file container.c.

{
  int i;
  tor_assert(sl);
  tor_assert(element);
  for (i = 0; i < sl->num_used; ++i) {
    if (!strcmp(element, sl->list[i])) {
      tor_free(sl->list[i]);
      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
    }
  }
}

Here is the caller graph for this function:

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 230 of file container.c.

{
  if (sl1 == NULL)
    return sl2 == NULL;
  if (sl2 == NULL)
    return 0;
  if (smartlist_len(sl1) != smartlist_len(sl2))
    return 0;
  SMARTLIST_FOREACH(sl1, const char *, cp1, {
      const char *cp2 = smartlist_get(sl2, cp1_sl_idx);
      if (strcmp(cp1, cp2))
        return 0;
    });
  return 1;
}

Here is the caller graph for this function:

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.

Definition at line 290 of file container.c.

{
  int i;
  for (i=0; i < sl2->num_used; i++)
    smartlist_remove(sl1, sl2->list[i]);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 532 of file container.c.

{
  int i;
  for (i=1; i < sl->num_used; ++i) {
    if (compare((const void **)&(sl->list[i-1]),
                (const void **)&(sl->list[i])) == 0) {
      if (free_fn)
        free_fn(sl->list[i]);
      smartlist_del_keeporder(sl, i--);
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 846 of file container.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 877 of file container.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 628 of file container.c.

Here is the call graph for this function:

Here is the caller graph for this function:

void strmap_assert_ok ( const strmap_t *  map)

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

Definition at line 1355 of file container.c.

{
  tor_assert(!strmap_impl_HT_REP_IS_BAD_(&map->head));
}

Here is the caller graph for this function:

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.

Definition at line 901 of file container.c.

{
  return !strcmp(a->key, b->key);
}
static INLINE unsigned int strmap_entry_hash ( const strmap_entry_t *  a) [static]

Helper: return a hash value for a strmap_entry_t.

Definition at line 908 of file container.c.

{
  return ht_string_hash(a->key);
}

Here is the call graph for this function:

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.

Definition at line 1311 of file container.c.

{
  strmap_entry_t **ent, **next, *this;
  if (!map)
    return;

  for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) {
    this = *ent;
    next = HT_NEXT_RMV(strmap_impl, &map->head, ent);
    tor_free(this->key);
    if (free_val)
      free_val(this->val);
    tor_free(this);
  }
  tor_assert(HT_EMPTY(&map->head));
  HT_CLEAR(strmap_impl, &map->head);
  tor_free(map);
}

Here is the caller graph for this function:

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

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

Definition at line 1054 of file container.c.

{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
  resolve = HT_FIND(strmap_impl, &map->head, &search);
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

Here is the caller graph for this function:

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

Same as strmap_get, but first converts key to lowercase.

Definition at line 1148 of file container.c.

{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_get(map,lc_key);
  tor_free(lc_key);
  return v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int strmap_isempty ( const strmap_t *  map)

Return true iff map has no entries.

Definition at line 1369 of file container.c.

{
  return HT_EMPTY(&map->head);
}

Here is the caller graph for this function:

int strmap_iter_done ( strmap_iter_t *  iter)

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

Definition at line 1293 of file container.c.

{
  return iter == NULL;
}

Here is the caller graph for this function:

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.

Definition at line 1267 of file container.c.

{
  tor_assert(iter);
  tor_assert(*iter);
  tor_assert(keyp);
  tor_assert(valp);
  *keyp = (*iter)->key;
  *valp = (*iter)->val;
}

Here is the caller graph for this function:

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);
    }
 }

Definition at line 1197 of file container.c.

{
  tor_assert(map);
  return HT_START(strmap_impl, &map->head);
}

Here is the caller graph for this function:

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.

Definition at line 1214 of file container.c.

{
  tor_assert(map);
  tor_assert(iter);
  return HT_NEXT(strmap_impl, &map->head, iter);
}

Here is the caller graph for this function:

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.

Definition at line 1235 of file container.c.

{
  strmap_entry_t *rmv;
  tor_assert(map);
  tor_assert(iter);
  tor_assert(*iter);
  rmv = *iter;
  iter = HT_NEXT_RMV(strmap_impl, &map->head, iter);
  tor_free(rmv->key);
  tor_free(rmv);
  return iter;
}

Here is the caller graph for this function:

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.

Definition at line 1093 of file container.c.

{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
  resolve = HT_REMOVE(strmap_impl, &map->head, &search);
  if (resolve) {
    oldval = resolve->val;
    tor_free(resolve->key);
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

Here is the caller graph for this function:

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

Same as strmap_remove, but first converts key to lowercase.

Definition at line 1160 of file container.c.

{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_remove(map,lc_key);
  tor_free(lc_key);
  return v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 972 of file container.c.

{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  search.key = (char*)key;
  resolve = HT_FIND(strmap_impl, &map->head, &search);
  if (resolve) {
    oldval = resolve->val;
    resolve->val = val;
    return oldval;
  } else {
    resolve = tor_malloc_zero(sizeof(strmap_entry_t));
    resolve->key = tor_strdup(key);
    resolve->val = val;
    tor_assert(!HT_FIND(strmap_impl, &map->head, resolve));
    HT_INSERT(strmap_impl, &map->head, resolve);
    return NULL;
  }
}

Here is the caller graph for this function:

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

Same as strmap_set, but first converts key to lowercase.

Definition at line 1134 of file container.c.

{
  /* We could be a little faster by using strcasecmp instead, and a separate
   * type, but I don't think it matters. */
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_set(map,lc_key,val);
  tor_free(lc_key);
  return v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int strmap_size ( const strmap_t *  map)

Return the number of items in map.

Definition at line 1383 of file container.c.

{
  return HT_SIZE(&map->head);
}

Here is the caller graph for this function: