shithub: libmujs

Download patch

ref: ff6f94236518e06e6274fe50c2a660ed45ec776d
parent: ac6cc9f7b7b59f47d85b1e9f4c924dcb3c2ac134
author: Tor Andersson <[email protected]>
date: Fri Jan 24 19:45:28 EST 2014 

Add AA-tree node removal.

Simplify string interning AA-tree skew and split operations.

Remove the recursion which is not needed.


--- a/jsintern.c
+++ b/jsintern.c
@@ -23,14 +23,11 @@
 
 static js_StringNode *jsS_skew(js_StringNode *node)
 {
-	if (node->level != 0) {
-		if (node->left->level == node->level) {
-			js_StringNode *save = node;
-			node = node->left;
-			save->left = node->right;
-			node->right = save;
-		}
-		node->right = jsS_skew(node->right);
+	if (node->left->level == node->level) {
+		js_StringNode *temp = node;
+		node = node->left;
+		temp->left = node->right;
+		node->right = temp;
 	}
 	return node;
 }
@@ -37,13 +34,12 @@
 
 static js_StringNode *jsS_split(js_StringNode *node)
 {
-	if (node->level != 0 && node->right->right->level == node->level) {
-		js_StringNode *save = node;
+	if (node->right->right->level == node->level) {
+		js_StringNode *temp = node;
 		node = node->right;
-		save->right = node->left;
-		node->left = save;
-		node->level++;
-		node->right = jsS_split(node->right);
+		temp->right = node->left;
+		node->left = temp;
+		++node->level;
 	}
 	return node;
 }
--- a/jsproperty.c
+++ b/jsproperty.c
@@ -48,14 +48,11 @@
 
 static inline js_Property *skew(js_Property *node)
 {
-	if (node->level != 0) {
-		if (node->left->level == node->level) {
-			js_Property *save = node;
-			node = node->left;
-			save->left = node->right;
-			node->right = save;
-		}
-		node->right = skew(node->right);
+	if (node->left->level == node->level) {
+		js_Property *temp = node;
+		node = node->left;
+		temp->left = node->right;
+		node->right = temp;
 	}
 	return node;
 }
@@ -62,13 +59,12 @@
 
 static inline js_Property *split(js_Property *node)
 {
-	if (node->level != 0 && node->right->right->level == node->level) {
-		js_Property *save = node;
+	if (node->right->right->level == node->level) {
+		js_Property *temp = node;
 		node = node->right;
-		save->right = node->left;
-		node->left = save;
-		node->level++;
-		node->right = split(node->right);
+		temp->right = node->left;
+		node->left = temp;
+		++node->level;
 	}
 	return node;
 }
@@ -92,7 +88,46 @@
 
 static js_Property *delete(js_State *J, js_Property *node, const char *name)
 {
-	// TODO
+	js_Property *temp, *succ;
+
+	if (node != &sentinel) {
+		int c = strcmp(name, node->name);
+		if (c < 0) {
+			node->left = delete(J, node->left, name);
+		} else if (c > 0) {
+			node->right = delete(J, node->right, name);
+		} else {
+			if (node->left == &sentinel) {
+				temp = node;
+				node = node->right;
+				free(temp);
+			} else if (node->right == &sentinel) {
+				temp = node;
+				node = node->left;
+				free(temp);
+			} else {
+				succ = node->right;
+				while (succ->left != &sentinel)
+					succ = succ->left;
+				node->name = succ->name;
+				node->atts = succ->atts;
+				node->value = succ->value;
+				node->right = delete(J, node->right, succ->name);
+			}
+		}
+
+		if (node->left->level < node->level - 1 ||
+			node->right->level < node->level - 1)
+		{
+			if (node->right->level > --node->level)
+				node->right->level = node->level;
+			node = skew(node);
+			node->right = skew(node->right);
+			node->right->right = skew(node->right->right);
+			node = split(node);
+			node->right = split(node->right);
+		}
+	}
 	return node;
 }
 
--- a/jsrun.c
+++ b/jsrun.c
@@ -762,8 +762,8 @@
 			break;
 
 		case OP_DELPROP:
-			obj = js_toobject(J, -3);
-			str = js_tostring(J, -2);
+			obj = js_toobject(J, -2);
+			str = js_tostring(J, -1);
 			jsR_delproperty(J, obj, str);
 			js_pop(J, 2);
 			break;
@@ -770,7 +770,7 @@
 
 		case OP_DELPROPS:
 			str = ST[*pc++];
-			obj = js_toobject(J, -2);
+			obj = js_toobject(J, -1);
 			jsR_delproperty(J, obj, str);
 			js_pop(J, 1);
 			break;