From be024aa68a513a2a85a7cddb28de4664b0b96144 Mon Sep 17 00:00:00 2001 From: Jonathan McDowell Date: Sun, 17 Oct 2004 22:15:37 +0000 Subject: [PATCH 1/1] 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. --- Makefile.in | 4 +- keyarray.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++ keyarray.h | 25 +++++++++++++ keydb_db4.c | 65 ++++++++++++++------------------ 4 files changed, 160 insertions(+), 39 deletions(-) create mode 100644 keyarray.c create mode 100644 keyarray.h 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 + * + * Copyright 2004 Project Purple + */ + +#include +#include +#include +#include +#include + +#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 + * + * Copyright 2004 Project Purple + */ + +#ifndef __KEYARRAY_H__ +#define __KEYARRAY_H__ + +#include +#include + +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 #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); -- 2.39.5