作者ric2k1 (Ric)
看板EE_DSnP
标题Re: [讨论] BddNode and BddNodeInt
时间Mon Jan 8 22:22:47 2007
※ 引述《samuelduan ()》之铭言：
: 不好意思 我也想问一些很基本的问题...>"<
没问题!!
: ※ 引述《ric2k1 (Ric)》之铭言：
: : 9. All the operations on BddNodeInt* need to go through BddNode ---
: : * In the BddNode constructor, we increase the reference count of the
: : BddNode::_node. So if a BddNode variable is declared, the reference
: : count of its associated BddNodeInt* will be incremented by 1.
: : * In the BddNode descructor, we decrease the reference count of the
: : BddNode::_node. So if the program goes out of the scope of a certain
: : BddNode variable, the reference count of its BddNodeInt* will be
: : decremented by 1.
: : * In the BddNode assignment '=' operator, for example, f = g, we first
: : decrease the reference count of "f._node", and then increase the
: : reference count of "g._node". Of course, we will asssign
: : "f._node = g._node"
: Q1: 我对 f = g 的领会是 f node 指向(还是应该说是连到?) g node
: 可以了解 g 的ref count要加1
: 但是为何 f 的ref count也要减1呢
: f 本来的架构应该不会改变不是吗?
f, g are BddNodes. 把他们想成是 BddNodeInt* 的壳子...
f = g 的意思是将 g 的内容 copy 到 f 去,
所以原来 g 所包的 BddNodeInt* 就会有多一个 "人" (i.e. 'f') 包着他,
所以他的 reference count 要加一,
但是原来 f 所包的 BddNodeInt* 呢? 他被新的 BddNodeInt* 所取代,
所以他就少了一个 "人" 包着他, 所以他的 reference count 要减一.
: : 13. So we will take the advanatage of the fact that the pointer addresses are
: : multiplier of 4, and we can use the lowest two bits to record the edge
: : information. We use the lowest 1 bit to record the INVERSION.
: : 14. To use the lower bits of a pointer variable, we need to conver it to a
: : size_t variable, such as:
: : v = size_t(n);
: : and then the edge information can be added to it by v = v + 1.
: : 15. Combining the above, we redefine the classes BddNode and BddNodeInt as...
: : class BddNode {
: : size_t _nodeV; // to hold BddNodeInt* and 1-bit edge info
: : };
: : class BddNodeInt {
: : BddNode _left;
: : BddNode _right;
: : unsigned _level : 16;
: : unsigned _refCount : 15;
: : unsigned _visited : 1;
: : };
: Q2: 所以我可以把 size_t _nodeV 看成BddNodeInt* _node 有一样功能的data member
: 然後 BddNode::getBddNodeInt() 就是一个converter
可以这麽说
: 只是有点看不懂 BDD_NODE_PTR_MASK的定义
: ((UNIT_MAX >> BDD_EDGE_BITS) << BDD_EDGE_BITS 是让这个 _nodeV 变成一个合理的
: pointer address?
UINT_MAX = max unsigned integer = 32 bits of 1's
UINT_MAX >> BDD_EDGE_BITS = UINT_MAX >> 2 // right-shift 2 bits
(UINT_MAX >> BDD_EDGE_BITS) << BDD_EDGE_BITS // then left-shift 2 bits
overall, these two shifts produce "111....11100" (30 1's, 2 0's)
and when it "&" with _nodeV,
it makes the least two significant bits of _nodeV 0's. ==> the pointer address
: Q3: 在前面几篇有同学问到 BddNode::_one 和 BddNode::_zero
: 我比较疑问的是在 BddManager::init()中
: BddNode::_one = BddNode(BddNodeInt::_terminal, BDD_POS_EDGE);
: 如果这里 _terminal = 0
: 那当呼叫到 BddNode::BddNode(BddNodeInt* n, BDD_EDGE_FLAG f) 时
: 其中的 assert(n!=0) 不是会有问题吗?
_terminal 不是 0 !!!!!
_terminal has ----
_level = 0;
_left = 0;
_right = 0;
It itself is a valid BddNodeInt* !!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.121.129.139