Index: sys/netinet/libalias/alias_db.c
===================================================================
--- sys/netinet/libalias/alias_db.c
+++ sys/netinet/libalias/alias_db.c
@@ -323,9 +323,14 @@
 	int		sockfd;		/* socket descriptor */
 #endif
 	/* Linked list of pointers for input and output lookup tables  */
-	LIST_ENTRY    (alias_link) list_out;
-	LIST_ENTRY    (alias_link) list_in;
-	TAILQ_ENTRY   (alias_link) list_expire;
+	union {
+		struct {
+			SPLAY_ENTRY(alias_link) splay_out;
+			LIST_ENTRY (alias_link) list_in;
+		};
+		LIST_ENTRY(alias_link) list_pptp;
+	};
+	TAILQ_ENTRY(alias_link) list_expire;
 	/* Auxiliary data */
 	union {
 		char           *frag_ptr;
@@ -380,8 +385,6 @@
 /* Local prototypes */
 static struct group_in *
 StartPointIn(struct libalias *, struct in_addr, u_short, int, int);
-static u_int
-StartPointOut(struct in_addr, struct in_addr, u_short, u_short, int);
 static int	SeqDiff(u_long, u_long);
 
 #ifndef NO_FW_PUNCH
@@ -399,6 +402,24 @@
 
 void		SctpShowAliasStats(struct libalias *la);
 
+
+/* Splay handling */
+static inline int
+cmp_out(struct alias_link *a, struct alias_link *b) {
+	int i = a->src_port - b->src_port;
+	if (i != 0) return (i);
+	i = a->src_addr.s_addr - b->src_addr.s_addr;
+	if (i != 0) return (i);
+	i = a->dst_addr.s_addr - b->dst_addr.s_addr;
+	if (i != 0) return (i);
+	i = a->dst_port - b->dst_port;
+	if (i != 0) return (i);
+	i = a->link_type - b->link_type;
+	return (i);
+}
+SPLAY_PROTOTYPE(splay_out, alias_link, splay_out, cmp_out);
+SPLAY_GENERATE(splay_out, alias_link, splay_out, cmp_out);
+
 #define INGUARD						\
    if (lnk->alias_port != alias_port ||			\
        lnk->link_type != link_type ||			\
@@ -440,21 +461,6 @@
 }
 #undef INGUARD
 
-static u_int
-StartPointOut(struct in_addr src_addr, struct in_addr dst_addr,
-    u_short src_port, u_short dst_port, int link_type)
-{
-	u_int n;
-
-	n = src_addr.s_addr;
-	n += dst_addr.s_addr;
-	n += src_port;
-	n += dst_port;
-	n += link_type;
-
-	return (n % LINK_TABLE_OUT_SIZE);
-}
-
 static int
 SeqDiff(u_long x, u_long y)
 {
@@ -891,23 +897,28 @@
 	ClearFWHole(lnk);
 #endif
 
-	/* Free memory allocated for LSNAT server pool */
-	if (lnk->server != NULL) {
-		struct server *head, *curr, *next;
-
-		head = curr = lnk->server;
-		do {
-			next = curr->next;
-			free(curr);
-		} while ((curr = next) != head);
-	} else {
-		/* Adjust output table pointers */
-		LIST_REMOVE(lnk, list_out);
-	}
+	switch (lnk->link_type) {
+	case LINK_PPTP:
+		LIST_REMOVE(lnk, list_pptp);
+		break;
+	default:
+		/* Free memory allocated for LSNAT server pool */
+		if (lnk->server != NULL) {
+			struct server *head, *curr, *next;
+
+			head = curr = lnk->server;
+			do {
+				next = curr->next;
+				free(curr);
+			} while ((curr = next) != head);
+		} else {
+			/* Adjust output table pointers */
+			SPLAY_REMOVE(splay_out, &la->splayTableOut, lnk);
+		}
 
-	if (lnk->link_type != LINK_PPTP) {
 		/* Adjust input table pointers */
 		LIST_REMOVE(lnk, list_in);
+		break;
 	}
 
 	/* remove from housekeeping */
@@ -965,7 +976,6 @@
     struct in_addr alias_addr, u_short src_port, u_short dst_port,
     int alias_port_param, int link_type)
 {
-	u_int start_point;
 	struct alias_link *lnk;
 	struct group_in *grp_in;
 
@@ -1083,7 +1093,7 @@
 
 	switch (link_type) {
 	case LINK_PPTP:
-		LIST_INSERT_HEAD(&la->pptpTable, lnk, list_out);
+		LIST_INSERT_HEAD(&la->pptpTable, lnk, list_pptp);
 		break;
 	default:
 		grp_in = StartPointIn(la, alias_addr, lnk->alias_port, link_type, 1);
@@ -1093,9 +1103,7 @@
 		}
 
 		/* Set up pointers for output lookup table */
-		start_point = StartPointOut(src_addr, dst_addr,
-		    src_port, dst_port, link_type);
-		LIST_INSERT_HEAD(&la->linkTableOut[start_point], lnk, list_out);
+		SPLAY_INSERT(splay_out, &la->splayTableOut, lnk);
 
 		/* Set up pointers for input lookup table */
 		if (lnk->flags & LINK_PARTIALLY_SPECIFIED)
@@ -1145,35 +1153,25 @@
 	return (new_lnk);
 }
 
-
-#define OUTGUARD					\
-   if (lnk->src_port != src_port ||			\
-       lnk->src_addr.s_addr != src_addr.s_addr ||	\
-       lnk->dst_addr.s_addr != dst_addr.s_addr ||	\
-       lnk->dst_port != dst_port ||			\
-       lnk->link_type != link_type)			\
-	   continue;
-
 static struct alias_link *
 _SearchLinkOut(struct libalias *la, struct in_addr src_addr,
     struct in_addr dst_addr,
     u_short src_port,
     u_short dst_port,
     int link_type) {
-	u_int i;
 	struct alias_link *lnk;
-
-	i = StartPointOut(src_addr, dst_addr, src_port, dst_port, link_type);
-	LIST_FOREACH(lnk, &la->linkTableOut[i], list_out) {
-		OUTGUARD;
-		return (UseLink(la, lnk));
-	}
-
-	return (NULL);
+	struct alias_link needle = {
+		.src_addr = src_addr,
+		.dst_addr = dst_addr,
+		.src_port = src_port,
+		.dst_port = dst_port,
+		.link_type = link_type
+	};
+
+	lnk = SPLAY_FIND(splay_out, &la->splayTableOut, &needle);
+	return (UseLink(la, lnk));
 }
 
-#undef OUTGUARD
-
 static struct alias_link *
 _FindLinkOut(struct libalias *la, struct in_addr src_addr,
     struct in_addr dst_addr,
@@ -1642,7 +1640,7 @@
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	LIST_FOREACH(lnk, &la->pptpTable, list_out)
+	LIST_FOREACH(lnk, &la->pptpTable, list_pptp)
 		if (lnk->src_addr.s_addr == src_addr.s_addr &&
 		    lnk->dst_addr.s_addr == dst_addr.s_addr &&
 		    lnk->src_port == src_call_id)
@@ -1659,7 +1657,7 @@
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	LIST_FOREACH(lnk, &la->pptpTable, list_out)
+	LIST_FOREACH(lnk, &la->pptpTable, list_pptp)
 		if (lnk->src_addr.s_addr == src_addr.s_addr &&
 		    lnk->dst_addr.s_addr == dst_addr.s_addr &&
 		    lnk->dst_port == dst_call_id)
@@ -1677,7 +1675,7 @@
 
 	LIBALIAS_LOCK_ASSERT(la);
 
-	LIST_FOREACH(lnk, &la->pptpTable, list_out)
+	LIST_FOREACH(lnk, &la->pptpTable, list_pptp)
 		if (lnk->dst_port == dst_call_id &&
 		    lnk->dst_addr.s_addr == dst_addr.s_addr &&
 		    lnk->alias_addr.s_addr == alias_addr.s_addr)
@@ -1694,7 +1692,7 @@
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	LIST_FOREACH(lnk, &la->pptpTable, list_out)
+	LIST_FOREACH(lnk, &la->pptpTable, list_pptp)
 		if (lnk->alias_port == alias_call_id &&
 		    lnk->dst_addr.s_addr == dst_addr.s_addr &&
 		    lnk->alias_addr.s_addr == alias_addr.s_addr)
@@ -2339,7 +2337,7 @@
 		if (head == NULL) {
 			server->next = server;
 			/* not usable for outgoing connections */
-			LIST_REMOVE(lnk, list_out);
+			SPLAY_REMOVE(splay_out, &la->splayTableOut, lnk);
 		} else {
 			struct server *s;
 
@@ -2509,10 +2507,10 @@
 		LibAliasTime = time(NULL);
 #endif
 
-		for (i = 0; i < LINK_TABLE_OUT_SIZE; i++)
-			LIST_INIT(&la->linkTableOut[i]);
+		SPLAY_INIT(&la->splayTableOut);
 		for (i = 0; i < LINK_TABLE_IN_SIZE; i++)
 			LIST_INIT(&la->groupTableIn[i]);
+		LIST_INIT(&la->pptpTable);
 		TAILQ_INIT(&la->checkExpire);
 #ifdef _KERNEL
 		AliasSctpInit(la);
Index: sys/netinet/libalias/alias_local.h
===================================================================
--- sys/netinet/libalias/alias_local.h
+++ sys/netinet/libalias/alias_local.h
@@ -48,6 +48,7 @@
 #ifndef _ALIAS_LOCAL_H_
 #define	_ALIAS_LOCAL_H_
 
+#include <sys/tree.h>
 #include <sys/types.h>
 #include <sys/sysctl.h>
 
@@ -100,7 +101,7 @@
 	/* Lookup table of pointers to chains of link records.
 	 * Each link record is doubly indexed into input and
 	 * output lookup tables. */
-	LIST_HEAD (, alias_link) linkTableOut[LINK_TABLE_OUT_SIZE];
+	SPLAY_HEAD(splay_out, alias_link) splayTableOut;
 	LIST_HEAD (, group_in)   groupTableIn[LINK_TABLE_IN_SIZE];
 	LIST_HEAD (, alias_link) pptpTable;
 	/* HouseKeeping */