Practical Arduino C

Page 199

struct btNode{
  uint16_t key;
  void* data;
  btNode* left;
  btNode* right;
};
bool btInsert(uint16_t key, btNode** leaf, void* dta, size_t dtaSize) {
  if(*leaf == NULL) {
    *leaf = (btNode*)malloc(sizeof(btNode));
    if(!*leaf) {return false;}
    (*leaf)->key = key;
    (*leaf)->left = (*leaf)->right = NULL;
    (*leaf)->data = malloc(dtaSize);
  if(!(*leaf)->data) {return false;}
    memcpy((*leaf)->data, dta, dtaSize);
    return true;
  } 
  if (key < (*leaf)->key) {
    return btInsert(key, &(*leaf)->left, dta, dtaSize);
  }
  return btInsert(key, &(*leaf)->right, dta, dtaSize);
}

Page 200

void* btSearch(uint16_t key, btNode* leaf){
  if(leaf) {
    if(leaf->key == key) {
      return leaf->data;
    }
    if( key < leaf->key) {
      return btSearch(key, leaf->left);
    }
    return btSearch(key, leaf->right);
  } else {
    return NULL;
  }
}
int btCount(btNode* leaf) {
  if(leaf) {
    return 1 + btCount(leaf->left) + btCount(leaf->right);
  }
  return 0;
}
int btMax(int a, int b){
  return (a <= b) ? b : a;
}
int btHeight(btNode* leaf) {
  if(leaf) {
    return 1 + btMax(btHeight(leaf->left), btHeight(leaf->right));
  }
  return 0;
}
void btDeleteTree(btNode* leaf) {
  if(leaf) {
    btDeleteTree(leaf->left);
    btDeleteTree(leaf->right);
    free(leaf->data);
    free(leaf);
  }
}

Page 201

void* btSearch(uint16_t key, btNode* leaf){
  if(leaf) {
    if(leaf->key == key) {
      return leaf->data;
    }
    if( key < leaf->key) {
      return btSearch(key, leaf->left);
    }
    return btSearch(key, leaf->right);
  } else {
    return NULL;
  }
}
int btCount(btNode* leaf) {
  if(leaf) {
    return 1 + btCount(leaf->left) + btCount(leaf->right);
  }
  return 0;
}
int btMax(int a, int b){
  return (a <= b) ? b : a;
}
int btHeight(btNode* leaf) {
  if(leaf) {
    return 1 + btMax(btHeight(leaf->left), btHeight(leaf->right));
  }
  return 0;
}
void btDeleteTree(btNode* leaf) {
  if(leaf) {
    btDeleteTree(leaf->left);
    btDeleteTree(leaf->right);
    free(leaf->data);
    free(leaf);
  }
}

Page 202

Serial << "B-Tree height: " << btHeight(root) << '\n';
Serial << "Node Count: " << btCount(root) << '\n';
Serial << "Optimal height: " << 
           (int)(log(btCount(root)) / log(2) + 0.5) << '\n';

struct lNode{
  uint16_t key;
  void* data;
  lNode* next;
};
lNode *lStart = NULL, *lEnd = NULL;

Page 203

bool appendToList(uint16_t key, void* data) {
  lNode* nNode = (lNode*)malloc(sizeof(lNode));
  if(!nNode) {return false;}
  nNode->key = key;
  nNode->data = data;
  nNode->next = NULL;
  if(!lEnd) {
    lStart = lEnd = nNode;
  } else {
    lEnd = lEnd->next = nNode;
  }
  return true;
}
lNode* readListItem(int item) {
  lNode* rNode = lStart;
  for (int i = 0; i < item; i++) {
    rNode = rNode->next;
  }
  return rNode;
}
void deleteList() {
  lNode* dNode = lStart;
  while(dNode){
    lStart = dNode->next;
    free(dNode);
    dNode = lStart;
  }
  lStart = lEnd = NULL;
}

Page 204

void btExtractKeys(btNode* leaf) {
  if(leaf) {
    btExtractKeys(leaf->left);
    appendToList(leaf->key, leaf->data);
    btExtractKeys(leaf->right);
    free(leaf); // delete the tree leaf
  }
}
bool btReset(btNode** leaf, lNode* rNode) {
  if(*leaf == NULL) {
    *leaf = (btNode*)malloc(sizeof(btNode));
    (*leaf)->key = rNode->key;
    (*leaf)->left = (*leaf)->right = NULL;
    (*leaf)->data = rNode->data;
    return true;
  } else if (rNode->key < (*leaf)->key) {
    return btReset(&(*leaf)->left, rNode);
  }
  return btReset(&(*leaf)->right, rNode);
}
void resetTree(btNode** leaf, int iFrom, int iTo) {
  if(iFrom > iTo) {return;}
  int iMid = (iFrom + iTo) / 2;
  lNode* rNode = readListItem(iMid);
  btReset(leaf, rNode);
  resetTree(leaf, iFrom, iMid -1);
  resetTree(leaf, iMid + 1, iTo);
}

Page 205

void reBuildTree(btNode* root) {
  int nCount = btCount(root);
  btExtractKeys(root);
  root = NULL; //restart the tree
  resetTree(&root, 0, nCount-1);
  deleteList(); //recover the linked list memory;
}

void obsPrint(int key, observed* obs) {
  Serial << "Key: " << key << " Temp: " << obs->temp << 
         " Press: " << obs->airPress << " Hum: " << 
         obs->humidity << '\n';
}

reBuildTree(root);
Serial << "B-Tree height after rebuild: " << 
           btHeight(root) << '\n';

Page 206

void btIterate(btNode* leaf, void(*callback)(int, void*)) {
  if(leaf) {
    btIterate(leaf->left, callback);
    callback(leaf->key, leaf->data);
    btIterate(leaf->right, callback);
  }
}