code: mafs

Download patch

ref: 049a2d8b642eaa018ce78f723b0c137ed07a95a0
parent: d6bd63073480bf342aa572b39a176e24ff874a0e
author: 9ferno <gophone2015@gmail.com>
date: Thu Oct 27 10:41:22 EDT 2022 

obsoleted recursive doadd() as it is blowing up the stack


--- a/extents.c
+++ b/extents.c
@@ -57,10 +57,10 @@
 		/* e->low e =>
 			e->low c e
 		  */
-		if(e->low != nil)
-			e->low->high = c;
-		else
+		if(e->low == nil)
 			es->head = c;
+		else
+			e->low->high = c;
 		c->low = e->low;
 		e->low = c;
 		c->high = e;
@@ -221,47 +221,41 @@
 	e = es->lru;
 	dir = belongs(es->lru, start, len);
 	if(chatty9p > 7){
-		print(" 	belongs(e %llud %llud start %llud .. %llud) %llud\n",
+		print(" 	belongs(e %llud %llud start %llud .. %llud) %lld\n",
 			 e->start, e->start+e->len-1, start, start+len-1, dir);
 	}
-	if(dir == 0)
-		return increment(es, e, start, len);
-	else if(dir < 0){
+	if(dir < 0){
+		while(e->low != nil && (dir = belongs(e, start, len)) < 0){
+			es->lru = e;
+			e = e->low;
+		}
+		/* e->low e es->lru */
+		if(dir == 0)
+			return increment(es, e, start, len);
 		if(e->low == nil)
-			/* at the lowest extent, add a prev */
+			/* at the lowest extent, add below or above */
 			return addextent(es, e, start, len);
-		else if(e->low->start+e->low->len == start)
-			/* belongs in the ->low extent */
-			return increment(es, e->low, start, len);
-		else if(e->low->start+e->low->len < start)
-			/* between the e->low and e */
-			return addextent(es, e->low, start, len);
-		else{
-			/* search from e->low */
-			es->lru = e->low;
-			return doadd(es, start, len);
-		}
+
+		/* dir(e) > 0, hence, e < start < es->lru */
+		return addextent(es, es->lru, start, len);
 	}else if(dir > 0){
+		while(e->high != nil && (dir = belongs(e, start, len)) > 0){
+			es->lru = e;
+			e = e->high;
+		}
+		/* es->lru e e->high */
+		if(dir == 0)
+			return increment(es, e, start, len);
 		if(e->high == nil)
-			/* at the highest extent, add the next */
+			/* at the highest extent, add below or above */
 			return addextent(es, e, start, len);
-		else if(start+len == e->high->start)
-			/* belongs in the ->high extent */
-			return increment(es, e->high, start, len);
-		else if(start+len < e->high->start)
-			/* between e and e->high */
-			return addextent(es, e, start, len);
-		else{
-			es->lru = e->high;
-			/* search from e->high */
-			return doadd(es, start, len);
-		}
+
+		/* dir(e) < 0, hence, es->lru < start < e */
+		return addextent(es, es->lru, start, len);
 	}
+
 	/* dir == 0 */
-	sysfatal("add: should not be here"
-		 " e->start %llud .. %llud start %llud len %llud\n",
-		  e->start, e->start+e->len-1, start, len);
-	return e;
+	return increment(es, e, start, len);
 }
 
 Extent *
@@ -570,4 +564,70 @@
 initextents(Extents *es)
 {
 	es->isempty.l = &es->lck;
+}
+
+/* obsolete */
+Extent *
+doadd_recursive(Extents *es, u64 start, u64 len)
+{
+	s64 dir;
+	Extent *e;
+
+	if(es == nil)
+		panic("add es == nil");
+	if(es->lru == nil){
+		e = emalloc(sizeof(Extent));
+		e->low = e->high = nil;
+		e->start = start;
+		e->len = len;
+		es->lru = es->head = e;
+		es->n = 1;
+		return e;
+	}
+
+	/* using the previously used extent */
+	e = es->lru;
+	dir = belongs(es->lru, start, len);
+	if(chatty9p > 7){
+		print(" 	belongs(e %llud %llud start %llud .. %llud) %lld\n",
+			 e->start, e->start+e->len-1, start, start+len-1, dir);
+	}
+	if(dir == 0)
+		return increment(es, e, start, len);
+	else if(dir < 0){
+		if(e->low == nil)
+			/* at the lowest extent, add a prev */
+			return addextent(es, e, start, len);
+		else if(e->low->start+e->low->len == start)
+			/* belongs in the ->low extent */
+			return increment(es, e->low, start, len);
+		else if(e->low->start+e->low->len < start)
+			/* between the e->low and e */
+			return addextent(es, e->low, start, len);
+		else{
+			/* search from e->low */
+			es->lru = e->low;
+			return doadd(es, start, len);
+		}
+	}else if(dir > 0){
+		if(e->high == nil)
+			/* at the highest extent, add the next */
+			return addextent(es, e, start, len);
+		else if(start+len == e->high->start)
+			/* belongs in the ->high extent */
+			return increment(es, e->high, start, len);
+		else if(start+len < e->high->start)
+			/* between e and e->high */
+			return addextent(es, e, start, len);
+		else{
+			es->lru = e->high;
+			/* search from e->high */
+			return doadd(es, start, len);
+		}
+	}
+	/* dir == 0 */
+	sysfatal("add: should not be here"
+		 " e->start %llud .. %llud start %llud len %llud\n",
+		  e->start, e->start+e->len-1, start, len);
+	return e;
 }