nostrdb

commit 73e2306a16a1310d324242148b469fa00fb4ed1d
parent d05d8dffed9bdb6586bc3596047be7e7a4978d09
Author: William Casarin <jb55@jb55.com>
Date:   Wed,  3 Jan 2024 16:34:04 -0800

filter: sort filter elements

If they are sorted we can do binary search when matching filters like
how strfry does it.

Diffstat:
M
src/nostrdb.c
 | 
53
++++++++++++++++++++++++++++++++++++++++++++++++++++-
M
test.c
 | 
6
++++++

2 files changed, 58 insertions(+), 1 deletion(-)
diff --git a/src/nostrdb.c b/src/nostrdb.c
@@ -804,6 +804,31 @@ static int ndb_generic_filter_matches(struct ndb_filter_elements *els,
 	return 0;
 }
 
+static int compare_ids(const void *pa, const void *pb)
+{
+	const unsigned char *a = *(const unsigned char **)pa;
+	const unsigned char *b = *(const unsigned char **)pb;
+
+	return memcmp(a, b, 32);
+}
+
+static int compare_kinds(const void *pa, const void *pb)
+{
+
+	// NOTE: this should match type in `union ndb_filter_element`
+	uint64_t a = *(uint64_t *)pa;
+	uint64_t b = *(uint64_t *)pb;
+
+	if (a < b) {
+		return -1;
+	} else if (a > b) {
+		return 1;
+	} else {
+		return 0;
+	}
+}
+
+
 // returns 1 if a filter matches a note
 int ndb_filter_matches(struct ndb_filter *filter, struct ndb_note *note)
 {
@@ -860,8 +885,34 @@ cont:
 
 void ndb_filter_end_field(struct ndb_filter *filter)
 {
-	filter->elements[filter->num_elements++] = filter->current;
+	struct ndb_filter_elements *cur;
+
+	cur = filter->current;
+	filter->elements[filter->num_elements++] = cur;
+
+	// sort elements for binary search
+	switch (cur->field.type) {
+	case NDB_FILTER_IDS:
+	case NDB_FILTER_AUTHORS:
+		qsort(&cur->elements[0], cur->count,
+		      sizeof(cur->elements[0].id), compare_ids);
+		break;
+	case NDB_FILTER_KINDS:
+		qsort(&cur->elements[0], cur->count,
+		      sizeof(cur->elements[0].integer), compare_kinds);
+		break;
+	case NDB_FILTER_GENERIC:
+		// TODO: generic tag search sorting
+		break;
+	case NDB_FILTER_SINCE:
+	case NDB_FILTER_UNTIL:
+	case NDB_FILTER_LIMIT:
+		// don't need to sort these
+		break;
+	}
+
 	filter->current = NULL;
+
 }
 
 void ndb_filter_group_init(struct ndb_filter_group *group)
diff --git a/test.c b/test.c
@@ -47,6 +47,7 @@ static void print_search(struct ndb_txn *txn, struct ndb_search *search)
 static void test_filters()
 {
 	struct ndb_filter filter, *f;
+	struct ndb_filter_elements *current;
 	struct ndb_note *note;
 	unsigned char buffer[4096];
 
@@ -60,6 +61,7 @@ static void test_filters()
 	assert(ndb_filter_add_int_element(f, 1337));
 	assert(ndb_filter_add_int_element(f, 2));
 
+	current = f->current;
 	assert(f->current->count == 2);
 	assert(f->current->field.type == NDB_FILTER_KINDS);
 
@@ -68,6 +70,10 @@ static void test_filters()
 	assert(ndb_filter_start_field(f, NDB_FILTER_GENERIC) == 0);
 	ndb_filter_end_field(f);
 
+	// should be sorted after end
+	assert(current->elements[0].integer == 2);
+	assert(current->elements[1].integer == 1337);
+
 	// try matching the filter
 	assert(ndb_filter_matches(f, note));