res_list.hh

来自「M5,一个功能强大的多处理器系统模拟器.很多针对处理器架构,性能的研究都使用它作」· HH 代码 · 共 759 行 · 第 1/2 页

        }
        else {
            //  if we don't allocate storage, then we just want to
            //  point to the specified object
            p.point_to(d);
        }
    }

    return p;
}


template <class T>
inline typename res_list<T>::iterator
res_list<T>::insert_after(iterator prev)
{

#if DEBUG_MEMORY
    if (active_elements > 2*base_elements) {
        what_the();
    }
#endif

    //  If we have no unused elements, make some more
    if (unused_elements.isnull()) {

        if (build_size == 0) {
            return 0;   // No space left, and can't allocate more....
        }

        extra_elements += allocate_elements(build_size, allocate_storage);
    }

    //  grab the first unused element
    res_element *p = unused_elements.res_el_ptr();

    unused_elements = unused_elements.next();

    ++active_elements;

    //  Insert the new element
    if (head_ptr.isnull()) {
        //
        //  Special case #1: Empty List
        //
        head_ptr = p;
        tail_ptr = p;
        p->prev = 0;
        p->next = 0;
    }
    else if (prev.isnull()) {
        //
        //  Special case #2: Insert at head
        //

        // our next ptr points to old head element
        p->next = head_ptr.res_el_ptr();

        // our element becomes the new head element
        head_ptr = p;

        // no previous element for the head
        p->prev = 0;

        // old head element points back to this element
        p->next->prev = p;
    }
    else if (prev.next().isnull()) {
        //
        //  Special case #3 Insert at tail
        //

        // our prev pointer points to old tail element
        p->prev = tail_ptr.res_el_ptr();

        // our element becomes the new tail
        tail_ptr = p;

        // no next element for the tail
        p->next = 0;

        // old tail element point to this element
        p->prev->next = p;
    }
    else {
        //
        //  Normal insertion (after prev)
        //
        p->prev = prev.res_el_ptr();
        p->next = prev.next().res_el_ptr();

        prev.res_el_ptr()->next = p;
        p->next->prev = p;
    }

    return iterator(p);
}

template <class T>
inline typename res_list<T>::iterator
res_list<T>::insert_before(iterator next, T &d)
{
    iterator p;

    p = insert_before(next);
    if (p.notnull()) {

        if (allocate_storage) {
            //  if we allocate storage, then copy the contents of the
            //  specified object to our object
            *p = d;
        }
        else {
            //  if we don't allocate storage, then we just want to
            //  point to the specified object
            p.point_to(d);
        }
    }

    return p;
}


template <class T>
inline typename res_list<T>::iterator
res_list<T>::insert_before(iterator next)
{

#if DEBUG_MEMORY
    if (active_elements > 2*base_elements) {
        what_the();
    }
#endif

    //  If we have no unused elements, make some more
    if (unused_elements.isnull()) {

        if (build_size == 0) {
            return 0;   // No space left, and can't allocate more....
        }

        extra_elements += allocate_elements(build_size, allocate_storage);
    }

    //  grab the first unused element
    res_element *p = unused_elements.res_el_ptr();

    unused_elements = unused_elements.next();

    ++active_elements;

    //  Insert the new element
    if (head_ptr.isnull()) {
        //
        //  Special case #1: Empty List
        //
        head_ptr = p;
        tail_ptr = p;
        p->prev = 0;
        p->next = 0;
    }
    else if (next.isnull()) {
        //
        //  Special case #2 Insert at tail
        //

        // our prev pointer points to old tail element
        p->prev = tail_ptr.res_el_ptr();

        // our element becomes the new tail
        tail_ptr = p;

        // no next element for the tail
        p->next = 0;

        // old tail element point to this element
        p->prev->next = p;
    }
    else if (next.prev().isnull()) {
        //
        //  Special case #3: Insert at head
        //

        // our next ptr points to old head element
        p->next = head_ptr.res_el_ptr();

        // our element becomes the new head element
        head_ptr = p;

        // no previous element for the head
        p->prev = 0;

        // old head element points back to this element
        p->next->prev = p;
    }
    else {
        //
        //  Normal insertion (before next)
        //
        p->next = next.res_el_ptr();
        p->prev = next.prev().res_el_ptr();

        next.res_el_ptr()->prev = p;
        p->prev->next = p;
    }

    return iterator(p);
}


template <class T>
inline typename res_list<T>::iterator
res_list<T>::remove(iterator q)
{
    res_element *p = q.res_el_ptr();
    iterator n = 0;

    //  Handle the special cases
    if (active_elements == 1) {    // This is the only element
        head_ptr = 0;
        tail_ptr = 0;
    }
    else if (q == head_ptr) {      // This is the head element
        head_ptr = q.next();
        head_ptr.res_el_ptr()->prev = 0;

        n = head_ptr;
    }
    else if (q == tail_ptr) {      // This is the tail element
        tail_ptr = q.prev();
        tail_ptr.res_el_ptr()->next = 0;
    }
    else {                         // This is between two elements
        p->prev->next = p->next;
        p->next->prev = p->prev;

        // Get the "next" element for return
        n = p->next;
    }

    --active_elements;

    //  Put this element back onto the unused list
    p->next = unused_elements.res_el_ptr();
    p->prev = 0;
    if (p->next) {           // NULL if unused list is empty
        p->next->prev = p;
    }

    if (!allocate_storage) {
        p->data = 0;
    }

    unused_elements = q;

    //  A little "garbage collection"
    if (++remove_count > 10) {
        //	    free_extras();
        remove_count = 0;
    }

#if DEBUG_REMOVE
    unsigned unused_count = 0;
    for (iterator i=unused_elements;
         i.notnull();
         i = i.next()) {

        ++unused_count;
    }

    assert((active_elements+unused_count) == (base_elements+extra_elements));
#endif

    return iterator(n);
}


template <class T>
inline bool
res_list<T>::in_list(iterator j)
{
    iterator i;

    for (i=head(); i.notnull(); i=i.next()) {
        if (j.res_el_ptr() == i.res_el_ptr()) {
            return true;
        }
    }

    return false;
}

template <class T>
inline void
res_list<T>::free_extras(void)
{
    unsigned num_unused = base_elements + extra_elements - active_elements;
    unsigned to_free = extra_elements;
    res_element *p;


    if (extra_elements != 0) {
        //
        //  Free min(extra_elements, # unused elements)
        //
        if (extra_elements > num_unused) {
            to_free = num_unused;
        }

        p = unused_elements.res_el_ptr();
        for (int i=0; i<to_free; ++i) {
            res_element *q = p->next;

            delete p;

            p = q;
        }

        //  update the unused element pointer to point to the first
        //  element that wasn't deleted.
        unused_elements = iterator(p);

        //  Update the number of extra elements
        extra_elements -= to_free;
    }

    return;
}


template <class T>
inline void
res_list<T>::clear(void)
{
    iterator i,n;

    for (i=head_ptr; i.notnull(); i=n) {
        n = i.next();
        remove(i);
    }

    free_extras();
}

template <class T>
inline void
res_list<T>::dump(void)
{
    for (iterator i=head(); !i.isnull(); i=i.next())
        i->dump();
}

template <class T>
inline void
res_list<T>::raw_dump(void)
{
    int j = 0;
    res_element *p;
    for (iterator i=head(); !i.isnull(); i=i.next()) {
        cprintf("Element %d:\n", j);

        if (i.notnull()) {
            p = i.res_el_ptr();
            cprintf("  points to res_element @ %#x\n", p);
            p->dump();
            cprintf("  Data Element:\n");
            i->dump();
        }
        else {
            cprintf("  NULL iterator!\n");
        }

        ++j;
    }

}

#endif // __RES_LIST_HH__