From 921e67980817b1d2517758914bc743e401142de4 Mon Sep 17 00:00:00 2001 From: John Mark Bell Date: Thu, 19 Jul 2007 23:56:22 +0000 Subject: Document implications of reference counting on DOM node destruction. svn path=/trunk/dom/; revision=3444 --- docs/RefCnt | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+) create mode 100644 docs/RefCnt (limited to 'docs') diff --git a/docs/RefCnt b/docs/RefCnt new file mode 100644 index 0000000..ba0fa08 --- /dev/null +++ b/docs/RefCnt @@ -0,0 +1,102 @@ +Reference counting +------------------ + +Overview +-------- + + DOM Nodes are reference counted, so as to ensure they are only destroyed + when nothing is using them. Each node has a reference count member + variable, which is a count of external references upon the node. Links + between nodes in the DOM tree (internal references) are not counted, as + they are implicitly available by consulting the relevant pointers. + +Destruction semantics +--------------------- + + A simplistic DOM tree might look like the following: + + Node1 + | ^ + | | + +-------------|-+---------------+ + +-|-------------+-|-------------+ | + | | | | | | + v | v | v | + Node2<--------->Node3<--------->Node4 + | ^ + | | + +-----|-+-------+ + +-|-----+-------+ | + | | | | + v | v | + Node5<--------->Node6 + + Thus, each node possesses the following links: + + a) A link to its parent + b) A link to each of its children + c) A link to the sibling immediately prior to it + d) A link to the sibling immediately after it + + None of these links are reference counted, as the reference can be + determined implicitly from the pointer value (i.e. a non-NULL pointer + implies a reference). + + A node becomes eligible for destruction when: + + a) its reference count variable equals 0 + b) its parent node pointer equals NULL + + I.E. There exist no external references upon the node and the node has + been detached from the tree. + + Note that the presence of children or siblings attached to a node has no + impact upon its eligibility for destruction, as these links are "weak". + +Destruction process +------------------- + + The node destruction process proceeds as follows: + + 1) Any children of the node are detached from it and an attempt is + made to destroy them. + 2) The node is destroyed. + + If, when attempting to destroy children of the node, a child is found + to have a non-zero reference count (i.e. an external reference is + being held upon the child), the child (and its children) is not + destroyed. The child is added to the list of nodes pending deletion + and will be destroyed once its reference count reaches zero. + +Example +------- + + This example uses the DOM tree depicted above, and a system state as + follows: + + a) A NodeList collection references Node6. There are no other active + collections. The NodeList has a reference count of 1. + b) Node2 (and its subtree) has been removed from the document and + is referenced solely by the client code that caused it to be + removed from the document. + + The client code unreferences Node2, thus reducing its reference count to + zero. It is now eligible for destruction. Destruction occurs as follows: + + 1) Node5 is detached from Node2 and an attempt is made to destroy it. + a) Node5 has no children and has a reference count of zero, so it + is destroyed. + 2) Node6 is detached from Node2 and an attempt is made to destroy it. + a) Node6's reference count is non-zero, so it is added to the list + of nodes pending deletion. + 3) Node2 has no further children, so it is destroyed. + + The client code unreferences the NodeList: + + 1) The NodeList unreferences the node it's attached to (Node6). + Node6's reference count is now zero, so it is eligible for + destruction. + a) Node6 has no children, so it is destroyed (and removed from the + list of nodes pending deletion). + 2) The NodeList is destroyed. + -- cgit v1.2.3