1 files changed, 175 insertions, 10 deletions

diff --git a/src/common/container.c b/src/common/container.c
index c649787c0f..f452a51e42 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -44,7 +44,8 @@ smartlist_create(void)
 void
 smartlist_free(smartlist_t *sl)
 {
-  tor_assert(sl != NULL);
+  if (!sl)
+    return;
   tor_free(sl->list);
   tor_free(sl);
 }
@@ -459,6 +460,42 @@ smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
         (int (*)(const void *,const void*))compare);
 }
 
+/** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
+ * return the most frequent member in the list.  Break ties in favor of
+ * later elements.  If the list is empty, return NULL.
+ */
+void *
+smartlist_get_most_frequent(const smartlist_t *sl,
+                            int (*compare)(const void **a, const void **b))
+{
+  const void *most_frequent = NULL;
+  int most_frequent_count = 0;
+
+  const void *cur = NULL;
+  int i, count=0;
+
+  if (!sl->num_used)
+    return NULL;
+  for (i = 0; i < sl->num_used; ++i) {
+    const void *item = sl->list[i];
+    if (cur && 0 == compare(&cur, &item)) {
+      ++count;
+    } else {
+      if (cur && count >= most_frequent_count) {
+        most_frequent = cur;
+        most_frequent_count = count;
+      }
+      cur = item;
+      count = 1;
+    }
+  }
+  if (cur && count >= most_frequent_count) {
+    most_frequent = cur;
+    most_frequent_count = count;
+  }
+  return (void*)most_frequent;
+}
+
 /** Given a sorted smartlist <b>sl</b> and the comparison function used to
  * sort it, remove all duplicate members.  If free_fn is provided, calls
  * free_fn on each duplicate.  Otherwise, just removes them.  Preserves order.
@@ -550,6 +587,13 @@ smartlist_sort_strings(smartlist_t *sl)
   smartlist_sort(sl, _compare_string_ptrs);
 }
 
+/** Return the most frequent string in the sorted list <b>sl</b> */
+char *
+smartlist_get_most_frequent_string(smartlist_t *sl)
+{
+  return smartlist_get_most_frequent(sl, _compare_string_ptrs);
+}
+
 /** Remove duplicate strings from a sorted list, and free them with tor_free().
  */
 void
@@ -561,6 +605,38 @@ smartlist_uniq_strings(smartlist_t *sl)
 /* Heap-based priority queue implementation for O(lg N) insert and remove.
  * Recall that the heap property is that, for every index I, h[I] <
  * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
+ *
+ * For us to remove items other than the topmost item, each item must store
+ * its own index within the heap.  When calling the pqueue functions, tell
+ * them about the offset of the field that stores the index within the item.
+ *
+ * Example:
+ *
+ *   typedef struct timer_t {
+ *     struct timeval tv;
+ *     int heap_index;
+ *   } timer_t;
+ *
+ *   static int compare(const void *p1, const void *p2) {
+ *     const timer_t *t1 = p1, *t2 = p2;
+ *     if (t1->tv.tv_sec < t2->tv.tv_sec) {
+ *        return -1;
+ *     } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
+ *        return 1;
+ *     } else {
+ *        return t1->tv.tv_usec - t2->tv_usec;
+ *     }
+ *   }
+ *
+ *   void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
+ *      smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index),
+ *         timer);
+ *   }
+ *
+ *   void timer_heap_pop(smartlist_t *heap) {
+ *      return smartlist_pqueue_pop(heap, compare,
+ *         STRUCT_OFFSET(timer_t, heap_index));
+ *   }
  */
 
 /* For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
@@ -572,12 +648,22 @@ smartlist_uniq_strings(smartlist_t *sl)
 #define RIGHT_CHILD(i) ( 2*(i) + 2 )
 #define PARENT(i)      ( ((i)-1) / 2 )
 
+#define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
+
+#define UPDATE_IDX(i)  do {                            \
+    void *updated = sl->list[i];                       \
+    *IDXP(updated) = i;                                \
+  } while (0)
+
+#define IDX_OF_ITEM(p) (*IDXP(p))
+
 /** Helper. <b>sl</b> may have at most one violation of the heap property:
  * the item at <b>idx</b> may be greater than one or both of its children.
  * Restore the heap property. */
 static INLINE void
 smartlist_heapify(smartlist_t *sl,
                   int (*compare)(const void *a, const void *b),
+                  int idx_field_offset,
                   int idx)
 {
   while (1) {
@@ -600,21 +686,28 @@ smartlist_heapify(smartlist_t *sl,
       void *tmp = sl->list[idx];
       sl->list[idx] = sl->list[best_idx];
       sl->list[best_idx] = tmp;
+      UPDATE_IDX(idx);
+      UPDATE_IDX(best_idx);
 
       idx = best_idx;
     }
   }
 }
 
-/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order
- * is determined by <b>compare</b>. */
+/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
+ * determined by <b>compare</b> and the offset of the item in the heap is
+ * stored in an int-typed field at position <b>idx_field_offset</b> within
+ * item.
+ */
 void
 smartlist_pqueue_add(smartlist_t *sl,
                      int (*compare)(const void *a, const void *b),
+                     int idx_field_offset,
                      void *item)
 {
   int idx;
   smartlist_add(sl,item);
+  UPDATE_IDX(sl->num_used-1);
 
   for (idx = sl->num_used - 1; idx; ) {
     int parent = PARENT(idx);
@@ -622,6 +715,8 @@ smartlist_pqueue_add(smartlist_t *sl,
       void *tmp = sl->list[parent];
       sl->list[parent] = sl->list[idx];
       sl->list[idx] = tmp;
+      UPDATE_IDX(parent);
+      UPDATE_IDX(idx);
       idx = parent;
     } else {
       return;
@@ -630,32 +725,63 @@ smartlist_pqueue_add(smartlist_t *sl,
 }
 
 /** Remove and return the top-priority item from the heap stored in <b>sl</b>,
- * where order is determined by <b>compare</b>.  <b>sl</b> must not be
- * empty. */
+ * where order is determined by <b>compare</b> and the item's position is
+ * stored at position <b>idx_field_offset</b> within the item.  <b>sl</b> must
+ * not be empty. */
 void *
 smartlist_pqueue_pop(smartlist_t *sl,
-                     int (*compare)(const void *a, const void *b))
+                     int (*compare)(const void *a, const void *b),
+                     int idx_field_offset)
 {
   void *top;
   tor_assert(sl->num_used);
 
   top = sl->list[0];
+  *IDXP(top)=-1;
   if (--sl->num_used) {
     sl->list[0] = sl->list[sl->num_used];
-    smartlist_heapify(sl, compare, 0);
+    UPDATE_IDX(0);
+    smartlist_heapify(sl, compare, idx_field_offset, 0);
   }
   return top;
 }
 
+/** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
+ * where order is determined by <b>compare</b> and the item's position is
+ * stored at position <b>idx_field_offset</b> within the item.  <b>sl</b> must
+ * not be empty. */
+void
+smartlist_pqueue_remove(smartlist_t *sl,
+                        int (*compare)(const void *a, const void *b),
+                        int idx_field_offset,
+                        void *item)
+{
+  int idx = IDX_OF_ITEM(item);
+  tor_assert(idx >= 0);
+  tor_assert(sl->list[idx] == item);
+  --sl->num_used;
+  *IDXP(item) = -1;
+  if (idx == sl->num_used) {
+    return;
+  } else {
+    sl->list[idx] = sl->list[sl->num_used];
+    UPDATE_IDX(idx);
+    smartlist_heapify(sl, compare, idx_field_offset, idx);
+  }
+}
+
 /** Assert that the heap property is correctly maintained by the heap stored
  * in <b>sl</b>, where order is determined by <b>compare</b>. */
 void
 smartlist_pqueue_assert_ok(smartlist_t *sl,
-                           int (*compare)(const void *a, const void *b))
+                           int (*compare)(const void *a, const void *b),
+                           int idx_field_offset)
 {
   int i;
-  for (i = sl->num_used - 1; i > 0; --i) {
-    tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
+  for (i = sl->num_used - 1; i >= 0; --i) {
+    if (i>0)
+      tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
+    tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
   }
 }
 
@@ -681,6 +807,37 @@ smartlist_uniq_digests(smartlist_t *sl)
   smartlist_uniq(sl, _compare_digests, _tor_free);
 }
 
+/** Helper: compare two DIGEST256_LEN digests. */
+static int
+_compare_digests256(const void **_a, const void **_b)
+{
+  return memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
+}
+
+/** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
+void
+smartlist_sort_digests256(smartlist_t *sl)
+{
+  smartlist_sort(sl, _compare_digests256);
+}
+
+/** Return the most frequent member of the sorted list of DIGEST256_LEN
+ * digests in <b>sl</b> */
+char *
+smartlist_get_most_frequent_digest256(smartlist_t *sl)
+{
+  return smartlist_get_most_frequent(sl, _compare_digests256);
+}
+
+/** Remove duplicate 256-bit digests from a sorted list, and free them with
+ * tor_free().
+ */
+void
+smartlist_uniq_digests256(smartlist_t *sl)
+{
+  smartlist_uniq(sl, _compare_digests256, _tor_free);
+}
+
 /** Helper: Declare an entry type and a map type to implement a mapping using
  * ht.h.  The map type will be called <b>maptype</b>.  The key part of each
  * entry is declared using the C declaration <b>keydecl</b>.  All functions
@@ -1113,6 +1270,9 @@ void
 strmap_free(strmap_t *map, void (*free_val)(void*))
 {
   strmap_entry_t **ent, **next, *this;
+  if (!map)
+    return;
+
   for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) {
     this = *ent;
     next = HT_NEXT_RMV(strmap_impl, &map->head, ent);
@@ -1134,6 +1294,8 @@ void
 digestmap_free(digestmap_t *map, void (*free_val)(void*))
 {
   digestmap_entry_t **ent, **next, *this;
+  if (!map)
+    return;
   for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) {
     this = *ent;
     next = HT_NEXT_RMV(digestmap_impl, &map->head, ent);
@@ -1220,6 +1382,7 @@ IMPLEMENT_ORDER_FUNC(find_nth_int, int)
 IMPLEMENT_ORDER_FUNC(find_nth_time, time_t)
 IMPLEMENT_ORDER_FUNC(find_nth_double, double)
 IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t)
+IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t)
 IMPLEMENT_ORDER_FUNC(find_nth_long, long)
 
 /** Return a newly allocated digestset_t, optimized to hold a total of
@@ -1248,6 +1411,8 @@ digestset_new(int max_elements)
 void
 digestset_free(digestset_t *set)
 {
+  if (!set)
+    return;
   bitarray_free(set->ba);
   tor_free(set);
 }