Back to index

lightning-sunbird  0.9+nobinonly
TestVoidBTree.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org Code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1999
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 #include <stdlib.h>
00039 #include <stdio.h>
00040 #include "nsVoidBTree.h"
00041 #include "nsVoidArray.h"
00042 
00043 #define COUNT 1024
00044 #define POINTER(i) NS_REINTERPRET_CAST(void*, 4 + 4 * (i))
00045 
00046 static PRBool
00047 Equal(const nsVoidArray& aControl, const nsVoidBTree& aTest)
00048 {
00049     if (aControl.Count() != aTest.Count()) {
00050         printf("counts not equal; ");
00051         return PR_FALSE;
00052     }
00053 
00054     for (PRInt32 i = aControl.Count() - 1; i >= 0; --i) {
00055         if (aControl[i] != aTest[i]) {
00056             printf("element %d differs; ", i);
00057             return PR_FALSE;
00058         }
00059     }
00060 
00061     return PR_TRUE;
00062 }
00063 
00064 
00065 static void
00066 CheckForwardEnumeration(const nsVoidArray& aControl, const nsVoidBTree& aTest)
00067 {
00068     PRInt32 index = 0;
00069 
00070     nsVoidBTree::ConstIterator last = aTest.Last();
00071     for (nsVoidBTree::ConstIterator element = aTest.First(); element != last; ++element, ++index) {
00072         if (*element != aControl[index]) {
00073             printf("failed forward enumeration\n");
00074             exit(-1);
00075         }
00076     }
00077 
00078     if (index != aControl.Count()) {
00079         printf("erratic termination during forward enumeration\n");
00080         exit(-1);
00081     }
00082 }
00083 
00084 static void
00085 CheckBackwardEnumeration(const nsVoidArray& aControl, const nsVoidBTree& aTest)
00086 {
00087     PRInt32 index = aControl.Count();
00088     nsVoidBTree::ConstIterator first = aTest.First();
00089     nsVoidBTree::ConstIterator element = aTest.Last();
00090 
00091     if (first != element) {
00092         do {
00093             if (*--element != aControl[--index]) {
00094                 printf("failed backward enumeration\n");
00095                 exit(-1);
00096             }
00097         } while (element != first);
00098     }
00099 
00100     if (index != 0) {
00101         printf("erratic termination during backward enumeration\n");
00102         exit(-1);
00103     }
00104 }
00105 
00106 int main(int argc, char* argv[])
00107 {
00108     nsVoidBTree btree;
00109 
00110     PRInt32 i;
00111 
00112     //----------------------------------------
00113     // Tail fill
00114     for (i = 0; i < COUNT; ++i)
00115         btree.InsertElementAt(NS_REINTERPRET_CAST(void*, POINTER(i)), i);
00116 
00117     for (i = 0; i < COUNT; ++i) {
00118         if (btree[i] != POINTER(i)) {
00119             printf("tail fill failed\n");
00120             return -1;
00121         }
00122     }
00123 
00124     printf("tail fill succeeded\n");
00125 
00126     //----------------------------------------
00127     // Tail empty
00128     for (i = COUNT - 1; i >= 0; --i)
00129         btree.RemoveElementAt(i);
00130 
00131     if (btree.Count() != 0) {
00132         printf("tail empty failed\n");
00133         return -1;
00134     }
00135 
00136     printf("tail empty succeeded\n");
00137 
00138     // N.B. no intervening Clear() to verify that we handle the re-use
00139     // case.
00140 
00141     //----------------------------------------
00142     // Front fill
00143     for (i = 0; i < COUNT; ++i)
00144         btree.InsertElementAt(POINTER(i), 0);
00145 
00146     for (i = 0; i < COUNT; ++i) {
00147         if (btree[COUNT - (i + 1)] != POINTER(i)) {
00148             printf("simple front fill failed\n");
00149             return -1;
00150         }
00151     }
00152 
00153     printf("front fill succeeded\n");
00154 
00155     //----------------------------------------
00156     // Front empty
00157     for (i = COUNT - 1; i >= 0; --i)
00158         btree.RemoveElementAt(0);
00159 
00160     if (btree.Count() != 0) {
00161         printf("front empty failed\n");
00162         return -1;
00163     }
00164 
00165     printf("front empty succeeded\n");
00166     fflush(stdout);
00167 
00168     //----------------------------------------
00169     // Test boundary conditions with small btree
00170 
00171     {
00172         printf("small btree boundary conditions ");
00173         fflush(stdout);
00174 
00175         nsVoidArray control;
00176         btree.Clear();
00177 
00178         CheckBackwardEnumeration(control, btree);
00179         CheckForwardEnumeration(control, btree);
00180 
00181         btree.AppendElement(POINTER(0));
00182         control.AppendElement(POINTER(0));
00183 
00184         CheckBackwardEnumeration(control, btree);
00185         CheckForwardEnumeration(control, btree);
00186 
00187         btree.AppendElement(POINTER(1));
00188         control.AppendElement(POINTER(1));
00189 
00190         CheckBackwardEnumeration(control, btree);
00191         CheckForwardEnumeration(control, btree);
00192 
00193         btree.RemoveElementAt(0);
00194         btree.RemoveElementAt(0);
00195         control.RemoveElementAt(0);
00196         control.RemoveElementAt(0);
00197 
00198         CheckBackwardEnumeration(control, btree);
00199         CheckForwardEnumeration(control, btree);
00200 
00201         printf("succeeded\n");
00202     }
00203 
00204     //----------------------------------------
00205     // Iterator
00206     {
00207         nsVoidArray control;
00208         btree.Clear();
00209 
00210         // Fill
00211         for (i = 0; i < COUNT; ++i) {
00212             PRInt32 slot = i ? rand() % i : 0;
00213 
00214             btree.InsertElementAt(POINTER(i), slot);
00215             control.InsertElementAt(POINTER(i), slot);
00216 
00217             if (! Equal(control, btree)) {
00218                 printf("failed\n");
00219                 return -1;
00220             }
00221         }
00222 
00223         for (nsVoidBTree::Iterator m = btree.First(); m != btree.Last(); ++m) {
00224             nsVoidBTree::Iterator n;
00225             for (n = m, ++n; n != btree.Last(); ++n) {
00226                 if (*m > *n) {
00227                     void* tmp = *m;
00228                     *m = *n;
00229                     *n = tmp;
00230                 }
00231             }
00232         }
00233 
00234         nsVoidBTree::Iterator el;
00235         for (el = btree.First(), i = 0; el != btree.Last(); ++el, ++i) {
00236             if (*el != POINTER(i)) {
00237                 printf("bubble sort failed\n");
00238                 return -1;
00239             }
00240         }
00241 
00242         printf("iteration succeeded\n");
00243     }
00244 
00245     //----------------------------------------
00246     // Random hammering
00247 
00248     printf("random fill/empty: ");
00249 
00250     for (PRInt32 iter = 10; iter >= 1; --iter) {
00251         printf("%d ", iter);
00252         fflush(stdout);
00253 
00254         nsVoidArray control;
00255         btree.Clear();
00256 
00257         // Fill
00258         for (i = 0; i < COUNT; ++i) {
00259             PRInt32 slot = i ? rand() % i : 0;
00260 
00261             btree.InsertElementAt(POINTER(i), slot);
00262             control.InsertElementAt(POINTER(i), slot);
00263 
00264             if (! Equal(control, btree)) {
00265                 printf("failed\n");
00266                 return -1;
00267             }
00268         }
00269 
00270         // IndexOf
00271         for (i = 0; i < COUNT; ++i) {
00272             void* element = control[i];
00273             if (btree.IndexOf(element) != i) {
00274                 printf("failed IndexOf at %d\n", i);
00275                 return -1;
00276             }
00277         }
00278 
00279         // Backward enumeration
00280         CheckBackwardEnumeration(control, btree);
00281                
00282         // Forward enumeration
00283         CheckForwardEnumeration(control, btree);
00284 
00285         // Empty
00286         for (i = COUNT - 1; i >= 0; --i) {
00287             PRInt32 slot = i ? rand() % i : 0;
00288 
00289             btree.RemoveElementAt(slot);
00290             control.RemoveElementAt(slot);
00291 
00292             if (! Equal(control, btree)) {
00293                 printf("failed\n");
00294                 return -1;
00295             }
00296         }
00297     }
00298 
00299     printf("succeeded\n");
00300 
00301     return 0;
00302 }