damus

commit 6cd7b945ca7e91d328152ce4c4da376dbe807880
parent e5e6735129f050a3686ac9e3865b0669030f3915
Author: William Casarin <jb55@jb55.com>
Date:   Wed,  3 Jan 2024 17:02:42 -0800

nostrdb/filter: use binary search for large contact list filters

This is much more efficient than linear scans

Signed-off-by: William Casarin <jb55@jb55.com>

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

1 file changed, 8 insertions(+), 7 deletions(-)
diff --git a/nostrdb/src/nostrdb.c b/nostrdb/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: