[master] Add support for manipulating lease queues via a binary search.

Add support for manipluating the queues holding leaes for time
based events (free, backup, active, expired, abandoned and reserved)
via a binary search instead of walking through the linked list.

3 files changed, 552 insertions, 11 deletions

diff --git a/server/tests/Makefile.am b/server/tests/Makefile.am
index fb345c54..84ae202b 100644
--- a/server/tests/Makefile.am
+++ b/server/tests/Makefile.am
@@ -15,7 +15,7 @@ info:
 DHCPSRC = ../dhcp.c ../bootp.c ../confpars.c ../db.c ../class.c      \
           ../failover.c ../omapi.c ../mdb.c ../stables.c ../salloc.c \
           ../ddns.c ../dhcpleasequery.c ../dhcpv6.c ../mdb6.c        \
-          ../ldap.c ../ldap_casa.c ../dhcpd.c
+          ../ldap.c ../ldap_casa.c ../dhcpd.c ../leasechain.c
 
 DHCPLIBS = $(top_builddir)/common/libdhcp.a $(top_builddir)/omapip/libomapi.a    \
           $(top_builddir)/dhcpctl/libdhcpctl.a $(top_builddir)/bind/lib/libirs.a \
@@ -25,7 +25,7 @@ DHCPLIBS = $(top_builddir)/common/libdhcp.a $(top_builddir)/omapip/libomapi.a
 ATF_TESTS =
 if HAVE_ATF
 
-ATF_TESTS += dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests
+ATF_TESTS += dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests leaseq_unittests
 
 dhcpd_unittests_SOURCES = $(DHCPSRC)
 dhcpd_unittests_SOURCES += simple_unittest.c
@@ -45,6 +45,9 @@ legacy_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 load_bal_unittests_SOURCES = $(DHCPSRC) load_bal_unittest.c
 load_bal_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 
+leaseq_unittests_SOURCES = $(DHCPSRC) leaseq_unittest.c
+leaseq_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
+
 check: $(ATF_TESTS)
 	sh ${top_srcdir}/tests/unittest.sh
 
diff --git a/server/tests/Makefile.in b/server/tests/Makefile.in
index a103666e..d0da6aa4 100644
--- a/server/tests/Makefile.in
+++ b/server/tests/Makefile.in
@@ -77,7 +77,7 @@ PRE_UNINSTALL = :
 POST_UNINSTALL = :
 build_triplet = @build@
 host_triplet = @host@
-@HAVE_ATF_TRUE@am__append_1 = dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests
+@HAVE_ATF_TRUE@am__append_1 = dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests leaseq_unittests
 check_PROGRAMS = $(am__EXEEXT_2)
 subdir = server/tests
 DIST_COMMON = $(srcdir)/Makefile.in $(srcdir)/Makefile.am \
@@ -93,19 +93,20 @@ CONFIG_CLEAN_VPATH_FILES =
 @HAVE_ATF_TRUE@am__EXEEXT_1 = dhcpd_unittests$(EXEEXT) \
 @HAVE_ATF_TRUE@	legacy_unittests$(EXEEXT) \
 @HAVE_ATF_TRUE@	hash_unittests$(EXEEXT) \
-@HAVE_ATF_TRUE@	load_bal_unittests$(EXEEXT)
+@HAVE_ATF_TRUE@	load_bal_unittests$(EXEEXT) \
+@HAVE_ATF_TRUE@	leaseq_unittests$(EXEEXT)
 am__EXEEXT_2 = $(am__EXEEXT_1)
 am__dhcpd_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
 	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
 	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
 	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
-	simple_unittest.c
+	../leasechain.c simple_unittest.c
 am__objects_1 = dhcp.$(OBJEXT) bootp.$(OBJEXT) confpars.$(OBJEXT) \
 	db.$(OBJEXT) class.$(OBJEXT) failover.$(OBJEXT) \
 	omapi.$(OBJEXT) mdb.$(OBJEXT) stables.$(OBJEXT) \
 	salloc.$(OBJEXT) ddns.$(OBJEXT) dhcpleasequery.$(OBJEXT) \
 	dhcpv6.$(OBJEXT) mdb6.$(OBJEXT) ldap.$(OBJEXT) \
-	ldap_casa.$(OBJEXT) dhcpd.$(OBJEXT)
+	ldap_casa.$(OBJEXT) dhcpd.$(OBJEXT) leasechain.$(OBJEXT)
 @HAVE_ATF_TRUE@am_dhcpd_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	simple_unittest.$(OBJEXT)
 dhcpd_unittests_OBJECTS = $(am_dhcpd_unittests_OBJECTS)
@@ -118,17 +119,27 @@ am__hash_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
 	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
 	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
 	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
-	hash_unittest.c
+	../leasechain.c hash_unittest.c
 @HAVE_ATF_TRUE@am_hash_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	hash_unittest.$(OBJEXT)
 hash_unittests_OBJECTS = $(am_hash_unittests_OBJECTS)
 @HAVE_ATF_TRUE@hash_unittests_DEPENDENCIES = $(DHCPLIBS) \
 @HAVE_ATF_TRUE@	$(am__DEPENDENCIES_1)
+am__leaseq_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
+	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
+	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
+	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
+	../leasechain.c leaseq_unittest.c
+@HAVE_ATF_TRUE@am_leaseq_unittests_OBJECTS = $(am__objects_1) \
+@HAVE_ATF_TRUE@	leaseq_unittest.$(OBJEXT)
+leaseq_unittests_OBJECTS = $(am_leaseq_unittests_OBJECTS)
+@HAVE_ATF_TRUE@leaseq_unittests_DEPENDENCIES = $(DHCPLIBS) \
+@HAVE_ATF_TRUE@	$(am__DEPENDENCIES_1)
 am__legacy_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
 	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
 	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
 	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
-	mdb6_unittest.c
+	../leasechain.c mdb6_unittest.c
 @HAVE_ATF_TRUE@am_legacy_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	mdb6_unittest.$(OBJEXT)
 legacy_unittests_OBJECTS = $(am_legacy_unittests_OBJECTS)
@@ -138,7 +149,7 @@ am__load_bal_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c \
 	../confpars.c ../db.c ../class.c ../failover.c ../omapi.c \
 	../mdb.c ../stables.c ../salloc.c ../ddns.c \
 	../dhcpleasequery.c ../dhcpv6.c ../mdb6.c ../ldap.c \
-	../ldap_casa.c ../dhcpd.c load_bal_unittest.c
+	../ldap_casa.c ../dhcpd.c ../leasechain.c load_bal_unittest.c
 @HAVE_ATF_TRUE@am_load_bal_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	load_bal_unittest.$(OBJEXT)
 load_bal_unittests_OBJECTS = $(am_load_bal_unittests_OBJECTS)
@@ -177,9 +188,11 @@ am__v_CCLD_ = $(am__v_CCLD_@AM_DEFAULT_V@)
 am__v_CCLD_0 = @echo "  CCLD    " $@;
 am__v_CCLD_1 = 
 SOURCES = $(dhcpd_unittests_SOURCES) $(hash_unittests_SOURCES) \
-	$(legacy_unittests_SOURCES) $(load_bal_unittests_SOURCES)
+	$(leaseq_unittests_SOURCES) $(legacy_unittests_SOURCES) \
+	$(load_bal_unittests_SOURCES)
 DIST_SOURCES = $(am__dhcpd_unittests_SOURCES_DIST) \
 	$(am__hash_unittests_SOURCES_DIST) \
+	$(am__leaseq_unittests_SOURCES_DIST) \
 	$(am__legacy_unittests_SOURCES_DIST) \
 	$(am__load_bal_unittests_SOURCES_DIST)
 RECURSIVE_TARGETS = all-recursive check-recursive cscopelist-recursive \
@@ -361,7 +374,7 @@ EXTRA_DIST = Atffile
 DHCPSRC = ../dhcp.c ../bootp.c ../confpars.c ../db.c ../class.c      \
           ../failover.c ../omapi.c ../mdb.c ../stables.c ../salloc.c \
           ../ddns.c ../dhcpleasequery.c ../dhcpv6.c ../mdb6.c        \
-          ../ldap.c ../ldap_casa.c ../dhcpd.c
+          ../ldap.c ../ldap_casa.c ../dhcpd.c ../leasechain.c
 
 DHCPLIBS = $(top_builddir)/common/libdhcp.a $(top_builddir)/omapip/libomapi.a    \
           $(top_builddir)/dhcpctl/libdhcpctl.a $(top_builddir)/bind/lib/libirs.a \
@@ -380,6 +393,8 @@ ATF_TESTS = $(am__append_1)
 @HAVE_ATF_TRUE@legacy_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 @HAVE_ATF_TRUE@load_bal_unittests_SOURCES = $(DHCPSRC) load_bal_unittest.c
 @HAVE_ATF_TRUE@load_bal_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
+@HAVE_ATF_TRUE@leaseq_unittests_SOURCES = $(DHCPSRC) leaseq_unittest.c
+@HAVE_ATF_TRUE@leaseq_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 all: all-recursive
 
 .SUFFIXES:
@@ -426,6 +441,10 @@ hash_unittests$(EXEEXT): $(hash_unittests_OBJECTS) $(hash_unittests_DEPENDENCIES
 	@rm -f hash_unittests$(EXEEXT)
 	$(AM_V_CCLD)$(LINK) $(hash_unittests_OBJECTS) $(hash_unittests_LDADD) $(LIBS)
 
+leaseq_unittests$(EXEEXT): $(leaseq_unittests_OBJECTS) $(leaseq_unittests_DEPENDENCIES) $(EXTRA_leaseq_unittests_DEPENDENCIES) 
+	@rm -f leaseq_unittests$(EXEEXT)
+	$(AM_V_CCLD)$(LINK) $(leaseq_unittests_OBJECTS) $(leaseq_unittests_LDADD) $(LIBS)
+
 legacy_unittests$(EXEEXT): $(legacy_unittests_OBJECTS) $(legacy_unittests_DEPENDENCIES) $(EXTRA_legacy_unittests_DEPENDENCIES) 
 	@rm -f legacy_unittests$(EXEEXT)
 	$(AM_V_CCLD)$(LINK) $(legacy_unittests_OBJECTS) $(legacy_unittests_LDADD) $(LIBS)
@@ -453,6 +472,8 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ldap.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ldap_casa.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/leasechain.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/leaseq_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/load_bal_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mdb.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mdb6.Po@am__quote@
@@ -714,6 +735,20 @@ dhcpd.obj: ../dhcpd.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o dhcpd.obj `if test -f '../dhcpd.c'; then $(CYGPATH_W) '../dhcpd.c'; else $(CYGPATH_W) '$(srcdir)/../dhcpd.c'; fi`
 
+leasechain.o: ../leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT leasechain.o -MD -MP -MF $(DEPDIR)/leasechain.Tpo -c -o leasechain.o `test -f '../leasechain.c' || echo '$(srcdir)/'`../leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/leasechain.Tpo $(DEPDIR)/leasechain.Po
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='../leasechain.c' object='leasechain.o' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o leasechain.o `test -f '../leasechain.c' || echo '$(srcdir)/'`../leasechain.c
+
+leasechain.obj: ../leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT leasechain.obj -MD -MP -MF $(DEPDIR)/leasechain.Tpo -c -o leasechain.obj `if test -f '../leasechain.c'; then $(CYGPATH_W) '../leasechain.c'; else $(CYGPATH_W) '$(srcdir)/../leasechain.c'; fi`
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/leasechain.Tpo $(DEPDIR)/leasechain.Po
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='../leasechain.c' object='leasechain.obj' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o leasechain.obj `if test -f '../leasechain.c'; then $(CYGPATH_W) '../leasechain.c'; else $(CYGPATH_W) '$(srcdir)/../leasechain.c'; fi`
+
 # This directory's subdirectories are mostly independent; you can cd
 # into them and run 'make' without going through this Makefile.
 # To change the values of 'make' variables: instead of editing Makefiles,
diff --git a/server/tests/leaseq_unittest.c b/server/tests/leaseq_unittest.c
new file mode 100644
index 00000000..9a9313e5
--- /dev/null
+++ b/server/tests/leaseq_unittest.c
@@ -0,0 +1,503 @@
+/*
+ * Copyright (C) 2015 Internet Systems Consortium, Inc. ("ISC")
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
+ * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
+ * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+ * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
+ * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <config.h>
+
+#include "dhcpd.h"
+
+#include <atf-c.h>
+
+/*
+ * Test the lease queue code.  These tests will verify that we can
+ * add, find and remove leases from the lease queue code
+ *
+ * Thoughout the tests
+ * lq will be the lease queue for which we add or removing leases
+ * test_leaseX will be the leases we add or remove
+ * We only care about the sort_time in the lease structure for these
+ * tests but need to do a lease_reference in order to keep the ref
+ * count positive to avoid the omapi code trying to free the object.
+ * We can't use lease_allocate easily as we haven't set up the omapi
+ * object information in the test.
+ */
+
+#if defined (BINARY_LEASES)
+#define INIT_LQ(LQ) memset(&(LQ), 0, sizeof(struct leasechain))
+#else
+#define INIT_LQ(LQ) lq = NULL
+#endif
+
+/* Test basic leaseq functions with a single lease */
+/*- empty, add, get, and remove */
+ATF_TC(leaseq_basic);
+ATF_TC_HEAD(leaseq_basic, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify basic functions");
+}
+
+ATF_TC_BODY(leaseq_basic, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease1, *check_lease;
+
+	INIT_LQ(lq);
+
+	memset(&test_lease1, 0, sizeof(struct lease));
+	test_lease1.sort_time = 10;
+	check_lease = NULL;
+	lease_reference(&check_lease, &test_lease1, MDL);
+
+	/* Check that the lq is empty */
+	if ((LEASE_NOT_EMPTY(lq)) || (LEASE_NOT_EMPTYP(&lq)))
+		atf_tc_fail("lq not empty at start.");
+
+	/* And that getting the first lease is okay when queue is empty  */
+	if ((LEASE_GET_FIRST(lq) != NULL) || (LEASE_GET_FIRSTP(&lq) != NULL))
+		atf_tc_fail("lease not null");
+
+	/* Add a lease */
+	LEASE_INSERTP(&lq, &test_lease1);
+
+	/* lq shouldn't be empty anymore */
+	if (!(LEASE_NOT_EMPTY(lq)) || !(LEASE_NOT_EMPTYP(&lq)))
+		atf_tc_fail("lq empty after insertion.");
+
+	/* We should have the same lease we inserted */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease1)
+		atf_tc_fail("leases don't match");
+
+	/* We should have the same lease we inserted */
+	check_lease = LEASE_GET_FIRSTP(&lq);
+	if (check_lease != &test_lease1)
+		atf_tc_fail("leases don't match");
+
+	/* Check that doing a get on the last lease returns NULL */
+	if ((LEASE_GET_NEXT(lq, check_lease) != NULL) ||
+	    (LEASE_GET_NEXTP(&lq, check_lease) != NULL)) {
+		atf_tc_fail("Next not null");
+	}
+
+	/* Remove the lease */
+	LEASE_REMOVEP(&lq, &test_lease1);
+
+	/* and verify the lease queue is empty again */
+	if ((LEASE_NOT_EMPTY(lq)) || (LEASE_NOT_EMPTYP(&lq)))
+		atf_tc_fail("lq not empty afer removal");
+
+	/* And that getting the first lease is okay when queue is empty  */
+	if ((LEASE_GET_FIRST(lq) != NULL) || (LEASE_GET_FIRSTP(&lq) != NULL))
+		atf_tc_fail("lease not null");
+}
+
+/* Test if we can add leases to the end of the list and remove them
+ * from the end */
+ATF_TC(leaseq_add_to_end);
+ATF_TC_HEAD(leaseq_add_to_end, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding to end of list");
+}
+
+ATF_TC_BODY(leaseq_add_to_end, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create and add 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 3; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+
+	/* Remove the last lease and check the list */
+	LEASE_REMOVEP(&lq, &test_lease[2]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("wrong lease after remove, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("wrong lease after remove, 2");
+
+	LEASE_REMOVEP(&lq, &test_lease[1]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("wrong lease after remove, 3");
+
+	LEASE_REMOVEP(&lq, check_lease);
+
+	/* The lease queue should now be empty */
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("lq not empty afer removal");
+}
+
+/* Test if we can add leases to the start of the list and remove them
+ * from the start */
+ATF_TC(leaseq_add_to_start);
+ATF_TC_HEAD(leaseq_add_to_start, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding to start of list");
+}
+
+ATF_TC_BODY(leaseq_add_to_start, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+	}
+
+	/* Add leases */
+	LEASE_INSERTP(&lq, &test_lease[2]);
+	LEASE_INSERTP(&lq, &test_lease[1]);
+	LEASE_INSERTP(&lq, &test_lease[0]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 3; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+
+	/* Remove the first lease and check the next one */
+	check_lease = LEASE_GET_FIRST(lq);
+	LEASE_REMOVEP(&lq, check_lease);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("wrong lease after remove, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 2");
+
+	check_lease = LEASE_GET_FIRST(lq);
+	LEASE_REMOVEP(&lq, check_lease);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 3");
+
+	LEASE_REMOVEP(&lq, check_lease);
+
+	/* The lease queue should now be empty */
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("lq not empty afer removal");
+}
+
+/* Test if we can add leases to the middle of the list and remove them
+ * from the middle */
+ATF_TC(leaseq_add_to_middle);
+ATF_TC_HEAD(leaseq_add_to_middle, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding to end of list");
+}
+
+ATF_TC_BODY(leaseq_add_to_middle, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+	}
+
+	/* Add leases */
+	LEASE_INSERTP(&lq, &test_lease[0]);
+	LEASE_INSERTP(&lq, &test_lease[2]);
+	LEASE_INSERTP(&lq, &test_lease[1]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 3; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+
+	/* Remove the middle lease and check the list */
+	LEASE_REMOVEP(&lq, &test_lease[1]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("wrong lease after remove, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 2");
+
+	LEASE_REMOVEP(&lq, &test_lease[0]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 3");
+
+	LEASE_REMOVEP(&lq, check_lease);
+
+	/* The lease queue should now be empty */
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("lq not empty afer removal");
+}
+
+/* Test if we can cycle the leases we add three leases then remove
+ * the first one, update it's sort time and re add it */
+ATF_TC(leaseq_cycle);
+ATF_TC_HEAD(leaseq_cycle, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify cycling the list");
+}
+
+ATF_TC_BODY(leaseq_cycle, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create and add 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* Remove first lease, update it and re-insert it */
+	LEASE_REMOVEP(&lq, &test_lease[0]);
+	test_lease[0].sort_time = 4;
+	LEASE_INSERTP(&lq, &test_lease[0]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("leases don't match, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("leases don't match, 2");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("leases don't match, 3");
+
+	/* Remove first lease, update it and re-insert it */
+	LEASE_REMOVEP(&lq, &test_lease[1]);
+	test_lease[1].sort_time = 5;
+	LEASE_INSERTP(&lq, &test_lease[1]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("leases don't match, 4");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("leases don't match, 5");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("leases don't match, 6");
+
+	/* Remove first lease, update it and re-insert it */
+	LEASE_REMOVEP(&lq, &test_lease[2]);
+	test_lease[2].sort_time = 6;
+	LEASE_INSERTP(&lq, &test_lease[2]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("leases don't match, 7");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("leases don't match, 8");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("leases don't match, 9");
+}
+
+/* Test what happens if we set the growth factor to a smallish number
+ * and add enough leases to require it to grow multiple times
+ * Mostly this is for the binary leases case but we can most of the
+ * test for both.
+ */
+
+ATF_TC(leaseq_long);
+ATF_TC_HEAD(leaseq_long, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify a long list");
+}
+
+ATF_TC_BODY(leaseq_long, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[20], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+#if defined (BINARY_LEASES)
+	lc_init_growth(&lq, 5);
+#endif
+
+	/* create and add 10 leases */
+	for (i = 0; i < 10; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 10; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+
+	/* Remove first 5 */
+	for (i = 0; i < 5; i++) {
+		LEASE_REMOVEP(&lq, &test_lease[i]);
+	}
+
+	/* Add 10 more */
+	for (i = 10; i < 20; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* and the first 5 */
+	for (i = 0; i < 5; i++) {
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* and check them all out */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 20; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+}
+
+/* Test if we can add leases that all have the same sort time
+ */
+ATF_TC(leaseq_same_time);
+ATF_TC_HEAD(leaseq_same_time, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding leases with same time");
+}
+
+ATF_TC_BODY(leaseq_same_time, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[20], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create and add 20 leases */
+	for (i = 0; i < 20; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		if (i < 10) 
+			test_lease[i].sort_time = 10;
+		else
+			test_lease[i].sort_time = 20;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+#if defined (BINARY_LEASES)
+	/* the ordering isn't well defined for either but we check
+	 * to see what happens in the binary case.  At the start
+	 * the leases should stay in the order they were added.
+	 */
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 20; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match 1, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+#endif
+
+	/* Remove first 10, update their time, but still before
+	 * the previous 10 and re add them */
+	for (i = 0; i < 10; i++) {
+		LEASE_REMOVEP(&lq, &test_lease[i]);
+		test_lease[i].sort_time = 15;
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* The ordering becomes random at this point so we don't
+	 * check it.  We try to remove them all and see that
+	 * we got to an empty queue.
+	 */
+	for (i = 0; i < 20; i++) {
+		LEASE_REMOVEP(&lq, &test_lease[i]);
+	}
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("queue not empty");
+
+}
+
+ATF_TP_ADD_TCS(tp)
+{
+	ATF_TP_ADD_TC(tp, leaseq_basic);
+	ATF_TP_ADD_TC(tp, leaseq_add_to_end);
+	ATF_TP_ADD_TC(tp, leaseq_add_to_start);
+	ATF_TP_ADD_TC(tp, leaseq_add_to_middle);
+	ATF_TP_ADD_TC(tp, leaseq_cycle);
+	ATF_TP_ADD_TC(tp, leaseq_long);
+	ATF_TP_ADD_TC(tp, leaseq_same_time);
+	return (atf_no_error());
+}