partial sorted-set implementation

6 files changed, 201 insertions, 22 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 610d2578..1bb98e2f 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -26,7 +26,6 @@ if USE_DM_GETOPT
 DM_GETOPT = dm_getopt.c
 endif
 
-
 sbin_PROGRAMS = dbmail-deliver \
 	dbmail-pop3d \
 	dbmail-imapd \
@@ -53,7 +52,8 @@ COMMON = dbmail-user.c \
 	dm_digest.c \
 	dm_match.c \
 	dm_iconv.c \
-	dm_dsn.c $(DM_GETOPT)
+	dm_dsn.c \
+	dm_sset.c $(DM_GETOPT)
 	
 
 SERVER = server.c \
diff --git a/src/dbmail.h.in b/src/dbmail.h.in
index 9b65a930..090d2b9d 100644
--- a/src/dbmail.h.in
+++ b/src/dbmail.h.in
@@ -134,6 +134,7 @@
 #include "dm_iconv.h"
 #include "dm_getopt.h"
 #include "dm_match.h"
+#include "dm_sset.h"
 
 #ifdef SIEVE
 #include <sieve2.h>
diff --git a/src/dm_sset.c b/src/dm_sset.c
index 7fd256aa..dee185e3 100644
--- a/src/dm_sset.c
+++ b/src/dm_sset.c
@@ -18,78 +18,95 @@
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
 
-#include "dbmail.h"
 #include "dm_sset.h"
+#include <stdlib.h>
+#include <search.h>
+#include <assert.h>
 
 #define THIS_MODULE "SSET"
 
 /*
- * implements the Sorted Set interface
+ * implements the Sorted Set interface using standard posix binary trees
  */
 
-#define T SSet_T
+#define T Sset_T
 
 struct T {
-	GTree *items;
+	void *root;
 	int (*cmp)(const void *, const void *);
-	int (*hash)(const void *);
+	int len;
 };
 
 
-T Sset_new(int (*cmp)(const void *a, const void *b), int (*hash)(const void *c))
+T Sset_new(int (*cmp)(const void *a, const void *b))
 {
-
 	T S;
-	S = g_malloc0(sizeof(*S));
-	S->items = g_tree_new_full((GCompareDataFunc)(cmp), NULL, (GDestroyNotify)g_free, (GDestroyNotify)g_free);
+	S = calloc(1, sizeof(*S));
+	S->root = NULL;
 	S->cmp = cmp;
-	S->hash = hash;
+	return S;
 }
 
 int Sset_has(T S, const void *a)
 {
-	return g_tree_lookup(S->items, a)?1:0;
+	if (!S->root) return 0;
+	return tfind(a, &(S->root), S->cmp)?1:0;
 }
 
 
 void Sset_add(T S, const void *a)
 {
-
+	if (! Sset_has(S, a)) {
+		void * t = NULL;
+		t = tsearch(a, &(S->root), S->cmp);
+		assert(t);
+		S->len++;
+	}
 }
 
 int Sset_len(T S)
 {
-
+	return S->len;
 }
 
 void * Sset_del(T S, const void * a)
 {
+	void * t = NULL;
+	if ((t = tdelete(a, &(S->root), S->cmp)) != NULL)
+		S->len--;
+	return t;
+}
 
+void Sset_map(T S, void (*func)(const void *))
+{
+	return;
 }
 
 void Sset_free(T *S)
 {
-
+	T s = *S;
+	if (s) free(s);
+	s = NULL;
 }
 
 T Sset_or(T a, T b) // a + b
 {
-
+	return a;
 }
 
 T Sset_and(T a, T b) // a * b
 {
-
+	return a;
 }
 
 T Sset_not(T a, T b) // a - b
 {
-
+	return a;
 }
 
-T Sset_xor(T a, T b); // a / b
+T Sset_xor(T a, T b) // a / b
 {
-
+	return a;
 }
 
 
diff --git a/src/dm_sset.h b/src/dm_sset.h
index d3b50cfe..86a156c8 100644
--- a/src/dm_sset.h
+++ b/src/dm_sset.h
@@ -32,11 +32,12 @@
 
 typedef struct T *T;
 
-extern T               Sset_new(int (*cmp)(const void *, const void *), int (*hash)(const void *));
+extern T               Sset_new(int (*cmp)(const void *, const void *));
 extern int             Sset_has(T, const void *); 
 extern void            Sset_add(T, const void *);
 extern int             Sset_len(T);
 extern void *          Sset_del(T, const void *);
+extern void            Sset_map(T, void (*func)(const void *));
 extern void            Sset_free(T *);
 
 extern T               Sset_or(T, T); // a + b
diff --git a/test/Makefile.am b/test/Makefile.am
index a11429d1..5e0a984c 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -29,6 +29,7 @@ TESTS=check_dbmail_common \
 	check_dbmail_util \
 	check_dbmail_dsn \
 	check_dbmail_capa \
+	check_dbmail_sset \
 	check_dbmail_db
 
 IMAPD = $(top_srcdir)/src/dm_quota.c \
@@ -104,4 +105,7 @@ check_dbmail_capa_SOURCES=check_dbmail_capa.c
 check_dbmail_capa_LDADD=$(CHECK_LDADD)
 check_dbmail_capa_INCLUDES=@CHECK_CFLAGS@
 
+check_dbmail_sset_SOURCES=check_dbmail_sset.c $(top_srcdir)/src/dm_sset.c
+check_dbmail_sset_LDADD=$(CHECK_LDADD)
+check_dbmail_sset_INCLUDES=@CHECK_CFLAGS@
 endif
diff --git a/test/check_dbmail_sset.c b/test/check_dbmail_sset.c
new file mode 100644
index 00000000..db93f00e
--- /dev/null
+++ b/test/check_dbmail_sset.c
@@ -0,0 +1,156 @@
+/*
+ *   Copyright (c) 2005-2006 NFG Net Facilities Group BV support@nfg.nl
+ *
+ *   This program is free software; you can redistribute it and/or
+ *   modify it under the terms of the GNU General Public License
+ *   as published by the Free Software Foundation; either
+ *   version 2 of the License, or (at your option) any later
+ *   version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ *
+ *   
+ *
+ *
+ *  
+ *
+ *   Basic unit-test framework for dbmail (www.dbmail.org)
+ *
+ *   See http://check.sf.net for details and docs.
+ *
+ *
+ *   Run 'make check' to see some action.
+ *
+ */ 
+
+#include <check.h>
+#include "check_dbmail.h"
+
+#include <sys/times.h>
+#include <time.h>
+#include <stdio.h>
+
+extern char *configFile;
+
+/*
+ *
+ * the test fixtures
+ *
+ */
+static clock_t st_time;
+static clock_t en_time;
+static struct tms st_cpu;
+static struct tms en_cpu;
+
+static void start_clock(void)
+{
+	st_time = times(&st_cpu);
+}
+
+static void end_clock(char *msg)
+{
+	en_time = times(&en_cpu);
+	printf("%sReal Time: %LF, User Time %LF, System Time %LF\n",
+			msg,
+			(long double)(en_time - st_time),
+			(long double)(en_cpu.tms_utime - st_cpu.tms_utime),
+			(long double)(en_cpu.tms_stime - st_cpu.tms_stime));
+}
+
+Sset_T V;
+
+
+struct item {
+	int key;
+	long long int value;
+};
+
+static int compare(const void *a, const void *b)
+{
+	struct item *x, *y;
+	x = (struct item *)a;
+	y = (struct item *)b;
+
+	if (x->key>y->key)
+		return 1;
+	if (x->key==y->key)
+		return 0;
+	return -1;
+}
+
+void setup(void)
+{
+	configure_debug(255,0);
+	config_read(configFile);
+	V = Sset_new(compare);
+}
+
+void teardown(void)
+{
+	Sset_free(&V);
+}
+
+START_TEST(test_sset_add)
+{
+	int i, n = 1000000;
+	struct item p, *t, *k;
+       
+	start_clock();
+	k = malloc(sizeof(struct item) * n);
+	end_clock("malloc: ");
+
+	t = k;
+	start_clock();
+	for (i = 0; i<n; i++, t++) {
+		t->key = i;
+	        t->value = rand();
+		Sset_add(V, (void *)t);
+	}
+	end_clock("Sset_add: ");
+
+	memset(&p, 0, sizeof(struct item));
+	start_clock();
+	for (i = 0; i<n; i++, t++) {
+		p.key = i;
+		Sset_del(V, (void *)&t);
+	}
+	end_clock("Sset_del: ");
+
+
+	free(k);
+}
+END_TEST
+
+Suite *dbmail_sset_suite(void)
+{
+	Suite *s = suite_create("Dbmail Sset");
+	TCase *tc_sset = tcase_create("Sset");
+	
+	suite_add_tcase(s, tc_sset);
+	
+	tcase_add_checked_fixture(tc_sset, setup, teardown);
+	tcase_add_test(tc_sset, test_sset_add);
+
+	return s;
+}
+
+int main(void)
+{
+	int nf;
+	Suite *s = dbmail_sset_suite();
+	SRunner *sr = srunner_create(s);
+	srunner_run_all(sr, CK_NORMAL);
+	nf = srunner_ntests_failed(sr);
+	srunner_free(sr);
+	return (nf == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
+	
+