Add sorting/searching to smartlist

svn:r4977

3 files changed, 65 insertions, 0 deletions

diff --git a/src/common/container.c b/src/common/container.c
index ac10d60f0b..74b2dd9072 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -387,6 +387,37 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join,
   return r;
 }
 
+/** Sort the members of <b>sl</b> into an order defined by
+ * the ordering function <b>compare</b>, which returns less then 0 if a
+ * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
+ */
+void
+smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
+{
+  if (!sl->num_used)
+    return;
+  qsort(sl->list, sl->num_used, sizeof(void*),
+        (int (*)(const void *,const void*))compare);
+}
+
+/** 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
+ * less than member, and greater than 0 if key is greater then member.
+ */
+void *
+smartlist_bsearch(smartlist_t *sl, const void *key,
+                  int (*compare)(const void *key, const void **member))
+{
+  void ** r;
+  if (!sl->num_used)
+    return NULL;
+
+  r = bsearch(key, sl->list, sl->num_used, sizeof(void*),
+              (int (*)(const void *, const void *))compare);
+  return r ? *r : NULL;
+}
+
 /* Splay-tree implementation of string-to-void* map
  */
 typedef struct strmap_entry_t {
diff --git a/src/common/container.h b/src/common/container.h
index 260177767a..98b8ab1a8e 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -50,6 +50,10 @@ int smartlist_len(const smartlist_t *sl);
 void smartlist_del(smartlist_t *sl, int idx);
 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_bsearch(smartlist_t *sl, const void *key,
+                        int (*compare)(const void *key, const void **member));
 
 #define SPLIT_SKIP_SPACE   0x01
 #define SPLIT_IGNORE_BLANK 0x02
diff --git a/src/or/test.c b/src/or/test.c
index e10a149263..4b1453660f 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -604,6 +604,21 @@ test_crypto_s2k(void)
   test_memeq(buf, buf2, 29);
 }
 
+static int
+_compare_strs(const void **a, const void **b)
+{
+  const char *s1 = *a, *s2 = *b;
+  return strcmp(s1, s2);
+}
+
+static int
+_compare_without_first_ch(const void *a, const void **b)
+{
+  const char *s1 = a, *s2 = *b;
+  printf("%s v %s\n",s1, s2);
+  return strcasecmp(s1+1, s2);
+}
+
 static void
 test_util(void)
 {
@@ -776,6 +791,21 @@ test_util(void)
   test_eq(2, smartlist_len(sl));
   test_streq("efgh", smartlist_get(sl, 1));
 
+  SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
+  smartlist_clear(sl);
+
+  /* Test smartlist sorting. */
+  smartlist_split_string(sl, "the,onion,router,by,arma,and,nickm", ",", 0, 0);
+  test_eq(7, smartlist_len(sl));
+  smartlist_sort(sl, _compare_strs);
+  cp = smartlist_join_strings(sl, ",", 0, NULL);
+  test_streq(cp,"and,arma,by,nickm,onion,router,the");
+  tor_free(cp);
+
+  test_streq("nickm", smartlist_bsearch(sl, "zNicKM", _compare_without_first_ch));
+  test_streq("and", smartlist_bsearch(sl, " AND", _compare_without_first_ch));
+  test_eq_ptr(NULL, smartlist_bsearch(sl, " ANz", _compare_without_first_ch));
+
   /* Test tor_strstrip() */
   strcpy(buf, "Testing 1 2 3");
   test_eq(0, tor_strstrip(buf, ",!"));