r6958@Kushana: nickm | 2006-07-29 18:54:15 -0400

 Looks like we might need a priority queue.


svn:r6953

2 files changed, 90 insertions, 0 deletions

diff --git a/src/common/container.c b/src/common/container.c
index 7795e514be..d8ce9d654b 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -461,6 +461,87 @@ smartlist_sort_strings(smartlist_t *sl)
   smartlist_sort(sl, _compare_string_ptrs);
 }
 
+#define LEFT_CHILD(i)  ( ((i)+1)*2 - 1)
+#define RIGHT_CHILD(i) ( ((i)+1)*2 )
+#define PARENT(i)      ( ((i)+1)/2 - 1)
+
+static INLINE void
+smartlist_heapify(smartlist_t *sl,
+                  int (*compare)(const void *a, const void *b),
+                  int idx)
+{
+  while (1) {
+    int left_idx = LEFT_CHILD(idx);
+    int best_idx;
+
+    if (left_idx >= sl->num_used)
+      return;
+    if (compare(sl->list[idx],sl->list[left_idx]) < 0)
+      best_idx = idx;
+    else
+      best_idx = left_idx;
+    if (left_idx+1 < sl->num_used &&
+        compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
+      best_idx = left_idx + 1;
+
+    if (best_idx == idx) {
+      return;
+    } else {
+      void *tmp = sl->list[idx];
+      sl->list[idx] = sl->list[best_idx];
+      sl->list[best_idx] = tmp;
+
+      idx = best_idx;
+    }
+  }
+}
+
+void
+smartlist_pqueue_add(smartlist_t *sl,
+                     int (*compare)(const void *a, const void *b),
+                     void *item)
+{
+  int idx;
+  smartlist_add(sl,item);
+
+  for (idx = sl->num_used - 1; idx; ) {
+    int parent = PARENT(idx);
+    if (compare(sl->list[idx], sl->list[parent]) < 0) {
+      void *tmp = sl->list[parent];
+      sl->list[parent] = sl->list[idx];
+      sl->list[idx] = tmp;
+      idx = parent;
+    } else {
+      return;
+    }
+  }
+}
+
+void *
+smartlist_pqueue_pop(smartlist_t *sl,
+                     int (*compare)(const void *a, const void *b))
+{
+  void *top;
+  tor_assert(sl->num_used);
+
+  top = sl->list[0];
+  if (--sl->num_used) {
+    sl->list[0] = sl->list[sl->num_used];
+    smartlist_heapify(sl, compare, 0);
+  }
+  return top;
+}
+
+void
+smartlist_pqueue_assert_ok(smartlist_t *sl,
+                           int (*compare)(const void *a, const void *b))
+{
+  int i;
+  for (i = sl->num_used - 1; i > 0; --i) {
+    tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
+  }
+}
+
 /** Helper: compare two DIGEST_LEN digests. */
 static int
 _compare_digests(const void **_a, const void **_b)
diff --git a/src/common/container.h b/src/common/container.h
index 1031a6ef13..0b5d0618af 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -38,6 +38,7 @@ int smartlist_string_num_isin(const smartlist_t *sl, int num);
 int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2);
 void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2);
 void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2);
+
 /* smartlist_choose() is defined in crypto.[ch] */
 #ifdef DEBUG_SMARTLIST
 /** Return the number of items in sl.
@@ -76,6 +77,14 @@ void smartlist_sort_digests(smartlist_t *sl);
 void *smartlist_bsearch(smartlist_t *sl, const void *key,
                         int (*compare)(const void *key, const void **member));
 
+void smartlist_pqueue_add(smartlist_t *sl,
+                          int (*compare)(const void *a, const void *b),
+                          void *item);
+void *smartlist_pqueue_pop(smartlist_t *sl,
+                           int (*compare)(const void *a, const void *b));
+void smartlist_pqueue_assert_ok(smartlist_t *sl,
+                                int (*compare)(const void *a, const void *b));
+
 #define SPLIT_SKIP_SPACE   0x01
 #define SPLIT_IGNORE_BLANK 0x02
 int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,