Add any() and remove_any() to ph.

These functions select the easiest-to-remove element in the heap, which
is either the most recently inserted aux list element or the root.  If
no calls are made to first() or remove_first(), the behavior (and time
complexity) is the same as for a LIFO queue.

1 files changed, 30 insertions, 1 deletions

diff --git a/test/unit/ph.c b/test/unit/ph.c
index 91516fa..01df340 100644
--- a/test/unit/ph.c
+++ b/test/unit/ph.c
@@ -142,6 +142,7 @@ TEST_BEGIN(test_ph_empty) {
 	heap_new(&heap);
 	assert_true(heap_empty(&heap), "Heap should be empty");
 	assert_ptr_null(heap_first(&heap), "Unexpected node");
+	assert_ptr_null(heap_any(&heap), "Unexpected node");
 }
 TEST_END
 
@@ -159,6 +160,13 @@ node_remove_first(heap_t *heap) {
 	return node;
 }
 
+static node_t *
+node_remove_any(heap_t *heap) {
+	node_t *node = heap_remove_any(heap);
+	node->magic = 0;
+	return node;
+}
+
 TEST_BEGIN(test_ph_random) {
 #define NNODES 25
 #define NBAGS 250
@@ -204,6 +212,8 @@ TEST_BEGIN(test_ph_random) {
 			for (k = 0; k < j; k++) {
 				heap_insert(&heap, &nodes[k]);
 				if (i % 13 == 12) {
+					assert_ptr_not_null(heap_any(&heap),
+					    "Heap should not be empty");
 					/* Trigger merging. */
 					assert_ptr_not_null(heap_first(&heap),
 					    "Heap should not be empty");
@@ -216,7 +226,7 @@ TEST_BEGIN(test_ph_random) {
 			    "Heap should not be empty");
 
 			/* Remove nodes. */
-			switch (i % 4) {
+			switch (i % 6) {
 			case 0:
 				for (k = 0; k < j; k++) {
 					assert_u_eq(heap_validate(&heap), j - k,
@@ -264,12 +274,31 @@ TEST_BEGIN(test_ph_random) {
 					prev = node;
 				}
 				break;
+			} case 4: {
+				for (k = 0; k < j; k++) {
+					node_remove_any(&heap);
+					assert_u_eq(heap_validate(&heap), j - k
+					    - 1, "Incorrect node count");
+				}
+				break;
+			} case 5: {
+				for (k = 0; k < j; k++) {
+					node_t *node = heap_any(&heap);
+					assert_u_eq(heap_validate(&heap), j - k,
+					    "Incorrect node count");
+					node_remove(&heap, node);
+					assert_u_eq(heap_validate(&heap), j - k
+					    - 1, "Incorrect node count");
+				}
+				break;
 			} default:
 				not_reached();
 			}
 
 			assert_ptr_null(heap_first(&heap),
 			    "Heap should be empty");
+			assert_ptr_null(heap_any(&heap),
+			    "Heap should be empty");
 			assert_true(heap_empty(&heap), "Heap should be empty");
 		}
 	}