+1 (315) 557-6473 

Program To Represent A BST-Based Database System in C Assignment Solutions.


Instructions

Objective
Write a program for a BST-based database system in C language.

Requirements and Specifications

Write your C assignment submission in this file
A main function and some profiling tools have already been set up to test your code in the task2.c file. All you need to do is fill out this file
with an appropriate Binary Search Tree implementation.
The input data will be books. A book is comprised of a title and a word count. You should store both these values in the tree along with a unique integer ID which you will generate.
We are aiming for speed here. A BST based database should be orders of magnitude faster than a linked list implementation if the BST is written correctly.
We have provided an example implementation of what a linked list based solution to this problem might look like in the db/listdb.c file. If you are struggling to understand the problem or what one of the functions below ought to do, consider looking at that file to see if it helps your understanding.
There are 6 functions you need to look at. Each is provided with a comment which explains how it should behave. The functions are:
 + bstdb_init
 + bstdb_add
 + bstdb_get_word_count
 + bstdb_get_name
 + bstdb_stat
 + bstdb_quit
Source Code
#include "bstdb.h"
#include
#include
#include
// Write your submission in this file
//
// A main function and some profiling tools have already been set up to test
// your code in the task2.c file. All you need to do is fill out this file
// with an appropriate Binary Search Tree implementation.
//
// The input data will be books. A book is comprised of a title and a word
// count. You should store both these values in the tree along with a unique
// integer ID which you will generate.
//
// We are aiming for speed here. A BST based database should be orders of
// magnitude faster than a linked list implementation if the BST is written
// correctly.
//
// We have provided an example implementation of what a linked list based
// solution to this problem might look like in the db/listdb.c file. If you
// are struggling to understand the problem or what one of the functions
// below ought to do, consider looking at that file to see if it helps your
// understanding.
//
// There are 6 functions you need to look at. Each is provided with a comment
// which explains how it should behave. The functions are:
//
// + bstdb_init
// + bstdb_add
// + bstdb_get_word_count
// + bstdb_get_name
// + bstdb_stat
// + bstdb_quit
//
// Do not rename these functions or change their arguments/return types.
// Otherwise the profiler will not be able to find them. If you think you
// need more functionality than what is provided by these 6 functions, you
// may write additional functions in this file.
//============================================================================
struct bst_node {
  int doc_id; // unique identifier for the document
  char *name; // file name of the document
  int word_count; // number of words in the document
  struct bst_node *left; // pointer to the left node in the tree
  struct bst_node *right; // pointer to the left node in the tree
};
int capacity = 131072;
int g_next_level_capacity;
int g_next_level_size;
int g_next_id; // ID of the next document to be added
struct bst_node *g_bst_root; // database storage
int g_num_comps;
int g_num_searches;
void update_next_id(void) {
  g_next_level_size++;
  if (g_next_level_size == g_next_level_capacity) {
    g_next_level_capacity *= 2;
    g_next_level_size = 0;
  }
  g_next_id = capacity / (2 * g_next_level_capacity) +
              g_next_level_size * (capacity / g_next_level_capacity);
}
static void free_bst_node(struct bst_node *node) {
  if (node->left != NULL) {
    free_bst_node(node->left);
  }
  if (node->right != NULL) {
    free_bst_node(node->right);
  }
  free(node->name);
  free(node);
}
static int bst_node_height(struct bst_node *node) {
  if (node == NULL) {
    return 0;
  }
  int lh = bst_node_height(node->left);
  int rh = bst_node_height(node->right);
  return 1 + ((lh > rh) ? lh : rh);
}
static int bst_node_size(struct bst_node *node) {
  if (node == NULL) {
    return 0;
  }
  return 1 + bst_node_size(node->left) + bst_node_size(node->right);
}
static struct bst_node *create_bst_node(int doc_id, char *name,
                                        int word_count) {
  struct bst_node *bn;
  size_t len_name;
  // Allocate memory for the new bst node
  bn = malloc(sizeof(struct bst_node));
  // malloc can fail, so make sure ln is pointing to something before we try
  // writing to it.
  if (bn) {
    // Store data in the list node
    bn->doc_id = doc_id;
    bn->word_count = word_count;
    bn->left = NULL;
    bn->right = NULL;
    // Allocate memory to store the file name and copy the string into the
    // new bst node
    len_name = strlen(name) + 1;
    bn->name = calloc(len_name, sizeof(char));
    if (bn->name) {
      // if calloc was successful, copy the filename into the node
      strcpy(bn->name, name);
    } else {
      // if calloc failed, release any memory that was allocated and
      // report an error by returning NULL
      free(bn);
      bn = NULL;
    }
  }
  return bn;
}
int bstdb_init(void) {
  // This function will run once (and only once) when the database first
  // starts. Use it to allocate any memory you want to use or initialize
  // some globals if you need to. Function should return 1 if initialization
  // was successful and 0 if something went wrong.
  g_next_level_capacity = 1;
  g_next_level_size = 0;
  g_next_id = capacity / 2;
  g_bst_root = NULL;
  g_num_comps = 0;
  g_num_searches = 0;
  return 1;
}
int bstdb_add(char *name, int word_count) {
  // This function should create a new node in the binary search tree,
  // populate it with the name and word_count of the arguments and store
  // the result in the tree.
  //
  // This function should also generate and return an identifier that is
  // unique to this document. A user can find the stored data by passing
  // this ID to one of the two search functions below.
  //
  // How you generate this ID is up to you, but it must be an integer. Note
  // that this ID should also form the keys of the nodes in your BST, so
  // try to generate them in a way that will result in a balanced tree.
  //
  // If something goes wrong and the data cannot be stored, this function
  // should return -1. Otherwise it should return the ID of the new node
  int doc_id = g_next_id;
  struct bst_node *tmp = create_bst_node(doc_id, name, word_count);
  if (!tmp) {
    return -1;
  }
  update_next_id();
  if (g_bst_root == NULL) {
    g_bst_root = tmp;
  return doc_id;
  } else {
    struct bst_node *curr = g_bst_root;
    while (1) {
      if (curr->doc_id > doc_id) {
        if (curr->left == NULL) {
          curr->left = tmp;
          return doc_id;
        }
        curr = curr->left;
      } else {
        if (curr->right == NULL) {
          curr->right = tmp;
          return doc_id;
        }
        curr = curr->right;
      }
    }
  }
 printf("ERROR: %d\n", doc_id);
  return -1;
}
int bstdb_get_word_count(int doc_id) {
  // This is a search function. It should traverse the binary search tree
  // and return the word_count of the node with the corresponding doc_id.
  //
  // If the required node is not found, this function should return -1
  struct bst_node *curr = g_bst_root;
 g_num_searches++;
  while (curr != NULL) {
  g_num_comps++;
    if (curr->doc_id == doc_id) {
      return curr->word_count;
    }
    if (curr->doc_id > doc_id) {
      curr = curr->left;
    } else {
      curr = curr->right;
    }
  }
  return -1;
}
char *bstdb_get_name(int doc_id) {
  // This is a search function. It should traverse the binary search tree
  // and return the name of the node with the corresponding doc_id.
  //
  // If the required node is not found, this function should return NULL or 0
  struct bst_node *curr = g_bst_root;
 g_num_searches++;
  while (curr != NULL) {
  g_num_comps++;
    if (curr->doc_id == doc_id) {
      return curr->name;
    }
    if (curr->doc_id > doc_id) {
      curr = curr->left;
    } else {
      curr = curr->right;
    }
  }
  return NULL;
}
void bstdb_stat(void) {
  // Use this function to show off! It will be called once after the
  // profiler ends. The profiler checks for execution time and simple errors,
  // but you should use this function to demonstrate your own innovation.
  //
  // Suggestions for things you might want to demonstrate are given below,
  // but in general what you choose to show here is up to you. This function
  // counts for marks so make sure it does something interesting or useful.
  //
  // + Check if your tree is balanced and print the result
  //
  // + Does the number of nodes in the tree match the number you expect
  // based on the number of insertions you performed?
  //
  // + How many nodes on average did you need to traverse in order to find
  // a search result?
  //
  // + Can you prove that there are no accidental duplicate document IDs
  // in the tree?
  printf("STAT\n");
  printf("Avg comparisons per search -> %lf\n",
         (double)g_num_comps / g_num_searches);
  printf("Tree height: %d\n", bst_node_height(g_bst_root));
  printf("Tree size: %d\n", bst_node_size(g_bst_root));
}
void bstdb_quit(void) {
  // This function will run once (and only once) when the program ends. Use
  // it to free any memory you allocated in the course of operating the
  // database.
  if (g_bst_root != NULL) {
    free_bst_node(g_bst_root);
  }
}