/* Copyright (c) 2003-2004, Roger Dingledine * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. * Copyright (c) 2007-2017, The Tor Project, Inc. */ /* See LICENSE for licensing information */ /** * \file container.c * \brief Implements a smartlist (a resizable array) along * with helper functions to use smartlists. Also includes * hash table implementations of a string-to-void* map, and of * a digest-to-void* map. **/ #include "compat.h" #include "util.h" #include "torlog.h" #include "container.h" #include "crypto.h" #include #include #include #include "ht.h" /** All newly allocated smartlists have this capacity. */ #define SMARTLIST_DEFAULT_CAPACITY 16 /** Allocate and return an empty smartlist. */ MOCK_IMPL(smartlist_t *, smartlist_new,(void)) { smartlist_t *sl = tor_malloc(sizeof(smartlist_t)); sl->num_used = 0; sl->capacity = SMARTLIST_DEFAULT_CAPACITY; sl->list = tor_calloc(sizeof(void *), sl->capacity); return sl; } /** Deallocate a smartlist. Does not release storage associated with the * list's elements. */ MOCK_IMPL(void, smartlist_free,(smartlist_t *sl)) { if (!sl) return; tor_free(sl->list); tor_free(sl); } /** Remove all elements from the list. */ void smartlist_clear(smartlist_t *sl) { memset(sl->list, 0, sizeof(void *) * sl->num_used); sl->num_used = 0; } #if SIZE_MAX < INT_MAX #error "We don't support systems where size_t is smaller than int." #endif /** Make sure that sl can hold at least size entries. */ static inline void smartlist_ensure_capacity(smartlist_t *sl, size_t size) { /* Set MAX_CAPACITY to MIN(INT_MAX, SIZE_MAX / sizeof(void*)) */ #if (SIZE_MAX/SIZEOF_VOID_P) > INT_MAX #define MAX_CAPACITY (INT_MAX) #else #define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*)))) #endif tor_assert(size <= MAX_CAPACITY); if (size > (size_t) sl->capacity) { size_t higher = (size_t) sl->capacity; if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) { higher = MAX_CAPACITY; } else { while (size > higher) higher *= 2; } sl->list = tor_reallocarray(sl->list, sizeof(void *), ((size_t)higher)); memset(sl->list + sl->capacity, 0, sizeof(void *) * (higher - sl->capacity)); sl->capacity = (int) higher; } #undef ASSERT_CAPACITY #undef MAX_CAPACITY } /** Append element to the end of the list. */ void smartlist_add(smartlist_t *sl, void *element) { smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1); sl->list[sl->num_used++] = element; } /** Append each element from S2 to the end of S1. */ void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2) { size_t new_size = (size_t)s1->num_used + (size_t)s2->num_used; tor_assert(new_size >= (size_t) 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*)); tor_assert(new_size <= INT_MAX); /* redundant. */ s1->num_used = (int) new_size; } /** 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. */ void smartlist_remove(smartlist_t *sl, const void *element) { 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 */ sl->list[sl->num_used] = NULL; } } /** As smartlist_remove, but do not change the order of * any elements not removed */ void smartlist_remove_keeporder(smartlist_t *sl, const void *element) { int i, j, num_used_orig = sl->num_used; if (element == NULL) return; for (i=j=0; j < num_used_orig; ++j) { if (sl->list[j] == element) { --sl->num_used; } else { sl->list[i++] = sl->list[j]; } } } /** If sl is nonempty, remove and return the final element. Otherwise, * return NULL. */ void * smartlist_pop_last(smartlist_t *sl) { tor_assert(sl); if (sl->num_used) { void *tmp = sl->list[--sl->num_used]; sl->list[sl->num_used] = NULL; return tmp; } else return NULL; } /** Reverse the order of the items in sl. */ void smartlist_reverse(smartlist_t *sl) { 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; } } /** If there are any strings in sl equal to element, remove and free them. * Does not preserve order. */ void smartlist_string_remove(smartlist_t *sl, const char *element) { 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 */ sl->list[sl->num_used] = NULL; } } } /** Return true iff some element E of sl has E==element. */ int smartlist_contains(const smartlist_t *sl, const void *element) { int i; for (i=0; i < sl->num_used; i++) if (sl->list[i] == element) return 1; return 0; } /** Return true iff sl has some element E such that * !strcmp(E,element) */ int smartlist_contains_string(const smartlist_t *sl, const char *element) { 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; } /** If element is equal to an element of sl, return that * element's index. Otherwise, return -1. */ int smartlist_string_pos(const smartlist_t *sl, const char *element) { 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; } /** If element is the same pointer as an element of sl, return * that element's index. Otherwise, return -1. */ int smartlist_pos(const smartlist_t *sl, const void *element) { int i; if (!sl) return -1; for (i=0; i < sl->num_used; i++) if (element == sl->list[i]) return i; return -1; } /** Return true iff sl has some element E such that * !strcasecmp(E,element) */ int smartlist_contains_string_case(const smartlist_t *sl, const char *element) { 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; } /** Return true iff sl has some element E such that E is equal * to the decimal encoding of num. */ int smartlist_contains_int_as_string(const smartlist_t *sl, int num) { char buf[32]; /* long enough for 64-bit int, and then some. */ tor_snprintf(buf,sizeof(buf),"%d", num); return smartlist_contains_string(sl, buf); } /** Return true iff the two lists contain the same strings in the same * order, or if they are both NULL. */ int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2) { 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; } /** Return true iff the two lists contain the same int pointer values in * the same order, or if they are both NULL. */ int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2) { if (sl1 == NULL) return sl2 == NULL; if (sl2 == NULL) return 0; if (smartlist_len(sl1) != smartlist_len(sl2)) return 0; SMARTLIST_FOREACH(sl1, int *, cp1, { int *cp2 = smartlist_get(sl2, cp1_sl_idx); if (*cp1 != *cp2) return 0; }); return 1; } /** Return true iff sl has some element E such that * tor_memeq(E,element,DIGEST_LEN) */ int smartlist_contains_digest(const smartlist_t *sl, const char *element) { 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; } /** Return true iff some element E of sl2 has smartlist_contains(sl1,E). */ int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2) { int i; for (i=0; i < sl2->num_used; i++) if (smartlist_contains(sl1, sl2->list[i])) return 1; return 0; } /** Remove every element E of sl1 such that !smartlist_contains(sl2,E). * Does not preserve the order of sl1. */ void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2) { int i; for (i=0; i < sl1->num_used; i++) if (!smartlist_contains(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 */ sl1->list[sl1->num_used] = NULL; } } /** Remove every element E of sl1 such that smartlist_contains(sl2,E). * Does not preserve the order of sl1. */ void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2) { int i; for (i=0; i < sl2->num_used; i++) smartlist_remove(sl1, sl2->list[i]); } /** 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(smartlist_t *sl, int idx) { tor_assert(sl); tor_assert(idx>=0); tor_assert(idx < sl->num_used); sl->list[idx] = sl->list[--sl->num_used]; sl->list[sl->num_used] = NULL; } /** 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. */ void smartlist_del_keeporder(smartlist_t *sl, int idx) { 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)); sl->list[sl->num_used] = NULL; } /** Insert the value val as the new idxth element of * sl, moving all items previously at idx or later * forward one space. */ void smartlist_insert(smartlist_t *sl, int idx, void *val) { 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, ((size_t) 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; } } /** * 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. */ int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, int flags, int max) { 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; } /** 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. */ char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out) { return smartlist_join_strings2(sl,join,strlen(join),terminate,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.) */ char * 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 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_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 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. If count_out is * non-null, set it to the count of the most frequent member. */ void * smartlist_get_most_frequent_(const smartlist_t *sl, int (*compare)(const void **a, const void **b), int *count_out) { const void *most_frequent = NULL; int most_frequent_count = 0; const void *cur = NULL; int i, count=0; if (!sl->num_used) { if (count_out) *count_out = 0; 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; } if (count_out) *count_out = most_frequent_count; return (void*)most_frequent; } /** Given a sorted smartlist sl and the comparison function used to * sort it, remove all duplicate members. If free_fn is provided, calls * free_fn on each duplicate. Otherwise, just removes them. Preserves order. */ 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 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. */ 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 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. */ int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int (*compare)(const void *key, const void **member), int *found_out) { int hi, lo, cmp, mid, len, diff; tor_assert(sl); tor_assert(compare); tor_assert(found_out); len = smartlist_len(sl); /* Check for the trivial case of a zero-length list */ if (len == 0) { *found_out = 0; /* We already know smartlist_len(sl) is 0 in this case */ return 0; } /* Okay, we have a real search to do */ tor_assert(len > 0); lo = 0; hi = len - 1; /* * These invariants are always true: * * For all i such that 0 <= i < lo, sl[i] < key * For all i such that hi < i <= len, sl[i] > key */ while (lo <= hi) { diff = hi - lo; /* * We want mid = (lo + hi) / 2, but that could lead to overflow, so * instead diff = hi - lo (non-negative because of loop condition), and * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2). */ mid = lo + (diff / 2); cmp = compare(key, (const void**) &(sl->list[mid])); if (cmp == 0) { /* sl[mid] == key; we found it */ *found_out = 1; return mid; } else if (cmp > 0) { /* * key > sl[mid] and an index i such that sl[i] == key must * have i > mid if it exists. */ /* * Since lo <= mid <= hi, hi can only decrease on each iteration (by * being set to mid - 1) and hi is initially len - 1, mid < len should * always hold, and this is not symmetric with the left end of list * mid > 0 test below. A key greater than the right end of the list * should eventually lead to lo == hi == mid == len - 1, and then * we set lo to len below and fall out to the same exit we hit for * a key in the middle of the list but not matching. Thus, we just * assert for consistency here rather than handle a mid == len case. */ tor_assert(mid < len); /* Move lo to the element immediately after sl[mid] */ lo = mid + 1; } else { /* This should always be true in this case */ tor_assert(cmp < 0); /* * key < sl[mid] and an index i such that sl[i] == key must * have i < mid if it exists. */ if (mid > 0) { /* Normal case, move hi to the element immediately before sl[mid] */ hi = mid - 1; } else { /* These should always be true in this case */ tor_assert(mid == lo); tor_assert(mid == 0); /* * We were at the beginning of the list and concluded that every * element e compares e > key. */ *found_out = 0; return 0; } } } /* * lo > hi; we have no element matching key but we have elements falling * on both sides of it. The lo index points to the first element > key. */ tor_assert(lo == hi + 1); /* All other cases should have been handled */ tor_assert(lo >= 0); tor_assert(lo <= len); tor_assert(hi >= 0); tor_assert(hi <= len); if (lo < len) { cmp = compare(key, (const void **) &(sl->list[lo])); tor_assert(cmp < 0); } else { cmp = compare(key, (const void **) &(sl->list[len-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 sl containing strings into lexically ascending * order. */ void smartlist_sort_strings(smartlist_t *sl) { smartlist_sort(sl, compare_string_ptrs_); } /** Return the most frequent string in the sorted list sl */ const char * smartlist_get_most_frequent_string(smartlist_t *sl) { return smartlist_get_most_frequent(sl, compare_string_ptrs_); } /** Return the most frequent string in the sorted list sl. * If count_out is provided, set count_out to the * number of times that string appears. */ const char * smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out) { return smartlist_get_most_frequent_(sl, compare_string_ptrs_, count_out); } /** 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_); } /** Helper: compare two pointers. */ static int compare_ptrs_(const void **_a, const void **_b) { const void *a = *_a, *b = *_b; if (asl in ascending order of the pointers it contains. */ void smartlist_sort_pointers(smartlist_t *sl) { smartlist_sort(sl, compare_ptrs_); } /* 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 us to remove items other than the topmost item, each item must store * its own index within the heap. When calling the pqueue functions, tell * them about the offset of the field that stores the index within the item. * * Example: * * typedef struct timer_t { * struct timeval tv; * int heap_index; * } timer_t; * * static int compare(const void *p1, const void *p2) { * const timer_t *t1 = p1, *t2 = p2; * if (t1->tv.tv_sec < t2->tv.tv_sec) { * return -1; * } else if (t1->tv.tv_sec > t2->tv.tv_sec) { * return 1; * } else { * return t1->tv.tv_usec - t2->tv_usec; * } * } * * void timer_heap_insert(smartlist_t *heap, timer_t *timer) { * smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index), * timer); * } * * void timer_heap_pop(smartlist_t *heap) { * return smartlist_pqueue_pop(heap, compare, * STRUCT_OFFSET(timer_t, heap_index)); * } */ /** @{ */ /** Functions to manipulate heap indices to find a node's parent and children. * * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x] * = 2*x + 1. But this is C, so we have to adjust a little. */ /* MAX_PARENT_IDX is the largest IDX in the smartlist which might have * children whose indices fit inside an int. * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2; * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1; * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size. */ #define MAX_PARENT_IDX ((INT_MAX - 2) / 2) /* If this is true, then i is small enough to potentially have children * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */ #define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX) #define LEFT_CHILD(i) ( 2*(i) + 1 ) #define RIGHT_CHILD(i) ( 2*(i) + 2 ) #define PARENT(i) ( ((i)-1) / 2 ) /** }@ */ /** @{ */ /** Helper macros for heaps: Given a local variable idx_field_offset * set to the offset of an integer index within the heap element structure, * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to * where p's index is stored. Given additionally a local smartlist sl, * UPDATE_IDX(i) sets the index of the element at i to the correct * value (that is, to i). */ #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset)) #define UPDATE_IDX(i) do { \ void *updated = sl->list[i]; \ *IDXP(updated) = i; \ } while (0) #define IDX_OF_ITEM(p) (*IDXP(p)) /** @} */ /** Helper. sl may have at most one violation of the heap property: * the item at idx may be greater than one or both of its children. * Restore the heap property. */ static inline void smartlist_heapify(smartlist_t *sl, int (*compare)(const void *a, const void *b), int idx_field_offset, int idx) { while (1) { if (! IDX_MAY_HAVE_CHILDREN(idx)) { /* idx is so large that it cannot have any children, since doing so * would mean the smartlist was over-capacity. Therefore it cannot * violate the heap property by being greater than a child (since it * doesn't have any). */ return; } int left_idx = LEFT_CHILD(idx); int best_idx; if (left_idx >= sl->num_used) return; if (compare(sl->list[idx],sl->list[left_idx]) < 0) best_idx = idx; else best_idx = left_idx; if (left_idx+1 < sl->num_used && compare(sl->list[left_idx+1],sl->list[best_idx]) < 0) best_idx = left_idx + 1; if (best_idx == idx) { return; } else { void *tmp = sl->list[idx]; sl->list[idx] = sl->list[best_idx]; sl->list[best_idx] = tmp; UPDATE_IDX(idx); UPDATE_IDX(best_idx); idx = best_idx; } } } /** 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_add(smartlist_t *sl, int (*compare)(const void *a, const void *b), int idx_field_offset, void *item) { 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; } } } /** 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. */ void * smartlist_pqueue_pop(smartlist_t *sl, int (*compare)(const void *a, const void *b), int idx_field_offset) { 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]; sl->list[sl->num_used] = NULL; UPDATE_IDX(0); smartlist_heapify(sl, compare, idx_field_offset, 0); } sl->list[sl->num_used] = NULL; return top; } /** 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. */ void smartlist_pqueue_remove(smartlist_t *sl, int (*compare)(const void *a, const void *b), int idx_field_offset, void *item) { 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) { sl->list[sl->num_used] = NULL; return; } else { sl->list[idx] = sl->list[sl->num_used]; sl->list[sl->num_used] = NULL; UPDATE_IDX(idx); smartlist_heapify(sl, compare, idx_field_offset, idx); } } /** Assert that the heap property is correctly maintained by the heap stored * in sl, where order is determined by compare. */ void smartlist_pqueue_assert_ok(smartlist_t *sl, int (*compare)(const void *a, const void *b), int idx_field_offset) { 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); } } /** Helper: compare two DIGEST_LEN digests. */ static int compare_digests_(const void **_a, const void **_b) { return tor_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_); } /** Helper: compare two DIGEST256_LEN digests. */ static int compare_digests256_(const void **_a, const void **_b) { return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); } /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */ void smartlist_sort_digests256(smartlist_t *sl) { smartlist_sort(sl, compare_digests256_); } /** Return the most frequent member of the sorted list of DIGEST256_LEN * digests in sl */ const uint8_t * smartlist_get_most_frequent_digest256(smartlist_t *sl) { return smartlist_get_most_frequent(sl, compare_digests256_); } /** Remove duplicate 256-bit digests from a sorted list, and free them with * tor_free(). */ void smartlist_uniq_digests256(smartlist_t *sl) { smartlist_uniq(sl, compare_digests256_, tor_free_); } /** Helper: Declare an entry type and a map type to implement a mapping using * ht.h. The map type will be called maptype. The key part of each * entry is declared using the C declaration keydecl. All functions * and types associated with the map get prefixed with prefix */ #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_); DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_); /** 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 (unsigned) siphash24g(a->key, strlen(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 tor_memeq(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) { return (unsigned) siphash24g(a->key, DIGEST_LEN); } /** Helper: compare digestmap_entry_t objects by key value. */ static inline int digest256map_entries_eq(const digest256map_entry_t *a, const digest256map_entry_t *b) { return tor_memeq(a->key, b->key, DIGEST256_LEN); } /** Helper: return a hash value for a digest_map_t. */ static inline unsigned int digest256map_entry_hash(const digest256map_entry_t *a) { return (unsigned) siphash24g(a->key, DIGEST256_LEN); } HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, strmap_entries_eq) HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash, strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, digestmap_entries_eq) HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node, digest256map_entry_hash, digest256map_entries_eq) HT_GENERATE2(digest256map_impl, digest256map_entry_t, node, digest256map_entry_hash, digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_) static inline void strmap_entry_free(strmap_entry_t *ent) { tor_free(ent->key); tor_free(ent); } static inline void digestmap_entry_free(digestmap_entry_t *ent) { tor_free(ent); } static inline void digest256map_entry_free(digest256map_entry_t *ent) { tor_free(ent); } static inline void strmap_assign_tmp_key(strmap_entry_t *ent, const char *key) { ent->key = (char*)key; } static inline void digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key) { memcpy(ent->key, key, DIGEST_LEN); } static inline void digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key) { memcpy(ent->key, key, DIGEST256_LEN); } static inline void strmap_assign_key(strmap_entry_t *ent, const char *key) { ent->key = tor_strdup(key); } static inline void digestmap_assign_key(digestmap_entry_t *ent, const char *key) { memcpy(ent->key, key, DIGEST_LEN); } static inline void digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key) { memcpy(ent->key, key, DIGEST256_LEN); } /** * Macro: implement all the functions for a map that are declared in * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a * prefix_entry_free_() function to free entries (and their keys), a * prefix_assign_tmp_key() function to temporarily set a stack-allocated * entry to hold a key, and a prefix_assign_key() function to set a * heap-allocated entry to hold a key. */ #define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \ /** Create and return a new empty map. */ \ MOCK_IMPL(maptype *, \ prefix##_new,(void)) \ { \ maptype *result; \ result = tor_malloc(sizeof(maptype)); \ HT_INIT(prefix##_impl, &result->head); \ return result; \ } \ \ /** Return the item from map whose key matches key, or \ * NULL if no such value exists. */ \ void * \ prefix##_get(const maptype *map, const keytype key) \ { \ prefix ##_entry_t *resolve; \ prefix ##_entry_t search; \ tor_assert(map); \ tor_assert(key); \ prefix ##_assign_tmp_key(&search, key); \ resolve = HT_FIND(prefix ##_impl, &map->head, &search); \ if (resolve) { \ return resolve->val; \ } else { \ return NULL; \ } \ } \ \ /** Add an entry to map mapping key to val; \ * return the previous value, or NULL if no such value existed. */ \ void * \ prefix##_set(maptype *map, const keytype key, void *val) \ { \ prefix##_entry_t search; \ void *oldval; \ tor_assert(map); \ tor_assert(key); \ tor_assert(val); \ prefix##_assign_tmp_key(&search, key); \ /* We a lot of our time in this function, so the code below is */ \ /* meant to optimize the check/alloc/set cycle by avoiding the two */\ /* trips to the hash table that we would do in the unoptimized */ \ /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \ /* HT_SET_HASH and HT_FIND_P.) */ \ HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \ &(map->head), \ prefix##_entry_t, &search, ptr, \ { \ /* we found an entry. */ \ oldval = (*ptr)->val; \ (*ptr)->val = val; \ return oldval; \ }, \ { \ /* We didn't find the entry. */ \ prefix##_entry_t *newent = \ tor_malloc_zero(sizeof(prefix##_entry_t)); \ prefix##_assign_key(newent, key); \ newent->val = val; \ HT_FOI_INSERT_(node, &(map->head), \ &search, newent, ptr); \ return NULL; \ }); \ } \ \ /** Remove the value currently associated with key from the map. \ * Return the value if one was set, or NULL if there was no entry for \ * key. \ * \ * Note: you must free any storage associated with the returned value. \ */ \ void * \ prefix##_remove(maptype *map, const keytype key) \ { \ prefix##_entry_t *resolve; \ prefix##_entry_t search; \ void *oldval; \ tor_assert(map); \ tor_assert(key); \ prefix##_assign_tmp_key(&search, key); \ resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \ if (resolve) { \ oldval = resolve->val; \ prefix##_entry_free(resolve); \ return oldval; \ } else { \ return NULL; \ } \ } \ \ /** Return the number of elements in map. */ \ int \ prefix##_size(const maptype *map) \ { \ return HT_SIZE(&map->head); \ } \ \ /** Return true iff map has no entries. */ \ int \ prefix##_isempty(const maptype *map) \ { \ return HT_EMPTY(&map->head); \ } \ \ /** Assert that map is not corrupt. */ \ void \ prefix##_assert_ok(const maptype *map) \ { \ tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \ } \ \ /** Remove all entries from map, and deallocate storage for \ * those entries. If free_val is provided, invoked it every value in \ * map. */ \ MOCK_IMPL(void, \ prefix##_free, (maptype *map, void (*free_val)(void*))) \ { \ prefix##_entry_t **ent, **next, *this; \ if (!map) \ return; \ for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \ ent = next) { \ this = *ent; \ next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \ if (free_val) \ free_val(this->val); \ prefix##_entry_free(this); \ } \ tor_assert(HT_EMPTY(&map->head)); \ HT_CLEAR(prefix##_impl, &map->head); \ tor_free(map); \ } \ \ /** return an iterator pointer to the front of a map. \ * \ * Iterator example: \ * \ * \code \ * // uppercase values in "map", removing empty values. \ * \ * strmap_iter_t *iter; \ * const char *key; \ * void *val; \ * char *cp; \ * \ * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { \ * strmap_iter_get(iter, &key, &val); \ * cp = (char*)val; \ * if (!*cp) { \ * iter = strmap_iter_next_rmv(map,iter); \ * free(val); \ * } else { \ * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); \ */ \ prefix##_iter_t * \ prefix##_iter_init(maptype *map) \ { \ tor_assert(map); \ return HT_START(prefix##_impl, &map->head); \ } \ \ /** Advance iter a single step to the next entry, and return \ * its new value. */ \ prefix##_iter_t * \ prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \ { \ tor_assert(map); \ tor_assert(iter); \ return HT_NEXT(prefix##_impl, &map->head, iter); \ } \ /** Advance iter a single step to the next entry, removing the \ * current entry, and return its new value. */ \ prefix##_iter_t * \ prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \ { \ prefix##_entry_t *rmv; \ tor_assert(map); \ tor_assert(iter); \ tor_assert(*iter); \ rmv = *iter; \ iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \ prefix##_entry_free(rmv); \ return iter; \ } \ /** Set *keyp and *valp to the current entry pointed \ * to by iter. */ \ void \ prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \ void **valp) \ { \ tor_assert(iter); \ tor_assert(*iter); \ tor_assert(keyp); \ tor_assert(valp); \ *keyp = (*iter)->key; \ *valp = (*iter)->val; \ } \ /** Return true iff iter has advanced past the last entry of \ * map. */ \ int \ prefix##_iter_done(prefix##_iter_t *iter) \ { \ return iter == NULL; \ } IMPLEMENT_MAP_FNS(strmap_t, char *, strmap) IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap) IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map) /** Same as strmap_set, but first converts key to lowercase. */ void * strmap_set_lc(strmap_t *map, const char *key, void *val) { /* 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; } /** Same as strmap_get, but first converts key to lowercase. */ void * strmap_get_lc(const strmap_t *map, const char *key) { void *v; char *lc_key = tor_strdup(key); tor_strlower(lc_key); v = strmap_get(map,lc_key); tor_free(lc_key); return v; } /** Same as strmap_remove, but first converts key to lowercase */ void * strmap_remove_lc(strmap_t *map, const char *key) { void *v; char *lc_key = tor_strdup(key); tor_strlower(lc_key); v = strmap_remove(map,lc_key); tor_free(lc_key); return v; } /** Declare a function called funcname that acts as a find_nth_FOO * function for an array of type elt_t*. * * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding * the kth element of an n-element list can be done in O(n). Then again, this * implementation is not in critical path, and it is obviously correct. */ #define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \ static int \ _cmp_ ## elt_t(const void *_a, const void *_b) \ { \ const elt_t *a = _a, *b = _b; \ if (*a<*b) \ return -1; \ else if (*a>*b) \ return 1; \ else \ return 0; \ } \ elt_t \ funcname(elt_t *array, int n_elements, int nth) \ { \ tor_assert(nth >= 0); \ tor_assert(nth < n_elements); \ qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \ return array[nth]; \ } IMPLEMENT_ORDER_FUNC(find_nth_int, int) IMPLEMENT_ORDER_FUNC(find_nth_time, time_t) IMPLEMENT_ORDER_FUNC(find_nth_double, double) IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t) IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t) IMPLEMENT_ORDER_FUNC(find_nth_long, long) /** Return a newly allocated digestset_t, optimized to hold a total of * max_elements digests with a reasonably low false positive weight. */ digestset_t * digestset_new(int max_elements) { /* 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; } /** Free all storage held in set. */ void digestset_free(digestset_t *set) { if (!set) return; bitarray_free(set->ba); tor_free(set); }