diff options
Diffstat (limited to 'src/lib/container/smartlist.c')
| -rw-r--r-- | src/lib/container/smartlist.c | 1094 |
1 files changed, 1094 insertions, 0 deletions
diff --git a/src/lib/container/smartlist.c b/src/lib/container/smartlist.c new file mode 100644 index 0000000000..6aef728547 --- /dev/null +++ b/src/lib/container/smartlist.c @@ -0,0 +1,1094 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, 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 "lib/malloc/util_malloc.h" +#include "lib/container/smartlist.h" +#include "common/util.h" +#include "lib/crypt_ops/crypto_digest.h" +#include "lib/ctime/di_ops.h" + +#include <stdlib.h> +#include <string.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 <b>sl</b> can hold at least <b>size</b> 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 + + raw_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; +} + +/** Append a copy of string to sl */ +void +smartlist_add_strdup(struct smartlist_t *sl, const char *string) +{ + char *copy; + + copy = tor_strdup(string); + + smartlist_add(sl, copy); +} + +/** 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 <b>smartlist_remove</b>, 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 <b>sl</b> 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 <b>sl</b>. */ +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 <b>sl</b> has some element E such that + * !strcmp(E,<b>element</b>) + */ +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 <b>element</b> is equal to an element of <b>sl</b>, 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 <b>element</b> is the same pointer as an element of <b>sl</b>, 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 <b>sl</b> has some element E such that + * !strcasecmp(E,<b>element</b>) + */ +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 <b>sl</b> has some element E such that E is equal + * to the decimal encoding of <b>num</b>. + */ +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 <b>sl</b> has some element E such that + * tor_memeq(E,<b>element</b>,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 <b>idx</b>th element of sl; if idx is not the last + * element, swap the last element of sl into the <b>idx</b>th 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 <b>idx</b>th element of sl; if idx is not the last element, + * moving all subsequent elements back one space. Return the old value + * of the <b>idx</b>th 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 <b>val</b> as the new <b>idx</b>th element of + * <b>sl</b>, moving all items previously at <b>idx</b> 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 <b>str</b> along all occurrences of <b>sep</b>, + * appending the (newly allocated) split strings, in order, to + * <b>sl</b>. Return the number of strings added to <b>sl</b>. + * + * If <b>flags</b>&SPLIT_SKIP_SPACE is true, remove initial and + * trailing space from each entry. + * If <b>flags</b>&SPLIT_IGNORE_BLANK is true, remove any entries + * of length 0. + * If <b>flags</b>&SPLIT_STRIP_SPACE is true, strip spaces from each + * split string. + * + * If <b>max</b>\>0, divide the string into no more than <b>max</b> pieces. If + * <b>sep</b> 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 <b>sl</b>, in order, separated by <b>join</b>. If + * <b>terminate</b> is true, also terminate the string with <b>join</b>. + * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of + * the returned string. Requires that every element of <b>sl</b> 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 <b>join</b>, uses the <b>join_len</b>-byte sequence + * at <b>join</b>. (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 <b>sl</b> into an order defined by + * the ordering function <b>compare</b>, which returns less then 0 if a + * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b. + */ +void +smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)) +{ + if (!sl->num_used) + return; + qsort(sl->list, sl->num_used, sizeof(void*), + (int (*)(const void *,const void*))compare); +} + +/** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>, + * 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 <b>sl</b> and the comparison function used to + * sort it, remove all duplicate members. If free_fn is provided, calls + * free_fn on each duplicate. Otherwise, just removes them. Preserves order. + */ +void +smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *a)) +{ + int i; + for (i=1; i < sl->num_used; ++i) { + if (compare((const void **)&(sl->list[i-1]), + (const void **)&(sl->list[i])) == 0) { + if (free_fn) + free_fn(sl->list[i]); + smartlist_del_keeporder(sl, i--); + } + } +} + +/** Assuming the members of <b>sl</b> are in order, return a pointer to the + * member that matches <b>key</b>. Ordering and matching are defined by a + * <b>compare</b> function that returns 0 on a match; less than 0 if key is + * less than member, and greater than 0 if key is greater then member. + */ +void * +smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)) +{ + int found, idx; + idx = smartlist_bsearch_idx(sl, key, compare, &found); + return found ? smartlist_get(sl, idx) : NULL; +} + +/** Assuming the members of <b>sl</b> are in order, return the index of the + * member that matches <b>key</b>. If no member matches, return the index of + * the first member greater than <b>key</b>, or smartlist_len(sl) if no member + * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to + * false otherwise. Ordering and matching are defined by a <b>compare</b> + * function that returns 0 on a match; less than 0 if key is less than member, + * and greater than 0 if key is greater then member. + */ +int +smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out) +{ + int hi, 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 <b>sl</b> 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 <b>sl</b> */ +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 <b>sl</b>. + * If <b>count_out</b> is provided, set <b>count_out</b> 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 (a<b) + return -1; + else if (a==b) + return 0; + else + return 1; +} + +/** Sort <b>sl</b> 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, offsetof(timer_t, heap_index), + * timer); + * } + * + * void timer_heap_pop(smartlist_t *heap) { + * return smartlist_pqueue_pop(heap, compare, + * offsetof(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 <b>idx_field_offset</b> + * 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 <b>sl</b>, + * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct + * value (that is, to <b>i</b>). + */ +#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. <b>sl</b> may have at most one violation of the heap property: + * the item at <b>idx</b> may be greater than one or both of its children. + * Restore the heap property. */ +static inline void +smartlist_heapify(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_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 <b>item</b> into the heap stored in <b>sl</b>, where order is + * determined by <b>compare</b> and the offset of the item in the heap is + * stored in an int-typed field at position <b>idx_field_offset</b> 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 <b>sl</b>, + * where order is determined by <b>compare</b> and the item's position is + * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> 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 <b>item</b> from the heap stored in <b>sl</b>, + * where order is determined by <b>compare</b> and the item's position is + * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> 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 <b>sl</b>, where order is determined by <b>compare</b>. */ +void +smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int 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 <b>sl</b> */ +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_); +} |