btree_per_small_page.cpp

#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <cstdlib>
#include <unistd.h>
#include <sys/auxv.h>
#include <sys/mman.h>
#include <sys/prctl.h>
#include <math.h>
#include <time.h>
#include <fstream>

// Number of small pages: (considering max 64GB RAM)
#define SMALL_PAGE_SIZE 4 // 4KB 4*1024
#define MAX_NUMBER_OF_SMALL_PAGES (64*1024*1024)/SMALL_PAGE_SIZE // 16777216
#define PER_PAGE_BTREE_SZ (SMALL_PAGE_SIZE*1024)/32

// #define DEBUG
// #define BIGTAG // if we want 8bit tags
#define FREED_NODES_BITARR // if we want to store freed nodes' addresses in the form of a bit array.

// COPY btree full code
#define BT_MAX_CHILD 5
#define BT_MAX_NODE 4
#define BT_MIN_CHILD 3
#define BT_MIN_NODE 2

#ifdef BIGTAG
#define PER_NODE_TAGARR_NUM_BYTES BT_MAX_NODE
#define MAX_TAG_VALUE 255
#define INVALID_TAG_VALUE 256
#else
#define PER_NODE_TAGARR_NUM_BYTES BT_MAX_NODE/2
#define MAX_TAG_VALUE 15
#define INVALID_TAG_VALUE 16
#endif

// Using 8-bit key/child/parent ptrs for within each small_page BTree.
// SMALL PAGE: 4KB, Size of array space: 128bytes. Total #small pages : M/4KB, ~2^24 for 
// ONLY need 7bits to address offset within 
struct BTreeNode {
  unsigned char keys[BT_MAX_NODE]; // stores upto 4 8-bit keys : 4byt. Each small page only has 4KB/16 granules, i.e. 8-bit keys
  
  unsigned char tags[PER_NODE_TAGARR_NUM_BYTES]; // stores a 4/8bit tag per key : 2/4byt i.e. 0-15 OR 0-255
  
  char count; // 8bits: bits[3:0]: #keys : 1byt
  unsigned char children[BT_MAX_CHILD]; // stores upto 5 8-bit offsets. : 5byt
  unsigned char parent; // stores 32-bit parent ptr offset. : 1byt // parent == node_offset means node is root.
  // bool is_leaf;
};

#define REUSING_FREED_NODE 1
#define ALLOC_FREED_ARR_SZ 5
#define PER_PAGE_MAX_BTREE_NODES (int)PER_PAGE_BTREE_SZ/sizeof(struct BTreeNode)

char* global_btree_buffer; // 64-bit METADATA

// PER PAGE BUFFER:
// For Physical Page i, it should be global_buffer + i*per_page_buffer_sz

// PER PAGE ROOT_OFFSET : 8bit for each page
unsigned char per_page_root_offset[MAX_NUMBER_OF_SMALL_PAGES];

// PER PAGE BUFFER_FIRST_AVAIL : 8bit for each page: 0-128, 7bit!
unsigned char per_page_buffer_first_avail[MAX_NUMBER_OF_SMALL_PAGES];

#ifndef FREED_NODES_BITARR
// PER PAGE freed_nodes ct, freed_nodes_arr (char [])
char per_page_alloc_freed_nodes_arr[MAX_NUMBER_OF_SMALL_PAGES][ALLOC_FREED_ARR_SZ];
#else
bool per_page_alloc_freed_nodes_bitarr[MAX_NUMBER_OF_SMALL_PAGES][16]; // 2bytes cuz upto 9nodes per page
#endif

// PER page current #freed nodes:
char per_page_alloc_freed_nodes[MAX_NUMBER_OF_SMALL_PAGES];

// PER PAGE total_alloc_freed_nodes: Just for accounting, not metadata
int per_page_total_alloc_freed_nodes[MAX_NUMBER_OF_SMALL_PAGES];

// Just for printing / book-keeping: [Not metadata]
long long int global_stg_call_count;
bool btree_verify_failed = false;

// PER PAGE last_printed_page_btree_buf_first_avail
char per_page_last_printed_btree_buf_first_avail[MAX_NUMBER_OF_SMALL_PAGES];

template <class myType>
myType min(myType a, myType b)
{
  return (a>b) ? b : a;
}

inline int getPageNumber(long long int addr)
{
  return (addr/(1024*SMALL_PAGE_SIZE));
}

int getSelfOffset(struct BTreeNode* node, int page_id)
{
  return (char*)node - global_btree_buffer - page_id*PER_PAGE_BTREE_SZ;
}

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

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


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

void printBoolArr(bool* arr, int len)
{
  for (int x = 0; x < len; x++)
    printf("%i, ", arr[x]);
}

void printBTreeNode(struct BTreeNode* node, int page_id)
{
  printf("[pg: %i] N off: %i , p_off: %i , ct: %i | K: ", page_id, getSelfOffset(node, page_id), node->parent, node->count);
  printUCharArr(node->keys, BT_MAX_NODE);
  printf(" | T: ");
  printUCharArr(node->tags, PER_NODE_TAGARR_NUM_BYTES);
  printf(" | Ch: ");
  printUCharArr(node->children, BT_MAX_CHILD);
}

void printBTree(struct BTreeNode* rnode, int level, int page_id)
{
  printf("\n LEVEL %i : ", level);
  if (level < 7)
  {
    printBTreeNode(rnode, page_id);
    for (int i = 0; i <= rnode->count; i++)
    // ASSUMPTION: if child ptr = rnode, invalid ptr.
      if (rnode->children[i] != getSelfOffset(rnode, page_id))
        printBTree((struct BTreeNode*)(global_btree_buffer + page_id*PER_PAGE_BTREE_SZ + rnode->children[i]), level+1, page_id);
  }
  else
    printf("ERRORRRRR!!!! TREE DEPTH MORE THAN 6!!!! [page: %i, first_avail: %i, freed_nodes: %i] \n", page_id, per_page_buffer_first_avail[page_id], per_page_alloc_freed_nodes[page_id]);
}

static struct BTreeNode* getPageRootPtr(int page_id)
{
  // global_btree_buffer + page_id*PER_PAGE_BTREE_SZ : buffer_start point for page_id page
  // then, add root offset.
  return (struct BTreeNode*) (global_btree_buffer + page_id*PER_PAGE_BTREE_SZ + per_page_root_offset[page_id]);
}

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

void initBTree(char* page_btree_buffer, int page_id)
{
  // make a new BTreeNode, with key=0,tag=0. []
  struct BTreeNode* root = (struct BTreeNode*) page_btree_buffer;
  initBTreeNode(root, 0, 0); // parent = null ptr, equal to root's offset.
  root->count = 1;
  root->keys[0] = 0;

  // UPDATE per-page metadata:
  per_page_buffer_first_avail[page_id] += sizeof(struct BTreeNode);
  per_page_root_offset[page_id] = 0;

  #ifndef FREED_NODES_BITARR
  for (int i = 0; i < ALLOC_FREED_ARR_SZ; i++)
    per_page_alloc_freed_nodes_arr[page_id][i] = -1; // initialize freed addresses with -1.
  #else
  for (int i = 0; i < 16; i++)
    per_page_alloc_freed_nodes_bitarr[page_id][i] = false; // initialize: no addr is freed (first avail will denote all addresses are available)
  #endif

  per_page_alloc_freed_nodes[page_id] = 0; // tracks fragmentation.
  per_page_total_alloc_freed_nodes[page_id] = 0;
  if (page_id % (16*1024) == 1)
    printf("##### FINISHED initBTree: root ptr: %p, new first_avail: %i, page_btree_root_offset: %i, alloc_freed_nodes: %i, total_alloc_freed_nodes: %i, PER_PAGE_MAX_BTREE_NODES: %li, BTreeNode sz: %li [FOR PAGE %i] \n", root, per_page_buffer_first_avail[page_id], per_page_root_offset[page_id], per_page_alloc_freed_nodes[page_id], per_page_total_alloc_freed_nodes[page_id], PER_PAGE_MAX_BTREE_NODES, sizeof(struct BTreeNode), page_id);
}

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

void setArrIthTag(unsigned char* tag_arr, int i, unsigned char tag)
{
  if (tag > MAX_TAG_VALUE)
  {
    printf("ERRORRRRR! setArrIthTag called with invalid tag value!!! %i (more than max possible: %i) \n", tag, MAX_TAG_VALUE);
    // throw;
  }

  #ifndef BIGTAG
  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]);
  #else
  tag_arr[i] = tag;
  #endif
}

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

bool isValidChild(struct BTreeNode* root, int i, int page_id)
{
  // return (!root->is_leaf) && (i <= root->count);
  return (i <= root->count) && (root->children[i] != getSelfOffset(root, page_id));
}

void freeNodeOffset(int offset, int page_id)
{
  per_page_total_alloc_freed_nodes[page_id] += 1;
  
  #ifndef FREED_NODES_BITARR
  per_page_alloc_freed_nodes_arr[page_id][per_page_alloc_freed_nodes[page_id]%ALLOC_FREED_ARR_SZ] = offset;
  per_page_alloc_freed_nodes[page_id] = min(per_page_alloc_freed_nodes[page_id]+1, ALLOC_FREED_ARR_SZ);
  #else
  per_page_alloc_freed_nodes_bitarr[page_id][offset/sizeof(struct BTreeNode)] = true; // offset can be b/w 0 - [128/sizeof(BTreeNode)]
  per_page_alloc_freed_nodes[page_id] = min( per_page_alloc_freed_nodes[page_id]+1, (int)(PER_PAGE_MAX_BTREE_NODES) );
  // if (page_id == 1)
  //   printf("Pg %i, Just freed offset %i (id = %li), per_page_alloc_freed_nodes: %i \n", page_id, offset, offset/sizeof(struct BTreeNode), per_page_alloc_freed_nodes[page_id] );
  #endif

  // printf("FREE-ed addr %i, alloc_freed_nodes: %i, total_alloc_freed_nodes: %i ", offset, alloc_freed_nodes, total_alloc_freed_nodes);
  // printIntArr(alloc_freed_nodes_arr, ALLOC_FREED_ARR_SZ);
}

// Use this func to get offset for assigning new node:
// Manages free-d nodes' space. [if REUSING_FREED_NODE == 1, it tries to re-use freed node space]
char getNewNodeOffset(int page_id)
{
  long long int ans = 0;
  if ((per_page_alloc_freed_nodes[page_id] == 0) || (REUSING_FREED_NODE == 0))
  {
    // Use fresh unused space, increment buffer_first_avail:
    ans = per_page_buffer_first_avail[page_id];
    per_page_buffer_first_avail[page_id] += sizeof(struct BTreeNode);
  
    #ifdef DEBUG
    if (page_id == 1)
    {
      printf("IN getNewNodeOffset for page %i : Assigning new first-avail: ans: %lli, first_avail: %i \n", page_id, ans, per_page_buffer_first_avail[page_id]);
      // printBTree( getPageRootPtr(page_id), 0, page_id );
    }
    #endif
  }
  else
  {
    // use a free-d addr, update free-d count:
    // printf("IN getNewNodeOffset: RE-using a free-d space: alloc_freed_nodes: %i, total_alloc_freed_nodes: %i", alloc_freed_nodes, total_alloc_freed_nodes);
    // printIntArr(alloc_freed_nodes_arr, ALLOC_FREED_ARR_SZ);

    per_page_alloc_freed_nodes[page_id] -= 1;
    per_page_total_alloc_freed_nodes[page_id] -= 1;

    #ifndef FREED_NODES_BITARR
    ans = per_page_alloc_freed_nodes_arr[page_id][ (per_page_alloc_freed_nodes[page_id]) % ALLOC_FREED_ARR_SZ];
    per_page_alloc_freed_nodes_arr[page_id][ (per_page_alloc_freed_nodes[page_id]) % ALLOC_FREED_ARR_SZ] = -1;
    #else
    ans = -1;
    for (int i = 0; i < PER_PAGE_MAX_BTREE_NODES; i++)
      if (per_page_alloc_freed_nodes_bitarr[page_id][i])
      {
        ans = sizeof(struct BTreeNode) * i;
        per_page_alloc_freed_nodes_bitarr[page_id][i] = false;
        // if (page_id == 1)
        //   printf("IN PAGE (%i) BITARR: Found %i offset FREE!! per_page_alloc_freed_nodes: %i \n", page_id, i, per_page_alloc_freed_nodes[page_id]);
        break;
      }
    #endif
    
    if (ans == -1)
      printf("IN getNewNodeOffset: ERRORRRR!!!! freed_addr was -1!!! page_alloc_freed_nodes: %i, page_total_alloc_freed_nodes: %i, addr: %lli", per_page_alloc_freed_nodes[page_id], per_page_total_alloc_freed_nodes[page_id], ans);
  }

  if ((per_page_buffer_first_avail[page_id] > (PER_PAGE_MAX_BTREE_NODES*sizeof(struct BTreeNode))) && (per_page_alloc_freed_nodes[page_id] == 0))
  {
    printf("WARNINGGGGGG!!!!! BTREE FOR PAGE %i IS TOO BIGG!!!! first_avail: %i, freed_nodes: %i, total_freed_nodes: %i \n", page_id, per_page_buffer_first_avail[page_id], per_page_alloc_freed_nodes[page_id], per_page_total_alloc_freed_nodes[page_id]);
    printBTree(getPageRootPtr(page_id), 0, page_id);

    #ifndef FREED_NODES_BITARR
    printCharArr(per_page_alloc_freed_nodes_arr[page_id], (int)ALLOC_FREED_ARR_SZ);
    #else
    printBoolArr(per_page_alloc_freed_nodes_bitarr[page_id], 16);
    #endif

    ans = 0; // DONT WANT THIS BTREE TO OVERFLOW TO ANOTHER BTree. SHOULD COPY TAGS TO ARRAY AT THIS POINT.
  }
  return ans;
}

// 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.
// this addr is the granule# in page pageID, and returns char since nodes within the small_page BTree have 8-bit addr.
int getLargestNodeLessThan(struct BTreeNode* root, unsigned char addr, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;
  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) && (isValidChild(root, i, page_id)) ) // root->children[i] != -1
    {
      int ans_in_right_child = getLargestNodeLessThan( (struct BTreeNode*)(page_btree_buffer + root->children[i]), addr, page_id );
      return (ans_in_right_child == -1) ? ((char*)root - page_btree_buffer) : ans_in_right_child;
    }
    else
      return ((char*)root - page_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 - page_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) && (isValidChild(root, i, page_id) ) ) // root->children[i] != -1
      ans_in_left_child = getLargestNodeLessThan( (struct BTreeNode*)(page_btree_buffer + root->children[i]), addr, page_id );

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

// 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, unsigned char addr, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;
  if (!root)
    return -1;

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

  // printf("IN getSmallestNodeMoreThan: addr: %i, i: %i, root->count: %i \n", addr, i, root->count);

  // 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 (isValidChild(root, 0, page_id) ) // root->children[0] != -1
    {
      int ans_in_left_child = getSmallestNodeMoreThan( (struct BTreeNode*)(page_btree_buffer+root->children[0]) , addr, page_id);
      return (ans_in_left_child == -1) ? ((char*) root - page_btree_buffer) : ans_in_left_child;
    }
    else
      return (char)((char*)root - page_btree_buffer); // the current root node has the smallest key>=addr.
  }
  // case2:
  if (root->keys[i] == addr)
    return ((char*)root - page_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 (isValidChild(root, i+1, page_id)) //  root->children[i+1] != -1
      ans_in_right_child = getSmallestNodeMoreThan((struct BTreeNode*)(page_btree_buffer+root->children[i+1]) , addr, page_id);

    // printf("IN getSmallestNodeMoreThan: addr: %i, i: %i, root->keys[i]: %i, ans_in_right_child: %i, root->children[i+1]: %i \n", addr, i, root->keys[i], ans_in_right_child, root->children[i+1]);
    return (ans_in_right_child == -1) ? ((i == (root->count-1)) ? -1 : ((char*) root - page_btree_buffer) ) : ans_in_right_child;
  }
  return -1;
}

void getLargestKeyTagLessThan(struct BTreeNode* root, unsigned char 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, unsigned char 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, unsigned char key, int tag, bool right_child, int child_offset, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;
  int rnode_offset = getSelfOffset(rnode, page_id);
  // find where to insert
  int i = 0;
  while ((i < rnode->count) && (rnode->keys[i] < key) )
    i++;

  #ifdef DEBUG
  if ((page_id == 3299) )
    printf("INSERTING key %i into node %i at i=%i , with tag %i, right_child: %i, child_offset: %i \n", key, rnode_offset, i, tag, right_child, child_offset);
  #endif

  // insert key at rnode->keys[i]
  // shift tags,keys,children
  int curr = key;
  int curr_tag = tag;
  int curr_child = (child_offset == -1) ? rnode_offset : 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) // child_offset != -1
  {
    struct BTreeNode* child_ptr = (struct BTreeNode*) (page_btree_buffer + child_offset);
    child_ptr->parent = (char*)rnode - page_btree_buffer;
  }

  rnode->count += 1;
}

// deletes key&tag from rnode - i.e. updates keys, count, children.
// equivalent to removeVal func in programiz code.
// rebalanceBTree can call 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)
{
  // printf("in deleteBTreeKeyFromNode: FOR KEY %i, del_child: %i, ", key, 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) // deleting left child
      rnode->children[i] = rnode->children[i+1];
    else // deleting right child
      rnode->children[i+1] = rnode->children[i+2];
    i++;
  }
  rnode->keys[rnode->count - 1] = 0; // 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;
}

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

  int node_with_largest_less_than_off = getLargestNodeLessThan(getPageRootPtr(page_id), addr, page_id);
  struct BTreeNode* node_with_largest_less_than = (struct BTreeNode*) (page_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;
  }

  // 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!!! [for getBTreeTag for addr %i in page: %i] node_with_largest_less_than_off: %i, 0th key: %i", addr, page_id, node_with_largest_less_than_off, node_with_largest_less_than->keys[i]);
      printBTree(getPageRootPtr(page_id), 0, page_id);
      // 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;
  }

  return -1;
}

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

    if (rleaf->parent != rleaf_offset ) // non null parent ~ parent=self_offset // rleaf->parent != -1
    {
      struct BTreeNode* rleaf_parent = (struct BTreeNode*) (page_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) && (isValidChild(rleaf_parent, i+1, page_id))) // rleaf_parent->children[i+1] != -1
      {
        // rleaf_right_bro_offset = rleaf_parent->children[i+1];
        rleaf_right_bro = (struct BTreeNode*) (page_btree_buffer + rleaf_parent->children[i+1]);
        if (rleaf_right_bro->count > BT_MIN_NODE)
        {
          // separator key moves to rleaf
          rleaf->keys[(int)(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[(int)(rleaf->count)] = (!isValidChild(rleaf_right_bro, 0, page_id)) ? rleaf_offset : rleaf_right_bro->children[0];
          if (isValidChild(rleaf_right_bro, 0, page_id) ) // rleaf_right_bro->children[0] != -1
          {
            struct BTreeNode* rl_right_bro_c0 = (struct BTreeNode*) (page_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 (offset: %i) \n", rleaf_right_bro, rleaf_right_bro_offset);
          // printBTreeNode(rleaf);
          // printBTreeNode(rleaf_right_bro);
          // printBTreeNode(rleaf_parent);

          return;
        }
      }
      // check if can rotate with left sibling:
      if ((i > 0) && (isValidChild(rleaf_parent, i-1, page_id) )) // rleaf_parent->children[i-1] != -1
      {
        rleaf_left_bro_offset = rleaf_parent->children[i-1];
        rleaf_left_bro = (struct BTreeNode*) (page_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:
          int insert_child_in_node = (rleaf_left_bro->children[(int)(rleaf_left_bro->count)] == rleaf_left_bro_offset) ? -1 : rleaf_left_bro->children[(int)(rleaf_left_bro->count)];
          insertBTreeKeyInNode(rleaf, rleaf_parent->keys[i-1], getArrIthTag(rleaf_parent->tags,i-1), 0, insert_child_in_node, page_id);

          // make rleaf_left_bro's last child, the first child of rleaf: [Doing this as part of insertBTreeKeyInNode]

          // 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[(int)(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[(int)(rleaf_left_bro->count)] = rleaf->keys[rx];
          setArrIthTag(rleaf_left_bro->tags, rleaf_left_bro->count, getArrIthTag(rleaf->tags,rx));
          rleaf_left_bro->children[(int)(rleaf_left_bro->count)] = (rleaf->children[rx] == rleaf_offset) ? rleaf_left_bro_offset : rleaf->children[rx];
          if (isValidChild(rleaf, rx, page_id) ) // rleaf->children[rx] != -1
          {
            struct BTreeNode* rleaf_child_rx = (struct BTreeNode*) (page_btree_buffer + rleaf->children[rx]);
            rleaf_child_rx->parent = rleaf_left_bro_offset;
          }
          rleaf_left_bro->count += 1;
        }
        rleaf_left_bro->children[(int)(rleaf_left_bro->count)] = (rleaf->children[(int)(rleaf->count)] == rleaf_offset) ? rleaf_left_bro_offset : rleaf->children[(int)(rleaf->count)];
        if (isValidChild(rleaf, (int)(rleaf->count), page_id) ) // rleaf->children[] != -1
        {
          struct BTreeNode* rleaf_child_last = (struct BTreeNode*) (page_btree_buffer + rleaf->children[(int)(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!!!

        #ifdef DEBUG
        if (page_id == 3299)
        {
          printf("IN rebalanceBTree: Merged with rleaf_left_bro: %p \n", rleaf_left_bro);
          printBTreeNode(rleaf_left_bro, page_id);
          printBTreeNode(rleaf_parent, page_id);          
        }
        #endif

      }
      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!

        // NOTE: a child ptr will point to itself if its invalid. So, invalid child ptr value is different for different nodes!
        // We pass -1 as the child offset if its an invalid ptr. The insertBTreeKeyInNode function takes care of this internally.
        // 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] == rleaf_offset) ? -1 : rleaf->children[lx]), page_id);
      
        // if (page_id == 62)
        //   printBTreeNode(rleaf_right_bro, page_id);

        // put separator in rleaf_right_bro
        insertBTreeKeyInNode(rleaf_right_bro, rleaf_parent->keys[i], getArrIthTag(rleaf_parent->tags, i), 0, ((rleaf->children[(int)(rleaf->count)] == rleaf_offset) ? -1 : rleaf->children[(int)(rleaf->count)]), page_id);

        // if (page_id == 62)
        //   printBTreeNode(rleaf_right_bro, page_id);

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

        #ifdef DEBUG
        if (page_id == 3299)
        {
          printf("IN rebalanceBTree: Merged with rleaf_right_bro: %p \n", rleaf_right_bro);
          printBTreeNode(rleaf_right_bro, page_id);
        }
        #endif
        // printBTreeNode(rleaf_parent);

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

      // Call re-balance on rleaf_parent, if needed
      if (rleaf_parent->count == 0)
      {
        if (rleaf_parent->parent != rleaf->parent) // rleaf_parent->parent != -1, rleaf_parent->parent is invalid if its equal to rleaf_parent offset, which is rleaf->parent.
        {
          printf("ERRORRR: SOMEHOW NON-ROOT node is EMPTY!!!! page_id: %i, rleaf_offset: %i, rleaf_parent: %i, rleaf_parent->parent: %i \n ", page_id, rleaf_offset, rleaf->parent, rleaf_parent->parent);
          // throw;
        }
        else
        {
          // free current root:
          freeNodeOffset(per_page_root_offset[page_id], page_id);
          // alloc_freed_nodes_arr[total_alloc_freed_nodes%ALLOC_FREED_ARR_SZ] = global_btree_root_offset;
          // total_alloc_freed_nodes += 1;
          // printIntArr(alloc_freed_nodes_arr, ALLOC_FREED_ARR_SZ);

          // 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 = ((char*) new_root - page_btree_buffer);
          per_page_root_offset[page_id] = (char*) new_root - page_btree_buffer;

          // 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]
    }
    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!! pg: %i (rleaf_offset: %i, rleaf->count: %i, rlea->parent: %i) \n", page_id, rleaf_offset, rleaf->count, rleaf->parent);
        // throw; // this should never happen!
      }
      return; // WE'RE DONE!!!
    }
    iter_ct++;
  }
  printf("ERRORRRRRR!!!!!! RECURSION IN deleteBTreeKey MORE THAN 20 TIMES!!!!");
}

// TODO: FIX CHILD PTR INVALID ~~ POINT TO ITSELF.

// deletes key from rnode, and tries to balance the BTree
bool deleteBTreeKey(struct BTreeNode* rnode, int key, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;  
  #ifdef DEBUG
  if (page_id == 3299)
    printf("IN deleteBTreeKey!!! for key %i, on page %i, ", key, page_id);
  #endif

  if (isBTreeNodeLeaf(rnode, page_id))
  {
    deleteBTreeKeyFromNode(rnode, key, 1);
    if (rnode->count < BT_MIN_NODE)
    {
      // re-balance
      rebalanceBTree(rnode, page_id);
    }
  }
  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*)(page_btree_buffer + rnode->children[i+1]), key, page_id );
    struct BTreeNode* smallest_node_more_key = (struct BTreeNode*) (page_btree_buffer + smallest_node_more_key_off);
    // replacement should be in a leaf.
    if (!isBTreeNodeLeaf(smallest_node_more_key, page_id))
    {
      printf("IN deleteBTreeKey: ERRORRRR!!!! smallestNodeMoreThan key %i is NOT a leaf!!! \n", key);
      return false;
    }
    // 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, page_id);
    }
  }
  return true;
}

int findLeafNodeToInsertAddr(struct BTreeNode* rnode, int addr, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;  
  if (isBTreeNodeLeaf(rnode, page_id))
    return (char*)rnode - page_btree_buffer;

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

  if ( !isValidChild(rnode, i, page_id) ) // 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]);
    return -1;
    // throw;
  }
  else
    return findLeafNodeToInsertAddr( (struct BTreeNode*)(page_btree_buffer + rnode->children[i]), addr, page_id );
  // 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);
}

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

// 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, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;
  int rnode_offset = (char*)rnode - page_btree_buffer;
  if (rnode->count < BT_MAX_NODE)
  {
    printf("ERROR: 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] == rnode_offset) ? -1 : rnode->children[j];
    }
    full_arr[i] = insert_addr;
    setArrIthTag(full_tag_arr, i, insert_tag);
    full_children_arr[i] = (rnode->children[i] == rnode_offset) ? -1 : 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] == rnode_offset) ? -1 : 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] == -1) ? rnode_offset : full_children_arr[j];
      }
      else if (j == median_id)
        rnode->children[j] = (full_children_arr[j] == -1) ? rnode_offset : full_children_arr[j];
      else
        rnode->children[j] = rnode_offset; // null ptrs : point to itself.

      // 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*) (page_btree_buffer + full_children_arr[j]);
        full_child_j->parent = rnode_offset; // (char*)rnode - page_btree_buffer;
      }
    }
    rnode->count = median_id;

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

    if (median_key != full_arr[median_id])
        printf("SPLITNODE: ERRORRR!!! median key %i doens't match full_arr median %i !! \n", median_key, full_arr[median_id]);

    // Split rnode: elems>median_key in new node.
    int new_node_create_offset = getNewNodeOffset(page_id);
    if (new_node_create_offset == -1)
          return -1; // BTree Overflow
    struct BTreeNode* new_node_right = (struct BTreeNode*) (page_btree_buffer + new_node_create_offset);
    initBTreeNode(new_node_right, new_node_create_offset, new_node_create_offset);
    int new_node_right_offset = new_node_create_offset;
    // NOTE: we now do this in getNewNodeOffset func: 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*) (page_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] == -1) ? new_node_right_offset : 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] == -1) ? new_node_right_offset : 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] = new_node_right_offset; // NULL ptr
    }

    // update new_node_right's parent ptr:
    // check if rnode's parent is invalid, i.e. if rnode->parent == rnode_offset!
    new_node_right->parent = (rnode->parent == rnode_offset) ? new_node_right_offset : rnode->parent;
    // new_node_right->is_leaf = rnode->is_leaf;

    // 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 - page_btree_buffer);
}

// TODO:

bool insertBTreeKey(int addr, unsigned char tag, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;

  // find the leaf where we'll insert addr:
  int leaf_to_insert_offset = findLeafNodeToInsertAddr(getPageRootPtr(page_id), addr, page_id);
  struct BTreeNode* leaf_to_insert = (struct BTreeNode*) (page_btree_buffer + leaf_to_insert_offset);

  #ifdef DEBUG
  if ( ((addr < 10) || (addr > 250)) && (page_id == 3299))
    printf("IN insertBTreeKey: addr: %i, tag: %i, leaf_to_insert_offset: %i \n", addr, tag, leaf_to_insert_offset);
  #endif

  // 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;
  struct BTreeNode* node_to_insert = leaf_to_insert;
  int node_to_insert_offset = (char*) node_to_insert - page_btree_buffer;
  int insert_child_right_offs = -1;
  while (true)
  {
    if (node_to_insert->count < BT_MAX_NODE)
    {
      // printf("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 == -1) ? node_to_insert_offset : 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]; // since all children values are valid, this will never be -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 == -1) ? node_to_insert_offset : 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*) (page_btree_buffer + insert_child_right_offs);
        insert_child_right->parent = (char*)(node_to_insert) - page_btree_buffer;
      }

      node_to_insert->count += 1;
      return true;
    }
    else
    {
      // get median key (after splitting into 2 nodes), 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, page_id);
      if (new_node_right_offset == -1)
      {
        printf("WARNINGGGGGG : IN insertBTreeKey: new_node_right_offset: %i, node_to_insert_offset: %i, node_to_insert->parent: %i \n", new_node_right_offset, node_to_insert_offset, node_to_insert->parent);
        return false;
      }

      // recurse to parent:
      if (node_to_insert->parent == node_to_insert_offset) // node_to_insert was root, so we make a new root:
      {
        // Construct new root!
        int new_node_create_offset = getNewNodeOffset(page_id);
        if (new_node_create_offset == -1)
          return false; // BTree Overflow
        struct BTreeNode* new_root = (struct BTreeNode*)(page_btree_buffer + new_node_create_offset);
        initBTreeNode(new_root, new_node_create_offset, new_node_create_offset); // parent = itself, children = itself.
        new_root->keys[0] = median_key;
        setArrIthTag(new_root->tags, 0, median_tag);
        new_root->children[0] = (char*)node_to_insert - page_btree_buffer;
        new_root->children[1] = new_node_right_offset;
        new_root->count = 1;
        // new_root->is_leaf = false;

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

        // update global_btree_root_offset, first_avail
        per_page_root_offset[page_id] = new_node_create_offset;
        // global_btree_buffer_first_avail += sizeof(struct BTreeNode); // NO need to do this cuz we do this in getNewNodeOffset().
        // printf("IN insertBTreeKey: JUST MODIFIED the per_page_root_offset[%i] to %i !!!! \n", page_id, new_node_create_offset);

        return true;
      }
      else
      {
        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*) (page_btree_buffer + node_to_insert_offset);

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

void setBTreeTag(struct BTreeNode* root, unsigned char addr, unsigned char tag, int page_id)
{
  char* page_btree_buffer = global_btree_buffer + page_id*PER_PAGE_BTREE_SZ;
  // 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(getPageRootPtr(page_id), addr, page_id);
  int tag_x = -1, x = -1, x_ind = -1;
  struct BTreeNode* largest_node_less = NULL;

  // printf("IN setBTreeTag (tag: %i): page_id %i, largest_node_less_offset: %i \n", tag, page_id, largest_node_less_offset);

  if (largest_node_less_offset != -1)
  {
    // get tag_x, x from largest_node_less_offset:
    largest_node_less = (struct BTreeNode*) (page_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) ERRORR !!! \n", addr);
    printBTree(root, 0, page_id);
    // throw;
  }

  // printf("IN largest_node_less: tag_x: %i, x: %i, x_ind: %i \n", tag_x, x, x_ind);

  // 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(getPageRootPtr(page_id), x+1, page_id); // (x==255) ? -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*) (page_btree_buffer + smallest_node_more_x_offset);
    getSmallestKeyTagMoreThan(smallest_node_more_x, x+1, &xnext, &tag_xnext);    
  }

  #ifdef DEBUG
  // if (((addr < 10) || (addr > 250)) && (page_id == 3299))
  //   printf("Midway thru setTag (page: %i): addr: %i, x: %i, tag_x: %i, xnext: %i, tag_xnext: %i, smallest_node_more_x_offset: %i \n", page_id, addr, x, tag_x, xnext, tag_xnext, smallest_node_more_x_offset);
  #endif

  // 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 = (x==0) ? -1 : getLargestNodeLessThan( getPageRootPtr(page_id), x-1, page_id);

    // printf("IN setTag: largest_node_less_offset (<= x-1): %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*) (page_btree_buffer + largest_node_less_x_offset);
      getLargestKeyTagLessThan(largest_node_less_x, x-1, &xprev, &tag_xprev);

      #ifdef DEBUG
      // if (((addr < 10) || (addr > 250)) && (page_id == 3299))
      //   printf("IN setTag [pg: %i]: addr: %i, tag: %i, x: %i, xprev: %i , tag_xprev: %i \n", page_id, addr, tag, x, xprev, tag_xprev);
      #endif

      // 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, page_id);

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

          // printf("IN setTag [JUST deleted key x!!] : 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, page_id);

      // printf("IN setTag [JUST deleted key xnext]: 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, page_id);      
    }
    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, page_id);
  
    // printBTreeNode(largest_node_less);
    // printBTreeNode(getGlobalRootPtr());
  }

}


////////////////////////////////////// MAIN code BEGINS:
#define GRANULE_SZ 16
#define MALLOC_ARR_LEN 90000 // this has to be atleast the #rows in the workload file!

#define insert_random_tag() (rand()%(MAX_TAG_VALUE) + 1)

// convert addr to granule # relative to Page start [0,4KB/32] : 8bit.
void set_tag(long long int addr, unsigned char tag)
{
  int page_id = getPageNumber(addr); // addr/(SMALL_PAGE_SIZE*1024);
  int page_relative_addr = addr%(SMALL_PAGE_SIZE*1024);

  // CHECKING IF BTree is about to overflow the space reserved for an array.
  if ((per_page_buffer_first_avail[page_id] > (PER_PAGE_MAX_BTREE_NODES-1)*sizeof(struct BTreeNode)) && (per_page_alloc_freed_nodes[page_id] == 0))
  {
    #ifdef DEBUG
    if (page_id == 1)
      printf("Pg: %i : TRIED setting tag for addr %lli (relative: %i) to %i, BUT OVERflow! [first_avail: %i] \n", page_id, addr, page_relative_addr, tag, per_page_buffer_first_avail[page_id]);
    #endif

    return;
  }

  // printf("\n ///// CALLING setBTreeTag FOR addr %lli, with tag %i, page_id: %i [current root: %i], page_relative_addr: %i \n", addr, tag, page_id, per_page_root_offset[page_id], page_relative_addr);
  setBTreeTag(getPageRootPtr(page_id), page_relative_addr/GRANULE_SZ, tag, page_id);
}


int get_tag(long long int addr)
{
  int page_id = getPageNumber(addr); // addr/(SMALL_PAGE_SIZE*1024);
  int page_relative_addr = addr%(SMALL_PAGE_SIZE*1024);

  // CHECKING IF BTree is about to overflow the space reserved for an array.
  if ((per_page_buffer_first_avail[page_id] > (PER_PAGE_MAX_BTREE_NODES-1)*sizeof(struct BTreeNode)) && (per_page_alloc_freed_nodes[page_id] == 0))
    return INVALID_TAG_VALUE;

  return getBTreeTag(getPageRootPtr(page_id), page_relative_addr/GRANULE_SZ, page_id);
}


int main(int argc, char const *argv[])
{
  long int total_mallocs = 0;
  long long int total_mallocs_sz = 0;
  int malloc_sizes[MALLOC_ARR_LEN]; // +ve elems: new malloc, -ve elems: del (-1*elem)th malloc, i.e. tag=0
  int malloc_ids[MALLOC_ARR_LEN];
  long int malloc_orig_offsets[MALLOC_ARR_LEN];

  int useless_arr[1000];

  // TESTing:
  ///////// TESTcase STARTS
  // total_mallocs = 17;
  // malloc_sizes[0] = 4016; // page0
  // malloc_sizes[1] = 4016; // page0,1
  // malloc_sizes[2] = 5008; // page1,2,3
  // malloc_sizes[3] = 256; // page3
  // malloc_sizes[4] = 256; // page3
  // malloc_sizes[5] = 512; // page3
  // malloc_sizes[6] = 512; // page3

  // for (int i = 0; i < 10; i++)
  //   malloc_sizes[i+7] = 64 + (rand()%10)*16;

  // for (int i = 0; i < total_mallocs; i++)
  // {
  //   malloc_orig_offsets[i] = total_mallocs_sz;
  //   total_mallocs_sz += malloc_sizes[i];  
  //   malloc_ids[i] = i;
  // }
  ///////// TESTcase ENDS

  // READING file with workload:
  FILE *fp;
  fp = fopen(argv[1], "r");
  if (!fp)
  {
    printf("INVALID File name!!! %s", argv[1]);
    return -1;
  }
  char buf[256];
  while (true)
  {
    if ((fscanf(fp, "%s", buf) == EOF) ) //  || (total_mallocs == 100) ifdef DEBUG
      break;
    if (buf[0] == 'm')
    {
      long msz, moffset, mid;
      
      if ((fscanf(fp, "%li", &msz) == 0) || (fscanf(fp, "%li", &moffset) == 0) || (fscanf(fp, "%li", &mid) == 0))
        printf("Parse: ERRORRRRRR!!!! malloc: sz / offset / id unavailable!!! \n");
      
      malloc_sizes[total_mallocs] = msz;
      malloc_orig_offsets[total_mallocs] = moffset;
      malloc_ids[total_mallocs] = mid;

      total_mallocs += 1;
      total_mallocs_sz = (total_mallocs_sz > (moffset+msz)) ? (total_mallocs_sz) : (moffset+msz);

    }
    else if (buf[0] == 'f')
    {
      long foffset;
      int fid;

      if ( (fscanf(fp, "%li", &foffset) == 0) || (fscanf(fp, "%i", &fid) == 0) )
        printf("Parse: ERRORRRRRR!!!! free: offset / id unavailable!!!! \n");

      malloc_sizes[total_mallocs] = -1 * fid;
      total_mallocs += 1;

      if (malloc_orig_offsets[fid] != foffset)
              printf("Parse: ERRORRRR!!!! free command fid: %i, foffset: %li, malloc_orig_offsets[fid]: %li offset not matching!!! \n", fid, foffset, malloc_orig_offsets[fid]);
    }

    if (total_mallocs % 5000 == 7)
      printf("total_mallocs: %li , total_mallocs_sz: %lli, Last inserted data: size: %i, Id: %i, Orig_offset: %li \n", total_mallocs, total_mallocs_sz, malloc_sizes[total_mallocs-1], malloc_ids[total_mallocs-1], malloc_orig_offsets[total_mallocs-1]);
  }


  unsigned char malloc_tags[total_mallocs];
  bool invalid_tags[total_mallocs];
  
  unsigned char granule_tags[ getPageNumber(total_mallocs_sz)*256 + 256 ] = {0}; // this is the right way of checking correctness: track the tag of every granule in an array. 
  bool freed_and_realloc_tags[total_mallocs] = {false};

  // INitializing BTree DS:
  // 64MB for RAMSz = 64MB*32 = 2GB
  long long int ram_sz = 2*1024*1024; // #KBs
  global_btree_buffer = (char*) malloc((ram_sz / 32) * 1024);
  srand(time(NULL)); 
  for (int i = 0; i < (ram_sz/(SMALL_PAGE_SIZE)); i++)
  {
    per_page_buffer_first_avail[i] = 0;
    per_page_last_printed_btree_buf_first_avail[i] = 0;
    initBTree(global_btree_buffer + i*PER_PAGE_BTREE_SZ, i);

    global_stg_call_count = 0;
  }

  printf("ABOUT TO START PROCESSING MALLOCS!! total_mallocs: %li, total_mallocs_sz:%lli, len of granule_tags: %i \n", total_mallocs, total_mallocs_sz, getPageNumber(total_mallocs_sz)*256 + 256);

  // Exclude space comparison for pages that weren't touched:
  bool page_touched[getPageNumber(total_mallocs_sz) + 1] = {false};

  // Get per-page mem allocation stats:
  long long int per_page_num_allocs[getPageNumber(total_mallocs_sz) + 1] = {0}; // #allocations on page
  long long int per_page_sum_allocs[getPageNumber(total_mallocs_sz) + 1] = {0}; // #granules allocated.

  int byte_number_test[2] = {0,GRANULE_SZ-1};  

  for (int i = 0; i < total_mallocs; i++)
  {
    int m_index = i;
    invalid_tags[i] = false;
          
    if (malloc_sizes[i] > 0)
    {
      malloc_tags[i] = insert_random_tag();
      for (int gi = 0; gi < (malloc_sizes[i]/GRANULE_SZ); gi++)
      {
        set_tag(malloc_orig_offsets[i] + gi*GRANULE_SZ, malloc_tags[i]);
        granule_tags[(malloc_orig_offsets[i] + gi*GRANULE_SZ)/GRANULE_SZ] = malloc_tags[i];
        
        int page_id = getPageNumber(malloc_orig_offsets[i] + gi*GRANULE_SZ); // (malloc_orig_offsets[i] + gi*GRANULE_SZ)/(SMALL_PAGE_SIZE*1024);
        per_page_sum_allocs[page_id] += 1;
        page_touched[page_id] = true;

        // #ifdef DEBUG
        // if (gi == 0 || (gi > 125))        
        // printf("ROOT Ptr for addr %li : %i \n", malloc_orig_offsets[i] + gi*GRANULE_SZ, per_page_root_offset[page_id]);
        // printf("global_btree_buffer: %p, PageRootPtr: %p, PageId: %i \n", global_btree_buffer, getPageRootPtr(page_id), page_id );
        // if (gi % 10000 == 0)
        //   printBTree(getPageRootPtr(page_id), 0, page_id);
        // if (page_id == 668)
        // {
        //   printf("JUST Set tag for i=%i (offset= %i, gi = %i) to %i !!! tree: \n", i, malloc_orig_offsets[i], gi, malloc_tags[i]);
        //   printBTree(getPageRootPtr(668), 0, 668);
        // }
        // #endif
      }
      int first_page_id = getPageNumber(malloc_orig_offsets[i]); // (malloc_orig_offsets[i])/(SMALL_PAGE_SIZE*1024);
      int last_page_id = getPageNumber(malloc_orig_offsets[i] + malloc_sizes[i] - 1); // (malloc_orig_offsets[i] + malloc_sizes[i] - 1)/(SMALL_PAGE_SIZE*1024);

      for (int pid = first_page_id; pid <= last_page_id; pid++)
      {
        per_page_num_allocs[pid] += 1;
        if ((per_page_num_allocs[pid] > 100) && (per_page_num_allocs[pid] % 100 == 2))
          printf("WEIRD::::: page ID: %i, #Allocs TOO LARGE!!! %lli (i=%i) \n", pid, per_page_num_allocs[pid], i);

        #ifdef DEBUG
        if (pid == 0)
        {
          printf("JUST finished i=%i [tag=%i], tree for pg0: ", i, malloc_tags[i]);
          printBTree(getPageRootPtr(0), 0, 0);
          // printBoolArr(invalid_tags, 24);
        }
        #endif
      }

      if (i % 50 == 7)
      {
        printf("FINISHED i=%i (orig_offset: %li, sz: %i, first_page_id: %i, last_page_id: %i) \n", i, malloc_orig_offsets[i], malloc_sizes[i], first_page_id, last_page_id);
        #ifdef DEBUG
        printBTree(getPageRootPtr(last_page_id), 0, last_page_id );
        #endif
      }
      
      // #ifdef DEBUG
      //   // if (i == 265)
      //   //   printBTree(getPageRootPtr(3299), 0, 3299);
      // #endif
    }
    else
    {
      int free_index = -1*malloc_sizes[i];
      m_index = free_index;
      if (i % 2500 == 7) // 5000 for mysqld big workload.
        printf("FREE-ing i=%i index %i at offset: %li (tag: %u, sz: %i) \n !!!", i, free_index, malloc_orig_offsets[free_index], malloc_tags[free_index], malloc_sizes[free_index]);

      malloc_tags[free_index] = 0;

      for (int gi = 0; gi < (malloc_sizes[free_index])/GRANULE_SZ; gi++)
      {
        set_tag(malloc_orig_offsets[free_index] + gi*GRANULE_SZ, malloc_tags[free_index]);
        granule_tags[(malloc_orig_offsets[free_index] + gi*GRANULE_SZ)/GRANULE_SZ] = 0;
        #ifdef DEBUG
        // if ((i == 112) && (gi > 364) && (gi-364)%5 == 0)
        if (getPageNumber(malloc_orig_offsets[free_index] + gi*GRANULE_SZ) == 0)
        {
          printf("JUST freed granule: i %i, gi: %i, addr: %li \n", i, gi, malloc_orig_offsets[free_index] + gi*GRANULE_SZ);
          printBTree(getPageRootPtr(668), 0, 668);
        }
        #endif
      }

      if (i % 50 == 7)
      {
        printf("JUST FREE-d index %i, here's the tree for last granule of this \n", free_index);
        printBTree(getPageRootPtr(getPageNumber(malloc_orig_offsets[free_index]+malloc_sizes[free_index])) , 0, getPageNumber(malloc_orig_offsets[free_index]+malloc_sizes[free_index])); 
      }

      // Checking:
      // for (int bi = 0; bi < malloc_sizes[free_index]; bi++)
      //   if (get_tag(malloc_orig_offsets[free_index] + bi) != malloc_tags[free_index])
      //   {
      //     printf("ERRORRRRR!!!!!! FOR i=%i Tag of addr %li (%i) DOESNT match Assigned tag %li \n", i, malloc_orig_offsets[free_index]+bi, get_tag(malloc_orig_offsets[free_index] + bi), malloc_tags[free_index]);
      //     printBTree( getPageRootPtr( (malloc_orig_offsets[free_index] + bi)/(SMALL_PAGE_SIZE*1024) ), 0, (malloc_orig_offsets[free_index] + bi)/(SMALL_PAGE_SIZE*1024) );
      //     return -1;
      //   }
    }

    // Jul10: Moved to testing tags of only 2 bytes per granule, instead of testing every single byte in every allocation.
    for (int j = 0; j <= m_index; j++)
      if (!invalid_tags[j])
        for (int gj = 0; gj < malloc_sizes[j]/GRANULE_SZ; gj++)
          for (int bn = 0; bn < 2; bn++)
          {
            int bj = gj*GRANULE_SZ + byte_number_test[bn];
            int gtag = get_tag(malloc_orig_offsets[j] + bj);
            if (gtag == INVALID_TAG_VALUE)
            {
              printf("[Done i=%i] FOR j=%i, bj=%i (offset: %li): INVALID tag- BTREE OVERFLOW|||", i, j, bj, malloc_orig_offsets[j]);
              invalid_tags[j] = true;
              break;
            }
            else if (gtag != malloc_tags[j])
            {
              // this granule might've been re-allocated!
              if ( (gtag == granule_tags[(malloc_orig_offsets[j] + bj)/GRANULE_SZ]) && (malloc_tags[j] == 0) )
              {
                if (!freed_and_realloc_tags[j])
                {
                  printf("DONE i=%i, Mem RE-Alloc! j=%i, bj=%i, malloc_tag[j] = %i, granule_tag: %i, & get_Tag: %i \n", i, j, bj, malloc_tags[j], granule_tags[(malloc_orig_offsets[j] + bj)/GRANULE_SZ], gtag );
                  freed_and_realloc_tags[j] = true;
                }
              }
              else
              {
                printf("ERRORRRRR!!!!!! [DONE till i=%i] FOR j=%i Tag of addr %li (%i) DOESNT match Assigned tag %i [granule_tag: %i] \n", i, j, malloc_orig_offsets[j]+bj, gtag, malloc_tags[j], granule_tags[(malloc_orig_offsets[j] + bj)/GRANULE_SZ]);
                printUCharArr(malloc_tags, j+1);
                printBTree(getPageRootPtr( getPageNumber(malloc_orig_offsets[j] + bj) ), 0, getPageNumber(malloc_orig_offsets[j] + bj) );
                return -1;              
              }
            }

          }
  }

  // check if tag is invalid / freed and realloc-ed / or wrong.
  // Jul10: Testing only for the first,last byte in each granule instead of testing for all bytes.
  for (int i = 0; i < total_mallocs; i++)
    if ((malloc_sizes[i] > 0) && (!invalid_tags[i]))
      for (int gi = 0; gi < malloc_sizes[i]/GRANULE_SZ; gi++)
        for (int bn = 0; bn < 2; bn++)
        {
          int bi = gi*GRANULE_SZ + byte_number_test[bn];
          int gtag = get_tag(malloc_orig_offsets[i] + bi);
          if ( (gtag != malloc_tags[i]) )
          {
            if ( (gtag != granule_tags[(malloc_orig_offsets[i] + bi)/GRANULE_SZ]) || (malloc_tags[i] != 0) )
            {
              printf("ERRORRRRR!!!!!! FOR i=%i Tag of addr %li (%i) DOESNT match Assigned tag %i [granule tag: %i , freed_and_realloc_tags? %i ] \n", i, malloc_orig_offsets[i]+bi, gtag, malloc_tags[i], granule_tags[(malloc_orig_offsets[i] + bi)/GRANULE_SZ], freed_and_realloc_tags[i] );
              printBTree(getPageRootPtr( getPageNumber(malloc_orig_offsets[i] + bi) ), 0, getPageNumber(malloc_orig_offsets[i] + bi) );
              printUCharArr(malloc_tags, total_mallocs);
              return -1;            
            }
          }
        }

   // WRITE per page stats to file
  std::ofstream per_page_stats_log;
  per_page_stats_log.open(argv[2]);
  // each line has page_id, page_touched, buffer_first_avail, alloc_freed_nodes, total_alloc_Freed_nodes, space_usage_TagArr, space_usage_OurDS, \n
  per_page_stats_log << "PageID, PageTouched, NumAllocs, NumAllocatedGranules, PageBufferFirstAvail, PageAllocFreedNodes, PageTotalAllocFreedNodes, Page_TagArraySpaceUsage, Page_OurSpaceUsage, \n";

  long long int total_btrees_space = 0;
  long long int total_arr_space = 0;
  for (int pid = 0; pid <= (total_mallocs_sz/(SMALL_PAGE_SIZE*1024)); pid++)
  {
    per_page_stats_log << pid << ", " << page_touched[pid] << ", " << per_page_num_allocs[pid] << ", " << per_page_sum_allocs[pid] << ", " << (int)(per_page_buffer_first_avail[pid]) << ", " << (int)(per_page_alloc_freed_nodes[pid]) << ", " << per_page_total_alloc_freed_nodes[pid] << ", ";
    if (page_touched[pid])
    {
      if (per_page_buffer_first_avail[pid] > 78)
      {
        printf("~~~~~ PRINTING PAGE TREE FOR PageId: %i \n", pid);
        printBTree(getPageRootPtr(pid), 0, pid );     
      }

      // array: 128bytes per page
      total_arr_space += 128;
      per_page_stats_log << "128, ";

      // add array space if BTree had overflown:
      if ((per_page_buffer_first_avail[pid] > (PER_PAGE_MAX_BTREE_NODES-1)*sizeof(struct BTreeNode)) && (per_page_alloc_freed_nodes[pid] == 0))
      {
        total_btrees_space += 128;
        printf("FOR PAGE %i, first_avail: %i, freed_nodes: %i || ADDING array space!!!~~~", pid, per_page_buffer_first_avail[pid], per_page_alloc_freed_nodes[pid]);
        per_page_stats_log << "128, \n";
      }
      else
      {
        total_btrees_space += per_page_buffer_first_avail[pid];
        per_page_stats_log << (int)(per_page_buffer_first_avail[pid]) << ", \n";
        if (pid % 50 == 7)
          printf("ADDED BTree space: %i", per_page_buffer_first_avail[pid]);
      }

    }
    else
    {
      printf("PAGE %i UNTOUCHED!!!!", pid);
      per_page_stats_log << "0, 0, \n";
    }
  }
  per_page_stats_log.close();

  printUCharArr(malloc_tags, total_mallocs);

  // COUNTING TOTAL SPACE USAGE:
  printf("TOTAL MALLOCS' SIZE: %lli , TAG Array Space: %lli (bytes), BTree-Per-Page Space: %lli, Array space(touched pages only) %lli \n", total_mallocs_sz, total_mallocs_sz/32, total_btrees_space, total_arr_space);
  return 0;
}