Mercurial > data_structures
view src/btree_mem_test.c @ 23:36018adade6d
valgrind reporting no memory leaks now.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Fri, 19 Oct 2012 18:19:39 -0500 |
| parents | ce502d2caaea |
| children | f27bdd5d40d0 |
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <limits.h>
6 #include "btree_mem.h"
9 #define MIN_DEGREE 2
10 #define MAX_LINE 1024
12 #ifdef DEBUG
13 #define DEBUG_BLOCK(x) x
14 #else
15 #define DEBUG_BLOCK(x)
16 #endif
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 }
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 }
40 ////////////////////////////////////////////////////////////////////////////////
41 void
42 wackify_data(int depth, void const * const key, void * data)
43 {
44 strcpy(data, "wack");
45 }
47 ////////////////////////////////////////////////////////////////////////////////
48 void
49 wackify_tree(struct btree_mem * bt)
50 {
51 btree_mem_walk_inorder(bt, wackify_data);
52 }
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 }
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 }
78 ////////////////////////////////////////////////////////////////////////////////
79 int
80 main(int argc, char ** argv)
81 {
82 int degree = MIN_DEGREE;
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 }
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 }
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);
127 if (*ip < minkey) minkey = *ip;
128 if (*ip > maxkey) maxkey = *ip;
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);
141 int * k;
142 char * d;
143 for (int key = minkey; key <= maxkey; key++)
144 {
145 if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
146 {
147 printf("not found!\n");
148 }
149 else
150 {
151 if (NULL == k)
152 printf("k is NULL\n");
153 else
154 free(k);
156 if (NULL == d)
157 printf("d is NULL\n");
158 else
159 free(d);
160 }
161 print_tree(bt);
162 }
165 btree_mem_delete(bt);
167 exit(EXIT_SUCCESS);
168 }