btree.c

#include "btree.h"

typedef enum {left = -1,right = 1} position_t;

typedef struct {
  bt_node * node;
  unsigned int index;
}node_pos;

static void print_single_node(btree *btree, bt_node * node);
static bt_node * allocate_btree_node (unsigned int order);
static int free_btree_node (bt_node * node);

static node_pos get_btree_node(btree * btree,uint64_t key);

static int delete_key_from_node(btree * btree, node_pos * node_pos);
static bt_node * merge_nodes(btree * btree, bt_node * n1, bt_key_val kv ,bt_node * n2);
static void move_key(btree * btree, bt_node * node, unsigned int index, position_t pos);
static node_pos get_max_key_pos(btree * btree, bt_node * subtree);
static node_pos get_min_key_pos(btree * btree, bt_node * subtree);
static bt_node * merge_siblings(btree * btree, bt_node * parent,unsigned int index,
          position_t pos);
static void copy_key_val(btree * btree,bt_key_val *src, bt_key_val *dst);

/**
* Used to create a btree with just the root node
* @param order The order of the B-tree
* @return The an empty B-tree
*/
btree * btree_create(unsigned int order) {
  btree * btree;
  btree = mem_alloc(sizeof(*btree));
  btree->order = order;
  btree->root = allocate_btree_node(order);
  btree->root->leaf = True;
  btree->root->nr_active = 0;
  btree->root->next = NULL;
  btree->root->level = 0;
  return btree;
}

/**
*       Function used to allocate memory for the btree node
*       @param order Order of the B-Tree
* @param leaf boolean set true for a leaf node
*       @return The allocated B-tree node
*/
static bt_node * allocate_btree_node (unsigned int order) {
        bt_node * node;

        // Allocate memory for the node
        node = (bt_node *)mem_alloc(sizeof(bt_node));
       
        // Initialize the number of active nodes
        node->nr_active = 0;

        // Initialize the keys
        node->key_vals = (bt_key_val *)mem_alloc(2*order*sizeof(bt_key_val) - 1);
        
        // Initialize the child pointers
        node->children = (bt_node **)mem_alloc(2*order*sizeof(bt_node*));

  // Use to determine whether it is a leaf
  node->leaf = True;

  // Use to determine the level in the tree
  node->level = 0;

  //Initialize the linked list pointer to NULL
  node->next = NULL;

        return node;
}

/**
*       Function used to free the memory allocated to the b-tree 
*       @param node The node to be freed
*       @param order Order of the B-Tree
*       @return The allocated B-tree node
*/
static int free_btree_node (bt_node * node) {

        mem_free(node->children);
        mem_free(node->key_vals);
        mem_free(node);

        return 0;
}

/**
* Used to split the child node and adjust the parent so that
* it has two children
* @param parent Parent Node
* @param index Index of the child node
* @param child  Full child node
* 
*/
static void btree_split_child(btree * btree, bt_node * parent, 
        unsigned int index,
        bt_node * child) {
  int i = 0;  
  unsigned int order = btree->order;

  bt_node * new_child = allocate_btree_node(btree->order); 
  new_child->leaf = child->leaf;
  new_child->level = child->level;
  new_child->nr_active = btree->order - 1;

  // Copy the higher order keys to the new child  
  for(i=0;i<order - 1;i++) {
    new_child->key_vals[i] = child->key_vals[i + order];
    if(!child->leaf) {
      new_child->children[i] = 
        child->children[i + order];
    } 
  }
  
  // Copy the last child pointer
  if(!child->leaf) {
    new_child->children[i] = 
    child->children[i + order];
  }

  child->nr_active = order - 1;
  
  for(i = parent->nr_active + 1;i > index + 1;i--) {
    parent->children[i] = parent->children[i - 1];
  }
  parent->children[index + 1] = new_child;

  for(i = parent->nr_active;i > index;i--) {
    parent->key_vals[i] = parent->key_vals[i - 1];
  }

  parent->key_vals[index] = child->key_vals[order - 1]; 
  parent->nr_active++;
}

/**
* Used to insert a key in the non-full node
* @param btree The btree
* @param node The node to which the key will be added
* @param the key value pair
* @return void
*/

static void btree_insert_nonfull (btree * btree, bt_node * parent_node,
        bt_key_val  key_val) {
  
  uint64_t key = key_val.key;
  int i ;
  bt_node * child;  
  bt_node * node = parent_node;

insert: i = node->nr_active - 1;
  if(node->leaf) {
    while(i >= 0 && key < node->key_vals[i].key) {
      node->key_vals[i + 1] = node->key_vals[i];
      i--;
    }
    node->key_vals[i + 1] = key_val;
    node->nr_active++; 
  } else {
    while (i >= 0 && key < node->key_vals[i].key) {
      i--;
    }
    i++;
    child = node->children[i]; 
    
    if(child->nr_active == 2*btree->order - 1) {
      btree_split_child(btree,node,i,child);  
      if(key_val.key > 
        node->key_vals[i].key) {
        i++;  
      } 
    }
    node = node->children[i];
    goto insert;  
  } 
}


/**
*       Function used to insert node into a B-Tree
*       @param root Root of the B-Tree
*       @param node The node to be inserted
*       @param compare Function used to compare the two nodes of the tree
*       @return success or failure
*/
int btree_insert_key(btree * btree, bt_key_val  key_val) {
  bt_node * rnode;

  rnode = btree->root;
  if(rnode->nr_active == (2*btree->order - 1)) {
    bt_node * new_root;
    new_root = allocate_btree_node(btree->order);
    new_root->level = btree->root->level + 1;
    btree->root = new_root; 
    new_root->leaf = False;
    new_root->nr_active = 0;
    new_root->children[0]  = rnode;
    btree_split_child(btree,new_root,0,rnode);
    btree_insert_nonfull(btree,new_root,key_val); 
  } else
    btree_insert_nonfull(btree,rnode,key_val);    

        return 0;
}

/**
* Used to get the position of the MAX key within the subtree
* @param btree The btree
* @param subtree The subtree to be searched
* @return The node containing the key and position of the key
*/
static node_pos get_max_key_pos(btree * btree, bt_node * subtree) {
  node_pos node_pos;
  bt_node * node = subtree; 

  while(True) {
    if(node == NULL) {
      break;
    }

    if(node->leaf) {
      node_pos.node   = node;
      node_pos.index  = node->nr_active - 1;
      return node_pos;  
    } else {
      node_pos.node   = node;
      node_pos.index  = node->nr_active - 1;
      node = node->children[node->nr_active]; 
    }
  }
  return node_pos;
}

/**
* Used to get the position of the MAX key within the subtree
* @param btree The btree
* @param subtree The subtree to be searched
* @return The node containing the key and position of the key
*/
static node_pos get_min_key_pos(btree * btree, bt_node * subtree) {
  node_pos node_pos;
  bt_node * node = subtree; 

  while(True) {
    if(node == NULL) {
      break;
    }

    if(node->leaf) {
      node_pos.node   = node;
      node_pos.index  = 0;
      return node_pos;  
    } else {
      node_pos.node   = node;
      node_pos.index  = 0;
      node = node->children[0]; 
    }
  }
  return node_pos;
}

/**
* Merge nodes n1 and n2 (case 3b from Cormen)
* @param btree The btree 
* @param node The parent node 
* @param index of the child
* @param pos left or right
* @return none 
*/
static bt_node * merge_siblings(btree * btree, bt_node * parent, unsigned int index , 
          position_t pos) {
  unsigned int i,j;
  bt_node * new_node;
  bt_node * n1, * n2;
        
        if (index == (parent->nr_active)) {   
               index--;
         n1 = parent->children[parent->nr_active - 1];
         n2 = parent->children[parent->nr_active];
        } else {
               n1 = parent->children[index];
         n2 = parent->children[index + 1];
        }

  //Merge the current node with the left node
  new_node = allocate_btree_node(btree->order);
  new_node->level = n1->level;
  new_node->leaf = n1->leaf;

  for(j=0;j<btree->order - 1; j++) {
    new_node->key_vals[j] = n1->key_vals[j];
    new_node->children[j] = n1->children[j];
  }
  
  new_node->key_vals[btree->order - 1] =  parent->key_vals[index];
  new_node->children[btree->order - 1] =  n1->children[btree->order - 1];

  for(j=0;j<btree->order - 1; j++) {
    new_node->key_vals[j + btree->order] =  n2->key_vals[j];
    new_node->children[j + btree->order] =  n2->children[j];
  }
  new_node->children[2*btree->order - 1] = n2->children[btree->order - 1];

  parent->children[index] = new_node;

  for(j = index;j<parent->nr_active;j++) {
    parent->key_vals[j] = parent->key_vals[j + 1];
    parent->children[j + 1] = parent->children[j + 2];
  }

  new_node->nr_active = n1->nr_active + n2->nr_active + 1;
  parent->nr_active--;

//  for(i=parent->nr_active;i < 2*btree->order - 1; i++) {
//    parent->key_vals[i] = (bt_key_val)0; 
//  }

  free_btree_node(n1);
  free_btree_node(n2);

  if (parent->nr_active == 0 && btree->root == parent) {
    free_btree_node(parent);
    btree->root = new_node;
    if(new_node->level)
      new_node->leaf = False;
    else
      new_node->leaf = True; 
  }

  return new_node;
}

/**
* Move the key from node to another 
* @param btree The B-Tree
* @param node The parent node
* @param index of the key to be moved done 
* @param pos the position of the child to receive the key 
* @return none
*/
static void move_key(btree * btree, bt_node * node, unsigned int index, position_t pos) {
  bt_node * lchild;
  bt_node * rchild;
  unsigned int i;

  if(pos == right) {
    index--;
  }
  lchild = node->children[index];
  rchild = node->children[index + 1];
  
  // Move the key from the parent to the left child
  if(pos == left) {
    lchild->key_vals[lchild->nr_active] = node->key_vals[index];
    lchild->children[lchild->nr_active + 1] = rchild->children[0];
    rchild->children[0] = NULL;
    lchild->nr_active++;

    node->key_vals[index] = rchild->key_vals[0];
    //rchild->key_vals[0] = NULL;

    for(i=0;i<rchild->nr_active - 1;i++) {
      rchild->key_vals[i] = rchild->key_vals[i + 1];
      rchild->children[i] = rchild->children[i + 1];
    }
    rchild->children[rchild->nr_active - 1] = 
        rchild->children[rchild->nr_active];
    rchild->nr_active--;
  } else {
    // Move the key from the parent to the right child
    for(i=rchild->nr_active;i > 0 ; i--) {
      rchild->key_vals[i] = rchild->key_vals[i - 1];
      rchild->children[i + 1] = rchild->children[i];    
    }
    rchild->children[1] = rchild->children[0];    
    rchild->children[0] = NULL;

    rchild->key_vals[0] = node->key_vals[index];

    rchild->children[0] = lchild->children[lchild->nr_active];  
    lchild->children[lchild->nr_active] = NULL;

    node->key_vals[index] = lchild->key_vals[lchild->nr_active - 1];
    //lchild->key_vals[lchild->nr_active - 1] = NULL;
      
    lchild->nr_active--;
    rchild->nr_active++;    
  }       
}

/**
* Merge nodes n1 and n2
* @param n1 First node
* @param n2 Second node
* @return combined node
*/
static bt_node * merge_nodes(btree * btree, bt_node * n1, bt_key_val  kv,
                                                bt_node * n2) {
  bt_node * new_node;
  unsigned int i; 

  new_node = allocate_btree_node(btree->order);
  new_node->leaf = True;
  
  for(i=0;i<n1->nr_active;i++) {
    new_node->key_vals[i]   = n1->key_vals[i];  
                new_node->children[i]   = n1->children[i];
  }
        new_node->children[n1->nr_active] = n1->children[n1->nr_active];
        new_node->key_vals[n1->nr_active] = kv;

  for(i=0;i<n2->nr_active;i++) {
    new_node->key_vals[i + n1->nr_active + 1] = n2->key_vals[i];
                new_node->children[i + n1->nr_active + 1] = n2->children[i];
  }
        new_node->children[2*btree->order - 1] = n2->children[n2->nr_active];
  
        new_node->nr_active = n1->nr_active + n2->nr_active + 1;
        new_node->leaf = n1->leaf;
        new_node->level = n1->level;

  free_btree_node(n1);
  free_btree_node(n2);

  return new_node;
}

/**
* Used to delete a key from the B-tree node
* @param btree The btree
* @param node The node from which the key is to be deleted  
* @param key The key to be deleted
* @return 0 on success -1 on error 
*/

int delete_key_from_node(btree * btree, node_pos * node_pos) {
  unsigned int keys_max = 2*btree->order - 1;
  unsigned int i;
  bt_key_val  key_val;
  bt_node * node = node_pos->node;

  if(node->leaf == False) {
    return -1;
  } 
  
  key_val = node->key_vals[node_pos->index];

  for(i=node_pos->index;i< keys_max - 1;i++) {
    node->key_vals[i] = node->key_vals[i + 1];  
  }
  
/*  if(key_val->key) {
    mem_free(key_val->key);
                key_val->key = NULL;
  }

  if(key_val->val) {
    mem_free(key_val->val);
                key_val->val = NULL;
  }*/
  
  node->nr_active--;

  if(node->nr_active == 0 ) {
    free_btree_node(node);
  }
  return 0;
}

/**
*       Function used to delete a node from a  B-Tree
*       @param btree The B-Tree
*       @param key Key of the node to be deleted
*       @param value function to map the key to an unique integer value        
*       @param compare Function used to compare the two nodes of the tree
*       @return success or failure
*/

int btree_delete_key(btree * btree,bt_node * subtree, uint64_t key) {
  unsigned int i,index;
  bt_node * node = NULL, * rsibling, *lsibling;
  bt_node * comb_node, * parent;
  node_pos sub_node_pos;
  node_pos node_pos;
  bt_key_val key_val,new_key_val;
  uint64_t kv = key;  

  node = subtree;
  parent = NULL;  

del_loop:for (i = 0;;i = 0) {
             
            //If there are no keys simply return
            if(!node->nr_active)
                return -1;

      // Fix the index of the key greater than or equal
      // to the key that we would like to search
    
      while (i < node->nr_active && kv > 
          node->key_vals[i].key)  {
        i++;
      }
      index = i;

      // If we find such key break        
      if(i < node->nr_active && 
      kv == node->key_vals[i].key) {
      break;
      }
            if(node->leaf)
                return -1;
                
          //Store the parent node
      parent = node;

      // To get a child node 
      node = node->children[i];

            //If NULL not found
            if (node == NULL)
                return -1;

            if (index == (parent->nr_active)) {   
                lsibling =  parent->children[parent->nr_active - 1];
        rsibling = NULL; 
            } else if (index == 0) {
                lsibling = NULL;
                rsibling = parent->children[1];
            } else {
          lsibling = parent->children[i - 1];
        rsibling = parent->children[i + 1];
            }

      if (node->nr_active == btree->order - 1 && parent) {
    // The current node has (t - 1) keys but the right sibling has > (t - 1)
    // keys
    if (rsibling && (rsibling->nr_active > btree->order - 1)) {
      move_key(btree,parent,i,left);
    } else
    // The current node has (t - 1) keys but the left sibling has (t - 1)
    // keys
    if (lsibling && (lsibling->nr_active > btree->order - 1)) {
      move_key(btree,parent,i,right);
    } else
    // Left sibling has (t - 1) keys
          if(lsibling && (lsibling->nr_active == btree->order - 1)) {
            node = merge_siblings(btree,parent,i,left);
    } else
                // Right sibling has (t - 1) keys
          if(rsibling && (rsibling->nr_active == btree->order - 1)) {
            node = merge_siblings(btree,parent,i,right);
    }
      }
        }            
  
  //Case 1 : The node containing the key is found and is the leaf node.
  //Also the leaf node has keys greater than the minimum required.
  //Simply remove the key
  if(node->leaf && (node->nr_active > btree->order - 1)) {
    node_pos.node = node;
    node_pos.index = index;
    delete_key_from_node(btree,&node_pos);
    return 0;
  }

  //If the leaf node is the root permit deletion even if the number of keys is
  //less than (t - 1)
  if(node->leaf && (node == btree->root)) {
    node_pos.node = node;
    node_pos.index = index;
    delete_key_from_node(btree,&node_pos);
    return 0;
  }


  //Case 2: The node containing the key is found and is an internal node
  if(node->leaf == False) {
    if(node->children[index]->nr_active > btree->order - 1 ) {
      sub_node_pos = get_max_key_pos(btree,node->children[index]);
                        key_val = sub_node_pos.node->key_vals[sub_node_pos.index];

                        //new_key_val = (bt_key_val *)mem_alloc(sizeof(bt_key_val));
                        copy_key_val(btree,&key_val,&new_key_val);
            node->key_vals[index] = new_key_val;  
               
                        btree_delete_key(btree,node->children[index],key_val.key);
      if(sub_node_pos.node->leaf == False) {
                                print("Not leaf\n");
                        }
    } else if ((node->children[index + 1]->nr_active > btree->order - 1) ) {
      sub_node_pos = 
                                get_min_key_pos(btree,node->children[index + 1]);
                        key_val = sub_node_pos.node->key_vals[sub_node_pos.index];

                        //new_key_val = (bt_key_val *)mem_alloc(sizeof(bt_key_val));
                        copy_key_val(btree,&key_val,&new_key_val);
            node->key_vals[index] = new_key_val;  
               
                        btree_delete_key(btree,node->children[index + 1],key_val.key);
      if(sub_node_pos.node->leaf == False) {
                                print("Not leaf\n");
                        }

    } else if ( 
      node->children[index]->nr_active == btree->order - 1 &&
      node->children[index + 1]->nr_active == btree->order - 1) {

      comb_node = merge_nodes(btree,node->children[index],
                                node->key_vals[index],
        node->children[index + 1]);
      node->children[index] = comb_node;
      
      for(i=index + 1;i<node->nr_active;i++) {
        node->children[i] = node->children[i + 1];
        node->key_vals[i - 1] = node->key_vals[i];
      }
      node->nr_active--;
                        if (node->nr_active == 0 && btree->root == node) {
                                free_btree_node(node);
                                btree->root = comb_node;        
                        } 
                        node = comb_node;
                        goto del_loop;
    }   
          }
  
  // Case 3:
  // In this case start from the top of the tree and continue
  // moving to the leaf node making sure that each node that
  // we encounter on the way has atleast 't' (order of the tree)
  // keys 
  if(node->leaf && (node->nr_active > btree->order - 1)) {
        node_pos.node = node;
        node_pos.index = index;
        delete_key_from_node(btree,&node_pos);
  }

        return 0;
}

/**
* Function used to get the node containing the given key
* @param btree The btree to be searched
* @param key The the key to be searched
* @return The node and position of the key within the node 
*/
node_pos  get_btree_node(btree * btree, uint64_t key) {
  node_pos kp;
  uint64_t key_val = key; 
  bt_node * node;
  unsigned int i = 0;
  static k=0,j=0;
  k++;
  kp.node = NULL;
  node = btree->root;

    
  for (;;i = 0) { 

      // Fix the index of the key greater than or equal
      // to the key that we would like to search
    
      while (i < node->nr_active && key_val > 
          node->key_vals[i].key)  {
        i++; j++;
      }

      // If we find such key return the key-value pair        
      if(i < node->nr_active && 
      key_val == node->key_vals[i].key) {
        kp.node = node;
        kp.index = i; 
        j++;
#ifdef DEBUG
        if ((k+1)%100 == 0)
          fprintf(stdout, "get_btree_node: avg search calls = %d\n", j/k);
#endif
        return kp;
      }
  
      // If the node is leaf and if we did not find the key 
      // return NULL
      if(node->leaf) {
        return kp;
      }

      // To got a child node 
      node = node->children[i];
  }
        return kp;

}

/**
*       Used to destory btree
*       @param btree The B-tree
*       @return none
*/
void btree_destroy(btree * btree) {
       int i = 0;
       unsigned int current_level;

       bt_node * head, * tail, * node;
       bt_node * child, * del_node;

       node = btree->root;
       current_level = node->level;
       head = node;
       tail = node;

       while(True) {
               if(head == NULL) {
                       break;
               }
               if (head->level < current_level) {
                       current_level = head->level;
               }

               if(head->leaf == False) {
                       for(i = 0 ; i < head->nr_active + 1; i++) {
                               child = head->children[i];
                               tail->next = child;
                               tail = child;
                               child->next = NULL;
                       }
               }
               del_node = head;
               head = head->next;
               free_btree_node(del_node);
       }

}

/**
*       Function used to search a node in a B-Tree
*       @param btree The B-tree to be searched
*       @param key Key of the node to be search
*       @return The key-value pair
*/
bt_key_val btree_search(btree * btree, uint64_t key) {

  bt_key_val key_val;
  key_val.key = 0;
  key_val.val = 0;
  key_val.pt = NULL;

  node_pos kp = get_btree_node(btree,key);

  if(kp.node) {
    key_val = kp.node->key_vals[kp.index];
  }
  return key_val; 
}

/**
*       Used to copy key value from source to destination
*       @param src The source key value
*       @param dst The dest key value
*       @return none
*/
static void copy_key_val(btree * btree, bt_key_val  *src, bt_key_val  *dst) {
        unsigned int keysize;
        unsigned int datasize;

        dst->key = src->key;
        
        dst->val = src->val;
        dst->pt = src->pt;
        
}

/**
* Get the max key in the btree
* @param btree The btree
* @return The max key 
*/
uint64_t btree_get_max_key(btree * btree) {
  node_pos node_pos;
  node_pos = get_max_key_pos(btree,btree->root);
  return node_pos.node->key_vals[node_pos.index].key;
}

/**
* Get the min key in the btree
* @param btree The btree
* @return The max key 
*/
uint64_t btree_get_min_key(btree * btree) {
  node_pos node_pos;
  node_pos = get_min_key_pos(btree,btree->root);
  return node_pos.node->key_vals[node_pos.index].key;
}

#ifdef DEBUG

/**
* Used to print the keys of the bt_node
* @param node The node whose keys are to be printed
* @return none
*/

static void print_single_node(btree *btree, bt_node * node) {
  
  int i = 0;
  
  print(" { "); 
  while(i < node->nr_active) {
    print("k %llx v %llx (%d) ", node->key_vals[i].key, node->key_vals[i].val,
      node->level);
    i++;
  }
  print("} (0x%x,%d) ", node,node->leaf); 
}

/**
*       Function used to print the B-tree
*       @param root Root of the B-Tree
*       @param print_key Function used to print the key value
*       @return none
*/

void print_subtree(btree *btree,bt_node * node) {
  
  int i = 0;
  unsigned int current_level;

  bt_node * head, * tail;
  bt_node * child;

  current_level = node->level;
  head = node;
  tail = node;

  while(True) {
    if(head == NULL) {
      break;
    }
    if (head->level < current_level) {
      current_level = head->level;
      print("\n");
    }
    print_single_node(btree,head);

    if(head->leaf == False) { 
      for(i = 0 ; i < head->nr_active + 1; i++) {
        child = head->children[i];
        tail->next = child;
        tail = child;
        child->next = NULL;
      }
    }
    head = head->next;  
  }
  print("\n");
}


#endif