E_BOOL_TYPE Insert2List(PT_NODE ptHeadNode, char* tagName, char* content)
{
    PT_NODE ptNode = NULL;
    PT_NODE ptFirst = NULL;
   
    ptNode = (PT_NODE) malloc(sizeof(T_NODE));
    if ( ptNode == NULL )
    {
        return FAIL;
    }
   
    ptNode->tagName = (char*)dupstr(tagName);
       if ( !ptNode->tagName )
       {
           FreeNode(&ptNode);
           return FAIL;
    }

    ptNode->content = (char*)dupstr(content);
       if ( !ptNode->content )
       {
           FreeNode(&ptNode);
           return FAIL;
    }
   
    ptFirst = ptHeadNode->next;
    ptHeadNode->next = ptNode;
    ptNode->next = ptFirst;
    
    return SUCCESS;
}

/*
**    FreeNode() recursively frees a given node.
*/
void    FreeNode(node *n) {
	if (n->type != TGEN && n->type != TNUM) {
		FreeNode(n->cont.op.l);
		FreeNode(n->cont.op.r);
	}
	Free(n);
}

NODE * Mul( NODE *n1, NODE *n2 )
{
  if( n1 == 0 ) return n2;
  if( n2 == 0 ) return n1;
  
  if( IsConst( n1, 1 ) ) { 
    n2->sign *= n1->sign;
    FreeNode( n1 );
    return n2;   
  }
  if( IsConst( n2, 1 ) ) {
    n2->sign *= n1->sign;
    FreeNode( n2 );
    return n1;
  }
  if( IsConst( n1, 0 ) ) { 
    FreeNode( n2 );
    return n1;   
  }
  if( IsConst( n2, 0 ) ) {
    FreeNode( n1 );
    return n2;
  }
  
  return BinaryOp( MUL, n1, n2 );                                  
}

/**
 * 算法2.21
 */
Status MergeList(LinkList &La, LinkList &Lb, LinkList &Lc, 
				int (*compare)(ElemType, ElemType))
{
	Link ha, hb, pa, pb, q;
	ElemType a, b;
	if (!InitList(Lc))
		return ERROR;
	ha = GetHead(La);
	hb = GetHead(Lb);
	pa = NextPos(La, ha);
	pb = NextPos(Lb, hb);
	while (pa && pb) {
		a = GetCurElem(pa);
		b = GetCurElem(pb);
		if (compare(a, b) <= 0) {   // a<=b
			DelFirst(ha, q);
			Append(Lc, q);
			pa = NextPos(La, ha);
		} else {    // a>b
			DelFirst(hb, q);
			Append(Lc, q);
			pb = NextPos(Lb, hb);
		}   
	} // while
	if (pa)
		Append(Lc, pa);
	else
		Append(Lc, pb);
	FreeNode(ha);
	FreeNode(hb);
	return OK;
}

void RmSubst( NODE *n )
{
NODE *pn;
NODE *cn;

  pn = 0;
  cn = substList;
  while( cn != 0 ) {
    if( NodeCmp( n, cn ) ) 
      break;
    pn = cn;
    cn = cn->left;
  }
  if( cn == 0 ) return;

  FreeNode( cn->right );
  if( pn )
    pn->left = cn->left;
  else 
    substList = cn->left;  
  
  cn->right = 0;
  cn->left = 0;
  FreeNode( cn );
}

	//************************************************
	//	删除一个节点，可以被派生类重载
	//***********************************************
	virtual void DeleteItem(HSTREEITEM hItem)
	{
		HSTREENODE hsNode= (HSTREENODE)hItem;
		DUIASSERT(hsNode);
		if(hsNode==STVN_ROOT)
		{
			FreeNode(STVN_ROOT);
			m_hRootFirst=NULL;
			m_hRootLast=NULL;
			return;
		}
		STREENODE nodeCopy=*hsNode;
		BOOL bRootFirst=hsNode==m_hRootFirst;
		BOOL bRootLast=hsNode==m_hRootLast;
		FreeNode(hsNode);

		if(nodeCopy.hPrevSibling)//has prevsibling
			nodeCopy.hPrevSibling->hNextSibling=nodeCopy.hNextSibling;
		else if(nodeCopy.hParent)//parent's first child
			nodeCopy.hParent->hChildFirst=nodeCopy.hNextSibling;
		if(nodeCopy.hNextSibling)// update next sibling's previous sibling
			nodeCopy.hNextSibling->hPrevSibling=nodeCopy.hPrevSibling;
		else if(nodeCopy.hParent)//parent's last child
			nodeCopy.hParent->hChildLast=nodeCopy.hPrevSibling;
		//update root item
		if(bRootFirst)	m_hRootFirst=nodeCopy.hNextSibling;
		if(bRootLast)   m_hRootLast=nodeCopy.hPrevSibling;
	}

void SortPolyn(polynomail *p) {
	Link *p1, *p2;						//采用直接插入排序
	for (p1 = p->head->next; p1; p1 = p1->next) {
		for (p2 = p->head->next; p2 != p1; p2 = p2->next) {
			if (p2->data->expn == p1->data->expn) {	//若后边待排序的节点的指数跟前面已排序
				Link *pri;						//节点的指数相同，则应该合并两项，即删除后者，并入前者
				p2->data->coef += p1->data->coef;
				pri = PriorPos(*p, p1);
				DelFirst(pri, &p1);
				FreeNode(p1);
				--p->len;
				if (fabs(p2->data->coef) < 1e-6) {	//如果合并后系数为0，那也要把这个节点删除
					pri = PriorPos(*p, p2);
					DelFirst(pri, &p2);
					FreeNode(p2);
					--p->len;
				}
				p1 = pri;
				break;
			}
			else if (p1->data->expn < p2->data->expn) {
				Link *pri1, *pri2;
				pri1 = PriorPos(*p, p1);
				DelFirst(pri1, &p1);
				pri2 = PriorPos(*p, p2);
				InsFirst(pri2, p1);
				p1 = pri1;
				break;
			}
		}
	}
	p->tail = GetLast(*p);
}

/* Get the identity-based hash value for an object reference at *v. This may
   cause the object to move, thus updating *v. */
AValue AGetIdHashValue(AThread *t, AValue *v)
{
    void *p = AValueToPtr(*v);
    HashMappingTable *table;
    AValue hash;

    if (AIsInNursery(p))
        table = &NewGenTable;
    else
        table = &OldGenTable;

    ALockHashMappings();
    hash = GetHashMapping(table, p);
    if (AIsError(hash)) {
        /* Could not find a mapping -- insert a new hash mapping. */

        int i;
        HashValueNode *n;

        /* Allocate a new hash node. Note that this may cause the object to be
           moved, but we'll handle that case later. */
        n = AllocNode(p);
        if (n == NULL) {
            /* Out of memory. */
            AUnlockHashMappings();
            return ARaiseMemoryErrorND(t);
        }

        /* Check if it is time to grow the hash table. This may cause the
           object to be moved. */
        if (table->num > table->size) {
            if (!GrowHashTable(table)) {
                /* Out of memory. */
                FreeNode(n);
                AUnlockHashMappings();
                return ARaiseMemoryErrorND(t);
            }
        }

        /* If the target value moved to the old generation, try again. */
        if (p != AValueToPtr(*v)) {
            FreeNode(n);
            AUnlockHashMappings();
            return AGetIdHashValue(t, v);
        }

        /* Calculate hash value for the internal hash table. */
        i = PtrHashValue(p) & (table->size - 1);

        /* Initialize the new table entry. */
        n->next = table->table[i];
        table->num++;
        table->table[i] = n;
        hash = n->hashValue;
    }
    AUnlockHashMappings();

    return hash;
}

void FreeNode( NODE * n )
{
  if( n == 0 ) return;
  FreeNode( n->left );
  FreeNode( n->right );
  if( n->elm ) free( n->elm );
  free( n );
}

void b2DynamicTree::RemoveLeaf(int32 leaf)
{
	if (leaf == m_root)
	{
		m_root = b2_nullNode;
		return;
	}

	int32 parent = m_nodes[leaf].parent;
	int32 grandParent = m_nodes[parent].parent;
	int32 sibling;
	if (m_nodes[parent].child1 == leaf)
	{
		sibling = m_nodes[parent].child2;
	}
	else
	{
		sibling = m_nodes[parent].child1;
	}

	if (grandParent != b2_nullNode)
	{
		// Destroy parent and connect sibling to grandParent.
		if (m_nodes[grandParent].child1 == parent)
		{
			m_nodes[grandParent].child1 = sibling;
		}
		else
		{
			m_nodes[grandParent].child2 = sibling;
		}
		m_nodes[sibling].parent = grandParent;
		FreeNode(parent);

		// Adjust ancestor bounds.
		int32 index = grandParent;
		while (index != b2_nullNode)
		{
			index = Balance(index);

			int32 child1 = m_nodes[index].child1;
			int32 child2 = m_nodes[index].child2;

			m_nodes[index].aabb.Combine(m_nodes[child1].aabb, m_nodes[child2].aabb);
			m_nodes[index].height = 1 + b2Max(m_nodes[child1].height, m_nodes[child2].height);

			index = m_nodes[index].parent;
		}
	}
	else
	{
		m_root = sibling;
		m_nodes[sibling].parent = b2_nullNode;
		FreeNode(parent);
	}

	//Validate();
}

void b2DynamicTree::RemoveLeaf(int32 leaf)
{
	if (leaf == m_root)
	{
		m_root = b2_nullNode;
		return;
	}

	int32 node2 = m_nodes[leaf].parent;
	int32 node1 = m_nodes[node2].parent;
	int32 sibling;
	if (m_nodes[node2].child1 == leaf)
	{
		sibling = m_nodes[node2].child2;
	}
	else
	{
		sibling = m_nodes[node2].child1;
	}

	if (node1 != b2_nullNode)
	{
		// Destroy node2 and connect node1 to sibling.
		if (m_nodes[node1].child1 == node2)
		{
			m_nodes[node1].child1 = sibling;
		}
		else
		{
			m_nodes[node1].child2 = sibling;
		}
		m_nodes[sibling].parent = node1;
		FreeNode(node2);

		// Adjust ancestor bounds.
		while (node1 != b2_nullNode)
		{
			b2AABB oldAABB = m_nodes[node1].aabb;
			m_nodes[node1].aabb.Combine(m_nodes[m_nodes[node1].child1].aabb, m_nodes[m_nodes[node1].child2].aabb);

			if (oldAABB.Contains(m_nodes[node1].aabb))
			{
				break;
			}

			node1 = m_nodes[node1].parent;
		}
	}
	else
	{
		m_root = sibling;
		m_nodes[sibling].parent = b2_nullNode;
		FreeNode(node2);
	}
}

/**
 *  Read multiplexer information from the .xml transistor characteristics.
 *  This contains the estimates of mux output voltages, depending on 1) Mux Size 2) Mux Vin
 *  */
static void power_tech_xml_load_multiplexer_info(ezxml_t parent) {
	ezxml_t child, prev, gc;
	int num_mux_sizes;
	int i, j;

	/* Process all multiplexer sizes */
	num_mux_sizes = CountChildren(parent, "multiplexer", 1);

	/* Add entries for 0 and 1, for convenience, although
	 * they will never be used
	 */
	g_power_tech->max_mux_sl_size = 1 + num_mux_sizes;
	g_power_tech->mux_voltage_inf = (t_power_mux_volt_inf*) my_calloc(
			g_power_tech->max_mux_sl_size + 1, sizeof(t_power_mux_volt_inf));

	child = FindFirstElement(parent, "multiplexer", TRUE);
	i = 1;
	while (child) {
		int num_voltages;

		assert(i == GetFloatProperty(child, "size", TRUE, 0));

		/* For each mux size, process all of the Vin levels */
		num_voltages = CountChildren(child, "voltages", 1);

		g_power_tech->mux_voltage_inf[i].num_voltage_pairs = num_voltages;
		g_power_tech->mux_voltage_inf[i].mux_voltage_pairs =
				(t_power_mux_volt_pair*) my_calloc(num_voltages,
						sizeof(t_power_mux_volt_pair));

		gc = FindFirstElement(child, "voltages", TRUE);
		j = 0;
		while (gc) {
			/* For each mux size, and Vin level, get the min/max V_out */
			g_power_tech->mux_voltage_inf[i].mux_voltage_pairs[j].v_in =
					GetFloatProperty(gc, "in", TRUE, 0.0);
			g_power_tech->mux_voltage_inf[i].mux_voltage_pairs[j].v_out_min =
					GetFloatProperty(gc, "out_min", TRUE, 0.0);
			g_power_tech->mux_voltage_inf[i].mux_voltage_pairs[j].v_out_max =
					GetFloatProperty(gc, "out_max", TRUE, 0.0);

			prev = gc;
			gc = gc->next;
			FreeNode(prev);
			j++;
		}

		prev = child;
		child = child->next;
		FreeNode(prev);
		i++;
	}
}

void palProfiler::FreeNode(palProfilerNode* node) {
  if (node->child) {
    palProfilerNode* sibling_node = node->child->sibling;
    while (sibling_node != NULL) {
      palProfilerNode* next = sibling_node->sibling;
      FreeNode(sibling_node);
      sibling_node = next;
    }
    FreeNode(node->child);
  }
  if (node != &root_) {
    _profile_proxy_allocator->Destruct(node);
  }
}

void MkSubst( NODE *n1, NODE *n2 )
{
NODE *n;

  n = LookUpSubst( n1 );
  if( n == 0 ) {
    n = n1;
    n->left = substList;
    substList = n;
  } else {
    FreeNode( n->right );
    FreeNode( n1 );
  }
  n->right = n2;
}

NODE * Sub( NODE *n1, NODE *n2 )
{
  if( n1 == 0 ) return BinaryOp( SUB, 0, n2 );
  if( n2 == 0 ) return n1;
  
  if( IsConst( n1, 0 ) ) {
    FreeNode( n1 );
    return  BinaryOp( SUB, 0, n2 );   
  }
  if( IsConst( n2, 0 ) ) {
    FreeNode( n2 );
    return n1;
  }
  return BinaryOp( SUB, n1, n2 );                                  
}

NODE * Add( NODE *n1, NODE *n2 )
{
  if( n1 == 0 ) return n2;
  if( n2 == 0 ) return n1;
  
  if( IsConst( n1, 0 ) ) {
    FreeNode( n1 );
    return n2;   
  }
  if( IsConst( n2, 0 ) ) {
    FreeNode( n2 );
    return n1;
  }
  return BinaryOp( ADD, n1, n2 );                                  
}

//删除树节点,到此时的树节点，最多只有一个孩子,而且是左孩子
void DeleteTreeNode(TreePtr tree,TreeNodePtr node)
{
	TreeNodePtr brother = NULL;
	TreeNodePtr child = NULL;
	TreeNodePtr parent = NULL;

	parent = node->parent;
	child = (NULL == node->left) ? node->right : node->left;
	//child = node->left;

	//没有父节点和子女节点,是唯一一个节点,case 1
	if ((NULL == child) && (NULL == parent))
	{
		SetRootNode(tree,NULL);
	}
	else if ((NULL != child) && (NULL == parent))
	{
		//只有一个孩子节点,没有父节点,case 2
		SetRootNode(tree,child);
	}
	else if ((NULL == child) && (NULL != parent))
	{
		//没有孩子节点,有父节点
		if (node == parent->left)
		{
			SetLeftChild(parent,NULL);//child = NULL
		}
		else
		{
			SetRightChild(parent,NULL);//child = NULL
		}
		/*
		if (BlackNode == node->color)
		{
		DeleteNodeFix(tree,node);
		}
		*/
	}
	else
	{
		//有孩子节点,有父节点
		if (node == parent->left)
		{
			SetLeftChild(parent,child);//child = NULL
		}
		else
		{
			SetRightChild(parent,child);//child = NULL
		}
		//N=B但是P=R,C=R时，需要将孩子节点设置为黑色
		child->color = BlackNode;
		if (BlackNode == node->color)
		{
			//这个节点已经代替了node的位置
			DeleteNodeFix(tree,child);
		}
	}

	FreeNode(tree,node);
}

void H2_3D_Tree::FreeNode(nodeT *A) {
	int i;
	
    // Free all child nodes first
	for (i=0;i<8;i++) {
		if (A->leaves[i] != NULL) {
			FreeNode(A->leaves[i]);
		}
	}
	
    // Free the arrays for the field and source values
	if (A->fieldval != NULL)
        free(A->fieldval), A->fieldval=NULL;
	if (A->sourceval != NULL)
        free(A->sourceval), A->sourceval=NULL;
	if (A->proxysval != NULL)
        free(A->proxysval), A->proxysval=NULL;
	if (A->sourcefre != NULL)
	    free(A->sourcefre), A->sourcefre=NULL;
    // Free the field and source lists
	if (A->fieldlist != NULL)
        free(A->fieldlist), A->fieldlist=NULL;
	if (A->sourcelist != NULL)
        free(A->sourcelist), A->sourcelist=NULL;
	
    // Last free the node
	free(A);
}

/**
 *  {{{ 删除列表 
 */
int DeleteNode(Link to_delete)
{
	Link curr, prev;
	int i;

	if (Head == NULL) 
		return 0;
	
	for (prev = NULL, curr = Head; curr != NULL && (i = NodeCmp(to_delete, curr)) > 0; prev = curr, curr = curr->Next) {
		// empty loop	
	}

	if (curr != NULL && i == 0) {
		if (prev) {
			prev->Next = curr->Next;	
		} else {
			Head = curr->Next;	
		}

		FreeNode(curr);
		NodeCount -= 1;
		return 1;
	}

	return 0;
}

bool CudaAllocBuckets::Free(void* p) {
	AddressMap::iterator it = _addressMap.find(p);
	if(it == _addressMap.end()) {
		// If the pointer was not found in the address map, cudaFree it anyways
		// but return false.
		if(p) cudaFree(p);
		return false;
	}

	// Because we're freeing a page, it had better not be in the priority queue.
	MemList::iterator memIt = it->second;
	assert(memIt->priority == _priorityMap.end());

	// Always free allocations larger than the largest bucket
	if(NumBuckets == memIt->bucket)
		FreeNode(memIt);
	else {
		it->second->priority = _priorityMap.insert(
			std::make_pair(_counter++ - memIt->bucket, memIt));

		// Freed nodes are moved to the front, committed nodes are moved to the
		// end.
		MemList& list = _memLists[memIt->bucket];
		list.splice(list.begin(), list, memIt);
		_committed -= BucketSizes[memIt->bucket];
	}
	Compact(0);
	return true;
}