rb-test.c

Mon, 17 Jan 2005 22:02:09 +0100

author
tuomov
date
Mon, 17 Jan 2005 22:02:09 +0100
changeset 85
9f94b2e96e3b
parent 65
58e382ae97cd
permissions
-rw-r--r--

trunk: changeset 1934
Fixed everything that requires locale stuff to check CF_NO_LOCALE.

65
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
1 /*
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
2 Generic C code for red-black trees.
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
3 Copyright (C) 2000 James S. Plank
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
4
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
5 This library is free software; you can redistribute it and/or
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
6 modify it under the terms of the GNU Lesser General Public
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
7 License as published by the Free Software Foundation; either
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
8 version 2.1 of the License, or (at your option) any later version.
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
9
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
10 This library is distributed in the hope that it will be useful,
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
13 Lesser General Public License for more details.
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
14
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
15 You should have received a copy of the GNU Lesser General Public
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
16 License along with this library; if not, write to the Free Software
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
18 */
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
19
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
20 /* Revision 1.2. Jim Plank */
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
21
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
22 #include "rb.h"
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
23 #include <stdio.h>
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
24
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
25 /* an example -- this allocates a red-black tree for integers. For a
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
26 * user-specified number of iterations, it does the following:
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
27
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
28 * delete a random element in the tree.
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
29 * make two new random elements, and insert them into the tree
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
30
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
31 * At the end, it prints the sorted list of elements, and then prints
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
32 * stats of the number of black nodes in any path in the tree, and
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
33 * the minimum and maximum path lengths.
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
34
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
35 * Rb_find_ikey and rb_inserti could have been used, but instead
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
36 * rb_find_gkey and rb_insertg were used to show how they work.
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
37
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
38 */
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
39
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
40 int icomp(char *i, char *j)
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
41 {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
42 int I, J;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
43
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
44 I = (int) i;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
45 J = (int) j;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
46 if (I == J) return 0;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
47 if (I > J) return -1; else return 1;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
48 }
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
49
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
50 main(int argc, char **argv)
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
51 {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
52 int i, j, tb, nb, mxp, mnp, p;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
53 int iterations;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
54 Rb_node argt, t;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
55 int *a;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
56
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
57 if (argc != 2) {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
58 fprintf(stderr, "usage: main #iterations\n");
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
59 exit(1);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
60 }
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
61 argt = make_rb();
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
62 srandom(time(0));
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
63 iterations = atoi(argv[1]);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
64 a = (int *) malloc (iterations*sizeof(int));
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
65
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
66 for (i = 0; i < atoi(argv[1]); i++) {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
67 if (i > 0) {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
68 j = random()%i;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
69
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
70 rb_delete_node(rb_find_gkey(argt, (char *) (a[j]), icomp));
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
71 a[j] = random() % 1000;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
72 rb_insertg(argt, (char *) (a[j]), NULL, icomp);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
73 }
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
74 a[i] = random() % 1000;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
75 rb_insertg(argt, (char *) (a[i]), NULL, icomp);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
76 }
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
77 tb = 0;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
78 mxp = 0;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
79 mnp = 0;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
80 rb_traverse(t, argt) {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
81 printf("%d ", t->k.ikey);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
82 nb = rb_nblack(t);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
83 p = rb_plength(t);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
84 if (tb == 0) {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
85 tb = nb;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
86 } else if (tb != nb) {
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
87 printf("Conflict: tb=%d, nb=%d\n", tb, nb);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
88 exit(1);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
89 }
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
90 mxp = (mxp == 0 || mxp < p) ? p : mxp;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
91 mnp = (mnp == 0 || mxp > p) ? p : mnp;
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
92 }
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
93 printf("\n");
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
94
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
95 printf("Nblack = %d\n", tb);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
96 printf("Max = %d\n", mxp);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
97 printf("Min = %d\n", mnp);
58e382ae97cd trunk: changeset 1368
tuomov
parents:
diff changeset
98 }

mercurial