btree.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define BT_MAX_CHILD 5
#define BT_MAX_NODE 4
#define BT_MIN_CHILD 3
#define BT_MIN_NODE 2

// v1: one BTree per unique memory_region_get_ram_ptr(mr)
//     xlat is the actual index of the arr we'll search for.
// v1.5: store a byte (2tags) per key (i.e. xlat). 
//       Then, store_tag1, load_tag1 work similar to original code.
// qemu: 1 tag array, so, for us: one BTree...
// v2: one BTree, 

#define ALLOC_FREED_ARR_SZ 10

char* global_btree_buffer; // 64-bit
long long int global_btree_buffer_first_avail; // 64-bit
int global_btree_root_offset;
int alloc_freed_nodes;
int alloc_freed_nodes_arr[ALLOC_FREED_ARR_SZ];

// total 43 bytes, rounded off to 44.
struct BTreeNode {
  int keys[BT_MAX_NODE]; // stores upto 4 32-bit keys : 16byt
  unsigned char tags[BT_MAX_NODE/2]; // stores a 4bit tag per key : 2byt
  char count; // 8bits: bits[3:0]: #keys : 1byt
  int children[BT_MAX_CHILD]; // stores upto 5 32-bit offsets. : 20byt
  int parent; // stores 32-bit parent ptr offset. : 4byt
};

// struct BTreeNode *root;
// v2: Assuming global_btree_buffer is the root ptr (cast)
// There can NEVER be duplicate keys!

void printIntArr(int* arr, int len)
{
  for (int x = 0; x < len; x++)
    printf("arr[%i] : %i, ", x, arr[x]);
  printf("\n");
}

void printCharArr(unsigned char* arr, int len)
{
  for (int x = 0; x < len; x++)
    printf("arr[%i] : %i, ", x, arr[x]);
  printf("\n");
}

void printBTreeNode(struct BTreeNode* node)
{
  printf("NODE!!! Offset: %li , parent_offset: %i , count: %i \n", ((char*)node-global_btree_buffer), node->parent, node->count);
  printIntArr(node->keys, BT_MAX_NODE);
  printCharArr(node->tags, BT_MAX_NODE/2);
  printIntArr(node->children, BT_MAX_CHILD);
}

void printBTree(struct BTreeNode* rnode, int level)
{
  printf("LEVEL %i : ", level);
  printBTreeNode(rnode);
  for (int i = 0; i <= rnode->count; i++)
    if (rnode->children[i] != -1)
      printBTree((struct BTreeNode*)(global_btree_buffer + rnode->children[i]), level+1);
}

struct BTreeNode* getGlobalRootPtr()
{
  return (struct BTreeNode*) (global_btree_buffer + global_btree_root_offset);
}

void initBTreeNode(struct BTreeNode* rnode, int parent_offset)
{
  rnode->count = 0;
  for (int i = 0; i < BT_MAX_NODE; i++)
    rnode->keys[i] = -1;
  for (int i = 0; i < BT_MAX_CHILD; i++)
    rnode->children[i] = -1; // null ptr
  rnode->parent = parent_offset;
}

void initBTree(char* global_btree_buffer)
{
  // make a new BTreeNode, with key=0,tag=0. []
  struct BTreeNode* root = (struct BTreeNode*) global_btree_buffer;
  initBTreeNode(root, -1); // parent = null ptr
  root->count = 1;
  root->keys[0] = 0;

  global_btree_buffer_first_avail += sizeof(struct BTreeNode);
  global_btree_root_offset = 0;
  alloc_freed_nodes = 0; // tracks fragmentation.

  printf("##### FINISHED initBTree: root ptr: %p, new first_avail: %lli, global_btree_root_offset: %i, alloc_freed_nodes: %i \n", root, global_btree_buffer_first_avail, global_btree_root_offset, alloc_freed_nodes);
}

unsigned char getArrIthTag(unsigned char* tag_arr, int i)
{
  return (i%2 == 1) ? ((tag_arr[i/2])%16) : (tag_arr[i/2] >> 4) ;
}

unsigned char setArrIthTag(unsigned char* tag_arr, int i, unsigned char tag)
{
  if (tag >= 16)
  {
    printf("ERRORRRRR! setArrIthTag called with invalid tag value!!! %i \n", tag);
    // throw;
  }

  if (i%2 == 1)
    tag_arr[i/2] = (tag_arr[i/2] & 0xf0) | tag;
  else
    tag_arr[i/2] = (tag_arr[i/2] & 0x0f) | (tag << 4);
  printf("Done with setArrIthTag [inputs: i: %i, tag: %i] new i/2th tag byte: %i \n", i, tag, tag_arr[i/2]);
}

// leaf if all children are -1 (i.e. null ptr)
bool isBTreeNodeLeaf(struct BTreeNode* root)
{
  for (int i = 0; i < BT_MAX_CHILD; i++)
    if (root->children[i] != -1)
      return false;
  return true;
}

// if there's any child that has the wrong parent ptr, returns false.
bool verifyBTreePtrs(struct BTreeNode* root)
{
    int root_offset = (char*) root - global_btree_buffer;
    for (int i = 0; i <= root->count; i++)
    {
        if (root->children[i] != -1)
        {
            struct BTreeNode* r_child_i = (struct BTreeNode*) (global_btree_buffer + root->children[i]);
            if (r_child_i->parent != root_offset)
                return false;
            if (!verifyBTreePtrs(r_child_i))
                return false;
        }
    }
    return true;
}

// get ptr (in terms of offset from root addr) to node containing largest key <= addr.
// note that since this func is called for random ptrs in BTree, the root input is NOT the absolute root of tree.
// Hence, child ptr = global buffer ptr + offset.
int getLargestNodeLessThan(struct BTreeNode* root, int addr)
{
  if (!root)
    return -1;

  int i=0;
  while ((i < root->count) && (root->keys[i] < addr) )
    i++;

  // case1: i = root->count: ans is in the right most child OR root node.
  if (i >= root->count)
  {
    if ( (i < BT_MAX_CHILD) && (root->children[i] != -1) )
    {
      int ans_in_right_child = getLargestNodeLessThan( (struct BTreeNode*)(global_btree_buffer + root->children[i]), addr );
      return (ans_in_right_child == -1) ? ((char*)root - global_btree_buffer) : ans_in_right_child;
    }
    else
      return ((char*)root - global_btree_buffer); // the current root node has the largest key<=addr.
  }

  // case2: keys[i] = addr: return root node!
  if (root->keys[i] == addr)
    return ((char*)root - global_btree_buffer);

  // case3: keys[i] > addr: go to the just-left child of ith key, i.e. children[i] OR root node.
  if (root->keys[i] > addr)
  {
    int ans_in_left_child = -1;
    if ( (i < BT_MAX_CHILD) && (root->children[i] != -1) )
      ans_in_left_child = getLargestNodeLessThan( (struct BTreeNode*)(global_btree_buffer + root->children[i]), addr );

    return (ans_in_left_child == -1) ? ( (i == 0) ? -1 : ((char*)root - global_btree_buffer) ) : ans_in_left_child;
  }
}

// get ptr (in terms of offset from root addr) to node containing smallest key >= addr.
// note that since this func is called for random ptrs in BTree, the root input is NOT the absolute root of tree.
// Hence, child ptr = global buffer ptr + offset.
int getSmallestNodeMoreThan(struct BTreeNode* root, int addr)
{
  if (!root)
    return -1;

  int i=(root->count)-1;
  while ( (i >= 0) && (root->keys[i] >= addr))
    i--;

  // i < (root->ct)-1 implies there's atleast one elem in root which is >= addr.
  // case1: i = -1, i.e. all elems in array are >= addr
  if (i <= -1)
  {
    if (root->children[0] != -1)
    {
      int ans_in_left_child = getSmallestNodeMoreThan( (struct BTreeNode*)(global_btree_buffer+root->children[0]) , addr);
      return (ans_in_left_child == -1) ? ((char*) root - global_btree_buffer) : ans_in_left_child;
    }
    else
      return ((char*)root - global_btree_buffer); // the current root node has the smallest key>=addr.
  }
  // case2:
  if (root->keys[i] == addr)
    return ((char*)root - global_btree_buffer);

  // case3: all elems including keys[i] are < addr. check right child of keys[i]
  if (root->keys[i] < addr)
  {
    int ans_in_right_child = -1;
    if (root->children[i+1] != -1)
      ans_in_right_child = getSmallestNodeMoreThan((struct BTreeNode*)(global_btree_buffer+root->children[i+1]) , addr);

    return (ans_in_right_child == -1) ? ((i == (root->count-1)) ? -1 : ((char*) root - global_btree_buffer) ) : ans_in_right_child;
  }
}

void getLargestKeyTagLessThan(struct BTreeNode* root, int addr, int* x_key, int* x_tag)
{
  int i=0;
  while ((i < root->count) && (root->keys[i] < addr) )
    i++;

  if (i >= root->count)
  {
    *x_key = root->keys[i-1];
    *x_tag = getArrIthTag(root->tags, i-1);
  }
  else if (root->keys[i] == addr)
  {
    *x_key = root->keys[i];
    *x_tag = getArrIthTag(root->tags, i);
  }
  else if (root->keys[i] > addr)
  {
    if (i == 0)
    {
      printf("IN getLargestKeyTagLessThan: 1st Elem in root is > addr!!! \n");
      *x_key = -1;
      *x_tag = -1;
      // throw;
    }
    *x_key = root->keys[i-1];
    *x_tag = getArrIthTag(root->tags, i-1);
  }
  else
  {
    printf("IN getLargestKeyTagLessThan: WEIRD ERROR!!!! \n");
    // throw;
  }  
}

void getSmallestKeyTagMoreThan(struct BTreeNode* root, int addr, int* x_key, int* x_tag)
{
  int i=(root->count)-1;
  while ((i >= 0) && (root->keys[i] > addr) )
    i--;

  if (i < 0) // all elems in root are >= addr
  {
    *x_key = root->keys[0];
    *x_tag = getArrIthTag(root->tags, 0);
  }
  else if (root->keys[i] == addr)
  {
    *x_key = root->keys[i];
    *x_tag = getArrIthTag(root->tags, i);
  }
  else if (root->keys[i] < addr)
  {
    if (i == (root->count - 1))
    {
      printf("IN getSmallestKeyTagMoreThan: last elem is < addr!!! \n");
      *x_key = -1;
      *x_tag = -1;
      // throw;
    }
    *x_key = root->keys[i+1];
    *x_tag = getArrIthTag(root->tags, i+1);
  }
  else
  {
    printf("IN getSmallestKeyTagMoreThan: WEIRD ERROR!!!! \n");
    // throw;
  }  
}

// adding 1 key,tag & 1 child to node
void insertBTreeKeyInNode(struct BTreeNode* rnode, int key, int tag, bool right_child, int child_offset)
{
  // find where to insert
  int i = 0;
  while ((i < rnode->count) && (rnode->keys[i] < key) )
    i++;

  // insert key at rnode->keys[i]
  // shift tags,keys,children
  int curr = key;
  int curr_tag = tag;
  int curr_child = child_offset;
  while (i <= rnode->count)
  {
    int new_curr = rnode->keys[i];
    int new_curr_tag = getArrIthTag(rnode->tags, i);
    int new_curr_child = (right_child) ? rnode->children[i+1] : rnode->children[i];

    rnode->keys[i] = curr;
    setArrIthTag(rnode->tags, i, curr_tag);
    if (right_child)
      rnode->children[i+1] = curr_child;
    else
      rnode->children[i] = curr_child;

    curr = new_curr;
    curr_tag = new_curr_tag;
    curr_child = new_curr_child;

    i++;
  }
  if (!right_child)
    rnode->children[i] = curr_child;

  if (child_offset != -1)
  {
    struct BTreeNode* child_ptr = (struct BTreeNode*) (global_btree_buffer + child_offset);
    child_ptr->parent = (char*)rnode - global_btree_buffer;
  }

  rnode->count += 1;
}


// deletes key&tag from rnode - i.e. updates keys, count, children.
// equivalent to removeVal func in programiz code.
// rebalanceBTree calls this for non-leaf nodes, so,
// del_child: if 0, delete left child of key, else delete right child of key.
bool deleteBTreeKeyFromNode(struct BTreeNode* rnode, int key, int del_child)
{
  int i = 0;
  while ((i < rnode->count) && (rnode->keys[i] != key))
    i++;

  while (i < (rnode->count-1))
  {
    // update tags, keys, children:
    rnode->keys[i] = rnode->keys[i+1];
    setArrIthTag(rnode->tags, i, getArrIthTag(rnode->tags, i+1));
    // children:
    if (del_child == 0)
      rnode->children[i] = rnode->children[i+1];
    else
      rnode->children[i+1] = rnode->children[i+2];
    i++;
  }
  rnode->keys[rnode->count - 1] = -1; // just to avoid confusion when printing/reading BTree node
  // set last tag to 0
  setArrIthTag(rnode->tags, i, 0);
  // move last child, extra move if del_left_child.
  if (del_child == 0)
    rnode->children[i] = rnode->children[i+1];

  rnode->count -= 1;

  return true;
}

// v1: return ptr to the byte containing the tag
// v2: get tag of addr granule, equiv to TagArr[addr]
// NOTE: ALWAYS CALL this func with root as the global root ptr.
unsigned char getTag(struct BTreeNode* root, int addr)
{
  struct BTreeNode* groot = (struct BTreeNode*) (global_btree_buffer + global_btree_root_offset);
  if (!root)
    return -1;

  int node_with_largest_less_than_off = getLargestNodeLessThan(getGlobalRootPtr(), addr);
  struct BTreeNode* node_with_largest_less_than = (struct BTreeNode*) (global_btree_buffer + node_with_largest_less_than_off);

  // find the largest key <= addr in the tree
  int i=0;
  while ((i < node_with_largest_less_than->count) && (node_with_largest_less_than->keys[i] < addr) )
    i++;

  // case1: i = root->count: go to the right most child OR Null.
  if (i >= node_with_largest_less_than->count)
  {
    unsigned char node_last_tag = getArrIthTag(node_with_largest_less_than->tags, i-1);
    return node_last_tag;
    /* Old:
    // if ( (i < BT_MAX_CHILD) && root->children[i])
    // {
    //   char rightmostC_tag = getTag(root->children[i], addr);
    //   return (rightmostC_tag != -1) ? rightmostC_tag : node_last_tag;
    // }
    // else
    //   return node_last_tag; // root->keys[count-1] is the largest node <= addr. */
  }

  // case2: keys[i] = addr: return ith tag!
  if (node_with_largest_less_than->keys[i] == addr)
    return getArrIthTag(node_with_largest_less_than->tags, i); // (i%2 == 1) ? ((root->tags[i/2])%16) : (root->tags[i/2] >> 4); // &(root->tags[i]);

  // case3: keys[i] > addr: go to the just-left child of ith key, i.e. children[i]
  if (node_with_largest_less_than->keys[i] > addr)
  {
    // TODO: its possible that all elems in this child are > addr.
    if (i == 0)
    {
      printf("ERRORRR: No ELEMENT in tree <= addr!!!");
      // throw;
    }
    unsigned char node_last_tag = getArrIthTag(node_with_largest_less_than->tags, i-1);
    return node_last_tag;
    // Old code: 
    // char leftC_tag = getTag(root->children[i], addr);
    // return (leftC_tag != -1) ? leftC_tag : node_last_tag;
  }
}

// re-balance, starting from a deficient leaf node:
void rebalanceBTree(struct BTreeNode* rnode)
{
  struct BTreeNode* rleaf = rnode;
  int iter_ct = 0;
  while (iter_ct < 20)
  {
    int rleaf_offset = (char*) rleaf - global_btree_buffer;
    
    printf("IN rebalanceBTree: for node %p, parent: %i \n", rleaf, rleaf->parent);

    if (rleaf->parent != -1)
    {
      struct BTreeNode* rleaf_parent = (struct BTreeNode*) (global_btree_buffer + rleaf->parent);
      int i = 0;
      while ((i <= rleaf_parent->count) && (rleaf_parent->children[i] != rleaf_offset))
        i++;

      struct BTreeNode* rleaf_left_bro = NULL;
      struct BTreeNode* rleaf_right_bro = NULL;

      int rleaf_left_bro_offset = -1, rleaf_right_bro_offset = -1;

      // check right sibling:
      if ((i < rleaf_parent->count) && (rleaf_parent->children[i+1] != -1))
      {
        rleaf_right_bro_offset = rleaf_parent->children[i+1];
        rleaf_right_bro = (struct BTreeNode*) (global_btree_buffer + rleaf_parent->children[i+1]);
        if (rleaf_right_bro->count > BT_MIN_NODE)
        {
          // separator key moves to rleaf
          rleaf->keys[rleaf->count] = rleaf_parent->keys[i];
          setArrIthTag(rleaf->tags, rleaf->count, getArrIthTag(rleaf_parent->tags, i));
          rleaf->count += 1;

          // use rleaf_right_bro->children[0] as the last child of rleaf:
          rleaf->children[rleaf->count] = rleaf_right_bro->children[0];
          if (rleaf_right_bro->children[0] != -1)
          {
            struct BTreeNode* rl_right_bro_c0 = (struct BTreeNode*) (global_btree_buffer + rleaf_right_bro->children[0]);
            rl_right_bro_c0->parent = rleaf_offset;
          }

          // delete left most key from rleaf_right_bro, 
          // use it to replace separator_key in rleaf_parent.
          rleaf_parent->keys[i] = rleaf_right_bro->keys[0];
          setArrIthTag(rleaf_parent->tags, i, getArrIthTag(rleaf_right_bro->tags, 0));
          deleteBTreeKeyFromNode(rleaf_right_bro, rleaf_right_bro->keys[0], 0); // ensures we delete left child of key[0], i.e. child[0]
         
          printf("IN rebalanceBTree: rotated with rleaf_right_bro: %p", rleaf_right_bro);
          printBTreeNode(rleaf);
          printBTreeNode(rleaf_right_bro);
          printBTreeNode(rleaf_parent);

          return;
        }
      }
      // check if can rotate with left sibling:
      if ((i > 0) && (rleaf_parent->children[i-1] != -1))
      {
        rleaf_left_bro_offset = rleaf_parent->children[i-1];
        rleaf_left_bro = (struct BTreeNode*) (global_btree_buffer + rleaf_parent->children[i-1]);
        if (rleaf_left_bro->count > BT_MIN_NODE)
        {
          // separator key moves to rleaf TODO: this will move at rleaf->keys[0], slide all existing keys/children/tags:
          insertBTreeKeyInNode(rleaf, rleaf_parent->keys[i-1], getArrIthTag(rleaf_parent->tags,i-1), 0, rleaf_left_bro->children[rleaf_left_bro->count]);
          // rleaf->keys[rleaf->count] = rleaf_parent->keys[i-1];
          // setArrIthTag(rleaf->tags, rleaf->count, getArrIthTag(rleaf_parent->tags, i-1));
          // rleaf->count += 1;

          // make rleaf_left_bro's last child, the first child of rleaf: [Doing this as part of insertBTreeKeyInNode]
          // rleaf->children[0] = rleaf_left_bro->children[rleaf_left_bro->count];

          // delete rightmost key from rleaf_left_bro, use it to replace separator_key in rleaf_parent.
          rleaf_parent->keys[i-1] = rleaf_left_bro->keys[rleaf_left_bro->count-1];
          setArrIthTag(rleaf_parent->tags, i-1, getArrIthTag(rleaf_left_bro->tags, rleaf_left_bro->count-1));
          deleteBTreeKeyFromNode(rleaf_left_bro, rleaf_left_bro->keys[rleaf_left_bro->count-1], 1 ); // deleting right child of last key

          printf("IN rebalanceBTree: rotated with rleaf_right_bro: %p", rleaf_left_bro);
          printBTreeNode(rleaf);
          printBTreeNode(rleaf_left_bro);
          printBTreeNode(rleaf_parent);

          return;
        }
      }
      // Need to merge: [no sibling with >min_keys]
      // put separator, rleaf->keys in either left_bro or right_bro.
      if (rleaf_left_bro != NULL)
      {
        // put separator in rleaf_left_bro
        rleaf_left_bro->keys[rleaf_left_bro->count] = rleaf_parent->keys[i-1];
        setArrIthTag(rleaf_left_bro->tags, rleaf_left_bro->count, getArrIthTag(rleaf_parent->tags,i-1));
        rleaf_left_bro->count += 1;

        // put rleaf->keys in rleaf_left_bro
        for (int rx = 0; rx < rleaf->count; rx++)
        {
          rleaf_left_bro->keys[rleaf_left_bro->count] = rleaf->keys[rx];
          setArrIthTag(rleaf_left_bro->tags, rleaf_left_bro->count, getArrIthTag(rleaf->tags,rx));
          rleaf_left_bro->children[rleaf_left_bro->count] = rleaf->children[rx];
          if (rleaf->children[rx] != -1)
          {
            struct BTreeNode* rleaf_child_rx = (struct BTreeNode*) (global_btree_buffer + rleaf->children[rx]);
            rleaf_child_rx->parent = rleaf_left_bro_offset;
          }
          rleaf_left_bro->count += 1;
        }
        rleaf_left_bro->children[rleaf_left_bro->count] = rleaf->children[rleaf->count];
        if (rleaf->children[rleaf->count] != -1)
        {
          struct BTreeNode* rleaf_child_last = (struct BTreeNode*) (global_btree_buffer + rleaf->children[rleaf->count]);
          rleaf_child_last->parent = rleaf_left_bro_offset;
        }

        // delete separator from parent: delete right child of this key
        deleteBTreeKeyFromNode(rleaf_parent, rleaf_parent->keys[i-1], 1); // rleaf_parent is a non leaf node!!!

        printf("IN rebalanceBTree: Merged with rleaf_left_bro: %p \n", rleaf_left_bro);
        printBTreeNode(rleaf_left_bro);
        printBTreeNode(rleaf_parent);

      }
      else if (rleaf_right_bro != NULL)
      {
        // Done: Handle children here!! [insertBTreeKeyInNode handles it]
        // children rleaf_right_bro: key_ct += 1+rleaf->ct, child_ct += 0+rleaf->ct+1. Works!

        // put rleaf's keys in rleaf_right_bro
        for (int lx = 0; lx < rleaf->count; lx++)
          insertBTreeKeyInNode(rleaf_right_bro, rleaf->keys[lx], getArrIthTag(rleaf->tags,lx), 0, rleaf->children[lx]);
      
        // put separator in rleaf_right_bro
        insertBTreeKeyInNode(rleaf_right_bro, rleaf_parent->keys[i], getArrIthTag(rleaf_parent->tags, i), 0, rleaf->children[rleaf->count]);

        // delete separator from parent: delete left child of this key
        deleteBTreeKeyFromNode(rleaf_parent, rleaf_parent->keys[i], 0);

        printf("IN rebalanceBTree: Merged with rleaf_right_bro: %p \n", rleaf_right_bro);
        printBTreeNode(rleaf_right_bro);
        printBTreeNode(rleaf_parent);

      }
      else
      {
        printf("ERRORRR!!! Both left, right bros are NULL!! \n");
        // throw;
      }
      // 'delete' rleaf node.
      alloc_freed_nodes_arr[alloc_freed_nodes%ALLOC_FREED_ARR_SZ] = rleaf_offset;
      alloc_freed_nodes += 1;
      printf("IN rebalanceBTree: UPDATED alloc_freed_nodes to %i \n", alloc_freed_nodes);
      printIntArr(alloc_freed_nodes_arr, ALLOC_FREED_ARR_SZ);

      // Call re-balance on rleaf_parent, if needed
      if (rleaf_parent->count == 0)
      {
        if (rleaf_parent->parent != -1)
        {
          printf("ERRORRR: SOMEHOW NON-ROOT node is EMPTY!!!!");
          // throw;
        }
        else
        {
          // make rleaf_left/right_bro as the new root.
          struct BTreeNode* new_root = (rleaf_left_bro != NULL) ? rleaf_left_bro : rleaf_right_bro;
          new_root->parent = -1;
          global_btree_root_offset = (char*) new_root - global_btree_buffer;
          alloc_freed_nodes_arr[alloc_freed_nodes%ALLOC_FREED_ARR_SZ] = global_btree_root_offset;
          alloc_freed_nodes += 1;

          printf("IN rebalanceBTree: JUST MODIFIED the global_btree_root_offset to %i !!!! \n", global_btree_root_offset);
          return;
        }
      }
      if (rleaf_parent->count < BT_MIN_NODE)
        rleaf = rleaf_parent;
      else
        return; // WE ARE DONE!!! [Update: Mar24] If we dont return, we'll recurse again on rleaf (which is deleted actually!)
    }
    else
    {
      // rleaf is the root Node. Its okay for it to be deficient.
      printf("ROOT has %i keys, < min %i \n", rleaf->count, BT_MIN_NODE);
      if (rleaf->count == 0)
      {
        printf("ERRORRR!!!! Somehow ROOT is empty, and we called rebalance!! \n");
        // throw; // this should never happen!
      }
      return;
    }
    iter_ct++;
  }
  printf("ERRORRRRRR!!!!!! RECURSION IN deleteBTreeKey MORE THAN 20 TIMES!!!!");
}


// deletes key from rnode, and tries to balance the BTree
bool deleteBTreeKey(struct BTreeNode* rnode, int key)
{
  if (isBTreeNodeLeaf(rnode))
  {
    deleteBTreeKeyFromNode(rnode, key, 1);
    if (rnode->count < BT_MIN_NODE)
    {
      // re-balance
      rebalanceBTree(rnode);
    }
  }
  else
  {
    int i = 0;
    while ((i < rnode->count) && (rnode->keys[i] != key))
      i++;
    // Need to find a replacement for this key: largest key' < key OR smallest key' > key
    // node with smallest elem >= key.
    int smallest_node_more_key_off = getSmallestNodeMoreThan( (struct BTreeNode*)(global_btree_buffer + rnode->children[i+1]), key );
    struct BTreeNode* smallest_node_more_key = (struct BTreeNode*) (global_btree_buffer + smallest_node_more_key_off);
    // replacement should be in a leaf.
    if (!isBTreeNodeLeaf(smallest_node_more_key))
    {
      printf("IN deleteBTreeKey: ERRORRRR!!!! smallestNodeMoreThan key %i is NOT a leaf!!! \n", key);
      // throw;
    }
    // remove the replacement (key,tag) from its leaf and put it in rnode (at ith place)
    int sj = smallest_node_more_key->count-1;
    while ( (sj >= 0) && (smallest_node_more_key->keys[sj] > key) )
      sj--;

    printf("IN deleteBTreeKey: Deleting %i from node %p, borrowing key %i from leaf_ptr %p \n", key, rnode, smallest_node_more_key->keys[sj+1], smallest_node_more_key);

    rnode->keys[i] = smallest_node_more_key->keys[sj+1]; // this was previously key, replacing with smallest > key.
    setArrIthTag(rnode->tags, i, getArrIthTag(smallest_node_more_key->tags, sj+1) );
    deleteBTreeKeyFromNode(smallest_node_more_key, smallest_node_more_key->keys[sj+1], 1); // note smallest_node_more_key is a leaf

    printBTreeNode(rnode);
    printBTreeNode(smallest_node_more_key);

    // if leaf count < BT_MIN_NODE
    if (smallest_node_more_key->count < BT_MIN_NODE)
    {
      // re-balance
      rebalanceBTree(smallest_node_more_key);
    }
  }
}

int findLeafNodeToInsertAddr(struct BTreeNode* rnode, int addr)
{
  if (isBTreeNodeLeaf(rnode))
    return (char*)rnode - global_btree_buffer;

  int i = 0;
  while (i < rnode->count && (rnode->keys[i] < addr) )
    i++;

  if ( rnode->children[i] == -1)
  {
    printf("In findLeafNodeToInsertAddr: ERROR!!! Non leaf node (count=%i) has null child (%ith child: %i)!!! \n", rnode->count, i, rnode->children[i]);
    // throw;
  }
  else
    return findLeafNodeToInsertAddr( (struct BTreeNode*)(global_btree_buffer + rnode->children[i]), addr );
  // leftmost / rightmost / middle child:
  // if (i == rnode->count)
  //   return findLeafNodeToInsertAddr( global_btree_buffer + rnode->children[i], addr);
  // else if (i == 0)
  //   return findLeafNodeToInsertAddr( global_btree_buffer + rnode->children[0], addr);
}

// splits rnode->keys + insert_addr array.
// returns offset for new node, and writes median_key to the ptr, and tag for median key to the ptr.
// ASSUMES rnode has BT_MAX_NODE keys!!!
// Note: need to pass new child ptr too, since we need it to correctly update children of new_node_right that we make here:
int splitNode(struct BTreeNode* rnode, int insert_addr, int insert_tag, int insert_child_right_offset, int* pmedian_key, unsigned char* pmedian_tag)
{
  if (rnode->count < BT_MAX_NODE)
  {
    printf("SPLITNODE CALLED for NON-FULL node!!!");
    // throw;
  }
  // find median, split.
    int i = 0; 
    while ( (i < rnode->count) && (rnode->keys[i] < insert_addr) )
      i++;

    // ith elem would be addr, elems i - count will be shifted to right.
    int median_id = (rnode->count + 1)/2;
    int median_key = (median_id < i) ? rnode->keys[median_id] : ( (median_id == i) ? insert_addr : (rnode->keys[median_id-1]) ) ;

    // make new arr with rnode->count + 1 elems. Will make updating rnode, new_node_right MUCH easier.
    int full_arr[rnode->count+1];
    unsigned char full_tag_arr[ (int)ceil((rnode->count+1)/2.0) ]; // Note: important to divide by 2.0, o.w. ct/2 was int division.
    int full_children_arr[rnode->count+2];

    // printf("rnode->count %i, %f, ceil((rnode->count+1)/2): %f, int_cast: %i \n", rnode->count, (rnode->count+1)/2.0, ceil((rnode->count+1)/2.0), (int)ceil((rnode->count+1)/2.0));
    for (int xx = 0; xx < (int)ceil((rnode->count+1)/2.0); xx++)
      full_tag_arr[xx] = 0;
      // printf("full_tag_arr[%i] : %i \n", xx, full_tag_arr[xx]);

    for (int j = 0; j < i; j++)
    {
      full_arr[j] = rnode->keys[j];
      setArrIthTag(full_tag_arr, j, getArrIthTag(rnode->tags, j) );
      full_children_arr[j] = rnode->children[j];
    }
    full_arr[i] = insert_addr;
    setArrIthTag(full_tag_arr, i, insert_tag);
    full_children_arr[i] = rnode->children[i]; // note that this child would've been split in a previous recursive call.
    full_children_arr[i+1] = insert_child_right_offset; // the new_node_right made by previous recursive call
    for (int j = i; j < rnode->count; j++)
    {
      full_arr[j+1] = rnode->keys[j];
      setArrIthTag(full_tag_arr, j+1, getArrIthTag(rnode->tags, j) );
      full_children_arr[j+2] = rnode->children[j+1];
    }

    // update rnode keys & count & children:
    // We DO need to update full_chil_arr[0 - median_id]->parent to rnode?
    // median_id is always <= rnode->count, but we dont know where insert_addr, insert_child_right_offset are in the full_arr!
    for (int j = 0; j < BT_MAX_CHILD; j++)
    {
      if (j<median_id)
      {
        rnode->keys[j] = full_arr[j];
        setArrIthTag(rnode->tags, j, getArrIthTag(full_tag_arr, j) );
        rnode->children[j] = full_children_arr[j];        
      }
      else if (j == median_id)
        rnode->children[j] = full_children_arr[j];
      else
        rnode->children[j] = -1; // null ptrs

      // Update children's parent to rnode, for j <= median_id:
      if ((j <= median_id) && (full_children_arr[j] != -1))
      {
        struct BTreeNode* full_child_j = (struct BTreeNode*) (global_btree_buffer + full_children_arr[j]);
        full_child_j->parent = (char*)rnode - global_btree_buffer;
      }
    }
    rnode->count = median_id;

    // update the return values:
    *pmedian_key = full_arr[median_id];
    *pmedian_tag = getArrIthTag(full_tag_arr, median_id);

    // Split rnode: elems>median_key in new node.
    struct BTreeNode* new_node_right = (struct BTreeNode*) (global_btree_buffer + global_btree_buffer_first_avail);
    int new_node_right_offset = global_btree_buffer_first_avail;
    global_btree_buffer_first_avail += sizeof(struct BTreeNode);
    // new_node_right->count = rnode->count / 2;
    
    // add keys, tags, children to new_node_right.
    for (int j = 0; j < BT_MAX_CHILD; j++)
    {
      int jth_id = j+median_id+1;
      struct BTreeNode* new_node_right_child = NULL;
      if (full_children_arr[jth_id] != -1)
        new_node_right_child = (struct BTreeNode*) (global_btree_buffer + full_children_arr[jth_id]);

      if (jth_id < (BT_MAX_NODE+1))
      {
        new_node_right->keys[j] = full_arr[jth_id];
        setArrIthTag(new_node_right->tags, (j), getArrIthTag(full_tag_arr, jth_id) );
        new_node_right->children[j] = full_children_arr[jth_id];
        if (new_node_right_child)
          new_node_right_child->parent = new_node_right_offset;
        new_node_right->count += 1;
      }
      else if ( jth_id == (BT_MAX_NODE + 1) )
      {
        new_node_right->children[j] = full_children_arr[jth_id]; // last elem of full_children_arr
        if (new_node_right_child)
          new_node_right_child->parent = new_node_right_offset;
      }
      else
        new_node_right->children[j] = -1; // NULL ptr
    }

    // update new_node_right's parent ptr:
    new_node_right->parent = rnode->parent;

    printf("SPLIT node ptr %p (%li) [orig ct: %i, new ct: %i] [inserting addr: %i, median_key: %i (full_arr[%i]: %i), new_node_right ptr: %p (%li), count: %i] \n", rnode, (char*)rnode - global_btree_buffer, BT_MAX_NODE, rnode->count, insert_addr, median_key, median_id, full_arr[median_id], new_node_right, (char*)new_node_right - global_btree_buffer, new_node_right->count);
    printBTreeNode(rnode);
    printBTreeNode(new_node_right);
    return ((char*)new_node_right - global_btree_buffer);
}

bool insertBTreeKey(int addr, unsigned char tag)
{
  // find the leaf where we'll insert addr:
  int leaf_to_insert_offset = findLeafNodeToInsertAddr(getGlobalRootPtr(), addr);
  struct BTreeNode* leaf_to_insert = (struct BTreeNode*) (global_btree_buffer + leaf_to_insert_offset);

  printf("IN insertBTreeKey: addr: %i, tag: %i, leaf_to_insert_offset: %i \n", addr, tag, leaf_to_insert_offset);

  // we recurse, and update insert_addr, insert_tag, insert_child_right, node_to_insert in each iteration:
  int insert_addr = addr;
  int insert_tag = tag;
  int insert_child_right_offs = -1;
  struct BTreeNode* node_to_insert = leaf_to_insert;
  while (true)
  {
    if (node_to_insert->count < BT_MAX_NODE)
    {
      // just insert in this leaf & done
      int i = 0; 
      while ( (i < node_to_insert->count) && (node_to_insert->keys[i] < insert_addr) )
        i++;
      
      if (i == node_to_insert->count)
      {
        node_to_insert->keys[i] = insert_addr;
        node_to_insert->children[i+1] = insert_child_right_offs;
        setArrIthTag(node_to_insert->tags, i, insert_tag);
      }
      else
      {
        // move all other elems [keys, tags, children] to right.
        int curr = node_to_insert->keys[i];
        int curr_tag = getArrIthTag(node_to_insert->tags, i);
        int curr_child = node_to_insert->children[i+1];

        // put insert_addr at i:
        node_to_insert->keys[i] = insert_addr;
        setArrIthTag(node_to_insert->tags, i, insert_tag);
        node_to_insert->children[i+1] = insert_child_right_offs;
        i++;
        while (i <= node_to_insert->count)
        {
          int new_curr = node_to_insert->keys[i];
          int new_curr_tag = getArrIthTag(node_to_insert->tags, i);
          int new_curr_child = node_to_insert->children[i+1];
          node_to_insert->keys[i] = curr;
          setArrIthTag(node_to_insert->tags, i, curr_tag);
          node_to_insert->children[i+1] = curr_child;

          curr = new_curr;
          curr_tag = new_curr_tag;
          curr_child = new_curr_child;
          i++;
        }
      }

      // update insert_child_right's parent to node_to_insert.
      if (insert_child_right_offs != -1)
      {
        struct BTreeNode* insert_child_right = (struct BTreeNode*) (global_btree_buffer + insert_child_right_offs);
        insert_child_right->parent = (char*)(node_to_insert) - global_btree_buffer;
      }

      node_to_insert->count += 1;
      return true;
    }
    else
    {
      // get median key, push to parent. Parent might split too, recurse till root.    
      int median_key;
      unsigned char median_tag;
      int new_node_right_offset = splitNode(node_to_insert, insert_addr, insert_tag, insert_child_right_offs, &median_key, &median_tag);

      // recurse to parent:
      if (node_to_insert->parent == -1) // node_to_insert was root
      {
        // Construct new root!
        struct BTreeNode* new_root = (struct BTreeNode*)(global_btree_buffer + global_btree_buffer_first_avail);
        initBTreeNode(new_root, -1); // parent = -1
        new_root->keys[0] = median_key;
        setArrIthTag(new_root->tags, 0, median_tag);
        new_root->children[0] = (char*)node_to_insert - global_btree_buffer;
        new_root->children[1] = new_node_right_offset;
        new_root->count = 1;

        // update parents of node_to_insert & new_node_right_offset:
        node_to_insert->parent = global_btree_buffer_first_avail;
        struct BTreeNode* new_node_right = (struct BTreeNode*)(global_btree_buffer+new_node_right_offset);
        new_node_right->parent = global_btree_buffer_first_avail;

        // update global_btree_root_offset, first_avail
        global_btree_root_offset = global_btree_buffer_first_avail; // (char*)new_root - global_btree_buffer;
        global_btree_buffer_first_avail += sizeof(struct BTreeNode);
        printf("IN insertBTreeKey: JUST MODIFIED the global_btree_root_offset to %i !!!! \n", global_btree_root_offset);

        return true;
      }
      else
      {
        int node_to_insert_offset = node_to_insert->parent;
        // recurse here:
        insert_addr = median_key;
        insert_tag = median_tag;
        insert_child_right_offs = new_node_right_offset;
        node_to_insert = (struct BTreeNode*) (global_btree_buffer + node_to_insert_offset);

        printf("IN insertBTreeKey: Recursing for splitNode on node %p , inserting addr %i \n", node_to_insert, insert_addr);
      }
      
    }
  }

  
}

// set tag of addr granule.
// TODO: root is at (global_btree_buffer + global_btree_root_offset)
void setTag(struct BTreeNode* root, int addr, int tag)
{
  printf("STARTING setTag root: %p , addr: %i, tag: %i \n", root, addr, tag);
  // struct BTreeNode* groot = (struct BTreeNode*) (global_btree_buffer + global_btree_root_offset);
  // first find largest key x <= addr.
  if (!root)
    return;

  int largest_node_less_offset = getLargestNodeLessThan(getGlobalRootPtr(), addr);
  int tag_x = -1, x = -1, x_ind = -1;
  struct BTreeNode* largest_node_less = NULL;
  if (largest_node_less_offset != -1)
  {
    // get tag_x, x from largest_node_less_offset:
    largest_node_less = (struct BTreeNode*) (global_btree_buffer + largest_node_less_offset);
    getLargestKeyTagLessThan(largest_node_less, addr, &x, &tag_x);

    x_ind = 0;
    while ((x_ind < largest_node_less->count) && (largest_node_less->keys[x_ind] != x))
      x_ind++;
  }
  else
  {
    printf("IN setTag: COULDN'T FIND ANY x <= addr (%i) !!! \n", addr);
    // throw;
  }

  // if tag[x] = tag, done
  if (tag_x == tag)
  {
    printf("IN setTag: [x: %i] Returning cuz current tag for addr %i is %i \n !!!", x, addr, tag_x);
    return;
  }

  // Find the run on immediate right (xnext) i.e. smallest>x, smallest>=x+1. Needed for later logic.
  int smallest_node_more_x_offset = getSmallestNodeMoreThan(getGlobalRootPtr(), x+1);
  int tag_xnext = -1, xnext = -1;
  struct BTreeNode* smallest_node_more_x = NULL;

  int tag_xprev = -1, xprev = -1;

  if (smallest_node_more_x_offset != -1)
  {
    // This offset could be -1!!! (i.e. x is the last run)
    smallest_node_more_x = (struct BTreeNode*) (global_btree_buffer + smallest_node_more_x_offset);
    getSmallestKeyTagMoreThan(smallest_node_more_x, x+1, &xnext, &tag_xnext);    
  }

  printf("Midway thru setTag: x: %i, tag_x: %i, xnext: %i, tag_xnext: %i \n", x, tag_x, xnext, tag_xnext);

  // Possibility of merging with left run.
  if (x == addr)
  {
    // find xprev: largest key < x. i.e. largest <= (x-1)
    int largest_node_less_x_offset = getLargestNodeLessThan( getGlobalRootPtr(), x-1);

    printf("IN setTag: largest_node_less_offset: %i \n", largest_node_less_x_offset);

    // This offset could be -1!!! (i.e. x is the first run)
    if (largest_node_less_x_offset != -1)
    {
      struct BTreeNode* largest_node_less_x = (struct BTreeNode*) (global_btree_buffer + largest_node_less_x_offset);
      getLargestKeyTagLessThan(largest_node_less_x, x-1, &xprev, &tag_xprev);

      printf("IN setTag: xprev: %i , tag_xprev: %i \n", xprev, tag_xprev);

      // if tag = tag[xprev] & addr=x : [merge with xprev run]
      if (tag == tag_xprev)
      {
        // if xnext > (x+1) OR there is no xnext: change x to x+1. 
        if ((xnext > (x+1)) || (xnext == -1))
        {
          // change largest_node_less keys arr: replace x by x+1.
          int i = 0;
          while ((i < largest_node_less->count) && (largest_node_less->keys[i] != x))
            i++;
          largest_node_less->keys[i] = x+1;

          printf("IN setTag: addr: %i, x: %i, xnext: %i, xprev: %i, tag_xprev: %i [largest_node_less,Returning!] \n", addr, x, xnext, xprev, tag_xprev);
          printBTreeNode(largest_node_less);

          return;
        }
        // else: delete key x: a. shrink node[keys], b. if node empty: ??
        else if (xnext == (x+1))
        {
          deleteBTreeKey(largest_node_less, x);

          printf("IN setTag: addr: %i, x: %i, xnext: %i, xprev: %i, tag_xprev: %i [largest_node_less,Returning!] \n", addr, x, xnext, xprev, tag_xprev);
          printBTreeNode(largest_node_less);

          return;
        }
      }
    }
    
  }
  
  // find xnext: smallest key > x.
  // else if tag = tag[xnext] & addr=xnext-1: [merge with xnext run]
  // if xnext == -1, we won't enter this conditional.
  if ((addr == (xnext - 1) ) && (tag == tag_xnext))
  {
    if (xnext > (x+1))
    {
      // Done: Change xnext value to xnext-1, in smallest_node_more_x:
      int i = smallest_node_more_x->count-1;
      while ( (i >= 0) && (smallest_node_more_x->keys[i] > xnext) )
        i--;
      smallest_node_more_x->keys[i] = xnext-1;

      printf("IN setTag: addr: %i, x: %i, xnext: %i, xprev: %i, tag_xprev: %i, tag_xnext: %i [smallest_node_more_x,Returning!] \n", addr, x, xnext, xprev, tag_xprev, tag_xnext);
      printBTreeNode(smallest_node_more_x);

      return;
    }
    else
    {
      // delete x and replace xnext in smallest_node_more_x by xnext-1 = x.
      // Option1: delete x, delete (xnext,tag) & insert (x,tag)
      // THIS: Option2: update x' tag to xnext_tag & delete (xnext,tag)
      
      setArrIthTag(largest_node_less->tags, x_ind, tag_xnext);
      deleteBTreeKey(smallest_node_more_x, xnext);

      printf("IN setTag: addr: %i, x: %i, xnext: %i, xprev: %i, tag_xprev: %i, tag_xnext: %i [smallest_node_more_x,Returning!] \n", addr, x, xnext, xprev, tag_xprev, tag_xnext);
      printBTreeNode(smallest_node_more_x);

      return;
    }
  }

  // DONE: else [split x into 3 keys]: x,tag[x] | addr,tag | addr+1, i.e. potentially inserting 2 new keys.
  {
    printf("IN setTag: Couldn't merge newTag with left/right runs. Splitting x into 3 keys \n");
    // x <= addr
    if (x < addr)
    {
      // insert addr,tag as new key
      insertBTreeKey(addr, tag);      
    }
    else
      setArrIthTag(largest_node_less->tags, x_ind, tag);
    // insert a+1,tag_x as new key, BUT if addr+1 = xnext, then addr+1's tag is actually tag_xnext,
    // we dont need to insert (addr+1,tag) separately.
    if ((xnext == -1) || ((addr+1) < xnext))
      insertBTreeKey(addr+1, tag_x);
  
    printBTreeNode(largest_node_less);
    printBTreeNode(getGlobalRootPtr());
  }

  // Potential perf optimizations: a. store prev, next tag? | b. store prev,next ptr? | c. store run length alongwith tag?

}

void insertAndTestRun(int start_ind, int len, unsigned char tag, int total_len)
{
  printf("RUNNING insertAndTestRun with start_ind: %i, len: %i, tag: %i \n", start_ind, len, tag);
  for (int i = start_ind; i < (start_ind+len); i++)
  {
    setTag(getGlobalRootPtr(), i, tag);
  }
  printf("global_btree_root_offset: %i , alloc_freed_nodes: %i \n", global_btree_root_offset, alloc_freed_nodes);
  
  for (int i = 0; i < total_len; i++)
    printf("Tag for addr=%i : %i, ", i, getTag(getGlobalRootPtr(), i));
  printf("\n");
}

void fullTest1()
{
    // TEST1: do 4 allocs, (0,5) (3,4) (9,3) (12,2)
  // root (9) has 2 kids (0|3) and (12|16)
  int total_len = 16;
  insertAndTestRun(0, 3, 5, total_len);
  insertAndTestRun(3, 6, 4, total_len);
  insertAndTestRun(9, 3, 3, total_len);
  insertAndTestRun(12, 4, 2, total_len);
}

void fullTest2()
{
  int total_len = 15;
  // root with 1 key (10), 2 children (0|4) and (14|15)
  insertAndTestRun(0, 4, 1, total_len);
  insertAndTestRun(4, 6, 2, total_len);
  insertAndTestRun(10, 4, 3, total_len);
  insertAndTestRun(14, 1, 4, total_len);
  // insertAndTestRun(15, 1, 5, total_len);

  // setTag of 14th to , which will delete one key, requiring a merge-Left. Leading to a single root node.
  setTag(getGlobalRootPtr(), 14, 0);
  for (int i = 0; i < total_len; i++)
    printf("Tag for addr=%i : %i, ", i, getTag(getGlobalRootPtr(), i));
}

void fullTest3(bool ttype)
{
  int total_len = 16;
  // root with 1 key (10), 2 children (0|4) and (14|15)
  insertAndTestRun(0, 4, 1, total_len);
  insertAndTestRun(4, 1, 2, total_len);
  insertAndTestRun(5, 9, 3, total_len);
  insertAndTestRun(14, 2, 4, total_len);
  // insertAndTestRun(15, 1, 5, total_len);

  // setTag of 4th to , which will delete one key, requiring a merge-Right. Leads to a single root node.
  if (ttype)
    setTag(getGlobalRootPtr(), 4, 3); // del from root, causes root to borrow from right child, then rebalance called on right child
  else
    setTag(getGlobalRootPtr(), 4, 1); // del from left child, causes merge right.
  for (int i = 0; i < total_len; i++)
    printf("Tag for addr=%i : %i, ", i, getTag(getGlobalRootPtr(), i));
  printBTree(getGlobalRootPtr(), 0);
}

void fullTest4()
{
  int total_len = 48;
  printBTreeNode(getGlobalRootPtr());
  insertAndTestRun(0, 4, 1, total_len); // root: 2keys
  insertAndTestRun(5, 9, 3, total_len); // root: 4keys 0|4|5|14
  insertAndTestRun(4, 3, 2, total_len); // issue(resolved) - need to insertKey (addr+1,tag) only if addr+1<xnext OR if xnext=-1
  insertAndTestRun(10, 4, 2, total_len);
  insertAndTestRun(14, 1, 4, total_len);
  insertAndTestRun(17, 4, 5, total_len);
  insertAndTestRun(21, 3, 6, total_len);
  insertAndTestRun(24, 3, 7, total_len); // issue(Resolved): why is tag[24]=-1?
  printBTreeNode(getGlobalRootPtr());
  insertAndTestRun(27, 3, 8, total_len); // issue(RESOLVED) - need to use unsigned char for tags (range 0-255)
  insertAndTestRun(30, 3, 9, total_len);
  insertAndTestRun(35, 3, 10, total_len);
  insertAndTestRun(38, 3, 11, total_len);
  printBTreeNode(getGlobalRootPtr()); // here, root has 4keys, child0-3 have 2kyes, child4 has 4keys
  insertAndTestRun(41, 3, 12, total_len);
  insertAndTestRun(44, 3, 13, total_len); // now 2-level BTree 
  // issue(resolved): when splitting node n into n,n2, need to update n's children's parent ptr to n2.
  // issue(Resolved): when putting children ptr into new_node_right in splitNode, there was a 1-off error in child-ids.
  printBTree(getGlobalRootPtr(), 0); // root (24), 2 children, (7,15) and (33,41)

  printf("CALLING verifyBTree: %i \n", verifyBTreePtrs(getGlobalRootPtr()));

  // to cause multi level merging:
  insertAndTestRun(14, 1, 0, total_len);
  printBTree(getGlobalRootPtr(), 0);
}

int main(int argc, char const *argv[])
{
  printf("TESTING our B-Tree!!!! \n");

  // Init global_buffer
  if (!global_btree_buffer)
  {
    global_btree_buffer = malloc(16*1024);
    initBTree(global_btree_buffer);
  }
  struct BTreeNode* groot = (struct BTreeNode*) (global_btree_buffer + global_btree_root_offset);
  printf("global buffer: %p , global_btree_root_offset: %i \n", global_btree_buffer, global_btree_root_offset);

  // fullTest1();
  // fullTest2();
  // fullTest3(0);
  fullTest4();
  return 0;
}