Mercurial > data_structures
view src/btree_mem_test.c @ 20:66aecb6a0057
making progress
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Thu, 18 Oct 2012 20:08:51 -0500 |
| parents | 0bf94d0ed0b0 |
| children | ce502d2caaea |
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.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 i;
105 char s[MAX_LINE+1];
106 while (1 == scanf("%d ", &i))
107 {
108 int * ip = malloc(sizeof(int));
109 if (NULL == ip)
110 {
111 perror("malloc");
112 exit(EXIT_FAILURE);
113 }
114 *ip = i;
115 fgets(s, MAX_LINE, stdin);
116 if (s[strlen(s)-1] != '\n')
117 {
118 fprintf(stderr, "input line exceeds maximum length of %d\n", MAX_LINE);
119 exit(EXIT_FAILURE);
120 }
121 s[strlen(s)-1] = '\0';
122 char * data = (s == NULL) ? NULL : strdup(s);
123 if (NULL == btree_mem_insert(bt, ip, data))
124 {
125 fprintf(stderr, "btree_mem_insert failed\n");
126 exit(EXIT_FAILURE);
127 }
128 DEBUG_BLOCK( print_tree(bt); )
129 }
130 // wackify_tree(bt);
131 print_tree(bt);
133 int * k;
134 char * d;
135 int key = 5;
136 printf("removing %d\n", key);
137 if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
138 {
139 printf("not found!\n");
140 }
141 else
142 {
143 if (NULL == k)
144 printf("k is NULL\n");
145 else
146 free(k);
148 if (NULL == d)
149 printf("d is NULL\n");
150 else
151 free(d);
152 }
153 print_tree(bt);
156 exit(EXIT_SUCCESS);
157 }