Sort Memory Blocks in C Assignment Sample
You need to write a sort routine that uses a binary tree to store the allocated memory based on the size of the memory to allocate. The function to compare should use a function pointer so that the type of comparison can be changed. You should read the file to sort and use strok to parse it. For more C programming assignments contact us for a quote.
Solution:
bst.h
#ifndef BST_H
#define BST_H
typedef struct _node{
void* data;
struct _node* left;
struct _node* right;
}node;
typedef struct{
node* root;
int (*cmp)(const void* x, const void* y);
}bst;
/* ******* BST ******** */
/* These functions are what programmers using the BST would use */
/* create a new bst, initialize its root to be NULL
*/
bst* bst_new(int (*cmp)(const void* x, const void* y));
/* Insert a new node to the bst
*/
void bst_insert(bst* b, void* data);
/* Search a node with data in a bst.
*/
void* bst_search(bst* b, void* data);
/* traverse a bst in ascending order.
* Apply func to the data of each node.
*/
void bst_inorder_traversal(bst* b, void(*func)(void* data));
/* free the bst with
*/
void bst_free(bst* b);
/* delete a node containing data from the bst
*/
void bst_delete(bst* b, void* data);
/* ******* Node ****** */
/* These functions are only in the .h file so you can
* call them for testing purposes. Normally,they would
* not be in the .h because they aren’t intended to be
* called from outside bst.c
*/
/* malloc a new node and assign the data
* pointer to its data field
*/
node* node_new(void* data);
/* Insert a node to to a subtree with a root node as parameter
* Insertion is in sorted order.
* Return the new root of the modified subtree.
*/
node* node_insert(node* root, void* data,
int (*cmp)(const void* x, const void* y));
/* delete a node from a subtree with a given root node
* use the comparison function to search the node and delete
* it when a matching node is found. This function only
* deletes the first occurrence of the node, i.e, if multiple
* nodes contain the data we are looking for, only the first node
* we found is deleted.
* Return the new root node after deletion.
*/
node* node_delete(node* root, void* data,
int (*cmp)(const void* x, const void* y));
/* Search for a node containing data in a subtree with
* a given root node. Use recursion to search that node.
* Return the first occurrence of node.
*/
void* node_search(node* root, void* data,
int (*cmp)(const void* x, const void* y));
/* traverse a subtree with root in ascending order.
* Apply func to the data of each node.
*/
void inorder_traversal(node* root, void(*func)(void* data));
#endif
bst.c
#include
#include
#include “bst.h”
/* malloc a new node and assign the data
* pointer to its data field
*/
node* node_new(void* data) {
//TODO’
node* newNode = (node*) malloc(sizeof(node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
/* create a new bst, initialize its root to be NULL
*/
bst* bst_new(int (*cmp)(const void* x, const void* y)) {
//TODO
bst* newBST = (bst*) malloc(sizeof(bst));
newBST->root = NULL;
newBST->cmp = cmp;
return newBST;
}
/* Insert a node to to a subtree with a root node as parameter
* Insertion is in sorted order.
* Return the new root of the modified subtree.
*/
node* node_insert(node* root, void* data,
int (*cmp)(const void* x, const void* y)){
//TODO
node* current = root;
if (current == NULL) {
root = node_new(data);
return root;
}
int compareNode = cmp(data, current->data);
switch (compareNode) {
case 1:
if (current->right == NULL) {
current->right = node_new(data);
return root;
} else {
node_insert(current->right, data, cmp);
}
break;
case 0:
case -1:
if (current->left == NULL) {
current->left = node_new(data);
return root;
} else {
node_insert(current->left, data, cmp);
}
break;
default:
printf(“node_insert(). Error\n”);
}
return root;
}
/* Insert a new node to the bst
*/
void bst_insert(bst* b, void* data){
//TODO
b->root = node_insert(b->root, data, b->cmp);
}
/**
* find max node in BST tree
*/
node* max(node* root) {
node* current = root;
if (current == NULL) {
return NULL;
}
if (current->right == NULL) {
return current;
} else {
return max(current->right);
}
}
/**
* find min node in BST tree
*/
node* min(node* root) {
node* current = root;
if (current == NULL) {
return NULL;
}
if (current->left == NULL) {
return current;
} else {
return min(current->left);
}
}
/* delete a node from a subtree with a given root node
* use the comparison function to search the node and delete
* it when a matching node is found. This function only
* deletes the first occurrence of the node, i.e, if multiple
* nodes contain the data we are looking for, only the first node
* we found is deleted.
* Return the new root node after deletion.
*/
node* node_delete(node* root, void* data,
int (*cmp)(const void* x, const void* y)){
//TODO
if (root == NULL) {
return NULL;
}
int compareNode = cmp(data, root->data);
switch (compareNode) {
case -1:
root->left = node_delete(root->left, data, cmp);
return root;
case 0:
if ((root->right == NULL) && (root->left == NULL)) {
free(root);
return NULL;
} else if ((root->left != NULL) && (root->right == NULL)) {
node* maxNode = max(root->left);
root->data = maxNode->data;
root->left = node_delete(root->left, maxNode->data, cmp);
return root;
} else if ((root->left == NULL) && (root->right != NULL)) {
node* minNode = min(root->right);
root->data = minNode->data;
root->right = node_delete(root->right, minNode->data, cmp);
return root;
} else if ((root->left != NULL) && (root->right != NULL)) {
node* minNode = min(root->right);
root->data = minNode->data;
root->right = node_delete(root->right, minNode->data, cmp);
return root;
}
break;
case 1:
root->right = node_delete(root->right, data, cmp);
return root;
default:
return NULL;
}
// if (compareNode == -1) {
// root->left = node_delete(root->left, data, cmp);
// return root;
// } else if (compareNode == 1) {
// root->right = node_delete(root->right, data, cmp);
// return root;
// } else if (compareNode == 0) {
// if ((root->right == NULL) && (root->left == NULL)) {
// free(root);
// return NULL;
// } else if ((root->left != NULL) && (root->right == NULL)) {
// node* maxNode = max(root->left);
// root->data = maxNode->data;
// root->left = node_delete(root->left, maxNode->data, cmp);
// return root;
// } else if ((root->left == NULL) && (root->right != NULL)) {
// node* minNode = min(root->right);
// root->data = minNode->data;
// root->right = node_delete(root->right, minNode->data, cmp);
// return root;
// } else if ((root->left != NULL) && (root->right != NULL)) {
// node* minNode = min(root->right);
// root->data = minNode->data;
// root->right = node_delete(root->right, minNode->data, cmp);
// return root;
// }
// }
return NULL;
}
/* delete a node containing data from the bst
*/
void bst_delete(bst* b, void* data){
//TODO
int compareNode = b->cmp(data, b->root->data);
switch (compareNode) {
case 0:
if ((b->root->left == NULL) && (b->root->right == NULL)) {
b->root = NULL;
return;
} else if (b->root->left != NULL) {
b->root = b->root->left;
return;
} else if (b->root->right != NULL) {
b->root = b->root->right;
return;
}
}
b->root = node_delete(b->root, data, b->cmp);
}
/* Search for a node containing data in a subtree with
* a given root node. Use recursion to search that node.
* Return the first occurrence of node.
*/
void* node_search(node* root, void* data,
int (*cmp)(const void* x, const void* y)){
//TODO
node* currentNode = root;
if (currentNode != NULL) {
int compareNode = cmp(data, currentNode->data);
switch (compareNode) {
case 0:
return currentNode;
case -1:
return node_search(currentNode->left, data, cmp);
case 1:
return node_search(currentNode->right, data, cmp);
default:
return NULL;
}
} else {
printf(“ERROR: node_search(): node did not exist in tree\n”);
}
return NULL;
}
/* Search a node with data in a bst.
*/
void* bst_search(bst* b, void* data) {
//TODO
node* result = node_search(b->root, data, b->cmp);
return result;
}
/* traverse a subtree with root in ascending order.
* Apply func to the data of each node.
*/
void inorder_traversal(node* root, void(*func)(void* data)){
//TODO
if (root == NULL) {
return;
} else {
inorder_traversal(root->left, func);
func(root->data);
inorder_traversal(root->right, func);
}
}
/* traverse a bst in ascending order.
* Apply func to the data of each node.
*/
void bst_inorder_traversal(bst* b, void (*func)(void* data)) {
//TODO
inorder_traversal(b->root, func);
}
/**
* Free node helper
*/
void freeNode(node* n)
{
if(n == NULL){
return;
}
else {
freeNode(n->left);
freeNode(n->right);
free(n);
}
}
/* free the bst with
*/
void bst_free(bst* b) {
//TODO
if (b != NULL) {
freeNode(b->root);
}
}
hw7.h
#ifndef HW7_H_
#define HW7_H_
#include “memory.h”
#include “bst.h”
/**
* function takes in a filename.
* It reads in the file and splits the file into memory blocks
*/
bst* read_memory_blocks(char *filename,
int (*cmp)(const void* x, const void* y));
#endif /* HW7_H_ */
hw7.c
#include
#include
#include
#include “hw7.h”
#define BUFSIZE 255
/**
* function takes in a filename.
* It reads in the file and splits the file into memory blocks
*/
bst* read_memory_blocks(char *filename, int (*cmp)(const void* x, const void* y))
{
FILE * fp;
bst *memory_tree = NULL;
fp = fopen(filename, “r”);
char delim[] = “,”;
char line[BUFSIZE];
if (filename != NULL)
{
/* Read line */
while (fgets(line, sizeof(line), (FILE*) fp) != NULL)
{
/* fprintf(stdout, “DEBUG. Line: %s\n”, line); */
/* Split line*/
char *ptr = strtok(line, delim);
unsigned int addr, size;
int count = 0;
/* Read data */
while (ptr != NULL)
{
// Read addr
switch (count)
{
case 0:
/* Read address */
addr = atoi(ptr);
/* fprintf(stdout, “DEBUG. Addr: %d. ptr: %s\n”, addr, ptr); */
break;
case 1:
/* Read size */
size = atoi(ptr);
/* fprintf(stdout, “DEBUG. Addr: %d. ptr: %s\n”, addr, ptr); */
break;
default:
fprintf(stderr, “Invald format with line %s\n”, line);
/* Free the tree for memory leak */
if (memory_tree == NULL)
bst_free(memory_tree);
fclose(fp);
return NULL;
break;
}
count++;
ptr = strtok(NULL, delim);
}
/* Add address and size. Create new memory block*/
memory *new_mem = memory_new(addr, size);
/* Add to tree */
if (memory_tree == NULL)
{
/* Create BST tree if it does not exist*/
memory_tree = bst_new(cmp);
bst_insert(memory_tree, new_mem);
}
else
bst_insert(memory_tree, new_mem);
}
/* splite the file */
fclose(fp);
}
else
{
fprintf(stderr, “Could not open file %s\n”, filename);
}
return memory_tree;
}
hw7_main.c
#include
#include
#include “hw7.h”
#define TEST1 “testmemory1.txt”
#define TEST2 “testmemory2.txt”
int main(int argc, char** argv)
{
bst *memorytree = read_memory_blocks(TEST1, memory_addr_cmp);
if (memorytree)
{
fprintf(stdout, “Memory in %s with memory compare base on address:\n”, TEST1);
bst_inorder_traversal(memorytree, memory_print);
}
bst *memorytree2 = read_memory_blocks(TEST2, memory_size_cmp);
if (memorytree2)
{
fprintf(stdout, “Memory in %s with memory compare base on size:\n”, TEST2);
bst_inorder_traversal(memorytree2, memory_print);
}
return 0;
}
memory.h
#ifndef MEMORY_H
#define MEMORY_H
/* This file contains the structs and function signatures for
* memory. A memory structure stores the memory address as
* well as the size of a memory slot. It has a constructor
* (memory_new), and two comparison functions, so they can be
* scored in a sorted data structure either by the memory
* address or by memory size.
*/
typedef struct {
unsigned int addr;
unsigned int size;
}memory;
/* memory_new
* create a new memory struct, initialze its address and size
*/
memory* memory_new(unsigned int addr, unsigned int size);
/* free the dynamically allocated memory struct
*/
void memory_free(void* p);
/* compare two memory variables x and y by address
* if x is less than y, return -1
* if x is greater than y, return 1
* if they are equal, return 0
*/
int memory_addr_cmp(const void* x, const void* y);
/* compare two memory variables x and y by size
* if x is less than y, return -1
* if x is greater than y, return 1
* if they are equal, return 0
*/
int memory_size_cmp(const void* x, const void* y);
/* print the memory address and size
*/
void memory_print(void* data);
#endif
memory.c
#include
#include
#include “memory.h”
/* memory_new
* create a new memory struct, initialze its address and size
*/
memory* memory_new(unsigned int addr, unsigned int size){
memory* m = (memory*)malloc(sizeof(memory));
m->addr = addr;
m->size = size;
return m;
}
/* free the dynamically allocated memory struct
*/
void memory_free(void* p){
memory* m = (memory*)p;
free(m);
}
/* compare two memory variables x and y by address
* if x is less than y, return -1
* if x is greater than y, return 1
* if they are equal, return 0
*/
int memory_addr_cmp(const void* x, const void* y) {
//TODO
memory* xCast = (memory*) x;
memory* yCast = (memory*) y;
if ((xCast->addr) < (yCast->addr)) {
return -1;
}
if ((xCast->addr) > (yCast->addr)) {
return 1;
}
if ((xCast->addr) == (yCast->addr)) {
return 0;
} else {
printf(“error\n”);
return 2;
}
return 0;
}
/* compare two memory variables x and y by size
* if x is less than y, return -1
* if x is greater than y, return 1
* if they are equal, return 0
*/
int memory_size_cmp(const void* x, const void* y) {
//TODO
memory* xCast = (memory*) x;
memory* yCast = (memory*) y;
if ((xCast->size) < (yCast->size)) {
return -1;
}
if ((xCast->size) > (yCast->size)) {
return 1;
}
return 0;
}
/* print the memory address and size
*/
void memory_print(void* data){
if (data == NULL) return;
memory* m = (memory*)data;
printf(“address: %u, size: %u\n”, m->addr, m->size);
}