1 /* Copyright 2003-2004 Roger Dingledine
2 Copyright 2004-2006 Roger Dingledine, Nick Mathewson */
3 /* See LICENSE for licensing information */
5 const char container_c_id
[] =
10 * \brief Implements a smartlist (a resizable array) along
11 * with helper functions to use smartlists. Also includes
12 * hash table implementations of a string-to-void* map, and of
13 * a digest-to-void* map.
19 #include "container.h"
31 /* All newly allocated smartlists have this capacity.
33 #define SMARTLIST_DEFAULT_CAPACITY 32
35 /** Allocate and return an empty smartlist.
38 smartlist_create(void)
40 smartlist_t
*sl
= tor_malloc(sizeof(smartlist_t
));
42 sl
->capacity
= SMARTLIST_DEFAULT_CAPACITY
;
43 sl
->list
= tor_malloc(sizeof(void *) * sl
->capacity
);
47 /** Deallocate a smartlist. Does not release storage associated with the
51 smartlist_free(smartlist_t
*sl
)
53 tor_assert(sl
!= NULL
);
58 /** Change the capacity of the smartlist to <b>n</b>, so that we can grow
59 * the list up to <b>n</b> elements with no further reallocation or wasted
60 * space. If <b>n</b> is less than or equal to the number of elements
61 * currently in the list, reduce the list's capacity as much as
62 * possible without losing elements.
65 smartlist_set_capacity(smartlist_t
*sl
, int n
)
69 if (sl
->capacity
!= n
) {
71 sl
->list
= tor_realloc(sl
->list
, sizeof(void*)*sl
->capacity
);
75 /** Remove all elements from the list.
78 smartlist_clear(smartlist_t
*sl
)
83 /** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
85 smartlist_ensure_capacity(smartlist_t
*sl
, int size
)
87 if (size
> sl
->capacity
) {
88 int higher
= sl
->capacity
* 2;
91 tor_assert(higher
> sl
->capacity
); /* detect overflow */
92 sl
->capacity
= higher
;
93 sl
->list
= tor_realloc(sl
->list
, sizeof(void*)*sl
->capacity
);
97 /** Append element to the end of the list. */
99 smartlist_add(smartlist_t
*sl
, void *element
)
101 smartlist_ensure_capacity(sl
, sl
->num_used
+1);
102 sl
->list
[sl
->num_used
++] = element
;
105 /** Append each element from S2 to the end of S1. */
107 smartlist_add_all(smartlist_t
*s1
, const smartlist_t
*s2
)
109 smartlist_ensure_capacity(s1
, s1
->num_used
+ s2
->num_used
);
110 memcpy(s1
->list
+ s1
->num_used
, s2
->list
, s2
->num_used
*sizeof(void*));
111 s1
->num_used
+= s2
->num_used
;
114 /** Remove all elements E from sl such that E==element. Preserve
115 * the order of any elements before E, but elements after E can be
119 smartlist_remove(smartlist_t
*sl
, const void *element
)
124 for (i
=0; i
< sl
->num_used
; i
++)
125 if (sl
->list
[i
] == element
) {
126 sl
->list
[i
] = sl
->list
[--sl
->num_used
]; /* swap with the end */
127 i
--; /* so we process the new i'th element */
131 /** If <b>sl</b> is nonempty, remove and return the final element. Otherwise,
134 smartlist_pop_last(smartlist_t
*sl
)
138 return sl
->list
[--sl
->num_used
];
143 /** Reverse the order of the items in <b>sl</b>. */
145 smartlist_reverse(smartlist_t
*sl
)
150 for (i
= 0, j
= sl
->num_used
-1; i
< j
; ++i
, --j
) {
152 sl
->list
[i
] = sl
->list
[j
];
157 /** If there are any strings in sl equal to element, remove and free them.
158 * Does not preserve order. */
160 smartlist_string_remove(smartlist_t
*sl
, const char *element
)
165 for (i
= 0; i
< sl
->num_used
; ++i
) {
166 if (!strcmp(element
, sl
->list
[i
])) {
167 tor_free(sl
->list
[i
]);
168 sl
->list
[i
] = sl
->list
[--sl
->num_used
]; /* swap with the end */
169 i
--; /* so we process the new i'th element */
174 /** Return true iff some element E of sl has E==element.
177 smartlist_isin(const smartlist_t
*sl
, const void *element
)
180 for (i
=0; i
< sl
->num_used
; i
++)
181 if (sl
->list
[i
] == element
)
186 /** Return true iff <b>sl</b> has some element E such that
187 * !strcmp(E,<b>element</b>)
190 smartlist_string_isin(const smartlist_t
*sl
, const char *element
)
194 for (i
=0; i
< sl
->num_used
; i
++)
195 if (strcmp((const char*)sl
->list
[i
],element
)==0)
200 /** Return true iff <b>sl</b> has some element E such that E is equal
201 * to the decimal encoding of <b>num</b>.
204 smartlist_string_num_isin(const smartlist_t
*sl
, int num
)
207 tor_snprintf(buf
,sizeof(buf
),"%d", num
);
208 return smartlist_string_isin(sl
, buf
);
211 /** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
214 smartlist_overlap(const smartlist_t
*sl1
, const smartlist_t
*sl2
)
217 for (i
=0; i
< sl2
->num_used
; i
++)
218 if (smartlist_isin(sl1
, sl2
->list
[i
]))
223 /** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
224 * Does not preserve the order of sl1.
227 smartlist_intersect(smartlist_t
*sl1
, const smartlist_t
*sl2
)
230 for (i
=0; i
< sl1
->num_used
; i
++)
231 if (!smartlist_isin(sl2
, sl1
->list
[i
])) {
232 sl1
->list
[i
] = sl1
->list
[--sl1
->num_used
]; /* swap with the end */
233 i
--; /* so we process the new i'th element */
237 /** Remove every element E of sl1 such that smartlist_isin(sl2,E).
238 * Does not preserve the order of sl1.
241 smartlist_subtract(smartlist_t
*sl1
, const smartlist_t
*sl2
)
244 for (i
=0; i
< sl2
->num_used
; i
++)
245 smartlist_remove(sl1
, sl2
->list
[i
]);
248 /** Remove the <b>idx</b>th element of sl; if idx is not the last
249 * element, swap the last element of sl into the <b>idx</b>th space.
250 * Return the old value of the <b>idx</b>th element.
253 smartlist_del(smartlist_t
*sl
, int idx
)
257 tor_assert(idx
< sl
->num_used
);
258 sl
->list
[idx
] = sl
->list
[--sl
->num_used
];
261 /** Remove the <b>idx</b>th element of sl; if idx is not the last element,
262 * moving all subsequent elements back one space. Return the old value
263 * of the <b>idx</b>th element.
266 smartlist_del_keeporder(smartlist_t
*sl
, int idx
)
270 tor_assert(idx
< sl
->num_used
);
272 if (idx
< sl
->num_used
)
273 memmove(sl
->list
+idx
, sl
->list
+idx
+1, sizeof(void*)*(sl
->num_used
-idx
));
276 /** Insert the value <b>val</b> as the new <b>idx</b>th element of
277 * <b>sl</b>, moving all items previously at <b>idx</b> or later
281 smartlist_insert(smartlist_t
*sl
, int idx
, void *val
)
285 tor_assert(idx
<= sl
->num_used
);
286 if (idx
== sl
->num_used
) {
287 smartlist_add(sl
, val
);
289 smartlist_ensure_capacity(sl
, sl
->num_used
+1);
290 /* Move other elements away */
291 if (idx
< sl
->num_used
)
292 memmove(sl
->list
+ idx
+ 1, sl
->list
+ idx
,
293 sizeof(void*)*(sl
->num_used
-idx
));
300 * Split a string <b>str</b> along all occurrences of <b>sep</b>,
301 * adding the split strings, in order, to <b>sl</b>. If
302 * <b>flags</b>&SPLIT_SKIP_SPACE is true, remove initial and
303 * trailing space from each entry. If
304 * <b>flags</b>&SPLIT_IGNORE_BLANK is true, remove any entries of
305 * length 0. If max>0, divide the string into no more than <b>max</b>
306 * pieces. If <b>sep</b> is NULL, split on any sequence of horizontal space.
309 smartlist_split_string(smartlist_t
*sl
, const char *str
, const char *sep
,
312 const char *cp
, *end
, *next
;
320 if (flags
&SPLIT_SKIP_SPACE
) {
321 while (TOR_ISSPACE(*cp
)) ++cp
;
324 if (max
>0 && n
== max
-1) {
325 end
= strchr(cp
,'\0');
327 end
= strstr(cp
,sep
);
329 end
= strchr(cp
,'\0');
331 for (end
= cp
; *end
&& *end
!= '\t' && *end
!= ' '; ++end
)
338 next
= end
+strlen(sep
);
341 while (*next
== '\t' || *next
== ' ')
345 if (flags
&SPLIT_SKIP_SPACE
) {
346 while (end
> cp
&& TOR_ISSPACE(*(end
-1)))
349 if (end
!= cp
|| !(flags
&SPLIT_IGNORE_BLANK
)) {
350 smartlist_add(sl
, tor_strndup(cp
, end
-cp
));
361 /** Allocate and return a new string containing the concatenation of
362 * the elements of <b>sl</b>, in order, separated by <b>join</b>. If
363 * <b>terminate</b> is true, also terminate the string with <b>join</b>.
364 * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
365 * the returned string. Requires that every element of <b>sl</b> is
366 * NUL-terminated string.
369 smartlist_join_strings(smartlist_t
*sl
, const char *join
,
370 int terminate
, size_t *len_out
)
372 return smartlist_join_strings2(sl
,join
,strlen(join
),terminate
,len_out
);
375 /** As smartlist_join_strings, but instead of separating/terminated with a
376 * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
377 * at <b>join</b>. (Useful for generating a sequence of NUL-terminated
381 smartlist_join_strings2(smartlist_t
*sl
, const char *join
,
382 size_t join_len
, int terminate
, size_t *len_out
)
386 char *r
= NULL
, *dst
, *src
;
394 for (i
= 0; i
< sl
->num_used
; ++i
) {
395 n
+= strlen(sl
->list
[i
]);
396 if (i
+1 < sl
->num_used
) /* avoid double-counting the last one */
399 dst
= r
= tor_malloc(n
+1);
400 for (i
= 0; i
< sl
->num_used
; ) {
401 for (src
= sl
->list
[i
]; *src
; )
403 if (++i
< sl
->num_used
) {
404 memcpy(dst
, join
, join_len
);
409 memcpy(dst
, join
, join_len
);
419 /** Sort the members of <b>sl</b> into an order defined by
420 * the ordering function <b>compare</b>, which returns less then 0 if a
421 * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
424 smartlist_sort(smartlist_t
*sl
, int (*compare
)(const void **a
, const void **b
))
428 qsort(sl
->list
, sl
->num_used
, sizeof(void*),
429 (int (*)(const void *,const void*))compare
);
432 /** Given a sorted smartlist <b>sl</b> and the comparison function used to
433 * sort it, remove all duplicate members. If free_fn is provided, calls
434 * free_fn on each duplicate. Otherwise, frees them with tor_free(), which
435 * may not be what you want.. Preserves order.
438 smartlist_uniq(smartlist_t
*sl
,
439 int (*compare
)(const void **a
, const void **b
),
440 void (*free_fn
)(void *a
))
443 for (i
=1; i
< sl
->num_used
; ++i
) {
444 if (compare((const void **)&(sl
->list
[i
-1]),
445 (const void **)&(sl
->list
[i
])) == 0) {
447 free_fn(sl
->list
[i
]);
449 tor_free(sl
->list
[i
]);
450 smartlist_del_keeporder(sl
, i
--);
455 /** Assuming the members of <b>sl</b> are in order, return a pointer to the
456 * member which matches <b>key</b>. Ordering and matching are defined by a
457 * <b>compare</b> function, which returns 0 on a match; less than 0 if key is
458 * less than member, and greater than 0 if key is greater then member.
461 smartlist_bsearch(smartlist_t
*sl
, const void *key
,
462 int (*compare
)(const void *key
, const void **member
))
468 r
= bsearch(key
, sl
->list
, sl
->num_used
, sizeof(void*),
469 (int (*)(const void *, const void *))compare
);
470 return r
? *r
: NULL
;
473 /** Helper: compare two const char **s. */
475 _compare_string_ptrs(const void **_a
, const void **_b
)
477 return strcmp((const char*)*_a
, (const char*)*_b
);
480 /** Sort a smartlist <b>sl</b> containing strings into lexically ascending
483 smartlist_sort_strings(smartlist_t
*sl
)
485 smartlist_sort(sl
, _compare_string_ptrs
);
488 /** Remove duplicate strings from a sorted list, and free them with tor_free().
491 smartlist_uniq_strings(smartlist_t
*sl
)
493 smartlist_uniq(sl
, _compare_string_ptrs
, NULL
);
496 /* Heap-based priority queue implementation for O(lg N) insert and remove.
497 * Recall that the heap property is that, for every index I, h[I] <
498 * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
501 /* For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
502 * = 2*x + 1. But this is C, so we have to adjust a little. */
503 //#define LEFT_CHILD(i) ( ((i)+1)*2 - 1)
504 //#define RIGHT_CHILD(i) ( ((i)+1)*2 )
505 //#define PARENT(i) ( ((i)+1)/2 - 1)
506 #define LEFT_CHILD(i) ( 2*(i) + 1 )
507 #define RIGHT_CHILD(i) ( 2*(i) + 2 )
508 #define PARENT(i) ( ((i)-1) / 2 )
510 /** Helper. <b>sl</b> may have at most one violation of the heap property:
511 * the item at <b>idx</b> may be greater than one or both of its children.
512 * Restore the heap property. */
514 smartlist_heapify(smartlist_t
*sl
,
515 int (*compare
)(const void *a
, const void *b
),
519 int left_idx
= LEFT_CHILD(idx
);
522 if (left_idx
>= sl
->num_used
)
524 if (compare(sl
->list
[idx
],sl
->list
[left_idx
]) < 0)
528 if (left_idx
+1 < sl
->num_used
&&
529 compare(sl
->list
[left_idx
+1],sl
->list
[best_idx
]) < 0)
530 best_idx
= left_idx
+ 1;
532 if (best_idx
== idx
) {
535 void *tmp
= sl
->list
[idx
];
536 sl
->list
[idx
] = sl
->list
[best_idx
];
537 sl
->list
[best_idx
] = tmp
;
544 /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order
545 * is determined by <b>compare</b>. */
547 smartlist_pqueue_add(smartlist_t
*sl
,
548 int (*compare
)(const void *a
, const void *b
),
552 smartlist_add(sl
,item
);
554 for (idx
= sl
->num_used
- 1; idx
; ) {
555 int parent
= PARENT(idx
);
556 if (compare(sl
->list
[idx
], sl
->list
[parent
]) < 0) {
557 void *tmp
= sl
->list
[parent
];
558 sl
->list
[parent
] = sl
->list
[idx
];
567 /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
568 * where order is determined by <b>compare</b>. <b>sl</b> must not be
571 smartlist_pqueue_pop(smartlist_t
*sl
,
572 int (*compare
)(const void *a
, const void *b
))
575 tor_assert(sl
->num_used
);
578 if (--sl
->num_used
) {
579 sl
->list
[0] = sl
->list
[sl
->num_used
];
580 smartlist_heapify(sl
, compare
, 0);
585 /** Assert that the heap property is correctly maintained by the heap stored
586 * in <b>sl</b>, where order is determined by <b>compare</b>. */
588 smartlist_pqueue_assert_ok(smartlist_t
*sl
,
589 int (*compare
)(const void *a
, const void *b
))
592 for (i
= sl
->num_used
- 1; i
> 0; --i
) {
593 tor_assert(compare(sl
->list
[PARENT(i
)], sl
->list
[i
]) <= 0);
597 /** Helper: compare two DIGEST_LEN digests. */
599 _compare_digests(const void **_a
, const void **_b
)
601 return memcmp((const char*)*_a
, (const char*)*_b
, DIGEST_LEN
);
604 /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
606 smartlist_sort_digests(smartlist_t
*sl
)
608 smartlist_sort(sl
, _compare_digests
);
611 /** Remove duplicate digests from a sorted list, and free them with tor_free().
614 smartlist_uniq_digests(smartlist_t
*sl
)
616 smartlist_uniq(sl
, _compare_digests
, NULL
);
619 #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \
620 typedef struct prefix ## entry_t { \
621 HT_ENTRY(prefix ## entry_t) node; \
624 } prefix ## entry_t; \
626 HT_HEAD(prefix ## impl, prefix ## entry_t) head; \
629 DEFINE_MAP_STRUCTS(strmap_t
, char *key
, strmap_
);
630 DEFINE_MAP_STRUCTS(digestmap_t
, char key
[DIGEST_LEN
], digestmap_
);
632 /** Helper: compare strmap_entry_t objects by key value. */
634 strmap_entries_eq(strmap_entry_t
*a
, strmap_entry_t
*b
)
636 return !strcmp(a
->key
, b
->key
);
639 /** Helper: return a hash value for a strmap_entry_t. */
640 static INLINE
unsigned int
641 strmap_entry_hash(strmap_entry_t
*a
)
643 return ht_string_hash(a
->key
);
646 /** Helper: compare digestmap_entry_t objects by key value. */
648 digestmap_entries_eq(digestmap_entry_t
*a
, digestmap_entry_t
*b
)
650 return !memcmp(a
->key
, b
->key
, DIGEST_LEN
);
653 /** Helper: return a hash value for a digest_map_t. */
654 static INLINE
unsigned int
655 digestmap_entry_hash(digestmap_entry_t
*a
)
657 uint32_t *p
= (uint32_t*)a
->key
;
658 return ht_improve_hash(p
[0] ^ p
[1] ^ p
[2] ^ p
[3] ^ p
[4]);
661 HT_PROTOTYPE(strmap_impl
, strmap_entry_t
, node
, strmap_entry_hash
,
663 HT_GENERATE(strmap_impl
, strmap_entry_t
, node
, strmap_entry_hash
,
664 strmap_entries_eq
, 0.6, malloc
, realloc
, free
);
666 HT_PROTOTYPE(digestmap_impl
, digestmap_entry_t
, node
, digestmap_entry_hash
,
667 digestmap_entries_eq
);
668 HT_GENERATE(digestmap_impl
, digestmap_entry_t
, node
, digestmap_entry_hash
,
669 digestmap_entries_eq
, 0.6, malloc
, realloc
, free
);
671 /** Constructor to create a new empty map from strings to void*'s.
677 result
= tor_malloc(sizeof(strmap_t
));
678 HT_INIT(strmap_impl
, &result
->head
);
682 /** Constructor to create a new empty map from digests to void*'s.
688 result
= tor_malloc(sizeof(digestmap_t
));
689 HT_INIT(digestmap_impl
, &result
->head
);
693 /** Set the current value for <b>key</b> to <b>val</b>. Returns the previous
694 * value for <b>key</b> if one was set, or NULL if one was not.
696 * This function makes a copy of <b>key</b> if necessary, but not of
700 strmap_set(strmap_t
*map
, const char *key
, void *val
)
702 strmap_entry_t
*resolve
;
703 strmap_entry_t search
;
708 search
.key
= (char*)key
;
709 resolve
= HT_FIND(strmap_impl
, &map
->head
, &search
);
711 oldval
= resolve
->val
;
715 resolve
= tor_malloc_zero(sizeof(strmap_entry_t
));
716 resolve
->key
= tor_strdup(key
);
718 tor_assert(!HT_FIND(strmap_impl
, &map
->head
, resolve
));
719 HT_INSERT(strmap_impl
, &map
->head
, resolve
);
724 /** Like strmap_set() above but for digestmaps. */
726 digestmap_set(digestmap_t
*map
, const char *key
, void *val
)
728 digestmap_entry_t
*resolve
;
729 digestmap_entry_t search
;
734 memcpy(&search
.key
, key
, DIGEST_LEN
);
735 resolve
= HT_FIND(digestmap_impl
, &map
->head
, &search
);
737 oldval
= resolve
->val
;
741 resolve
= tor_malloc_zero(sizeof(digestmap_entry_t
));
742 memcpy(resolve
->key
, key
, DIGEST_LEN
);
744 HT_INSERT(digestmap_impl
, &map
->head
, resolve
);
749 /** Return the current value associated with <b>key</b>, or NULL if no
753 strmap_get(strmap_t
*map
, const char *key
)
755 strmap_entry_t
*resolve
;
756 strmap_entry_t search
;
759 search
.key
= (char*)key
;
760 resolve
= HT_FIND(strmap_impl
, &map
->head
, &search
);
768 /** Like strmap_get() above but for digestmaps. */
770 digestmap_get(digestmap_t
*map
, const char *key
)
772 digestmap_entry_t
*resolve
;
773 digestmap_entry_t search
;
776 memcpy(&search
.key
, key
, DIGEST_LEN
);
777 resolve
= HT_FIND(digestmap_impl
, &map
->head
, &search
);
785 /** Remove the value currently associated with <b>key</b> from the map.
786 * Return the value if one was set, or NULL if there was no entry for
789 * Note: you must free any storage associated with the returned value.
792 strmap_remove(strmap_t
*map
, const char *key
)
794 strmap_entry_t
*resolve
;
795 strmap_entry_t search
;
799 search
.key
= (char*)key
;
800 resolve
= HT_REMOVE(strmap_impl
, &map
->head
, &search
);
802 oldval
= resolve
->val
;
803 tor_free(resolve
->key
);
811 /** Like strmap_remove() above but for digestmaps. */
813 digestmap_remove(digestmap_t
*map
, const char *key
)
815 digestmap_entry_t
*resolve
;
816 digestmap_entry_t search
;
820 memcpy(&search
.key
, key
, DIGEST_LEN
);
821 resolve
= HT_REMOVE(digestmap_impl
, &map
->head
, &search
);
823 oldval
= resolve
->val
;
831 /** Same as strmap_set, but first converts <b>key</b> to lowercase. */
833 strmap_set_lc(strmap_t
*map
, const char *key
, void *val
)
835 /* We could be a little faster by using strcasecmp instead, and a separate
836 * type, but I don't think it matters. */
838 char *lc_key
= tor_strdup(key
);
839 tor_strlower(lc_key
);
840 v
= strmap_set(map
,lc_key
,val
);
845 /** Same as strmap_get, but first converts <b>key</b> to lowercase. */
847 strmap_get_lc(strmap_t
*map
, const char *key
)
850 char *lc_key
= tor_strdup(key
);
851 tor_strlower(lc_key
);
852 v
= strmap_get(map
,lc_key
);
857 /** Same as strmap_remove, but first converts <b>key</b> to lowercase */
859 strmap_remove_lc(strmap_t
*map
, const char *key
)
862 char *lc_key
= tor_strdup(key
);
863 tor_strlower(lc_key
);
864 v
= strmap_remove(map
,lc_key
);
869 /** return an <b>iterator</b> pointer to the front of a map.
874 * // uppercase values in "map", removing empty values.
876 * strmap_iter_t *iter;
881 * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) {
882 * strmap_iter_get(iter, &key, &val);
885 * iter = strmap_iter_next_rmv(iter);
888 * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp);
889 * iter = strmap_iter_next(iter);
896 strmap_iter_init(strmap_t
*map
)
899 return HT_START(strmap_impl
, &map
->head
);
903 digestmap_iter_init(digestmap_t
*map
)
906 return HT_START(digestmap_impl
, &map
->head
);
909 /** Advance the iterator <b>iter</b> for map a single step to the next entry.
912 strmap_iter_next(strmap_t
*map
, strmap_iter_t
*iter
)
916 return HT_NEXT(strmap_impl
, &map
->head
, iter
);
920 digestmap_iter_next(digestmap_t
*map
, digestmap_iter_t
*iter
)
924 return HT_NEXT(digestmap_impl
, &map
->head
, iter
);
927 /** Advance the iterator <b>iter</b> a single step to the next entry, removing
931 strmap_iter_next_rmv(strmap_t
*map
, strmap_iter_t
*iter
)
938 iter
= HT_NEXT_RMV(strmap_impl
, &map
->head
, iter
);
945 digestmap_iter_next_rmv(digestmap_t
*map
, digestmap_iter_t
*iter
)
947 digestmap_entry_t
*rmv
;
952 iter
= HT_NEXT_RMV(digestmap_impl
, &map
->head
, iter
);
957 /** Set *keyp and *valp to the current entry pointed to by iter.
960 strmap_iter_get(strmap_iter_t
*iter
, const char **keyp
, void **valp
)
966 *keyp
= (*iter
)->key
;
967 *valp
= (*iter
)->val
;
971 digestmap_iter_get(digestmap_iter_t
*iter
, const char **keyp
, void **valp
)
977 *keyp
= (*iter
)->key
;
978 *valp
= (*iter
)->val
;
981 /** Return true iff iter has advanced past the last entry of map.
984 strmap_iter_done(strmap_iter_t
*iter
)
989 digestmap_iter_done(digestmap_iter_t
*iter
)
994 /** Remove all entries from <b>map</b>, and deallocate storage for those
995 * entries. If free_val is provided, it is invoked on every value in
999 strmap_free(strmap_t
*map
, void (*free_val
)(void*))
1001 strmap_entry_t
**ent
, **next
, *this;
1002 for (ent
= HT_START(strmap_impl
, &map
->head
); ent
!= NULL
; ent
= next
) {
1004 next
= HT_NEXT_RMV(strmap_impl
, &map
->head
, ent
);
1005 tor_free(this->key
);
1007 free_val(this->val
);
1010 tor_assert(HT_EMPTY(&map
->head
));
1011 HT_CLEAR(strmap_impl
, &map
->head
);
1015 digestmap_free(digestmap_t
*map
, void (*free_val
)(void*))
1017 digestmap_entry_t
**ent
, **next
, *this;
1018 for (ent
= HT_START(digestmap_impl
, &map
->head
); ent
!= NULL
; ent
= next
) {
1020 next
= HT_NEXT_RMV(digestmap_impl
, &map
->head
, ent
);
1022 free_val(this->val
);
1025 tor_assert(HT_EMPTY(&map
->head
));
1026 HT_CLEAR(digestmap_impl
, &map
->head
);
1031 strmap_assert_ok(strmap_t
*map
)
1033 tor_assert(!_strmap_impl_HT_REP_IS_BAD(&map
->head
));
1036 digestmap_assert_ok(digestmap_t
*map
)
1038 tor_assert(!_digestmap_impl_HT_REP_IS_BAD(&map
->head
));
1041 /** Return true iff <b>map</b> has no entries. */
1043 strmap_isempty(strmap_t
*map
)
1045 return HT_EMPTY(&map
->head
);
1049 digestmap_isempty(digestmap_t
*map
)
1051 return HT_EMPTY(&map
->head
);
1054 /** Return the number of items in <b>map</b>. */
1056 strmap_size(strmap_t
*map
)
1058 return HT_SIZE(&map
->head
);
1062 digestmap_size(digestmap_t
*map
)
1064 return HT_SIZE(&map
->head
);