home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 April: Mac OS SDK / Dev.CD Apr 97 SDK1.toast / Development Kits (Disc 1) / Apple Shared Library Manager / ASLM Examples / TestTools / Sources / TestHashList.cp < prev    next >
Encoding:
Text File  |  1996-11-19  |  13.9 KB  |  580 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        TestHashList.cp
  3.  
  4.     Contains:    Tester for the THashList class
  5.  
  6.     Copyright:    © 1991-1994 by Apple Computer, Inc., all rights reserved.
  7.  
  8. */
  9.  
  10. #ifndef __TESTHASHLIST__
  11. #include "TestHashList.h"
  12. #endif
  13.  
  14. /**********************************************************************
  15. ** PUBLIC Constructor/Destructor
  16. ***********************************************************************/
  17.  
  18. Constructor(HashList)
  19. Destructor(HashList)
  20.  
  21. #define kArraySize    (sizeof(fArray)/sizeof(TDynamic*))
  22.  
  23. /**********************************************************************
  24. ** Test methods 
  25. ***********************************************************************/
  26.  
  27. void TTestHashList :: TestIsEmpty(Boolean correct) const
  28. {
  29.     if (correct)
  30.     {
  31.         if (!fTest->IsEmpty())
  32.             Printf("### ERROR: IsEmpty returned false when the list was not empty\n");
  33.     }
  34.     else
  35.     {
  36.         if (fTest->IsEmpty())
  37.             Printf("### ERROR: IsEmpty returned true when the list was empty\n");
  38.     }
  39. }
  40.  
  41. void TTestHashList :: TestCount(size_t shouldBe) const
  42. {
  43.     size_t is = fTest->Count();
  44.     if (is != shouldBe)
  45.         Printf("### ERROR: Count returned %u when it should have returned %u\n",
  46.                 is, shouldBe);
  47. }
  48.  
  49. void TTestHashList :: TestMember(short number, Boolean ifGone) const
  50. {
  51.     TNumber         obj(number);
  52.     TNumber*        ptr;
  53.     
  54.     if ((ptr = (TNumber*)fTest->Member(obj)) != NULL)
  55.     {
  56.         if (ifGone)
  57.             Printf("### ERROR: Member(match) returned #%hu when it should not be present\n",
  58.                     ptr->fNumber);
  59.         else
  60.             if (number != ptr->fNumber)
  61.                 Printf("### ERROR: Member(match) returned #%hu when it should have returned #%hu\n",
  62.                         ptr->fNumber, number);
  63.             else
  64.                 if (ptr != (TNumber*)fArray[number])
  65.                     Printf("### ERROR: Member(match) returned the wrong object for #%hu\n",
  66.                             ptr->fNumber);
  67.     }
  68.     else
  69.         if (!ifGone)
  70.             Printf("### ERROR: Member(match) returned no object when #%hu should have been present\n",
  71.                     number);
  72.     if (fTest->Member(fArray[number]))
  73.     {
  74.         if (ifGone)
  75.             Printf("### ERROR: Member(void*) returned TRUE when it should not be present\n");
  76.     }
  77.     else
  78.         if (!ifGone)
  79.             Printf("### ERROR: Member(void*) returned FALSE when #%hu should have been present\n",
  80.                     number);
  81. }    
  82.  
  83. /*******************************************************************************
  84. ** PUBLIC DoMiscTests
  85. ********************************************************************************/
  86.  
  87. void TTestHashList::DoMiscTests(Boolean ifAll) const
  88. {
  89.     HashListInfo    info;
  90.     fTest->GetHashListInfo(info);
  91.  
  92.     if (ifAll)
  93.     {
  94.         if (info.emptySlots != 0)
  95.             Printf("### ERROR: List is full, but # empty slots is %u instead of 0\n",
  96.                    info.emptySlots);
  97.         if (info.longestChain < 3)
  98.             Printf("### ERROR: List is full, but longest chain came back as %u instead of at least 3\n",
  99.                    info.longestChain);
  100.         if (info.longestChain > 5)
  101.             Printf("### WARNING: List is full, and longest chain came back as %u\n", info.longestChain);
  102.     }
  103.     else
  104.     {
  105.         if (info.emptySlots != fTest->GetTableSize())
  106.             Printf("### ERROR: List is empty, but # empty slots is %u instead of %u\n",
  107.                    info.emptySlots, fTest->GetTableSize());
  108.         if (info.longestChain != 0)
  109.             Printf("### ERROR: List is empty, but longest chain came back as %u instead of 0\n",
  110.                    info.longestChain);
  111.     }
  112. }
  113.  
  114. /**********************************************************************
  115. ** PUBLIC InitTest
  116. ***********************************************************************/
  117.  
  118. void TTestHashList :: InitTest(BooleanParm verbose, BooleanParm, int, char**)
  119. {
  120.     short            idx;
  121.     TNumberHasher*    hasher = NULL;
  122.     
  123.     TStandardPool* pool = GetPool();
  124.  
  125.     if (pool == NULL)
  126.     {
  127.         Printf("### ERROR: There is no global pool\n");
  128.         return;
  129.     }
  130.  
  131.     for (idx = 0; idx < kArraySize; ++idx)
  132.         fArray[idx] = NULL;
  133.     
  134.     fTest = NULL;
  135.     
  136.     TRY
  137.         hasher = new (pool) TNumberHasher;
  138.         if (hasher)
  139.             fTest = new (pool) THashList(hasher, kArraySize/4);
  140.     CATCH_ALL
  141.     ENDTRY
  142.     
  143.     if (hasher == NULL)
  144.     {
  145.         Printf("### ERROR: Could not create TNumberHasher\n");
  146.         return;
  147.     }
  148.     if (fTest == NULL)
  149.     {
  150.         Printf("### ERROR: Could not create THashList\n");
  151.         delete hasher;
  152.         return;
  153.     }
  154.     
  155.     for (idx = 0; idx < kArraySize; ++idx)
  156.     {
  157.         TNumber* num;
  158.         if ((num = new (pool) TNumber(idx)) == NULL)
  159.         {
  160.             Printf("### ERROR: Out of Memory at #%d\n", idx);
  161.             break;
  162.         }
  163.         fArray[idx] = num;
  164.     }
  165.     if (idx == kArraySize && verbose)
  166.         Printf("INFO: Allocated %u objects\n", kArraySize);
  167. }
  168.  
  169. /**********************************************************************
  170. ** PUBLIC RunTestIteration
  171. ***********************************************************************/
  172.  
  173. void TTestHashList :: RunTestIteration(BooleanParm verbose, BooleanParm)
  174. {
  175.     short            matchFirst;
  176.     short            matchLast;
  177.     short            toMatch;
  178.     short            idx, jdx;
  179.     TNumber*        ptr;
  180.     OSErr            err;
  181.     HashListInfo    info;
  182.     
  183.     if (verbose)
  184.         Printf("INFO: Testing EmptyList\n");
  185.         
  186.     TestIsEmpty(true);
  187.     TestCount(0);
  188.     for (jdx = 0; jdx < kArraySize; ++jdx)
  189.         TestMember(jdx, true);
  190.     DoMiscTests(false);
  191.     
  192.     if (verbose)
  193.         Printf("INFO: Testing Add, Member, Count, and IsEmpty\n");
  194.     
  195.     for (idx = 0; idx < kArraySize; ++idx)
  196.     {
  197.         ptr = (TNumber*)fArray[idx];
  198.         fTest->Add(ptr);
  199.         
  200.         TestIsEmpty(false);
  201.         TestCount(idx + 1);
  202.  
  203.         for (jdx = 0; jdx < kArraySize; ++jdx)
  204.             TestMember(jdx, jdx > idx);
  205.     }
  206.     
  207.     TestIsEmpty(false);
  208.     TestCount(kArraySize);
  209.     DoMiscTests(true);
  210.  
  211.     if (verbose)
  212.     {
  213.         fTest->GetHashListInfo(info);
  214.         Printf("\nINFO: # empty slots  = %u\n", info.emptySlots);
  215.         Printf("INFO: # single slots = %u\n", info.singleSlots);
  216.         Printf("INFO: # chains       = %u\n", info.numChains);
  217.         Printf("INFO: longest chain  = %u\n", info.longestChain);
  218.         Printf("INFO: avg chain      = %u\n\n", info.avgChain);
  219.     }
  220.     if (verbose)
  221.         Printf("INFO: Testing AddUnique, Member, Count, and IsEmpty\n");
  222.     
  223.     for (idx = 0; idx < kArraySize; ++idx)
  224.     {
  225.         ptr = (TNumber*)fArray[idx];
  226.         err = fTest->AddUnique(ptr);
  227.         if (err != kASLMDuplicateFoundErr)
  228.         {
  229.             Printf("### ERROR: AddUnique of index #%hu return error %d\n",
  230.                    idx, err);
  231.         }
  232.     }
  233.  
  234.     matchFirst = 0;
  235.     matchLast  = kArraySize - 1;
  236.     if (verbose)
  237.         Printf("INFO: Testing Member and Remove by pointer methods\n");
  238.  
  239.     for (idx = 0; idx < kArraySize; ++idx)
  240.     {
  241.         Boolean result;
  242.         
  243.         TestIsEmpty(false);
  244.         TestCount(kArraySize - idx);
  245.  
  246.         for (jdx = 0; jdx < kArraySize; ++jdx)
  247.             TestMember(jdx, jdx < matchFirst || jdx > matchLast);
  248.         
  249.         if (idx & 1)
  250.         {
  251.             result = fTest->Remove(fArray[matchFirst]);
  252.             toMatch = matchFirst;
  253.             matchFirst += 1;
  254.         }
  255.         else
  256.         {
  257.             result = fTest->Remove(fArray[matchLast]);
  258.             toMatch = matchLast;
  259.             matchLast -= 1;
  260.         }
  261.         if (!result)
  262.             Printf("### ERROR: Remove(obj) return FALSE for #%hu\n", 
  263.                    toMatch);
  264.         if (fTest->Remove(fArray[toMatch]))
  265.             Printf("### ERROR: Remove(obj) a 2nd time returned TRUE for #%hu\n", 
  266.                    toMatch);
  267.     }
  268.     
  269.     TestIsEmpty(true);
  270.     TestCount(0);
  271.     for (jdx = 0; jdx < kArraySize; ++jdx)
  272.         TestMember(jdx, true);
  273.     DoMiscTests(false);
  274.         
  275.     if (verbose)
  276.         Printf("INFO: Testing AddUnique in Random order\n");
  277.     
  278.     fTest->RemoveAll();     // Just in case
  279.     
  280.     matchFirst = 0;
  281.     matchLast  = kArraySize - 1;
  282.     for (idx = 0; idx < kArraySize; ++idx)
  283.     {
  284.         if (idx & 1)
  285.             ptr = (TNumber*)fArray[matchFirst];
  286.         else
  287.             ptr = (TNumber*)fArray[matchLast];
  288.         fTest->Add(ptr);
  289.         
  290.         TestIsEmpty(false);
  291.         TestCount(idx + 1);
  292.  
  293.         for (jdx = 0; jdx < kArraySize; ++jdx)
  294.             if (idx & 1)
  295.                 TestMember(jdx, jdx > matchFirst && jdx <= matchLast);
  296.             else
  297.                 TestMember(jdx, jdx >= matchFirst && jdx < matchLast);
  298.         if (idx & 1)
  299.             matchFirst += 1;
  300.         else
  301.             matchLast -= 1;
  302.     }
  303.     
  304.     TestIsEmpty(false);
  305.     TestCount(kArraySize);
  306.     for (jdx = 0; jdx < kArraySize; ++jdx)
  307.         TestMember(jdx, false);
  308.     DoMiscTests(true);
  309.     if (verbose)
  310.     {
  311.         fTest->GetHashListInfo(info);
  312.         Printf("\nINFO: # empty slots  = %u\n", info.emptySlots);
  313.         Printf("INFO: # single slots = %u\n", info.singleSlots);
  314.         Printf("INFO: # chains       = %u\n", info.numChains);
  315.         Printf("INFO: longest chain  = %u\n", info.longestChain);
  316.         Printf("INFO: avg chain      = %u\n\n", info.avgChain);
  317.     }
  318.  
  319.     if (verbose)
  320.         Printf("INFO: Testing Remove by reference\n");
  321.         
  322.     matchFirst = (kArraySize/2) - 1;
  323.     matchLast  = kArraySize/2;
  324.  
  325.     for (idx = 0; idx < kArraySize; ++idx)
  326.     {
  327.         for (jdx = 0; jdx < kArraySize; ++jdx)
  328.             TestMember(jdx, jdx > matchFirst && jdx < matchLast);
  329.         if (idx & 1)
  330.             jdx = matchFirst;
  331.         else
  332.             jdx = matchLast;
  333.         
  334.         TestIsEmpty(false);
  335.         TestCount(kArraySize - idx);
  336.         
  337.         {
  338.             TNumber    test(jdx);
  339.             ptr = (TNumber*)fTest->Remove(test);
  340.             if (ptr == NULL)
  341.                 Printf("ERROR: Remove for number #%u returned NULL\n", jdx);
  342.             else
  343.             {
  344.                 if (ptr != fArray[jdx])
  345.                     Printf("### ERROR: Remove for number #%u returned the wrong pointer\n", jdx);
  346.                 if (ptr->fNumber != jdx)
  347.                     Printf("### ERROR: Remove for number #%u return #%u\n", jdx, ptr->fNumber);
  348.             }
  349.             ptr = (TNumber*)fTest->Remove(test);
  350.             if (ptr != NULL)
  351.                 Printf("### ERROR: Remove for number #%u a second time return #%u\n",
  352.                        jdx, ptr->fNumber);
  353.         }
  354.  
  355.         TestCount(kArraySize - 1 -idx);
  356.                 
  357.         if (idx & 1)
  358.             matchFirst -= 1;
  359.         else
  360.             matchLast += 1;
  361.             
  362.     }
  363.  
  364.     TestIsEmpty(true);
  365.     TestCount(0);
  366.     for (jdx = 0; jdx < kArraySize; ++jdx)
  367.         TestMember(jdx, true);
  368.     DoMiscTests(false);
  369.  
  370.     if (verbose)
  371.         Printf("INFO: Testing RemoveAll\n");
  372.     
  373.     fTest->RemoveAll();
  374.     
  375.     TestIsEmpty(true);
  376.     TestCount(0);
  377.     for (jdx = 0; jdx < kArraySize; ++jdx)
  378.         TestMember(jdx, true);
  379.         
  380.     for (idx = 0; idx < kArraySize; ++idx)
  381.         fTest->Add(fArray[idx]);
  382.     
  383.     if (verbose)
  384.         Printf("INFO: Testing Iterator::Next()\n");
  385.         
  386.     Boolean        saw[kArraySize];
  387.     Boolean        ok;
  388.     TIterator* it = fTest->CreateIterator((TStandardPool*)TMemoryPool::RecoverPool(fTest));
  389.     TNumber*    num;
  390.     memset(saw, 0, sizeof(saw));
  391.     while ((num = (TNumber*)it->Next()) != NULL)
  392.     {
  393.         if (num->fNumber < 0 || num->fNumber > 99)
  394.             Printf("ERROR: Iterator returned a #%u object\n", num->fNumber);
  395.         else
  396.         {
  397.             if (saw[num->fNumber])
  398.                 Printf("ERROR: Iterator returned #%u more than once\n", num->fNumber);
  399.             saw[num->fNumber] = true;
  400.         }
  401.     }
  402.     ok = true;
  403.     for (jdx = 0; jdx < kArraySize; ++jdx)
  404.         if (!saw[jdx])
  405.         {
  406.             ok = false;
  407.             Printf("ERROR: Iterator did not return #%u\n", jdx);
  408.         }
  409.         
  410.     if (ok)
  411.     {
  412.         if (verbose)
  413.             Printf("INFO: Testing Iterator::RemoveCurrentObject\n");
  414.         it->Reset();
  415.         memset(saw, 0, sizeof(saw));
  416.  
  417.         while ((num = (TNumber*)it->Next()) != NULL)
  418.         {
  419.             if (num->fNumber < 0 || num->fNumber > 99)
  420.                 Printf("ERROR: Iterator returned a #%u object\n", num->fNumber);
  421.             else
  422.             {
  423.                 if (saw[num->fNumber])
  424.                     Printf("ERROR: Iterator returned #%u more than once\n", num->fNumber);
  425.                 saw[num->fNumber] = true;
  426.                 if (!it->RemoveCurrentObject())
  427.                     Printf("ERROR: RemoveCurrentObject returned false on #%u\n", num->fNumber);
  428.                 for (jdx = 0; jdx < kArraySize; ++jdx)
  429.                     TestMember(jdx, saw[jdx]);
  430.             }
  431.         }
  432.         TestIsEmpty(true);
  433.         TestCount(0);
  434.     }
  435.     if (ok && fTest->IsEmpty())
  436.     {
  437.         if (verbose)
  438.             Printf("INFO: Testing Iterator::RemoveCurrentObject Randomly\n");
  439.         for (idx = 0; idx < kArraySize; ++idx)
  440.             fTest->Add(fArray[idx]);
  441.         
  442.         TestIsEmpty(false);
  443.         TestCount(kArraySize);
  444.         
  445.         memset(saw, 0, sizeof(saw));
  446.         size_t    count = 0;
  447.         TFastRandom    rand;
  448.         while (count < 100)
  449.         {
  450.             unsigned long    kill;
  451.             do
  452.             {
  453.                 kill = rand.GetRandomNumber(0, 99);
  454.             } while (saw[kill]);
  455.             
  456.             it->Reset();
  457.  
  458.             while ((num = (TNumber*)it->Next()) != NULL)
  459.             {
  460.                 if (num->fNumber < 0 || num->fNumber > 99)
  461.                     Printf("ERROR: Iterator returned a #%u object\n", num->fNumber);
  462.                 else
  463.                 {
  464.                     if (saw[num->fNumber])
  465.                         Printf("ERROR: Iterator returned #%u more than once\n", num->fNumber);
  466.                     if (num->fNumber == kill)
  467.                     {
  468.                         ++count;
  469.                         saw[num->fNumber] = true;
  470.                         if (!it->RemoveCurrentObject())
  471.                             Printf("ERROR: RemoveCurrentObject returned false on #%u\n", num->fNumber);
  472.                         for (jdx = 0; jdx < kArraySize; ++jdx)
  473.                             TestMember(jdx, saw[jdx]);
  474.                     }
  475.                 }
  476.             }
  477.         }
  478.     }
  479.     if (ok && fTest->IsEmpty())
  480.     {
  481.         size_t    todo = fTest->GetTableSize() + fTest->GetTableSize()/2;
  482.         if (verbose)
  483.             Printf("INFO: Testing Iterator::RemoveCurrentObject Randomly with mixed chains\n");
  484.         for (idx = 0; idx < todo; ++idx)
  485.             fTest->Add(fArray[idx]);
  486.         
  487.         TestIsEmpty(false);
  488.         TestCount(todo);
  489.         if (verbose)
  490.         {
  491.             fTest->GetHashListInfo(info);
  492.             Printf("\nINFO: # empty slots  = %u\n", info.emptySlots);
  493.             Printf("INFO: # single slots = %u\n", info.singleSlots);
  494.             Printf("INFO: # chains       = %u\n", info.numChains);
  495.             Printf("INFO: longest chain  = %u\n", info.longestChain);
  496.             Printf("INFO: avg chain      = %u\n\n", info.avgChain);
  497.         }
  498.                 
  499.         memset(saw, 0, sizeof(saw));
  500.         size_t    count = 0;
  501.         TFastRandom    rand;
  502.         while (count < todo)
  503.         {
  504.             size_t    kill;
  505.             do
  506.             {
  507.                 kill = size_t(rand.GetRandomNumber(0, todo - 1));
  508.             } while (saw[kill]);
  509.             
  510.             it->Reset();
  511.  
  512.             while ((num = (TNumber*)it->Next()) != NULL)
  513.             {
  514.                 if (num->fNumber < 0 || num->fNumber > todo - 1)
  515.                     Printf("ERROR: Iterator returned a #%u object\n", num->fNumber);
  516.                 else
  517.                 {
  518.                     if (saw[num->fNumber])
  519.                         Printf("ERROR: Iterator returned #%u more than once\n", num->fNumber);
  520.                     if (num->fNumber == kill)
  521.                     {
  522.                         ++count;
  523.                         saw[num->fNumber] = true;
  524.                         if (!it->RemoveCurrentObject())
  525.                             Printf("ERROR: RemoveCurrentObject returned false on #%u\n", num->fNumber);
  526.                         for (jdx = 0; jdx < todo; ++jdx)
  527.                             TestMember(jdx, saw[jdx]);
  528.                     }
  529.                 }
  530.             }
  531.         }
  532.     }
  533.     delete it;
  534.     
  535.     TestIsEmpty(true);
  536.     TestCount(0);
  537.     if (fTest->IsEmpty())
  538.     {
  539.         for (idx = 0; idx < kArraySize; ++idx)
  540.             fTest->Add(fArray[idx]);
  541.         
  542.         TestIsEmpty(false);
  543.         TestCount(kArraySize);
  544.         if (verbose)
  545.             Printf("INFO: Testing DeleteAll\n");
  546.         
  547.         fTest->DeleteAll(kTDynamicPointer);
  548.         
  549.         TestIsEmpty(true);
  550.         TestCount(0);
  551.     }
  552.     
  553.     for (jdx = 0; jdx < kArraySize; ++jdx)
  554.     {
  555.         TNumber    foo(jdx);
  556.         if (!fTest->Member(foo))
  557.             fArray[jdx] = NULL;
  558.         else
  559.             Printf("ERROR: Member #%u still seems to exists\n", jdx);
  560.     }
  561.     DoMiscTests(false);
  562. }
  563.  
  564. /**********************************************************************
  565. ** PUBLIC EndTest
  566. ***********************************************************************/
  567.  
  568. void TTestHashList :: EndTest(BooleanParm verbose, BooleanParm)
  569. {
  570.     if (verbose)
  571.         Printf("INFO: End of HashList test\n");
  572.     TNumberHasher* hasher = (TNumberHasher*)fTest->GetHashObject();
  573.     delete hasher;
  574.     for (short idx = 0; idx < kArraySize; ++idx)
  575.     {
  576.         TDynamic* obj = fArray[idx];
  577.         delete obj;
  578.     }
  579. }
  580.