From 24820d6ee9985782fb66b407e4897ef16163356f Mon Sep 17 00:00:00 2001
From: Heng Li <lh3@me.com>
Date: Sat, 14 Apr 2018 19:46:12 -0400
Subject: [PATCH] faster way to delete the first node

---
 kavl.h | 21 ++++++++++++++-------
 1 file changed, 14 insertions(+), 7 deletions(-)

diff --git a/kavl.h b/kavl.h
index 3155cc3..a1c40f3 100644
--- a/kavl.h
+++ b/kavl.h
@@ -182,12 +182,18 @@ int main(void) {
 		unsigned char dir[KAVL_MAX_DEPTH]; \
 		int i, d = 0, cmp; \
 		fake.__head.p[0] = *root_, fake.__head.p[1] = 0; \
-		for (cmp = -1, p = &fake; cmp; cmp = __cmp(x, p)) { \
-			int which = (cmp > 0); \
-			dir[d] = which; \
-			path[d++] = p; \
-			p = p->__head.p[which]; \
-			if (p == 0) return 0; \
+		if (x) { \
+			for (cmp = -1, p = &fake; cmp; cmp = __cmp(x, p)) { \
+				int which = (cmp > 0); \
+				dir[d] = which; \
+				path[d++] = p; \
+				p = p->__head.p[which]; \
+				if (p == 0) return 0; \
+			} \
+		} else { \
+			for (p = &fake; p; p = p->__head.p[0]) \
+				dir[d] = 0, path[d++] = p; \
+			p = path[--d]; \
 		} \
 		for (i = 1; i < d; ++i) --path[i]->__head.size; \
 		if (p->__head.p[1] == 0) { /* ((1,.)2,3)4 => (1,3)4; p=2 */ \
@@ -314,11 +320,12 @@ int main(void) {
  *
  * @param suf     name suffix used in KAVL_INIT()
  * @param proot   pointer to the root of the tree (in/out: root may change)
- * @param x       node value to delete (in)
+ * @param x       node value to delete; if NULL, delete the first node (in)
  *
  * @return node removed from the tree if present, or NULL if absent
  */
 #define kavl_erase(suf, proot, x) kavl_erase_##suf(proot, x)
+#define kavl_erase_first(suf, proot) kavl_erase_##suf(proot, 0)
 
 #define kavl_itr_t(suf) struct kavl_itr_##suf
 #define kavl_itr_first(suf, root, itr) kavl_itr_first_##suf(root, itr)
-- 
2.47.3