diff options
| -rw-r--r-- | src/common/container.c | 26 | ||||
| -rw-r--r-- | src/common/container.h | 21 | ||||
| -rw-r--r-- | src/common/crypto.c | 15 | ||||
| -rw-r--r-- | src/common/crypto.h | 1 | ||||
| -rw-r--r-- | src/common/ht.h | 8 |
5 files changed, 49 insertions, 22 deletions
diff --git a/src/common/container.c b/src/common/container.c index e3523735d..d5785b732 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -658,28 +658,28 @@ DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_); /** Helper: compare strmap_entry_t objects by key value. */ static INLINE int -strmap_entries_eq(strmap_entry_t *a, strmap_entry_t *b) +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(strmap_entry_t *a) +strmap_entry_hash(const strmap_entry_t *a) { return ht_string_hash(a->key); } /** Helper: compare digestmap_entry_t objects by key value. */ static INLINE int -digestmap_entries_eq(digestmap_entry_t *a, digestmap_entry_t *b) +digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b) { return !memcmp(a->key, b->key, DIGEST_LEN); } /** Helper: return a hash value for a digest_map_t. */ static INLINE unsigned int -digestmap_entry_hash(digestmap_entry_t *a) +digestmap_entry_hash(const digestmap_entry_t *a) { uint32_t *p = (uint32_t*)a->key; return ht_improve_hash(p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]); @@ -780,7 +780,7 @@ digestmap_set(digestmap_t *map, const char *key, void *val) * value is set. */ void * -strmap_get(strmap_t *map, const char *key) +strmap_get(const strmap_t *map, const char *key) { strmap_entry_t *resolve; strmap_entry_t search; @@ -797,7 +797,7 @@ strmap_get(strmap_t *map, const char *key) /** Like strmap_get() above but for digestmaps. */ void * -digestmap_get(digestmap_t *map, const char *key) +digestmap_get(const digestmap_t *map, const char *key) { digestmap_entry_t *resolve; digestmap_entry_t search; @@ -874,7 +874,7 @@ strmap_set_lc(strmap_t *map, const char *key, void *val) /** Same as strmap_get, but first converts <b>key</b> to lowercase. */ void * -strmap_get_lc(strmap_t *map, const char *key) +strmap_get_lc(const strmap_t *map, const char *key) { void *v; char *lc_key = tor_strdup(key); @@ -1058,38 +1058,38 @@ digestmap_free(digestmap_t *map, void (*free_val)(void*)) } void -strmap_assert_ok(strmap_t *map) +strmap_assert_ok(const strmap_t *map) { tor_assert(!_strmap_impl_HT_REP_IS_BAD(&map->head)); } void -digestmap_assert_ok(digestmap_t *map) +digestmap_assert_ok(const digestmap_t *map) { tor_assert(!_digestmap_impl_HT_REP_IS_BAD(&map->head)); } /** Return true iff <b>map</b> has no entries. */ int -strmap_isempty(strmap_t *map) +strmap_isempty(const strmap_t *map) { return HT_EMPTY(&map->head); } int -digestmap_isempty(digestmap_t *map) +digestmap_isempty(const digestmap_t *map) { return HT_EMPTY(&map->head); } /** Return the number of items in <b>map</b>. */ int -strmap_size(strmap_t *map) +strmap_size(const strmap_t *map) { return HT_SIZE(&map->head); } int -digestmap_size(digestmap_t *map) +digestmap_size(const digestmap_t *map) { return HT_SIZE(&map->head); } diff --git a/src/common/container.h b/src/common/container.h index b07f92b63..5da0fbc85 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -78,6 +78,17 @@ extern INLINE void smartlist_set(smartlist_t *sl, int idx, void *val) { #define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val)) #endif +void smartlist_swap(smartlist_t *sl, int idx1, int idx2); +/**DOCDOC*/ +extern INLINE void smartlist_swap(smartlist_t *sl, int idx1, int idx2) +{ + if (idx1 != idx2) { + void *elt = smartlist_get(sl, idx1); + smartlist_set(sl, idx1, smartlist_get(sl, idx2)); + smartlist_set(sl, idx2, elt); + } +} + void smartlist_del(smartlist_t *sl, int idx); void smartlist_del_keeporder(smartlist_t *sl, int idx); void smartlist_insert(smartlist_t *sl, int idx, void *val); @@ -171,24 +182,24 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join, typedef struct prefix##entry_t *prefix##iter_t; \ maptype* prefix##new(void); \ void* prefix##set(maptype *map, keytype key, void *val); \ - void* prefix##get(maptype *map, keytype key); \ + void* prefix##get(const maptype *map, keytype key); \ void* prefix##remove(maptype *map, keytype key); \ void prefix##free(maptype *map, void (*free_val)(void*)); \ - int prefix##isempty(maptype *map); \ - int prefix##size(maptype *map); \ + int prefix##isempty(const maptype *map); \ + int prefix##size(const maptype *map); \ prefix##iter_t *prefix##iter_init(maptype *map); \ prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \ prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \ void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \ int prefix##iter_done(prefix##iter_t *iter); \ - void prefix##assert_ok(maptype *map); + void prefix##assert_ok(const maptype *map); /* Map from const char * to void *. Implemented with a hash table. */ DECLARE_MAP_FNS(strmap_t, const char *, strmap_); DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_); void* strmap_set_lc(strmap_t *map, const char *key, void *val); -void* strmap_get_lc(strmap_t *map, const char *key); +void* strmap_get_lc(const strmap_t *map, const char *key); void* strmap_remove_lc(strmap_t *map, const char *key); #endif diff --git a/src/common/crypto.c b/src/common/crypto.c index 40cb5fafa..bcb8a375a 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -1677,6 +1677,21 @@ smartlist_choose(const smartlist_t *sl) return NULL; /* no elements to choose from */ } +/** Scramble the elements of sl into a random order. */ +void +smartlist_shuffle(smartlist_t *sl) +{ + int i; + /* From the end of the list to the front, choose at random from the + positions we haven't looked at yet, and swap that position into the + current position. Remember to give "no swap" the same probability as + any other swap. */ + for (i = smartlist_len(sl)-1; i > 0; --i) { + int j = crypto_rand_int(i+1); + smartlist_swap(sl, i, j); + } +} + /** Base-64 encode <b>srclen</b> bytes of data from <b>src</b>. Write * the result into <b>dest</b>, if it will fit within <b>destlen</b> * bytes. Return the number of bytes written on success; -1 if diff --git a/src/common/crypto.h b/src/common/crypto.h index c85fc118e..62c7674bb 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -157,6 +157,7 @@ uint64_t crypto_rand_uint64(uint64_t max); struct smartlist_t; void *smartlist_choose(const struct smartlist_t *sl); +void smartlist_shuffle(struct smartlist_t *sl); int base64_encode(char *dest, size_t destlen, const char *src, size_t srclen); int base64_decode(char *dest, size_t destlen, const char *src, size_t srclen); diff --git a/src/common/ht.h b/src/common/ht.h index 11b61ed34..e6afdd88f 100644 --- a/src/common/ht.h +++ b/src/common/ht.h @@ -91,7 +91,7 @@ ht_string_hash(const char *s) #define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ void name##_HT_CLEAR(struct name *ht); \ - int _##name##_HT_REP_IS_BAD(struct name *ht); \ + int _##name##_HT_REP_IS_BAD(const struct name *ht); \ static INLINE void \ name##_HT_INIT(struct name *head) { \ head->hth_table_length = 0; \ @@ -119,11 +119,11 @@ ht_string_hash(const char *s) /* Return a pointer to the element in the table 'head' matching 'elm', \ * or NULL if no such element exists */ \ static INLINE struct type * \ - name##_HT_FIND(struct name *head, struct type *elm) \ + name##_HT_FIND(const struct name *head, struct type *elm) \ { \ struct type **p; \ _HT_SET_HASH(elm, field, hashfn); \ - p = _##name##_HT_FIND_P(head, elm); \ + p = _##name##_HT_FIND_P((struct name *)head, elm); \ return p ? *p : NULL; \ } \ /* Insert the element 'elm' into the table 'head'. Do not call this \ @@ -349,7 +349,7 @@ ht_string_hash(const char *s) /* Debugging helper: return false iff the representation of 'head' is \ * internally consistent. */ \ int \ - _##name##_HT_REP_IS_BAD(struct name *head) \ + _##name##_HT_REP_IS_BAD(const struct name *head) \ { \ unsigned n, i; \ struct type *elm; \ |