Tor  0.4.7.0-alpha-dev
smartlist.c
Go to the documentation of this file.
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 
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"
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 smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern, ...)
37 {
38  va_list ap;
39  va_start(ap, pattern);
40  smartlist_add_vasprintf(sl, pattern, ap);
41  va_end(ap);
42 }
43 
44 /** va_list-based backend of smartlist_add_asprintf. */
45 void
46 smartlist_add_vasprintf(struct smartlist_t *sl, const char *pattern,
47  va_list args)
48 {
49  char *str = NULL;
50 
51  tor_vasprintf(&str, pattern, args);
52  tor_assert(str != NULL);
53 
54  smartlist_add(sl, str);
55 }
56 
57 /** Reverse the order of the items in <b>sl</b>. */
58 void
60 {
61  int i, j;
62  void *tmp;
63  tor_assert(sl);
64  for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
65  tmp = sl->list[i];
66  sl->list[i] = sl->list[j];
67  sl->list[j] = tmp;
68  }
69 }
70 
71 /** If there are any strings in sl equal to element, remove and free them.
72  * Does not preserve order. */
73 void
74 smartlist_string_remove(smartlist_t *sl, const char *element)
75 {
76  int i;
77  tor_assert(sl);
78  tor_assert(element);
79  for (i = 0; i < sl->num_used; ++i) {
80  if (!strcmp(element, sl->list[i])) {
81  tor_free(sl->list[i]);
82  sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
83  i--; /* so we process the new i'th element */
84  sl->list[sl->num_used] = NULL;
85  }
86  }
87 }
88 
89 /** Return true iff <b>sl</b> has some element E such that
90  * !strcmp(E,<b>element</b>)
91  */
92 int
93 smartlist_contains_string(const smartlist_t *sl, const char *element)
94 {
95  int i;
96  if (!sl) return 0;
97  for (i=0; i < sl->num_used; i++)
98  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 smartlist_string_pos(const smartlist_t *sl, const char *element)
107 {
108  int i;
109  if (!sl) return -1;
110  for (i=0; i < sl->num_used; i++)
111  if (strcmp((const char*)sl->list[i],element)==0)
112  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 smartlist_pos(const smartlist_t *sl, const void *element)
120 {
121  int i;
122  if (!sl) return -1;
123  for (i=0; i < sl->num_used; i++)
124  if (element == sl->list[i])
125  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 smartlist_contains_string_case(const smartlist_t *sl, const char *element)
134 {
135  int i;
136  if (!sl) return 0;
137  for (i=0; i < sl->num_used; i++)
138  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
148 {
149  char buf[32]; /* long enough for 64-bit int, and then some. */
150  tor_snprintf(buf,sizeof(buf),"%d", num);
151  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
158 {
159  if (sl1 == NULL)
160  return sl2 == NULL;
161  if (sl2 == NULL)
162  return 0;
163  if (smartlist_len(sl1) != smartlist_len(sl2))
164  return 0;
165  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
177 {
178  if (sl1 == NULL)
179  return sl2 == NULL;
180  if (sl2 == NULL)
181  return 0;
182  if (smartlist_len(sl1) != smartlist_len(sl2))
183  return 0;
184  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
199 {
200  if (s1 == s2)
201  return 1;
202 
203  // Note: pointers cannot both be NULL at this point, because
204  // above check.
205  if (s1 == NULL || s2 == NULL)
206  return 0;
207 
208  if (smartlist_len(s1) != smartlist_len(s2))
209  return 0;
210 
211  for (int i = 0; i < smartlist_len(s1); i++) {
212  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 smartlist_contains_digest(const smartlist_t *sl, const char *element)
224 {
225  int i;
226  if (!sl) return 0;
227  for (i=0; i < sl->num_used; i++)
228  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
237 {
238  int i;
239  for (i=0; i < sl2->num_used; i++)
240  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
250 {
251  int i;
252  for (i=0; i < sl1->num_used; i++)
253  if (!smartlist_contains(sl2, sl1->list[i])) {
254  sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
255  i--; /* so we process the new i'th element */
256  sl1->list[sl1->num_used] = NULL;
257  }
258 }
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
265 {
266  int i;
267  for (i=0; i < sl2->num_used; i++)
268  smartlist_remove(sl1, sl2->list[i]);
269 }
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 smartlist_join_strings(smartlist_t *sl, const char *join,
280  int terminate, size_t *len_out)
281 {
282  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 smartlist_join_strings2(smartlist_t *sl, const char *join,
292  size_t join_len, int terminate, size_t *len_out)
293 {
294  int i;
295  size_t n = 0;
296  char *r = NULL, *dst, *src;
297 
298  tor_assert(sl);
299  tor_assert(join);
300 
301  if (terminate)
302  n = join_len;
303 
304  for (i = 0; i < sl->num_used; ++i) {
305  n += strlen(sl->list[i]);
306  if (i+1 < sl->num_used) /* avoid double-counting the last one */
307  n += join_len;
308  }
309  dst = r = tor_malloc(n+1);
310  for (i = 0; i < sl->num_used; ) {
311  for (src = sl->list[i]; *src; )
312  *dst++ = *src++;
313  if (++i < sl->num_used) {
314  memcpy(dst, join, join_len);
315  dst += join_len;
316  }
317  }
318  if (terminate) {
319  memcpy(dst, join, join_len);
320  dst += join_len;
321  }
322  *dst = '\0';
323 
324  if (len_out)
325  *len_out = dst-r;
326  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 smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
335 {
336  if (!sl->num_used)
337  return;
338  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 *
349  int (*compare)(const void **a, const void **b),
350  int *count_out)
351 {
352  const void *most_frequent = NULL;
353  int most_frequent_count = 0;
354 
355  const void *cur = NULL;
356  int i, count=0;
357 
358  if (!sl->num_used) {
359  if (count_out)
360  *count_out = 0;
361  return NULL;
362  }
363  for (i = 0; i < sl->num_used; ++i) {
364  const void *item = sl->list[i];
365  if (cur && 0 == compare(&cur, &item)) {
366  ++count;
367  } else {
368  if (cur && count >= most_frequent_count) {
369  most_frequent = cur;
370  most_frequent_count = count;
371  }
372  cur = item;
373  count = 1;
374  }
375  }
376  if (cur && count >= most_frequent_count) {
377  most_frequent = cur;
378  most_frequent_count = count;
379  }
380  if (count_out)
381  *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
391  int (*compare)(const void **a, const void **b),
392  void (*free_fn)(void *a))
393 {
394  int i;
395  for (i=1; i < sl->num_used; ++i) {
396  if (compare((const void **)&(sl->list[i-1]),
397  (const void **)&(sl->list[i])) == 0) {
398  if (free_fn)
399  free_fn(sl->list[i]);
400  smartlist_del_keeporder(sl, i--);
401  }
402  }
403 }
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 smartlist_bsearch(const smartlist_t *sl, const void *key,
412  int (*compare)(const void *key, const void **member))
413 {
414  int found, idx;
415  idx = smartlist_bsearch_idx(sl, key, compare, &found);
416  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 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  int hi, lo, cmp, mid, len, diff;
433 
434  tor_assert(sl);
435  tor_assert(compare);
436  tor_assert(found_out);
437 
438  len = smartlist_len(sl);
439 
440  /* Check for the trivial case of a zero-length list */
441  if (len == 0) {
442  *found_out = 0;
443  /* We already know smartlist_len(sl) is 0 in this case */
444  return 0;
445  }
446 
447  /* Okay, we have a real search to do */
448  tor_assert(len > 0);
449  lo = 0;
450  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  while (lo <= hi) {
460  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  mid = lo + (diff / 2);
467  cmp = compare(key, (const void**) &(sl->list[mid]));
468  if (cmp == 0) {
469  /* sl[mid] == key; we found it */
470  *found_out = 1;
471  return mid;
472  } 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  tor_assert(mid < len);
489  /* Move lo to the element immediately after sl[mid] */
490  lo = mid + 1;
491  } else {
492  /* This should always be true in this case */
493  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  if (mid > 0) {
501  /* Normal case, move hi to the element immediately before sl[mid] */
502  hi = mid - 1;
503  } else {
504  /* These should always be true in this case */
505  tor_assert(mid == lo);
506  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  *found_out = 0;
512  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  tor_assert(lo == hi + 1); /* All other cases should have been handled */
522  tor_assert(lo >= 0);
523  tor_assert(lo <= len);
524  tor_assert(hi >= 0);
525  tor_assert(hi <= len);
526 
527  if (lo < len) {
528  cmp = compare(key, (const void **) &(sl->list[lo]));
529  tor_assert(cmp < 0);
530  } else {
531  cmp = compare(key, (const void **) &(sl->list[len-1]));
532  tor_assert(cmp > 0);
533  }
534 
535  *found_out = 0;
536  return lo;
537 }
538 
539 /** Helper: compare two const char **s. */
540 static int
541 compare_string_ptrs_(const void **_a, const void **_b)
542 {
543  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
550 {
552 }
553 
554 /** Return the most frequent string in the sorted list <b>sl</b> */
555 const char *
557 {
558  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 *
567 {
568  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
575 {
577 }
578 
579 /** Helper: compare two pointers. */
580 static int
581 compare_ptrs_(const void **_a, const void **_b)
582 {
583  const void *a = *_a, *b = *_b;
584  if (a<b)
585  return -1;
586  else if (a==b)
587  return 0;
588  else
589  return 1;
590 }
591 
592 /** Sort <b>sl</b> in ascending order of the pointers it contains. */
593 void
595 {
597 }
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
680  int (*compare)(const void *a, const void *b),
681  ptrdiff_t idx_field_offset,
682  int idx)
683 {
684  while (1) {
685  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  int left_idx = LEFT_CHILD(idx);
694  int best_idx;
695 
696  if (left_idx >= sl->num_used)
697  return;
698  if (compare(sl->list[idx],sl->list[left_idx]) < 0)
699  best_idx = idx;
700  else
701  best_idx = left_idx;
702  if (left_idx+1 < sl->num_used &&
703  compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
704  best_idx = left_idx + 1;
705 
706  if (best_idx == idx) {
707  return;
708  } else {
709  void *tmp = sl->list[idx];
710  sl->list[idx] = sl->list[best_idx];
711  sl->list[best_idx] = tmp;
712  UPDATE_IDX(idx);
713  UPDATE_IDX(best_idx);
714 
715  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
727  int (*compare)(const void *a, const void *b),
728  ptrdiff_t idx_field_offset,
729  void *item)
730 {
731  int idx;
732  smartlist_add(sl,item);
733  UPDATE_IDX(sl->num_used-1);
734 
735  for (idx = sl->num_used - 1; idx; ) {
736  int parent = PARENT(idx);
737  if (compare(sl->list[idx], sl->list[parent]) < 0) {
738  void *tmp = sl->list[parent];
739  sl->list[parent] = sl->list[idx];
740  sl->list[idx] = tmp;
741  UPDATE_IDX(parent);
742  UPDATE_IDX(idx);
743  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 *
756  int (*compare)(const void *a, const void *b),
757  ptrdiff_t idx_field_offset)
758 {
759  void *top;
760  tor_assert(sl->num_used);
761 
762  top = sl->list[0];
763  *IDXP(top)=-1;
764  if (--sl->num_used) {
765  sl->list[0] = sl->list[sl->num_used];
766  sl->list[sl->num_used] = NULL;
767  UPDATE_IDX(0);
768  smartlist_heapify(sl, compare, idx_field_offset, 0);
769  }
770  sl->list[sl->num_used] = NULL;
771  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
780  int (*compare)(const void *a, const void *b),
781  ptrdiff_t idx_field_offset,
782  void *item)
783 {
784  int idx = IDX_OF_ITEM(item);
785  tor_assert(idx >= 0);
786  tor_assert(sl->list[idx] == item);
787  --sl->num_used;
788  *IDXP(item) = -1;
789  if (idx == sl->num_used) {
790  sl->list[sl->num_used] = NULL;
791  return;
792  } else {
793  sl->list[idx] = sl->list[sl->num_used];
794  sl->list[sl->num_used] = NULL;
795  UPDATE_IDX(idx);
796  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
804  int (*compare)(const void *a, const void *b),
805  ptrdiff_t idx_field_offset)
806 {
807  int i;
808  for (i = sl->num_used - 1; i >= 0; --i) {
809  if (i>0)
810  tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
811  tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
812  }
813 }
814 
815 /** Helper: compare two DIGEST_LEN digests. */
816 static int
817 compare_digests_(const void **_a, const void **_b)
818 {
819  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
825 {
827 }
828 
829 /** Remove duplicate digests from a sorted list, and free them with tor_free().
830  */
831 void
833 {
835 }
836 
837 /** Helper: compare two DIGEST256_LEN digests. */
838 static int
839 compare_digests256_(const void **_a, const void **_b)
840 {
841  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
847 {
849 }
850 
851 /** Return the most frequent member of the sorted list of DIGEST256_LEN
852  * digests in <b>sl</b> */
853 const uint8_t *
855 {
856  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
864 {
866 }
Locale-independent character-type inspection (header)
Header for compat_string.c.
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
int tor_memcmp(const void *a, const void *b, size_t len)
Definition: di_ops.c:31
Headers for di_ops.c.
Definitions for common sizes of cryptographic digests.
#define DIGEST_LEN
Definition: digest_sizes.h:20
#define DIGEST256_LEN
Definition: digest_sizes.h:23
void tor_free_(void *mem)
Definition: malloc.c:227
Headers for util_malloc.c.
#define tor_free(p)
Definition: malloc.h:52
int tor_vasprintf(char **strp, const char *fmt, va_list args)
Definition: printf.c:96
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
Header for printf.c.
void smartlist_sort_digests(smartlist_t *sl)
Definition: smartlist.c:824
int smartlist_ptrs_eq(const smartlist_t *s1, const smartlist_t *s2)
Definition: smartlist.c:198
void smartlist_sort_digests256(smartlist_t *sl)
Definition: smartlist.c:846
void smartlist_string_remove(smartlist_t *sl, const char *element)
Definition: smartlist.c:74
void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:249
void smartlist_uniq_digests(smartlist_t *sl)
Definition: smartlist.c:832
void * smartlist_get_most_frequent_(const smartlist_t *sl, int(*compare)(const void **a, const void **b), int *count_out)
Definition: smartlist.c:348
int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:157
const char * smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out)
Definition: smartlist.c:566
void smartlist_pqueue_assert_ok(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
Definition: smartlist.c:803
int smartlist_contains_digest(const smartlist_t *sl, const char *element)
Definition: smartlist.c:223
void smartlist_uniq_digests256(smartlist_t *sl)
Definition: smartlist.c:863
void smartlist_add_vasprintf(struct smartlist_t *sl, const char *pattern, va_list args)
Definition: smartlist.c:46
int smartlist_contains_string_case(const smartlist_t *sl, const char *element)
Definition: smartlist.c:133
static int compare_digests_(const void **_a, const void **_b)
Definition: smartlist.c:817
void smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern,...)
Definition: smartlist.c:36
int smartlist_pos(const smartlist_t *sl, const void *element)
Definition: smartlist.c:119
void smartlist_reverse(smartlist_t *sl)
Definition: smartlist.c:59
void * smartlist_bsearch(const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member))
Definition: smartlist.c:411
#define IDXP(p)
Definition: smartlist.c:665
int smartlist_contains_int_as_string(const smartlist_t *sl, int num)
Definition: smartlist.c:147
const uint8_t * smartlist_get_most_frequent_digest256(smartlist_t *sl)
Definition: smartlist.c:854
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:264
void smartlist_uniq_strings(smartlist_t *sl)
Definition: smartlist.c:574
void smartlist_sort_strings(smartlist_t *sl)
Definition: smartlist.c:549
static int compare_ptrs_(const void **_a, const void **_b)
Definition: smartlist.c:581
static int compare_digests256_(const void **_a, const void **_b)
Definition: smartlist.c:839
char * smartlist_join_strings2(smartlist_t *sl, const char *join, size_t join_len, int terminate, size_t *len_out)
Definition: smartlist.c:291
void smartlist_pqueue_add(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, void *item)
Definition: smartlist.c:726
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
Definition: smartlist.c:279
int smartlist_contains_string(const smartlist_t *sl, const char *element)
Definition: smartlist.c:93
static int compare_string_ptrs_(const void **_a, const void **_b)
Definition: smartlist.c:541
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
Definition: smartlist.c:755
void smartlist_sort(smartlist_t *sl, int(*compare)(const void **a, const void **b))
Definition: smartlist.c:334
const char * smartlist_get_most_frequent_string(smartlist_t *sl)
Definition: smartlist.c:556
int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:176
void smartlist_pqueue_remove(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, void *item)
Definition: smartlist.c:779
int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member), int *found_out)
Definition: smartlist.c:428
static void smartlist_heapify(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, int idx)
Definition: smartlist.c:679
void smartlist_sort_pointers(smartlist_t *sl)
Definition: smartlist.c:594
int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:236
int smartlist_string_pos(const smartlist_t *sl, const char *element)
Definition: smartlist.c:106
void smartlist_uniq(smartlist_t *sl, int(*compare)(const void **a, const void **b), void(*free_fn)(void *a))
Definition: smartlist.c:390
Header for smartlist.c.
int smartlist_contains(const smartlist_t *sl, const void *element)
void smartlist_add(smartlist_t *sl, void *element)
void smartlist_remove(smartlist_t *sl, const void *element)
void smartlist_del_keeporder(smartlist_t *sl, int idx)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
void ** list
Headers for torerr.c.
Macros to manage assertions, fatal and non-fatal.
#define tor_assert(expr)
Definition: util_bug.h:102
Header for util_string.c.