Omnetpp

以太网仿真算法

  19.36%  471.omnetpp  471.omnetpp        [.] cMessageHeap::shiftup(int)                                                                                             ◆
   7.22%  471.omnetpp  471.omnetpp        [.] _int_malloc                                                                                                            ▒
   5.15%  471.omnetpp  471.omnetpp        [.] cMessageHeap::insert(cMessage*)                                                                                        ▒
   4.44%  471.omnetpp  471.omnetpp        [.] cObject::setOwner(cObject*)       

 h = new cMessage *[size+1];

void cMessageHeap::shiftup(int from)
{
    int i = from;
    while ((j=2*i) <= n)  // n是堆中元素总数
    {
        // 1. 选择左右子节点中较小的一个
        if (j<n && (*h[j] > *h[j+1]))   // 如果右子节点存在且比左子节点小
            j++;                         // j指向较小的子节点

        // 2. 如果当前节点大于子节点中的较小者，则交换
        if (*h[i] > *h[j])  
        {
            // 交换节点
            temp = h[j];
            (h[j]=h[i])->heapindex=j;
            (h[i]=temp)->heapindex=i;
            i = j;  // 继续向下检查
        }
        else
            break;  // 堆性质已满足，退出
    }
}

h是指针数组

关键点说明：

• 数据结构:
• h是一个指针数组，存储cMessage对象的指针
• 使用1-based索引（h[0]不使用）
• 对于节点i，其左子节点为2i，右子节点为2i+1
• 比较操作:
• 通过重载的operator>进行消息比较
• 比较优先级：到达时间(arrivalTime) > 优先级(priority) > 插入顺序(insertOrder)
• 堆的维护:
• 函数名shiftup实际上执行的是"下沉"操作（有些地方也叫sift-down或heapify）
• 从给定节点开始，不断与子节点比较并交换，直到满足堆的性质

应该是指针预取器有效，在好的预取器上效果不错，目前的MPKI=7，已经不错了