sw/qa/core/Test-BigPtrArray.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <cppunit/TestAssert.h>
  21 #include <cppunit/TestFixture.h>
  22 #include <cppunit/extensions/HelperMacros.h>
  23
  24 //#define TIMELOG for measuring performance
  25
  26 #include <bparr.hxx>
  27
  28 namespace /* private */
  29 {
  30     const sal_Int32 NUM_ENTRIES = 10;
  31
  32     class BigPtrEntryMock : public BigPtrEntry
  33     {
  34     public:
  35         explicit BigPtrEntryMock(sal_Int32 count) : count_(count)
  36         {
  37         }
  38
  39         sal_Int32 getCount() const
  40         {
  41             return count_;
  42         }
  43
  44         sal_Int32 Position() const
  45         {
  46             return GetPos();
  47         }
  48
  49     private:
  50         sal_Int32 count_;
  51     };
  52
  53     void fillBigPtrArray(BigPtrArray& bparr, sal_Int32 numEntries)
  54     {
  55         for (sal_Int32 i = 0; i < numEntries; i++)
  56             bparr.Insert(new BigPtrEntryMock(i), bparr.Count());
  57     }
  58
  59     bool checkElementPositions(const BigPtrArray& bparr)
  60     {
  61         for (sal_Int32 i = 0; i < bparr.Count(); i++)
  62         {
  63             if (static_cast<BigPtrEntryMock*>(bparr[i])->Position() != i)
  64                 return false;
  65         }
  66         return true;
  67     }
  68
  69     void releaseBigPtrArrayContent(BigPtrArray const & bparr)
  70     {
  71         for (sal_Int32 i = 0; i < bparr.Count(); i++)
  72             delete bparr[i];
  73     }
  74 }
  75
  76 class BigPtrArrayUnittest : public CppUnit::TestFixture
  77 {
  78 public:
  79
  80     BigPtrArrayUnittest()
  81     {
  82     }
  83
  84     /** Test constructor/destructor
  85         The size of the BigPtrArray
  86         aka the 'Count' should be 0
  87         initially.
  88     */
  89     void test_ctor()
  90     {
  91         BigPtrArray bparr;
  92
  93         CPPUNIT_ASSERT_EQUAL_MESSAGE
  94         (
  95             "BigPtrArray ctor failed",
  96             static_cast<sal_Int32>(0), bparr.Count()
  97         );
  98     }
  99
 100     void test_insert_entries_at_front()
 101     {
 102         BigPtrArray bparr;
 103
 104         for (sal_Int32 i = 0; i < NUM_ENTRIES; i++)
 105         {
 106             sal_Int32 oldCount = bparr.Count();
 107             bparr.Insert(new BigPtrEntryMock(i), 0);
 108             CPPUNIT_ASSERT_EQUAL_MESSAGE
 109             (
 110                 "test_insert_entries_at_front failed",
 111                 oldCount + 1, bparr.Count()
 112             );
 113         }
 114
 115         for (sal_Int32 i = 0, j = NUM_ENTRIES - 1; i < NUM_ENTRIES; i++, j--)
 116         {
 117             CPPUNIT_ASSERT_EQUAL_MESSAGE
 118             (
 119                 "test_insert_entries_at_front failed",
 120                 j, static_cast<BigPtrEntryMock*>(bparr[i])->getCount()
 121             );
 122         }
 123
 124         CPPUNIT_ASSERT_MESSAGE
 125         (
 126             "test_insert_entries_at_front failed",
 127             checkElementPositions(bparr)
 128         );
 129
 130         releaseBigPtrArrayContent(bparr);
 131     }
 132
 133     void test_insert_entries_in_the_middle()
 134     {
 135         BigPtrArray bparr;
 136
 137         fillBigPtrArray(bparr, NUM_ENTRIES);
 138
 139         sal_Int32 oldCount = bparr.Count();
 140
 141         bparr.Insert(new BigPtrEntryMock(NUM_ENTRIES), bparr.Count() / 2);
 142
 143         CPPUNIT_ASSERT_EQUAL_MESSAGE
 144         (
 145             "test_insert_entries_in_the_middle failed",
 146             oldCount + 1, bparr.Count()
 147         );
 148         CPPUNIT_ASSERT_EQUAL_MESSAGE
 149         (
 150             "test_insert_entries_in_the_middle failed",
 151             NUM_ENTRIES, static_cast<BigPtrEntryMock*>(bparr[bparr.Count() / 2])->getCount()
 152         );
 153
 154         CPPUNIT_ASSERT_MESSAGE
 155         (
 156             "test_insert_entries_in_the_middle failed",
 157             checkElementPositions(bparr)
 158         );
 159
 160         releaseBigPtrArrayContent(bparr);
 161     }
 162
 163     void test_insert_at_already_used_index()
 164     {
 165         BigPtrArray bparr;
 166
 167         fillBigPtrArray(bparr, NUM_ENTRIES);
 168
 169         const sal_Int32 oldCount = bparr.Count();
 170
 171         // insert 5 elements
 172         for (sal_Int32 i = 0, j = 30; i < 5; i++, j++)
 173             bparr.Insert(new BigPtrEntryMock(j), i);
 174
 175         CPPUNIT_ASSERT_EQUAL_MESSAGE
 176         (
 177             "test_insert_at_already_used_index failed",
 178             oldCount + 5, bparr.Count()
 179         );
 180
 181         // now, first 5 elements have counts: 30,31,..34
 182         // next 10 elements have counts: 0,1,..9
 183         for (sal_Int32 i = 0, j = 30; i < bparr.Count(); i++, j++)
 184         {
 185             CPPUNIT_ASSERT_EQUAL_MESSAGE
 186             (
 187                 "test_insert_at_already_used_index failed",
 188                 (i < 5 ? j : i - 5), static_cast<BigPtrEntryMock*>(bparr[i])->getCount()
 189             );
 190         }
 191
 192         CPPUNIT_ASSERT_MESSAGE
 193         (
 194             "test_insert_at_already_used_index failed",
 195             checkElementPositions(bparr)
 196         );
 197
 198         releaseBigPtrArrayContent(bparr);
 199     }
 200
 201     void test_insert_at_end()
 202     {
 203         BigPtrArray bparr;
 204
 205         fillBigPtrArray(bparr, NUM_ENTRIES);
 206
 207         sal_Int32 oldCount = bparr.Count();
 208         bparr.Insert(new BigPtrEntryMock(NUM_ENTRIES), bparr.Count());
 209
 210         CPPUNIT_ASSERT_EQUAL_MESSAGE
 211         (
 212             "test_insert_at_end failed",
 213             oldCount + 1, bparr.Count()
 214         );
 215         CPPUNIT_ASSERT_EQUAL_MESSAGE
 216         (
 217             "test_insert_at_end failed",
 218             NUM_ENTRIES, static_cast<BigPtrEntryMock*>(bparr[bparr.Count()-1])->getCount()
 219         );
 220
 221         CPPUNIT_ASSERT_MESSAGE
 222         (
 223             "test_insert_at_end failed",
 224             checkElementPositions(bparr)
 225         );
 226
 227         releaseBigPtrArrayContent(bparr);
 228     }
 229
 230     void test_remove_at_front()
 231     {
 232         BigPtrArray bparr;
 233
 234         fillBigPtrArray(bparr, NUM_ENTRIES);
 235
 236         for (sal_Int32 i = 0; i < NUM_ENTRIES; i++)
 237         {
 238             sal_Int32 oldCount = bparr.Count();
 239
 240             delete bparr[0]; // release content
 241             bparr.Remove(0); // remove item from container
 242
 243             CPPUNIT_ASSERT_EQUAL_MESSAGE
 244             (
 245                 "test_remove_at_front failed (wrong count)",
 246                 oldCount - 1, bparr.Count()
 247             );
 248
 249             for (sal_Int32 j = 0, k = i + 1; j < bparr.Count(); j++, k++)
 250             {
 251                 CPPUNIT_ASSERT_EQUAL_MESSAGE
 252                 (
 253                     "test_remove_at_front failed",
 254                     k, static_cast<BigPtrEntryMock*>(bparr[j])->getCount()
 255                 );
 256             }
 257
 258             CPPUNIT_ASSERT_MESSAGE
 259             (
 260                 "test_remove_at_front failed",
 261                 checkElementPositions(bparr)
 262             );
 263         }
 264     }
 265
 266     void test_remove_at_back()
 267     {
 268         BigPtrArray bparr;
 269
 270         fillBigPtrArray(bparr, NUM_ENTRIES);
 271
 272         for (int i = NUM_ENTRIES - 1; i >= 0; i--)
 273         {
 274             sal_Int32 oldCount = bparr.Count();
 275             delete bparr[i];
 276             bparr.Remove(i);
 277
 278             CPPUNIT_ASSERT_EQUAL_MESSAGE
 279             (
 280                 "test_remove_at_back failed (wrong count)",
 281                 (oldCount - 1), bparr.Count()
 282             );
 283
 284             for (sal_Int32 j = 0; j < bparr.Count(); j++)
 285             {
 286                 CPPUNIT_ASSERT_EQUAL_MESSAGE
 287                 (
 288                     "test_remove_at_back failed",
 289                     j, static_cast<BigPtrEntryMock*>(bparr[j])->getCount()
 290                 );
 291             }
 292
 293             CPPUNIT_ASSERT_MESSAGE
 294             (
 295                 "test_remove_at_back failed",
 296                 checkElementPositions(bparr)
 297             );
 298         }
 299     }
 300
 301     void test_remove_in_the_middle()
 302     {
 303         BigPtrArray bparr;
 304
 305         fillBigPtrArray(bparr, NUM_ENTRIES);
 306
 307         while (bparr.Count())
 308         {
 309             sal_Int32 oldCount = bparr.Count();
 310             sal_Int32 oldElement = static_cast<BigPtrEntryMock*>(bparr[bparr.Count() / 2])->getCount();
 311
 312             delete bparr[bparr.Count() / 2];
 313             bparr.Remove(bparr.Count() / 2);
 314
 315             CPPUNIT_ASSERT_EQUAL_MESSAGE
 316             (
 317                 "test_remove_in_the_middle failed (wrong count)",
 318                 oldCount - 1, bparr.Count()
 319             );
 320
 321             for (sal_Int32 i = 0; i < bparr.Count(); i++)
 322             {
 323                 CPPUNIT_ASSERT_MESSAGE
 324                 (
 325                     "test_remove_in_the_middle failed",
 326                     static_cast<BigPtrEntryMock*>(bparr[i])->getCount() != oldElement
 327                 );
 328             }
 329
 330             CPPUNIT_ASSERT_MESSAGE
 331             (
 332                 "test_remove_in_the_middle failed",
 333                 checkElementPositions(bparr)
 334             );
 335         }
 336     }
 337
 338     void test_remove_multiple_elements_at_once()
 339     {
 340         BigPtrArray bparr;
 341
 342         fillBigPtrArray(bparr, NUM_ENTRIES);
 343
 344         while(bparr.Count())
 345         {
 346             sal_Int32 nRemove = std::min<sal_Int32>(bparr.Count(), 3);
 347             sal_Int32 oldCount = bparr.Count();
 348
 349             for (sal_Int32 i = 0; i < nRemove; i++)
 350                 delete bparr[i];
 351
 352             bparr.Remove(0, nRemove);
 353
 354             CPPUNIT_ASSERT_EQUAL_MESSAGE
 355             (
 356                 "test_remove_multiple_elements_at_once failed",
 357                 oldCount - nRemove, bparr.Count()
 358             );
 359
 360             CPPUNIT_ASSERT_MESSAGE
 361             (
 362                 "test_remove_multiple_elements_at_once failed",
 363                 checkElementPositions(bparr)
 364             );
 365         }
 366     }
 367
 368     void test_remove_all_elements_at_once()
 369     {
 370         BigPtrArray bparr;
 371
 372         fillBigPtrArray(bparr, NUM_ENTRIES);
 373
 374         releaseBigPtrArrayContent(bparr);
 375         bparr.Remove(0, bparr.Count());
 376
 377         CPPUNIT_ASSERT_EQUAL_MESSAGE
 378         (
 379             "test_remove_all_elements_at_once failed",
 380             static_cast<sal_Int32>(0), bparr.Count()
 381         );
 382     }
 383
 384     void test_move_elements_from_lower_to_higher_pos()
 385     {
 386         BigPtrArray bparr;
 387
 388         fillBigPtrArray(bparr, NUM_ENTRIES);
 389
 390         for (sal_Int32 i = 0; i < NUM_ENTRIES - 1; i++)
 391         {
 392             bparr.Move(i, i + 2);
 393         }
 394
 395         for (sal_Int32 i = 0; i < (NUM_ENTRIES - 1); i++)
 396         {
 397             CPPUNIT_ASSERT_EQUAL_MESSAGE
 398             (
 399                 "test_move_elements_from_lower_to_higher_pos failed",
 400                 (i + 1), static_cast<BigPtrEntryMock*>(bparr[i])->getCount()
 401             );
 402         }
 403
 404         CPPUNIT_ASSERT_EQUAL_MESSAGE
 405         (
 406             "test_move_elements_from_lower_to_higher_pos failed",
 407             static_cast<sal_Int32>(0), static_cast<BigPtrEntryMock*>(bparr[NUM_ENTRIES -1])->getCount()
 408         );
 409
 410         CPPUNIT_ASSERT_MESSAGE
 411         (
 412             "test_move_elements_from_lower_to_higher_pos failed",
 413             checkElementPositions(bparr)
 414         );
 415
 416         releaseBigPtrArrayContent(bparr);
 417     }
 418
 419     void test_move_elements_from_higher_to_lower_pos()
 420     {
 421         BigPtrArray bparr;
 422
 423         fillBigPtrArray(bparr, NUM_ENTRIES);
 424
 425         for (int i = NUM_ENTRIES - 1; i >= 1; i--)
 426         {
 427             bparr.Move(i, i - 1);
 428         }
 429
 430         CPPUNIT_ASSERT_EQUAL_MESSAGE
 431         (
 432             "test_move_elements_from_higher_to_lower_pos failed",
 433             (NUM_ENTRIES - 1), static_cast<BigPtrEntryMock*>(bparr[0])->getCount()
 434         );
 435
 436         for (sal_Int32 i = 1; i < NUM_ENTRIES; i++)
 437         {
 438             CPPUNIT_ASSERT_EQUAL_MESSAGE
 439             (
 440                 "test_move_elements_from_higher_to_lower_pos failed",
 441                 (i - 1), static_cast<BigPtrEntryMock*>(bparr[i])->getCount()
 442             );
 443         }
 444
 445         CPPUNIT_ASSERT_MESSAGE
 446         (
 447             "test_move_elements_from_higher_to_lower_pos failed",
 448             checkElementPositions(bparr)
 449         );
 450
 451         releaseBigPtrArrayContent(bparr);
 452     }
 453
 454     void test_move_to_same_position()
 455     {
 456         BigPtrArray bparr;
 457
 458         fillBigPtrArray(bparr, NUM_ENTRIES);
 459
 460         for (sal_Int32 i = 0; i < NUM_ENTRIES; i++)
 461         {
 462             bparr.Move(i, i);
 463         }
 464
 465         for (sal_Int32 i = 0; i < NUM_ENTRIES; i++)
 466         {
 467             CPPUNIT_ASSERT_EQUAL_MESSAGE
 468             (
 469                 "test_move_to_same_position failed",
 470                 i, static_cast<BigPtrEntryMock*>(bparr[i])->getCount()
 471             );
 472         }
 473
 474         CPPUNIT_ASSERT_MESSAGE
 475         (
 476             "test_move_to_same_position failed",
 477             checkElementPositions(bparr)
 478         );
 479
 480         releaseBigPtrArrayContent(bparr);
 481     }
 482
 483     void test_replace_elements()
 484     {
 485         BigPtrArray bparr;
 486
 487         fillBigPtrArray(bparr, NUM_ENTRIES);
 488
 489         for (sal_Int32 i = 0, j = NUM_ENTRIES - 1; i < NUM_ENTRIES; i++, j--)
 490         {
 491             delete bparr[i];
 492             bparr.Replace(i, new BigPtrEntryMock(j));
 493         }
 494
 495         for (sal_Int32 i = 0; i < NUM_ENTRIES; i++)
 496         {
 497             CPPUNIT_ASSERT_EQUAL_MESSAGE
 498             (
 499                 "test_replace_elements failed",
 500                 (NUM_ENTRIES - i - 1), static_cast<BigPtrEntryMock*>(bparr[i])->getCount()
 501             );
 502         }
 503
 504         CPPUNIT_ASSERT_MESSAGE
 505         (
 506             "test_replace_elements failed",
 507             checkElementPositions(bparr)
 508         );
 509
 510         releaseBigPtrArrayContent(bparr);
 511     }
 512
 513     CPPUNIT_TEST_SUITE(BigPtrArrayUnittest);
 514     CPPUNIT_TEST(test_ctor);
 515     CPPUNIT_TEST(test_insert_entries_at_front);
 516     CPPUNIT_TEST(test_insert_entries_in_the_middle);
 517     CPPUNIT_TEST(test_insert_at_already_used_index);
 518     CPPUNIT_TEST(test_insert_at_end);
 519     CPPUNIT_TEST(test_remove_at_front);
 520     CPPUNIT_TEST(test_remove_at_back);
 521     CPPUNIT_TEST(test_remove_in_the_middle);
 522     CPPUNIT_TEST(test_remove_multiple_elements_at_once);
 523     CPPUNIT_TEST(test_remove_all_elements_at_once);
 524     CPPUNIT_TEST(test_move_elements_from_lower_to_higher_pos);
 525     CPPUNIT_TEST(test_move_elements_from_higher_to_lower_pos);
 526     CPPUNIT_TEST(test_move_to_same_position);
 527     CPPUNIT_TEST(test_replace_elements);
 528     CPPUNIT_TEST_SUITE_END();
 529 };
 530
 531 #if defined TIMELOG
 532
 533 const char* const START = "START: ";
 534 const char* const END = "END: ";
 535
 536 class PerformanceTracer
 537 {
 538 public:
 539
 540 public:
 541     explicit PerformanceTracer(const string& methodName) :
 542         startString_(START),
 543         endString_(END)
 544     {
 545         startString_ += methodName;
 546         endString_ += methodName;
 547     }
 548
 549     ~PerformanceTracer()
 550     {
 551     }
 552
 553 private:
 554     string startString_;
 555     string endString_;
 556 };
 557
 558 class BigPtrArrayPerformanceTest : public CppUnit::TestFixture
 559 {
 560 public:
 561     BigPtrArrayPerformanceTest()
 562     {
 563     }
 564
 565     void test_insert_at_end_1000()
 566     { test_insert_at_end("1000"); }
 567
 568     void test_insert_at_end_10000()
 569     { test_insert_at_end("10000"); }
 570
 571     void test_insert_at_end_100000()
 572     { test_insert_at_end("100000"); }
 573
 574     void test_insert_at_end_1000000()
 575     { test_insert_at_end("1000000"); }
 576
 577     void test_insert_at_front_1000()
 578     { test_insert_at_front("1000"); }
 579
 580     void test_insert_at_front_10000()
 581     { test_insert_at_front("10000"); }
 582
 583     void test_insert_at_front_100000()
 584     { test_insert_at_front("100000"); }
 585
 586     void test_insert_at_front_1000000()
 587     { test_insert_at_front("1000000"); }
 588
 589     CPPUNIT_TEST_SUITE(BigPtrArrayPerformanceTest);
 590     CPPUNIT_TEST(test_insert_at_end_1000);
 591     CPPUNIT_TEST(test_insert_at_end_10000);
 592     CPPUNIT_TEST(test_insert_at_end_100000);
 593     CPPUNIT_TEST(test_insert_at_end_1000000);
 594     CPPUNIT_TEST(test_insert_at_front_1000);
 595     CPPUNIT_TEST(test_insert_at_front_10000);
 596     CPPUNIT_TEST(test_insert_at_front_100000);
 597     CPPUNIT_TEST(test_insert_at_front_1000000);
 598     CPPUNIT_TEST_SUITE_END();
 599
 600 private:
 601     void test_insert_at_end(const char* numElements)
 602     {
 603         OStringBuffer buff("test_insert_at_end ");
 604         buff.append(numElements);
 605         int n = atoi(numElements);
 606         PerformanceTracer tracer(buff.getStr());
 607         BigPtrArray bparr;
 608         for (int i = 0; i < n; i++)
 609             bparr.Insert(new BigPtrEntryMock(i), bparr.Count());
 610
 611         releaseBigPtrArrayContent(bparr);
 612     }
 613
 614     void test_insert_at_front(const char* numElements)
 615     {
 616         OStringBuffer buff("test_insert_at_front ");
 617         buff.append(numElements);
 618         int n = atoi(numElements);
 619         PerformanceTracer tracer(buff.getStr());
 620         BigPtrArray bparr;
 621         for (int i = 0; i < n; i++)
 622             bparr.Insert(new BigPtrEntryMock(i), 0);
 623
 624         releaseBigPtrArrayContent(bparr);
 625     }
 626 };
 627
 628 #endif
 629
 630 // register test suites
 631 CPPUNIT_TEST_SUITE_REGISTRATION(BigPtrArrayUnittest);
 632 #ifdef TIMELOG
 633 CPPUNIT_TEST_SUITE_REGISTRATION(BigPtrArrayPerformanceTest);
 634 #endif
 635
 636 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */