android/android-emu/android/base/containers/TailQueueList.h

// Copyright 2014 The Android Open Source Project
//
// This software is licensed under the terms of the GNU General Public
// License version 2, as published by the Free Software Foundation, and
// may be copied, distributed, and modified under those terms.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

#pragma once

#include "android/base/Compiler.h"
#include "android/base/Log.h"

#include <stddef.h>

namespace android {
namespace base {

// Convenience classes and macros to define generic tail-queue lists.
//
// Generally speaking, these lists perform poorly on modern CPUs since their
// use can introduce cache trashing at runtime. However, they're still
// efficient if one wants to quickly and often remove liberal items from
// the list in an O(1) way.
//
// Usage example:
//
//   1/ The type of each item in the list must have a TailQueueLink<T> field,
//      called the 'link',  which is used by the implementation to store
//      opaque queue-related fields. For example:
//
//      struct Foo {
//          Foo() { ... }
//          TailQueueLink<Foo> mLink;
//      }
//
//   2/ The type must also have a public Traits structure that provides
//      a single function named link() used to return the address of a
//      link. One way to define it is to use the macro:
//
//          TAIL_QUEUE_LIST_TRAITS(Traits, Foo, mLink);
//
//      which defines the |Traits| structure that returns the address of
//      Foo::mLink inside a Foo instance. If you don't want to use the
//      macro, the definition must be:
//
//          struct Traits {
//              static inline TailQueueLink<Foo>* link(Foo* foo) {
//                  return &foo->mLink;
//              }
//          };
//
//   3/ Define the tail-queue-list type with:
//
//          typedef TailQueueList<Foo> FooList;
//
//      By default, this relies on Foo::Traits being defined, it is possible
//      to give the name of a different Traits structure as a second template
//      parameter. This is useful if a single object can actually be
//      contained inside two parallel lists, as in:
//
//          class Bar {
//          public:
//              Bar() { ... }
//
//              TAIL_QUEUE_LIST_TRAITS(Traits1, Bar, mLink1);
//              TAIL_QUEUE_LIST_TRAITS(Traits2, Bar, mLink2);
//          private:
//              TailQueueLink<Bar> mLink1;
//              TailQueueLink<Bar> mLink2;
//              ...
//          };
//
//          typedef TailQueueList<Bar, Traits1>  BarList1;
//          typedef TailQueueList<Bar, Traits2>  BarList2;
//
//   4/ One can use the link's next() method to get a pointer to the next
//      item in the list, or NULL if this is the last item. For example, the
//      following can be used to remove all items from a queue if |mLink| is
//      a public field.
//
//          FooList* queue = ...;
//          Foo* foo = queue->front();
//          while (foo) {
//              Foo* next = foo->mLink.next();
//              queue->remove(foo);
//              foo = next;
//          }
//
//      If the field is private, consider adding an appropriate public
//      method in the declaration of Foo, as in:
//
//          class Foo {
//          public:
//              Foo() ...;
//              Foo* nextInList() const { return mLink.next(); }
//          private:
//              TailQueueLink<Foo> mLink;
//              ...
//          };
//
//      Then use foo->nextInList() within the loop instead of foo->mLink.next()
//

// Template class for link fields inside objects that belong to a
// tail-queue list.
template <typename T>
class TailQueueLink {
public:
    TailQueueLink() : mNext(NULL), mPrevPointer(NULL) {}

    ~TailQueueLink() {}

    T* next() const { return mNext; }

    bool inQueue() const { return !!mPrevPointer; }

    bool isLast() const { return !mNext; }

    // These fields are public to make it easier for TailQueueList<>
    // to access them.
    T* mNext;
    T** mPrevPointer;
};

// Helper template class for tail-queue list instances.
// |T| is the type of objects that can be added to the list.
// |TRAITS| is the type of a structure that provides a single
// method that is:
//
//    static TailQueueLink<T>* link(T* t) const;
//
// Do not use this class directly, use the DECLARE_TAIL_QUEUE_LIST_CLASS
// macro instead, as defined below.
//
// Note that the implementation relies on the fact that the size and field
// layout of a TailQueueList<T,OFFSET> is identical to the one of a
// TailQueueListBase. This considerably reduces template instantiation
// bloat.
template <typename T, typename TRAITS = typename T::Traits>
class TailQueueList {
public:
    // Convenience typedef for link types.
    typedef TailQueueLink<T> LinkType;

    // Default constructor initializes an empty tail-queue list.
    TailQueueList() : mHead(NULL), mTail(&mHead) {}

    // Default destructor doesn't do anything.
    ~TailQueueList() {}

    // Returns truee iff the list is empty.
    bool empty() const {
        return mHead == NULL;
    }

    // Returns the address of the first item in the list, or NULL if it
    // is empty. This does not modify the list.
    T* front() const {
        return mHead;
    }

    // Returns the address of the last item in the list, or NULL if it
    // is empty. This does not modify the list.
    T* last() const {
        // Technical note: mTail points to either a link inside the last
        // item, or the mHead. Derefencing the value will point to the
        // last item in the tail queue list.
        return *(reinterpret_cast<TailQueueList*>(mTail)->mTail);
    }

    // Remove the first item from the list and return it to the caller.
    // Return NULL if the list was empty.
    T* popFront() {
        T* result = front();
        if (result) {
            remove(result);
        }
        return result;
    }

    // Append a new item to the list. This is a convenience alias for
    // insertTail().
    void pushBack(T* obj) {
        insertTail(obj);
    }

    // Prepend a new object |obj| to the list. Note that |obj| cannot be
    // NULL or already in another list using the same link.
    void insertHead(T* obj) {
        LinkType* link = TRAITS::link(obj);
        DCHECK(!link->inQueue());

        link->mNext = mHead;
        if (mHead) {
            LinkType* firstLink = TRAITS::link(mHead);
            firstLink->mPrevPointer = &link->mNext;
        } else {
            mTail = &link->mNext;
        }
        mHead = obj;
        link->mPrevPointer = &mHead;
    }

    // Append a new object |obj| to the list. Note that |obj| cannot be
    // NULL or already in another list using the same link.
    void insertTail(T* obj) {
        LinkType* link = TRAITS::link(obj);
        DCHECK(!link->inQueue());

        link->mNext = NULL;
        link->mPrevPointer = mTail;
        *mTail = obj;
        mTail = &link->mNext;
    }

    // Insert a new object |obj| into the list, before object |insert|.
    // Note that |obj| and |insert| cannot be NULL, |obj| must not be in
    // another list using the same link, and |insert| must already be
    // in the list.
    void insertBefore(T* insert, T* obj) {
        LinkType* link = TRAITS::link(obj);
        DCHECK(!link->inQueue());

        LinkType* insertLink = TRAITS::link(insert);
        DCHECK(insertLink->inQueue());

        link->mPrevPointer = insertLink->mPrevPointer;
        link->mNext = insert;
        *insertLink->mPrevPointer = obj;
        insertLink->mPrevPointer = &link->mNext;
    }

    // Insert a new object |obj| into the list, after object |insert|.
    // Note that |obj| and |insert| cannot be NULL, |obj| must not be in
    // another list using the same link, and |insert| must already be
    // in the list.
    void insertAfter(T* insert, T* obj) {
        LinkType* link = TRAITS::link(obj);
        DCHECK(!link->inQueue());

        LinkType* insertLink = TRAITS::link(insert);
        DCHECK(insertLink->inQueue());

        link->mNext = insertLink->mNext;
        if (link->mNext) {
            LinkType* nextLink = TRAITS::link(link->mNext);
            nextLink->mPrevPointer = &link->mNext;
        } else {
            mTail = &link->mNext;
        }
        insertLink->mNext = obj;
        link->mPrevPointer = &insertLink->mNext;
    }

    // Remove object |obj| from the list. |obj| cannot be NULL and must
    // be in the list.
    void remove(T* obj) {
        LinkType* link = TRAITS::link(obj);
        DCHECK(link->inQueue());

        if (link->mNext) {
            LinkType* nextLink = TRAITS::link(link->mNext);
            nextLink->mPrevPointer = link->mPrevPointer;
        } else {
            mTail = link->mPrevPointer;
        }
        *link->mPrevPointer = link->mNext;

        link->mNext = NULL;
        link->mPrevPointer = NULL;
    }

    // Return the number of objects in this list. WARNING: O(n) performance.
    size_t size() const {
        size_t count = 0;
        T* item = mHead;
        while (item) {
            count += 1;
            item = TRAITS::link(item)->mNext;
        }
        return count;
    }

    // Return true iff the list contains object |obj|.
    // WARNING: O(n) performance.
    bool contains(T* obj) const {
        T* item = mHead;
        while (item) {
            if (item == obj) {
                return true;
            }
            item = TRAITS::link(item)->mNext;
        }
        return false;
    }

    // Return the n-th item in the list, where |pos| is its position,
    // starting from 0. Return NULL if the position is out of bounds.
    // WARNING: O(n) performance.
    T* nth(size_t pos) const {
        T* item = mHead;
        while (item && pos > 0) {
            pos--;
            item = TRAITS::link(item)->mNext;
        }
        return item;
    }

private:
    DISALLOW_COPY_AND_ASSIGN(TailQueueList);

    // The layout of these fields should match TailQueueListBase exactly.
    T* mHead;
    T** mTail;
};

#define TAIL_QUEUE_LIST_TRAITS(traits_name, type_name, field_name) \
    struct traits_name { \
        static inline ::android::base::TailQueueLink<type_name>* \
                link(type_name* t) { \
            return &(t)->field_name; \
        } \
    }

}  // namespace base
}  // namespace android