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