container.c
上传用户:awang829
上传日期:2019-07-14
资源大小:2356k
文件大小:34k
源码类别:

网络

开发平台:

Unix_Linux

  1. /* Copyright (c) 2003-2004, Roger Dingledine
  2.  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3.  * Copyright (c) 2007-2009, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. /**
  6.  * file container.c
  7.  * brief Implements a smartlist (a resizable array) along
  8.  * with helper functions to use smartlists.  Also includes
  9.  * hash table implementations of a string-to-void* map, and of
  10.  * a digest-to-void* map.
  11.  **/
  12. #include "compat.h"
  13. #include "util.h"
  14. #include "log.h"
  15. #include "container.h"
  16. #include "crypto.h"
  17. #include <stdlib.h>
  18. #include <string.h>
  19. #include <assert.h>
  20. #include "ht.h"
  21. /** All newly allocated smartlists have this capacity. */
  22. #define SMARTLIST_DEFAULT_CAPACITY 16
  23. /** Allocate and return an empty smartlist.
  24.  */
  25. smartlist_t *
  26. smartlist_create(void)
  27. {
  28.   smartlist_t *sl = tor_malloc(sizeof(smartlist_t));
  29.   sl->num_used = 0;
  30.   sl->capacity = SMARTLIST_DEFAULT_CAPACITY;
  31.   sl->list = tor_malloc(sizeof(void *) * sl->capacity);
  32.   return sl;
  33. }
  34. /** Deallocate a smartlist.  Does not release storage associated with the
  35.  * list's elements.
  36.  */
  37. void
  38. smartlist_free(smartlist_t *sl)
  39. {
  40.   tor_assert(sl != NULL);
  41.   tor_free(sl->list);
  42.   tor_free(sl);
  43. }
  44. /** Remove all elements from the list.
  45.  */
  46. void
  47. smartlist_clear(smartlist_t *sl)
  48. {
  49.   sl->num_used = 0;
  50. }
  51. /** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
  52. static INLINE void
  53. smartlist_ensure_capacity(smartlist_t *sl, int size)
  54. {
  55.   if (size > sl->capacity) {
  56.     int higher = sl->capacity * 2;
  57.     while (size > higher)
  58.       higher *= 2;
  59.     tor_assert(higher > 0); /* detect overflow */
  60.     sl->capacity = higher;
  61.     sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
  62.   }
  63. }
  64. /** Append element to the end of the list. */
  65. void
  66. smartlist_add(smartlist_t *sl, void *element)
  67. {
  68.   smartlist_ensure_capacity(sl, sl->num_used+1);
  69.   sl->list[sl->num_used++] = element;
  70. }
  71. /** Append each element from S2 to the end of S1. */
  72. void
  73. smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
  74. {
  75.   int new_size = s1->num_used + s2->num_used;
  76.   tor_assert(new_size >= s1->num_used); /* check for overflow. */
  77.   smartlist_ensure_capacity(s1, new_size);
  78.   memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
  79.   s1->num_used = new_size;
  80. }
  81. /** Remove all elements E from sl such that E==element.  Preserve
  82.  * the order of any elements before E, but elements after E can be
  83.  * rearranged.
  84.  */
  85. void
  86. smartlist_remove(smartlist_t *sl, const void *element)
  87. {
  88.   int i;
  89.   if (element == NULL)
  90.     return;
  91.   for (i=0; i < sl->num_used; i++)
  92.     if (sl->list[i] == element) {
  93.       sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
  94.       i--; /* so we process the new i'th element */
  95.     }
  96. }
  97. /** If <b>sl</b> is nonempty, remove and return the final element.  Otherwise,
  98.  * return NULL. */
  99. void *
  100. smartlist_pop_last(smartlist_t *sl)
  101. {
  102.   tor_assert(sl);
  103.   if (sl->num_used)
  104.     return sl->list[--sl->num_used];
  105.   else
  106.     return NULL;
  107. }
  108. /** Reverse the order of the items in <b>sl</b>. */
  109. void
  110. smartlist_reverse(smartlist_t *sl)
  111. {
  112.   int i, j;
  113.   void *tmp;
  114.   tor_assert(sl);
  115.   for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
  116.     tmp = sl->list[i];
  117.     sl->list[i] = sl->list[j];
  118.     sl->list[j] = tmp;
  119.   }
  120. }
  121. /** If there are any strings in sl equal to element, remove and free them.
  122.  * Does not preserve order. */
  123. void
  124. smartlist_string_remove(smartlist_t *sl, const char *element)
  125. {
  126.   int i;
  127.   tor_assert(sl);
  128.   tor_assert(element);
  129.   for (i = 0; i < sl->num_used; ++i) {
  130.     if (!strcmp(element, sl->list[i])) {
  131.       tor_free(sl->list[i]);
  132.       sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
  133.       i--; /* so we process the new i'th element */
  134.     }
  135.   }
  136. }
  137. /** Return true iff some element E of sl has E==element.
  138.  */
  139. int
  140. smartlist_isin(const smartlist_t *sl, const void *element)
  141. {
  142.   int i;
  143.   for (i=0; i < sl->num_used; i++)
  144.     if (sl->list[i] == element)
  145.       return 1;
  146.   return 0;
  147. }
  148. /** Return true iff <b>sl</b> has some element E such that
  149.  * !strcmp(E,<b>element</b>)
  150.  */
  151. int
  152. smartlist_string_isin(const smartlist_t *sl, const char *element)
  153. {
  154.   int i;
  155.   if (!sl) return 0;
  156.   for (i=0; i < sl->num_used; i++)
  157.     if (strcmp((const char*)sl->list[i],element)==0)
  158.       return 1;
  159.   return 0;
  160. }
  161. /** If <b>element</b> is equal to an element of <b>sl</b>, return that
  162.  * element's index.  Otherwise, return -1. */
  163. int
  164. smartlist_string_pos(const smartlist_t *sl, const char *element)
  165. {
  166.   int i;
  167.   if (!sl) return -1;
  168.   for (i=0; i < sl->num_used; i++)
  169.     if (strcmp((const char*)sl->list[i],element)==0)
  170.       return i;
  171.   return -1;
  172. }
  173. /** Return true iff <b>sl</b> has some element E such that
  174.  * !strcasecmp(E,<b>element</b>)
  175.  */
  176. int
  177. smartlist_string_isin_case(const smartlist_t *sl, const char *element)
  178. {
  179.   int i;
  180.   if (!sl) return 0;
  181.   for (i=0; i < sl->num_used; i++)
  182.     if (strcasecmp((const char*)sl->list[i],element)==0)
  183.       return 1;
  184.   return 0;
  185. }
  186. /** Return true iff <b>sl</b> has some element E such that E is equal
  187.  * to the decimal encoding of <b>num</b>.
  188.  */
  189. int
  190. smartlist_string_num_isin(const smartlist_t *sl, int num)
  191. {
  192.   char buf[16];
  193.   tor_snprintf(buf,sizeof(buf),"%d", num);
  194.   return smartlist_string_isin(sl, buf);
  195. }
  196. /** Return true iff <b>sl</b> has some element E such that
  197.  * !memcmp(E,<b>element</b>,DIGEST_LEN)
  198.  */
  199. int
  200. smartlist_digest_isin(const smartlist_t *sl, const char *element)
  201. {
  202.   int i;
  203.   if (!sl) return 0;
  204.   for (i=0; i < sl->num_used; i++)
  205.     if (memcmp((const char*)sl->list[i],element,DIGEST_LEN)==0)
  206.       return 1;
  207.   return 0;
  208. }
  209. /** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
  210.  */
  211. int
  212. smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
  213. {
  214.   int i;
  215.   for (i=0; i < sl2->num_used; i++)
  216.     if (smartlist_isin(sl1, sl2->list[i]))
  217.       return 1;
  218.   return 0;
  219. }
  220. /** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
  221.  * Does not preserve the order of sl1.
  222.  */
  223. void
  224. smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
  225. {
  226.   int i;
  227.   for (i=0; i < sl1->num_used; i++)
  228.     if (!smartlist_isin(sl2, sl1->list[i])) {
  229.       sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
  230.       i--; /* so we process the new i'th element */
  231.     }
  232. }
  233. /** Remove every element E of sl1 such that smartlist_isin(sl2,E).
  234.  * Does not preserve the order of sl1.
  235.  */
  236. void
  237. smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
  238. {
  239.   int i;
  240.   for (i=0; i < sl2->num_used; i++)
  241.     smartlist_remove(sl1, sl2->list[i]);
  242. }
  243. /** Remove the <b>idx</b>th element of sl; if idx is not the last
  244.  * element, swap the last element of sl into the <b>idx</b>th space.
  245.  * Return the old value of the <b>idx</b>th element.
  246.  */
  247. void
  248. smartlist_del(smartlist_t *sl, int idx)
  249. {
  250.   tor_assert(sl);
  251.   tor_assert(idx>=0);
  252.   tor_assert(idx < sl->num_used);
  253.   sl->list[idx] = sl->list[--sl->num_used];
  254. }
  255. /** Remove the <b>idx</b>th element of sl; if idx is not the last element,
  256.  * moving all subsequent elements back one space. Return the old value
  257.  * of the <b>idx</b>th element.
  258.  */
  259. void
  260. smartlist_del_keeporder(smartlist_t *sl, int idx)
  261. {
  262.   tor_assert(sl);
  263.   tor_assert(idx>=0);
  264.   tor_assert(idx < sl->num_used);
  265.   --sl->num_used;
  266.   if (idx < sl->num_used)
  267.     memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
  268. }
  269. /** Insert the value <b>val</b> as the new <b>idx</b>th element of
  270.  * <b>sl</b>, moving all items previously at <b>idx</b> or later
  271.  * forward one space.
  272.  */
  273. void
  274. smartlist_insert(smartlist_t *sl, int idx, void *val)
  275. {
  276.   tor_assert(sl);
  277.   tor_assert(idx>=0);
  278.   tor_assert(idx <= sl->num_used);
  279.   if (idx == sl->num_used) {
  280.     smartlist_add(sl, val);
  281.   } else {
  282.     smartlist_ensure_capacity(sl, sl->num_used+1);
  283.     /* Move other elements away */
  284.     if (idx < sl->num_used)
  285.       memmove(sl->list + idx + 1, sl->list + idx,
  286.               sizeof(void*)*(sl->num_used-idx));
  287.     sl->num_used++;
  288.     sl->list[idx] = val;
  289.   }
  290. }
  291. /**
  292.  * Split a string <b>str</b> along all occurrences of <b>sep</b>,
  293.  * adding the split strings, in order, to <b>sl</b>.
  294.  *
  295.  * If <b>flags</b>&amp;SPLIT_SKIP_SPACE is true, remove initial and
  296.  * trailing space from each entry.
  297.  * If <b>flags</b>&amp;SPLIT_IGNORE_BLANK is true, remove any entries
  298.  * of length 0.
  299.  * If <b>flags</b>&amp;SPLIT_STRIP_SPACE is true, strip spaces from each
  300.  * split string.
  301.  *
  302.  * If max>0, divide the string into no more than <b>max</b> pieces. If
  303.  * <b>sep</b> is NULL, split on any sequence of horizontal space.
  304.  */
  305. int
  306. smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
  307.                        int flags, int max)
  308. {
  309.   const char *cp, *end, *next;
  310.   int n = 0;
  311.   tor_assert(sl);
  312.   tor_assert(str);
  313.   cp = str;
  314.   while (1) {
  315.     if (flags&SPLIT_SKIP_SPACE) {
  316.       while (TOR_ISSPACE(*cp)) ++cp;
  317.     }
  318.     if (max>0 && n == max-1) {
  319.       end = strchr(cp,'');
  320.     } else if (sep) {
  321.       end = strstr(cp,sep);
  322.       if (!end)
  323.         end = strchr(cp,'');
  324.     } else {
  325.       for (end = cp; *end && *end != 't' && *end != ' '; ++end)
  326.         ;
  327.     }
  328.     tor_assert(end);
  329.     if (!*end) {
  330.       next = NULL;
  331.     } else if (sep) {
  332.       next = end+strlen(sep);
  333.     } else {
  334.       next = end+1;
  335.       while (*next == 't' || *next == ' ')
  336.         ++next;
  337.     }
  338.     if (flags&SPLIT_SKIP_SPACE) {
  339.       while (end > cp && TOR_ISSPACE(*(end-1)))
  340.         --end;
  341.     }
  342.     if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) {
  343.       char *string = tor_strndup(cp, end-cp);
  344.       if (flags&SPLIT_STRIP_SPACE)
  345.         tor_strstrip(string, " ");
  346.       smartlist_add(sl, string);
  347.       ++n;
  348.     }
  349.     if (!next)
  350.       break;
  351.     cp = next;
  352.   }
  353.   return n;
  354. }
  355. /** Allocate and return a new string containing the concatenation of
  356.  * the elements of <b>sl</b>, in order, separated by <b>join</b>.  If
  357.  * <b>terminate</b> is true, also terminate the string with <b>join</b>.
  358.  * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
  359.  * the returned string. Requires that every element of <b>sl</b> is
  360.  * NUL-terminated string.
  361.  */
  362. char *
  363. smartlist_join_strings(smartlist_t *sl, const char *join,
  364.                        int terminate, size_t *len_out)
  365. {
  366.   return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
  367. }
  368. /** As smartlist_join_strings, but instead of separating/terminated with a
  369.  * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
  370.  * at <b>join</b>.  (Useful for generating a sequence of NUL-terminated
  371.  * strings.)
  372.  */
  373. char *
  374. smartlist_join_strings2(smartlist_t *sl, const char *join,
  375.                         size_t join_len, int terminate, size_t *len_out)
  376. {
  377.   int i;
  378.   size_t n = 0;
  379.   char *r = NULL, *dst, *src;
  380.   tor_assert(sl);
  381.   tor_assert(join);
  382.   if (terminate)
  383.     n = join_len;
  384.   for (i = 0; i < sl->num_used; ++i) {
  385.     n += strlen(sl->list[i]);
  386.     if (i+1 < sl->num_used) /* avoid double-counting the last one */
  387.       n += join_len;
  388.   }
  389.   dst = r = tor_malloc(n+1);
  390.   for (i = 0; i < sl->num_used; ) {
  391.     for (src = sl->list[i]; *src; )
  392.       *dst++ = *src++;
  393.     if (++i < sl->num_used) {
  394.       memcpy(dst, join, join_len);
  395.       dst += join_len;
  396.     }
  397.   }
  398.   if (terminate) {
  399.     memcpy(dst, join, join_len);
  400.     dst += join_len;
  401.   }
  402.   *dst = '';
  403.   if (len_out)
  404.     *len_out = dst-r;
  405.   return r;
  406. }
  407. /** Sort the members of <b>sl</b> into an order defined by
  408.  * the ordering function <b>compare</b>, which returns less then 0 if a
  409.  * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
  410.  */
  411. void
  412. smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
  413. {
  414.   if (!sl->num_used)
  415.     return;
  416.   qsort(sl->list, sl->num_used, sizeof(void*),
  417.         (int (*)(const void *,const void*))compare);
  418. }
  419. /** Given a sorted smartlist <b>sl</b> and the comparison function used to
  420.  * sort it, remove all duplicate members.  If free_fn is provided, calls
  421.  * free_fn on each duplicate.  Otherwise, just removes them.  Preserves order.
  422.  */
  423. void
  424. smartlist_uniq(smartlist_t *sl,
  425.                int (*compare)(const void **a, const void **b),
  426.                void (*free_fn)(void *a))
  427. {
  428.   int i;
  429.   for (i=1; i < sl->num_used; ++i) {
  430.     if (compare((const void **)&(sl->list[i-1]),
  431.                 (const void **)&(sl->list[i])) == 0) {
  432.       if (free_fn)
  433.         free_fn(sl->list[i]);
  434.       smartlist_del_keeporder(sl, i--);
  435.     }
  436.   }
  437. }
  438. /** Assuming the members of <b>sl</b> are in order, return a pointer to the
  439.  * member that matches <b>key</b>.  Ordering and matching are defined by a
  440.  * <b>compare</b> function that returns 0 on a match; less than 0 if key is
  441.  * less than member, and greater than 0 if key is greater then member.
  442.  */
  443. void *
  444. smartlist_bsearch(smartlist_t *sl, const void *key,
  445.                   int (*compare)(const void *key, const void **member))
  446. {
  447.   int found, idx;
  448.   idx = smartlist_bsearch_idx(sl, key, compare, &found);
  449.   return found ? smartlist_get(sl, idx) : NULL;
  450. }
  451. /** Assuming the members of <b>sl</b> are in order, return the index of the
  452.  * member that matches <b>key</b>.  If no member matches, return the index of
  453.  * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
  454.  * is greater than <b>key</b>.  Set <b>found_out</b> to true on a match, to
  455.  * false otherwise.  Ordering and matching are defined by a <b>compare</b>
  456.  * function that returns 0 on a match; less than 0 if key is less than member,
  457.  * and greater than 0 if key is greater then member.
  458.  */
  459. int
  460. smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
  461.                       int (*compare)(const void *key, const void **member),
  462.                       int *found_out)
  463. {
  464.   int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid;
  465.   while (lo <= hi) {
  466.     mid = (lo + hi) / 2;
  467.     cmp = compare(key, (const void**) &(sl->list[mid]));
  468.     if (cmp>0) { /* key > sl[mid] */
  469.       lo = mid+1;
  470.     } else if (cmp<0) { /* key < sl[mid] */
  471.       hi = mid-1;
  472.     } else { /* key == sl[mid] */
  473.       *found_out = 1;
  474.       return mid;
  475.     }
  476.   }
  477.   /* lo > hi. */
  478.   {
  479.     tor_assert(lo >= 0);
  480.     if (lo < smartlist_len(sl)) {
  481.       cmp = compare(key, (const void**) &(sl->list[lo]));
  482.       tor_assert(cmp < 0);
  483.     } else if (smartlist_len(sl)) {
  484.       cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1]));
  485.       tor_assert(cmp > 0);
  486.     }
  487.   }
  488.   *found_out = 0;
  489.   return lo;
  490. }
  491. /** Helper: compare two const char **s. */
  492. static int
  493. _compare_string_ptrs(const void **_a, const void **_b)
  494. {
  495.   return strcmp((const char*)*_a, (const char*)*_b);
  496. }
  497. /** Sort a smartlist <b>sl</b> containing strings into lexically ascending
  498.  * order. */
  499. void
  500. smartlist_sort_strings(smartlist_t *sl)
  501. {
  502.   smartlist_sort(sl, _compare_string_ptrs);
  503. }
  504. /** Remove duplicate strings from a sorted list, and free them with tor_free().
  505.  */
  506. void
  507. smartlist_uniq_strings(smartlist_t *sl)
  508. {
  509.   smartlist_uniq(sl, _compare_string_ptrs, _tor_free);
  510. }
  511. /* Heap-based priority queue implementation for O(lg N) insert and remove.
  512.  * Recall that the heap property is that, for every index I, h[I] <
  513.  * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
  514.  */
  515. /* For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
  516.  * = 2*x + 1.  But this is C, so we have to adjust a little. */
  517. //#define LEFT_CHILD(i)  ( ((i)+1)*2 - 1)
  518. //#define RIGHT_CHILD(i) ( ((i)+1)*2 )
  519. //#define PARENT(i)      ( ((i)+1)/2 - 1)
  520. #define LEFT_CHILD(i)  ( 2*(i) + 1 )
  521. #define RIGHT_CHILD(i) ( 2*(i) + 2 )
  522. #define PARENT(i)      ( ((i)-1) / 2 )
  523. /** Helper. <b>sl</b> may have at most one violation of the heap property:
  524.  * the item at <b>idx</b> may be greater than one or both of its children.
  525.  * Restore the heap property. */
  526. static INLINE void
  527. smartlist_heapify(smartlist_t *sl,
  528.                   int (*compare)(const void *a, const void *b),
  529.                   int idx)
  530. {
  531.   while (1) {
  532.     int left_idx = LEFT_CHILD(idx);
  533.     int best_idx;
  534.     if (left_idx >= sl->num_used)
  535.       return;
  536.     if (compare(sl->list[idx],sl->list[left_idx]) < 0)
  537.       best_idx = idx;
  538.     else
  539.       best_idx = left_idx;
  540.     if (left_idx+1 < sl->num_used &&
  541.         compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
  542.       best_idx = left_idx + 1;
  543.     if (best_idx == idx) {
  544.       return;
  545.     } else {
  546.       void *tmp = sl->list[idx];
  547.       sl->list[idx] = sl->list[best_idx];
  548.       sl->list[best_idx] = tmp;
  549.       idx = best_idx;
  550.     }
  551.   }
  552. }
  553. /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order
  554.  * is determined by <b>compare</b>. */
  555. void
  556. smartlist_pqueue_add(smartlist_t *sl,
  557.                      int (*compare)(const void *a, const void *b),
  558.                      void *item)
  559. {
  560.   int idx;
  561.   smartlist_add(sl,item);
  562.   for (idx = sl->num_used - 1; idx; ) {
  563.     int parent = PARENT(idx);
  564.     if (compare(sl->list[idx], sl->list[parent]) < 0) {
  565.       void *tmp = sl->list[parent];
  566.       sl->list[parent] = sl->list[idx];
  567.       sl->list[idx] = tmp;
  568.       idx = parent;
  569.     } else {
  570.       return;
  571.     }
  572.   }
  573. }
  574. /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
  575.  * where order is determined by <b>compare</b>.  <b>sl</b> must not be
  576.  * empty. */
  577. void *
  578. smartlist_pqueue_pop(smartlist_t *sl,
  579.                      int (*compare)(const void *a, const void *b))
  580. {
  581.   void *top;
  582.   tor_assert(sl->num_used);
  583.   top = sl->list[0];
  584.   if (--sl->num_used) {
  585.     sl->list[0] = sl->list[sl->num_used];
  586.     smartlist_heapify(sl, compare, 0);
  587.   }
  588.   return top;
  589. }
  590. /** Assert that the heap property is correctly maintained by the heap stored
  591.  * in <b>sl</b>, where order is determined by <b>compare</b>. */
  592. void
  593. smartlist_pqueue_assert_ok(smartlist_t *sl,
  594.                            int (*compare)(const void *a, const void *b))
  595. {
  596.   int i;
  597.   for (i = sl->num_used - 1; i > 0; --i) {
  598.     tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
  599.   }
  600. }
  601. /** Helper: compare two DIGEST_LEN digests. */
  602. static int
  603. _compare_digests(const void **_a, const void **_b)
  604. {
  605.   return memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
  606. }
  607. /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
  608. void
  609. smartlist_sort_digests(smartlist_t *sl)
  610. {
  611.   smartlist_sort(sl, _compare_digests);
  612. }
  613. /** Remove duplicate digests from a sorted list, and free them with tor_free().
  614.  */
  615. void
  616. smartlist_uniq_digests(smartlist_t *sl)
  617. {
  618.   smartlist_uniq(sl, _compare_digests, _tor_free);
  619. }
  620. /** Helper: Declare an entry type and a map type to implement a mapping using
  621.  * ht.h.  The map type will be called <b>maptype</b>.  The key part of each
  622.  * entry is declared using the C declaration <b>keydecl</b>.  All functions
  623.  * and types associated with the map get prefixed with <b>prefix</b> */
  624. #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      
  625.   typedef struct prefix ## entry_t {                      
  626.     HT_ENTRY(prefix ## entry_t) node;                     
  627.     void *val;                                            
  628.     keydecl;                                              
  629.   } prefix ## entry_t;                                    
  630.   struct maptype {                                        
  631.     HT_HEAD(prefix ## impl, prefix ## entry_t) head;      
  632.   }
  633. DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
  634. DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
  635. /** Helper: compare strmap_entry_t objects by key value. */
  636. static INLINE int
  637. strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
  638. {
  639.   return !strcmp(a->key, b->key);
  640. }
  641. /** Helper: return a hash value for a strmap_entry_t. */
  642. static INLINE unsigned int
  643. strmap_entry_hash(const strmap_entry_t *a)
  644. {
  645.   return ht_string_hash(a->key);
  646. }
  647. /** Helper: compare digestmap_entry_t objects by key value. */
  648. static INLINE int
  649. digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
  650. {
  651.   return !memcmp(a->key, b->key, DIGEST_LEN);
  652. }
  653. /** Helper: return a hash value for a digest_map_t. */
  654. static INLINE unsigned int
  655. digestmap_entry_hash(const digestmap_entry_t *a)
  656. {
  657. #if SIZEOF_INT != 8
  658.   const uint32_t *p = (const uint32_t*)a->key;
  659.   return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
  660. #else
  661.   const uint64_t *p = (const uint64_t*)a->key;
  662.   return p[0] ^ p[1];
  663. #endif
  664. }
  665. HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  666.              strmap_entries_eq)
  667. HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
  668.             strmap_entries_eq, 0.6, malloc, realloc, free)
  669. HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  670.              digestmap_entries_eq)
  671. HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
  672.             digestmap_entries_eq, 0.6, malloc, realloc, free)
  673. /** Constructor to create a new empty map from strings to void*'s.
  674.  */
  675. strmap_t *
  676. strmap_new(void)
  677. {
  678.   strmap_t *result;
  679.   result = tor_malloc(sizeof(strmap_t));
  680.   HT_INIT(strmap_impl, &result->head);
  681.   return result;
  682. }
  683. /** Constructor to create a new empty map from digests to void*'s.
  684.  */
  685. digestmap_t *
  686. digestmap_new(void)
  687. {
  688.   digestmap_t *result;
  689.   result = tor_malloc(sizeof(digestmap_t));
  690.   HT_INIT(digestmap_impl, &result->head);
  691.   return result;
  692. }
  693. /** Set the current value for <b>key</b> to <b>val</b>.  Returns the previous
  694.  * value for <b>key</b> if one was set, or NULL if one was not.
  695.  *
  696.  * This function makes a copy of <b>key</b> if necessary, but not of
  697.  * <b>val</b>.
  698.  */
  699. void *
  700. strmap_set(strmap_t *map, const char *key, void *val)
  701. {
  702.   strmap_entry_t *resolve;
  703.   strmap_entry_t search;
  704.   void *oldval;
  705.   tor_assert(map);
  706.   tor_assert(key);
  707.   tor_assert(val);
  708.   search.key = (char*)key;
  709.   resolve = HT_FIND(strmap_impl, &map->head, &search);
  710.   if (resolve) {
  711.     oldval = resolve->val;
  712.     resolve->val = val;
  713.     return oldval;
  714.   } else {
  715.     resolve = tor_malloc_zero(sizeof(strmap_entry_t));
  716.     resolve->key = tor_strdup(key);
  717.     resolve->val = val;
  718.     tor_assert(!HT_FIND(strmap_impl, &map->head, resolve));
  719.     HT_INSERT(strmap_impl, &map->head, resolve);
  720.     return NULL;
  721.   }
  722. }
  723. #define OPTIMIZED_DIGESTMAP_SET
  724. /** Like strmap_set() above but for digestmaps. */
  725. void *
  726. digestmap_set(digestmap_t *map, const char *key, void *val)
  727. {
  728. #ifndef OPTIMIZED_DIGESTMAP_SET
  729.   digestmap_entry_t *resolve;
  730. #endif
  731.   digestmap_entry_t search;
  732.   void *oldval;
  733.   tor_assert(map);
  734.   tor_assert(key);
  735.   tor_assert(val);
  736.   memcpy(&search.key, key, DIGEST_LEN);
  737. #ifndef OPTIMIZED_DIGESTMAP_SET
  738.   resolve = HT_FIND(digestmap_impl, &map->head, &search);
  739.   if (resolve) {
  740.     oldval = resolve->val;
  741.     resolve->val = val;
  742.     return oldval;
  743.   } else {
  744.     resolve = tor_malloc_zero(sizeof(digestmap_entry_t));
  745.     memcpy(resolve->key, key, DIGEST_LEN);
  746.     resolve->val = val;
  747.     HT_INSERT(digestmap_impl, &map->head, resolve);
  748.     return NULL;
  749.   }
  750. #else
  751.   /* We spend up to 5% of our time in this function, so the code below is
  752.    * meant to optimize the check/alloc/set cycle by avoiding the two trips to
  753.    * the hash table that we do in the unoptimized code above.  (Each of
  754.    * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.)
  755.    */
  756.   _HT_FIND_OR_INSERT(digestmap_impl, node, digestmap_entry_hash, &(map->head),
  757.          digestmap_entry_t, &search, ptr,
  758.          {
  759.             /* we found an entry. */
  760.             oldval = (*ptr)->val;
  761.             (*ptr)->val = val;
  762.             return oldval;
  763.          },
  764.          {
  765.            /* We didn't find the entry. */
  766.            digestmap_entry_t *newent =
  767.              tor_malloc_zero(sizeof(digestmap_entry_t));
  768.            memcpy(newent->key, key, DIGEST_LEN);
  769.            newent->val = val;
  770.            _HT_FOI_INSERT(node, &(map->head), &search, newent, ptr);
  771.            return NULL;
  772.          });
  773. #endif
  774. }
  775. /** Return the current value associated with <b>key</b>, or NULL if no
  776.  * value is set.
  777.  */
  778. void *
  779. strmap_get(const strmap_t *map, const char *key)
  780. {
  781.   strmap_entry_t *resolve;
  782.   strmap_entry_t search;
  783.   tor_assert(map);
  784.   tor_assert(key);
  785.   search.key = (char*)key;
  786.   resolve = HT_FIND(strmap_impl, &map->head, &search);
  787.   if (resolve) {
  788.     return resolve->val;
  789.   } else {
  790.     return NULL;
  791.   }
  792. }
  793. /** Like strmap_get() above but for digestmaps. */
  794. void *
  795. digestmap_get(const digestmap_t *map, const char *key)
  796. {
  797.   digestmap_entry_t *resolve;
  798.   digestmap_entry_t search;
  799.   tor_assert(map);
  800.   tor_assert(key);
  801.   memcpy(&search.key, key, DIGEST_LEN);
  802.   resolve = HT_FIND(digestmap_impl, &map->head, &search);
  803.   if (resolve) {
  804.     return resolve->val;
  805.   } else {
  806.     return NULL;
  807.   }
  808. }
  809. /** Remove the value currently associated with <b>key</b> from the map.
  810.  * Return the value if one was set, or NULL if there was no entry for
  811.  * <b>key</b>.
  812.  *
  813.  * Note: you must free any storage associated with the returned value.
  814.  */
  815. void *
  816. strmap_remove(strmap_t *map, const char *key)
  817. {
  818.   strmap_entry_t *resolve;
  819.   strmap_entry_t search;
  820.   void *oldval;
  821.   tor_assert(map);
  822.   tor_assert(key);
  823.   search.key = (char*)key;
  824.   resolve = HT_REMOVE(strmap_impl, &map->head, &search);
  825.   if (resolve) {
  826.     oldval = resolve->val;
  827.     tor_free(resolve->key);
  828.     tor_free(resolve);
  829.     return oldval;
  830.   } else {
  831.     return NULL;
  832.   }
  833. }
  834. /** Like strmap_remove() above but for digestmaps. */
  835. void *
  836. digestmap_remove(digestmap_t *map, const char *key)
  837. {
  838.   digestmap_entry_t *resolve;
  839.   digestmap_entry_t search;
  840.   void *oldval;
  841.   tor_assert(map);
  842.   tor_assert(key);
  843.   memcpy(&search.key, key, DIGEST_LEN);
  844.   resolve = HT_REMOVE(digestmap_impl, &map->head, &search);
  845.   if (resolve) {
  846.     oldval = resolve->val;
  847.     tor_free(resolve);
  848.     return oldval;
  849.   } else {
  850.     return NULL;
  851.   }
  852. }
  853. /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
  854. void *
  855. strmap_set_lc(strmap_t *map, const char *key, void *val)
  856. {
  857.   /* We could be a little faster by using strcasecmp instead, and a separate
  858.    * type, but I don't think it matters. */
  859.   void *v;
  860.   char *lc_key = tor_strdup(key);
  861.   tor_strlower(lc_key);
  862.   v = strmap_set(map,lc_key,val);
  863.   tor_free(lc_key);
  864.   return v;
  865. }
  866. /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
  867. void *
  868. strmap_get_lc(const strmap_t *map, const char *key)
  869. {
  870.   void *v;
  871.   char *lc_key = tor_strdup(key);
  872.   tor_strlower(lc_key);
  873.   v = strmap_get(map,lc_key);
  874.   tor_free(lc_key);
  875.   return v;
  876. }
  877. /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
  878. void *
  879. strmap_remove_lc(strmap_t *map, const char *key)
  880. {
  881.   void *v;
  882.   char *lc_key = tor_strdup(key);
  883.   tor_strlower(lc_key);
  884.   v = strmap_remove(map,lc_key);
  885.   tor_free(lc_key);
  886.   return v;
  887. }
  888. /** return an <b>iterator</b> pointer to the front of a map.
  889.  *
  890.  * Iterator example:
  891.  *
  892.  * code
  893.  * // uppercase values in "map", removing empty values.
  894.  *
  895.  * strmap_iter_t *iter;
  896.  * const char *key;
  897.  * void *val;
  898.  * char *cp;
  899.  *
  900.  * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) {
  901.  *    strmap_iter_get(iter, &key, &val);
  902.  *    cp = (char*)val;
  903.  *    if (!*cp) {
  904.  *       iter = strmap_iter_next_rmv(map,iter);
  905.  *       free(val);
  906.  *    } else {
  907.  *       for (;*cp;cp++) *cp = TOR_TOUPPER(*cp);
  908.  *       iter = strmap_iter_next(map,iter);
  909.  *    }
  910.  * }
  911.  * endcode
  912.  *
  913.  */
  914. strmap_iter_t *
  915. strmap_iter_init(strmap_t *map)
  916. {
  917.   tor_assert(map);
  918.   return HT_START(strmap_impl, &map->head);
  919. }
  920. /** Start iterating through <b>map</b>.  See strmap_iter_init() for example. */
  921. digestmap_iter_t *
  922. digestmap_iter_init(digestmap_t *map)
  923. {
  924.   tor_assert(map);
  925.   return HT_START(digestmap_impl, &map->head);
  926. }
  927. /** Advance the iterator <b>iter</b> for <b>map</b> a single step to the next
  928.  * entry, and return its new value. */
  929. strmap_iter_t *
  930. strmap_iter_next(strmap_t *map, strmap_iter_t *iter)
  931. {
  932.   tor_assert(map);
  933.   tor_assert(iter);
  934.   return HT_NEXT(strmap_impl, &map->head, iter);
  935. }
  936. /** Advance the iterator <b>iter</b> for map a single step to the next entry,
  937.  * and return its new value. */
  938. digestmap_iter_t *
  939. digestmap_iter_next(digestmap_t *map, digestmap_iter_t *iter)
  940. {
  941.   tor_assert(map);
  942.   tor_assert(iter);
  943.   return HT_NEXT(digestmap_impl, &map->head, iter);
  944. }
  945. /** Advance the iterator <b>iter</b> a single step to the next entry, removing
  946.  * the current entry, and return its new value.
  947.  */
  948. strmap_iter_t *
  949. strmap_iter_next_rmv(strmap_t *map, strmap_iter_t *iter)
  950. {
  951.   strmap_entry_t *rmv;
  952.   tor_assert(map);
  953.   tor_assert(iter);
  954.   tor_assert(*iter);
  955.   rmv = *iter;
  956.   iter = HT_NEXT_RMV(strmap_impl, &map->head, iter);
  957.   tor_free(rmv->key);
  958.   tor_free(rmv);
  959.   return iter;
  960. }
  961. /** Advance the iterator <b>iter</b> a single step to the next entry, removing
  962.  * the current entry, and return its new value.
  963.  */
  964. digestmap_iter_t *
  965. digestmap_iter_next_rmv(digestmap_t *map, digestmap_iter_t *iter)
  966. {
  967.   digestmap_entry_t *rmv;
  968.   tor_assert(map);
  969.   tor_assert(iter);
  970.   tor_assert(*iter);
  971.   rmv = *iter;
  972.   iter = HT_NEXT_RMV(digestmap_impl, &map->head, iter);
  973.   tor_free(rmv);
  974.   return iter;
  975. }
  976. /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
  977.  * iter. */
  978. void
  979. strmap_iter_get(strmap_iter_t *iter, const char **keyp, void **valp)
  980. {
  981.   tor_assert(iter);
  982.   tor_assert(*iter);
  983.   tor_assert(keyp);
  984.   tor_assert(valp);
  985.   *keyp = (*iter)->key;
  986.   *valp = (*iter)->val;
  987. }
  988. /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
  989.  * iter. */
  990. void
  991. digestmap_iter_get(digestmap_iter_t *iter, const char **keyp, void **valp)
  992. {
  993.   tor_assert(iter);
  994.   tor_assert(*iter);
  995.   tor_assert(keyp);
  996.   tor_assert(valp);
  997.   *keyp = (*iter)->key;
  998.   *valp = (*iter)->val;
  999. }
  1000. /** Return true iff <b>iter</b> has advanced past the last entry of
  1001.  * <b>map</b>. */
  1002. int
  1003. strmap_iter_done(strmap_iter_t *iter)
  1004. {
  1005.   return iter == NULL;
  1006. }
  1007. /** Return true iff <b>iter</b> has advanced past the last entry of
  1008.  * <b>map</b>. */
  1009. int
  1010. digestmap_iter_done(digestmap_iter_t *iter)
  1011. {
  1012.   return iter == NULL;
  1013. }
  1014. /** Remove all entries from <b>map</b>, and deallocate storage for those
  1015.  * entries.  If free_val is provided, it is invoked on every value in
  1016.  * <b>map</b>.
  1017.  */
  1018. void
  1019. strmap_free(strmap_t *map, void (*free_val)(void*))
  1020. {
  1021.   strmap_entry_t **ent, **next, *this;
  1022.   for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) {
  1023.     this = *ent;
  1024.     next = HT_NEXT_RMV(strmap_impl, &map->head, ent);
  1025.     tor_free(this->key);
  1026.     if (free_val)
  1027.       free_val(this->val);
  1028.     tor_free(this);
  1029.   }
  1030.   tor_assert(HT_EMPTY(&map->head));
  1031.   HT_CLEAR(strmap_impl, &map->head);
  1032.   tor_free(map);
  1033. }
  1034. /** Remove all entries from <b>map</b>, and deallocate storage for those
  1035.  * entries.  If free_val is provided, it is invoked on every value in
  1036.  * <b>map</b>.
  1037.  */
  1038. void
  1039. digestmap_free(digestmap_t *map, void (*free_val)(void*))
  1040. {
  1041.   digestmap_entry_t **ent, **next, *this;
  1042.   for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) {
  1043.     this = *ent;
  1044.     next = HT_NEXT_RMV(digestmap_impl, &map->head, ent);
  1045.     if (free_val)
  1046.       free_val(this->val);
  1047.     tor_free(this);
  1048.   }
  1049.   tor_assert(HT_EMPTY(&map->head));
  1050.   HT_CLEAR(digestmap_impl, &map->head);
  1051.   tor_free(map);
  1052. }
  1053. /** Fail with an assertion error if anything has gone wrong with the internal
  1054.  * representation of <b>map</b>. */
  1055. void
  1056. strmap_assert_ok(const strmap_t *map)
  1057. {
  1058.   tor_assert(!_strmap_impl_HT_REP_IS_BAD(&map->head));
  1059. }
  1060. /** Fail with an assertion error if anything has gone wrong with the internal
  1061.  * representation of <b>map</b>. */
  1062. void
  1063. digestmap_assert_ok(const digestmap_t *map)
  1064. {
  1065.   tor_assert(!_digestmap_impl_HT_REP_IS_BAD(&map->head));
  1066. }
  1067. /** Return true iff <b>map</b> has no entries. */
  1068. int
  1069. strmap_isempty(const strmap_t *map)
  1070. {
  1071.   return HT_EMPTY(&map->head);
  1072. }
  1073. /** Return true iff <b>map</b> has no entries. */
  1074. int
  1075. digestmap_isempty(const digestmap_t *map)
  1076. {
  1077.   return HT_EMPTY(&map->head);
  1078. }
  1079. /** Return the number of items in <b>map</b>. */
  1080. int
  1081. strmap_size(const strmap_t *map)
  1082. {
  1083.   return HT_SIZE(&map->head);
  1084. }
  1085. /** Return the number of items in <b>map</b>. */
  1086. int
  1087. digestmap_size(const digestmap_t *map)
  1088. {
  1089.   return HT_SIZE(&map->head);
  1090. }
  1091. /** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
  1092.  * function for an array of type <b>elt_t</b>*.
  1093.  *
  1094.  * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding
  1095.  * the kth element of an n-element list can be done in O(n).  Then again, this
  1096.  * implementation is not in critical path, and it is obviously correct. */
  1097. #define IMPLEMENT_ORDER_FUNC(funcname, elt_t)                   
  1098.   static int                                                    
  1099.   _cmp_ ## elt_t(const void *_a, const void *_b)                
  1100.   {                                                             
  1101.     const elt_t *a = _a, *b = _b;                               
  1102.     if (*a<*b)                                                  
  1103.       return -1;                                                
  1104.     else if (*a>*b)                                             
  1105.       return 1;                                                 
  1106.     else                                                        
  1107.       return 0;                                                 
  1108.   }                                                             
  1109.   elt_t                                                         
  1110.   funcname(elt_t *array, int n_elements, int nth)               
  1111.   {                                                             
  1112.     tor_assert(nth >= 0);                                       
  1113.     tor_assert(nth < n_elements);                               
  1114.     qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t);     
  1115.     return array[nth];                                          
  1116.   }
  1117. IMPLEMENT_ORDER_FUNC(find_nth_int, int)
  1118. IMPLEMENT_ORDER_FUNC(find_nth_time, time_t)
  1119. IMPLEMENT_ORDER_FUNC(find_nth_double, double)
  1120. IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t)
  1121. IMPLEMENT_ORDER_FUNC(find_nth_long, long)
  1122. /** Return a newly allocated digestset_t, optimized to hold a total of
  1123.  * <b>max_elements</b> digests with a reasonably low false positive weight. */
  1124. digestset_t *
  1125. digestset_new(int max_elements)
  1126. {
  1127.   /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
  1128.    * is the number of hash functions per entry, m is the bits in the array,
  1129.    * and n is the number of elements inserted.  For us, k==4, n<=max_elements,
  1130.    * and m==n_bits= approximately max_elements*32.  This gives
  1131.    *   P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
  1132.    *
  1133.    * It would be more optimal in space vs false positives to get this false
  1134.    * positive rate by going for k==13, and m==18.5n, but we also want to
  1135.    * conserve CPU, and k==13 is pretty big.
  1136.    */
  1137.   int n_bits = 1u << (tor_log2(max_elements)+5);
  1138.   digestset_t *r = tor_malloc(sizeof(digestset_t));
  1139.   r->mask = n_bits - 1;
  1140.   r->ba = bitarray_init_zero(n_bits);
  1141.   return r;
  1142. }
  1143. /** Free all storage held in <b>set</b>. */
  1144. void
  1145. digestset_free(digestset_t *set)
  1146. {
  1147.   bitarray_free(set->ba);
  1148.   tor_free(set);
  1149. }