Skip to content

Commit 2377f7c

Browse files
mbostockmbostock
committed
Fix leak when removing nodes from rb-tree.
1 parent 3c8808a commit 2377f7c

5 files changed

Lines changed: 91 additions & 86 deletions

File tree

‎d3.js‎

Lines changed: 42 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -4536,7 +4536,7 @@ d3 = function() {
45364536
}
45374537
var d3_geom_voronoiEdges, d3_geom_voronoiCells, d3_geom_voronoiBeaches, d3_geom_voronoiBeachJunkyard = [], d3_geom_voronoiFirstCircle, d3_geom_voronoiCircles, d3_geom_voronoiCircleJunkyard = [];
45384538
function d3_geom_voronoiBeach() {
4539-
d3_geom_voronoiRedBlackNode.call(this);
4539+
d3_geom_voronoiRedBlackNode(this);
45404540
this.edge = this.site = this.circle = null;
45414541
}
45424542
function d3_geom_voronoiCreateBeach(site) {
@@ -4548,6 +4548,7 @@ d3 = function() {
45484548
d3_geom_voronoiDetachCircle(beach);
45494549
d3_geom_voronoiBeaches.remove(beach);
45504550
d3_geom_voronoiBeachJunkyard.push(beach);
4551+
d3_geom_voronoiRedBlackNode(beach);
45514552
}
45524553
function d3_geom_voronoiRemoveBeach(beach) {
45534554
var circle = beach.circle, x = circle[0], y = circle.cy, vertex = [ x, y ], previous = beach.P, next = beach.N, disappearing = [ beach ];
@@ -4699,7 +4700,7 @@ d3 = function() {
46994700
return b.angle - a.angle;
47004701
}
47014702
function d3_geom_voronoiCircle() {
4702-
d3_geom_voronoiRedBlackNode.call(this);
4703+
d3_geom_voronoiRedBlackNode(this);
47034704
this[0] = this[1] = this.arc = this.site = this.cy = null;
47044705
}
47054706
function d3_geom_voronoiAttachCircle(arc) {
@@ -4741,6 +4742,7 @@ d3 = function() {
47414742
if (!circle.P) d3_geom_voronoiFirstCircle = circle.N;
47424743
d3_geom_voronoiCircles.remove(circle);
47434744
d3_geom_voronoiCircleJunkyard.push(circle);
4745+
d3_geom_voronoiRedBlackNode(circle);
47444746
arc.circle = null;
47454747
}
47464748
}
@@ -4882,53 +4884,53 @@ d3 = function() {
48824884
function d3_geom_voronoiRedBlackTree() {
48834885
this._ = null;
48844886
}
4885-
function d3_geom_voronoiRedBlackNode() {
4886-
this.U = this.C = this.L = this.R = this.P = this.N = null;
4887+
function d3_geom_voronoiRedBlackNode(node) {
4888+
node.U = node.C = node.L = node.R = node.P = node.N = null;
48874889
}
48884890
d3_geom_voronoiRedBlackTree.prototype = {
4889-
insert: function(node, successor) {
4891+
insert: function(after, node) {
48904892
var parent, grandpa, uncle;
4891-
if (node) {
4892-
successor.P = node;
4893-
successor.N = node.N;
4894-
if (node.N) node.N.P = successor;
4895-
node.N = successor;
4896-
if (node.R) {
4897-
node = node.R;
4898-
while (node.L) node = node.L;
4899-
node.L = successor;
4893+
if (after) {
4894+
node.P = after;
4895+
node.N = after.N;
4896+
if (after.N) after.N.P = node;
4897+
after.N = node;
4898+
if (after.R) {
4899+
after = after.R;
4900+
while (after.L) after = after.L;
4901+
after.L = node;
49004902
} else {
4901-
node.R = successor;
4903+
after.R = node;
49024904
}
4903-
parent = node;
4905+
parent = after;
49044906
} else if (this._) {
4905-
node = d3_geom_voronoiRedBlackFirst(this._);
4906-
successor.P = null;
4907-
successor.N = node;
4908-
node.P = node.L = successor;
4909-
parent = node;
4907+
after = d3_geom_voronoiRedBlackFirst(this._);
4908+
node.P = null;
4909+
node.N = after;
4910+
after.P = after.L = node;
4911+
parent = after;
49104912
} else {
4911-
successor.P = successor.N = null;
4912-
this._ = successor;
4913+
node.P = node.N = null;
4914+
this._ = node;
49134915
parent = null;
49144916
}
4915-
successor.L = successor.R = null;
4916-
successor.U = parent;
4917-
successor.C = true;
4918-
node = successor;
4917+
node.L = node.R = null;
4918+
node.U = parent;
4919+
node.C = true;
4920+
after = node;
49194921
while (parent && parent.C) {
49204922
grandpa = parent.U;
49214923
if (parent === grandpa.L) {
49224924
uncle = grandpa.R;
49234925
if (uncle && uncle.C) {
49244926
parent.C = uncle.C = false;
49254927
grandpa.C = true;
4926-
node = grandpa;
4928+
after = grandpa;
49274929
} else {
4928-
if (node === parent.R) {
4930+
if (after === parent.R) {
49294931
d3_geom_voronoiRedBlackRotateLeft(this, parent);
4930-
node = parent;
4931-
parent = node.U;
4932+
after = parent;
4933+
parent = after.U;
49324934
}
49334935
parent.C = false;
49344936
grandpa.C = true;
@@ -4939,35 +4941,35 @@ d3 = function() {
49394941
if (uncle && uncle.C) {
49404942
parent.C = uncle.C = false;
49414943
grandpa.C = true;
4942-
node = grandpa;
4944+
after = grandpa;
49434945
} else {
4944-
if (node === parent.L) {
4946+
if (after === parent.L) {
49454947
d3_geom_voronoiRedBlackRotateRight(this, parent);
4946-
node = parent;
4947-
parent = node.U;
4948+
after = parent;
4949+
parent = after.U;
49484950
}
49494951
parent.C = false;
49504952
grandpa.C = true;
49514953
d3_geom_voronoiRedBlackRotateLeft(this, grandpa);
49524954
}
49534955
}
4954-
parent = node.U;
4956+
parent = after.U;
49554957
}
49564958
this._.C = false;
49574959
},
49584960
remove: function(node) {
49594961
if (node.N) node.N.P = node.P;
49604962
if (node.P) node.P.N = node.N;
49614963
node.N = node.P = null;
4962-
var parent = node.U, sibling, left = node.L, right = node.R, next, isRed;
4964+
var parent = node.U, sibling, left = node.L, right = node.R, next, red;
49634965
if (!left) next = right; else if (!right) next = left; else next = d3_geom_voronoiRedBlackFirst(right);
49644966
if (parent) {
49654967
if (parent.L === node) parent.L = next; else parent.R = next;
49664968
} else {
49674969
this._ = next;
49684970
}
49694971
if (left && right) {
4970-
isRed = next.C;
4972+
red = next.C;
49714973
next.C = node.C;
49724974
next.L = left;
49734975
left.U = next;
@@ -4984,11 +4986,11 @@ d3 = function() {
49844986
node = next.R;
49854987
}
49864988
} else {
4987-
isRed = node.C;
4989+
red = node.C;
49884990
node = next;
49894991
}
49904992
if (node) node.U = parent;
4991-
if (isRed) return;
4993+
if (red) return;
49924994
if (node && node.C) {
49934995
node.C = false;
49944996
return;

‎d3.min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/geom/voronoi/beach.js‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
function d3_geom_voronoiBeach() {
2-
d3_geom_voronoiRedBlackNode.call(this);
2+
d3_geom_voronoiRedBlackNode(this);
33
this.edge =
44
this.site =
55
this.circle = null;
@@ -15,6 +15,7 @@ function d3_geom_voronoiDetachBeach(beach) {
1515
d3_geom_voronoiDetachCircle(beach);
1616
d3_geom_voronoiBeaches.remove(beach);
1717
d3_geom_voronoiBeachJunkyard.push(beach);
18+
d3_geom_voronoiRedBlackNode(beach);
1819
}
1920

2021
function d3_geom_voronoiRemoveBeach(beach) {

‎src/geom/voronoi/circle.js‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
function d3_geom_voronoiCircle() {
2-
d3_geom_voronoiRedBlackNode.call(this);
2+
d3_geom_voronoiRedBlackNode(this);
33
this[0] =
44
this[1] =
55
this.arc =
@@ -67,6 +67,7 @@ function d3_geom_voronoiDetachCircle(arc) {
6767
if (!circle.P) d3_geom_voronoiFirstCircle = circle.N;
6868
d3_geom_voronoiCircles.remove(circle);
6969
d3_geom_voronoiCircleJunkyard.push(circle);
70+
d3_geom_voronoiRedBlackNode(circle);
7071
arc.circle = null;
7172
}
7273
}

‎src/geom/voronoi/red-black.js‎

Lines changed: 44 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -2,62 +2,62 @@ function d3_geom_voronoiRedBlackTree() {
22
this._ = null; // root node
33
}
44

5-
function d3_geom_voronoiRedBlackNode() {
6-
this.U = // parent node
7-
this.C = // color - true for red, false for black
8-
this.L = // left node
9-
this.R = // right node
10-
this.P = // previous node
11-
this.N = null; // next node
5+
function d3_geom_voronoiRedBlackNode(node) {
6+
node.U = // parent node
7+
node.C = // color - true for red, false for black
8+
node.L = // left node
9+
node.R = // right node
10+
node.P = // previous node
11+
node.N = null; // next node
1212
}
1313

1414
d3_geom_voronoiRedBlackTree.prototype = {
1515

16-
insert: function(node, successor) {
16+
insert: function(after, node) {
1717
var parent, grandpa, uncle;
1818

19-
if (node) {
20-
successor.P = node;
21-
successor.N = node.N;
22-
if (node.N) node.N.P = successor;
23-
node.N = successor;
24-
if (node.R) {
25-
node = node.R;
26-
while (node.L) node = node.L;
27-
node.L = successor;
19+
if (after) {
20+
node.P = after;
21+
node.N = after.N;
22+
if (after.N) after.N.P = node;
23+
after.N = node;
24+
if (after.R) {
25+
after = after.R;
26+
while (after.L) after = after.L;
27+
after.L = node;
2828
} else {
29-
node.R = successor;
29+
after.R = node;
3030
}
31-
parent = node;
31+
parent = after;
3232
} else if (this._) {
33-
node = d3_geom_voronoiRedBlackFirst(this._);
34-
successor.P = null;
35-
successor.N = node;
36-
node.P = node.L = successor;
37-
parent = node;
33+
after = d3_geom_voronoiRedBlackFirst(this._);
34+
node.P = null;
35+
node.N = after;
36+
after.P = after.L = node;
37+
parent = after;
3838
} else {
39-
successor.P = successor.N = null;
40-
this._ = successor;
39+
node.P = node.N = null;
40+
this._ = node;
4141
parent = null;
4242
}
43-
successor.L = successor.R = null;
44-
successor.U = parent;
45-
successor.C = true;
43+
node.L = node.R = null;
44+
node.U = parent;
45+
node.C = true;
4646

47-
node = successor;
47+
after = node;
4848
while (parent && parent.C) {
4949
grandpa = parent.U;
5050
if (parent === grandpa.L) {
5151
uncle = grandpa.R;
5252
if (uncle && uncle.C) {
5353
parent.C = uncle.C = false;
5454
grandpa.C = true;
55-
node = grandpa;
55+
after = grandpa;
5656
} else {
57-
if (node === parent.R) {
57+
if (after === parent.R) {
5858
d3_geom_voronoiRedBlackRotateLeft(this, parent);
59-
node = parent;
60-
parent = node.U;
59+
after = parent;
60+
parent = after.U;
6161
}
6262
parent.C = false;
6363
grandpa.C = true;
@@ -68,19 +68,19 @@ d3_geom_voronoiRedBlackTree.prototype = {
6868
if (uncle && uncle.C) {
6969
parent.C = uncle.C = false;
7070
grandpa.C = true;
71-
node = grandpa;
71+
after = grandpa;
7272
} else {
73-
if (node === parent.L) {
73+
if (after === parent.L) {
7474
d3_geom_voronoiRedBlackRotateRight(this, parent);
75-
node = parent;
76-
parent = node.U;
75+
after = parent;
76+
parent = after.U;
7777
}
7878
parent.C = false;
7979
grandpa.C = true;
8080
d3_geom_voronoiRedBlackRotateLeft(this, grandpa);
8181
}
8282
}
83-
parent = node.U;
83+
parent = after.U;
8484
}
8585
this._.C = false;
8686
},
@@ -95,7 +95,7 @@ d3_geom_voronoiRedBlackTree.prototype = {
9595
left = node.L,
9696
right = node.R,
9797
next,
98-
isRed;
98+
red;
9999

100100
if (!left) next = right;
101101
else if (!right) next = left;
@@ -109,7 +109,7 @@ d3_geom_voronoiRedBlackTree.prototype = {
109109
}
110110

111111
if (left && right) {
112-
isRed = next.C;
112+
red = next.C;
113113
next.C = node.C;
114114
next.L = left;
115115
left.U = next;
@@ -126,12 +126,12 @@ d3_geom_voronoiRedBlackTree.prototype = {
126126
node = next.R;
127127
}
128128
} else {
129-
isRed = node.C;
129+
red = node.C;
130130
node = next;
131131
}
132132

133133
if (node) node.U = parent;
134-
if (isRed) return;
134+
if (red) return;
135135
if (node && node.C) { node.C = false; return; }
136136

137137
do {
@@ -185,6 +185,7 @@ d3_geom_voronoiRedBlackTree.prototype = {
185185
node = parent;
186186
parent = parent.U;
187187
} while (!node.C);
188+
188189
if (node) node.C = false;
189190
}
190191

0 commit comments

Comments
 (0)