android/android-emu/android/base/containers/TailQueueList_unittest.cpp

// 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.

#include "android/base/containers/TailQueueList.h"

#include <gtest/gtest.h>

namespace android {
namespace base {

namespace {

// Helper class used to hold an integer value, and which can be
class Foo {
public:
    Foo() : mValue(0) {}
    explicit Foo(int value) : mValue(value) {}

    int value() const { return mValue; }
    Foo* next() const { return mLink.next(); }

    TAIL_QUEUE_LIST_TRAITS(Traits, Foo, mLink);

private:
    TailQueueLink<Foo> mLink;
    int mValue;
};

typedef TailQueueList<Foo> FooList;

void clearFooList(FooList* list) {
    for (;;) {
        Foo* foo = list->popFront();
        if (!foo) {
            break;
        }
        delete foo;
    }
}

class ScopedFooList : public FooList {
public:
    ~ScopedFooList() {
        clearFooList((FooList*)this);
    }
};

}  // namespace

TEST(TailQueueList, init) {
    FooList list;
    EXPECT_TRUE(list.empty());
    EXPECT_EQ(0U, list.size());
    EXPECT_FALSE(list.contains(NULL));
}

TEST(TailQueueList, front) {
    ScopedFooList list;
    const size_t kCount = 100;

    EXPECT_FALSE(list.front());

    for (size_t n = 0; n < kCount; ++n) {
        list.pushBack(new Foo(n));
        EXPECT_TRUE(list.front()) << "Item #" << n;
        EXPECT_EQ(0U, list.front()->value()) << "Item #" << n;
    }
}

TEST(TailQueueList, last) {
    ScopedFooList list;
    const size_t kCount = 100;

    EXPECT_FALSE(list.last());

    for (size_t n = 0; n < kCount; ++n) {
        list.pushBack(new Foo(n));
        EXPECT_TRUE(list.last()) << "Item #" << n;
        EXPECT_EQ(n, list.last()->value()) << "Item #" << n;
    }
}

TEST(TailQueueList, insertTail) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.pushBack(new Foo(n));
        EXPECT_EQ(n + 1, list.size()) << "Item #" << n;
    }

    EXPECT_EQ(kCount, list.size());

    size_t n = 0;
    Foo* foo = list.front();
    for (; n < kCount && foo; n++, foo = foo->next()) {
        EXPECT_EQ(n, foo->value()) << "Item #" << n;
    }

    EXPECT_EQ(kCount, n);
    EXPECT_FALSE(foo);
}

TEST(TailQueueList, insertHead) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertHead(new Foo(n));
        EXPECT_EQ(n + 1, list.size()) << "Item #" << n;
    }

    EXPECT_EQ(kCount, list.size());

    size_t n = 0;
    Foo* foo = list.front();
    for (; n < kCount && foo; n++, foo = foo->next()) {
        EXPECT_EQ(kCount - 1 - n, foo->value()) << "Item #" << n;
    }

    EXPECT_EQ(kCount, n);
    EXPECT_FALSE(foo);
}

TEST(TailQueueList, insertBefore) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertTail(new Foo(n));
    }

    // Insert before head.
    list.insertBefore(list.front(), new Foo(kCount + 1U));
    EXPECT_EQ(kCount + 1U, list.size());

    Foo* foo = list.front();
    EXPECT_EQ(kCount + 1U, foo->value());

    // Insert before second.
    foo = foo->next();
    EXPECT_EQ(0U, foo->value()) << "Item #1";

    list.insertBefore(foo, new Foo(kCount + 2U));
    EXPECT_EQ(kCount + 2U, list.size());

    foo = list.front();
    EXPECT_EQ(kCount + 1U, foo->value());
    foo = foo->next();
    EXPECT_EQ(kCount + 2U, foo->value());
    foo = foo->next();

    for (size_t n = 0; n < kCount; ++n) {
        EXPECT_EQ(n, foo->value()) << "Item #" << (n + 2u);
        foo = foo->next();
    }
}

TEST(TailQueueList, insertAfter) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertTail(new Foo(n));
    }

    // Insert after head.
    list.insertAfter(list.front(), new Foo(kCount + 1U));
    EXPECT_EQ(kCount + 1U, list.size());

    Foo* foo = list.front();
    EXPECT_EQ(0U, foo->value());
    foo = foo->next();
    EXPECT_EQ(kCount + 1U, foo->value());
    foo = foo->next();

    for (size_t n = 1; n < kCount - 1U; ++n) {
        EXPECT_EQ(n, foo->value()) << "Item #" << (n + 2U);
        foo = foo->next();
    }

    EXPECT_EQ(kCount - 1U, foo->value()) << "Item #" << kCount - 1U;

    // Insert after last.
    list.insertAfter(foo, new Foo(kCount + 2U));
    foo = list.front();
    EXPECT_EQ(0U, foo->value());
    foo = foo->next();
    EXPECT_EQ(kCount + 1U, foo->value());
    foo = foo->next();

    for (size_t n = 1; n < kCount - 1U; ++n) {
        EXPECT_EQ(n, foo->value()) << "Item #" << (n + 1U);
        foo = foo->next();
    }

    EXPECT_EQ(kCount - 1U, foo->value());
    foo = foo->next();
    EXPECT_TRUE(foo);
    EXPECT_EQ(kCount + 2U, foo->value());
}

TEST(TailQueueList, removeLinearFromHead) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertTail(new Foo(n));
    }

    // Remove all items in order, from the head.
    Foo* foo = list.front();
    for (size_t n = 0; n < kCount; ++n) {
        Foo* next = foo->next();
        EXPECT_EQ(n, foo->value());
        list.remove(foo);
        EXPECT_EQ(kCount - n - 1, list.size());
        EXPECT_EQ(next, list.front());
        foo = next;
    }
    EXPECT_TRUE(list.empty());
    EXPECT_EQ(0U, list.size());
}

TEST(TailQueueList, removeLinearFromTail) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertTail(new Foo(n));
    }

    // Remove all items in reverse order, from the tail.
    for (size_t pos = kCount; pos > 0; --pos) {
        // Get item at position |pos - 1|
        Foo* foo = list.front();
        for (size_t n = 1; n < pos; ++n) {
            foo = foo->next();
        }
        EXPECT_TRUE(foo);
        EXPECT_EQ(pos - 1U, foo->value());
        list.remove(foo);
        EXPECT_EQ(pos - 1U, list.size());
    }
    EXPECT_TRUE(list.empty());
    EXPECT_EQ(0U, list.size());
}

TEST(TailQueueList, removeOddOnly) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertTail(new Foo(n));
    }

    Foo* foo = list.front()->next();
    for (size_t n = 0; n < kCount / 2U; ++n) {
        Foo* next = (n < kCount / 2U - 1U) ? foo->next()->next() : NULL;
        EXPECT_EQ(n * 2U + 1U, foo->value());
        list.remove(foo);
        foo = next;
    }

    EXPECT_EQ(kCount / 2U, list.size());

    foo = list.front();
    for (size_t n = 0; n < kCount / 2; ++n) {
        EXPECT_TRUE(foo);
        EXPECT_EQ(n*2U, foo->value());
        foo = foo->next();
    }
}

TEST(TailQueueList, size) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertTail(new Foo(n));
        EXPECT_EQ(n + 1U, list.size());
    }
}

TEST(TailQueueList, nth) {
    ScopedFooList list;
    const size_t kCount = 100;

    for (size_t n = 0; n < kCount; ++n) {
        list.insertTail(new Foo(n));
    }

    for (size_t n = 0; n < kCount; ++n) {
        Foo* foo = list.nth(n);
        EXPECT_TRUE(foo);
        EXPECT_EQ(n, foo->value());
    }

    EXPECT_FALSE(list.nth(kCount));
    EXPECT_FALSE(list.nth(kCount + 1U));
}

}  // namespace base
}  // namespace android