← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/xpcom/tests/TestVoidBTree.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

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