1 /* Copyright (c) 2003-2004, Roger Dingledine
2 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 * Copyright (c) 2007-2009, The Tor Project, Inc. */
4 /* See LICENSE for licensing information */
8 * \brief Implements a smartlist (a resizable array) along
9 * with helper functions to use smartlists. Also includes
10 * hash table implementations of a string-to-void* map, and of
11 * a digest-to-void* map.
17 #include "container.h"
26 /** All newly allocated smartlists have this capacity. */
27 #define SMARTLIST_DEFAULT_CAPACITY 16
29 /** Allocate and return an empty smartlist.
32 smartlist_create(void)
34 smartlist_t
*sl
= tor_malloc(sizeof(smartlist_t
));
36 sl
->capacity
= SMARTLIST_DEFAULT_CAPACITY
;
37 sl
->list
= tor_malloc(sizeof(void *) * sl
->capacity
);
41 /** Deallocate a smartlist. Does not release storage associated with the
45 smartlist_free(smartlist_t
*sl
)
47 tor_assert(sl
!= NULL
);
52 /** Remove all elements from the list.
55 smartlist_clear(smartlist_t
*sl
)
60 /** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
62 smartlist_ensure_capacity(smartlist_t
*sl
, int size
)
64 if (size
> sl
->capacity
) {
65 int higher
= sl
->capacity
* 2;
68 tor_assert(higher
> 0); /* detect overflow */
69 sl
->capacity
= higher
;
70 sl
->list
= tor_realloc(sl
->list
, sizeof(void*)*sl
->capacity
);
74 /** Append element to the end of the list. */
76 smartlist_add(smartlist_t
*sl
, void *element
)
78 smartlist_ensure_capacity(sl
, sl
->num_used
+1);
79 sl
->list
[sl
->num_used
++] = element
;
82 /** Append each element from S2 to the end of S1. */
84 smartlist_add_all(smartlist_t
*s1
, const smartlist_t
*s2
)
86 int new_size
= s1
->num_used
+ s2
->num_used
;
87 tor_assert(new_size
>= s1
->num_used
); /* check for overflow. */
88 smartlist_ensure_capacity(s1
, new_size
);
89 memcpy(s1
->list
+ s1
->num_used
, s2
->list
, s2
->num_used
*sizeof(void*));
90 s1
->num_used
= new_size
;
93 /** Remove all elements E from sl such that E==element. Preserve
94 * the order of any elements before E, but elements after E can be
98 smartlist_remove(smartlist_t
*sl
, const void *element
)
103 for (i
=0; i
< sl
->num_used
; i
++)
104 if (sl
->list
[i
] == element
) {
105 sl
->list
[i
] = sl
->list
[--sl
->num_used
]; /* swap with the end */
106 i
--; /* so we process the new i'th element */
110 /** If <b>sl</b> is nonempty, remove and return the final element. Otherwise,
113 smartlist_pop_last(smartlist_t
*sl
)
117 return sl
->list
[--sl
->num_used
];
122 /** Reverse the order of the items in <b>sl</b>. */
124 smartlist_reverse(smartlist_t
*sl
)
129 for (i
= 0, j
= sl
->num_used
-1; i
< j
; ++i
, --j
) {
131 sl
->list
[i
] = sl
->list
[j
];
136 /** If there are any strings in sl equal to element, remove and free them.
137 * Does not preserve order. */
139 smartlist_string_remove(smartlist_t
*sl
, const char *element
)
144 for (i
= 0; i
< sl
->num_used
; ++i
) {
145 if (!strcmp(element
, sl
->list
[i
])) {
146 tor_free(sl
->list
[i
]);
147 sl
->list
[i
] = sl
->list
[--sl
->num_used
]; /* swap with the end */
148 i
--; /* so we process the new i'th element */
153 /** Return true iff some element E of sl has E==element.
156 smartlist_isin(const smartlist_t
*sl
, const void *element
)
159 for (i
=0; i
< sl
->num_used
; i
++)
160 if (sl
->list
[i
] == element
)
165 /** Return true iff <b>sl</b> has some element E such that
166 * !strcmp(E,<b>element</b>)
169 smartlist_string_isin(const smartlist_t
*sl
, const char *element
)
173 for (i
=0; i
< sl
->num_used
; i
++)
174 if (strcmp((const char*)sl
->list
[i
],element
)==0)
179 /** If <b>element</b> is equal to an element of <b>sl</b>, return that
180 * element's index. Otherwise, return -1. */
182 smartlist_string_pos(const smartlist_t
*sl
, const char *element
)
186 for (i
=0; i
< sl
->num_used
; i
++)
187 if (strcmp((const char*)sl
->list
[i
],element
)==0)
192 /** Return true iff <b>sl</b> has some element E such that
193 * !strcasecmp(E,<b>element</b>)
196 smartlist_string_isin_case(const smartlist_t
*sl
, const char *element
)
200 for (i
=0; i
< sl
->num_used
; i
++)
201 if (strcasecmp((const char*)sl
->list
[i
],element
)==0)
206 /** Return true iff <b>sl</b> has some element E such that E is equal
207 * to the decimal encoding of <b>num</b>.
210 smartlist_string_num_isin(const smartlist_t
*sl
, int num
)
213 tor_snprintf(buf
,sizeof(buf
),"%d", num
);
214 return smartlist_string_isin(sl
, buf
);
217 /** Return true iff <b>sl</b> has some element E such that
218 * !memcmp(E,<b>element</b>,DIGEST_LEN)
221 smartlist_digest_isin(const smartlist_t
*sl
, const char *element
)
225 for (i
=0; i
< sl
->num_used
; i
++)
226 if (memcmp((const char*)sl
->list
[i
],element
,DIGEST_LEN
)==0)
231 /** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
234 smartlist_overlap(const smartlist_t
*sl1
, const smartlist_t
*sl2
)
237 for (i
=0; i
< sl2
->num_used
; i
++)
238 if (smartlist_isin(sl1
, sl2
->list
[i
]))
243 /** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
244 * Does not preserve the order of sl1.
247 smartlist_intersect(smartlist_t
*sl1
, const smartlist_t
*sl2
)
250 for (i
=0; i
< sl1
->num_used
; i
++)
251 if (!smartlist_isin(sl2
, sl1
->list
[i
])) {
252 sl1
->list
[i
] = sl1
->list
[--sl1
->num_used
]; /* swap with the end */
253 i
--; /* so we process the new i'th element */
257 /** Remove every element E of sl1 such that smartlist_isin(sl2,E).
258 * Does not preserve the order of sl1.
261 smartlist_subtract(smartlist_t
*sl1
, const smartlist_t
*sl2
)
264 for (i
=0; i
< sl2
->num_used
; i
++)
265 smartlist_remove(sl1
, sl2
->list
[i
]);
268 /** Remove the <b>idx</b>th element of sl; if idx is not the last
269 * element, swap the last element of sl into the <b>idx</b>th space.
270 * Return the old value of the <b>idx</b>th element.
273 smartlist_del(smartlist_t
*sl
, int idx
)
277 tor_assert(idx
< sl
->num_used
);
278 sl
->list
[idx
] = sl
->list
[--sl
->num_used
];
281 /** Remove the <b>idx</b>th element of sl; if idx is not the last element,
282 * moving all subsequent elements back one space. Return the old value
283 * of the <b>idx</b>th element.
286 smartlist_del_keeporder(smartlist_t
*sl
, int idx
)
290 tor_assert(idx
< sl
->num_used
);
292 if (idx
< sl
->num_used
)
293 memmove(sl
->list
+idx
, sl
->list
+idx
+1, sizeof(void*)*(sl
->num_used
-idx
));
296 /** Insert the value <b>val</b> as the new <b>idx</b>th element of
297 * <b>sl</b>, moving all items previously at <b>idx</b> or later
301 smartlist_insert(smartlist_t
*sl
, int idx
, void *val
)
305 tor_assert(idx
<= sl
->num_used
);
306 if (idx
== sl
->num_used
) {
307 smartlist_add(sl
, val
);
309 smartlist_ensure_capacity(sl
, sl
->num_used
+1);
310 /* Move other elements away */
311 if (idx
< sl
->num_used
)
312 memmove(sl
->list
+ idx
+ 1, sl
->list
+ idx
,
313 sizeof(void*)*(sl
->num_used
-idx
));
320 * Split a string <b>str</b> along all occurrences of <b>sep</b>,
321 * adding the split strings, in order, to <b>sl</b>.
323 * If <b>flags</b>&SPLIT_SKIP_SPACE is true, remove initial and
324 * trailing space from each entry.
325 * If <b>flags</b>&SPLIT_IGNORE_BLANK is true, remove any entries
327 * If <b>flags</b>&SPLIT_STRIP_SPACE is true, strip spaces from each
330 * If max>0, divide the string into no more than <b>max</b> pieces. If
331 * <b>sep</b> is NULL, split on any sequence of horizontal space.
334 smartlist_split_string(smartlist_t
*sl
, const char *str
, const char *sep
,
337 const char *cp
, *end
, *next
;
345 if (flags
&SPLIT_SKIP_SPACE
) {
346 while (TOR_ISSPACE(*cp
)) ++cp
;
349 if (max
>0 && n
== max
-1) {
350 end
= strchr(cp
,'\0');
352 end
= strstr(cp
,sep
);
354 end
= strchr(cp
,'\0');
356 for (end
= cp
; *end
&& *end
!= '\t' && *end
!= ' '; ++end
)
365 next
= end
+strlen(sep
);
368 while (*next
== '\t' || *next
== ' ')
372 if (flags
&SPLIT_SKIP_SPACE
) {
373 while (end
> cp
&& TOR_ISSPACE(*(end
-1)))
376 if (end
!= cp
|| !(flags
&SPLIT_IGNORE_BLANK
)) {
377 char *string
= tor_strndup(cp
, end
-cp
);
378 if (flags
&SPLIT_STRIP_SPACE
)
379 tor_strstrip(string
, " ");
380 smartlist_add(sl
, string
);
391 /** Allocate and return a new string containing the concatenation of
392 * the elements of <b>sl</b>, in order, separated by <b>join</b>. If
393 * <b>terminate</b> is true, also terminate the string with <b>join</b>.
394 * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
395 * the returned string. Requires that every element of <b>sl</b> is
396 * NUL-terminated string.
399 smartlist_join_strings(smartlist_t
*sl
, const char *join
,
400 int terminate
, size_t *len_out
)
402 return smartlist_join_strings2(sl
,join
,strlen(join
),terminate
,len_out
);
405 /** As smartlist_join_strings, but instead of separating/terminated with a
406 * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
407 * at <b>join</b>. (Useful for generating a sequence of NUL-terminated
411 smartlist_join_strings2(smartlist_t
*sl
, const char *join
,
412 size_t join_len
, int terminate
, size_t *len_out
)
416 char *r
= NULL
, *dst
, *src
;
424 for (i
= 0; i
< sl
->num_used
; ++i
) {
425 n
+= strlen(sl
->list
[i
]);
426 if (i
+1 < sl
->num_used
) /* avoid double-counting the last one */
429 dst
= r
= tor_malloc(n
+1);
430 for (i
= 0; i
< sl
->num_used
; ) {
431 for (src
= sl
->list
[i
]; *src
; )
433 if (++i
< sl
->num_used
) {
434 memcpy(dst
, join
, join_len
);
439 memcpy(dst
, join
, join_len
);
449 /** Sort the members of <b>sl</b> into an order defined by
450 * the ordering function <b>compare</b>, which returns less then 0 if a
451 * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
454 smartlist_sort(smartlist_t
*sl
, int (*compare
)(const void **a
, const void **b
))
458 qsort(sl
->list
, sl
->num_used
, sizeof(void*),
459 (int (*)(const void *,const void*))compare
);
462 /** Given a sorted smartlist <b>sl</b> and the comparison function used to
463 * sort it, remove all duplicate members. If free_fn is provided, calls
464 * free_fn on each duplicate. Otherwise, just removes them. Preserves order.
467 smartlist_uniq(smartlist_t
*sl
,
468 int (*compare
)(const void **a
, const void **b
),
469 void (*free_fn
)(void *a
))
472 for (i
=1; i
< sl
->num_used
; ++i
) {
473 if (compare((const void **)&(sl
->list
[i
-1]),
474 (const void **)&(sl
->list
[i
])) == 0) {
476 free_fn(sl
->list
[i
]);
477 smartlist_del_keeporder(sl
, i
--);
482 /** Assuming the members of <b>sl</b> are in order, return a pointer to the
483 * member that matches <b>key</b>. Ordering and matching are defined by a
484 * <b>compare</b> function that returns 0 on a match; less than 0 if key is
485 * less than member, and greater than 0 if key is greater then member.
488 smartlist_bsearch(smartlist_t
*sl
, const void *key
,
489 int (*compare
)(const void *key
, const void **member
))
492 idx
= smartlist_bsearch_idx(sl
, key
, compare
, &found
);
493 return found
? smartlist_get(sl
, idx
) : NULL
;
496 /** Assuming the members of <b>sl</b> are in order, return the index of the
497 * member that matches <b>key</b>. If no member matches, return the index of
498 * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
499 * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to
500 * false otherwise. Ordering and matching are defined by a <b>compare</b>
501 * function that returns 0 on a match; less than 0 if key is less than member,
502 * and greater than 0 if key is greater then member.
505 smartlist_bsearch_idx(const smartlist_t
*sl
, const void *key
,
506 int (*compare
)(const void *key
, const void **member
),
509 int hi
= smartlist_len(sl
) - 1, lo
= 0, cmp
, mid
;
513 cmp
= compare(key
, (const void**) &(sl
->list
[mid
]));
514 if (cmp
>0) { /* key > sl[mid] */
516 } else if (cmp
<0) { /* key < sl[mid] */
518 } else { /* key == sl[mid] */
526 if (lo
< smartlist_len(sl
)) {
527 cmp
= compare(key
, (const void**) &(sl
->list
[lo
]));
529 } else if (smartlist_len(sl
)) {
530 cmp
= compare(key
, (const void**) &(sl
->list
[smartlist_len(sl
)-1]));
538 /** Helper: compare two const char **s. */
540 _compare_string_ptrs(const void **_a
, const void **_b
)
542 return strcmp((const char*)*_a
, (const char*)*_b
);
545 /** Sort a smartlist <b>sl</b> containing strings into lexically ascending
548 smartlist_sort_strings(smartlist_t
*sl
)
550 smartlist_sort(sl
, _compare_string_ptrs
);
553 /** Remove duplicate strings from a sorted list, and free them with tor_free().
556 smartlist_uniq_strings(smartlist_t
*sl
)
558 smartlist_uniq(sl
, _compare_string_ptrs
, _tor_free
);
561 /* Heap-based priority queue implementation for O(lg N) insert and remove.
562 * Recall that the heap property is that, for every index I, h[I] <
563 * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
566 /* For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
567 * = 2*x + 1. But this is C, so we have to adjust a little. */
568 //#define LEFT_CHILD(i) ( ((i)+1)*2 - 1)
569 //#define RIGHT_CHILD(i) ( ((i)+1)*2 )
570 //#define PARENT(i) ( ((i)+1)/2 - 1)
571 #define LEFT_CHILD(i) ( 2*(i) + 1 )
572 #define RIGHT_CHILD(i) ( 2*(i) + 2 )
573 #define PARENT(i) ( ((i)-1) / 2 )
575 /** Helper. <b>sl</b> may have at most one violation of the heap property:
576 * the item at <b>idx</b> may be greater than one or both of its children.
577 * Restore the heap property. */
579 smartlist_heapify(smartlist_t
*sl
,
580 int (*compare
)(const void *a
, const void *b
),
584 int left_idx
= LEFT_CHILD(idx
);
587 if (left_idx
>= sl
->num_used
)
589 if (compare(sl
->list
[idx
],sl
->list
[left_idx
]) < 0)
593 if (left_idx
+1 < sl
->num_used
&&
594 compare(sl
->list
[left_idx
+1],sl
->list
[best_idx
]) < 0)
595 best_idx
= left_idx
+ 1;
597 if (best_idx
== idx
) {
600 void *tmp
= sl
->list
[idx
];
601 sl
->list
[idx
] = sl
->list
[best_idx
];
602 sl
->list
[best_idx
] = tmp
;
609 /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order
610 * is determined by <b>compare</b>. */
612 smartlist_pqueue_add(smartlist_t
*sl
,
613 int (*compare
)(const void *a
, const void *b
),
617 smartlist_add(sl
,item
);
619 for (idx
= sl
->num_used
- 1; idx
; ) {
620 int parent
= PARENT(idx
);
621 if (compare(sl
->list
[idx
], sl
->list
[parent
]) < 0) {
622 void *tmp
= sl
->list
[parent
];
623 sl
->list
[parent
] = sl
->list
[idx
];
632 /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
633 * where order is determined by <b>compare</b>. <b>sl</b> must not be
636 smartlist_pqueue_pop(smartlist_t
*sl
,
637 int (*compare
)(const void *a
, const void *b
))
640 tor_assert(sl
->num_used
);
643 if (--sl
->num_used
) {
644 sl
->list
[0] = sl
->list
[sl
->num_used
];
645 smartlist_heapify(sl
, compare
, 0);
650 /** Assert that the heap property is correctly maintained by the heap stored
651 * in <b>sl</b>, where order is determined by <b>compare</b>. */
653 smartlist_pqueue_assert_ok(smartlist_t
*sl
,
654 int (*compare
)(const void *a
, const void *b
))
657 for (i
= sl
->num_used
- 1; i
> 0; --i
) {
658 tor_assert(compare(sl
->list
[PARENT(i
)], sl
->list
[i
]) <= 0);
662 /** Helper: compare two DIGEST_LEN digests. */
664 _compare_digests(const void **_a
, const void **_b
)
666 return memcmp((const char*)*_a
, (const char*)*_b
, DIGEST_LEN
);
669 /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
671 smartlist_sort_digests(smartlist_t
*sl
)
673 smartlist_sort(sl
, _compare_digests
);
676 /** Remove duplicate digests from a sorted list, and free them with tor_free().
679 smartlist_uniq_digests(smartlist_t
*sl
)
681 smartlist_uniq(sl
, _compare_digests
, _tor_free
);
684 /** Helper: Declare an entry type and a map type to implement a mapping using
685 * ht.h. The map type will be called <b>maptype</b>. The key part of each
686 * entry is declared using the C declaration <b>keydecl</b>. All functions
687 * and types associated with the map get prefixed with <b>prefix</b> */
688 #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \
689 typedef struct prefix ## entry_t { \
690 HT_ENTRY(prefix ## entry_t) node; \
693 } prefix ## entry_t; \
695 HT_HEAD(prefix ## impl, prefix ## entry_t) head; \
698 DEFINE_MAP_STRUCTS(strmap_t
, char *key
, strmap_
);
699 DEFINE_MAP_STRUCTS(digestmap_t
, char key
[DIGEST_LEN
], digestmap_
);
701 /** Helper: compare strmap_entry_t objects by key value. */
703 strmap_entries_eq(const strmap_entry_t
*a
, const strmap_entry_t
*b
)
705 return !strcmp(a
->key
, b
->key
);
708 /** Helper: return a hash value for a strmap_entry_t. */
709 static INLINE
unsigned int
710 strmap_entry_hash(const strmap_entry_t
*a
)
712 return ht_string_hash(a
->key
);
715 /** Helper: compare digestmap_entry_t objects by key value. */
717 digestmap_entries_eq(const digestmap_entry_t
*a
, const digestmap_entry_t
*b
)
719 return !memcmp(a
->key
, b
->key
, DIGEST_LEN
);
722 /** Helper: return a hash value for a digest_map_t. */
723 static INLINE
unsigned int
724 digestmap_entry_hash(const digestmap_entry_t
*a
)
727 const uint32_t *p
= (const uint32_t*)a
->key
;
728 return p
[0] ^ p
[1] ^ p
[2] ^ p
[3] ^ p
[4];
730 const uint64_t *p
= (const uint64_t*)a
->key
;
735 HT_PROTOTYPE(strmap_impl
, strmap_entry_t
, node
, strmap_entry_hash
,
737 HT_GENERATE(strmap_impl
, strmap_entry_t
, node
, strmap_entry_hash
,
738 strmap_entries_eq
, 0.6, malloc
, realloc
, free
)
740 HT_PROTOTYPE(digestmap_impl
, digestmap_entry_t
, node
, digestmap_entry_hash
,
741 digestmap_entries_eq
)
742 HT_GENERATE(digestmap_impl
, digestmap_entry_t
, node
, digestmap_entry_hash
,
743 digestmap_entries_eq
, 0.6, malloc
, realloc
, free
)
745 /** Constructor to create a new empty map from strings to void*'s.
751 result
= tor_malloc(sizeof(strmap_t
));
752 HT_INIT(strmap_impl
, &result
->head
);
756 /** Constructor to create a new empty map from digests to void*'s.
762 result
= tor_malloc(sizeof(digestmap_t
));
763 HT_INIT(digestmap_impl
, &result
->head
);
767 /** Set the current value for <b>key</b> to <b>val</b>. Returns the previous
768 * value for <b>key</b> if one was set, or NULL if one was not.
770 * This function makes a copy of <b>key</b> if necessary, but not of
774 strmap_set(strmap_t
*map
, const char *key
, void *val
)
776 strmap_entry_t
*resolve
;
777 strmap_entry_t search
;
782 search
.key
= (char*)key
;
783 resolve
= HT_FIND(strmap_impl
, &map
->head
, &search
);
785 oldval
= resolve
->val
;
789 resolve
= tor_malloc_zero(sizeof(strmap_entry_t
));
790 resolve
->key
= tor_strdup(key
);
792 tor_assert(!HT_FIND(strmap_impl
, &map
->head
, resolve
));
793 HT_INSERT(strmap_impl
, &map
->head
, resolve
);
798 #define OPTIMIZED_DIGESTMAP_SET
800 /** Like strmap_set() above but for digestmaps. */
802 digestmap_set(digestmap_t
*map
, const char *key
, void *val
)
804 #ifndef OPTIMIZED_DIGESTMAP_SET
805 digestmap_entry_t
*resolve
;
807 digestmap_entry_t search
;
812 memcpy(&search
.key
, key
, DIGEST_LEN
);
813 #ifndef OPTIMIZED_DIGESTMAP_SET
814 resolve
= HT_FIND(digestmap_impl
, &map
->head
, &search
);
816 oldval
= resolve
->val
;
820 resolve
= tor_malloc_zero(sizeof(digestmap_entry_t
));
821 memcpy(resolve
->key
, key
, DIGEST_LEN
);
823 HT_INSERT(digestmap_impl
, &map
->head
, resolve
);
827 /* We spend up to 5% of our time in this function, so the code below is
828 * meant to optimize the check/alloc/set cycle by avoiding the two trips to
829 * the hash table that we do in the unoptimized code above. (Each of
830 * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.)
832 _HT_FIND_OR_INSERT(digestmap_impl
, node
, digestmap_entry_hash
, &(map
->head
),
833 digestmap_entry_t
, &search
, ptr
,
835 /* we found an entry. */
836 oldval
= (*ptr
)->val
;
841 /* We didn't find the entry. */
842 digestmap_entry_t
*newent
=
843 tor_malloc_zero(sizeof(digestmap_entry_t
));
844 memcpy(newent
->key
, key
, DIGEST_LEN
);
846 _HT_FOI_INSERT(node
, &(map
->head
), &search
, newent
, ptr
);
852 /** Return the current value associated with <b>key</b>, or NULL if no
856 strmap_get(const strmap_t
*map
, const char *key
)
858 strmap_entry_t
*resolve
;
859 strmap_entry_t search
;
862 search
.key
= (char*)key
;
863 resolve
= HT_FIND(strmap_impl
, &map
->head
, &search
);
871 /** Like strmap_get() above but for digestmaps. */
873 digestmap_get(const digestmap_t
*map
, const char *key
)
875 digestmap_entry_t
*resolve
;
876 digestmap_entry_t search
;
879 memcpy(&search
.key
, key
, DIGEST_LEN
);
880 resolve
= HT_FIND(digestmap_impl
, &map
->head
, &search
);
888 /** Remove the value currently associated with <b>key</b> from the map.
889 * Return the value if one was set, or NULL if there was no entry for
892 * Note: you must free any storage associated with the returned value.
895 strmap_remove(strmap_t
*map
, const char *key
)
897 strmap_entry_t
*resolve
;
898 strmap_entry_t search
;
902 search
.key
= (char*)key
;
903 resolve
= HT_REMOVE(strmap_impl
, &map
->head
, &search
);
905 oldval
= resolve
->val
;
906 tor_free(resolve
->key
);
914 /** Like strmap_remove() above but for digestmaps. */
916 digestmap_remove(digestmap_t
*map
, const char *key
)
918 digestmap_entry_t
*resolve
;
919 digestmap_entry_t search
;
923 memcpy(&search
.key
, key
, DIGEST_LEN
);
924 resolve
= HT_REMOVE(digestmap_impl
, &map
->head
, &search
);
926 oldval
= resolve
->val
;
934 /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
936 strmap_set_lc(strmap_t
*map
, const char *key
, void *val
)
938 /* We could be a little faster by using strcasecmp instead, and a separate
939 * type, but I don't think it matters. */
941 char *lc_key
= tor_strdup(key
);
942 tor_strlower(lc_key
);
943 v
= strmap_set(map
,lc_key
,val
);
948 /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
950 strmap_get_lc(const strmap_t
*map
, const char *key
)
953 char *lc_key
= tor_strdup(key
);
954 tor_strlower(lc_key
);
955 v
= strmap_get(map
,lc_key
);
960 /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
962 strmap_remove_lc(strmap_t
*map
, const char *key
)
965 char *lc_key
= tor_strdup(key
);
966 tor_strlower(lc_key
);
967 v
= strmap_remove(map
,lc_key
);
972 /** return an <b>iterator</b> pointer to the front of a map.
977 * // uppercase values in "map", removing empty values.
979 * strmap_iter_t *iter;
984 * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) {
985 * strmap_iter_get(iter, &key, &val);
988 * iter = strmap_iter_next_rmv(map,iter);
991 * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp);
992 * iter = strmap_iter_next(map,iter);
999 strmap_iter_init(strmap_t
*map
)
1002 return HT_START(strmap_impl
, &map
->head
);
1005 /** Start iterating through <b>map</b>. See strmap_iter_init() for example. */
1007 digestmap_iter_init(digestmap_t
*map
)
1010 return HT_START(digestmap_impl
, &map
->head
);
1013 /** Advance the iterator <b>iter</b> for <b>map</b> a single step to the next
1014 * entry, and return its new value. */
1016 strmap_iter_next(strmap_t
*map
, strmap_iter_t
*iter
)
1020 return HT_NEXT(strmap_impl
, &map
->head
, iter
);
1023 /** Advance the iterator <b>iter</b> for map a single step to the next entry,
1024 * and return its new value. */
1026 digestmap_iter_next(digestmap_t
*map
, digestmap_iter_t
*iter
)
1030 return HT_NEXT(digestmap_impl
, &map
->head
, iter
);
1033 /** Advance the iterator <b>iter</b> a single step to the next entry, removing
1034 * the current entry, and return its new value.
1037 strmap_iter_next_rmv(strmap_t
*map
, strmap_iter_t
*iter
)
1039 strmap_entry_t
*rmv
;
1044 iter
= HT_NEXT_RMV(strmap_impl
, &map
->head
, iter
);
1050 /** Advance the iterator <b>iter</b> a single step to the next entry, removing
1051 * the current entry, and return its new value.
1054 digestmap_iter_next_rmv(digestmap_t
*map
, digestmap_iter_t
*iter
)
1056 digestmap_entry_t
*rmv
;
1061 iter
= HT_NEXT_RMV(digestmap_impl
, &map
->head
, iter
);
1066 /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
1069 strmap_iter_get(strmap_iter_t
*iter
, const char **keyp
, void **valp
)
1075 *keyp
= (*iter
)->key
;
1076 *valp
= (*iter
)->val
;
1079 /** Set *<b>keyp</b> and *<b>valp</b> to the current entry pointed to by
1082 digestmap_iter_get(digestmap_iter_t
*iter
, const char **keyp
, void **valp
)
1088 *keyp
= (*iter
)->key
;
1089 *valp
= (*iter
)->val
;
1092 /** Return true iff <b>iter</b> has advanced past the last entry of
1095 strmap_iter_done(strmap_iter_t
*iter
)
1097 return iter
== NULL
;
1100 /** Return true iff <b>iter</b> has advanced past the last entry of
1103 digestmap_iter_done(digestmap_iter_t
*iter
)
1105 return iter
== NULL
;
1108 /** Remove all entries from <b>map</b>, and deallocate storage for those
1109 * entries. If free_val is provided, it is invoked on every value in
1113 strmap_free(strmap_t
*map
, void (*free_val
)(void*))
1115 strmap_entry_t
**ent
, **next
, *this;
1116 for (ent
= HT_START(strmap_impl
, &map
->head
); ent
!= NULL
; ent
= next
) {
1118 next
= HT_NEXT_RMV(strmap_impl
, &map
->head
, ent
);
1119 tor_free(this->key
);
1121 free_val(this->val
);
1124 tor_assert(HT_EMPTY(&map
->head
));
1125 HT_CLEAR(strmap_impl
, &map
->head
);
1129 /** Remove all entries from <b>map</b>, and deallocate storage for those
1130 * entries. If free_val is provided, it is invoked on every value in
1134 digestmap_free(digestmap_t
*map
, void (*free_val
)(void*))
1136 digestmap_entry_t
**ent
, **next
, *this;
1137 for (ent
= HT_START(digestmap_impl
, &map
->head
); ent
!= NULL
; ent
= next
) {
1139 next
= HT_NEXT_RMV(digestmap_impl
, &map
->head
, ent
);
1141 free_val(this->val
);
1144 tor_assert(HT_EMPTY(&map
->head
));
1145 HT_CLEAR(digestmap_impl
, &map
->head
);
1149 /** Fail with an assertion error if anything has gone wrong with the internal
1150 * representation of <b>map</b>. */
1152 strmap_assert_ok(const strmap_t
*map
)
1154 tor_assert(!_strmap_impl_HT_REP_IS_BAD(&map
->head
));
1156 /** Fail with an assertion error if anything has gone wrong with the internal
1157 * representation of <b>map</b>. */
1159 digestmap_assert_ok(const digestmap_t
*map
)
1161 tor_assert(!_digestmap_impl_HT_REP_IS_BAD(&map
->head
));
1164 /** Return true iff <b>map</b> has no entries. */
1166 strmap_isempty(const strmap_t
*map
)
1168 return HT_EMPTY(&map
->head
);
1171 /** Return true iff <b>map</b> has no entries. */
1173 digestmap_isempty(const digestmap_t
*map
)
1175 return HT_EMPTY(&map
->head
);
1178 /** Return the number of items in <b>map</b>. */
1180 strmap_size(const strmap_t
*map
)
1182 return HT_SIZE(&map
->head
);
1185 /** Return the number of items in <b>map</b>. */
1187 digestmap_size(const digestmap_t
*map
)
1189 return HT_SIZE(&map
->head
);
1192 /** Declare a function called <b>funcname</b> that acts as a find_nth_FOO
1193 * function for an array of type <b>elt_t</b>*.
1195 * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding
1196 * the kth element of an n-element list can be done in O(n). Then again, this
1197 * implementation is not in critical path, and it is obviously correct. */
1198 #define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \
1200 _cmp_ ## elt_t(const void *_a, const void *_b) \
1202 const elt_t *a = _a, *b = _b; \
1211 funcname(elt_t *array, int n_elements, int nth) \
1213 tor_assert(nth >= 0); \
1214 tor_assert(nth < n_elements); \
1215 qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \
1216 return array[nth]; \
1219 IMPLEMENT_ORDER_FUNC(find_nth_int
, int)
1220 IMPLEMENT_ORDER_FUNC(find_nth_time
, time_t)
1221 IMPLEMENT_ORDER_FUNC(find_nth_double
, double)
1222 IMPLEMENT_ORDER_FUNC(find_nth_uint32
, uint32_t)
1223 IMPLEMENT_ORDER_FUNC(find_nth_long
, long)
1225 /** Return a newly allocated digestset_t, optimized to hold a total of
1226 * <b>max_elements</b> digests with a reasonably low false positive weight. */
1228 digestset_new(int max_elements
)
1230 /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
1231 * is the number of hash functions per entry, m is the bits in the array,
1232 * and n is the number of elements inserted. For us, k==4, n<=max_elements,
1233 * and m==n_bits= approximately max_elements*32. This gives
1234 * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
1236 * It would be more optimal in space vs false positives to get this false
1237 * positive rate by going for k==13, and m==18.5n, but we also want to
1238 * conserve CPU, and k==13 is pretty big.
1240 int n_bits
= 1u << (tor_log2(max_elements
)+5);
1241 digestset_t
*r
= tor_malloc(sizeof(digestset_t
));
1242 r
->mask
= n_bits
- 1;
1243 r
->ba
= bitarray_init_zero(n_bits
);
1247 /** Free all storage held in <b>set</b>. */
1249 digestset_free(digestset_t
*set
)
1251 bitarray_free(set
->ba
);