system_wrappers/source/list_unittest.cc

/*
 *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
 *
 *  Use of this source code is governed by a BSD-style license
 *  that can be found in the LICENSE file in the root of the source
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */

#include "gtest/gtest.h"

#include "system_wrappers/interface/list_wrapper.h"
#include "system_wrappers/interface/scoped_ptr.h"

using ::webrtc::ListWrapper;
using ::webrtc::ListItem;
using ::webrtc::scoped_ptr;

// Note: kNumberOfElements needs to be even.
const unsigned int kNumberOfElements = 10;

// An opaque implementation of dynamic or statically allocated unsigned ints.
// This class makes it possible to use the exact same code for testing of both
// the dynamic and static implementation of ListWrapper.
// Clarification: ListWrapper has two versions of PushBack(..). It takes an
// unsigned integer or a void pointer. The integer implementation takes care
// of memory management. The void pointer version expect the caller to manage
// the memory associated with the void pointer.
// This class works like the integer version but can be implemented on top of
// either the integer version or void pointer version of ListWrapper.
// Note: the non-virtual fuctions behave the same for both versions.
class ListWrapperSimple {
public:
    static ListWrapperSimple* Create(bool static_allocation);
    virtual ~ListWrapperSimple() {}

    // These three functions should be used for manipulating ListItems so that
    // they are the type corresponding to the underlying implementation.
    virtual unsigned int GetUnsignedItem(
        const ListItem* item) const = 0;
    virtual ListItem* CreateListItem(unsigned int item_id) = 0;
    unsigned int GetSize() const {
        return list_.GetSize();
    }
    virtual int PushBack(const unsigned int item_id) = 0;
    virtual int PushFront(const unsigned int item_id) = 0;
    virtual int PopFront() = 0;
    virtual int PopBack() = 0;
    bool Empty() const {
        return list_.Empty();
    }
    ListItem* First() const {
        return list_.First();
    }
    ListItem* Last() const {
        return list_.Last();
    }
    ListItem* Next(ListItem* item) const {
        return list_.Next(item);
    }
    ListItem* Previous(ListItem* item) const {
        return list_.Previous(item);
    }
    virtual int Erase(ListItem* item) = 0;
    int Insert(ListItem* existing_previous_item,
               ListItem* new_item) {
        const int retval = list_.Insert(existing_previous_item, new_item);
        if (retval != 0) {
            EXPECT_TRUE(DestroyListItem(new_item));
        }
        return retval;
    }

    int InsertBefore(ListItem* existing_next_item,
                     ListItem* new_item) {
        const int retval = list_.InsertBefore(existing_next_item, new_item);
        if (retval != 0) {
            EXPECT_TRUE(DestroyListItem(new_item));
        }
        return retval;
    }
protected:
    ListWrapperSimple() {}

    virtual bool DestroyListItemContent(ListItem* item) = 0;
    bool DestroyListItem(ListItem* item) {
        const bool retval = DestroyListItemContent(item);
        delete item;
        return retval;
    }

    ListWrapper list_;
};

void ClearList(ListWrapperSimple* list_wrapper) {
  if (list_wrapper == NULL) {
      return;
  }
  ListItem* list_item = list_wrapper->First();
  while (list_item != NULL) {
    EXPECT_EQ(list_wrapper->Erase(list_item), 0);
    list_item = list_wrapper->First();
  }
}

class ListWrapperStatic : public ListWrapperSimple {
public:
    ListWrapperStatic() {}
    virtual ~ListWrapperStatic() {
        ClearList(this);
    }

    virtual unsigned int GetUnsignedItem(const ListItem* item) const {
        return item->GetUnsignedItem();
    }
    virtual ListItem* CreateListItem(unsigned int item_id) {
        return new ListItem(item_id);
    }
    virtual bool DestroyListItemContent(ListItem* item) {
        return true;
    }
    virtual int PushBack(const unsigned int item_id) {
        return list_.PushBack(item_id);
    }
    virtual int PushFront(const unsigned int item_id) {
        return list_.PushFront(item_id);
    }
    virtual int PopFront() {
        return list_.PopFront();
    }
    virtual int PopBack() {
        return list_.PopBack();
    }
    virtual int Erase(ListItem* item) {
        return list_.Erase(item);
    }
};

class ListWrapperDynamic : public ListWrapperSimple {
public:
    ListWrapperDynamic() {}
    virtual ~ListWrapperDynamic() {
        ClearList(this);
    }

    virtual unsigned int GetUnsignedItem(const ListItem* item) const {
        const unsigned int* return_value_pointer =
            reinterpret_cast<unsigned int*> (item->GetItem());
        if (return_value_pointer == NULL) {
            return -1;
        }
        return *return_value_pointer;
    }
    virtual ListItem* CreateListItem(unsigned int item_id) {
        unsigned int* item_id_pointer = new unsigned int;
        if (item_id_pointer == NULL) {
            return NULL;
        }
        *item_id_pointer = item_id;
        ListItem* return_value = new ListItem(
            reinterpret_cast<void*>(item_id_pointer));
        if (return_value == NULL) {
            delete item_id_pointer;
            return NULL;
        }
        return return_value;
    }
    virtual bool DestroyListItemContent(ListItem* item) {
        if (item == NULL) {
            return false;
        }
        bool return_value = false;
        unsigned int* item_id_ptr = reinterpret_cast<unsigned int*>(
            item->GetItem());
        if (item_id_ptr != NULL) {
            return_value = true;
            delete item_id_ptr;
        }
        return return_value;
    }
    virtual int PushBack(const unsigned int item_id) {
        unsigned int* item_id_ptr = new unsigned int;
        if (item_id_ptr == NULL) {
            return -1;
        }
        *item_id_ptr = item_id;
        const int return_value = list_.PushBack(
            reinterpret_cast<void*>(item_id_ptr));
        if (return_value != 0) {
            delete item_id_ptr;
        }
        return return_value;
    }
    virtual int PushFront(const unsigned int item_id) {
        unsigned int* item_id_ptr = new unsigned int;
        if (item_id_ptr == NULL) {
            return -1;
        }
        *item_id_ptr = item_id;
        const int return_value = list_.PushFront(
            reinterpret_cast<void*>(item_id_ptr));
        if (return_value != 0) {
            delete item_id_ptr;
        }
        return return_value;
    }
    virtual int PopFront() {
        return Erase(list_.First());
    }
    virtual int PopBack() {
        return Erase(list_.Last());
    }
    virtual int Erase(ListItem* item) {
        if (item == NULL) {
            return -1;
        }
        int retval = 0;
        if (!DestroyListItemContent(item)) {
            retval = -1;
            ADD_FAILURE();
        }
        if (list_.Erase(item) != 0) {
            retval = -1;
        }
        return retval;
    }
};

ListWrapperSimple* ListWrapperSimple::Create(bool static_allocation) {
    if(static_allocation)
    {
        return new ListWrapperStatic();
    }
    return new ListWrapperDynamic();
}

ListWrapperSimple* CreateAscendingList(bool static_allocation) {
    ListWrapperSimple* return_value = ListWrapperSimple::Create(
        static_allocation);
    if (return_value == NULL) {
        return NULL;
    }
    for (unsigned int i = 0; i < kNumberOfElements; ++i) {
        if (return_value->PushBack(i) == -1) {
            ClearList(return_value);
            delete return_value;
            return NULL;
        }
    }
    return return_value;
}

ListWrapperSimple* CreateDescendingList(bool static_allocation) {
    ListWrapperSimple* return_value = ListWrapperSimple::Create(
        static_allocation);
    if (return_value == NULL) {
        return NULL;
    }
    for (unsigned int i = 0; i < kNumberOfElements; ++i) {
        if (return_value->PushBack(kNumberOfElements - i - 1) == -1) {
            ClearList(return_value);
            delete return_value;
            return NULL;
        }
    }
    return return_value;
}

// [0,kNumberOfElements - 1,1,kNumberOfElements - 2,...] (this is why
// kNumberOfElements need to be even)
ListWrapperSimple* CreateInterleavedList(bool static_allocation) {
    ListWrapperSimple* return_value = ListWrapperSimple::Create(
        static_allocation);
    if (return_value == NULL) {
        return NULL;
    }
    unsigned int uneven_count = 0;
    unsigned int even_count = 0;
    for (unsigned int i = 0; i < kNumberOfElements; i++) {
        unsigned int push_value = 0;
        if ((i % 2) == 0) {
            push_value = even_count;
            even_count++;
        } else {
            push_value = kNumberOfElements - uneven_count - 1;
            uneven_count++;
        }
        if (return_value->PushBack(push_value) == -1) {
            ClearList(return_value);
            delete return_value;
            return NULL;
        }
    }
    return return_value;
}

void PrintList(const ListWrapperSimple* list) {
    ListItem* list_item = list->First();
    printf("[");
    while (list_item != NULL)
    {
        printf("%3u", list->GetUnsignedItem(list_item));
        list_item = list->Next(list_item);
    }
    printf("]\n");
}

bool CompareLists(const ListWrapperSimple* lhs, const ListWrapperSimple* rhs) {
    const unsigned int list_size = lhs->GetSize();
    if (lhs->GetSize() != rhs->GetSize()) {
        return false;
    }
    if (lhs->Empty()) {
        return rhs->Empty();
    }
    unsigned int i = 0;
    ListItem* lhs_item = lhs->First();
    ListItem* rhs_item = rhs->First();
    while (i < list_size) {
        if (lhs_item == NULL) {
            return false;
        }
        if (rhs_item == NULL) {
            return false;
        }
        if (lhs->GetUnsignedItem(lhs_item) != rhs->GetUnsignedItem(rhs_item)) {
            return false;
        }
        i++;
        lhs_item = lhs->Next(lhs_item);
        rhs_item = rhs->Next(rhs_item);
    }
    return true;
}

TEST(ListWrapperTest,ReverseNewIntList) {
    // Create a new temporary list with elements reversed those of
    // new_int_list_
    const scoped_ptr<ListWrapperSimple> descending_list(
        CreateDescendingList(rand()%2));
    ASSERT_FALSE(descending_list.get() == NULL);
    ASSERT_FALSE(descending_list->Empty());
    ASSERT_EQ(kNumberOfElements,descending_list->GetSize());

    const scoped_ptr<ListWrapperSimple> ascending_list(
        CreateAscendingList(rand()%2));
    ASSERT_FALSE(ascending_list.get() == NULL);
    ASSERT_FALSE(ascending_list->Empty());
    ASSERT_EQ(kNumberOfElements,ascending_list->GetSize());

    scoped_ptr<ListWrapperSimple> list_to_reverse(
        ListWrapperSimple::Create(rand()%2));

    // Reverse the list using PushBack and Previous.
    for (ListItem* item = ascending_list->Last(); item != NULL;
         item = ascending_list->Previous(item)) {
         list_to_reverse->PushBack(ascending_list->GetUnsignedItem(item));
    }

    ASSERT_TRUE(CompareLists(descending_list.get(), list_to_reverse.get()));

    scoped_ptr<ListWrapperSimple> list_to_un_reverse(
        ListWrapperSimple::Create(rand()%2));
    ASSERT_FALSE(list_to_un_reverse.get() == NULL);
    // Reverse the reversed list using PushFront and Next.
    for (ListItem* item = list_to_reverse->First(); item != NULL;
         item = list_to_reverse->Next(item)) {
         list_to_un_reverse->PushFront(list_to_reverse->GetUnsignedItem(item));
    }
    ASSERT_TRUE(CompareLists(ascending_list.get(), list_to_un_reverse.get()));
}

TEST(ListWrapperTest,PopTest) {
    scoped_ptr<ListWrapperSimple> ascending_list(CreateAscendingList(rand()%2));
    ASSERT_FALSE(ascending_list.get() == NULL);
    ASSERT_FALSE(ascending_list->Empty());
    EXPECT_EQ(0, ascending_list->PopFront());
    EXPECT_EQ(1U, ascending_list->GetUnsignedItem(ascending_list->First()));

    EXPECT_EQ(0, ascending_list->PopBack());
    EXPECT_EQ(kNumberOfElements - 2, ascending_list->GetUnsignedItem(
              ascending_list->Last()));
    EXPECT_EQ(kNumberOfElements - 2, ascending_list->GetSize());
}

// Use Insert to interleave two lists.
TEST(ListWrapperTest,InterLeaveTest) {
    scoped_ptr<ListWrapperSimple> interleave_list(
        CreateAscendingList(rand()%2));
    ASSERT_FALSE(interleave_list.get() == NULL);
    ASSERT_FALSE(interleave_list->Empty());

    scoped_ptr<ListWrapperSimple> descending_list(
        CreateDescendingList(rand()%2));
    ASSERT_FALSE(descending_list.get() == NULL);

    for (unsigned int i = 0; i < kNumberOfElements/2; ++i) {
        ASSERT_EQ(0, interleave_list->PopBack());
        ASSERT_EQ(0, descending_list->PopBack());
    }
    ASSERT_EQ(kNumberOfElements/2, interleave_list->GetSize());
    ASSERT_EQ(kNumberOfElements/2, descending_list->GetSize());

    unsigned int insert_position = kNumberOfElements/2;
    ASSERT_EQ(insert_position * 2, kNumberOfElements);
    while (!descending_list->Empty())
    {
        ListItem* item = descending_list->Last();
        ASSERT_FALSE(item == NULL);

        const unsigned int item_id = descending_list->GetUnsignedItem(item);
        ASSERT_EQ(0, descending_list->Erase(item));

        ListItem* insert_item = interleave_list->CreateListItem(item_id);
        ASSERT_FALSE(insert_item == NULL);
        item = interleave_list->First();
        ASSERT_FALSE(item == NULL);
        for (unsigned int j = 0; j < insert_position - 1; ++j) {
            item = interleave_list->Next(item);
            ASSERT_FALSE(item == NULL);
        }
        EXPECT_EQ(0, interleave_list->Insert(item, insert_item));
        --insert_position;
    }

    scoped_ptr<ListWrapperSimple> interleaved_list(
        CreateInterleavedList(rand()%2));
    ASSERT_FALSE(interleaved_list.get() == NULL);
    ASSERT_FALSE(interleaved_list->Empty());
    ASSERT_TRUE(CompareLists(interleaved_list.get(), interleave_list.get()));
}

// Use InsertBefore to interleave two lists.
TEST(ListWrapperTest,InterLeaveTestII) {
    scoped_ptr<ListWrapperSimple> interleave_list(
        CreateDescendingList(rand()%2));
    ASSERT_FALSE(interleave_list.get() == NULL);
    ASSERT_FALSE(interleave_list->Empty());

    scoped_ptr<ListWrapperSimple> ascending_list(CreateAscendingList(rand()%2));
    ASSERT_FALSE(ascending_list.get() == NULL);

    for (unsigned int i = 0; i < kNumberOfElements/2; ++i) {
        ASSERT_EQ(0, interleave_list->PopBack());
        ASSERT_EQ(0, ascending_list->PopBack());
    }
    ASSERT_EQ(kNumberOfElements/2, interleave_list->GetSize());
    ASSERT_EQ(kNumberOfElements/2, ascending_list->GetSize());

    unsigned int insert_position = kNumberOfElements/2;
    ASSERT_EQ(insert_position * 2, kNumberOfElements);
    while (!ascending_list->Empty())
    {
        ListItem* item = ascending_list->Last();
        ASSERT_FALSE(item == NULL);

        const unsigned int item_id = ascending_list->GetUnsignedItem(item);
        ASSERT_EQ(0,ascending_list->Erase(item));

        ListItem* insert_item = interleave_list->CreateListItem(item_id);
        ASSERT_FALSE(insert_item == NULL);
        item = interleave_list->First();
        ASSERT_FALSE(item == NULL);
        for (unsigned int j = 0; j < insert_position - 1; ++j) {
            item = interleave_list->Next(item);
            ASSERT_FALSE(item == NULL);
        }
        EXPECT_EQ(interleave_list->InsertBefore(item, insert_item), 0);
        --insert_position;
    }

    scoped_ptr<ListWrapperSimple> interleaved_list(
        CreateInterleavedList(rand()%2));
    ASSERT_FALSE(interleaved_list.get() == NULL);
    ASSERT_FALSE(interleaved_list->Empty());

    ASSERT_TRUE(CompareLists(interleaved_list.get(), interleave_list.get()));
}