6 #ifndef TOR_CONTAINER_H 7 #define TOR_CONTAINER_H 32 #define smartlist_free(sl) FREE_AND_NULL(smartlist_t, smartlist_free_, (sl)) 56 #ifdef DEBUG_SMARTLIST 59 static inline int smartlist_len(
const smartlist_t *sl);
60 static inline int smartlist_len(
const smartlist_t *sl) {
62 return (sl)->num_used;
66 static inline void *smartlist_get(
const smartlist_t *sl,
int idx);
67 static inline void *smartlist_get(
const smartlist_t *sl,
int idx) {
73 static inline void smartlist_set(
smartlist_t *sl,
int idx,
void *val) {
80 #define smartlist_len(sl) ((sl)->num_used) 81 #define smartlist_get(sl, idx) ((sl)->list[idx]) 82 #define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val)) 87 static inline void smartlist_swap(
smartlist_t *sl,
int idx1,
int idx2)
90 void *elt = smartlist_get(sl, idx1);
91 smartlist_set(sl, idx1, smartlist_get(sl, idx2));
92 smartlist_set(sl, idx2, elt);
100 int (*compare)(
const void **a,
const void **b));
102 int (*compare)(
const void **a,
const void **b),
104 #define smartlist_get_most_frequent(sl, compare) \ 105 smartlist_get_most_frequent_((sl), (compare), NULL) 107 int (*compare)(
const void **a,
const void **b),
108 void (*free_fn)(
void *elt));
124 int (*compare)(
const void *key,
const void **member));
126 int (*compare)(
const void *key,
const void **member),
130 int (*compare)(
const void *a,
const void *b),
131 int idx_field_offset,
134 int (*compare)(
const void *a,
const void *b),
135 int idx_field_offset);
137 int (*compare)(
const void *a,
const void *b),
138 int idx_field_offset,
141 int (*compare)(
const void *a,
const void *b),
142 int idx_field_offset);
144 #define SPLIT_SKIP_SPACE 0x01 145 #define SPLIT_IGNORE_BLANK 0x02 146 #define SPLIT_STRIP_SPACE 0x04 150 size_t *len_out) ATTR_MALLOC;
152 size_t join_len,
int terminate,
size_t *len_out)
219 #define SMARTLIST_FOREACH_BEGIN(sl, type, var) \ 221 int var ## _sl_idx, var ## _sl_len=(sl)->num_used; \ 223 for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len; \ 224 ++var ## _sl_idx) { \ 225 var = (sl)->list[var ## _sl_idx]; 227 #define SMARTLIST_FOREACH_END(var) \ 229 (void) var ## _sl_idx; \ 240 #define SMARTLIST_FOREACH(sl, type, var, cmd) \ 241 SMARTLIST_FOREACH_BEGIN(sl,type,var) { \ 243 } SMARTLIST_FOREACH_END(var) 248 #define SMARTLIST_DEL_CURRENT(sl, var) \ 250 smartlist_del(sl, var ## _sl_idx); \ 258 #define SMARTLIST_DEL_CURRENT_KEEPORDER(sl, var) \ 260 smartlist_del_keeporder(sl, var ## _sl_idx); \ 269 #define SMARTLIST_REPLACE_CURRENT(sl, var, val) \ 271 smartlist_set(sl, var ## _sl_idx, val); \ 318 #define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, \ 319 cmpexpr, unmatched_var2) \ 321 int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used; \ 322 int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used; \ 323 int var1 ## _ ## var2 ## _cmp; \ 326 for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) { \ 327 var2 = (sl2)->list[var2##_sl_idx]; \ 328 while (var1##_sl_idx < var1##_sl_len) { \ 329 var1 = (sl1)->list[var1##_sl_idx]; \ 330 var1##_##var2##_cmp = (cmpexpr); \ 331 if (var1##_##var2##_cmp > 0) { \ 333 } else if (var1##_##var2##_cmp == 0) { \ 334 goto matched_##var2; \ 344 #define SMARTLIST_FOREACH_JOIN_END(var1, var2) \ 348 #define DECLARE_MAP_FNS(maptype, keytype, prefix) \ 349 typedef struct maptype maptype; \ 350 typedef struct prefix##entry_t *prefix##iter_t; \ 351 MOCK_DECL(maptype*, prefix##new, (void)); \ 352 void* prefix##set(maptype *map, keytype key, void *val); \ 353 void* prefix##get(const maptype *map, keytype key); \ 354 void* prefix##remove(maptype *map, keytype key); \ 355 MOCK_DECL(void, prefix##free_, (maptype *map, void (*free_val)(void*))); \ 356 int prefix##isempty(const maptype *map); \ 357 int prefix##size(const maptype *map); \ 358 prefix##iter_t *prefix##iter_init(maptype *map); \ 359 prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \ 360 prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \ 361 void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \ 362 int prefix##iter_done(prefix##iter_t *iter); \ 363 void prefix##assert_ok(const maptype *map) 366 DECLARE_MAP_FNS(strmap_t,
const char *, strmap_);
368 DECLARE_MAP_FNS(digestmap_t,
const char *, digestmap_);
371 DECLARE_MAP_FNS(digest256map_t,
const uint8_t *, digest256map_);
373 #define MAP_FREE_AND_NULL(maptype, map, fn) \ 375 maptype ## _free_((map), (fn)); \ 379 #define strmap_free(map, fn) MAP_FREE_AND_NULL(strmap, (map), (fn)) 380 #define digestmap_free(map, fn) MAP_FREE_AND_NULL(digestmap, (map), (fn)) 381 #define digest256map_free(map, fn) MAP_FREE_AND_NULL(digest256map, (map), (fn)) 383 #undef DECLARE_MAP_FNS 409 #define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \ 411 prefix##iter_t *keyvar##_iter; \ 412 for (keyvar##_iter = prefix##iter_init(map); \ 413 !prefix##iter_done(keyvar##_iter); \ 414 keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) { \ 416 void *valvar##_voidp; \ 418 prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ 419 valvar = valvar##_voidp; 449 #define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \ 451 prefix##iter_t *keyvar##_iter; \ 452 int keyvar##_del=0; \ 453 for (keyvar##_iter = prefix##iter_init(map); \ 454 !prefix##iter_done(keyvar##_iter); \ 455 keyvar##_iter = keyvar##_del ? \ 456 prefix##iter_next_rmv(map, keyvar##_iter) : \ 457 prefix##iter_next(map, keyvar##_iter)) { \ 459 void *valvar##_voidp; \ 462 prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ 463 valvar = valvar##_voidp; 467 #define MAP_DEL_CURRENT(keyvar) \ 473 #define MAP_FOREACH_END } STMT_END ; 481 #define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \ 482 MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar) 492 #define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ 493 MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar) 495 #define DIGESTMAP_FOREACH_END MAP_FOREACH_END 497 #define DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \ 498 MAP_FOREACH(digest256map_, map, const uint8_t *, keyvar, valtype, valvar) 499 #define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ 500 MAP_FOREACH_MODIFY(digest256map_, map, const uint8_t *, \ 501 keyvar, valtype, valvar) 502 #define DIGEST256MAP_FOREACH_END MAP_FOREACH_END 504 #define STRMAP_FOREACH(map, keyvar, valtype, valvar) \ 505 MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar) 506 #define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ 507 MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar) 508 #define STRMAP_FOREACH_END MAP_FOREACH_END 510 void*
strmap_set_lc(strmap_t *map,
const char *key,
void *val);
514 #define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \ 515 typedef struct maptype maptype; \ 516 typedef struct prefix##iter_t *prefix##iter_t; \ 517 ATTR_UNUSED static inline maptype* \ 520 return (maptype*)digestmap_new(); \ 522 ATTR_UNUSED static inline digestmap_t* \ 523 prefix##to_digestmap(maptype *map) \ 525 return (digestmap_t*)map; \ 527 ATTR_UNUSED static inline valtype* \ 528 prefix##get(maptype *map, const char *key) \ 530 return (valtype*)digestmap_get((digestmap_t*)map, key); \ 532 ATTR_UNUSED static inline valtype* \ 533 prefix##set(maptype *map, const char *key, valtype *val) \ 535 return (valtype*)digestmap_set((digestmap_t*)map, key, val); \ 537 ATTR_UNUSED static inline valtype* \ 538 prefix##remove(maptype *map, const char *key) \ 540 return (valtype*)digestmap_remove((digestmap_t*)map, key); \ 542 ATTR_UNUSED static inline void \ 543 prefix##f##ree_(maptype *map, void (*free_val)(void*)) \ 545 digestmap_free_((digestmap_t*)map, free_val); \ 547 ATTR_UNUSED static inline int \ 548 prefix##isempty(maptype *map) \ 550 return digestmap_isempty((digestmap_t*)map); \ 552 ATTR_UNUSED static inline int \ 553 prefix##size(maptype *map) \ 555 return digestmap_size((digestmap_t*)map); \ 557 ATTR_UNUSED static inline \ 558 prefix##iter_t *prefix##iter_init(maptype *map) \ 560 return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \ 562 ATTR_UNUSED static inline \ 563 prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter) \ 565 return (prefix##iter_t*) digestmap_iter_next( \ 566 (digestmap_t*)map, (digestmap_iter_t*)iter); \ 568 ATTR_UNUSED static inline prefix##iter_t* \ 569 prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter) \ 571 return (prefix##iter_t*) digestmap_iter_next_rmv( \ 572 (digestmap_t*)map, (digestmap_iter_t*)iter); \ 574 ATTR_UNUSED static inline void \ 575 prefix##iter_get(prefix##iter_t *iter, \ 580 digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \ 583 ATTR_UNUSED static inline int \ 584 prefix##iter_done(prefix##iter_t *iter) \ 586 return digestmap_iter_done((digestmap_iter_t*)iter); \ 590 #define BITARRAY_SHIFT 5 591 #elif SIZEOF_INT == 8 592 #define BITARRAY_SHIFT 6 594 #error "int is neither 4 nor 8 bytes. I can't deal with that." 596 #define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1) 599 typedef unsigned int bitarray_t;
601 static inline bitarray_t *
602 bitarray_init_zero(
unsigned int n_bits)
605 size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
606 return tor_calloc(sz,
sizeof(
unsigned int));
611 static inline bitarray_t *
612 bitarray_expand(bitarray_t *ba,
613 unsigned int n_bits_old,
unsigned int n_bits_new)
615 size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT;
616 size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT;
618 if (sz_new <= sz_old)
620 ptr = tor_reallocarray(ba, sz_new,
sizeof(
unsigned int));
623 memset(ptr+sz_old*
sizeof(
unsigned int), 0,
624 (sz_new-sz_old)*
sizeof(
unsigned int));
625 return (bitarray_t*) ptr;
629 bitarray_free_(bitarray_t *ba)
633 #define bitarray_free(ba) FREE_AND_NULL(bitarray_t, bitarray_free_, (ba)) 637 bitarray_set(bitarray_t *b,
int bit)
639 b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
643 bitarray_clear(bitarray_t *b,
int bit)
645 b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
649 static inline unsigned int 650 bitarray_is_set(bitarray_t *b,
int bit)
652 return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
662 #define BIT(n) ((n) & set->mask) 665 digestset_add(
digestset_t *
set,
const char *digest)
667 const uint64_t x = siphash24g(digest, 20);
668 const uint32_t d1 = (uint32_t) x;
669 const uint32_t
d2 = (uint32_t)( (x>>16) + x);
670 const uint32_t d3 = (uint32_t)( (x>>32) + x);
671 const uint32_t d4 = (uint32_t)( (x>>48) + x);
672 bitarray_set(set->ba,
BIT(d1));
673 bitarray_set(set->ba,
BIT(d2));
674 bitarray_set(set->ba,
BIT(d3));
675 bitarray_set(set->ba,
BIT(d4));
681 digestset_contains(
const digestset_t *
set,
const char *digest)
683 const uint64_t x = siphash24g(digest, 20);
684 const uint32_t d1 = (uint32_t) x;
685 const uint32_t
d2 = (uint32_t)( (x>>16) + x);
686 const uint32_t d3 = (uint32_t)( (x>>32) + x);
687 const uint32_t d4 = (uint32_t)( (x>>48) + x);
688 return bitarray_is_set(set->ba,
BIT(d1)) &&
689 bitarray_is_set(set->ba,
BIT(d2)) &&
690 bitarray_is_set(set->ba,
BIT(d3)) &&
691 bitarray_is_set(set->ba,
BIT(d4));
697 #define digestset_free(set) FREE_AND_NULL(digestset_t, digestset_free_, (set)) 703 int find_nth_int(
int *array,
int n_elements,
int nth);
704 time_t find_nth_time(time_t *array,
int n_elements,
int nth);
705 double find_nth_double(
double *array,
int n_elements,
int nth);
706 int32_t find_nth_int32(int32_t *array,
int n_elements,
int nth);
707 uint32_t find_nth_uint32(uint32_t *array,
int n_elements,
int nth);
708 long find_nth_long(
long *array,
int n_elements,
int nth);
710 median_int(
int *array,
int n_elements)
712 return find_nth_int(array, n_elements, (n_elements-1)/2);
715 median_time(time_t *array,
int n_elements)
717 return find_nth_time(array, n_elements, (n_elements-1)/2);
720 median_double(
double *array,
int n_elements)
722 return find_nth_double(array, n_elements, (n_elements-1)/2);
724 static inline uint32_t
725 median_uint32(uint32_t *array,
int n_elements)
727 return find_nth_uint32(array, n_elements, (n_elements-1)/2);
729 static inline int32_t
730 median_int32(int32_t *array,
int n_elements)
732 return find_nth_int32(array, n_elements, (n_elements-1)/2);
735 static inline uint32_t
736 third_quartile_uint32(uint32_t *array,
int n_elements)
738 return find_nth_uint32(array, n_elements, (n_elements*3)/4);
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, int flags, int max)
Definition: container.c:434
void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
Definition: container.c:344
int smartlist_contains_digest(const smartlist_t *sl, const char *element)
Definition: container.c:318
void smartlist_sort_digests(smartlist_t *sl)
Definition: container.c:1044
int smartlist_string_pos(const smartlist_t *sl, const char *element)
Definition: container.c:228
int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
Definition: container.c:279
void smartlist_pqueue_remove(smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset, void *item)
Definition: container.c:999
void * strmap_get_lc(const strmap_t *map, const char *key)
Definition: container.c:1455
int mask
Definition: container.h:657
void smartlist_sort_strings(smartlist_t *sl)
Definition: container.c:769
void smartlist_insert(smartlist_t *sl, int idx, void *val)
Definition: container.c:400
int smartlist_pos(const smartlist_t *sl, const void *element)
Definition: container.c:241
const char * smartlist_get_most_frequent_string(smartlist_t *sl)
Definition: container.c:776
#define tor_assert(expr)
Definition: util_bug.h:68
MOCK_DECL(int, router_have_minimum_dir_info,(void))
Definition: container.h:18
int smartlist_contains(const smartlist_t *sl, const void *element)
Definition: container.c:202
void smartlist_clear(smartlist_t *sl)
Definition: container.c:56
void ** list
Definition: container.h:24
void smartlist_uniq(smartlist_t *sl, int(*compare)(const void **a, const void **b), void(*free_fn)(void *a))
Definition: container.c:610
char * smartlist_join_strings2(smartlist_t *sl, const char *join, size_t join_len, int terminate, size_t *len_out)
Definition: container.c:511
Definition: container.h:656
void smartlist_uniq_strings(smartlist_t *sl)
Definition: container.c:794
int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
Definition: container.c:331
void smartlist_remove(smartlist_t *sl, const void *element)
Definition: container.c:122
int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2)
Definition: container.c:298
void * smartlist_get_most_frequent_(const smartlist_t *sl, int(*compare)(const void **a, const void **b), int *count_out)
Definition: container.c:568
void smartlist_string_remove(smartlist_t *sl, const char *element)
Definition: container.c:184
int smartlist_contains_string(const smartlist_t *sl, const char *element)
Definition: container.c:215
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset)
Definition: container.c:975
int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member), int *found_out)
Definition: container.c:648
int smartlist_contains_int_as_string(const smartlist_t *sl, int num)
Definition: container.c:269
void smartlist_sort(smartlist_t *sl, int(*compare)(const void **a, const void **b))
Definition: container.c:554
int smartlist_contains_string_case(const smartlist_t *sl, const char *element)
Definition: container.c:255
void smartlist_remove_keeporder(smartlist_t *sl, const void *element)
Definition: container.c:138
void smartlist_pqueue_add(smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset, void *item)
Definition: container.c:946
bitarray_t * ba
Definition: container.h:659
void * smartlist_bsearch(smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member))
Definition: container.c:631
void smartlist_del_keeporder(smartlist_t *sl, int idx)
Definition: container.c:384
void digestset_free_(digestset_t *set)
Definition: container.c:1535
void * smartlist_pop_last(smartlist_t *sl)
Definition: container.c:156
const char * smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out)
Definition: container.c:786
void * strmap_set_lc(strmap_t *map, const char *key, void *val)
Definition: container.c:1441
void smartlist_uniq_digests(smartlist_t *sl)
Definition: container.c:1052
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
Definition: container.c:359
void smartlist_add(smartlist_t *sl, void *element)
Definition: container.c:99
void smartlist_del(smartlist_t *sl, int idx)
Definition: container.c:370
void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
Definition: container.c:107
void smartlist_sort_pointers(smartlist_t *sl)
Definition: container.c:814
#define BIT(set, val)
Definition: address_set.c:79
void smartlist_uniq_digests256(smartlist_t *sl)
Definition: container.c:1083
void * strmap_remove_lc(strmap_t *map, const char *key)
Definition: container.c:1467
const uint8_t * smartlist_get_most_frequent_digest256(smartlist_t *sl)
Definition: container.c:1074
void smartlist_sort_digests256(smartlist_t *sl)
Definition: container.c:1066
#define tor_free(p)
Definition: util.h:95
digestset_t * digestset_new(int max_elements)
Definition: container.c:1514
void smartlist_reverse(smartlist_t *sl)
Definition: container.c:169
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
Definition: container.c:499
void smartlist_pqueue_assert_ok(smartlist_t *sl, int(*compare)(const void *a, const void *b), int idx_field_offset)
Definition: container.c:1023