nostrdb

commit e749479ef157fb5b8766959f5870741772d69fbc
parent 73e2306a16a1310d324242148b469fa00fb4ed1d
Author: William Casarin <jb55@jb55.com>
Date:   Wed,  3 Jan 2024 17:02:42 -0800

filter: use binary search for large contact list filters

This is much more efficient than linear scans

Diffstat:
M
src/nostrdb.c
 | 
15
++++++++-------

1 file changed, 8 insertions(+), 7 deletions(-)
diff --git a/src/nostrdb.c b/src/nostrdb.c
@@ -845,17 +845,18 @@ int ndb_filter_matches(struct ndb_filter *filter, struct ndb_note *note)
 					goto cont;
 			}
 			break;
-		// TODO: add filter hashtable for large id lists
 		case NDB_FILTER_IDS:
-			for (j = 0; j < els->count; j++) {
-				if (!memcmp(els->elements[j].id, note->id, 32))
-					goto cont;
+			unsigned char *id = note->id;
+			if (bsearch(&id, &els->elements[0], els->count,
+				    sizeof(els->elements[0].id), compare_ids)) {
+				goto cont;
 			}
 			break;
 		case NDB_FILTER_AUTHORS:
-			for (j = 0; j < els->count; j++) {
-				if (!memcmp(els->elements[j].id, note->pubkey, 32))
-					goto cont;
+			unsigned char *pubkey = note->pubkey;
+			if (bsearch(&pubkey, &els->elements[0], els->count,
+				    sizeof(els->elements[0].id), compare_ids)) {
+				goto cont;
 			}
 			break;
 		case NDB_FILTER_GENERIC: