From: Jonathan McDowell <noodles@earth.li>
Date: Sun, 17 Oct 2004 22:15:37 +0000 (+0000)
Subject: Introduce sorted keyid array functions and use in DB4.
X-Git-Url: https://git.sommitrealweird.co.uk/onak.git/commitdiff_plain/be024aa68a513a2a85a7cddb28de4664b0b96144?ds=inline
Introduce sorted keyid array functions and use in DB4.
Adds functions to keep a sorted array of keyids (aiding searching speed).
Makes use of these in the DB4 backed for searching for keys based on uid
text.
---
diff --git a/Makefile.in b/Makefile.in
index d9459c8..dec603d 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -18,11 +18,11 @@ exec_prefix ?= @exec_prefix@
PROGS = add lookup gpgwww onak splitkeys onak-mail.pl stripkey
CORE_OBJS = armor.o charfuncs.o decodekey.o getcgi.o hash.o \
keyid.o keyindex.o ll.o mem.o onak-conf.o parsekey.o sha1.o md5.o \
- log.o photoid.o wordlist.o cleanup.o merge.o sendsync.o
+ log.o photoid.o wordlist.o cleanup.o merge.o sendsync.o keyarray.o
SRCS = armor.c parsekey.c merge.c keyid.c md5.c sha1.c main.c getcgi.c mem.c \
keyindex.c stats.c lookup.c add.c keydb_$(DBTYPE).c ll.c hash.c \
gpgwww.c onak-conf.c charfuncs.c sendsync.c log.c photoid.c \
- wordlist.c cleankey.c cleanup.c
+ wordlist.c cleankey.c cleanup.c keyarray.c
ifeq (x@KEYD@, xyes)
PROGS += keyd
diff --git a/keyarray.c b/keyarray.c
new file mode 100644
index 0000000..389eb0d
--- /dev/null
+++ b/keyarray.c
@@ -0,0 +1,105 @@
+/*
+ * keyarray.c - routines to maintain a sorted array of keyids.
+ *
+ * Jonathan McDowell <noodles@earth.li>
+ *
+ * Copyright 2004 Project Purple
+ */
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "keyarray.h"
+
+bool array_find(struct keyarray *array, uint64_t key)
+{
+ bool found;
+ int top = 0;
+ int bottom = 0;
+ int curpos;
+
+ found = false;
+ if (array->keys != NULL && array->count > 0) {
+ bottom = -1;
+ top = array->count - 1;
+ while ((top - bottom) > 1) {
+ curpos = (top + bottom) / 2;
+ if (key > array->keys[curpos]) {
+ bottom = curpos;
+ } else {
+ top = curpos;
+ }
+ }
+ found = (array->keys[top] == key);
+ }
+
+ return found;
+}
+
+bool array_add(struct keyarray *array, uint64_t key)
+{
+ bool found;
+ int top = 0;
+ int bottom = 0;
+ int curpos = 0;
+
+ found = false;
+ if (array->keys != NULL && array->count > 0) {
+ bottom = -1;
+ top = array->count - 1;
+ while ((top - bottom) > 1) {
+ curpos = (top + bottom) / 2;
+ if (key > array->keys[curpos]) {
+ bottom = curpos;
+ } else {
+ top = curpos;
+ }
+ }
+ found = (array->keys[top] == key);
+
+ if (key > array->keys[top]) {
+ curpos = top + 1;
+ } else {
+ curpos = top;
+ }
+ }
+
+ if (!found) {
+ if (array->size == 0) {
+ array->keys = malloc(16 * sizeof(uint64_t));
+ array->size = 16;
+ array->count = 1;
+ array->keys[0] = key;
+ } else {
+ if (array->count >= array->size) {
+ array->size *= 2;
+ array->keys = realloc(array->keys,
+ array->size * sizeof(uint64_t));
+ }
+ if (curpos < array->count) {
+ memmove(&array->keys[curpos+1],
+ &array->keys[curpos],
+ sizeof(uint64_t) *
+ (array->count - curpos));
+ }
+ array->keys[curpos] = key;
+ array->count++;
+ }
+ }
+
+ return !found;
+}
+
+void array_free(struct keyarray *array)
+{
+ if (array->keys) {
+ free(array->keys);
+ array->keys = NULL;
+ }
+ array->count = array->size = 0;
+
+ return;
+}
diff --git a/keyarray.h b/keyarray.h
new file mode 100644
index 0000000..a25ad71
--- /dev/null
+++ b/keyarray.h
@@ -0,0 +1,25 @@
+/*
+ * keyarray.h - routines to maintain a sorted array of keyids.
+ *
+ * Jonathan McDowell <noodles@earth.li>
+ *
+ * Copyright 2004 Project Purple
+ */
+
+#ifndef __KEYARRAY_H__
+#define __KEYARRAY_H__
+
+#include <stdbool.h>
+#include <stdint.h>
+
+struct keyarray {
+ uint64_t *keys;
+ size_t count;
+ size_t size;
+};
+
+bool array_find(struct keyarray *array, uint64_t key);
+void array_free(struct keyarray *array);
+bool array_add(struct keyarray *array, uint64_t key);
+
+#endif /* __KEYARRAY_H__ */
diff --git a/keydb_db4.c b/keydb_db4.c
index 3f51cc2..1daf00b 100644
--- a/keydb_db4.c
+++ b/keydb_db4.c
@@ -19,6 +19,7 @@
#include <db.h>
#include "charfuncs.h"
+#include "keyarray.h"
#include "keydb.h"
#include "keyid.h"
#include "decodekey.h"
@@ -418,21 +419,21 @@ int fetch_key_text(const char *search, struct openpgp_publickey **publickey)
char *searchtext = NULL;
struct ll *wordlist = NULL;
struct ll *curword = NULL;
- struct ll *keylist = NULL;
- struct ll *newkeylist = NULL;
+ struct keyarray keylist = { NULL, 0, 0 };
+ struct keyarray newkeylist = { NULL, 0, 0 };
numkeys = 0;
searchtext = strdup(search);
wordlist = makewordlist(wordlist, searchtext);
- starttrans();
+ for (curword = wordlist; curword != NULL; curword = curword->next) {
+ starttrans();
- ret = worddb->cursor(worddb,
- txn,
- &cursor,
- 0); /* flags */
+ ret = worddb->cursor(worddb,
+ txn,
+ &cursor,
+ 0); /* flags */
- for (curword = wordlist; curword != NULL; curword = curword->next) {
memset(&key, 0, sizeof(key));
memset(&data, 0, sizeof(data));
key.data = curword->object;
@@ -452,54 +453,44 @@ int fetch_key_text(const char *search, struct openpgp_publickey **publickey)
data.data)[i];
}
- if (keylist == NULL ||
- llfind(keylist, data.data,
- worddb_cmp) != NULL) {
- newkeylist = lladd(newkeylist, data.data);
- data.data = NULL;
- } else {
- free(data.data);
- data.data = NULL;
+ if (keylist.count == 0 ||
+ array_find(&keylist, keyid)) {
+ array_add(&newkeylist, keyid);
}
+
+ free(data.data);
+ data.data = NULL;
+
ret = cursor->c_get(cursor,
&key,
&data,
DB_NEXT);
}
- llfree(keylist, free);
+ array_free(&keylist);
keylist = newkeylist;
- newkeylist = NULL;
+ newkeylist.keys = NULL;
+ newkeylist.count = newkeylist.size = 0;
if (data.data != NULL) {
free(data.data);
data.data = NULL;
}
+ ret = cursor->c_close(cursor);
+ cursor = NULL;
+ endtrans();
}
llfree(wordlist, NULL);
wordlist = NULL;
- for (newkeylist = keylist;
- newkeylist != NULL && numkeys < config.maxkeys;
- newkeylist = newkeylist->next) {
-
- keyid = 0;
- for (i = 4; i < 12; i++) {
- keyid <<= 8;
- keyid += ((unsigned char *)
- newkeylist->object)[i];
- }
-
- numkeys += fetch_key(keyid,
- publickey,
- true);
+ starttrans();
+ for (i = 0; i < keylist.count; i++) {
+ numkeys += fetch_key(keylist.keys[i],
+ publickey,
+ true);
}
- llfree(keylist, free);
- keylist = NULL;
+ array_free(&keylist);
free(searchtext);
searchtext = NULL;
- ret = cursor->c_close(cursor);
- cursor = NULL;
-
endtrans();
return (numkeys);