Use heap-based priority queue to schedule handshakes instead of a linked list

4 files changed, 13 insertions, 26 deletions

diff --git a/src/fastd.h b/src/fastd.h
index 88bd9a2..d15033c 100644
--- a/src/fastd.h
+++ b/src/fastd.h
@@ -36,7 +36,6 @@
 
 #pragma once
 
-#include "dlist.h"
 #include "buffer.h"
 #include "log.h"
 #include "poll.h"
@@ -313,7 +312,7 @@ struct fastd_context {
 	size_t peer_addr_ht_used;		/**< The current number of entries in the peer address hashtable */
 	VECTOR(fastd_peer_t *) *peer_addr_ht;	/**< An array of hash buckets for the peer hash table */
 
-	fastd_dlist_head_t handshake_queue;	/**< A doubly linked list of the peers currently queued for handshakes (ordered by the time of the next handshake) */
+	fastd_pqueue_t *handshake_queue;	/**< A priority queue of the peers currently queued for handshakes (ordered by the time of the next handshake) */
 	fastd_timeout_t next_maintenance;	/**< The time of the next maintenance call */
 
 	VECTOR(pid_t) async_pids;		/**< PIDs of asynchronously executed commands which still have to be reaped */
diff --git a/src/peer.c b/src/peer.c
index 67ce50d..87df22d 100644
--- a/src/peer.c
+++ b/src/peer.c
@@ -265,17 +265,8 @@ void fastd_peer_reset_socket(fastd_peer_t *peer) {
 void fastd_peer_schedule_handshake(fastd_peer_t *peer, int delay) {
 	fastd_peer_unschedule_handshake(peer);
 
-	peer->next_handshake = ctx.now + delay;
-
-	fastd_dlist_head_t *list;
-	for (list = &ctx.handshake_queue; list->next; list = list->next) {
-		fastd_peer_t *entry = container_of(list->next, fastd_peer_t, handshake_entry);
-
-		if (entry->next_handshake > peer->next_handshake)
-			break;
-	}
-
-	fastd_dlist_insert(list, &peer->handshake_entry);
+	peer->handshake_entry.value = ctx.now + delay;
+	fastd_pqueue_insert(&ctx.handshake_queue, &peer->handshake_entry);
 }
 
 /** Checks if the peer group \e group1 lies in \e group2 */
@@ -829,13 +820,13 @@ static void send_handshake(fastd_peer_t *peer, fastd_remote_t *next_remote) {
 
 /** Sends a handshake to one peer, if a scheduled handshake is due */
 void fastd_peer_handle_handshake_queue(void) {
-	if (!ctx.handshake_queue.next)
+	if (!ctx.handshake_queue)
 		return;
-
-	fastd_peer_t *peer = container_of(ctx.handshake_queue.next, fastd_peer_t, handshake_entry);
-	if (!fastd_timed_out(peer->next_handshake))
+	if (!fastd_timed_out(ctx.handshake_queue->value))
 		return;
 
+	fastd_peer_t *peer = container_of(ctx.handshake_queue, fastd_peer_t, handshake_entry);
+
 	fastd_peer_schedule_handshake_default(peer);
 
 	if (!fastd_peer_may_connect(peer)) {
diff --git a/src/peer.h b/src/peer.h
index 298adf4..5f5da54 100644
--- a/src/peer.h
+++ b/src/peer.h
@@ -33,6 +33,7 @@
 #pragma once
 
 #include "fastd.h"
+#include "pqueue.h"
 
 
 /** The state of a peer */
@@ -90,7 +91,7 @@ struct fastd_peer {
 
 	fastd_peer_state_t state;			/**< The peer's state */
 
-	fastd_timeout_t next_handshake;			/**< The time of the next handshake */
+	fastd_pqueue_t handshake_entry;			/**< Entry in the handshake queue */
 	fastd_timeout_t last_handshake_timeout;		/**< No handshakes are sent to the peer until this timeout has occured to avoid flooding the peer */
 	fastd_timeout_t last_handshake_response_timeout; /**< All handshakes from last_handshake_address will be ignored until this timeout has occured */
 	fastd_timeout_t establish_handshake_timeout;	/**< A timeout during which all handshakes for this peer will be ignored after a new connection has been established */
@@ -101,8 +102,6 @@ struct fastd_peer {
 
 	fastd_stats_t stats;				/**< Traffic statistics */
 
-	fastd_dlist_head_t handshake_entry;		/**< Entry in the handshake queue */
-
 #ifdef WITH_DYNAMIC_PEERS
 	fastd_timeout_t verify_timeout;			/**< Specifies the minimum time after which on-verify may be run again */
 	fastd_timeout_t verify_valid_timeout;		/**< Specifies how long a peer stays valid after a successful on-verify run */
@@ -176,7 +175,7 @@ static inline void fastd_peer_schedule_handshake_default(fastd_peer_t *peer) {
 
 /** Cancels a scheduled handshake */
 static inline void fastd_peer_unschedule_handshake(fastd_peer_t *peer) {
-	fastd_dlist_remove(&peer->handshake_entry);
+	fastd_pqueue_remove(&peer->handshake_entry);
 }
 
 #ifdef WITH_DYNAMIC_PEERS
@@ -193,7 +192,7 @@ static inline void fastd_peer_set_verified(fastd_peer_t *peer, bool ok) {
 
 /** Checks if there's a handshake queued for the peer */
 static inline bool fastd_peer_handshake_scheduled(fastd_peer_t *peer) {
-	return fastd_dlist_linked(&peer->handshake_entry);
+	return fastd_pqueue_linked(&peer->handshake_entry);
 }
 
 /** Checks if a peer is floating (is has at least one floating remote or no remotes at all) */
diff --git a/src/poll.c b/src/poll.c
index 2ae6867..0c4dfa9 100644
--- a/src/poll.c
+++ b/src/poll.c
@@ -53,12 +53,10 @@
 
 /** Returns the time to the next handshake or -1 */
 static inline int handshake_timeout(void) {
-	if (!ctx.handshake_queue.next)
+	if (!ctx.handshake_queue)
 		return -1;
 
-	fastd_peer_t *peer = container_of(ctx.handshake_queue.next, fastd_peer_t, handshake_entry);
-
-	int diff_msec = peer->next_handshake - ctx.now;
+	int diff_msec = ctx.handshake_queue->value - ctx.now;
 	if (diff_msec < 0)
 		return 0;
 	else