aboutsummaryrefslogtreecommitdiff
path: root/src/common/container.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/container.h')
-rw-r--r--src/common/container.h92
1 files changed, 50 insertions, 42 deletions
diff --git a/src/common/container.h b/src/common/container.h
index dab3b83f3..0d31f2093 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -1,12 +1,13 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2012, The Tor Project, Inc. */
+ * Copyright (c) 2007-2013, The Tor Project, Inc. */
/* See LICENSE for licensing information */
-#ifndef _TOR_CONTAINER_H
-#define _TOR_CONTAINER_H
+#ifndef TOR_CONTAINER_H
+#define TOR_CONTAINER_H
#include "util.h"
+#include "siphash.h"
/** A resizeable list of pointers, with associated helpful functionality.
*
@@ -35,13 +36,14 @@ void smartlist_remove(smartlist_t *sl, const void *element);
void *smartlist_pop_last(smartlist_t *sl);
void smartlist_reverse(smartlist_t *sl);
void smartlist_string_remove(smartlist_t *sl, const char *element);
-int smartlist_isin(const smartlist_t *sl, const void *element);
-int smartlist_string_isin(const smartlist_t *sl, const char *element);
+int smartlist_contains(const smartlist_t *sl, const void *element);
+int smartlist_contains_string(const smartlist_t *sl, const char *element);
int smartlist_string_pos(const smartlist_t *, const char *elt);
-int smartlist_string_isin_case(const smartlist_t *sl, const char *element);
-int smartlist_string_num_isin(const smartlist_t *sl, int num);
+int smartlist_contains_string_case(const smartlist_t *sl, const char *element);
+int smartlist_contains_int_as_string(const smartlist_t *sl, int num);
int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2);
-int smartlist_digest_isin(const smartlist_t *sl, const char *element);
+int smartlist_contains_digest(const smartlist_t *sl, const char *element);
+int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2);
int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2);
void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2);
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2);
@@ -101,6 +103,7 @@ void smartlist_uniq(smartlist_t *sl,
void smartlist_sort_strings(smartlist_t *sl);
void smartlist_sort_digests(smartlist_t *sl);
void smartlist_sort_digests256(smartlist_t *sl);
+void smartlist_sort_pointers(smartlist_t *sl);
char *smartlist_get_most_frequent_string(smartlist_t *sl);
char *smartlist_get_most_frequent_digest256(smartlist_t *sl);
@@ -471,64 +474,74 @@ void* strmap_remove_lc(strmap_t *map, const char *key);
#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \
typedef struct maptype maptype; \
typedef struct prefix##iter_t prefix##iter_t; \
- static INLINE maptype* prefix##new(void) \
+ ATTR_UNUSED static INLINE maptype* \
+ prefix##new(void) \
{ \
return (maptype*)digestmap_new(); \
} \
- static INLINE digestmap_t* prefix##to_digestmap(maptype *map) \
+ ATTR_UNUSED static INLINE digestmap_t* \
+ prefix##to_digestmap(maptype *map) \
{ \
return (digestmap_t*)map; \
} \
- static INLINE valtype* prefix##get(maptype *map, const char *key) \
+ ATTR_UNUSED static INLINE valtype* \
+ prefix##get(maptype *map, const char *key) \
{ \
return (valtype*)digestmap_get((digestmap_t*)map, key); \
} \
- static INLINE valtype* prefix##set(maptype *map, const char *key, \
- valtype *val) \
+ ATTR_UNUSED static INLINE valtype* \
+ prefix##set(maptype *map, const char *key, valtype *val) \
{ \
return (valtype*)digestmap_set((digestmap_t*)map, key, val); \
} \
- static INLINE valtype* prefix##remove(maptype *map, const char *key) \
+ ATTR_UNUSED static INLINE valtype* \
+ prefix##remove(maptype *map, const char *key) \
{ \
return (valtype*)digestmap_remove((digestmap_t*)map, key); \
} \
- static INLINE void prefix##free(maptype *map, void (*free_val)(void*)) \
+ ATTR_UNUSED static INLINE void \
+ prefix##free(maptype *map, void (*free_val)(void*)) \
{ \
digestmap_free((digestmap_t*)map, free_val); \
} \
- static INLINE int prefix##isempty(maptype *map) \
+ ATTR_UNUSED static INLINE int \
+ prefix##isempty(maptype *map) \
{ \
return digestmap_isempty((digestmap_t*)map); \
} \
- static INLINE int prefix##size(maptype *map) \
+ ATTR_UNUSED static INLINE int \
+ prefix##size(maptype *map) \
{ \
return digestmap_size((digestmap_t*)map); \
} \
- static INLINE prefix##iter_t *prefix##iter_init(maptype *map) \
+ ATTR_UNUSED static INLINE \
+ prefix##iter_t *prefix##iter_init(maptype *map) \
{ \
return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \
} \
- static INLINE prefix##iter_t *prefix##iter_next(maptype *map, \
- prefix##iter_t *iter) \
+ ATTR_UNUSED static INLINE \
+ prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter) \
{ \
return (prefix##iter_t*) digestmap_iter_next( \
(digestmap_t*)map, (digestmap_iter_t*)iter); \
} \
- static INLINE prefix##iter_t *prefix##iter_next_rmv(maptype *map, \
- prefix##iter_t *iter) \
+ ATTR_UNUSED static INLINE prefix##iter_t* \
+ prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter) \
{ \
return (prefix##iter_t*) digestmap_iter_next_rmv( \
(digestmap_t*)map, (digestmap_iter_t*)iter); \
} \
- static INLINE void prefix##iter_get(prefix##iter_t *iter, \
- const char **keyp, \
- valtype **valp) \
+ ATTR_UNUSED static INLINE void \
+ prefix##iter_get(prefix##iter_t *iter, \
+ const char **keyp, \
+ valtype **valp) \
{ \
void *v; \
digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \
*valp = v; \
} \
- static INLINE int prefix##iter_done(prefix##iter_t *iter) \
+ ATTR_UNUSED static INLINE int \
+ prefix##iter_done(prefix##iter_t *iter) \
{ \
return digestmap_iter_done((digestmap_iter_t*)iter); \
}
@@ -609,11 +622,11 @@ typedef struct {
static INLINE void
digestset_add(digestset_t *set, const char *digest)
{
- const uint32_t *p = (const uint32_t *)digest;
- const uint32_t d1 = p[0] + (p[1]>>16);
- const uint32_t d2 = p[1] + (p[2]>>16);
- const uint32_t d3 = p[2] + (p[3]>>16);
- const uint32_t d4 = p[3] + (p[0]>>16);
+ const uint64_t x = siphash24g(digest, 20);
+ const uint32_t d1 = (uint32_t) x;
+ const uint32_t d2 = (uint32_t)( (x>>16) + x);
+ const uint32_t d3 = (uint32_t)( (x>>32) + x);
+ const uint32_t d4 = (uint32_t)( (x>>48) + x);
bitarray_set(set->ba, BIT(d1));
bitarray_set(set->ba, BIT(d2));
bitarray_set(set->ba, BIT(d3));
@@ -623,13 +636,13 @@ digestset_add(digestset_t *set, const char *digest)
/** If <b>digest</b> is in <b>set</b>, return nonzero. Otherwise,
* <em>probably</em> return zero. */
static INLINE int
-digestset_isin(const digestset_t *set, const char *digest)
+digestset_contains(const digestset_t *set, const char *digest)
{
- const uint32_t *p = (const uint32_t *)digest;
- const uint32_t d1 = p[0] + (p[1]>>16);
- const uint32_t d2 = p[1] + (p[2]>>16);
- const uint32_t d3 = p[2] + (p[3]>>16);
- const uint32_t d4 = p[3] + (p[0]>>16);
+ const uint64_t x = siphash24g(digest, 20);
+ const uint32_t d1 = (uint32_t) x;
+ const uint32_t d2 = (uint32_t)( (x>>16) + x);
+ const uint32_t d3 = (uint32_t)( (x>>32) + x);
+ const uint32_t d4 = (uint32_t)( (x>>48) + x);
return bitarray_is_set(set->ba, BIT(d1)) &&
bitarray_is_set(set->ba, BIT(d2)) &&
bitarray_is_set(set->ba, BIT(d3)) &&
@@ -675,11 +688,6 @@ median_int32(int32_t *array, int n_elements)
{
return find_nth_int32(array, n_elements, (n_elements-1)/2);
}
-static INLINE long
-median_long(long *array, int n_elements)
-{
- return find_nth_long(array, n_elements, (n_elements-1)/2);
-}
#endif
generated by cgit v1.2.3 (git 2.25.4) at 2024-05-18 11:16:28 +0000