1/*
2 *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#include "gtest/gtest.h"
12
13#include "list_wrapper.h"
14
15using ::webrtc::ListWrapper;
16using ::webrtc::ListItem;
17
18// Note: kNumberOfElements needs to be even.
19const unsigned int kNumberOfElements = 10;
20
21// An opaque implementation of dynamic or statically allocated unsigned ints.
22// This class makes it possible to use the exact same code for testing of both
23// the dynamic and static implementation of ListWrapper.
24// Clarification: ListWrapper has two versions of PushBack(..). It takes an
25// unsigned integer or a void pointer. The integer implementation takes care
26// of memory management. The void pointer version expect the caller to manage
27// the memory associated with the void pointer.
28// This class works like the integer version but can be implemented on top of
29// either the integer version or void pointer version of ListWrapper.
30// Note: the non-virtual fuctions behave the same for both versions.
31class ListWrapperSimple {
32public:
33    static ListWrapperSimple* Create(bool static_allocation);
34    virtual ~ListWrapperSimple() {}
35
36    // These three functions should be used for manipulating ListItems so that
37    // they are the type corresponding to the underlying implementation.
38    virtual unsigned int GetUnsignedItem(
39        const ListItem* item) const = 0;
40    virtual ListItem* CreateListItem(unsigned int item_id) = 0;
41    virtual bool DestroyListItem(ListItem* item) = 0;
42
43    unsigned int GetSize() const {
44        return list_.GetSize();
45    }
46    virtual int PushBack(const unsigned int item_id) = 0;
47    virtual int PushFront(const unsigned int item_id) = 0;
48    virtual int PopFront() = 0;
49    virtual int PopBack() = 0;
50    bool Empty() const {
51        return list_.Empty();
52    }
53    ListItem* First() const {
54        return list_.First();
55    }
56    ListItem* Last() const {
57        return list_.Last();
58    }
59    ListItem* Next(ListItem* item) const {
60        return list_.Next(item);
61    }
62    ListItem* Previous(ListItem* item) const {
63        return list_.Previous(item);
64    }
65    virtual int Erase(ListItem* item) = 0;
66    int Insert(ListItem* existing_previous_item,
67                       ListItem* new_item) {
68        return list_.Insert(existing_previous_item, new_item);
69    }
70
71    int InsertBefore(ListItem* existing_next_item,
72                             ListItem* new_item) {
73        return list_.InsertBefore(existing_next_item, new_item);
74    }
75protected:
76    ListWrapperSimple() {}
77
78    ListWrapper list_;
79};
80
81class ListWrapperStatic : public ListWrapperSimple {
82public:
83    ListWrapperStatic() {}
84    virtual ~ListWrapperStatic() {}
85
86    virtual unsigned int GetUnsignedItem(const ListItem* item) const {
87        return item->GetUnsignedItem();
88    }
89    virtual ListItem* CreateListItem(unsigned int item_id) {
90        return new ListItem(item_id);
91    }
92    virtual bool DestroyListItem(ListItem* item) {
93        if (item == NULL) {
94            return false;
95        }
96        delete item;
97        return true;
98    }
99    virtual int PushBack(const unsigned int item_id) {
100        return list_.PushBack(item_id);
101    }
102    virtual int PushFront(const unsigned int item_id) {
103        return list_.PushFront(item_id);
104    }
105    virtual int PopFront() {
106        return list_.PopFront();
107    }
108    virtual int PopBack() {
109        return list_.PopBack();
110    }
111    virtual int Erase(ListItem* item) {
112        return list_.Erase(item);
113    }
114};
115
116class ListWrapperDynamic : public ListWrapperSimple {
117public:
118    ListWrapperDynamic() {}
119    virtual ~ListWrapperDynamic() {}
120
121    virtual unsigned int GetUnsignedItem(const ListItem* item) const {
122        const unsigned int* return_value_pointer =
123            reinterpret_cast<unsigned int*> (item->GetItem());
124        if (return_value_pointer == NULL) {
125            return -1;
126        }
127        return *return_value_pointer;
128    }
129    virtual ListItem* CreateListItem(unsigned int item_id) {
130        unsigned int* item_id_pointer = new unsigned int;
131        if (item_id_pointer == NULL) {
132            return NULL;
133        }
134        *item_id_pointer = item_id;
135        ListItem* return_value = new ListItem(
136            reinterpret_cast<void*>(item_id_pointer));
137        if (return_value == NULL) {
138            delete item_id_pointer;
139            return NULL;
140        }
141        return return_value;
142    }
143    virtual bool DestroyListItem(ListItem* item) {
144        if (item == NULL) {
145            return false;
146        }
147        bool return_value = false;
148        unsigned int* item_id_ptr = reinterpret_cast<unsigned int*>(
149            item->GetItem());
150        if (item_id_ptr != NULL) {
151            return_value = true;
152            delete item_id_ptr;
153        }
154        delete item;
155        return return_value;
156    }
157    virtual int PushBack(const unsigned int item_id) {
158        unsigned int* item_id_ptr = new unsigned int;
159        if (item_id_ptr == NULL) {
160            return -1;
161        }
162        *item_id_ptr = item_id;
163        const int return_value = list_.PushBack(
164            reinterpret_cast<void*>(item_id_ptr));
165        if (return_value != 0) {
166            delete item_id_ptr;
167        }
168        return return_value;
169    }
170    virtual int PushFront(const unsigned int item_id) {
171        unsigned int* item_id_ptr = new unsigned int;
172        if (item_id_ptr == NULL) {
173            return -1;
174        }
175        *item_id_ptr = item_id;
176        const int return_value = list_.PushFront(
177            reinterpret_cast<void*>(item_id_ptr));
178        if (return_value != 0) {
179            delete item_id_ptr;
180        }
181        return return_value;
182    }
183    virtual int PopFront() {
184        return Erase(list_.First());
185    }
186    virtual int PopBack() {
187        return Erase(list_.Last());
188    }
189    virtual int Erase(ListItem* item) {
190        if (item == NULL) {
191            return -1;
192        }
193        unsigned int* item_id_ptr = reinterpret_cast<unsigned int*> (
194            item->GetItem());
195        int return_value = -1;
196        if (item_id_ptr != NULL) {
197            delete item_id_ptr;
198            return_value = 0;
199        }
200        if (list_.Erase(item) != 0) {
201            return -1;
202        }
203        return return_value;
204    }
205};
206
207ListWrapperSimple* ListWrapperSimple::Create(bool static_allocation) {
208    if(static_allocation)
209    {
210        return new ListWrapperStatic();
211    }
212    return new ListWrapperDynamic();
213}
214
215void ClearList(ListWrapperSimple* list) {
216    if (list == NULL)
217    {
218        return;
219    }
220    while (list->Erase(list->First()) == 0) {
221    }
222}
223
224ListWrapperSimple* CreateAscendingList(bool static_allocation) {
225    ListWrapperSimple* return_value = ListWrapperSimple::Create(
226        static_allocation);
227    if (return_value == NULL) {
228        return NULL;
229    }
230    for (unsigned int i = 0; i < kNumberOfElements; ++i) {
231        if (return_value->PushBack(i) == -1) {
232            ClearList(return_value);
233            delete return_value;
234            return NULL;
235        }
236    }
237    return return_value;
238}
239
240ListWrapperSimple* CreateDecendingList(bool static_allocation) {
241    ListWrapperSimple* return_value = ListWrapperSimple::Create(
242        static_allocation);
243    if (return_value == NULL) {
244        return NULL;
245    }
246    for (unsigned int i = 0; i < kNumberOfElements; ++i) {
247        if (return_value->PushBack(kNumberOfElements - i - 1) == -1) {
248            ClearList(return_value);
249            delete return_value;
250            return NULL;
251        }
252    }
253    return return_value;
254}
255
256// [0,kNumberOfElements - 1,1,kNumberOfElements - 2,...] (this is why
257// kNumberOfElements need to be even)
258ListWrapperSimple* CreateInterleavedList(bool static_allocation) {
259    ListWrapperSimple* return_value = ListWrapperSimple::Create(
260        static_allocation);
261    if (return_value == NULL) {
262        return NULL;
263    }
264    unsigned int uneven_count = 0;
265    unsigned int even_count = 0;
266    for (unsigned int i = 0; i < kNumberOfElements; i++) {
267        unsigned int push_value = 0;
268        if ((i % 2) == 0) {
269            push_value = even_count;
270            even_count++;
271        } else {
272            push_value = kNumberOfElements - uneven_count - 1;
273            uneven_count++;
274        }
275        if (return_value->PushBack(push_value) == -1) {
276            ClearList(return_value);
277            delete return_value;
278            return NULL;
279        }
280    }
281    return return_value;
282}
283
284void PrintList(const ListWrapperSimple* list) {
285    ListItem* list_item = list->First();
286    printf("[");
287    while (list_item != NULL)
288    {
289        printf("%3u", list->GetUnsignedItem(list_item));
290        list_item = list->Next(list_item);
291    }
292    printf("]\n");
293}
294
295bool CompareLists(const ListWrapperSimple* lhs, const ListWrapperSimple* rhs) {
296    const unsigned int list_size = lhs->GetSize();
297    if (lhs->GetSize() != rhs->GetSize()) {
298        return false;
299    }
300    if (lhs->Empty()) {
301        return rhs->Empty();
302    }
303    unsigned int i = 0;
304    ListItem* lhs_item = lhs->First();
305    ListItem* rhs_item = rhs->First();
306    while (i < list_size) {
307        if (lhs_item == NULL) {
308            return false;
309        }
310        if (rhs_item == NULL) {
311            return false;
312        }
313        if (lhs->GetUnsignedItem(lhs_item) != rhs->GetUnsignedItem(rhs_item)) {
314            return false;
315        }
316        i++;
317        lhs_item = lhs->Next(lhs_item);
318        rhs_item = rhs->Next(rhs_item);
319    }
320    return true;
321}
322
323TEST(ListWrapperTest,ReverseNewIntList) {
324    // Create a new temporary list with elements reversed those of
325    // new_int_list_
326    const ListWrapperSimple* decending_list = CreateDecendingList(rand()%2);
327    ASSERT_FALSE(decending_list == NULL);
328    ASSERT_FALSE(decending_list->Empty());
329    ASSERT_EQ(kNumberOfElements,decending_list->GetSize());
330
331    const ListWrapperSimple* ascending_list = CreateAscendingList(rand()%2);
332    ASSERT_FALSE(ascending_list == NULL);
333    ASSERT_FALSE(ascending_list->Empty());
334    ASSERT_EQ(kNumberOfElements,ascending_list->GetSize());
335
336    ListWrapperSimple* list_to_reverse = ListWrapperSimple::Create(rand()%2);
337
338    // Reverse the list using PushBack and Previous.
339    for (ListItem* item = ascending_list->Last(); item != NULL;
340         item = ascending_list->Previous(item)) {
341         list_to_reverse->PushBack(ascending_list->GetUnsignedItem(item));
342    }
343
344    ASSERT_TRUE(CompareLists(decending_list,list_to_reverse));
345
346    ListWrapperSimple* list_to_un_reverse =
347        ListWrapperSimple::Create(rand()%2);
348    ASSERT_FALSE(list_to_un_reverse == NULL);
349    // Reverse the reversed list using PushFront and Next.
350    for (ListItem* item = list_to_reverse->First(); item != NULL;
351         item = list_to_reverse->Next(item)) {
352         list_to_un_reverse->PushFront(list_to_reverse->GetUnsignedItem(item));
353    }
354
355    ASSERT_TRUE(CompareLists(ascending_list,list_to_un_reverse));
356}
357
358TEST(ListWrapperTest,PopTest) {
359    ListWrapperSimple* ascending_list = CreateAscendingList(rand()%2);
360    ASSERT_FALSE(ascending_list == NULL);
361    ASSERT_FALSE(ascending_list->Empty());
362    EXPECT_EQ(0,ascending_list->PopFront());
363    EXPECT_EQ(1,ascending_list->GetUnsignedItem(ascending_list->First()));
364
365    EXPECT_EQ(0,ascending_list->PopBack());
366    EXPECT_EQ(kNumberOfElements - 2,ascending_list->GetUnsignedItem(
367              ascending_list->Last()));
368    EXPECT_EQ(kNumberOfElements - 2, ascending_list->GetSize());
369}
370
371// Use Insert to interleave two lists.
372TEST(ListWrapperTest,InterLeaveTest) {
373    ListWrapperSimple* interleave_list = CreateAscendingList(rand()%2);
374    ASSERT_FALSE(interleave_list == NULL);
375    ASSERT_FALSE(interleave_list->Empty());
376
377    ListWrapperSimple* decending_list = CreateDecendingList(rand()%2);
378    ASSERT_FALSE(decending_list == NULL);
379
380    for (int i = 0; i < kNumberOfElements/2; ++i) {
381        ASSERT_EQ(0,interleave_list->PopBack());
382        ASSERT_EQ(0,decending_list->PopBack());
383    }
384    ASSERT_EQ(kNumberOfElements/2,interleave_list->GetSize());
385    ASSERT_EQ(kNumberOfElements/2,decending_list->GetSize());
386
387    int insert_position = kNumberOfElements/2;
388    ASSERT_EQ(insert_position * 2, kNumberOfElements);
389    while (!decending_list->Empty())
390    {
391        ListItem* item = decending_list->Last();
392        ASSERT_FALSE(item == NULL);
393
394        const unsigned int item_id = decending_list->GetUnsignedItem(item);
395        ASSERT_EQ(0,decending_list->Erase(item));
396
397        ListItem* insert_item = interleave_list->CreateListItem(item_id);
398        ASSERT_FALSE(insert_item == NULL);
399        item = interleave_list->First();
400        ASSERT_FALSE(item == NULL);
401        for (int j = 0; j < insert_position - 1; ++j) {
402            item = interleave_list->Next(item);
403            ASSERT_FALSE(item == NULL);
404        }
405        if (0 != interleave_list->Insert(item,insert_item)) {
406            interleave_list->DestroyListItem(insert_item);
407            FAIL();
408        }
409        --insert_position;
410    }
411
412    ListWrapperSimple* interleaved_list = CreateInterleavedList(rand()%2);
413    ASSERT_FALSE(interleaved_list == NULL);
414    ASSERT_FALSE(interleaved_list->Empty());
415
416    ASSERT_TRUE(CompareLists(interleaved_list,interleave_list));
417}
418
419// Use InsertBefore to interleave two lists.
420TEST(ListWrapperTest,InterLeaveTestII) {
421    ListWrapperSimple* interleave_list = CreateDecendingList(rand()%2);
422    ASSERT_FALSE(interleave_list == NULL);
423    ASSERT_FALSE(interleave_list->Empty());
424
425    ListWrapperSimple* ascending_list = CreateAscendingList(rand()%2);
426    ASSERT_FALSE(ascending_list == NULL);
427
428    for (int i = 0; i < kNumberOfElements/2; ++i) {
429        ASSERT_EQ(0,interleave_list->PopBack());
430        ASSERT_EQ(0,ascending_list->PopBack());
431    }
432    ASSERT_EQ(kNumberOfElements/2,interleave_list->GetSize());
433    ASSERT_EQ(kNumberOfElements/2,ascending_list->GetSize());
434
435    int insert_position = kNumberOfElements/2;
436    ASSERT_EQ(insert_position * 2, kNumberOfElements);
437    while (!ascending_list->Empty())
438    {
439        ListItem* item = ascending_list->Last();
440        ASSERT_FALSE(item == NULL);
441
442        const unsigned int item_id = ascending_list->GetUnsignedItem(item);
443        ASSERT_EQ(0,ascending_list->Erase(item));
444
445        ListItem* insert_item = interleave_list->CreateListItem(item_id);
446        ASSERT_FALSE(insert_item == NULL);
447        item = interleave_list->First();
448        ASSERT_FALSE(item == NULL);
449        for (int j = 0; j < insert_position - 1; ++j) {
450            item = interleave_list->Next(item);
451            ASSERT_FALSE(item == NULL);
452        }
453        if (0 != interleave_list->InsertBefore(item,insert_item)) {
454            interleave_list->DestroyListItem(insert_item);
455            FAIL();
456        }
457        --insert_position;
458    }
459
460    ListWrapperSimple* interleaved_list = CreateInterleavedList(rand()%2);
461    ASSERT_FALSE(interleaved_list == NULL);
462    ASSERT_FALSE(interleaved_list->Empty());
463
464    ASSERT_TRUE(CompareLists(interleaved_list,interleave_list));
465}
466
467int main(int argc, char **argv)
468{
469    ::testing::InitGoogleTest(&argc, argv);
470    // Added return_value so that it's convenient to put a breakpoint before
471    // exiting please note that the return value from RUN_ALL_TESTS() must
472    // be returned by the main function.
473    const int return_value = RUN_ALL_TESTS();
474    return return_value;
475}
476