container.c

关于tor匿名通信的源代码

smartlist_join_strings2(smartlist_t *sl, const char *join,
                        size_t join_len, int terminate, size_t *len_out)
{
  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;
}

/** Sort the members of <b>sl</b> into an order defined by
 * the ordering function <b>compare</b>, which returns less then 0 if a
 * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
 */
void
smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
{
  if (!sl->num_used)
    return;
  qsort(sl->list, sl->num_used, sizeof(void*),
        (int (*)(const void *,const void*))compare);
}

/** Given a sorted smartlist <b>sl</b> 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.
 */
void
smartlist_uniq(smartlist_t *sl,
               int (*compare)(const void **a, const void **b),
               void (*free_fn)(void *a))
{
  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--);
    }
  }
}

/** Assuming the members of <b>sl</b> are in order, return a pointer to the
 * member that matches <b>key</b>.  Ordering and matching are defined by a
 * <b>compare</b> 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.
 */
void *
smartlist_bsearch(smartlist_t *sl, const void *key,
                  int (*compare)(const void *key, const void **member))
{
  int found, idx;
  idx = smartlist_bsearch_idx(sl, key, compare, &found);
  return found ? smartlist_get(sl, idx) : NULL;
}

/** Assuming the members of <b>sl</b> are in order, return the index of the
 * member that matches <b>key</b>.  If no member matches, return the index of
 * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
 * is greater than <b>key</b>.  Set <b>found_out</b> to true on a match, to
 * false otherwise.  Ordering and matching are defined by a <b>compare</b>
 * 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.
 */
int
smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
                      int (*compare)(const void *key, const void **member),
                      int *found_out)
{
  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;
}

/** Helper: compare two const char **s. */
static int
_compare_string_ptrs(const void **_a, const void **_b)
{
  return strcmp((const char*)*_a, (const char*)*_b);
}

/** Sort a smartlist <b>sl</b> containing strings into lexically ascending
 * order. */
void
smartlist_sort_strings(smartlist_t *sl)
{
  smartlist_sort(sl, _compare_string_ptrs);
}

/** Remove duplicate strings from a sorted list, and free them with tor_free().
 */
void
smartlist_uniq_strings(smartlist_t *sl)
{
  smartlist_uniq(sl, _compare_string_ptrs, _tor_free);
}

/* Heap-based priority queue implementation for O(lg N) insert and remove.
 * Recall that the heap property is that, for every index I, h[I] <
 * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
 */

/* 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. */
//#define LEFT_CHILD(i)  ( ((i)+1)*2 - 1)
//#define RIGHT_CHILD(i) ( ((i)+1)*2 )
//#define PARENT(i)      ( ((i)+1)/2 - 1)
#define LEFT_CHILD(i)  ( 2*(i) + 1 )
#define RIGHT_CHILD(i) ( 2*(i) + 2 )
#define PARENT(i)      ( ((i)-1) / 2 )

/** Helper. <b>sl</b> may have at most one violation of the heap property:
 * the item at <b>idx</b> may be greater than one or both of its children.
 * Restore the heap property. */
static INLINE void
smartlist_heapify(smartlist_t *sl,
                  int (*compare)(const void *a, const void *b),
                  int idx)
{
  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;

      idx = best_idx;
    }
  }
}

/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order
 * is determined by <b>compare</b>. */
void
smartlist_pqueue_add(smartlist_t *sl,
                     int (*compare)(const void *a, const void *b),
                     void *item)
{
  int idx;
  smartlist_add(sl,item);

  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;
      idx = parent;
    } else {
      return;
    }
  }
}

/** Remove and return the top-priority item from the heap stored in <b>sl</b>,
 * where order is determined by <b>compare</b>.  <b>sl</b> must not be
 * empty. */
void *
smartlist_pqueue_pop(smartlist_t *sl,
                     int (*compare)(const void *a, const void *b))
{
  void *top;
  tor_assert(sl->num_used);

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

/** Assert that the heap property is correctly maintained by the heap stored
 * in <b>sl</b>, where order is determined by <b>compare</b>. */
void
smartlist_pqueue_assert_ok(smartlist_t *sl,
                           int (*compare)(const void *a, const void *b))
{
  int i;
  for (i = sl->num_used - 1; i > 0; --i) {
    tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
  }
}

/** Helper: compare two DIGEST_LEN digests. */
static int
_compare_digests(const void **_a, const void **_b)
{
  return memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
}

/** Sort the list of DIGEST_LEN-byte digests into ascending order. */
void
smartlist_sort_digests(smartlist_t *sl)
{
  smartlist_sort(sl, _compare_digests);
}

/** Remove duplicate digests from a sorted list, and free them with tor_free().
 */
void
smartlist_uniq_digests(smartlist_t *sl)
{
  smartlist_uniq(sl, _compare_digests, _tor_free);
}

#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
  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;      \
  }

DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);

/** Helper: compare strmap_entry_t objects by key value. */
static INLINE int
strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
{
  return !strcmp(a->key, b->key);
}

/** Helper: return a hash value for a strmap_entry_t. */
static INLINE unsigned int
strmap_entry_hash(const strmap_entry_t *a)
{
  return ht_string_hash(a->key);
}

/** Helper: compare digestmap_entry_t objects by key value. */
static INLINE int
digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
{
  return !memcmp(a->key, b->key, DIGEST_LEN);
}

/** Helper: return a hash value for a digest_map_t. */
static INLINE unsigned int
digestmap_entry_hash(const digestmap_entry_t *a)
{
#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
}

HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
             strmap_entries_eq)
HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
            strmap_entries_eq, 0.6, malloc, realloc, free)

HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
             digestmap_entries_eq)
HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
            digestmap_entries_eq, 0.6, malloc, realloc, free)

/** Constructor to create a new empty map from strings to void*'s.
 */
strmap_t *
strmap_new(void)
{
  strmap_t *result;
  result = tor_malloc(sizeof(strmap_t));
  HT_INIT(strmap_impl, &result->head);
  return result;
}

/** Constructor to create a new empty map from digests to void*'s.
 */
digestmap_t *
digestmap_new(void)
{
  digestmap_t *result;
  result = tor_malloc(sizeof(digestmap_t));
  HT_INIT(digestmap_impl, &result->head);
  return result;
}

/** Set the current value for <b>key</b> to <b>val</b>.  Returns the previous
 * value for <b>key</b> if one was set, or NULL if one was not.
 *
 * This function makes a copy of <b>key</b> if necessary, but not of
 * <b>val</b>.
 */
void *
strmap_set(strmap_t *map, const char *key, void *val)
{
  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;
  }
}

#define OPTIMIZED_DIGESTMAP_SET

/** Like strmap_set() above but for digestmaps. */
void *
digestmap_set(digestmap_t *map, const char *key, void *val)
{
#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));