xpcom/tests/TestTArray.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is C++ array template tests.
  17  *
  18  * The Initial Developer of the Original Code is Google Inc.
  19  * Portions created by the Initial Developer are Copyright (C) 2005
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *  Darin Fisher <darin@meer.net>
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 #include <stdlib.h>
  40 #include <stdio.h>
  41 #include "nsTArray.h"
  42 #include "nsTPtrArray.h"
  43 #include "nsMemory.h"
  44 #include "nsAutoPtr.h"
  45 #include "nsString.h"
  46 #include "nsDirectoryServiceDefs.h"
  47 #include "nsDirectoryServiceUtils.h"
  48 #include "nsComponentManagerUtils.h"
  49 #include "nsXPCOM.h"
  50 #include "nsILocalFile.h"
  51
  52 namespace TestTArray {
  53
  54 // Define this so we can use test_basic_array in test_comptr_array
  55 template <class T>
  56 inline bool operator<(const nsCOMPtr<T>& lhs, const nsCOMPtr<T>& rhs) {
  57   return lhs.get() < rhs.get();
  58 }
  59
  60 //----
  61
  62 template <class ElementType>
  63 static PRBool test_basic_array(ElementType *data,
  64                                PRUint32 dataLen,
  65                                const ElementType& extra) {
  66   nsTArray<ElementType> ary;
  67   ary.AppendElements(data, dataLen);
  68   if (ary.Length() != dataLen) {
  69     return PR_FALSE;
  70   }
  71   if (!(ary == ary)) {
  72     return PR_FALSE;
  73   }
  74   PRUint32 i;
  75   for (i = 0; i < ary.Length(); ++i) {
  76     if (ary[i] != data[i])
  77       return PR_FALSE;
  78   }
  79   for (i = 0; i < ary.Length(); ++i) {
  80     if (ary.SafeElementAt(i, extra) != data[i])
  81       return PR_FALSE;
  82   }
  83   if (ary.SafeElementAt(ary.Length(), extra) != extra ||
  84       ary.SafeElementAt(ary.Length() * 10, extra) != extra)
  85     return PR_FALSE;
  86   // ensure sort results in ascending order
  87   ary.Sort();
  88   PRUint32 j = 0, k;
  89   if (ary.GreatestIndexLtEq(extra, k))
  90     return PR_FALSE;
  91   for (i = 0; i < ary.Length(); ++i) {
  92     if (!ary.GreatestIndexLtEq(ary[i], k))
  93       return PR_FALSE;
  94     if (k < j)
  95       return PR_FALSE;
  96     j = k;
  97   }
  98   for (i = ary.Length(); --i; ) {
  99     if (ary[i] < ary[i - 1])
 100       return PR_FALSE;
 101     if (ary[i] == ary[i - 1])
 102       ary.RemoveElementAt(i);
 103   }
 104   if (!(ary == ary)) {
 105     return PR_FALSE;
 106   }
 107   for (i = 0; i < ary.Length(); ++i) {
 108     if (ary.BinaryIndexOf(ary[i]) != i)
 109       return PR_FALSE;
 110   }
 111   if (ary.BinaryIndexOf(extra) != ary.NoIndex)
 112     return PR_FALSE;
 113   PRUint32 oldLen = ary.Length();
 114   ary.RemoveElement(data[dataLen / 2]);
 115   if (ary.Length() != (oldLen - 1))
 116     return PR_FALSE;
 117   if (!(ary == ary))
 118     return PR_FALSE;
 119
 120   PRUint32 index = ary.Length() / 2;
 121   if (!ary.InsertElementAt(index, extra))
 122     return PR_FALSE;
 123   if (!(ary == ary))
 124     return PR_FALSE;
 125   if (ary[index] != extra)
 126     return PR_FALSE;
 127   if (ary.IndexOf(extra) == PR_UINT32_MAX)
 128     return PR_FALSE;
 129   if (ary.LastIndexOf(extra) == PR_UINT32_MAX)
 130     return PR_FALSE;
 131   // ensure proper searching
 132   if (ary.IndexOf(extra) > ary.LastIndexOf(extra))
 133     return PR_FALSE;
 134   if (ary.IndexOf(extra, index) != ary.LastIndexOf(extra, index))
 135     return PR_FALSE;
 136
 137   nsTArray<ElementType> copy(ary);
 138   if (!(ary == copy))
 139     return PR_FALSE;
 140   for (i = 0; i < copy.Length(); ++i) {
 141     if (ary[i] != copy[i])
 142       return PR_FALSE;
 143   }
 144   if (!ary.AppendElements(copy))
 145     return PR_FALSE;
 146   PRUint32 cap = ary.Capacity();
 147   ary.RemoveElementsAt(copy.Length(), copy.Length());
 148   ary.Compact();
 149   if (ary.Capacity() == cap)
 150     return PR_FALSE;
 151
 152   ary.Clear();
 153   if (!ary.IsEmpty() || ary.Elements() == nsnull)
 154     return PR_FALSE;
 155   if (!(ary == nsTArray<ElementType>()))
 156     return PR_FALSE;
 157   if (ary == copy)
 158     return PR_FALSE;
 159   if (ary.SafeElementAt(0, extra) != extra ||
 160       ary.SafeElementAt(10, extra) != extra)
 161     return PR_FALSE;
 162
 163   ary = copy;
 164   if (!(ary == copy))
 165     return PR_FALSE;
 166   for (i = 0; i < copy.Length(); ++i) {
 167     if (ary[i] != copy[i])
 168       return PR_FALSE;
 169   }
 170
 171   if (!ary.InsertElementsAt(0, copy))
 172     return PR_FALSE;
 173   if (ary == copy)
 174     return PR_FALSE;
 175   ary.RemoveElementsAt(0, copy.Length());
 176   for (i = 0; i < copy.Length(); ++i) {
 177     if (ary[i] != copy[i])
 178       return PR_FALSE;
 179   }
 180
 181   // These shouldn't crash!
 182   nsTArray<ElementType> empty;
 183   ary.AppendElements(reinterpret_cast<ElementType *>(0), 0);
 184   ary.AppendElements(empty);
 185
 186   // See bug 324981
 187   ary.RemoveElement(extra);
 188   ary.RemoveElement(extra);
 189
 190   return PR_TRUE;
 191 }
 192
 193 static PRBool test_int_array() {
 194   int data[] = {4,6,8,2,4,1,5,7,3};
 195   return test_basic_array(data, NS_ARRAY_LENGTH(data), int(14));
 196 }
 197
 198 static PRBool test_int64_array() {
 199   PRInt64 data[] = {4,6,8,2,4,1,5,7,3};
 200   return test_basic_array(data, NS_ARRAY_LENGTH(data), PRInt64(14));
 201 }
 202
 203 static PRBool test_char_array() {
 204   char data[] = {4,6,8,2,4,1,5,7,3};
 205   return test_basic_array(data, NS_ARRAY_LENGTH(data), char(14));
 206 }
 207
 208 static PRBool test_uint32_array() {
 209   PRUint32 data[] = {4,6,8,2,4,1,5,7,3};
 210   return test_basic_array(data, NS_ARRAY_LENGTH(data), PRUint32(14));
 211 }
 212
 213 //----
 214
 215 class Object {
 216   public:
 217     Object() : mNum(0) {
 218     }
 219     Object(const char *str, PRUint32 num) : mStr(str), mNum(num) {
 220     }
 221     Object(const Object& other) : mStr(other.mStr), mNum(other.mNum) {
 222     }
 223     ~Object() {}
 224
 225     Object& operator=(const Object& other) {
 226       mStr = other.mStr;
 227       mNum = other.mNum;
 228       return *this;
 229     }
 230
 231     PRBool operator==(const Object& other) const {
 232       return mStr == other.mStr && mNum == other.mNum;
 233     }
 234
 235     PRBool operator<(const Object& other) const {
 236       // sort based on mStr only
 237       return Compare(mStr, other.mStr) < 0;
 238     }
 239
 240     const char *Str() const { return mStr.get(); }
 241     PRUint32 Num() const { return mNum; }
 242
 243   private:
 244     nsCString mStr;
 245     PRUint32  mNum;
 246 };
 247
 248 static PRBool test_object_array() {
 249   nsTArray<Object> objArray;
 250   const char kdata[] = "hello world";
 251   PRUint32 i;
 252   for (i = 0; i < NS_ARRAY_LENGTH(kdata); ++i) {
 253     char x[] = {kdata[i],'\0'};
 254     if (!objArray.AppendElement(Object(x, i)))
 255       return PR_FALSE;
 256   }
 257   for (i = 0; i < NS_ARRAY_LENGTH(kdata); ++i) {
 258     if (objArray[i].Str()[0] != kdata[i])
 259       return PR_FALSE;
 260     if (objArray[i].Num() != i)
 261       return PR_FALSE;
 262   }
 263   objArray.Sort();
 264   const char ksorted[] = "\0 dehllloorw";
 265   for (i = 0; i < NS_ARRAY_LENGTH(kdata)-1; ++i) {
 266     if (objArray[i].Str()[0] != ksorted[i])
 267       return PR_FALSE;
 268   }
 269   return PR_TRUE;
 270 }
 271
 272 // nsTArray<nsAutoPtr<T>> is not supported
 273 #if 0
 274 static PRBool test_autoptr_array() {
 275   nsTArray< nsAutoPtr<Object> > objArray;
 276   const char kdata[] = "hello world";
 277   for (PRUint32 i = 0; i < NS_ARRAY_LENGTH(kdata); ++i) {
 278     char x[] = {kdata[i],'\0'};
 279     nsAutoPtr<Object> obj(new Object(x,i));
 280     if (!objArray.AppendElement(obj))  // XXX does not call copy-constructor for nsAutoPtr!!!
 281       return PR_FALSE;
 282     if (obj.get() == nsnull)
 283       return PR_FALSE;
 284     obj.forget();  // the array now owns the reference
 285   }
 286   for (PRUint32 i = 0; i < NS_ARRAY_LENGTH(kdata); ++i) {
 287     if (objArray[i]->Str()[0] != kdata[i])
 288       return PR_FALSE;
 289     if (objArray[i]->Num() != i)
 290       return PR_FALSE;
 291   }
 292   return PR_TRUE;
 293 }
 294 #endif
 295
 296 //----
 297
 298 static PRBool operator==(const nsCString &a, const char *b) {
 299   return a.Equals(b);
 300 }
 301
 302 static PRBool test_string_array() {
 303   nsTArray<nsCString> strArray;
 304   const char kdata[] = "hello world";
 305   PRUint32 i;
 306   for (i = 0; i < NS_ARRAY_LENGTH(kdata); ++i) {
 307     if (!strArray.AppendElement(nsCString(kdata[i])))
 308       return PR_FALSE;
 309   }
 310   for (i = 0; i < NS_ARRAY_LENGTH(kdata); ++i) {
 311     if (strArray[i].CharAt(0) != kdata[i])
 312       return PR_FALSE;
 313   }
 314
 315   const char kextra[] = "foo bar";
 316   PRUint32 oldLen = strArray.Length();
 317   if (!strArray.AppendElement(kextra))
 318     return PR_FALSE;
 319   strArray.RemoveElement(kextra);
 320   if (oldLen != strArray.Length())
 321     return PR_FALSE;
 322
 323   if (strArray.IndexOf("e") != 1)
 324     return PR_FALSE;
 325
 326   strArray.Sort();
 327   const char ksorted[] = "\0 dehllloorw";
 328   for (i = NS_ARRAY_LENGTH(kdata); i--; ) {
 329     if (strArray[i].CharAt(0) != ksorted[i])
 330       return PR_FALSE;
 331     if (i > 0 && strArray[i] == strArray[i - 1])
 332       strArray.RemoveElementAt(i);
 333   }
 334   for (i = 0; i < strArray.Length(); ++i) {
 335     if (strArray.BinaryIndexOf(strArray[i]) != i)
 336       return PR_FALSE;
 337   }
 338   if (strArray.BinaryIndexOf(EmptyCString()) != strArray.NoIndex)
 339     return PR_FALSE;
 340
 341   nsCString rawArray[NS_ARRAY_LENGTH(kdata)-1];
 342   for (i = 0; i < NS_ARRAY_LENGTH(rawArray); ++i)
 343     rawArray[i].Assign(kdata + i);  // substrings of kdata
 344   return test_basic_array(rawArray, NS_ARRAY_LENGTH(rawArray),
 345                           nsCString("foopy"));
 346 }
 347
 348 //----
 349
 350 typedef nsCOMPtr<nsIFile> FilePointer;
 351
 352 class nsFileNameComparator {
 353   public:
 354     PRBool Equals(const FilePointer &a, const char *b) const {
 355       nsCAutoString name;
 356       a->GetNativeLeafName(name);
 357       return name.Equals(b);
 358     }
 359 };
 360
 361 static PRBool test_comptr_array() {
 362   FilePointer tmpDir;
 363   NS_GetSpecialDirectory(NS_OS_TEMP_DIR, getter_AddRefs(tmpDir));
 364   if (!tmpDir)
 365     return PR_FALSE;
 366   const char *kNames[] = {
 367     "foo.txt", "bar.html", "baz.gif"
 368   };
 369   nsTArray<FilePointer> fileArray;
 370   PRUint32 i;
 371   for (i = 0; i < NS_ARRAY_LENGTH(kNames); ++i) {
 372     FilePointer f;
 373     tmpDir->Clone(getter_AddRefs(f));
 374     if (!f)
 375       return PR_FALSE;
 376     if (NS_FAILED(f->AppendNative(nsDependentCString(kNames[i]))))
 377       return PR_FALSE;
 378     fileArray.AppendElement(f);
 379   }
 380
 381   if (fileArray.IndexOf(kNames[1], 0, nsFileNameComparator()) != 1)
 382     return PR_FALSE;
 383
 384   // It's unclear what 'operator<' means for nsCOMPtr, but whatever...
 385   return test_basic_array(fileArray.Elements(), fileArray.Length(),
 386                           tmpDir);
 387 }
 388
 389 //----
 390
 391 class RefcountedObject {
 392   public:
 393     RefcountedObject() : rc(0) {}
 394     void AddRef() {
 395       ++rc;
 396     }
 397     void Release() {
 398       if (--rc == 0)
 399         delete this;
 400     }
 401     ~RefcountedObject() {}
 402   private:
 403     PRInt32 rc;
 404 };
 405
 406 static PRBool test_refptr_array() {
 407   PRBool rv = PR_TRUE;
 408
 409   nsTArray< nsRefPtr<RefcountedObject> > objArray;
 410
 411   RefcountedObject *a = new RefcountedObject(); a->AddRef();
 412   RefcountedObject *b = new RefcountedObject(); b->AddRef();
 413   RefcountedObject *c = new RefcountedObject(); c->AddRef();
 414
 415   objArray.AppendElement(a);
 416   objArray.AppendElement(b);
 417   objArray.AppendElement(c);
 418
 419   if (objArray.IndexOf(b) != 1)
 420     rv = PR_FALSE;
 421
 422   a->Release();
 423   b->Release();
 424   c->Release();
 425   return rv;
 426 }
 427
 428 //----
 429
 430 static PRBool test_ptrarray() {
 431   nsTPtrArray<PRUint32> ary;
 432   if (ary.SafeElementAt(0) != nsnull)
 433     return PR_FALSE;
 434   if (ary.SafeElementAt(1000) != nsnull)
 435     return PR_FALSE;
 436   PRUint32 a = 10;
 437   ary.AppendElement(&a);
 438   if (*ary[0] != a)
 439     return PR_FALSE;
 440   if (*ary.SafeElementAt(0) != a)
 441     return PR_FALSE;
 442
 443   nsTPtrArray<const PRUint32> cary;
 444   if (cary.SafeElementAt(0) != nsnull)
 445     return PR_FALSE;
 446   if (cary.SafeElementAt(1000) != nsnull)
 447     return PR_FALSE;
 448   const PRUint32 b = 14;
 449   cary.AppendElement(&a);
 450   cary.AppendElement(&b);
 451   if (*cary[0] != a || *cary[1] != b)
 452     return PR_FALSE;
 453   if (*cary.SafeElementAt(0) != a || *cary.SafeElementAt(1) != b)
 454     return PR_FALSE;
 455
 456   return PR_TRUE;
 457 }
 458
 459 //----
 460
 461 // This test relies too heavily on the existence of DebugGetHeader to be
 462 // useful in non-debug builds.
 463 #ifdef DEBUG
 464 static PRBool test_autoarray() {
 465   PRUint32 data[] = {4,6,8,2,4,1,5,7,3};
 466   nsAutoTArray<PRUint32, NS_ARRAY_LENGTH(data)> array;
 467
 468   void* hdr = array.DebugGetHeader();
 469   if (hdr == nsTArray<PRUint32>().DebugGetHeader())
 470     return PR_FALSE;
 471   if (hdr == nsAutoTArray<PRUint32, NS_ARRAY_LENGTH(data)>().DebugGetHeader())
 472     return PR_FALSE;
 473
 474   array.AppendElement(1u);
 475   if (hdr != array.DebugGetHeader())
 476     return PR_FALSE;
 477
 478   array.RemoveElement(1u);
 479   array.AppendElements(data, NS_ARRAY_LENGTH(data));
 480   if (hdr != array.DebugGetHeader())
 481     return PR_FALSE;
 482
 483   array.AppendElement(2u);
 484   if (hdr == array.DebugGetHeader())
 485     return PR_FALSE;
 486
 487   array.Clear();
 488   array.Compact();
 489   if (hdr != array.DebugGetHeader())
 490     return PR_FALSE;
 491   array.AppendElements(data, NS_ARRAY_LENGTH(data));
 492   if (hdr != array.DebugGetHeader())
 493     return PR_FALSE;
 494
 495   nsTArray<PRUint32> array2;
 496   void* emptyHdr = array2.DebugGetHeader();
 497   array.SwapElements(array2);
 498   if (emptyHdr == array.DebugGetHeader())
 499     return PR_FALSE;
 500   if (hdr == array2.DebugGetHeader())
 501     return PR_FALSE;
 502   PRUint32 i;
 503   for (i = 0; i < NS_ARRAY_LENGTH(data); ++i) {
 504     if (array2[i] != data[i])
 505       return PR_FALSE;
 506   }
 507   if (!array.IsEmpty())
 508     return PR_FALSE;
 509
 510   array.Compact();
 511   array.AppendElements(data, NS_ARRAY_LENGTH(data));
 512   PRUint32 data3[] = {5, 7, 11};
 513   nsAutoTArray<PRUint32, NS_ARRAY_LENGTH(data3)> array3;
 514   array3.AppendElements(data3, NS_ARRAY_LENGTH(data3));
 515   array.SwapElements(array3);
 516   for (i = 0; i < NS_ARRAY_LENGTH(data); ++i) {
 517     if (array3[i] != data[i])
 518       return PR_FALSE;
 519   }
 520   for (i = 0; i < NS_ARRAY_LENGTH(data3); ++i) {
 521     if (array[i] != data3[i])
 522       return PR_FALSE;
 523   }
 524
 525   return PR_TRUE;
 526 }
 527 #endif
 528
 529 //----
 530
 531 // IndexOf used to potentially scan beyond the end of the array.  Test for
 532 // this incorrect behavior by adding a value (5), removing it, then seeing
 533 // if IndexOf finds it.
 534 static PRBool test_indexof() {
 535   nsTArray<int> array;
 536   array.AppendElement(0);
 537   // add and remove the 5
 538   array.AppendElement(5);
 539   array.RemoveElementAt(1);
 540   // we should not find the 5!
 541   return array.IndexOf(5, 1) == array.NoIndex;
 542 }
 543
 544 //----
 545
 546 template <class Array>
 547 static PRBool is_heap(const Array& ary, PRUint32 len) {
 548   PRUint32 index = 1;
 549   while (index < len) {
 550     if (ary[index] > ary[(index - 1) >> 1])
 551       return PR_FALSE;
 552     index++;
 553   }
 554   return PR_TRUE;
 555 }
 556
 557 static PRBool test_heap() {
 558   const int data[] = {4,6,8,2,4,1,5,7,3};
 559   nsTArray<int> ary;
 560   ary.AppendElements(data, NS_ARRAY_LENGTH(data));
 561   // make a heap and make sure it's a heap
 562   ary.MakeHeap();
 563   if (!is_heap(ary, NS_ARRAY_LENGTH(data)))
 564     return PR_FALSE;
 565   // pop the root and make sure it's still a heap
 566   int root = ary[0];
 567   ary.PopHeap();
 568   if (!is_heap(ary, NS_ARRAY_LENGTH(data) - 1))
 569     return PR_FALSE;
 570   // push the previously poped value back on and make sure it's still a heap
 571   ary.PushHeap(root);
 572   if (!is_heap(ary, NS_ARRAY_LENGTH(data)))
 573     return PR_FALSE;
 574   // make sure the heap looks like what we expect
 575   const int expected_data[] = {8,7,5,6,4,1,4,2,3};
 576   PRUint32 index;
 577   for (index = 0; index < NS_ARRAY_LENGTH(data); index++)
 578     if (ary[index] != expected_data[index])
 579       return PR_FALSE;
 580   return PR_TRUE;
 581 }
 582
 583 //----
 584
 585 typedef PRBool (*TestFunc)();
 586 #define DECL_TEST(name) { #name, name }
 587
 588 static const struct Test {
 589   const char* name;
 590   TestFunc    func;
 591 } tests[] = {
 592   DECL_TEST(test_int_array),
 593   DECL_TEST(test_int64_array),
 594   DECL_TEST(test_char_array),
 595   DECL_TEST(test_uint32_array),
 596   DECL_TEST(test_object_array),
 597   DECL_TEST(test_string_array),
 598   DECL_TEST(test_comptr_array),
 599   DECL_TEST(test_refptr_array),
 600   DECL_TEST(test_ptrarray),
 601 #ifdef DEBUG
 602   DECL_TEST(test_autoarray),
 603 #endif
 604   DECL_TEST(test_indexof),
 605   DECL_TEST(test_heap),
 606   { nsnull, nsnull }
 607 };
 608
 609 }
 610
 611 using namespace TestTArray;
 612
 613 int main(int argc, char **argv) {
 614   int count = 1;
 615   if (argc > 1)
 616     count = atoi(argv[1]);
 617
 618   if (NS_FAILED(NS_InitXPCOM2(nsnull, nsnull, nsnull)))
 619     return -1;
 620
 621   while (count--) {
 622     for (const Test* t = tests; t->name != nsnull; ++t) {
 623       printf("%25s : %s\n", t->name, t->func() ? "SUCCESS" : "FAILURE");
 624     }
 625   }
 626
 627   NS_ShutdownXPCOM(nsnull);
 628   return 0;
 629 }