data.cc

功能较全面的反汇编器：反汇编器ht-2.0.15.tar.gz

void BinaryTree::load(ObjectStream &s)
{
	const void *m = getAtomValue(GETX_INT32(s, "comparator"));
	if (!m) throw MsgException("BinaryTree::load(): invalid comparator!");
	compare = (Comparator)m;

	GET_INT32D(s, ecount);
	root = NULL;
	own_objects = true;
	if (ecount) {
		GET_INT32X(s, hom_objid);
		loadR(s, &root, 0, ecount-1);
	} else {
		hom_objid = OBJID_TEMP;
	}
}

ObjectID BinaryTree::getObjectID() const
{
	return OBJID_BINARY_TREE;
}

void BinaryTree::storeR(ObjectStream &s, BinTreeNode *n) const
{
	if (!n) return;
	storeR(s, n->left);

	s.putObject(n->key, "element", hom_objid);

	storeR(s, n->right);
}

void	BinaryTree::store(ObjectStream &s) const
{
	int aId = getAtomId((void*)compare);
	if (!aId) throw MsgException("BinaryTree::store() : comparator not registered!");
	putIDComment(s, aId);
	PUTX_INT32X(s, aId, "comparator");

	PUT_INT32D(s, ecount);
	if (ecount) {
		assert(hom_objid != OBJID_TEMP);
		putIDComment(s, hom_objid);
		PUT_INT32X(s, hom_objid);
		storeR(s, root);
	}
}

uint BinaryTree::count() const
{
	return ecount;
}

int BinaryTree::compareObjects(const Object *a, const Object *b) const
{
	return compare(a, b);
}

ObjHandle BinaryTree::find(const Object *key) const
{
	return findNode(root, key);
}

ObjHandle BinaryTree::findG(const Object *key) const
{
	return findNodeG(root, key);
}

ObjHandle BinaryTree::findGE(const Object *key) const
{
	return findNodeGE(root, key);
}

ObjHandle BinaryTree::findL(const Object *key) const
{
	return findNodeL(root, key);
}

ObjHandle BinaryTree::findLE(const Object *key) const
{
	return findNodeLE(root, key);
}

Object *BinaryTree::get(ObjHandle h) const
{
	BinTreeNode *n = handleToNative(h);
	return validHandle(h) ? n->key : NULL;
}

uint BinaryTree::getObjIdx(ObjHandle h) const
{
	// FIXME: implement it
	throw NotImplementedException(HERE);
}

ObjHandle BinaryTree::findByIdx(int i) const
{
	return findByIdxR(root, i);
}

ObjHandle BinaryTree::findFirst() const
{
	return nativeToHandle(getLeftmost(root));
}

ObjHandle BinaryTree::findLast() const
{
	return nativeToHandle(getRightmost(root));
}

ObjHandle BinaryTree::findNext(ObjHandle h) const
{
	if (!validHandle(h)) return findFirst();
	BinTreeNode *n = handleToNative(h);
	if (n->right) return nativeToHandle(getLeftmost(n->right));
	BinTreeNode *x = root, *result = NULL;
	while (x) {
		int c = compareObjects(x->key, n->key);
		if (c > 0) {
			result = x;
			x = x->left;
		} else {
			x = x->right;
		}
	}
	return nativeToHandle(result);
}

ObjHandle BinaryTree::findPrev(ObjHandle h) const
{
	if (!validHandle(h)) return findLast();
	BinTreeNode *n = handleToNative(h);
	if (n->left) return nativeToHandle(getRightmost(n->left));
	BinTreeNode *x = root, *result = NULL;
	while (x) {
		int c = compareObjects(x->key, n->key);
		if (c < 0) {
			result = x;
			x = x->right;
		} else {
			x = x->left;
		}
	}
	return nativeToHandle(result);
}

bool BinaryTree::del(ObjHandle h)
{
	if (!validHandle(h)) return false;
	BinTreeNode *n = handleToNative(h);
	Object *obj = n->key;
	bool r = remove(h);
	freeObj(obj);
	return r;
}

// SB: ich haette gerne noch ein findOrInsert (besserer Name noetig),
//     das entweder einfuegt oder - wenns das schon gibt -
//     das ObjHandle zurueckgibt (bzw immer das objHandle zurueckgibt)
// SW: interface + naive implementierung in Container sind da
ObjHandle BinaryTree::insert(Object *obj)
{
	return insertR(root, obj);
}

ObjHandle BinaryTree::insertR(BinTreeNode *&node, Object *obj)
{
	if (!node) {
		node = allocNode();
		node->key = obj;
		node->left = NULL;
		node->right = NULL;
		ecount++;
		notifyInsertOrSet(obj);
		return nativeToHandle(node);
	}
	int c = compareObjects(obj, node->key);
	if (c > 0) {
		return insertR(node->right, obj);
	} else if (c < 0) {
		return insertR(node->left, obj);
	} else return invObjHandle;
}

Object *BinaryTree::remove(ObjHandle h)
{
	if (!validHandle(h)) return NULL;
	/* n is the node, whose key has to be removed */
	BinTreeNode *n = handleToNative(h);
	/* d is node that is to be removed - not necessarily n. */
	BinTreeNode *d;

	Object *o = n->key;
	if (n->left && n->right) {
		/* p is pointer to left/right inside Parent(d) with: *p = d */
		BinTreeNode **p = getLeftmostPtr(&n->right);
		d = *p;
		*p = (*p)->right;
	} else if (n->left || n->right) {
		d = n->left ? n->left : n->right;
		n->left = d->left;
		n->right = d->right;
	} else {
		// SB: hier wuerde ein remove(Object *o) mit integriertem find()
		//     auch (etwas) schneller sein, da man kein findNodePtr mehr braucht
		// SW: interface ist da: remove(Object *o)
		BinTreeNode **p = findNodePtr(&root, n->key);
		d = *p;
		*p = NULL;
	}

	n->key = d->key;
	deleteNode(d);
	ecount--;
	return o;
}

void BinaryTree::setNodeIdentity(BinTreeNode *node, BinTreeNode *newident)
{
	node->key = newident->key;
}

/*
 *	AVLTree
 */
AVLTree::AVLTree(bool aOwnObjects, Comparator aComparator)
 : BinaryTree(aOwnObjects, aComparator)
{

}

void debugOutNode(FILE *f, BinTreeNode *n, BinTreeNode *p)
{
	if (n) {
		char b[1024];
		ht_snprintf(b, sizeof b, "node: { title: \"%y\" label: \"%y (%d)\" }\n", n->key, n->key, n->unbalance);
		fputs(b, f);
		if (p) {
			ht_snprintf(b, sizeof b, "edge: { sourcename: \"%y\" targetname: \"%y\" }\n", p->key, n->key);
			fputs(b, f);
		}
		debugOutNode(f, n->right, n);
		debugOutNode(f, n->left, n);
	}
}

void AVLTree::debugOut()
{
	FILE *f = fopen("test.vcg", "wb");
	fputs("graph: {\nlayoutalgorithm: tree\n", f);
	debugOutNode(f, root, NULL);
	fputs("}\n", f);
	fclose(f);
}

bool AVLTree__expensiveCheck(BinTreeNode *n, int &height)
{
	if (n) {
		int left, right;
		if (!AVLTree__expensiveCheck(n->left, left)) return false;
		if (!AVLTree__expensiveCheck(n->right, right)) return false;
		height = MAX(left, right)+1;
		if (left < right) {
			return n->unbalance == 1;
		} else if (left > right) {
			return n->unbalance == -1;
		} else {
			return n->unbalance == 0;
		}
	} else {
		height = 0;
		return true;
	}
}

bool AVLTree::expensiveCheck() const
{
	int dummy;
	return AVLTree__expensiveCheck(root, dummy);
}

void AVLTree::cloneR(BinTreeNode *node)
{
	if (!node) return;
	Object *o = own_objects ? node->key->clone() : node->key;
	// SB: nicht gut: (unnoetige compares)
	insert(o);

	cloneR(node->left);
	cloneR(node->right);
}

AVLTree *AVLTree::clone() const
{
	AVLTree *c = new AVLTree(own_objects, compare);
	c->cloneR(root);
	return c;
}

int AVLTree::loadR(ObjectStream &s, BinTreeNode *&n, int l, int r)
{
	if (l > r) {
		n = NULL;
		return 0;
	}
	n = allocNode();
	uint m = (l+r)/2;

	int L = loadR(s, n->left, l, m-1);

	n->key = s.getObject("element", hom_objid);

	int R = loadR(s, n->right, m+1, r);

	if (L < R) {
		n->unbalance = +1;
	} else if (L > R) {
		n->unbalance = -1;
	} else {
		n->unbalance = 0;
	}
	return MAX(L, R)+1;
}

void AVLTree::load(ObjectStream &s)
{
	const void *m = getAtomValue(GETX_INT32X(s, "comparator"));
	if (!m) throw MsgException("AVLTree::load(): invalid 'comparator'!");
	compare = (Comparator)m;

	GET_INT32D(s, ecount);
	root = NULL;
	own_objects = true;
	if (ecount) {
		GET_INT32X(s, hom_objid);
		loadR(s, root, 0, ecount-1);
	} else {
		hom_objid = OBJID_TEMP;
	}
}

ObjectID AVLTree::getObjectID() const
{
	return OBJID_AVL_TREE;
}

ObjHandle AVLTree::insert(Object *obj)
{
	/* t will point to the node where rebalancing may be necessary */
	BinTreeNode **t = &root;
	/* *pp will walk through the tree */
	BinTreeNode **pp = &root;
	// Search
	while (*pp) {
		int c = compareObjects(obj, (*pp)->key);
		if (c < 0) {
			pp = &(*pp)->left;
		} else if (c > 0) {
			pp = &(*pp)->right;
		} else {
			// element found
			return invObjHandle;
		}
		if (*pp && (*pp)->unbalance) {
			t = pp;
		}
	}

	/* s points to the node where rebalancing may be necessary */
	BinTreeNode *s = *t;

	// Insert
	*pp = allocNode();
	BinTreeNode *retval = *pp;
	retval->key = obj;
	retval->left = retval->right = NULL;
	retval->unbalance = 0;
	ecount++;
	notifyInsertOrSet(obj);
	if (!s) return nativeToHandle(retval);

	// Rebalance
	int a;
	BinTreeNode *r;
	BinTreeNode *p;
	if (compareObjects(obj, s->key) < 0) {
		a = -1;
		r = p = s->left;
	} else {
		a = 1;
		r = p = s->right;
	}
	while (p != retval) {
		if (compareObjects(obj, p->key) < 0) {
			p->unbalance = -1;
			p = p->left;
		} else {
			p->unbalance = 1;
			p = p->right;
		}
	}
	if (!s->unbalance) {
		// tree was balanced before insertion
		s->unbalance = a;
	} else if (s->unbalance == -a) {
		// tree has become more balanced
		s->unbalance = 0;
	} else {
		// tree is out of balance
		if (r->unbalance == a) {
			// single rotation
			p = r;
			if (a < 0) {
				s->left = r->right;
				r->right = s;
			} else {
				s->right = r->left;
				r->left = s;
			}
			s->unbalance = r->unbalance = 0;
		} else {
			// double rotation
			if (a < 0) {
				p = r->right;
				r->right = p->left;
				p->left = r;
				s->left = p->right;
				p->right = s;
			} else {
				p = r->left;
				r->left = p->right;
				p->right = r;
				s->right = p->left;
				p->left = s;
			}
			s->unbalance = (p->unbalance == a) ? -a : 0;
			r->unbalance = (p->unbalance == -a) ? a : 0;
			p->unbalance = 0;
		}
		// finalization
		*t = p;
	}
	assert(root);
	return nativeToHandle(retval);
}

BinTreeNode *AVLTree::removeR(Object *key, BinTreeNode *&node, int &change, int cmp)
{
	if (node == NULL) {
		change = 0;
		return NULL;
	}

	BinTreeNode *found = NULL;
	int decrease = 0;

	int result;
	if (!cmp) {
		result = compareObjects(key, node->key);
		if (result < 0) {
			result = -1;
		} else if (result > 0) {
			result = 1;
		}
	} else if (cmp < 0) {
		result = (node->left == NULL) ? 0 : -1;
	} else {
		result = (node->right == NULL) ? 0 : 1;
	}

	if (result) {
		found = removeR(key, (result < 0) ? node->left : node->right, change, cmp);
		if (!found) return NULL;
		decrease = result * change;
	} else {
		found = node;

		/*
		 *	Same logic as in BinaryTree::remove()
		 */
		if (!node->left && !node->right) {
			node = NULL;
			change = 1;
			return found;
		} else if (!node->left || !node->right) {
			node = node->right ? node->right : node->left;
			change = 1;
			return found;
		} else {
			BinTreeNode *n = removeR(key, node->right, decrease, -1);
			setNodeIdentity(node, n);
			found = n;
		}
	}

	node->unbalance -= decrease;

	if (decrease) {
		if (node->unbalance) {
			change = 0;
			int a;
			BinTreeNode *r = NULL;
			if (node->unbalance < -1) {
				a = -1;
				r = node->left;
			} else if (node->unbalance > 1) {
				a = 1;
				r = node->right;
			} else {
				a = 0;
			}
			if (a) {
				/*
				 *	If r->unbalance == 0 do also a single rotation.
				 *	This case cant occure with insert operations.
				 */
				if (r->unbalance == -a) {
					/*
					 *	double rotation.
					 *	See insert
					 */
					BinTreeNode *p;
					if (a > 0) {
						p = r->left;
						r->left = p->right;
						p->right = r;
						node->right = p->left;
						p->left = node;
					} else {
						p = r->right;
						r->right = p->left;
						p->left = r;
						node->left = p->right;
						p->right = node;
					}
					node->unbalance = (p->unbalance == a) ? -a: 0;
					r->unbalance = (p->unbalance == -a) ? a: 0;
					p->unbalance = 0;
					node = p;
					change = 1;
				} else {
					/*
					 *	single rotation
					 *	Height of tree changes if r is/was unbalanced
					 */
					change = r->unbalance?1:0;
					if (a > 0) {
						node->right = r->left;
						r->left = node;
						r->unbalance--;
					} else {
						node->left = r->right;
						r->right = node;
						r->unbalance++;
					}
					node->unbalance = - r->unbalance;
					node = r;
				}
			}
		} else {
			/*
			 *	Tree has become more balanced
			 */
			change = 1;
		}
	} else {
		change = 0;
	}

	return found;
}

Object *AVLTree::remove(ObjHandle h)
{
	if (!validHandle(h)) return NULL;
	BinTreeNode *n = handleToNative(h);
	Object *o = n->key;
	int change;
	BinTreeNode *node = removeR(n->key, root, change, 0);
	if (node) {
		deleteNode(node);
		ecount--;
		return o;
	}
	return NULL;
}

/**
 *	A MRU Cache
 */
MRUCache::MRUCache(bool own_objects, Comparator comparator)
: AVLTree(own_objects, comparator)
{
	mostRU = leastRU = NULL;
}

MRUCacheNode *MRUCache::allocNode() const
{
	MRUCacheNode *a = new MRUCacheNode();
//	((MRUCacheNode*)a)->lessRU = (MRUCacheNode*)0xfffff789;
//	((MRUCacheNode*)a)->moreRU = (MRUCacheNode*)0xfffff888;
	return a;
}

MRUCache *MRUCache::clone() const
{
	throw NotImplementedException(HERE);
}

void MRUCache::delAll()
{
	AVLTree::delAll();
	mostRU = leastRU = NULL;
}

void MRUCache::deleteNode(BinTreeNode *node) const
{
//	((MRUCacheNode*)node)->lessRU = (MRUCacheNode*)0xdeadf0cc;
//	((MRUCacheNode*)node)->moreRU = (MRUCacheNode*)0xdeadf0c2;
	delete node;
}

ObjHandle MRUCache::insert(Object *obj)
{
//	checkList();
	uint count0 = count();
	ObjHandle h = AVLTree::insert(obj);
//	DPRINTF("mru_insert: %08x\n", (int)h);
	if (count0 != count()) {
		// make mostRU in MRU list
		MRUCacheNode *n = handleToNative(h);
		n->moreRU = NULL;
		n->lessRU = mostRU;
		if (mostRU == NULL) {
			mostRU = leastRU = n;
		} else {
			mostRU->moreRU = n;
			mostRU = n;
		}
//		checkList();
	}
	return h;
}

Object *MRUCache::remove(ObjHandle h)
{
/*	static int debug_rc = 0;
	++debug_rc;
	DPRINTF("mru_remove(%d): %08x\n", debug_rc, (int)h);
	if (debug_rc == 19) {
		int sdf=32;
	}
	checkList();*/
	if (h != invObjHandle) {
		MRUCacheNode *n = handleToNative(h);
		// remove from MRU list
		if (n == mostRU) {
			if (n == leastRU) {
//				DPRINTF("   --> removing leastRU entry --> empty list\n");
				mostRU = NULL;
				leastRU = NULL;
			} else {
//				DPRINTF("   --> removing mostRU entry\n");
				mostRU = n->lessRU;
				mostRU->moreRU = NULL;
			}
		} else if (n == leastRU) {
//			DPRINTF("   --> removing leastRU entry\n");
//			DPRINTF("       mostRU was: %08x, leastRU was: %08x\n", mostRU, leastRU);
			leastRU = n->moreRU;
			leastRU->lessRU = NULL;
//			DPRINTF("       mostRU is now: %08x, leastRU is now: %08x\n", mostRU, leastRU);
//			DPRINTF("       mostRU->moreRU: %08x\n", mostRU->moreRU);
		} else {
//			DPRINTF("   --> removing entry\n");
			n->moreRU->lessRU = n->lessRU;
			n->lessRU->moreRU = n->moreRU;
		}
	}
//	checkList();
	Object *o = AVLTree::remove(h);
	if ((h != invObjHandle) && (o == NULL)) assert(0);
//	checkList();
	return o;
}

void MRUCache::setNodeIdentity(BinTreeNode *node, BinTreeNode *newident)
{
	MRUCacheNode *_node = (MRUCacheNode *)node;
	MRUCacheNode *_newident = (MRUCacheNode *)newident;
	_node->key = _newident->key;
	_node->moreRU = _newident->moreRU;
	_node->lessRU = _newident->lessRU;
	if (_newident->moreRU) {
		_newident->moreRU->lessRU = _node;
	} else {
		mostRU = _node;
	}
	if (_newident->lessRU) {
		_newident->lessRU->moreRU = _node;
	} else {