Mercurial > data_structures

view src/btree_mem_test.c @ 24:f27bdd5d40d0

find changesets by author, revision, files, or words in the commit message
Ran more tests. Found another leak. Fixed it. Now it's really good. for (( MinDeg=2; MinDeg<=100; MinDeg++ )) ; do echo MinDeg 101 ; numwords 1000 | rev | valgrind --tool=memcheck --leak-check=full --show-reachable=yes ./btree_mem_test 101 2>&1 | grep "ERROR SUMMARY" ; done
author Eris Caffee <discordia@eldalin.com>
date Fri, 19 Oct 2012 19:42:17 -0500
parents 36018adade6d
children
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <limits.h>
5
6 #include "btree_mem.h"
7
8
9 #define MIN_DEGREE 2
10 #define MAX_LINE 1024
11
12 #ifdef DEBUG
13 #define DEBUG_BLOCK(x) x
14 #else
15 #define DEBUG_BLOCK(x)
16 #endif
17
18
19 ////////////////////////////////////////////////////////////////////////////////
20 int
21 key_cmp(void * a, void * b)
22 {
23 if (*((int *) a) < *((int *) b))
24 return -1;
25 else if (*((int *) a) == *((int *) b))
26 return 0;
27 return 1;
28 }
29
30
31 ////////////////////////////////////////////////////////////////////////////////
32 void
33 print_data(int depth, void const * const key, void * data)
34 {
35 for (int i = 0; i < depth; i++)
36 printf("\t");
37 printf("%d %s\n", *((int*)key), (char *) data);
38 }
39
40 ////////////////////////////////////////////////////////////////////////////////
41 void
42 wackify_data(int depth, void const * const key, void * data)
43 {
44 strcpy(data, "wack");
45 }
46
47 ////////////////////////////////////////////////////////////////////////////////
48 void
49 wackify_tree(struct btree_mem * bt)
50 {
51 btree_mem_walk_inorder(bt, wackify_data);
52 }
53
54 ////////////////////////////////////////////////////////////////////////////////
55 void
56 print_tree(struct btree_mem * bt)
57 {
58 printf("==================================\n");
59 btree_mem_dump(bt, print_data);
60 printf("==================================\n");
61 }
62
63 ////////////////////////////////////////////////////////////////////////////////
64 void
65 usage(char * progname)
66 {
67 printf("Usage: %s [mindegree]\n"
68 "mindegree is the minimum degree of the B-Tree to create. (As defined"
69 "by Cormen, et al., Introduction to Algorithms, Ch. 18.) The default"
70 "value is %d\n"
71 "\n"
72 "Data for the tree will be read from stdin. The first field on the line"
73 "should be an integer and will be used as the key. The remainder of the"
74 "line will be read as a single string that will be stored as the data."
75 , progname, MIN_DEGREE);
76 }
77
78 ////////////////////////////////////////////////////////////////////////////////
79 int
80 main(int argc, char ** argv)
81 {
82 int degree = MIN_DEGREE;
83
84 if (argc > 1)
85 {
86 char * end;
87 degree = strtol(argv[1], &end, 10);
88 if (*end != '\0')
89 {
90 fprintf(stderr, "Degree must be an integer greater than or equal to %d\n", MIN_DEGREE);
91 usage(argv[0]);
92 exit(EXIT_FAILURE);
93 }
94 }
95
96 struct btree_mem * bt = btree_mem_new(degree, key_cmp);
97 if (NULL == bt)
98 {
99 fprintf(stderr, "Unable to create new btree_mem\n");
100 exit(EXIT_FAILURE);
101 }
102
103 DEBUG_BLOCK( print_tree(bt); );
104 int minkey = INT_MAX;
105 int maxkey = INT_MIN;
106 int i;
107 char s[MAX_LINE+1];
108 while (1 == scanf("%d ", &i))
109 {
110 int * ip = malloc(sizeof(int));
111 if (NULL == ip)
112 {
113 perror("malloc");
114 exit(EXIT_FAILURE);
115 }
116 *ip = i;
117 fgets(s, MAX_LINE, stdin);
118 if (s[strlen(s)-1] != '\n')
119 {
120 fprintf(stderr, "input line exceeds maximum length of %d\n", MAX_LINE);
121 exit(EXIT_FAILURE);
122 }
123 s[strlen(s)-1] = '\0';
124 char * data = (s == NULL) ? NULL : strdup(s);
125
126
127 if (*ip < minkey) minkey = *ip;
128 if (*ip > maxkey) maxkey = *ip;
129
130 printf("Inserting k %p, d %p\n", ip, data);
131 if (NULL == btree_mem_insert(bt, ip, data))
132 {
133 fprintf(stderr, "btree_mem_insert failed\n");
134 exit(EXIT_FAILURE);
135 }
136 DEBUG_BLOCK( print_tree(bt); )
137 }
138 // wackify_tree(bt);
139 print_tree(bt);
140
141
142 printf("Deleting tree\n");
143 int * k;
144 char * d;
145 for (int key = minkey; key <= maxkey; key++)
146 {
147 if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
148 {
149 printf("not found!\n");
150 }
151 else
152 {
153 if (NULL == k)
154 printf("k is NULL\n");
155 else
156 free(k);
157
158 if (NULL == d)
159 printf("d is NULL\n");
160 else
161 free(d);
162 }
163 }
164 print_tree(bt);
165
166 btree_mem_delete(bt);
167
168 exit(EXIT_SUCCESS);
169 }