· 7 years ago · Dec 21, 2018, 05:02 PM
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX_STRING_SIZE 100
6#define HASHSIZE 101 /* comment here */
7#define ALLOCSIZE 1000 /*size of available space*/
8#define N 1000 // max number of lines to be read
9#define VALLEN 100 //max number of chars for description
10#define MAXC 1024
11#define MAX 1000
12
13static char allocbuf[ALLOCSIZE]; /* storage for alloc*/
14static char *allocp = allocbuf; /* next free position*/
15static struct map *hashtab[HASHSIZE]; /* pointer table */
16unsigned hash(char *); /* hashing function: form hash value for string s. used by both lookup and install*/
17char *strdup(char *);
18
19//char *alloc(int n) { /* return a pointer to n characters*/
20// if (allocbuf + ALLOCSIZE - allocp >= n) { /*it fits*/
21// allocp += n;
22// return allocp - n; /*old p*/
23// } else /*not enough room*/
24// return 0;
25//}
26
27typedef struct map { /* creating a map structure */
28 struct map *next;
29 char *value;
30 char *KEY;
31} map;
32
33typedef struct node {
34 int KEY;
35 char *value;
36 int node_count;
37 struct node *left, *right;
38 int unique_count;
39} node;
40
41// A utility function to create a new BST node
42
43node *newNode(int KEY, char *value) {
44 //Allocate a new overall structure
45 node *temp = (node *) malloc(sizeof (node));
46
47 //Copy the integer key
48 temp->KEY = KEY;
49 temp->value = value;
50
51 temp->left = temp->right = NULL;
52 temp->node_count = 1;
53 return temp;
54}
55
56// A utility function to do inorder traversal of BST
57
58void inorder(node *root, int *pin_count) {
59 if (root != NULL) {
60 inorder(root->left, pin_count);
61 printf("%d(%d)\n", root->KEY, root->node_count);
62 inorder(root->right, pin_count);
63 }
64}
65
66/* A utility function to find deepest keys of BST */
67
68/* This is done by extracting the key with the lowest count,
69since count member of node struct gets incremented each time it is read. */
70void unique_key(node *root, int *p_unique_count, int p_unique_key_arr[], char *p_value_arr[]) {
71 int count = 0;
72 char *p;
73
74 if (root != NULL) {
75 unique_key(root->left, p_unique_count, p_unique_key_arr, p_value_arr);
76 if (root->node_count == 1) {
77
78 if ((p = malloc(strlen(root[count].value) + 1)) == NULL) {
79 return;
80 } else {
81 root[count].unique_count = *p_unique_count;
82 p_unique_key_arr[*p_unique_count] = root[count].KEY;
83
84 strcpy(p, root[count].value);
85 p_value_arr[*p_unique_count] = p;
86 //printf("%s\n",p_value_arr[*p_unique_count][*p_unique_count]);
87
88 printf("%d(%d) -> %s %d\n", root->KEY, root->node_count, root->value, root->unique_count);
89 (*p_unique_count)++;
90 count++;
91 }
92 }
93 unique_key(root->right, p_unique_count, p_unique_key_arr, p_value_arr);
94 }
95}
96
97/* A utility function to insert a new node with given key in BST */
98node* insert_node(node* node, int key, char *value) {
99 /* If the tree is empty, return a new node */
100 if (node == NULL)
101 return newNode(key, value);
102
103 // If key already exists in BST, icnrement count and return
104 if (key == node->KEY) {
105 (node->node_count)++;
106 // return node;
107 }
108
109 /* Otherwise, recur down the tree */
110 if (key < node->KEY)
111 node->left = insert_node(node->left, key, value);
112 else
113 node->right = insert_node(node->right, key, value);
114
115 /* return the (unchanged) node pointer */
116 return node;
117}
118
119/* lookup function takes a pointer to char - s as an argument and returns a pointer to map structure */
120map *lookup(char *s) {
121 map *np;
122
123 for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
124 if (strcmp(s, np->KEY) == 0) {
125 return np;
126 }
127 }
128 return NULL;
129}
130
131/* insert function takes a pointer to a char - KEY, value and returns a pointer to map structure */
132map *insert_map(char* KEY, char* value) {
133 /* install: put (name, defn) in */
134 /* Install uses lookup to determine whether the KEY being installed
135 is already present. Proceeds to create a new entry or update*/
136 map *np;
137 unsigned hashval;
138
139 if ((np = lookup(KEY)) == NULL) {
140 np = (map *) malloc(sizeof (*np));
141 if (np == NULL || (np->KEY = strdup(KEY)) == NULL) {
142 return NULL;
143 }
144 hashval = hash(KEY);
145 np->next = hashtab[hashval];
146 hashtab[hashval] = np;
147 } else {
148 free((void *) np->value);
149 }
150 if ((np->value = strdup(value)) == NULL) { //map has no field value
151 return NULL;
152 }
153
154 return np;
155}
156
157/* uninstall function removes a key and calendar from table maintained by lookup and install */
158map *remove_map(char *KEY) {
159 map *found;
160
161 found = lookup(KEY);
162
163 if (found == NULL) /* not found and nothing to do */ {
164 //printf("%s - Nothing to delete.\n", KEY);
165 return NULL;
166 } else {
167 if (found->next != NULL) {
168 found->next = found->next->next;
169 found = found->next;
170 } else {
171 hashtab[hash(KEY)] = NULL;
172 free((void *) found);
173 }
174 }
175 return found;
176}
177
178/* simple implementation of strdup*/
179char *strdup(char *s) {
180
181 char *d = (char *) malloc(strlen(s) + 1); // Space for length plus null
182 if (d != NULL) {
183 strcpy(d, s); // Copy the characters
184 }
185 return d; // Return the new string
186}
187
188unsigned hash(char *s) {
189 /* hashing function: form hash value for string s */
190 /* used by both lookup and install*/
191 unsigned hashval;
192
193 for (hashval = 0; *s != '\0'; s++) {
194 hashval = *s + 31 * hashval;
195 }
196 return hashval % HASHSIZE;
197}
198
199// Driver Program to test above functions
200
201int main() {
202 FILE *f_cal;
203 FILE *f_op;
204 int total_unique = 0;
205 int in_count, count_create = 0;
206 int count_delete = 0;
207 int unique_key_arr[100]; // Make dynamic
208 char *value_arr[100];
209 char *VAL_arr_create[100]; // an array of pointers [unique][chars]
210 char *VAL_arr_delete[100];
211 char *KEY_arr_create[100];
212 char *KEY_arr_delete[100];
213
214 f_cal = fopen("calendar.txt", "r+");
215 f_op = fopen("operations.txt", "r+");
216
217 char buf[MAXC];
218 char *line[1024];
219 char *p_line;
220 char *ptr;
221 char *in_val_arr[100];
222 int in_key_arr[100];
223 char *in_val_op[100];
224 int in_key_op[100];
225 long key_arr_op;
226 int count_cal = 0;
227 int count_op = 0;
228 char delimiter[] = " ";
229 long key_arr;
230 node *root = NULL;
231
232 /* Both input files must wned with a new line*/
233 if (f_cal) {
234 printf("Processing calendar file...\n");
235 while (fgets(buf, MAXC, f_cal)) {
236 p_line = malloc(strlen(buf) + 1); // malloced with size of buffer.
237 //p_line = malloc(sizeof (char) + 1); // malloced with size of buffer.
238 char *in_val;
239 char *in_key;
240
241 strcpy(p_line, buf); //used to create a copy of input buffer
242 line[count_cal] = p_line;
243
244 /* separating the line based on the first space. The words after
245 * the delimeter will be copied into in_val */
246 char *copy = strchr(p_line, ' ');
247 if (copy) {
248 if ((in_val = malloc(strlen(line[count_cal]) + 1)) == NULL) {
249 return -1;
250 } else {
251 strcpy(in_val, copy + 1);
252 //printf("arr: %s", in_val);
253 in_val_arr[count_cal] = in_val;
254 }
255 } else
256 printf("Could not find a space (Incorrect file format)\n");
257
258 /* We now need to get the first word from the input buffer*/
259 in_key = strtok(buf, delimiter);
260 char *newkey = malloc(strlen(in_key) + 1); // <<<< allocate new memory
261 strcpy(newkey, in_key);
262 key_arr = strtol(newkey, &ptr, 10);
263 in_key_arr[count_cal] = key_arr;
264 count_cal++;
265 }
266 char *p_nl, *p_r; // remove new line
267 for (int i = 0; i < count_cal; ++i) {
268 if ((p_nl = strchr(in_val_arr[i], '\n')) != NULL) { //removing new line at the end, allows for easier comparison
269 *p_nl = '\0'; //adding string terminator at the end.
270 //printf("enter found");
271 }
272 if ((p_r = strchr(in_val_arr[i], '\r')) != NULL) { //removing \r at the end, messing with display
273 *p_r = '\0'; //adding string terminator at the end.
274 }
275 printf("key=%d, val = %s\n", in_key_arr[i], in_val_arr[i]);
276 root = insert_node(root, in_key_arr[i], in_val_arr[i]);
277 }
278 printf("%d \n ",count_cal);
279 fclose(f_cal);
280 }
281
282 if (f_op) {
283 printf("Processing operations file...\n");
284 while (fgets(buf, MAXC, f_op)) {
285 p_line = malloc(strlen(buf) + 1); // malloced with size of buffer.
286 char *in_valop;
287 char *in_keyop;
288 char *in_op;
289
290 strcpy(p_line, buf); //used to create a copy of input buffer
291 line[count_op] = p_line;
292
293 /* separating the line based on the first space. The words after
294 * the delimeter will be copied into in_val */
295 char *copy = strchr(p_line, ' ');
296 if (copy) {
297 if ((in_valop = malloc(strlen(line[count_op]) + 1)) == NULL) {
298 printf("out of memory");
299 return -1;
300 } else {
301 strcpy(in_valop, copy + 1);
302 //printf("arr: %s", in_val);
303 in_val_op[count_op] = in_valop;
304 }
305 } else
306 printf("Could not find a space (incorrect file format)\n");
307
308 /* We now need to get the first word from the input buffer*/
309 in_keyop = strtok(buf, delimiter);
310 char *newkey = malloc(strlen(in_keyop) + 1); // <<<< allocate new memory
311 strcpy(newkey, in_keyop);
312 key_arr_op = strtol(newkey, &ptr, 10);
313 in_key_op[count_op] = key_arr_op;
314 //printf("%d\n", in_key_op[count]);
315 count_op++;
316 }
317 char *p_nl, *p_r; // remove new line
318 for (int i = 0; i < count_op; ++i) {
319 if ((p_nl = strchr(in_val_op[i], '\n')) != NULL) { //removing new line at the end
320 *p_nl = '\0'; //adding string terminator at the end.
321 //printf("enter found2");
322 }
323 if ((p_r = strchr(in_val_op[i], '\r')) != NULL) { //removing \r at the end, messing with display
324 *p_r = '\0'; //adding string terminator at the end.
325 }
326 printf("key=%d, val = %s\n", in_key_op[i], in_val_op[i]);
327 root = insert_node(root, in_key_op[i], in_val_op[i]);
328 }
329 printf("%d operations read\n",count_op);
330 fclose(f_op);
331 }
332
333 /* Operating on data from operations file */
334 printf("Inorder traversal of the given tree \n");
335 inorder(root, &in_count);
336
337 printf("\nDeepest unique keys of the given tree: \n");
338 unique_key(root, &total_unique, unique_key_arr, value_arr);
339 printf("%d\n", total_unique);
340
341 printf("Deepest unique keys of the given tree in main: %d \n",total_unique);
342 for (int i = 0; i < total_unique; i++) {
343 printf("%d %s\n", unique_key_arr[i], value_arr[i]);
344 if (*value_arr[i] == 'C') { //Compare first char of pointer type
345 } else if (*value_arr[i] == 'U') { //Compare first char of pointer type
346 } else if (*value_arr[i] == 'D') { //Compare first char of pointer type
347 }
348 else {
349 printf("Incorrect operation type. Must be C, U or D\n");
350 }
351 }
352 printf("\n");
353
354 /* Map is for storing calendar. This should contain the unique elements
355 * from the BST above. Based on the first char inside `value_arr`, we
356 * should insert or delete a map. Number of operations to perform
357 depends on variable `unique_count`. Use strcpy()*/
358
359 printf("Deepest unique keys to map structure: %d\n", total_unique);
360 for (int unique_count = 0; unique_count < total_unique; unique_count++) {
361 char* p_val = malloc(strlen(value_arr[unique_count]) + 1); //pointer to char for value
362 char* p_key; //pointer to char for key
363 p_key = malloc(sizeof (char) + 1); //this is malloced to access different memory each time.
364
365 if (*value_arr[unique_count] == 'C' || *value_arr[unique_count] == 'U') { //Compare first char of pointer type
366
367 //if ((p_val = alloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
368 if ((p_val = malloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
369 printf("Failed 1");
370 return -1;
371 } else {
372 strcpy(p_val, value_arr[unique_count]); //copying value to pointer to char
373 VAL_arr_create[count_create] = p_val; //p passed to value array
374 }
375
376 //Convert integer to pointer to char
377 sprintf(p_key, "%d", unique_key_arr[unique_count]);
378 KEY_arr_create[count_create] = p_key; //array containing all create/updates
379
380 printf("I am here %s, %s\n", KEY_arr_create[count_create], VAL_arr_create[count_create]);
381 count_create++;
382
383 } else if (*value_arr[unique_count] == 'D') { //must be a delete
384
385 if ((p_val = malloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
386 printf("Failed 2");
387 return -1;
388 } else {
389 strcpy(p_val, value_arr[unique_count]); //copying value to pointer to char
390 VAL_arr_delete[count_delete] = p_val; //p passed to value array
391 }
392
393 //Convert integer to pointer to char
394 sprintf(p_key, "%d", unique_key_arr[unique_count]);
395 KEY_arr_delete[count_delete] = p_key; //array containing all deletes
396 printf("I am here2 %s, %s\n", KEY_arr_delete[count_delete], VAL_arr_delete[count_delete]);
397 count_delete++;
398 }
399 }
400
401 map * table[100]; //pointer to type map structure
402
403 printf("\nBefore insert CREATE %d\n", count_create);
404
405 for (int i = 0; i < count_create; i++) {
406 printf("CREATE %s, %s\n", KEY_arr_create[i], VAL_arr_create[i]);
407 /* Here I need to remove leading operation letter to display*/
408 char *p;
409 char *copy_val_create = strchr(VAL_arr_create[i], ' ');
410 if (copy_val_create)
411 printf("COPY: %s\n", copy_val_create + 1);
412 else
413 printf("Could not find a space\n");
414 table[i] = insert_map(KEY_arr_create[i], copy_val_create + 1);
415 }
416
417 printf("\nBefore insert DELETE %d\n", count_delete);
418 for (int i = 0; i < count_delete; i++) {
419 printf("DELETE %s, %s\n", KEY_arr_delete[i], VAL_arr_delete[i]);
420 remove_map(KEY_arr_delete[i]);
421 }
422
423 f_cal = fopen("calendar.txt", "w+");
424 printf("\nUPDATED CALENDAR - %d entries\n", count_create);
425 for (int i = 0; i < count_create; i++) {
426 // if ((p_r = strchr(table[i]->value, '\r')) != NULL) { //removing \r at the end, messing with display
427 // *p_r = '\0'; //adding string terminator at the end.
428 // }
429
430 /* Used to preserve original leading 0 when displaying the date*/
431 if (strlen(table[i]->KEY) == 7) {
432 printf("0%s %s \n", table[i]->KEY, table[i]->value);
433 fprintf(f_cal, "0%s %s\n", table[i]->KEY, table[i]->value);
434 } else {
435 printf("%s %s \n", table[i]->KEY, table[i]->value);
436 fprintf(f_cal, "%s %s\n", table[i]->KEY, table[i]->value);
437 }
438
439 }
440
441 fclose(f_cal);
442 printf("\n");
443
444 //remove_map("4082018");
445
446 return 0;
447}