xpcom/tests/TestVoidBTree.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is mozilla.org Code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1999
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either of the GNU General Public License Version 2 or later (the "GPL"),
  26  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 #include <stdlib.h>
  39 #include <stdio.h>
  40 #include "nsVoidBTree.h"
  41 #include "nsVoidArray.h"
  42
  43 #define COUNT 1024
  44 #define POINTER(i) reinterpret_cast<void*>(4 + 4 * (i))
  45
  46 static PRBool
  47 Equal(const nsVoidArray& aControl, const nsVoidBTree& aTest)
  48 {
  49     if (aControl.Count() != aTest.Count()) {
  50         printf("counts not equal; ");
  51         return PR_FALSE;
  52     }
  53
  54     for (PRInt32 i = aControl.Count() - 1; i >= 0; --i) {
  55         if (aControl[i] != aTest[i]) {
  56             printf("element %d differs; ", i);
  57             return PR_FALSE;
  58         }
  59     }
  60
  61     return PR_TRUE;
  62 }
  63
  64
  65 static void
  66 CheckForwardEnumeration(const nsVoidArray& aControl, const nsVoidBTree& aTest)
  67 {
  68     PRInt32 index = 0;
  69
  70     nsVoidBTree::ConstIterator last = aTest.Last();
  71     for (nsVoidBTree::ConstIterator element = aTest.First(); element != last; ++element, ++index) {
  72         if (*element != aControl[index]) {
  73             printf("failed forward enumeration\n");
  74             exit(-1);
  75         }
  76     }
  77
  78     if (index != aControl.Count()) {
  79         printf("erratic termination during forward enumeration\n");
  80         exit(-1);
  81     }
  82 }
  83
  84 static void
  85 CheckBackwardEnumeration(const nsVoidArray& aControl, const nsVoidBTree& aTest)
  86 {
  87     PRInt32 index = aControl.Count();
  88     nsVoidBTree::ConstIterator first = aTest.First();
  89     nsVoidBTree::ConstIterator element = aTest.Last();
  90
  91     if (first != element) {
  92         do {
  93             if (*--element != aControl[--index]) {
  94                 printf("failed backward enumeration\n");
  95                 exit(-1);
  96             }
  97         } while (element != first);
  98     }
  99
 100     if (index != 0) {
 101         printf("erratic termination during backward enumeration\n");
 102         exit(-1);
 103     }
 104 }
 105
 106 int main(int argc, char* argv[])
 107 {
 108     nsVoidBTree btree;
 109
 110     PRInt32 i;
 111
 112     //----------------------------------------
 113     // Tail fill
 114     for (i = 0; i < COUNT; ++i)
 115         btree.InsertElementAt(reinterpret_cast<void*>(POINTER(i)), i);
 116
 117     for (i = 0; i < COUNT; ++i) {
 118         if (btree[i] != POINTER(i)) {
 119             printf("tail fill failed\n");
 120             return -1;
 121         }
 122     }
 123
 124     printf("tail fill succeeded\n");
 125
 126     //----------------------------------------
 127     // Tail empty
 128     for (i = COUNT - 1; i >= 0; --i)
 129         btree.RemoveElementAt(i);
 130
 131     if (btree.Count() != 0) {
 132         printf("tail empty failed\n");
 133         return -1;
 134     }
 135
 136     printf("tail empty succeeded\n");
 137
 138     // N.B. no intervening Clear() to verify that we handle the re-use
 139     // case.
 140
 141     //----------------------------------------
 142     // Front fill
 143     for (i = 0; i < COUNT; ++i)
 144         btree.InsertElementAt(POINTER(i), 0);
 145
 146     for (i = 0; i < COUNT; ++i) {
 147         if (btree[COUNT - (i + 1)] != POINTER(i)) {
 148             printf("simple front fill failed\n");
 149             return -1;
 150         }
 151     }
 152
 153     printf("front fill succeeded\n");
 154
 155     //----------------------------------------
 156     // Front empty
 157     for (i = COUNT - 1; i >= 0; --i)
 158         btree.RemoveElementAt(0);
 159
 160     if (btree.Count() != 0) {
 161         printf("front empty failed\n");
 162         return -1;
 163     }
 164
 165     printf("front empty succeeded\n");
 166     fflush(stdout);
 167
 168     //----------------------------------------
 169     // Test boundary conditions with small btree
 170
 171     {
 172         printf("small btree boundary conditions ");
 173         fflush(stdout);
 174
 175         nsVoidArray control;
 176         btree.Clear();
 177
 178         CheckBackwardEnumeration(control, btree);
 179         CheckForwardEnumeration(control, btree);
 180
 181         btree.AppendElement(POINTER(0));
 182         control.AppendElement(POINTER(0));
 183
 184         CheckBackwardEnumeration(control, btree);
 185         CheckForwardEnumeration(control, btree);
 186
 187         btree.AppendElement(POINTER(1));
 188         control.AppendElement(POINTER(1));
 189
 190         CheckBackwardEnumeration(control, btree);
 191         CheckForwardEnumeration(control, btree);
 192
 193         btree.RemoveElementAt(0);
 194         btree.RemoveElementAt(0);
 195         control.RemoveElementAt(0);
 196         control.RemoveElementAt(0);
 197
 198         CheckBackwardEnumeration(control, btree);
 199         CheckForwardEnumeration(control, btree);
 200
 201         printf("succeeded\n");
 202     }
 203
 204     //----------------------------------------
 205     // Iterator
 206     {
 207         nsVoidArray control;
 208         btree.Clear();
 209
 210         // Fill
 211         for (i = 0; i < COUNT; ++i) {
 212             PRInt32 slot = i ? rand() % i : 0;
 213
 214             btree.InsertElementAt(POINTER(i), slot);
 215             control.InsertElementAt(POINTER(i), slot);
 216
 217             if (! Equal(control, btree)) {
 218                 printf("failed\n");
 219                 return -1;
 220             }
 221         }
 222
 223         for (nsVoidBTree::Iterator m = btree.First(); m != btree.Last(); ++m) {
 224             nsVoidBTree::Iterator n;
 225             for (n = m, ++n; n != btree.Last(); ++n) {
 226                 if (*m > *n) {
 227                     void* tmp = *m;
 228                     *m = *n;
 229                     *n = tmp;
 230                 }
 231             }
 232         }
 233
 234         nsVoidBTree::Iterator el;
 235         for (el = btree.First(), i = 0; el != btree.Last(); ++el, ++i) {
 236             if (*el != POINTER(i)) {
 237                 printf("bubble sort failed\n");
 238                 return -1;
 239             }
 240         }
 241
 242         printf("iteration succeeded\n");
 243     }
 244
 245     //----------------------------------------
 246     // Random hammering
 247
 248     printf("random fill/empty: ");
 249
 250     for (PRInt32 iter = 10; iter >= 1; --iter) {
 251         printf("%d ", iter);
 252         fflush(stdout);
 253
 254         nsVoidArray control;
 255         btree.Clear();
 256
 257         // Fill
 258         for (i = 0; i < COUNT; ++i) {
 259             PRInt32 slot = i ? rand() % i : 0;
 260
 261             btree.InsertElementAt(POINTER(i), slot);
 262             control.InsertElementAt(POINTER(i), slot);
 263
 264             if (! Equal(control, btree)) {
 265                 printf("failed\n");
 266                 return -1;
 267             }
 268         }
 269
 270         // IndexOf
 271         for (i = 0; i < COUNT; ++i) {
 272             void* element = control[i];
 273             if (btree.IndexOf(element) != i) {
 274                 printf("failed IndexOf at %d\n", i);
 275                 return -1;
 276             }
 277         }
 278
 279         // Backward enumeration
 280         CheckBackwardEnumeration(control, btree);
 281
 282         // Forward enumeration
 283         CheckForwardEnumeration(control, btree);
 284
 285         // Empty
 286         for (i = COUNT - 1; i >= 0; --i) {
 287             PRInt32 slot = i ? rand() % i : 0;
 288
 289             btree.RemoveElementAt(slot);
 290             control.RemoveElementAt(slot);
 291
 292             if (! Equal(control, btree)) {
 293                 printf("failed\n");
 294                 return -1;
 295             }
 296         }
 297     }
 298
 299     printf("succeeded\n");
 300
 301     return 0;
 302 }