39 va_start(ap, pattern);
64 for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
79 for (i = 0; i < sl->num_used; ++i) {
80 if (!strcmp(element, sl->
list[i])) {
82 sl->
list[i] = sl->
list[--sl->num_used];
84 sl->
list[sl->num_used] = NULL;
97 for (i=0; i < sl->num_used; i++)
98 if (strcmp((
const char*)sl->
list[i],element)==0)
110 for (i=0; i < sl->num_used; i++)
111 if (strcmp((
const char*)sl->
list[i],element)==0)
123 for (i=0; i < sl->num_used; i++)
124 if (element == sl->
list[i])
137 for (i=0; i < sl->num_used; i++)
138 if (strcasecmp((
const char*)sl->
list[i],element)==0)
163 if (smartlist_len(sl1) != smartlist_len(sl2))
166 const char *cp2 = smartlist_get(sl2, cp1_sl_idx);
167 if (strcmp(cp1, cp2))
182 if (smartlist_len(sl1) != smartlist_len(sl2))
185 int *cp2 = smartlist_get(sl2, cp1_sl_idx);
205 if (s1 == NULL || s2 == NULL)
208 if (smartlist_len(s1) != smartlist_len(s2))
211 for (
int i = 0; i < smartlist_len(s1); i++) {
212 if (smartlist_get(s1, i) != smartlist_get(s2, i))
227 for (i=0; i < sl->num_used; i++)
239 for (i=0; i < sl2->num_used; i++)
252 for (i=0; i < sl1->num_used; i++)
254 sl1->
list[i] = sl1->
list[--sl1->num_used];
256 sl1->
list[sl1->num_used] = NULL;
267 for (i=0; i < sl2->num_used; i++)
280 int terminate,
size_t *len_out)
292 size_t join_len,
int terminate,
size_t *len_out)
296 char *r = NULL, *dst, *src;
304 for (i = 0; i < sl->num_used; ++i) {
305 n += strlen(sl->
list[i]);
306 if (i+1 < sl->num_used)
309 dst = r = tor_malloc(n+1);
310 for (i = 0; i < sl->num_used; ) {
311 for (src = sl->
list[i]; *src; )
313 if (++i < sl->num_used) {
314 memcpy(dst, join, join_len);
319 memcpy(dst, join, join_len);
338 qsort(sl->
list, sl->num_used,
sizeof(
void*),
339 (int (*)(
const void *,
const void*))compare);
349 int (*compare)(
const void **a,
const void **b),
352 const void *most_frequent = NULL;
353 int most_frequent_count = 0;
355 const void *cur = NULL;
363 for (i = 0; i < sl->num_used; ++i) {
364 const void *item = sl->
list[i];
365 if (cur && 0 == compare(&cur, &item)) {
368 if (cur && count >= most_frequent_count) {
370 most_frequent_count = count;
376 if (cur && count >= most_frequent_count) {
378 most_frequent_count = count;
381 *count_out = most_frequent_count;
382 return (
void*)most_frequent;
391 int (*compare)(
const void **a,
const void **b),
392 void (*free_fn)(
void *a))
395 for (i=1; i < sl->num_used; ++i) {
396 if (compare((
const void **)&(sl->
list[i-1]),
397 (
const void **)&(sl->
list[i])) == 0) {
399 free_fn(sl->
list[i]);
412 int (*compare)(
const void *key,
const void **member))
416 return found ? smartlist_get(sl, idx) : NULL;
429 int (*compare)(
const void *key,
const void **member),
432 int hi, lo, cmp, mid, len, diff;
438 len = smartlist_len(sl);
466 mid = lo + (diff / 2);
467 cmp = compare(key, (
const void**) &(sl->
list[mid]));
472 }
else if (cmp > 0) {
528 cmp = compare(key, (
const void **) &(sl->
list[lo]));
531 cmp = compare(key, (
const void **) &(sl->
list[len-1]));
543 return strcmp((
const char*)*_a, (
const char*)*_b);
583 const void *a = *_a, *b = *_b;
648 #define MAX_PARENT_IDX ((INT_MAX - 2) / 2)
651 #define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX)
652 #define LEFT_CHILD(i) ( 2*(i) + 1 )
653 #define RIGHT_CHILD(i) ( 2*(i) + 2 )
654 #define PARENT(i) ( ((i)-1) / 2 )
665 #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
667 #define UPDATE_IDX(i) do { \
668 void *updated = sl->list[i]; \
669 *IDXP(updated) = i; \
672 #define IDX_OF_ITEM(p) (*IDXP(p))
680 int (*compare)(
const void *a,
const void *b),
681 ptrdiff_t idx_field_offset,
685 if (! IDX_MAY_HAVE_CHILDREN(idx)) {
693 int left_idx = LEFT_CHILD(idx);
696 if (left_idx >= sl->num_used)
698 if (compare(sl->
list[idx],sl->
list[left_idx]) < 0)
702 if (left_idx+1 < sl->num_used &&
703 compare(sl->
list[left_idx+1],sl->
list[best_idx]) < 0)
704 best_idx = left_idx + 1;
706 if (best_idx == idx) {
709 void *tmp = sl->
list[idx];
711 sl->
list[best_idx] = tmp;
713 UPDATE_IDX(best_idx);
727 int (*compare)(
const void *a,
const void *b),
728 ptrdiff_t idx_field_offset,
733 UPDATE_IDX(sl->num_used-1);
735 for (idx = sl->num_used - 1; idx; ) {
736 int parent = PARENT(idx);
737 if (compare(sl->
list[idx], sl->
list[parent]) < 0) {
738 void *tmp = sl->
list[parent];
756 int (*compare)(
const void *a,
const void *b),
757 ptrdiff_t idx_field_offset)
764 if (--sl->num_used) {
765 sl->
list[0] = sl->
list[sl->num_used];
766 sl->
list[sl->num_used] = NULL;
770 sl->
list[sl->num_used] = NULL;
780 int (*compare)(
const void *a,
const void *b),
781 ptrdiff_t idx_field_offset,
784 int idx = IDX_OF_ITEM(item);
789 if (idx == sl->num_used) {
790 sl->
list[sl->num_used] = NULL;
793 sl->
list[idx] = sl->
list[sl->num_used];
794 sl->
list[sl->num_used] = NULL;
804 int (*compare)(
const void *a,
const void *b),
805 ptrdiff_t idx_field_offset)
808 for (i = sl->num_used - 1; i >= 0; --i) {
Locale-independent character-type inspection (header)
Header for compat_string.c.
int tor_memeq(const void *a, const void *b, size_t sz)
int tor_memcmp(const void *a, const void *b, size_t len)
Definitions for common sizes of cryptographic digests.
void tor_free_(void *mem)
Headers for util_malloc.c.
int tor_vasprintf(char **strp, const char *fmt, va_list args)
int tor_snprintf(char *str, size_t size, const char *format,...)
void smartlist_sort_digests(smartlist_t *sl)
int smartlist_ptrs_eq(const smartlist_t *s1, const smartlist_t *s2)
void smartlist_sort_digests256(smartlist_t *sl)
void smartlist_string_remove(smartlist_t *sl, const char *element)
void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
void smartlist_uniq_digests(smartlist_t *sl)
void * smartlist_get_most_frequent_(const smartlist_t *sl, int(*compare)(const void **a, const void **b), int *count_out)
int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
const char * smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out)
void smartlist_pqueue_assert_ok(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
int smartlist_contains_digest(const smartlist_t *sl, const char *element)
void smartlist_uniq_digests256(smartlist_t *sl)
void smartlist_add_vasprintf(struct smartlist_t *sl, const char *pattern, va_list args)
int smartlist_contains_string_case(const smartlist_t *sl, const char *element)
static int compare_digests_(const void **_a, const void **_b)
void smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern,...)
int smartlist_pos(const smartlist_t *sl, const void *element)
void smartlist_reverse(smartlist_t *sl)
void * smartlist_bsearch(const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member))
int smartlist_contains_int_as_string(const smartlist_t *sl, int num)
const uint8_t * smartlist_get_most_frequent_digest256(smartlist_t *sl)
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
void smartlist_uniq_strings(smartlist_t *sl)
void smartlist_sort_strings(smartlist_t *sl)
static int compare_ptrs_(const void **_a, const void **_b)
static int compare_digests256_(const void **_a, const void **_b)
char * smartlist_join_strings2(smartlist_t *sl, const char *join, size_t join_len, int terminate, size_t *len_out)
void smartlist_pqueue_add(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, void *item)
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
int smartlist_contains_string(const smartlist_t *sl, const char *element)
static int compare_string_ptrs_(const void **_a, const void **_b)
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
void smartlist_sort(smartlist_t *sl, int(*compare)(const void **a, const void **b))
const char * smartlist_get_most_frequent_string(smartlist_t *sl)
int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2)
void smartlist_pqueue_remove(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, void *item)
int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member), int *found_out)
static void smartlist_heapify(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, int idx)
void smartlist_sort_pointers(smartlist_t *sl)
int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
int smartlist_string_pos(const smartlist_t *sl, const char *element)
void smartlist_uniq(smartlist_t *sl, int(*compare)(const void **a, const void **b), void(*free_fn)(void *a))
int smartlist_contains(const smartlist_t *sl, const void *element)
void smartlist_add(smartlist_t *sl, void *element)
void smartlist_remove(smartlist_t *sl, const void *element)
void smartlist_del_keeporder(smartlist_t *sl, int idx)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
Macros to manage assertions, fatal and non-fatal.
Header for util_string.c.