r8819@Kushana: nickm | 2006-09-15 00:27:45 -0400

 Implement a smartlist_uniq() that will with luck not end the world.


svn:r8396

2 files changed, 44 insertions, 0 deletions

diff --git a/src/common/container.c b/src/common/container.c
index c5529058f3..64ad420633 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -429,6 +429,29 @@ smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
         (int (*)(const void *,const void*))compare);
 }
 
+/** 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, frees them with tor_free(), which
+ * may not be what you want..  Preserves order.
+ */
+void
+smartlist_uniq(smartlist_t *sl,
+               int (*compare)(const void **a, const void **b),
+               void (*free_fn)(void *a))
+{
+  int i;
+  for (i=1; i < sl->num_used; ++i) {
+    if (compare((const void **)&(sl->list[i-1]),
+                (const void **)&(sl->list[i])) == 0) {
+      if (free_fn)
+        free_fn(sl->list[i]);
+      else
+        tor_free(sl->list[i]);
+      smartlist_del_keeporder(sl, i--);
+    }
+  }
+}
+
 /** Assuming the members of <b>sl</b> are in order, return a pointer to the
  * member which matches <b>key</b>.  Ordering and matching are defined by a
  * <b>compare</b> function, which returns 0 on a match; less than 0 if key is
@@ -462,6 +485,14 @@ smartlist_sort_strings(smartlist_t *sl)
   smartlist_sort(sl, _compare_string_ptrs);
 }
 
+/** Remove duplicate strings from a sorted list, and free them with tor_free().
+ */
+void
+smartlist_uniq_strings(smartlist_t *sl)
+{
+  smartlist_uniq(sl, _compare_string_ptrs, NULL);
+}
+
 #define LEFT_CHILD(i)  ( ((i)+1)*2 - 1)
 #define RIGHT_CHILD(i) ( ((i)+1)*2 )
 #define PARENT(i)      ( ((i)+1)/2 - 1)
@@ -557,6 +588,14 @@ smartlist_sort_digests(smartlist_t *sl)
   smartlist_sort(sl, _compare_digests);
 }
 
+/** Remove duplicate digests from a sorted list, and free them with tor_free().
+ */
+void
+smartlist_uniq_digests(smartlist_t *sl)
+{
+  smartlist_uniq(sl, _compare_digests, NULL);
+}
+
 #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
   typedef struct prefix ## entry_t {                      \
     HT_ENTRY(prefix ## entry_t) node;                     \
diff --git a/src/common/container.h b/src/common/container.h
index a4cac610d7..5f0417cf4d 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -74,8 +74,13 @@ void smartlist_del_keeporder(smartlist_t *sl, int idx);
 void smartlist_insert(smartlist_t *sl, int idx, void *val);
 void smartlist_sort(smartlist_t *sl,
                     int (*compare)(const void **a, const void **b));
+void smartlist_uniq(smartlist_t *sl,
+                    int (*compare)(const void **a, const void **b),
+                    void (*free_fn)(void *elt));
 void smartlist_sort_strings(smartlist_t *sl);
 void smartlist_sort_digests(smartlist_t *sl);
+void smartlist_uniq_strings(smartlist_t *sl);
+void smartlist_uniq_digests(smartlist_t *sl);
 void *smartlist_bsearch(smartlist_t *sl, const void *key,
                         int (*compare)(const void *key, const void **member))
  ATTR_PURE;