Line data Source code
1 : /* Copyright (c) 2003-2004, Roger Dingledine
2 : * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 : * Copyright (c) 2007-2021, The Tor Project, Inc. */
4 : /* See LICENSE for licensing information */
5 :
6 : /**
7 : * \file smartlist.c
8 : *
9 : * \brief Higher-level functions for the "smartlist" resizeable array
10 : * abstraction.
11 : *
12 : * The functions declared here use higher-level functionality than those in
13 : * smartlist_core.c, and handle things like smartlists of different types,
14 : * sorting, searching, heap-structured smartlists, and other convenience
15 : * functions.
16 : **/
17 :
18 : #include "lib/container/smartlist.h"
19 : #include "lib/err/torerr.h"
20 : #include "lib/malloc/malloc.h"
21 : #include "lib/defs/digest_sizes.h"
22 : #include "lib/ctime/di_ops.h"
23 : #include "lib/string/compat_ctype.h"
24 : #include "lib/string/compat_string.h"
25 : #include "lib/string/util_string.h"
26 : #include "lib/string/printf.h"
27 :
28 : #include "lib/log/util_bug.h"
29 :
30 : #include <stdlib.h>
31 : #include <string.h>
32 :
33 : /** Append the string produced by tor_asprintf(<b>pattern</b>, <b>...</b>)
34 : * to <b>sl</b>. */
35 : void
36 31669 : smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern, ...)
37 : {
38 31669 : va_list ap;
39 31669 : va_start(ap, pattern);
40 31669 : smartlist_add_vasprintf(sl, pattern, ap);
41 31669 : va_end(ap);
42 31669 : }
43 :
44 : /** va_list-based backend of smartlist_add_asprintf. */
45 : void
46 31669 : smartlist_add_vasprintf(struct smartlist_t *sl, const char *pattern,
47 : va_list args)
48 : {
49 31669 : char *str = NULL;
50 :
51 31669 : tor_vasprintf(&str, pattern, args);
52 31669 : tor_assert(str != NULL);
53 :
54 31669 : smartlist_add(sl, str);
55 31669 : }
56 :
57 : /** Reverse the order of the items in <b>sl</b>. */
58 : void
59 931 : smartlist_reverse(smartlist_t *sl)
60 : {
61 931 : int i, j;
62 931 : void *tmp;
63 931 : tor_assert(sl);
64 56162 : for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
65 55231 : tmp = sl->list[i];
66 55231 : sl->list[i] = sl->list[j];
67 55231 : sl->list[j] = tmp;
68 : }
69 931 : }
70 :
71 : /** If there are any strings in sl equal to element, remove and free them.
72 : * Does not preserve order. */
73 : void
74 48 : smartlist_string_remove(smartlist_t *sl, const char *element)
75 : {
76 48 : int i;
77 48 : tor_assert(sl);
78 48 : tor_assert(element);
79 552 : for (i = 0; i < sl->num_used; ++i) {
80 504 : if (!strcmp(element, sl->list[i])) {
81 48 : tor_free(sl->list[i]);
82 48 : sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
83 48 : i--; /* so we process the new i'th element */
84 48 : sl->list[sl->num_used] = NULL;
85 : }
86 : }
87 48 : }
88 :
89 : /** Return true iff <b>sl</b> has some element E such that
90 : * !strcmp(E,<b>element</b>)
91 : */
92 : int
93 2508 : smartlist_contains_string(const smartlist_t *sl, const char *element)
94 : {
95 2508 : int i;
96 2508 : if (!sl) return 0;
97 21490 : for (i=0; i < sl->num_used; i++)
98 20988 : if (strcmp((const char*)sl->list[i],element)==0)
99 : return 1;
100 : return 0;
101 : }
102 :
103 : /** If <b>element</b> is equal to an element of <b>sl</b>, return that
104 : * element's index. Otherwise, return -1. */
105 : int
106 2125 : smartlist_string_pos(const smartlist_t *sl, const char *element)
107 : {
108 2125 : int i;
109 2125 : if (!sl) return -1;
110 12281 : for (i=0; i < sl->num_used; i++)
111 12280 : if (strcmp((const char*)sl->list[i],element)==0)
112 2123 : return i;
113 : return -1;
114 : }
115 :
116 : /** If <b>element</b> is the same pointer as an element of <b>sl</b>, return
117 : * that element's index. Otherwise, return -1. */
118 : int
119 411 : smartlist_pos(const smartlist_t *sl, const void *element)
120 : {
121 411 : int i;
122 411 : if (!sl) return -1;
123 20930 : for (i=0; i < sl->num_used; i++)
124 20926 : if (element == sl->list[i])
125 406 : return i;
126 : return -1;
127 : }
128 :
129 : /** Return true iff <b>sl</b> has some element E such that
130 : * !strcasecmp(E,<b>element</b>)
131 : */
132 : int
133 36 : smartlist_contains_string_case(const smartlist_t *sl, const char *element)
134 : {
135 36 : int i;
136 36 : if (!sl) return 0;
137 54 : for (i=0; i < sl->num_used; i++)
138 23 : if (strcasecmp((const char*)sl->list[i],element)==0)
139 : return 1;
140 : return 0;
141 : }
142 :
143 : /** Return true iff <b>sl</b> has some element E such that E is equal
144 : * to the decimal encoding of <b>num</b>.
145 : */
146 : int
147 6 : smartlist_contains_int_as_string(const smartlist_t *sl, int num)
148 : {
149 6 : char buf[32]; /* long enough for 64-bit int, and then some. */
150 6 : tor_snprintf(buf,sizeof(buf),"%d", num);
151 6 : return smartlist_contains_string(sl, buf);
152 : }
153 :
154 : /** Return true iff the two lists contain the same strings in the same
155 : * order, or if they are both NULL. */
156 : int
157 19 : smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
158 : {
159 19 : if (sl1 == NULL)
160 2 : return sl2 == NULL;
161 17 : if (sl2 == NULL)
162 : return 0;
163 16 : if (smartlist_len(sl1) != smartlist_len(sl2))
164 : return 0;
165 27 : SMARTLIST_FOREACH(sl1, const char *, cp1, {
166 : const char *cp2 = smartlist_get(sl2, cp1_sl_idx);
167 : if (strcmp(cp1, cp2))
168 : return 0;
169 : });
170 : return 1;
171 : }
172 :
173 : /** Return true iff the two lists contain the same int pointer values in
174 : * the same order, or if they are both NULL. */
175 : int
176 10 : smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2)
177 : {
178 10 : if (sl1 == NULL)
179 2 : return sl2 == NULL;
180 8 : if (sl2 == NULL)
181 : return 0;
182 7 : if (smartlist_len(sl1) != smartlist_len(sl2))
183 : return 0;
184 14 : SMARTLIST_FOREACH(sl1, int *, cp1, {
185 : int *cp2 = smartlist_get(sl2, cp1_sl_idx);
186 : if (*cp1 != *cp2)
187 : return 0;
188 : });
189 : return 1;
190 : }
191 :
192 : /**
193 : * Return true if there is shallow equality between smartlists -
194 : * i.e. all indices correspond to exactly same object (pointer
195 : * values are matching). Otherwise, return false.
196 : */
197 : int
198 295 : smartlist_ptrs_eq(const smartlist_t *s1, const smartlist_t *s2)
199 : {
200 295 : if (s1 == s2)
201 : return 1;
202 :
203 : // Note: pointers cannot both be NULL at this point, because
204 : // above check.
205 295 : if (s1 == NULL || s2 == NULL)
206 : return 0;
207 :
208 295 : if (smartlist_len(s1) != smartlist_len(s2))
209 : return 0;
210 :
211 870 : for (int i = 0; i < smartlist_len(s1); i++) {
212 648 : if (smartlist_get(s1, i) != smartlist_get(s2, i))
213 : return 0;
214 : }
215 :
216 : return 1;
217 : }
218 :
219 : /** Return true iff <b>sl</b> has some element E such that
220 : * tor_memeq(E,<b>element</b>,DIGEST_LEN)
221 : */
222 : int
223 4 : smartlist_contains_digest(const smartlist_t *sl, const char *element)
224 : {
225 4 : int i;
226 4 : if (!sl) return 0;
227 7 : for (i=0; i < sl->num_used; i++)
228 6 : if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN))
229 : return 1;
230 : return 0;
231 : }
232 :
233 : /** Return true iff some element E of sl2 has smartlist_contains(sl1,E).
234 : */
235 : int
236 4 : smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
237 : {
238 4 : int i;
239 10 : for (i=0; i < sl2->num_used; i++)
240 9 : if (smartlist_contains(sl1, sl2->list[i]))
241 : return 1;
242 : return 0;
243 : }
244 :
245 : /** Remove every element E of sl1 such that !smartlist_contains(sl2,E).
246 : * Does not preserve the order of sl1.
247 : */
248 : void
249 1 : smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
250 : {
251 1 : int i;
252 6 : for (i=0; i < sl1->num_used; i++)
253 5 : if (!smartlist_contains(sl2, sl1->list[i])) {
254 2 : sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
255 2 : i--; /* so we process the new i'th element */
256 2 : sl1->list[sl1->num_used] = NULL;
257 : }
258 1 : }
259 :
260 : /** Remove every element E of sl1 such that smartlist_contains(sl2,E).
261 : * Does not preserve the order of sl1.
262 : */
263 : void
264 7 : smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
265 : {
266 7 : int i;
267 27 : for (i=0; i < sl2->num_used; i++)
268 20 : smartlist_remove(sl1, sl2->list[i]);
269 7 : }
270 :
271 : /** Allocate and return a new string containing the concatenation of
272 : * the elements of <b>sl</b>, in order, separated by <b>join</b>. If
273 : * <b>terminate</b> is true, also terminate the string with <b>join</b>.
274 : * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
275 : * the returned string. Requires that every element of <b>sl</b> is
276 : * NUL-terminated string.
277 : */
278 : char *
279 12072 : smartlist_join_strings(smartlist_t *sl, const char *join,
280 : int terminate, size_t *len_out)
281 : {
282 12072 : return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
283 : }
284 :
285 : /** As smartlist_join_strings, but instead of separating/terminated with a
286 : * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
287 : * at <b>join</b>. (Useful for generating a sequence of NUL-terminated
288 : * strings.)
289 : */
290 : char *
291 12073 : smartlist_join_strings2(smartlist_t *sl, const char *join,
292 : size_t join_len, int terminate, size_t *len_out)
293 : {
294 12073 : int i;
295 12073 : size_t n = 0;
296 12073 : char *r = NULL, *dst, *src;
297 :
298 12073 : tor_assert(sl);
299 12073 : tor_assert(join);
300 :
301 12073 : if (terminate)
302 285 : n = join_len;
303 :
304 164830 : for (i = 0; i < sl->num_used; ++i) {
305 152757 : n += strlen(sl->list[i]);
306 152757 : if (i+1 < sl->num_used) /* avoid double-counting the last one */
307 144445 : n += join_len;
308 : }
309 12073 : dst = r = tor_malloc(n+1);
310 176903 : for (i = 0; i < sl->num_used; ) {
311 3259284 : for (src = sl->list[i]; *src; )
312 3106527 : *dst++ = *src++;
313 152757 : if (++i < sl->num_used) {
314 144445 : memcpy(dst, join, join_len);
315 144445 : dst += join_len;
316 : }
317 : }
318 12073 : if (terminate) {
319 285 : memcpy(dst, join, join_len);
320 285 : dst += join_len;
321 : }
322 12073 : *dst = '\0';
323 :
324 12073 : if (len_out)
325 680 : *len_out = dst-r;
326 12073 : return r;
327 : }
328 :
329 : /** Sort the members of <b>sl</b> into an order defined by
330 : * the ordering function <b>compare</b>, which returns less then 0 if a
331 : * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
332 : */
333 : void
334 8590 : smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
335 : {
336 8590 : if (!sl->num_used)
337 : return;
338 7144 : qsort(sl->list, sl->num_used, sizeof(void*),
339 : (int (*)(const void *,const void*))compare);
340 : }
341 :
342 : /** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
343 : * return the most frequent member in the list. Break ties in favor of
344 : * later elements. If the list is empty, return NULL. If count_out is
345 : * non-null, set it to the count of the most frequent member.
346 : */
347 : void *
348 400 : smartlist_get_most_frequent_(const smartlist_t *sl,
349 : int (*compare)(const void **a, const void **b),
350 : int *count_out)
351 : {
352 400 : const void *most_frequent = NULL;
353 400 : int most_frequent_count = 0;
354 :
355 400 : const void *cur = NULL;
356 400 : int i, count=0;
357 :
358 400 : if (!sl->num_used) {
359 115 : if (count_out)
360 49 : *count_out = 0;
361 115 : return NULL;
362 : }
363 1137 : for (i = 0; i < sl->num_used; ++i) {
364 852 : const void *item = sl->list[i];
365 852 : if (cur && 0 == compare(&cur, &item)) {
366 547 : ++count;
367 : } else {
368 305 : if (cur && count >= most_frequent_count) {
369 19 : most_frequent = cur;
370 19 : most_frequent_count = count;
371 : }
372 305 : cur = item;
373 305 : count = 1;
374 : }
375 : }
376 285 : if (cur && count >= most_frequent_count) {
377 280 : most_frequent = cur;
378 280 : most_frequent_count = count;
379 : }
380 285 : if (count_out)
381 15 : *count_out = most_frequent_count;
382 : return (void*)most_frequent;
383 : }
384 :
385 : /** Given a sorted smartlist <b>sl</b> and the comparison function used to
386 : * sort it, remove all duplicate members. If free_fn is provided, calls
387 : * free_fn on each duplicate. Otherwise, just removes them. Preserves order.
388 : */
389 : void
390 1375 : smartlist_uniq(smartlist_t *sl,
391 : int (*compare)(const void **a, const void **b),
392 : void (*free_fn)(void *a))
393 : {
394 1375 : int i;
395 2409 : for (i=1; i < sl->num_used; ++i) {
396 1034 : if (compare((const void **)&(sl->list[i-1]),
397 1034 : (const void **)&(sl->list[i])) == 0) {
398 396 : if (free_fn)
399 396 : free_fn(sl->list[i]);
400 396 : smartlist_del_keeporder(sl, i--);
401 : }
402 : }
403 1375 : }
404 :
405 : /** Assuming the members of <b>sl</b> are in order, return a pointer to the
406 : * member that matches <b>key</b>. Ordering and matching are defined by a
407 : * <b>compare</b> function that returns 0 on a match; less than 0 if key is
408 : * less than member, and greater than 0 if key is greater then member.
409 : */
410 : void *
411 332287 : smartlist_bsearch(const smartlist_t *sl, const void *key,
412 : int (*compare)(const void *key, const void **member))
413 : {
414 332287 : int found, idx;
415 332287 : idx = smartlist_bsearch_idx(sl, key, compare, &found);
416 332287 : return found ? smartlist_get(sl, idx) : NULL;
417 : }
418 :
419 : /** Assuming the members of <b>sl</b> are in order, return the index of the
420 : * member that matches <b>key</b>. If no member matches, return the index of
421 : * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
422 : * is greater than <b>key</b>. Set <b>found_out</b> to true on a match, to
423 : * false otherwise. Ordering and matching are defined by a <b>compare</b>
424 : * function that returns 0 on a match; less than 0 if key is less than member,
425 : * and greater than 0 if key is greater then member.
426 : */
427 : int
428 400263 : smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
429 : int (*compare)(const void *key, const void **member),
430 : int *found_out)
431 : {
432 400263 : int hi, lo, cmp, mid, len, diff;
433 :
434 400263 : tor_assert(sl);
435 400263 : tor_assert(compare);
436 400263 : tor_assert(found_out);
437 :
438 400263 : len = smartlist_len(sl);
439 :
440 : /* Check for the trivial case of a zero-length list */
441 400263 : if (len == 0) {
442 74 : *found_out = 0;
443 : /* We already know smartlist_len(sl) is 0 in this case */
444 74 : return 0;
445 : }
446 :
447 : /* Okay, we have a real search to do */
448 400189 : tor_assert(len > 0);
449 400189 : lo = 0;
450 400189 : hi = len - 1;
451 :
452 : /*
453 : * These invariants are always true:
454 : *
455 : * For all i such that 0 <= i < lo, sl[i] < key
456 : * For all i such that hi < i <= len, sl[i] > key
457 : */
458 :
459 6113325 : while (lo <= hi) {
460 5847090 : diff = hi - lo;
461 : /*
462 : * We want mid = (lo + hi) / 2, but that could lead to overflow, so
463 : * instead diff = hi - lo (non-negative because of loop condition), and
464 : * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2).
465 : */
466 5847090 : mid = lo + (diff / 2);
467 5847090 : cmp = compare(key, (const void**) &(sl->list[mid]));
468 5847090 : if (cmp == 0) {
469 : /* sl[mid] == key; we found it */
470 133880 : *found_out = 1;
471 133880 : return mid;
472 5713210 : } else if (cmp > 0) {
473 : /*
474 : * key > sl[mid] and an index i such that sl[i] == key must
475 : * have i > mid if it exists.
476 : */
477 :
478 : /*
479 : * Since lo <= mid <= hi, hi can only decrease on each iteration (by
480 : * being set to mid - 1) and hi is initially len - 1, mid < len should
481 : * always hold, and this is not symmetric with the left end of list
482 : * mid > 0 test below. A key greater than the right end of the list
483 : * should eventually lead to lo == hi == mid == len - 1, and then
484 : * we set lo to len below and fall out to the same exit we hit for
485 : * a key in the middle of the list but not matching. Thus, we just
486 : * assert for consistency here rather than handle a mid == len case.
487 : */
488 4315728 : tor_assert(mid < len);
489 : /* Move lo to the element immediately after sl[mid] */
490 4315728 : lo = mid + 1;
491 : } else {
492 : /* This should always be true in this case */
493 1397482 : tor_assert(cmp < 0);
494 :
495 : /*
496 : * key < sl[mid] and an index i such that sl[i] == key must
497 : * have i < mid if it exists.
498 : */
499 :
500 1397482 : if (mid > 0) {
501 : /* Normal case, move hi to the element immediately before sl[mid] */
502 1397408 : hi = mid - 1;
503 : } else {
504 : /* These should always be true in this case */
505 74 : tor_assert(mid == lo);
506 74 : tor_assert(mid == 0);
507 : /*
508 : * We were at the beginning of the list and concluded that every
509 : * element e compares e > key.
510 : */
511 74 : *found_out = 0;
512 74 : return 0;
513 : }
514 : }
515 : }
516 :
517 : /*
518 : * lo > hi; we have no element matching key but we have elements falling
519 : * on both sides of it. The lo index points to the first element > key.
520 : */
521 266235 : tor_assert(lo == hi + 1); /* All other cases should have been handled */
522 266235 : tor_assert(lo >= 0);
523 266235 : tor_assert(lo <= len);
524 266235 : tor_assert(hi >= 0);
525 266235 : tor_assert(hi <= len);
526 :
527 266235 : if (lo < len) {
528 266050 : cmp = compare(key, (const void **) &(sl->list[lo]));
529 266050 : tor_assert(cmp < 0);
530 : } else {
531 185 : cmp = compare(key, (const void **) &(sl->list[len-1]));
532 185 : tor_assert(cmp > 0);
533 : }
534 :
535 266235 : *found_out = 0;
536 266235 : return lo;
537 : }
538 :
539 : /** Helper: compare two const char **s. */
540 : static int
541 4383 : compare_string_ptrs_(const void **_a, const void **_b)
542 : {
543 4383 : return strcmp((const char*)*_a, (const char*)*_b);
544 : }
545 :
546 : /** Sort a smartlist <b>sl</b> containing strings into lexically ascending
547 : * order. */
548 : void
549 343 : smartlist_sort_strings(smartlist_t *sl)
550 : {
551 343 : smartlist_sort(sl, compare_string_ptrs_);
552 343 : }
553 :
554 : /** Return the most frequent string in the sorted list <b>sl</b> */
555 : const char *
556 156 : smartlist_get_most_frequent_string(smartlist_t *sl)
557 : {
558 156 : return smartlist_get_most_frequent(sl, compare_string_ptrs_);
559 : }
560 :
561 : /** Return the most frequent string in the sorted list <b>sl</b>.
562 : * If <b>count_out</b> is provided, set <b>count_out</b> to the
563 : * number of times that string appears.
564 : */
565 : const char *
566 13 : smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out)
567 : {
568 13 : return smartlist_get_most_frequent_(sl, compare_string_ptrs_, count_out);
569 : }
570 :
571 : /** Remove duplicate strings from a sorted list, and free them with tor_free().
572 : */
573 : void
574 25 : smartlist_uniq_strings(smartlist_t *sl)
575 : {
576 25 : smartlist_uniq(sl, compare_string_ptrs_, tor_free_);
577 25 : }
578 :
579 : /** Helper: compare two pointers. */
580 : static int
581 257 : compare_ptrs_(const void **_a, const void **_b)
582 : {
583 257 : const void *a = *_a, *b = *_b;
584 257 : if (a<b)
585 : return -1;
586 144 : else if (a==b)
587 : return 0;
588 : else
589 134 : return 1;
590 : }
591 :
592 : /** Sort <b>sl</b> in ascending order of the pointers it contains. */
593 : void
594 10 : smartlist_sort_pointers(smartlist_t *sl)
595 : {
596 10 : smartlist_sort(sl, compare_ptrs_);
597 10 : }
598 :
599 : /* Heap-based priority queue implementation for O(lg N) insert and remove.
600 : * Recall that the heap property is that, for every index I, h[I] <
601 : * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
602 : *
603 : * For us to remove items other than the topmost item, each item must store
604 : * its own index within the heap. When calling the pqueue functions, tell
605 : * them about the offset of the field that stores the index within the item.
606 : *
607 : * Example:
608 : *
609 : * typedef struct timer_t {
610 : * struct timeval tv;
611 : * int heap_index;
612 : * } timer_t;
613 : *
614 : * static int compare(const void *p1, const void *p2) {
615 : * const timer_t *t1 = p1, *t2 = p2;
616 : * if (t1->tv.tv_sec < t2->tv.tv_sec) {
617 : * return -1;
618 : * } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
619 : * return 1;
620 : * } else {
621 : * return t1->tv.tv_usec - t2->tv_usec;
622 : * }
623 : * }
624 : *
625 : * void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
626 : * smartlist_pqueue_add(heap, compare, offsetof(timer_t, heap_index),
627 : * timer);
628 : * }
629 : *
630 : * void timer_heap_pop(smartlist_t *heap) {
631 : * return smartlist_pqueue_pop(heap, compare,
632 : * offsetof(timer_t, heap_index));
633 : * }
634 : */
635 :
636 : /** @{ */
637 : /** Functions to manipulate heap indices to find a node's parent and children.
638 : *
639 : * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
640 : * = 2*x + 1. But this is C, so we have to adjust a little. */
641 :
642 : /* MAX_PARENT_IDX is the largest IDX in the smartlist which might have
643 : * children whose indices fit inside an int.
644 : * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2;
645 : * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1;
646 : * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size.
647 : */
648 : #define MAX_PARENT_IDX ((INT_MAX - 2) / 2)
649 : /* If this is true, then i is small enough to potentially have children
650 : * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */
651 : #define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX)
652 : #define LEFT_CHILD(i) ( 2*(i) + 1 )
653 : #define RIGHT_CHILD(i) ( 2*(i) + 2 )
654 : #define PARENT(i) ( ((i)-1) / 2 )
655 : /** @} */
656 :
657 : /** @{ */
658 : /** Helper macros for heaps: Given a local variable <b>idx_field_offset</b>
659 : * set to the offset of an integer index within the heap element structure,
660 : * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to
661 : * where p's index is stored. Given additionally a local smartlist <b>sl</b>,
662 : * UPDATE_IDX(i) sets the index of the element at <b>i</b> to the correct
663 : * value (that is, to <b>i</b>).
664 : */
665 : #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
666 :
667 : #define UPDATE_IDX(i) do { \
668 : void *updated = sl->list[i]; \
669 : *IDXP(updated) = i; \
670 : } while (0)
671 :
672 : #define IDX_OF_ITEM(p) (*IDXP(p))
673 : /** @} */
674 :
675 : /** Helper. <b>sl</b> may have at most one violation of the heap property:
676 : * the item at <b>idx</b> may be greater than one or both of its children.
677 : * Restore the heap property. */
678 : static inline void
679 43 : smartlist_heapify(smartlist_t *sl,
680 : int (*compare)(const void *a, const void *b),
681 : ptrdiff_t idx_field_offset,
682 : int idx)
683 : {
684 83 : while (1) {
685 63 : if (! IDX_MAY_HAVE_CHILDREN(idx)) {
686 : /* idx is so large that it cannot have any children, since doing so
687 : * would mean the smartlist was over-capacity. Therefore it cannot
688 : * violate the heap property by being greater than a child (since it
689 : * doesn't have any). */
690 : return;
691 : }
692 :
693 63 : int left_idx = LEFT_CHILD(idx);
694 63 : int best_idx;
695 :
696 63 : if (left_idx >= sl->num_used)
697 : return;
698 24 : if (compare(sl->list[idx],sl->list[left_idx]) < 0)
699 : best_idx = idx;
700 : else
701 19 : best_idx = left_idx;
702 43 : if (left_idx+1 < sl->num_used &&
703 19 : compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
704 8 : best_idx = left_idx + 1;
705 :
706 24 : if (best_idx == idx) {
707 : return;
708 : } else {
709 20 : void *tmp = sl->list[idx];
710 20 : sl->list[idx] = sl->list[best_idx];
711 20 : sl->list[best_idx] = tmp;
712 20 : UPDATE_IDX(idx);
713 20 : UPDATE_IDX(best_idx);
714 :
715 20 : idx = best_idx;
716 : }
717 : }
718 : }
719 :
720 : /** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
721 : * determined by <b>compare</b> and the offset of the item in the heap is
722 : * stored in an int-typed field at position <b>idx_field_offset</b> within
723 : * item.
724 : */
725 : void
726 91 : smartlist_pqueue_add(smartlist_t *sl,
727 : int (*compare)(const void *a, const void *b),
728 : ptrdiff_t idx_field_offset,
729 : void *item)
730 : {
731 91 : int idx;
732 91 : smartlist_add(sl,item);
733 91 : UPDATE_IDX(sl->num_used-1);
734 :
735 108 : for (idx = sl->num_used - 1; idx; ) {
736 56 : int parent = PARENT(idx);
737 56 : if (compare(sl->list[idx], sl->list[parent]) < 0) {
738 17 : void *tmp = sl->list[parent];
739 17 : sl->list[parent] = sl->list[idx];
740 17 : sl->list[idx] = tmp;
741 17 : UPDATE_IDX(parent);
742 17 : UPDATE_IDX(idx);
743 17 : idx = parent;
744 : } else {
745 : return;
746 : }
747 : }
748 : }
749 :
750 : /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
751 : * where order is determined by <b>compare</b> and the item's position is
752 : * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
753 : * not be empty. */
754 : void *
755 57 : smartlist_pqueue_pop(smartlist_t *sl,
756 : int (*compare)(const void *a, const void *b),
757 : ptrdiff_t idx_field_offset)
758 : {
759 57 : void *top;
760 57 : tor_assert(sl->num_used);
761 :
762 57 : top = sl->list[0];
763 57 : *IDXP(top)=-1;
764 57 : if (--sl->num_used) {
765 35 : sl->list[0] = sl->list[sl->num_used];
766 35 : sl->list[sl->num_used] = NULL;
767 35 : UPDATE_IDX(0);
768 35 : smartlist_heapify(sl, compare, idx_field_offset, 0);
769 : }
770 57 : sl->list[sl->num_used] = NULL;
771 57 : return top;
772 : }
773 :
774 : /** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
775 : * where order is determined by <b>compare</b> and the item's position is
776 : * stored at position <b>idx_field_offset</b> within the item. <b>sl</b> must
777 : * not be empty. */
778 : void
779 31 : smartlist_pqueue_remove(smartlist_t *sl,
780 : int (*compare)(const void *a, const void *b),
781 : ptrdiff_t idx_field_offset,
782 : void *item)
783 : {
784 31 : int idx = IDX_OF_ITEM(item);
785 31 : tor_assert(idx >= 0);
786 31 : tor_assert(sl->list[idx] == item);
787 31 : --sl->num_used;
788 31 : *IDXP(item) = -1;
789 31 : if (idx == sl->num_used) {
790 23 : sl->list[sl->num_used] = NULL;
791 23 : return;
792 : } else {
793 8 : sl->list[idx] = sl->list[sl->num_used];
794 8 : sl->list[sl->num_used] = NULL;
795 8 : UPDATE_IDX(idx);
796 8 : smartlist_heapify(sl, compare, idx_field_offset, idx);
797 : }
798 : }
799 :
800 : /** Assert that the heap property is correctly maintained by the heap stored
801 : * in <b>sl</b>, where order is determined by <b>compare</b>. */
802 : void
803 12 : smartlist_pqueue_assert_ok(smartlist_t *sl,
804 : int (*compare)(const void *a, const void *b),
805 : ptrdiff_t idx_field_offset)
806 : {
807 12 : int i;
808 80 : for (i = sl->num_used - 1; i >= 0; --i) {
809 68 : if (i>0)
810 58 : tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
811 68 : tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
812 : }
813 12 : }
814 :
815 : /** Helper: compare two DIGEST_LEN digests. */
816 : static int
817 681 : compare_digests_(const void **_a, const void **_b)
818 : {
819 681 : return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
820 : }
821 :
822 : /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
823 : void
824 43 : smartlist_sort_digests(smartlist_t *sl)
825 : {
826 43 : smartlist_sort(sl, compare_digests_);
827 43 : }
828 :
829 : /** Remove duplicate digests from a sorted list, and free them with tor_free().
830 : */
831 : void
832 17 : smartlist_uniq_digests(smartlist_t *sl)
833 : {
834 17 : smartlist_uniq(sl, compare_digests_, tor_free_);
835 17 : }
836 :
837 : /** Helper: compare two DIGEST256_LEN digests. */
838 : static int
839 346 : compare_digests256_(const void **_a, const void **_b)
840 : {
841 346 : return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
842 : }
843 :
844 : /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
845 : void
846 94 : smartlist_sort_digests256(smartlist_t *sl)
847 : {
848 94 : smartlist_sort(sl, compare_digests256_);
849 94 : }
850 :
851 : /** Return the most frequent member of the sorted list of DIGEST256_LEN
852 : * digests in <b>sl</b> */
853 : const uint8_t *
854 90 : smartlist_get_most_frequent_digest256(smartlist_t *sl)
855 : {
856 90 : return smartlist_get_most_frequent(sl, compare_digests256_);
857 : }
858 :
859 : /** Remove duplicate 256-bit digests from a sorted list, and free them with
860 : * tor_free().
861 : */
862 : void
863 4 : smartlist_uniq_digests256(smartlist_t *sl)
864 : {
865 4 : smartlist_uniq(sl, compare_digests256_, tor_free_);
866 4 : }
|
