Back to index

tor  0.2.3.18-rc
Classes | Defines | Typedefs | Functions
container.h File Reference
#include "util.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  smartlist_t
 A resizeable list of pointers, with associated helpful functionality. More...
struct  digestset_t
 A set of digests, implemented as a Bloom filter. More...

Defines

#define smartlist_len(sl)   ((sl)->num_used)
#define smartlist_get(sl, idx)   ((sl)->list[idx])
#define smartlist_set(sl, idx, val)   ((sl)->list[idx] = (val))
#define SPLIT_SKIP_SPACE   0x01
#define SPLIT_IGNORE_BLANK   0x02
#define SPLIT_STRIP_SPACE   0x04
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
 Iterate over the items in a smartlist sl, in order.
#define SMARTLIST_FOREACH_END(var)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
#define SMARTLIST_DEL_CURRENT(sl, var)
 Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed with the variable var, remove the current element in a way that won't confuse the loop.
#define SMARTLIST_REPLACE_CURRENT(sl, var, val)
 Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed with the variable var, replace the current element with val.
#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2,cmpexpr, unmatched_var2)
#define SMARTLIST_FOREACH_JOIN_END(var1, var2)
#define DECLARE_MAP_FNS(maptype, keytype, prefix)
#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar)
 Iterates over the key-value pairs in a map map in order.
#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar)
 As MAP_FOREACH, except allows members to be removed from the map during the iteration via MAP_DEL_CURRENT.
#define MAP_DEL_CURRENT(keyvar)
 Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon member of the map.
#define MAP_FOREACH_END   } STMT_END ;
 Used to end a MAP_FOREACH() block.
#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar)   MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar)
 As MAP_FOREACH, but does not require declaration of prefix or keytype.
#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)   MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar)
 As MAP_FOREACH_MODIFY, but does not require declaration of prefix or keytype.
#define DIGESTMAP_FOREACH_END   MAP_FOREACH_END
 Used to end a DIGESTMAP_FOREACH() block.
#define STRMAP_FOREACH(map, keyvar, valtype, valvar)   MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar)
#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)   MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar)
#define STRMAP_FOREACH_END   MAP_FOREACH_END
#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype)
#define BITARRAY_MASK   ((1u<<BITARRAY_SHIFT)-1)
#define BIT(n)   ((n) & set->mask)

Typedefs

typedef struct smartlist_t smartlist_t
 A resizeable list of pointers, with associated helpful functionality.
typedef unsigned int bitarray_t
 A random-access array of one-bit-wide elements.

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.
void smartlist_add (smartlist_t *sl, void *element)
 Append element to the end of the list.
void smartlist_add_all (smartlist_t *sl, 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 *, const char *elt)
 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).
static INLINE void smartlist_swap (smartlist_t *sl, int idx1, int idx2)
 Exchange the elements at indices idx1 and idx2 of the smartlist sl.
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.
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 *elt))
void smartlist_sort_strings (smartlist_t *sl)
 Sort a smartlist sl containing strings into lexically ascending order.
void smartlist_sort_digests (smartlist_t *sl)
 Sort the list of DIGEST_LEN-byte digests into ascending order.
void smartlist_sort_digests256 (smartlist_t *sl)
 Sort the list of DIGEST256_LEN-byte digests into ascending order.
char * smartlist_get_most_frequent_string (smartlist_t *sl)
 Return the most frequent string in the sorted list sl
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_strings (smartlist_t *sl)
 Remove duplicate strings from a sorted list, and free them with tor_free().
void smartlist_uniq_digests (smartlist_t *sl)
 Remove duplicate digests from a sorted list, and free them with tor_free().
void smartlist_uniq_digests256 (smartlist_t *sl)
 Remove duplicate 256-bit digests from a sorted list, and free them with tor_free().
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.
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.
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) ATTR_MALLOC
 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) ATTR_MALLOC
 As smartlist_join_strings, but instead of separating/terminated with a NUL-terminated string join, uses the join_len-byte sequence at join.
 DECLARE_MAP_FNS (strmap_t, const char *, strmap_)
 DECLARE_MAP_FNS (digestmap_t, const char *, digestmap_)
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.
static INLINE bitarray_tbitarray_init_zero (unsigned int n_bits)
 Create a new bit array that can hold n_bits bits.
static INLINE bitarray_tbitarray_expand (bitarray_t *ba, unsigned int n_bits_old, unsigned int n_bits_new)
 Expand ba from holding n_bits_old to n_bits_new, clearing all new bits.
static INLINE void bitarray_free (bitarray_t *ba)
 Free the bit array ba.
static INLINE void bitarray_set (bitarray_t *b, int bit)
 Set the bitth bit in b to 1.
static INLINE void bitarray_clear (bitarray_t *b, int bit)
 Set the bitth bit in b to 0.
static INLINE unsigned int bitarray_is_set (bitarray_t *b, int bit)
 Return true iff bitth bit in b is nonzero.
static INLINE void digestset_add (digestset_t *set, const char *digest)
 Add the digest digest to set.
static INLINE int digestset_isin (const digestset_t *set, const char *digest)
 If digest is in set, return nonzero.
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.
int find_nth_int (int *array, int n_elements, int nth)
time_t find_nth_time (time_t *array, int n_elements, int nth)
double find_nth_double (double *array, int n_elements, int nth)
int32_t find_nth_int32 (int32_t *array, int n_elements, int nth)
uint32_t find_nth_uint32 (uint32_t *array, int n_elements, int nth)
long find_nth_long (long *array, int n_elements, int nth)
static INLINE int median_int (int *array, int n_elements)
static INLINE time_t median_time (time_t *array, int n_elements)
static INLINE double median_double (double *array, int n_elements)
static INLINE uint32_t median_uint32 (uint32_t *array, int n_elements)
static INLINE int32_t median_int32 (int32_t *array, int n_elements)
static INLINE long median_long (long *array, int n_elements)

Class Documentation

struct smartlist_t

A resizeable list of pointers, with associated helpful functionality.

The members of this struct are exposed only so that macros and inlines can use them; all access to smartlist internals should go through the functions and macros defined here.

Definition at line 17 of file container.h.

Class Members
int capacity
void ** list list has enough capacity to store exactly capacity elements before it needs to be resized. Only the first num_used (<= capacity) elements point to valid data.
int num_used
struct digestset_t

A set of digests, implemented as a Bloom filter.

Definition at line 595 of file container.h.

Class Members
bitarray_t * ba A bit array to implement the Bloom filter.
int mask One less than the number of bits in ba; always one less than a power of two.

Define Documentation

#define BIT (   n)    ((n) & set->mask)

Definition at line 601 of file container.h.

#define BITARRAY_MASK   ((1u<<BITARRAY_SHIFT)-1)

Definition at line 537 of file container.h.

#define DECLARE_MAP_FNS (   maptype,
  keytype,
  prefix 
)
Value:
typedef struct maptype maptype;                                       \
  typedef struct prefix##entry_t *prefix##iter_t;                       \
  maptype* prefix##new(void);                                           \
  void* prefix##set(maptype *map, keytype key, void *val);              \
  void* prefix##get(const maptype *map, keytype key);                   \
  void* prefix##remove(maptype *map, keytype key);                      \
  void prefix##free(maptype *map, void (*free_val)(void*));             \
  int prefix##isempty(const maptype *map);                              \
  int prefix##size(const maptype *map);                                 \
  prefix##iter_t *prefix##iter_init(maptype *map);                      \
  prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \
  prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \
  void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \
  int prefix##iter_done(prefix##iter_t *iter);                          \
  void prefix##assert_ok(const maptype *map)

Definition at line 319 of file container.h.

#define DECLARE_TYPED_DIGESTMAP_FNS (   prefix,
  maptype,
  valtype 
)

Definition at line 465 of file container.h.

#define DIGESTMAP_FOREACH (   map,
  keyvar,
  valtype,
  valvar 
)    MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar)

As MAP_FOREACH, but does not require declaration of prefix or keytype.

Example use: DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) { // use k and r } DIGESTMAP_FOREACH_END.

Definition at line 439 of file container.h.

Used to end a DIGESTMAP_FOREACH() block.

Definition at line 453 of file container.h.

#define DIGESTMAP_FOREACH_MODIFY (   map,
  keyvar,
  valtype,
  valvar 
)    MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar)

As MAP_FOREACH_MODIFY, but does not require declaration of prefix or keytype.

Example use: DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) { if (is_very_old(r)) MAP_DEL_CURRENT(k); } DIGESTMAP_FOREACH_END.

Definition at line 450 of file container.h.

#define MAP_DEL_CURRENT (   keyvar)
Value:
STMT_BEGIN                                      \
    keyvar##_del = 1;                             \
  STMT_END

Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon member of the map.

Definition at line 425 of file container.h.

#define MAP_FOREACH (   prefix,
  map,
  keytype,
  keyvar,
  valtype,
  valvar 
)
Value:
STMT_BEGIN                                                            \
    prefix##iter_t *keyvar##_iter;                                      \
    for (keyvar##_iter = prefix##iter_init(map);                        \
         !prefix##iter_done(keyvar##_iter);                             \
         keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) {       \
      keytype keyvar;                                                   \
      void *valvar##_voidp;                                             \
      valtype valvar;                                                   \
      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
      valvar = valvar##_voidp;

Iterates over the key-value pairs in a map map in order.

prefix is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_). The map's keys and values are of type keytype and valtype respectively; each iteration assigns them to keyvar and valvar.

Example use: MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { // use k and r } MAP_FOREACH_END.

Definition at line 367 of file container.h.

#define MAP_FOREACH_END   } STMT_END ;

Used to end a MAP_FOREACH() block.

Definition at line 431 of file container.h.

#define MAP_FOREACH_MODIFY (   prefix,
  map,
  keytype,
  keyvar,
  valtype,
  valvar 
)
Value:
STMT_BEGIN                                                            \
    prefix##iter_t *keyvar##_iter;                                      \
    int keyvar##_del=0;                                                 \
    for (keyvar##_iter = prefix##iter_init(map);                        \
         !prefix##iter_done(keyvar##_iter);                             \
         keyvar##_iter = keyvar##_del ?                                 \
           prefix##iter_next_rmv(map, keyvar##_iter) :                  \
           prefix##iter_next(map, keyvar##_iter)) {                     \
      keytype keyvar;                                                   \
      void *valvar##_voidp;                                             \
      valtype valvar;                                                   \
      keyvar##_del=0;                                                   \
      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
      valvar = valvar##_voidp;

As MAP_FOREACH, except allows members to be removed from the map during the iteration via MAP_DEL_CURRENT.

Example use:

Example use: MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { if (is_very_old(r)) MAP_DEL_CURRENT(k); } MAP_FOREACH_END.

Definition at line 407 of file container.h.

#define SMARTLIST_DEL_CURRENT (   sl,
  var 
)
Value:
STMT_BEGIN                                    \
    smartlist_del(sl, var ## _sl_idx);          \
    --var ## _sl_idx;                           \
    --var ## _sl_len;                           \
  STMT_END

Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed with the variable var, remove the current element in a way that won't confuse the loop.

Definition at line 229 of file container.h.

#define SMARTLIST_FOREACH (   sl,
  type,
  var,
  cmd 
)
Value:
SMARTLIST_FOREACH_BEGIN(sl,type,var) {                        \
    cmd;                                                        \
  } SMARTLIST_FOREACH_END(var)

Definition at line 221 of file container.h.

#define SMARTLIST_FOREACH_BEGIN (   sl,
  type,
  var 
)
Value:
STMT_BEGIN                                                    \
    int var ## _sl_idx, var ## _sl_len=(sl)->num_used;          \
    type var;                                                   \
    for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len;   \
         ++var ## _sl_idx) {                                    \
      var = (sl)->list[var ## _sl_idx];

Iterate over the items in a smartlist sl, in order.

For each item, assign it to a new local variable of type type named var, and execute the statement cmd. Inside the loop, the loop index can be accessed as var_sl_idx and the length of the list can be accessed as var_sl_len.

NOTE: Do not change the length of the list while the loop is in progress, unless you adjust the _sl_len variable correspondingly. See second example below.

Example use:

   smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
   SMARTLIST_FOREACH(list, char *, cp,
   {
     printf("%d: %s\n", cp_sl_idx, cp);
     tor_free(cp);
   });
   smartlist_free(list);
 

Example use (advanced):

   SMARTLIST_FOREACH(list, char *, cp,
   {
     if (!strcmp(cp, "junk")) {
       tor_free(cp);
       SMARTLIST_DEL_CURRENT(list, cp);
     }
   });
 

Definition at line 209 of file container.h.

#define SMARTLIST_FOREACH_END (   var)
Value:
var = NULL;                                 \
  } STMT_END

Definition at line 217 of file container.h.

#define SMARTLIST_FOREACH_JOIN (   sl1,
  type1,
  var1,
  sl2,
  type2,
  var2,
  cmpexpr,
  unmatched_var2 
)
Value:
STMT_BEGIN                                                            \
  int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used;             \
  int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used;             \
  int var1 ## _ ## var2 ## _cmp;                                        \
  type1 var1;                                                           \
  type2 var2;                                                           \
  for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) {              \
    var2 = (sl2)->list[var2##_sl_idx];                                  \
    while (var1##_sl_idx < var1##_sl_len) {                             \
      var1 = (sl1)->list[var1##_sl_idx];                                \
      var1##_##var2##_cmp = (cmpexpr);                                  \
      if (var1##_##var2##_cmp > 0) {                                    \
        break;                                                          \
      } else if (var1##_##var2##_cmp == 0) {                            \
        goto matched_##var2;                                            \
      } else {                                                          \
        ++var1##_sl_idx;                                                \
      }                                                                 \
    }                                                                   \
    /* Ran out of v1, or no match for var2. */                          \
    unmatched_var2;                                                     \
    continue;                                                           \
    matched_##var2: ;                                                   \

Definition at line 289 of file container.h.

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

Definition at line 315 of file container.h.

#define smartlist_get (   sl,
  idx 
)    ((sl)->list[idx])

Definition at line 75 of file container.h.

#define smartlist_len (   sl)    ((sl)->num_used)

Definition at line 74 of file container.h.

#define SMARTLIST_REPLACE_CURRENT (   sl,
  var,
  val 
)
Value:
STMT_BEGIN                                    \
    smartlist_set(sl, var ## _sl_idx, val);     \
  STMT_END

Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed with the variable var, replace the current element with val.

Does not deallocate the current value of var.

Definition at line 240 of file container.h.

#define smartlist_set (   sl,
  idx,
  val 
)    ((sl)->list[idx] = (val))

Definition at line 76 of file container.h.

#define SPLIT_IGNORE_BLANK   0x02

Definition at line 133 of file container.h.

#define SPLIT_SKIP_SPACE   0x01

Definition at line 132 of file container.h.

#define SPLIT_STRIP_SPACE   0x04

Definition at line 134 of file container.h.

#define STRMAP_FOREACH (   map,
  keyvar,
  valtype,
  valvar 
)    MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar)

Definition at line 455 of file container.h.

Definition at line 459 of file container.h.

#define STRMAP_FOREACH_MODIFY (   map,
  keyvar,
  valtype,
  valvar 
)    MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar)

Definition at line 457 of file container.h.


Typedef Documentation

typedef unsigned int bitarray_t

A random-access array of one-bit-wide elements.

Definition at line 540 of file container.h.

typedef struct smartlist_t smartlist_t

A resizeable list of pointers, with associated helpful functionality.

The members of this struct are exposed only so that macros and inlines can use them; all access to smartlist internals should go through the functions and macros defined here.


Function Documentation

static INLINE void bitarray_clear ( bitarray_t b,
int  bit 
) [static]

Set the bitth bit in b to 0.

Definition at line 582 of file container.h.

{
  b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
}

Here is the caller graph for this function:

static INLINE bitarray_t* bitarray_expand ( bitarray_t ba,
unsigned int  n_bits_old,
unsigned int  n_bits_new 
) [static]

Expand ba from holding n_bits_old to n_bits_new, clearing all new bits.

Returns a possibly changed pointer to the bitarray.

Definition at line 553 of file container.h.

{
  size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT;
  size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT;
  char *ptr;
  if (sz_new <= sz_old)
    return ba;
  ptr = tor_realloc(ba, sz_new*sizeof(unsigned int));
  /* This memset does nothing to the older excess bytes.  But they were
   * already set to 0 by bitarry_init_zero. */
  memset(ptr+sz_old*sizeof(unsigned int), 0,
         (sz_new-sz_old)*sizeof(unsigned int));
  return (bitarray_t*) ptr;
}
static INLINE void bitarray_free ( bitarray_t ba) [static]

Free the bit array ba.

Definition at line 570 of file container.h.

{
  tor_free(ba);
}

Here is the caller graph for this function:

static INLINE bitarray_t* bitarray_init_zero ( unsigned int  n_bits) [static]

Create a new bit array that can hold n_bits bits.

Definition at line 543 of file container.h.

{
  /* round up to the next int. */
  size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
  return tor_malloc_zero(sz*sizeof(unsigned int));
}

Here is the caller graph for this function:

static INLINE unsigned int bitarray_is_set ( bitarray_t b,
int  bit 
) [static]

Return true iff bitth bit in b is nonzero.

NOTE: does not necessarily return 1 on true.

Definition at line 589 of file container.h.

{
  return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
}

Here is the caller graph for this function:

static INLINE void bitarray_set ( bitarray_t b,
int  bit 
) [static]

Set the bitth bit in b to 1.

Definition at line 576 of file container.h.

{
  b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
}

Here is the caller graph for this function:

DECLARE_MAP_FNS ( strmap_t  ,
const char *  ,
strmap_   
)
DECLARE_MAP_FNS ( digestmap_t  ,
const char *  ,
digestmap_   
)
static INLINE void digestset_add ( digestset_t set,
const char *  digest 
) [static]

Add the digest digest to set.

Definition at line 604 of file container.h.

{
  const uint32_t *p = (const uint32_t *)digest;
  const uint32_t d1 = p[0] + (p[1]>>16);
  const uint32_t d2 = p[1] + (p[2]>>16);
  const uint32_t d3 = p[2] + (p[3]>>16);
  const uint32_t d4 = p[3] + (p[0]>>16);
  bitarray_set(set->ba, BIT(d1));
  bitarray_set(set->ba, BIT(d2));
  bitarray_set(set->ba, BIT(d3));
  bitarray_set(set->ba, BIT(d4));
}

Here is the call graph for this function:

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:

static INLINE int digestset_isin ( const digestset_t set,
const char *  digest 
) [static]

If digest is in set, return nonzero.

Otherwise, probably return zero.

Definition at line 620 of file container.h.

{
  const uint32_t *p = (const uint32_t *)digest;
  const uint32_t d1 = p[0] + (p[1]>>16);
  const uint32_t d2 = p[1] + (p[2]>>16);
  const uint32_t d3 = p[2] + (p[3]>>16);
  const uint32_t d4 = p[3] + (p[0]>>16);
  return bitarray_is_set(set->ba, BIT(d1)) &&
         bitarray_is_set(set->ba, BIT(d2)) &&
         bitarray_is_set(set->ba, BIT(d3)) &&
         bitarray_is_set(set->ba, BIT(d4));
}

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:

double find_nth_double ( double *  array,
int  n_elements,
int  nth 
)

Here is the caller graph for this function:

int find_nth_int ( int *  array,
int  n_elements,
int  nth 
)

Here is the caller graph for this function:

int32_t find_nth_int32 ( int32_t *  array,
int  n_elements,
int  nth 
)

Here is the caller graph for this function:

long find_nth_long ( long *  array,
int  n_elements,
int  nth 
)

Here is the caller graph for this function:

time_t find_nth_time ( time_t *  array,
int  n_elements,
int  nth 
)

Here is the caller graph for this function:

uint32_t find_nth_uint32 ( uint32_t *  array,
int  n_elements,
int  nth 
)

Here is the caller graph for this function:

static INLINE double median_double ( double *  array,
int  n_elements 
) [static]

Definition at line 658 of file container.h.

{
  return find_nth_double(array, n_elements, (n_elements-1)/2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE int median_int ( int *  array,
int  n_elements 
) [static]

Definition at line 648 of file container.h.

{
  return find_nth_int(array, n_elements, (n_elements-1)/2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE int32_t median_int32 ( int32_t *  array,
int  n_elements 
) [static]

Definition at line 668 of file container.h.

{
  return find_nth_int32(array, n_elements, (n_elements-1)/2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE long median_long ( long *  array,
int  n_elements 
) [static]

Definition at line 673 of file container.h.

{
  return find_nth_long(array, n_elements, (n_elements-1)/2);
}

Here is the call graph for this function:

static INLINE time_t median_time ( time_t *  array,
int  n_elements 
) [static]

Definition at line 653 of file container.h.

{
  return find_nth_time(array, n_elements, (n_elements-1)/2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE uint32_t median_uint32 ( uint32_t *  array,
int  n_elements 
) [static]

Definition at line 663 of file container.h.

{
  return find_nth_uint32(array, n_elements, (n_elements-1)/2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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:

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:

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:

static INLINE void smartlist_swap ( smartlist_t sl,
int  idx1,
int  idx2 
) [static]

Exchange the elements at indices idx1 and idx2 of the smartlist sl.

Definition at line 81 of file container.h.

{
  if (idx1 != idx2) {
    void *elt = smartlist_get(sl, idx1);
    smartlist_set(sl, idx1, smartlist_get(sl, idx2));
    smartlist_set(sl, idx2, elt);
  }
}

Here is the caller graph for this function:

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

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_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:

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_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: