Details of the database engine

This appendix describes in pseudocode how the basic operations (add, get, index, delete, since) of the key server are implemented. The code itself is more complex, since it has to deal with error checking and the general overhead of C memory management.

add(keyring) ::=
	for key in keyring
		dbkey = read-entry(key-db, keyid(key))
		if found then (key, newkeys) = merge-keys(dbkey, key)
		write-entry(key-db, keyid(key), key)
		for word in userids(key)
			keyid-list = read-entry(word-db, word)
			add-to-list(keyid-list, keyid(key))
			write-entry(word-db, word, keyid-list)
		end
		write-entry(time-db, now, keyid(key))
		allnewkeys = allnewkeys + newkeys
	end
	return(allnewkeys)

delete(keyid) ::=
	keyid-list = search(userid)
	for keyid in keyid-list
		key = read-entry(key-db, keyid(key))
		for word in userids(key)
			keyid-list = read-entry(word-db, word)
			delete-from-list(keyid-list, keyid(key))
			write-entry(word-db, word, keyid-list)
		end
		delete-entry(key-db, keyid(key))
	end

get(userid) ::=
	keyid-list = search(userid)
	for keyid in keyid-list
		keyring = keyring + read-entry(key-db, keyid)
	end
	return(ascii-armor(keyring))

index(userid,verbose,fingerprint) ::=
	keyid-list = search(userid)
	for keyid in keyid-list
		keyring = keyring + read-entry(key-db, keyid)
	end
	return(index(keyring,verbose,fingerprint))

since(time) ::=
	keyid-list = read-range(time-db, from time to end)
	for keyid in keyid-list
		keyring = keyring + read-entry(key-db, keyid)
	end
	return(ascii-armor(keyring))

The above pseudocode uses a few functions whose implementation is not trivial. These are defined here.

merge-keys(key1, key2) ::=
	output-key.modulus = key2.modulus
	output-key.exponent = key2.exponent
	if key1.primary-userid.name eq key2.primary-userid.name then
		output-key.primary-userid.name = key2.primary-userid.name
		output-key.primary-userid.sigs =
			merge-sigs(key1.primary-userid.sigs,
			           key2.primary-userid.sigs)
		output-key.secondary-userid-list = 
			merge-userids(key1.secondary-userid-list,
			              key2.secondary-userid-list)
	else
		for userid in key1.secondary-userid-list
			if userid.name eq key2.primary-userid.name then
				temp-userid = userid
			fi
		end
		delete-from-list(key1.secondary-userid-list, temp-userid)
		output-key.primary-userid.name = key2.primary-userid.name
		output-key.primary-userid.sigs =
			merge-sigs(temp-userid.sigs,
			           key2.primary-userid.sigs)
		output-key.secondary-userid-list = 
			merge-userids(key1.primary-userid,
			              key1.secondary-userid-list,
			              key2.secondary-userid-list)
	fi
	return(output-key)

merge-userids(userid-list-1, userid-list-2) ::=
	for (userid-1, userid2) in (userid-list-1, userid-list-2)
	                        such that userid-1.name eq userid-2.name
		output-userid.name = userid-2.name
		output-userid.sigs = merge-sigs(userid-1.sigs, userid-2.sigs)
		add-to-list(output-list, output-userid)
	end
	for userid-1 in userid-list-1
	             such that userid-1.name not in userid-list-2
		add-to-list(output-list, userid-1)
	end
	for userid-2 in userid-list-2
	             such that userid-2.name not in userid-list-1
		add-to-list(output-list, userid-2)
	end
	return(output-list)

merge-sigs(sigs-list-1, sigs-list-2) ::=
	return(add-to-list(sigs-list-1, sigs-list-2))

search(userid) ::=
	if (is-keyid-format(userid)) return(userid)
	for word in userid
		keyid-list = read-entry(word-db, word)
		if (output-list is empty)
			output-list = keyid-list
		else
			output-list = intersect(keyid-list, output-list)
		fi
	end
	return(output-list)