Dynamic Memory

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STRING_SIZE 100
#define HASHSIZE 101  /* comment here */
#define ALLOCSIZE 1000 /*size of available space*/
#define N 1000 // max number of lines to be read
#define VALLEN 100 //max number of chars for description
#define MAXC 1024
#define MAX 1000

static char allocbuf[ALLOCSIZE]; /* storage for alloc*/
static char *allocp = allocbuf; /* next free position*/
static struct map *hashtab[HASHSIZE]; /* pointer table */
unsigned hash(char *); /* hashing function: form hash value for string s. used by both lookup and install*/
char *strdup(char *);

//char *alloc(int n) { /* return a pointer to n characters*/
//    if (allocbuf + ALLOCSIZE - allocp >= n) { /*it fits*/
//        allocp += n;
//        return allocp - n; /*old p*/
//    } else /*not enough room*/
//        return 0;
//}

typedef struct map { /* creating a map structure */
    struct map *next;
    char *value;
    char *KEY;
} map;

typedef struct node {
    int KEY;
    char *value;
    int node_count;
    struct node *left, *right;
    int unique_count;
} node;

// A utility function to create a new BST node

node *newNode(int KEY, char *value) {
    //Allocate a new overall structure
    node *temp = (node *) malloc(sizeof (node));

    //Copy the integer key
    temp->KEY = KEY;
    temp->value = value;

    temp->left = temp->right = NULL;
    temp->node_count = 1;
    return temp;
}

// A utility function to do inorder traversal of BST

void inorder(node *root, int *pin_count) {
    if (root != NULL) {
        inorder(root->left, pin_count);
        printf("%d(%d)\n", root->KEY, root->node_count);
        inorder(root->right, pin_count);
    }
}

/* A utility function to find deepest keys of BST */

/* This is done by extracting the key with the lowest count,
since count member of node struct gets incremented each time it is read. */
void unique_key(node *root, int *p_unique_count, int p_unique_key_arr[], char *p_value_arr[]) {
    int count = 0;
    char *p;

    if (root != NULL) {
        unique_key(root->left, p_unique_count, p_unique_key_arr, p_value_arr);
        if (root->node_count == 1) {

            if ((p = malloc(strlen(root[count].value) + 1)) == NULL) {
                return;
            } else {
                root[count].unique_count = *p_unique_count;
                p_unique_key_arr[*p_unique_count] = root[count].KEY;

                strcpy(p, root[count].value);
                p_value_arr[*p_unique_count] = p;
                //printf("%s\n",p_value_arr[*p_unique_count][*p_unique_count]);

                printf("%d(%d) -> %s %d\n", root->KEY, root->node_count, root->value, root->unique_count);
                (*p_unique_count)++;
                count++;
            }
        }
        unique_key(root->right, p_unique_count, p_unique_key_arr, p_value_arr);
    }
}

/* A utility function to insert a new node with given key in BST */
node* insert_node(node* node, int key, char *value) {
    /* If the tree is empty, return a new node */
    if (node == NULL)
        return newNode(key, value);

    // If key already exists in BST, icnrement count and return
    if (key == node->KEY) {
        (node->node_count)++;
        //  return node;
    }

    /* Otherwise, recur down the tree */
    if (key < node->KEY)
        node->left = insert_node(node->left, key, value);
    else
        node->right = insert_node(node->right, key, value);

    /* return the (unchanged) node pointer */
    return node;
}

/* lookup function takes a pointer to char - s as an argument and returns a pointer to map structure */
map *lookup(char *s) {
    map *np;

    for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
        if (strcmp(s, np->KEY) == 0) {
            return np;
        }
    }
    return NULL;
}

/* insert function takes a pointer to a char - KEY, value and returns a pointer to map structure */
map *insert_map(char* KEY, char* value) {
    /* install: put (name, defn) in */
    /* Install uses lookup to determine whether the KEY being installed
       is already present. Proceeds to create a new entry or update*/
    map *np;
    unsigned hashval;

    if ((np = lookup(KEY)) == NULL) {
        np = (map *) malloc(sizeof (*np));
        if (np == NULL || (np->KEY = strdup(KEY)) == NULL) {
            return NULL;
        }
        hashval = hash(KEY);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else {
        free((void *) np->value);
    }
    if ((np->value = strdup(value)) == NULL) { //map has no field value
        return NULL;
    }

    return np;
}

/* uninstall function removes a key and calendar from table maintained by lookup and install */
map *remove_map(char *KEY) {
    map *found;

    found = lookup(KEY);

    if (found == NULL) /* not found and nothing to do */ {
        //printf("%s - Nothing to delete.\n", KEY);
        return NULL;
    } else {
        if (found->next != NULL) {
            found->next = found->next->next;
            found = found->next;
        } else {
            hashtab[hash(KEY)] = NULL;
            free((void *) found);
        }
    }
    return found;
}

/* simple implementation of strdup*/
char *strdup(char *s) {

    char *d = (char *) malloc(strlen(s) + 1); // Space for length plus null
    if (d != NULL) {
        strcpy(d, s); // Copy the characters
    }
    return d; // Return the new string
}

unsigned hash(char *s) {
    /* hashing function: form hash value for string s */
    /* used by both lookup and install*/
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++) {
        hashval = *s + 31 * hashval;
    }
    return hashval % HASHSIZE;
}

// Driver Program to test above functions

int main() {
    FILE *f_cal;
    FILE *f_op;
    int total_unique = 0;
    int in_count, count_create = 0;
    int count_delete = 0;
    int unique_key_arr[100]; // Make dynamic
    char *value_arr[100];
    char *VAL_arr_create[100]; // an array of pointers [unique][chars]
    char *VAL_arr_delete[100];
    char *KEY_arr_create[100];
    char *KEY_arr_delete[100];

    f_cal = fopen("calendar.txt", "r+");
    f_op = fopen("operations.txt", "r+");

    char buf[MAXC];
    char *line[1024];
    char *p_line;
    char *ptr;
    char *in_val_arr[100];
    int in_key_arr[100];
    char *in_val_op[100];
    int in_key_op[100];
    long key_arr_op;
    int count_cal = 0;
    int count_op = 0;
    char delimiter[] = " ";
    long key_arr;
    node *root = NULL;

    /* Both input files must wned with a new line*/
    if (f_cal) {
        printf("Processing calendar file...\n");
        while (fgets(buf, MAXC, f_cal)) {
            p_line = malloc(strlen(buf) + 1); // malloced with size of buffer.
            //p_line = malloc(sizeof (char) + 1); // malloced with size of buffer.
            char *in_val;
            char *in_key;

            strcpy(p_line, buf); //used to create a copy of input buffer
            line[count_cal] = p_line;

            /* separating the line based on the first space. The words after
             * the delimeter will be copied into in_val */
            char *copy = strchr(p_line, ' ');
            if (copy) {
                if ((in_val = malloc(strlen(line[count_cal]) + 1)) == NULL) {
                    return -1;
                } else {
                    strcpy(in_val, copy + 1);
                    //printf("arr: %s", in_val);
                    in_val_arr[count_cal] = in_val;
                }
            } else
                printf("Could not find a space (Incorrect file format)\n");

            /* We now need to get the first word from the input buffer*/
            in_key = strtok(buf, delimiter);
            char *newkey = malloc(strlen(in_key) + 1); // <<<< allocate new memory
            strcpy(newkey, in_key);
            key_arr = strtol(newkey, &ptr, 10);
            in_key_arr[count_cal] = key_arr;
            count_cal++;
        }
        char *p_nl, *p_r; // remove new line
        for (int i = 0; i < count_cal; ++i) {
            if ((p_nl = strchr(in_val_arr[i], '\n')) != NULL) { //removing new line at the end, allows for easier comparison
                *p_nl = '\0'; //adding string terminator at the end.
                //printf("enter found");
            }
            if ((p_r = strchr(in_val_arr[i], '\r')) != NULL) { //removing \r at the end, messing with display
                *p_r = '\0'; //adding string terminator at the end.
            }
            printf("key=%d, val = %s\n", in_key_arr[i], in_val_arr[i]);
            root = insert_node(root, in_key_arr[i], in_val_arr[i]);
        }
        printf("%d \n ",count_cal);
        fclose(f_cal);
    }

    if (f_op) {
        printf("Processing operations file...\n");
        while (fgets(buf, MAXC, f_op)) {
            p_line = malloc(strlen(buf) + 1); // malloced with size of buffer.
            char *in_valop;
            char *in_keyop;
            char *in_op;

            strcpy(p_line, buf); //used to create a copy of input buffer
            line[count_op] = p_line;

            /* separating the line based on the first space. The words after
             * the delimeter will be copied into in_val */
            char *copy = strchr(p_line, ' ');
            if (copy) {
                if ((in_valop = malloc(strlen(line[count_op]) + 1)) == NULL) {
                    printf("out of memory");
                    return -1;
                } else {
                    strcpy(in_valop, copy + 1);
                    //printf("arr: %s", in_val);
                    in_val_op[count_op] = in_valop;
                }
            } else
                printf("Could not find a space (incorrect file format)\n");

            /* We now need to get the first word from the input buffer*/
            in_keyop = strtok(buf, delimiter);
            char *newkey = malloc(strlen(in_keyop) + 1); // <<<< allocate new memory
            strcpy(newkey, in_keyop);
            key_arr_op = strtol(newkey, &ptr, 10);
            in_key_op[count_op] = key_arr_op;
            //printf("%d\n", in_key_op[count]);
            count_op++;
        }
        char *p_nl, *p_r; // remove new line
        for (int i = 0; i < count_op; ++i) {
            if ((p_nl = strchr(in_val_op[i], '\n')) != NULL) { //removing new line at the end
                *p_nl = '\0'; //adding string terminator at the end.
                //printf("enter found2");
            }
            if ((p_r = strchr(in_val_op[i], '\r')) != NULL) { //removing \r at the end, messing with display
                *p_r = '\0'; //adding string terminator at the end.
            }
            printf("key=%d, val = %s\n", in_key_op[i], in_val_op[i]);
            root = insert_node(root, in_key_op[i], in_val_op[i]);
        }
        printf("%d operations read\n",count_op);
        fclose(f_op);
    }

    /* Operating on data from operations file */
    printf("Inorder traversal of the given tree \n");
    inorder(root, &in_count);

    printf("\nDeepest unique keys of the given tree: \n");
    unique_key(root, &total_unique, unique_key_arr, value_arr);
    printf("%d\n", total_unique);

    printf("Deepest unique keys of the given tree in main: %d \n",total_unique);
    for (int i = 0; i < total_unique; i++) {
        printf("%d %s\n", unique_key_arr[i], value_arr[i]);
        if (*value_arr[i] == 'C') { //Compare first char of pointer type
        } else if (*value_arr[i] == 'U') { //Compare first char of pointer type
        } else if (*value_arr[i] == 'D') { //Compare first char of pointer type
        }
        else {
            printf("Incorrect operation type. Must be C, U or D\n");
        }
    }
    printf("\n");

    /* Map is for storing calendar. This should contain the unique elements
     * from the BST above. Based on the first char inside `value_arr`, we
     * should insert or delete a map. Number of operations to perform
      depends on variable `unique_count`. Use strcpy()*/

    printf("Deepest unique keys to map structure: %d\n", total_unique);
    for (int unique_count = 0; unique_count < total_unique; unique_count++) {
        char* p_val = malloc(strlen(value_arr[unique_count]) + 1); //pointer to char for value
        char* p_key; //pointer to char for key
        p_key = malloc(sizeof (char) + 1); //this is malloced to access different memory each time.

        if (*value_arr[unique_count] == 'C' || *value_arr[unique_count] == 'U') { //Compare first char of pointer type

            //if ((p_val = alloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
            if ((p_val = malloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
                printf("Failed 1");
                return -1;
            } else {
                strcpy(p_val, value_arr[unique_count]); //copying value to pointer to char
                VAL_arr_create[count_create] = p_val; //p passed to value array
            }

            //Convert integer to pointer to char
            sprintf(p_key, "%d", unique_key_arr[unique_count]);
            KEY_arr_create[count_create] = p_key; //array containing all create/updates

            printf("I am here %s, %s\n", KEY_arr_create[count_create], VAL_arr_create[count_create]);
            count_create++;

        } else if (*value_arr[unique_count] == 'D') { //must be a delete

            if ((p_val = malloc(strlen(value_arr[unique_count]) + 1)) == NULL) {
                printf("Failed 2");
                return -1;
            } else {
                strcpy(p_val, value_arr[unique_count]); //copying value to pointer to char
                VAL_arr_delete[count_delete] = p_val; //p passed to value array
            }

            //Convert integer to pointer to char
            sprintf(p_key, "%d", unique_key_arr[unique_count]);
            KEY_arr_delete[count_delete] = p_key; //array containing all deletes
            printf("I am here2 %s, %s\n", KEY_arr_delete[count_delete], VAL_arr_delete[count_delete]);
            count_delete++;
        }
    }

    map * table[100]; //pointer to type map structure

    printf("\nBefore insert CREATE %d\n", count_create);

    for (int i = 0; i < count_create; i++) {
        printf("CREATE %s, %s\n", KEY_arr_create[i], VAL_arr_create[i]);
        /* Here I need to remove leading operation letter to display*/
        char *p;
        char *copy_val_create = strchr(VAL_arr_create[i], ' ');
        if (copy_val_create)
            printf("COPY: %s\n", copy_val_create + 1);
        else
            printf("Could not find a space\n");
        table[i] = insert_map(KEY_arr_create[i], copy_val_create + 1);
    }

    printf("\nBefore insert DELETE %d\n", count_delete);
    for (int i = 0; i < count_delete; i++) {
        printf("DELETE %s, %s\n", KEY_arr_delete[i], VAL_arr_delete[i]);
        remove_map(KEY_arr_delete[i]);
    }

    f_cal = fopen("calendar.txt", "w+");
    printf("\nUPDATED CALENDAR - %d entries\n", count_create);
    for (int i = 0; i < count_create; i++) {
        //        if ((p_r = strchr(table[i]->value, '\r')) != NULL) { //removing \r at the end, messing with display
        //            *p_r = '\0'; //adding string terminator at the end.
        //        }

        /* Used to preserve original leading 0 when displaying the date*/
        if (strlen(table[i]->KEY) == 7) {
            printf("0%s %s \n", table[i]->KEY, table[i]->value);
            fprintf(f_cal, "0%s %s\n", table[i]->KEY, table[i]->value);
        } else {
            printf("%s %s \n", table[i]->KEY, table[i]->value);
            fprintf(f_cal, "%s %s\n", table[i]->KEY, table[i]->value);
        }

    }

    fclose(f_cal);
    printf("\n");

    //remove_map("4082018");

    return 0;
}