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