1 /* Copyright (c) 2003-2004, Roger Dingledine
2 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 * Copyright (c) 2007-2013, The Tor Project, Inc. */
4 /* See LICENSE for licensing information */
8 * \brief Implements a smartlist (a resizable array) along
9 * with helper functions to use smartlists. Also includes
10 * hash table implementations of a string-to-void* map, and of
11 * a digest-to-void* map.
17 #include "container.h"
26 /** All newly allocated smartlists have this capacity. */
27 #define SMARTLIST_DEFAULT_CAPACITY 16
29 /** Allocate and return an empty smartlist.
34 smartlist_t
*sl
= tor_malloc(sizeof(smartlist_t
));
36 sl
->capacity
= SMARTLIST_DEFAULT_CAPACITY
;
37 sl
->list
= tor_malloc(sizeof(void *) * sl
->capacity
);
41 /** Deallocate a smartlist. Does not release storage associated with the
45 smartlist_free(smartlist_t
*sl
)
53 /** Remove all elements from the list.
56 smartlist_clear(smartlist_t
*sl
)
61 #if SIZE_MAX < INT_MAX
62 #error "We don't support systems where size_t is smaller than int."
65 /** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
67 smartlist_ensure_capacity(smartlist_t
*sl
, size_t size
)
69 /* Set MAX_CAPACITY to MIN(INT_MAX, SIZE_MAX / sizeof(void*)) */
70 #if (SIZE_MAX/SIZEOF_VOID_P) > INT_MAX
71 #define MAX_CAPACITY (INT_MAX)
73 #define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*))))
75 tor_assert(size
<= MAX_CAPACITY
);
77 if (size
> (size_t) sl
->capacity
) {
78 size_t higher
= (size_t) sl
->capacity
;
79 if (PREDICT_UNLIKELY(size
> MAX_CAPACITY
/2)) {
80 tor_assert(size
<= MAX_CAPACITY
);
81 higher
= MAX_CAPACITY
;
86 tor_assert(higher
<= INT_MAX
); /* Redundant */
87 sl
->capacity
= (int) higher
;
88 sl
->list
= tor_realloc(sl
->list
, sizeof(void*)*((size_t)sl
->capacity
));
92 /** Append element to the end of the list. */
94 smartlist_add(smartlist_t
*sl
, void *element
)
96 smartlist_ensure_capacity(sl
, ((size_t) sl
->num_used
)+1);
97 sl
->list
[sl
->num_used
++] = element
;
100 /** Append each element from S2 to the end of S1. */
102 smartlist_add_all(smartlist_t
*s1
, const smartlist_t
*s2
)
104 size_t new_size
= (size_t)s1
->num_used
+ (size_t)s2
->num_used
;
105 tor_assert(new_size
>= (size_t) s1
->num_used
); /* check for overflow. */
106 smartlist_ensure_capacity(s1
, new_size
);
107 memcpy(s1
->list
+ s1
->num_used
, s2
->list
, s2
->num_used
*sizeof(void*));
108 tor_assert(new_size
<= INT_MAX
); /* redundant. */
109 s1
->num_used
= (int) new_size
;
112 /** Remove all elements E from sl such that E==element. Preserve
113 * the order of any elements before E, but elements after E can be
117 smartlist_remove(smartlist_t
*sl
, const void *element
)
122 for (i
=0; i
< sl
->num_used
; i
++)
123 if (sl
->list
[i
] == element
) {
124 sl
->list
[i
] = sl
->list
[--sl
->num_used
]; /* swap with the end */
125 i
--; /* so we process the new i'th element */
129 /** If <b>sl</b> is nonempty, remove and return the final element. Otherwise,
132 smartlist_pop_last(smartlist_t
*sl
)
136 return sl
->list
[--sl
->num_used
];
141 /** Reverse the order of the items in <b>sl</b>. */
143 smartlist_reverse(smartlist_t
*sl
)
148 for (i
= 0, j
= sl
->num_used
-1; i
< j
; ++i
, --j
) {
150 sl
->list
[i
] = sl
->list
[j
];
155 /** If there are any strings in sl equal to element, remove and free them.
156 * Does not preserve order. */
158 smartlist_string_remove(smartlist_t
*sl
, const char *element
)
163 for (i
= 0; i
< sl
->num_used
; ++i
) {
164 if (!strcmp(element
, sl
->list
[i
])) {
165 tor_free(sl
->list
[i
]);
166 sl
->list
[i
] = sl
->list
[--sl
->num_used
]; /* swap with the end */
167 i
--; /* so we process the new i'th element */
172 /** Return true iff some element E of sl has E==element.
175 smartlist_contains(const smartlist_t
*sl
, const void *element
)
178 for (i
=0; i
< sl
->num_used
; i
++)
179 if (sl
->list
[i
] == element
)
184 /** Return true iff <b>sl</b> has some element E such that
185 * !strcmp(E,<b>element</b>)
188 smartlist_contains_string(const smartlist_t
*sl
, const char *element
)
192 for (i
=0; i
< sl
->num_used
; i
++)
193 if (strcmp((const char*)sl
->list
[i
],element
)==0)
198 /** If <b>element</b> is equal to an element of <b>sl</b>, return that
199 * element's index. Otherwise, return -1. */
201 smartlist_string_pos(const smartlist_t
*sl
, const char *element
)
205 for (i
=0; i
< sl
->num_used
; i
++)
206 if (strcmp((const char*)sl
->list
[i
],element
)==0)
211 /** Return true iff <b>sl</b> has some element E such that
212 * !strcasecmp(E,<b>element</b>)
215 smartlist_contains_string_case(const smartlist_t
*sl
, const char *element
)
219 for (i
=0; i
< sl
->num_used
; i
++)
220 if (strcasecmp((const char*)sl
->list
[i
],element
)==0)
225 /** Return true iff <b>sl</b> has some element E such that E is equal
226 * to the decimal encoding of <b>num</b>.
229 smartlist_contains_int_as_string(const smartlist_t
*sl
, int num
)
231 char buf
[32]; /* long enough for 64-bit int, and then some. */
232 tor_snprintf(buf
,sizeof(buf
),"%d", num
);
233 return smartlist_contains_string(sl
, buf
);
236 /** Return true iff the two lists contain the same strings in the same
237 * order, or if they are both NULL. */
239 smartlist_strings_eq(const smartlist_t
*sl1
, const smartlist_t
*sl2
)
245 if (smartlist_len(sl1
) != smartlist_len(sl2
))
247 SMARTLIST_FOREACH(sl1
, const char *, cp1
, {
248 const char *cp2
= smartlist_get(sl2
, cp1_sl_idx
);
249 if (strcmp(cp1
, cp2
))
255 /** Return true iff <b>sl</b> has some element E such that
256 * tor_memeq(E,<b>element</b>,DIGEST_LEN)
259 smartlist_contains_digest(const smartlist_t
*sl
, const char *element
)
263 for (i
=0; i
< sl
->num_used
; i
++)
264 if (tor_memeq((const char*)sl
->list
[i
],element
,DIGEST_LEN
))
269 /** Return true iff some element E of sl2 has smartlist_contains(sl1,E).
272 smartlist_overlap(const smartlist_t
*sl1
, const smartlist_t
*sl2
)
275 for (i
=0; i
< sl2
->num_used
; i
++)
276 if (smartlist_contains(sl1
, sl2
->list
[i
]))
281 /** Remove every element E of sl1 such that !smartlist_contains(sl2,E).
282 * Does not preserve the order of sl1.
285 smartlist_intersect(smartlist_t
*sl1
, const smartlist_t
*sl2
)
288 for (i
=0; i
< sl1
->num_used
; i
++)
289 if (!smartlist_contains(sl2
, sl1
->list
[i
])) {
290 sl1
->list
[i
] = sl1
->list
[--sl1
->num_used
]; /* swap with the end */
291 i
--; /* so we process the new i'th element */
295 /** Remove every element E of sl1 such that smartlist_contains(sl2,E).
296 * Does not preserve the order of sl1.
299 smartlist_subtract(smartlist_t
*sl1
, const smartlist_t
*sl2
)
302 for (i
=0; i
< sl2
->num_used
; i
++)
303 smartlist_remove(sl1
, sl2
->list
[i
]);
306 /** Remove the <b>idx</b>th element of sl; if idx is not the last
307 * element, swap the last element of sl into the <b>idx</b>th space.
310 smartlist_del(smartlist_t
*sl
, int idx
)
314 tor_assert(idx
< sl
->num_used
);
315 sl
->list
[idx
] = sl
->list
[--sl
->num_used
];
318 /** Remove the <b>idx</b>th element of sl; if idx is not the last element,
319 * moving all subsequent elements back one space. Return the old value
320 * of the <b>idx</b>th element.
323 smartlist_del_keeporder(smartlist_t
*sl
, int idx
)
327 tor_assert(idx
< sl
->num_used
);
329 if (idx
< sl
->num_used
)
330 memmove(sl
->list
+idx
, sl
->list
+idx
+1, sizeof(void*)*(sl
->num_used
-idx
));
333 /** Insert the value <b>val</b> as the new <b>idx</b>th element of
334 * <b>sl</b>, moving all items previously at <b>idx</b> or later
338 smartlist_insert(smartlist_t
*sl
, int idx
, void *val
)
342 tor_assert(idx
<= sl
->num_used
);
343 if (idx
== sl
->num_used
) {
344 smartlist_add(sl
, val
);
346 smartlist_ensure_capacity(sl
, ((size_t) sl
->num_used
)+1);
347 /* Move other elements away */
348 if (idx
< sl
->num_used
)
349 memmove(sl
->list
+ idx
+ 1, sl
->list
+ idx
,
350 sizeof(void*)*(sl
->num_used
-idx
));
357 * Split a string <b>str</b> along all occurrences of <b>sep</b>,
358 * appending the (newly allocated) split strings, in order, to
359 * <b>sl</b>. Return the number of strings added to <b>sl</b>.
361 * If <b>flags</b>&SPLIT_SKIP_SPACE is true, remove initial and
362 * trailing space from each entry.
363 * If <b>flags</b>&SPLIT_IGNORE_BLANK is true, remove any entries
365 * If <b>flags</b>&SPLIT_STRIP_SPACE is true, strip spaces from each
368 * If <b>max</b>\>0, divide the string into no more than <b>max</b> pieces. If
369 * <b>sep</b> is NULL, split on any sequence of horizontal space.
372 smartlist_split_string(smartlist_t
*sl
, const char *str
, const char *sep
,
375 const char *cp
, *end
, *next
;
383 if (flags
&SPLIT_SKIP_SPACE
) {
384 while (TOR_ISSPACE(*cp
)) ++cp
;
387 if (max
>0 && n
== max
-1) {
388 end
= strchr(cp
,'\0');
390 end
= strstr(cp
,sep
);
392 end
= strchr(cp
,'\0');
394 for (end
= cp
; *end
&& *end
!= '\t' && *end
!= ' '; ++end
)
403 next
= end
+strlen(sep
);
406 while (*next
== '\t' || *next
== ' ')
410 if (flags
&SPLIT_SKIP_SPACE
) {
411 while (end
> cp
&& TOR_ISSPACE(*(end
-1)))
414 if (end
!= cp
|| !(flags
&SPLIT_IGNORE_BLANK
)) {
415 char *string
= tor_strndup(cp
, end
-cp
);
416 if (flags
&SPLIT_STRIP_SPACE
)
417 tor_strstrip(string
, " ");
418 smartlist_add(sl
, string
);
429 /** Allocate and return a new string containing the concatenation of
430 * the elements of <b>sl</b>, in order, separated by <b>join</b>. If
431 * <b>terminate</b> is true, also terminate the string with <b>join</b>.
432 * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
433 * the returned string. Requires that every element of <b>sl</b> is
434 * NUL-terminated string.
437 smartlist_join_strings(smartlist_t
*sl
, const char *join
,
438 int terminate
, size_t *len_out
)
440 return smartlist_join_strings2(sl
,join
,strlen(join
),terminate
,len_out
);
443 /** As smartlist_join_strings, but instead of separating/terminated with a
444 * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
445 * at <b>join</b>. (Useful for generating a sequence of NUL-terminated
449 smartlist_join_strings2(smartlist_t
*sl
, const char *join
,
450 size_t join_len
, int terminate
, size_t *len_out
)
454 char *r
= NULL
, *dst
, *src
;
462 for (i
= 0; i
< sl
->num_used
; ++i
) {
463 n
+= strlen(sl
->list
[i
]);
464 if (i
+1 < sl
->num_used
) /* avoid double-counting the last one */
467 dst
= r
= tor_malloc(n
+1);
468 for (i
= 0; i
< sl
->num_used
; ) {
469 for (src
= sl
->list
[i
]; *src
; )
471 if (++i
< sl
->num_used
) {
472 memcpy(dst
, join
, join_len
);
477 memcpy(dst
, join
, join_len
);
487 /** Sort the members of <b>sl</b> into an order defined by
488 * the ordering function <b>compare</b>, which returns less then 0 if a
489 * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
492 smartlist_sort(smartlist_t
*sl
, int (*compare
)(const void **a
, const void **b
))
496 qsort(sl
->list
, sl
->num_used
, sizeof(void*),
497 (int (*)(const void *,const void*))compare
);
500 /** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
501 * return the most frequent member in the list. Break ties in favor of
502 * later elements. If the list is empty, return NULL.
505 smartlist_get_most_frequent(const smartlist_t
*sl
,
506 int (*compare
)(const void **a
, const void **b
))
508 const void *most_frequent
= NULL
;
509 int most_frequent_count
= 0;
511 const void *cur
= NULL
;
516 for (i
= 0; i
< sl
->num_used
; ++i
) {
517 const void *item
= sl
->list
[i
];
518 if (cur
&& 0 == compare(&cur
, &item
)) {
521 if (cur
&& count
>= most_frequent_count
) {
523 most_frequent_count
= count
;
529 if (cur
&& count
>= most_frequent_count
) {
531 most_frequent_count
= count
;
533 return (void*)most_frequent
;
536 /** Given a sorted smartlist <b>sl</b> and the comparison function used to
537 * sort it, remove all duplicate members. If free_fn is provided, calls
538 * free_fn on each duplicate. Otherwise, just removes them. Preserves order.
541 smartlist_uniq(smartlist_t
*sl
,
542 int (*compare
)(const void **a
, const void **b
),
543 void (*free_fn
)(void *a
))
546 for (i
=1; i
< sl
->num_used
; ++i
) {
547 if (compare((const void **)&(sl
->list
[i
-1]),
548 (const void **)&(sl
->list
[i
])) == 0) {
550 free_fn(sl
->list
[i
]);
551 smartlist_del_keeporder(sl
, i
--);
556 /** Assuming the members of <b>sl</b> are in order, return a pointer to the
557 * member that matches <b>key</b>. Ordering and matching are defined by a
558 * <b>compare</b> function that returns 0 on a match; less than 0 if key is
559 * less than member, and greater than 0 if key is greater then member.
562 smartlist_bsearch(smartlist_t
*sl
, const void *key
,
563 int (*compare
)(const void *key
, const void **member
))
566 idx
= smartlist_bsearch_idx(sl
, key
, compare
, &found
);
567 return found
? smartlist_get(sl
, idx
) : NULL
;
570 /** Assuming the members of <b>sl</b> are in order, return the index of the
571 * member that matches <b>key</b>. If no member matches, return the index of
572 * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
573 * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to
574 * false otherwise. Ordering and matching are defined by a <b>compare</b>
575 * function that returns 0 on a match; less than 0 if key is less than member,
576 * and greater than 0 if key is greater then member.
579 smartlist_bsearch_idx(const smartlist_t
*sl
, const void *key
,
580 int (*compare
)(const void *key
, const void **member
),
583 int hi
, lo
, cmp
, mid
, len
, diff
;
587 tor_assert(found_out
);
589 len
= smartlist_len(sl
);
591 /* Check for the trivial case of a zero-length list */
594 /* We already know smartlist_len(sl) is 0 in this case */
598 /* Okay, we have a real search to do */
604 * These invariants are always true:
606 * For all i such that 0 <= i < lo, sl[i] < key
607 * For all i such that hi < i <= len, sl[i] > key
613 * We want mid = (lo + hi) / 2, but that could lead to overflow, so
614 * instead diff = hi - lo (non-negative because of loop condition), and
615 * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2).
617 mid
= lo
+ (diff
/ 2);
618 cmp
= compare(key
, (const void**) &(sl
->list
[mid
]));
620 /* sl[mid] == key; we found it */
623 } else if (cmp
> 0) {
625 * key > sl[mid] and an index i such that sl[i] == key must
626 * have i > mid if it exists.
630 * Since lo <= mid <= hi, hi can only decrease on each iteration (by
631 * being set to mid - 1) and hi is initially len - 1, mid < len should
632 * always hold, and this is not symmetric with the left end of list
633 * mid > 0 test below. A key greater than the right end of the list
634 * should eventually lead to lo == hi == mid == len - 1, and then
635 * we set lo to len below and fall out to the same exit we hit for
636 * a key in the middle of the list but not matching. Thus, we just
637 * assert for consistency here rather than handle a mid == len case.
639 tor_assert(mid
< len
);
640 /* Move lo to the element immediately after sl[mid] */
643 /* This should always be true in this case */
647 * key < sl[mid] and an index i such that sl[i] == key must
648 * have i < mid if it exists.
652 /* Normal case, move hi to the element immediately before sl[mid] */
655 /* These should always be true in this case */
656 tor_assert(mid
== lo
);
657 tor_assert(mid
== 0);
659 * We were at the beginning of the list and concluded that every
660 * element e compares e > key.
669 * lo > hi; we have no element matching key but we have elements falling
670 * on both sides of it. The lo index points to the first element > key.
672 tor_assert(lo
== hi
+ 1); /* All other cases should have been handled */
674 tor_assert(lo
<= len
);
676 tor_assert(hi
<= len
);
679 cmp
= compare(key
, (const void **) &(sl
->list
[lo
]));
682 cmp
= compare(key
, (const void **) &(sl
->list
[len
-1]));
690 /** Helper: compare two const char **s. */
692 compare_string_ptrs_(const void **_a
, const void **_b
)
694 return strcmp((const char*)*_a
, (const char*)*_b
);
697 /** Sort a smartlist <b>sl</b> containing strings into lexically ascending
700 smartlist_sort_strings(smartlist_t
*sl
)
702 smartlist_sort(sl
, compare_string_ptrs_
);
705 /** Return the most frequent string in the sorted list <b>sl</b> */
707 smartlist_get_most_frequent_string(smartlist_t
*sl
)
709 return smartlist_get_most_frequent(sl
, compare_string_ptrs_
);
712 /** Remove duplicate strings from a sorted list, and free them with tor_free().
715 smartlist_uniq_strings(smartlist_t
*sl
)
717 smartlist_uniq(sl
, compare_string_ptrs_
, tor_free_
);
720 /* Heap-based priority queue implementation for O(lg N) insert and remove.
721 * Recall that the heap property is that, for every index I, h[I] <
722 * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
724 * For us to remove items other than the topmost item, each item must store
725 * its own index within the heap. When calling the pqueue functions, tell
726 * them about the offset of the field that stores the index within the item.
730 * typedef struct timer_t {
735 * static int compare(const void *p1, const void *p2) {
736 * const timer_t *t1 = p1, *t2 = p2;
737 * if (t1->tv.tv_sec < t2->tv.tv_sec) {
739 * } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
742 * return t1->tv.tv_usec - t2->tv_usec;
746 * void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
747 * smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index),
751 * void timer_heap_pop(smartlist_t *heap) {
752 * return smartlist_pqueue_pop(heap, compare,
753 * STRUCT_OFFSET(timer_t, heap_index));
758 /** Functions to manipulate heap indices to find a node's parent and children.
760 * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
761 * = 2*x + 1. But this is C, so we have to adjust a little. */
762 //#define LEFT_CHILD(i) ( ((i)+1)*2 - 1)
763 //#define RIGHT_CHILD(i) ( ((i)+1)*2 )
764 //#define PARENT(i) ( ((i)+1)/2 - 1)
765 #define LEFT_CHILD(i) ( 2*(i) + 1 )
766 #define RIGHT_CHILD(i) ( 2*(i) + 2 )
767 #define PARENT(i) ( ((i)-1) / 2 )
771 /** Helper macros for heaps: Given a local variable <b>idx_field_offset</b>
772 * set to the offset of an integer index within the heap element structure,
773 * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to
774 * where p's index is stored. Given additionally a local smartlist <b>sl</b>,
775 * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct
776 * value (that is, to <b>i</b>).
778 #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
780 #define UPDATE_IDX(i) do { \
781 void *updated = sl->list[i]; \
782 *IDXP(updated) = i; \
785 #define IDX_OF_ITEM(p) (*IDXP(p))
788 /** Helper. <b>sl</b> may have at most one violation of the heap property:
789 * the item at <b>idx</b> may be greater than one or both of its children.
790 * Restore the heap property. */
792 smartlist_heapify(smartlist_t
*sl
,
793 int (*compare
)(const void *a
, const void *b
),
794 int idx_field_offset
,
798 int left_idx
= LEFT_CHILD(idx
);
801 if (left_idx
>= sl
->num_used
)
803 if (compare(sl
->list
[idx
],sl
->list
[left_idx
]) < 0)
807 if (left_idx
+1 < sl
->num_used
&&
808 compare(sl
->list
[left_idx
+1],sl
->list
[best_idx
]) < 0)
809 best_idx
= left_idx
+ 1;
811 if (best_idx
== idx
) {
814 void *tmp
= sl
->list
[idx
];
815 sl
->list
[idx
] = sl
->list
[best_idx
];
816 sl
->list
[best_idx
] = tmp
;
818 UPDATE_IDX(best_idx
);
825 /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
826 * determined by <b>compare</b> and the offset of the item in the heap is
827 * stored in an int-typed field at position <b>idx_field_offset</b> within
831 smartlist_pqueue_add(smartlist_t
*sl
,
832 int (*compare
)(const void *a
, const void *b
),
833 int idx_field_offset
,
837 smartlist_add(sl
,item
);
838 UPDATE_IDX(sl
->num_used
-1);
840 for (idx
= sl
->num_used
- 1; idx
; ) {
841 int parent
= PARENT(idx
);
842 if (compare(sl
->list
[idx
], sl
->list
[parent
]) < 0) {
843 void *tmp
= sl
->list
[parent
];
844 sl
->list
[parent
] = sl
->list
[idx
];
855 /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
856 * where order is determined by <b>compare</b> and the item's position is
857 * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
860 smartlist_pqueue_pop(smartlist_t
*sl
,
861 int (*compare
)(const void *a
, const void *b
),
862 int idx_field_offset
)
865 tor_assert(sl
->num_used
);
869 if (--sl
->num_used
) {
870 sl
->list
[0] = sl
->list
[sl
->num_used
];
872 smartlist_heapify(sl
, compare
, idx_field_offset
, 0);
877 /** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
878 * where order is determined by <b>compare</b> and the item's position is
879 * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
882 smartlist_pqueue_remove(smartlist_t
*sl
,
883 int (*compare
)(const void *a
, const void *b
),
884 int idx_field_offset
,
887 int idx
= IDX_OF_ITEM(item
);
888 tor_assert(idx
>= 0);
889 tor_assert(sl
->list
[idx
] == item
);
892 if (idx
== sl
->num_used
) {
895 sl
->list
[idx
] = sl
->list
[sl
->num_used
];
897 smartlist_heapify(sl
, compare
, idx_field_offset
, idx
);
901 /** Assert that the heap property is correctly maintained by the heap stored
902 * in <b>sl</b>, where order is determined by <b>compare</b>. */
904 smartlist_pqueue_assert_ok(smartlist_t
*sl
,
905 int (*compare
)(const void *a
, const void *b
),
906 int idx_field_offset
)
909 for (i
= sl
->num_used
- 1; i
>= 0; --i
) {
911 tor_assert(compare(sl
->list
[PARENT(i
)], sl
->list
[i
]) <= 0);
912 tor_assert(IDX_OF_ITEM(sl
->list
[i
]) == i
);
916 /** Helper: compare two DIGEST_LEN digests. */
918 compare_digests_(const void **_a
, const void **_b
)
920 return tor_memcmp((const char*)*_a
, (const char*)*_b
, DIGEST_LEN
);
923 /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
925 smartlist_sort_digests(smartlist_t
*sl
)
927 smartlist_sort(sl
, compare_digests_
);
930 /** Remove duplicate digests from a sorted list, and free them with tor_free().
933 smartlist_uniq_digests(smartlist_t
*sl
)
935 smartlist_uniq(sl
, compare_digests_
, tor_free_
);
938 /** Helper: compare two DIGEST256_LEN digests. */
940 compare_digests256_(const void **_a
, const void **_b
)
942 return tor_memcmp((const char*)*_a
, (const char*)*_b
, DIGEST256_LEN
);
945 /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
947 smartlist_sort_digests256(smartlist_t
*sl
)
949 smartlist_sort(sl
, compare_digests256_
);
952 /** Return the most frequent member of the sorted list of DIGEST256_LEN
953 * digests in <b>sl</b> */
955 smartlist_get_most_frequent_digest256(smartlist_t
*sl
)
957 return smartlist_get_most_frequent(sl
, compare_digests256_
);
960 /** Remove duplicate 256-bit digests from a sorted list, and free them with
964 smartlist_uniq_digests256(smartlist_t
*sl
)
966 smartlist_uniq(sl
, compare_digests256_
, tor_free_
);
969 /** Helper: Declare an entry type and a map type to implement a mapping using
970 * ht.h. The map type will be called <b>maptype</b>. The key part of each
971 * entry is declared using the C declaration <b>keydecl</b>. All functions
972 * and types associated with the map get prefixed with <b>prefix</b> */
973 #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \
974 typedef struct prefix ## entry_t { \
975 HT_ENTRY(prefix ## entry_t) node; \
978 } prefix ## entry_t; \
980 HT_HEAD(prefix ## impl, prefix ## entry_t) head; \
983 DEFINE_MAP_STRUCTS(strmap_t
, char *key
, strmap_
);
984 DEFINE_MAP_STRUCTS(digestmap_t
, char key
[DIGEST_LEN
], digestmap_
);
986 /** Helper: compare strmap_entry_t objects by key value. */
988 strmap_entries_eq(const strmap_entry_t
*a
, const strmap_entry_t
*b
)
990 return !strcmp(a
->key
, b
->key
);
993 /** Helper: return a hash value for a strmap_entry_t. */
994 static INLINE
unsigned int
995 strmap_entry_hash(const strmap_entry_t
*a
)
997 return ht_string_hash(a
->key
);
1000 /** Helper: compare digestmap_entry_t objects by key value. */
1002 digestmap_entries_eq(const digestmap_entry_t
*a
, const digestmap_entry_t
*b
)
1004 return tor_memeq(a
->key
, b
->key
, DIGEST_LEN
);
1007 /** Helper: return a hash value for a digest_map_t. */
1008 static INLINE
unsigned int
1009 digestmap_entry_hash(const digestmap_entry_t
*a
)
1012 const uint32_t *p
= (const uint32_t*)a
->key
;
1013 return p
[0] ^ p
[1] ^ p
[2] ^ p
[3] ^ p
[4];
1015 const uint64_t *p
= (const uint64_t*)a
->key
;
1020 HT_PROTOTYPE(strmap_impl
, strmap_entry_t
, node
, strmap_entry_hash
,
1022 HT_GENERATE(strmap_impl
, strmap_entry_t
, node
, strmap_entry_hash
,
1023 strmap_entries_eq
, 0.6, malloc
, realloc
, free
)
1025 HT_PROTOTYPE(digestmap_impl
, digestmap_entry_t
, node
, digestmap_entry_hash
,
1026 digestmap_entries_eq
)
1027 HT_GENERATE(digestmap_impl
, digestmap_entry_t
, node
, digestmap_entry_hash
,
1028 digestmap_entries_eq
, 0.6, malloc
, realloc
, free
)
1030 /** Constructor to create a new empty map from strings to void*'s.
1036 result
= tor_malloc(sizeof(strmap_t
));
1037 HT_INIT(strmap_impl
, &result
->head
);
1041 /** Constructor to create a new empty map from digests to void*'s.
1046 digestmap_t
*result
;
1047 result
= tor_malloc(sizeof(digestmap_t
));
1048 HT_INIT(digestmap_impl
, &result
->head
);
1052 /** Set the current value for <b>key</b> to <b>val</b>. Returns the previous
1053 * value for <b>key</b> if one was set, or NULL if one was not.
1055 * This function makes a copy of <b>key</b> if necessary, but not of
1059 strmap_set(strmap_t
*map
, const char *key
, void *val
)
1061 strmap_entry_t
*resolve
;
1062 strmap_entry_t search
;
1067 search
.key
= (char*)key
;
1068 resolve
= HT_FIND(strmap_impl
, &map
->head
, &search
);
1070 oldval
= resolve
->val
;
1074 resolve
= tor_malloc_zero(sizeof(strmap_entry_t
));
1075 resolve
->key
= tor_strdup(key
);
1077 tor_assert(!HT_FIND(strmap_impl
, &map
->head
, resolve
));
1078 HT_INSERT(strmap_impl
, &map
->head
, resolve
);
1083 #define OPTIMIZED_DIGESTMAP_SET
1085 /** Like strmap_set() above but for digestmaps. */
1087 digestmap_set(digestmap_t
*map
, const char *key
, void *val
)
1089 #ifndef OPTIMIZED_DIGESTMAP_SET
1090 digestmap_entry_t
*resolve
;
1092 digestmap_entry_t search
;
1097 memcpy(&search
.key
, key
, DIGEST_LEN
);
1098 #ifndef OPTIMIZED_DIGESTMAP_SET
1099 resolve
= HT_FIND(digestmap_impl
, &map
->head
, &search
);
1101 oldval
= resolve
->val
;
1105 resolve
= tor_malloc_zero(sizeof(digestmap_entry_t
));
1106 memcpy(resolve
->key
, key
, DIGEST_LEN
);
1108 HT_INSERT(digestmap_impl
, &map
->head
, resolve
);
1112 /* We spend up to 5% of our time in this function, so the code below is
1113 * meant to optimize the check/alloc/set cycle by avoiding the two trips to
1114 * the hash table that we do in the unoptimized code above. (Each of
1115 * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.)
1117 HT_FIND_OR_INSERT_(digestmap_impl
, node
, digestmap_entry_hash
, &(map
->head
),
1118 digestmap_entry_t
, &search
, ptr
,
1120 /* we found an entry. */
1121 oldval
= (*ptr
)->val
;
1126 /* We didn't find the entry. */
1127 digestmap_entry_t
*newent
=
1128 tor_malloc_zero(sizeof(digestmap_entry_t
));
1129 memcpy(newent
->key
, key
, DIGEST_LEN
);
1131 HT_FOI_INSERT_(node
, &(map
->head
), &search
, newent
, ptr
);
1137 /** Return the current value associated with <b>key</b>, or NULL if no
1141 strmap_get(const strmap_t
*map
, const char *key
)
1143 strmap_entry_t
*resolve
;
1144 strmap_entry_t search
;
1147 search
.key
= (char*)key
;
1148 resolve
= HT_FIND(strmap_impl
, &map
->head
, &search
);
1150 return resolve
->val
;
1156 /** Like strmap_get() above but for digestmaps. */
1158 digestmap_get(const digestmap_t
*map
, const char *key
)
1160 digestmap_entry_t
*resolve
;
1161 digestmap_entry_t search
;
1164 memcpy(&search
.key
, key
, DIGEST_LEN
);
1165 resolve
= HT_FIND(digestmap_impl
, &map
->head
, &search
);
1167 return resolve
->val
;
1173 /** Remove the value currently associated with <b>key</b> from the map.
1174 * Return the value if one was set, or NULL if there was no entry for
1177 * Note: you must free any storage associated with the returned value.
1180 strmap_remove(strmap_t
*map
, const char *key
)
1182 strmap_entry_t
*resolve
;
1183 strmap_entry_t search
;
1187 search
.key
= (char*)key
;
1188 resolve
= HT_REMOVE(strmap_impl
, &map
->head
, &search
);
1190 oldval
= resolve
->val
;
1191 tor_free(resolve
->key
);
1199 /** Like strmap_remove() above but for digestmaps. */
1201 digestmap_remove(digestmap_t
*map
, const char *key
)
1203 digestmap_entry_t
*resolve
;
1204 digestmap_entry_t search
;
1208 memcpy(&search
.key
, key
, DIGEST_LEN
);
1209 resolve
= HT_REMOVE(digestmap_impl
, &map
->head
, &search
);
1211 oldval
= resolve
->val
;
1219 /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
1221 strmap_set_lc(strmap_t
*map
, const char *key
, void *val
)
1223 /* We could be a little faster by using strcasecmp instead, and a separate
1224 * type, but I don't think it matters. */
1226 char *lc_key
= tor_strdup(key
);
1227 tor_strlower(lc_key
);
1228 v
= strmap_set(map
,lc_key
,val
);
1233 /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
1235 strmap_get_lc(const strmap_t
*map
, const char *key
)
1238 char *lc_key
= tor_strdup(key
);
1239 tor_strlower(lc_key
);
1240 v
= strmap_get(map
,lc_key
);
1245 /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
1247 strmap_remove_lc(strmap_t
*map
, const char *key
)
1250 char *lc_key
= tor_strdup(key
);
1251 tor_strlower(lc_key
);
1252 v
= strmap_remove(map
,lc_key
);
1257 /** return an <b>iterator</b> pointer to the front of a map.
1262 * // uppercase values in "map", removing empty values.
1264 * strmap_iter_t *iter;
1269 * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) {
1270 * strmap_iter_get(iter, &key, &val);
1273 * iter = strmap_iter_next_rmv(map,iter);
1276 * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp);
1277 * iter = strmap_iter_next(map,iter);
1284 strmap_iter_init(strmap_t
*map
)
1287 return HT_START(strmap_impl
, &map
->head
);
1290 /** Start iterating through <b>map</b>. See strmap_iter_init() for example. */
1292 digestmap_iter_init(digestmap_t
*map
)
1295 return HT_START(digestmap_impl
, &map
->head
);
1298 /** Advance the iterator <b>iter</b> for <b>map</b> a single step to the next
1299 * entry, and return its new value. */
1301 strmap_iter_next(strmap_t
*map
, strmap_iter_t
*iter
)
1305 return HT_NEXT(strmap_impl
, &map
->head
, iter
);
1308 /** Advance the iterator <b>iter</b> for map a single step to the next entry,
1309 * and return its new value. */
1311 digestmap_iter_next(digestmap_t
*map
, digestmap_iter_t
*iter
)
1315 return HT_NEXT(digestmap_impl
, &map
->head
, iter
);
1318 /** Advance the iterator <b>iter</b> a single step to the next entry, removing
1319 * the current entry, and return its new value.
1322 strmap_iter_next_rmv(strmap_t
*map
, strmap_iter_t
*iter
)
1324 strmap_entry_t
*rmv
;
1329 iter
= HT_NEXT_RMV(strmap_impl
, &map
->head
, iter
);
1335 /** Advance the iterator <b>iter</b> a single step to the next entry, removing
1336 * the current entry, and return its new value.
1339 digestmap_iter_next_rmv(digestmap_t
*map
, digestmap_iter_t
*iter
)
1341 digestmap_entry_t
*rmv
;
1346 iter
= HT_NEXT_RMV(digestmap_impl
, &map
->head
, iter
);
1351 /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
1354 strmap_iter_get(strmap_iter_t
*iter
, const char **keyp
, void **valp
)
1360 *keyp
= (*iter
)->key
;
1361 *valp
= (*iter
)->val
;
1364 /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
1367 digestmap_iter_get(digestmap_iter_t
*iter
, const char **keyp
, void **valp
)
1373 *keyp
= (*iter
)->key
;
1374 *valp
= (*iter
)->val
;
1377 /** Return true iff <b>iter</b> has advanced past the last entry of
1380 strmap_iter_done(strmap_iter_t
*iter
)
1382 return iter
== NULL
;
1385 /** Return true iff <b>iter</b> has advanced past the last entry of
1388 digestmap_iter_done(digestmap_iter_t
*iter
)
1390 return iter
== NULL
;
1393 /** Remove all entries from <b>map</b>, and deallocate storage for those
1394 * entries. If free_val is provided, it is invoked on every value in
1398 strmap_free(strmap_t
*map
, void (*free_val
)(void*))
1400 strmap_entry_t
**ent
, **next
, *this;
1404 for (ent
= HT_START(strmap_impl
, &map
->head
); ent
!= NULL
; ent
= next
) {
1406 next
= HT_NEXT_RMV(strmap_impl
, &map
->head
, ent
);
1407 tor_free(this->key
);
1409 free_val(this->val
);
1412 tor_assert(HT_EMPTY(&map
->head
));
1413 HT_CLEAR(strmap_impl
, &map
->head
);
1417 /** Remove all entries from <b>map</b>, and deallocate storage for those
1418 * entries. If free_val is provided, it is invoked on every value in
1422 digestmap_free(digestmap_t
*map
, void (*free_val
)(void*))
1424 digestmap_entry_t
**ent
, **next
, *this;
1427 for (ent
= HT_START(digestmap_impl
, &map
->head
); ent
!= NULL
; ent
= next
) {
1429 next
= HT_NEXT_RMV(digestmap_impl
, &map
->head
, ent
);
1431 free_val(this->val
);
1434 tor_assert(HT_EMPTY(&map
->head
));
1435 HT_CLEAR(digestmap_impl
, &map
->head
);
1439 /** Fail with an assertion error if anything has gone wrong with the internal
1440 * representation of <b>map</b>. */
1442 strmap_assert_ok(const strmap_t
*map
)
1444 tor_assert(!strmap_impl_HT_REP_IS_BAD_(&map
->head
));
1446 /** Fail with an assertion error if anything has gone wrong with the internal
1447 * representation of <b>map</b>. */
1449 digestmap_assert_ok(const digestmap_t
*map
)
1451 tor_assert(!digestmap_impl_HT_REP_IS_BAD_(&map
->head
));
1454 /** Return true iff <b>map</b> has no entries. */
1456 strmap_isempty(const strmap_t
*map
)
1458 return HT_EMPTY(&map
->head
);
1461 /** Return true iff <b>map</b> has no entries. */
1463 digestmap_isempty(const digestmap_t
*map
)
1465 return HT_EMPTY(&map
->head
);
1468 /** Return the number of items in <b>map</b>. */
1470 strmap_size(const strmap_t
*map
)
1472 return HT_SIZE(&map
->head
);
1475 /** Return the number of items in <b>map</b>. */
1477 digestmap_size(const digestmap_t
*map
)
1479 return HT_SIZE(&map
->head
);
1482 /** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
1483 * function for an array of type <b>elt_t</b>*.
1485 * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding
1486 * the kth element of an n-element list can be done in O(n). Then again, this
1487 * implementation is not in critical path, and it is obviously correct. */
1488 #define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \
1490 _cmp_ ## elt_t(const void *_a, const void *_b) \
1492 const elt_t *a = _a, *b = _b; \
1501 funcname(elt_t *array, int n_elements, int nth) \
1503 tor_assert(nth >= 0); \
1504 tor_assert(nth < n_elements); \
1505 qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \
1506 return array[nth]; \
1509 IMPLEMENT_ORDER_FUNC(find_nth_int
, int)
1510 IMPLEMENT_ORDER_FUNC(find_nth_time
, time_t)
1511 IMPLEMENT_ORDER_FUNC(find_nth_double
, double)
1512 IMPLEMENT_ORDER_FUNC(find_nth_uint32
, uint32_t)
1513 IMPLEMENT_ORDER_FUNC(find_nth_int32
, int32_t)
1514 IMPLEMENT_ORDER_FUNC(find_nth_long
, long)
1516 /** Return a newly allocated digestset_t, optimized to hold a total of
1517 * <b>max_elements</b> digests with a reasonably low false positive weight. */
1519 digestset_new(int max_elements
)
1521 /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
1522 * is the number of hash functions per entry, m is the bits in the array,
1523 * and n is the number of elements inserted. For us, k==4, n<=max_elements,
1524 * and m==n_bits= approximately max_elements*32. This gives
1525 * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
1527 * It would be more optimal in space vs false positives to get this false
1528 * positive rate by going for k==13, and m==18.5n, but we also want to
1529 * conserve CPU, and k==13 is pretty big.
1531 int n_bits
= 1u << (tor_log2(max_elements
)+5);
1532 digestset_t
*r
= tor_malloc(sizeof(digestset_t
));
1533 r
->mask
= n_bits
- 1;
1534 r
->ba
= bitarray_init_zero(n_bits
);
1538 /** Free all storage held in <b>set</b>. */
1540 digestset_free(digestset_t
*set
)
1544 bitarray_free(set
->ba
);