hmmer-3.3/easel/esl_red_black.c
// Checks a red-black tree to see if it maintains the red-black invaiants
// returns eslOK if so, eslFAIL if not
Checks a red-black tree to see if it maintains the red-black invaiants
returns eslOK if so, eslFAIL if not
Checks a red - black tree to see if it maintains the red - black invaiants returns eslOK if so eslFAIL if not
int esl_red_black_doublekey_check_invariants(ESL_RED_BLACK_DOUBLEKEY *tree){
  if(tree == NULL){
    return eslFAIL; 
  }
  if((tree->parent == NULL) && (tree->color !=ESL_RED_BLACK_COLOR_BLACK)){
    printf("Detected red root node in esl_red_black_doublekey_check_invariants\n");
    return eslFAIL;
  }
  if(tree->color == ESL_RED_BLACK_COLOR_RED){
    if(tree->parent != NULL){
      if(tree->parent->color == ESL_RED_BLACK_COLOR_RED){
        printf("Detected red parent of red node in esl_red_black_doublekey_check_invariants\n");
        return eslFAIL;
      }
    }
    if(tree->small != NULL){
      if(tree->small->color == ESL_RED_BLACK_COLOR_RED){
        printf("Detected red small child of red node in esl_red_black_doublekey_check_invariants\n");
        return eslFAIL;
      }
    }
    if(tree->large != NULL){
      if(tree->large->color == ESL_RED_BLACK_COLOR_RED){
        printf("Detected red large child of red node in esl_red_black_doublekey_check_invariants\n");
        return eslFAIL;
      }
    }
  }
  if(tree->parent != NULL){ 
    if((tree->parent->small != tree) && (tree->parent->large != tree)){
      printf("Node's parent didn't have it as a child in esl_red_black_doublekey_check_invariants\n");
      return eslFAIL;
    }
    if((tree->parent->small == tree) && (tree->parent->large == tree)){
      printf("Node was both the small and large child of its parent in esl_red_black_doublekey_check_invariants\n");
      return eslFAIL;
    }
  }
  if(tree->small != NULL){
    if(tree->small->parent != tree){
      printf("Node's small child didn't have it as a parent in esl_red_black_doublekey_check_invariants\n");
    }
  }
  if(tree->large != NULL){
    if(tree->large->parent != tree){
      printf("Node's large child didn't have it as a parent in esl_red_black_doublekey_check_invariants\n");
    }
  }
  if((tree->small != NULL) && (esl_red_black_doublekey_check_invariants(tree->small) != eslOK)){
    return eslFAIL;
  }
  if((tree->large != NULL) && (esl_red_black_doublekey_check_invariants(tree->large) != eslOK)){
    return eslFAIL;
  }
  return eslOK;
}
int esl_red_black_doublekey_check_invariants ( ESL_RED_BLACK_DOUBLEKEY * tree ) { if ( tree == NULL ) { return eslFAIL ; } if ( ( tree -> parent == NULL ) && ( tree -> color != ESL_RED_BLACK_COLOR_BLACK ) ) { printf ( " \n " ) ; return eslFAIL ; } if ( tree -> color == ESL_RED_BLACK_COLOR_RED ) { if ( tree -> parent != NULL ) { if ( tree -> parent -> color == ESL_RED_BLACK_COLOR_RED ) { printf ( " \n " ) ; return eslFAIL ; } } if ( tree -> small != NULL ) { if ( tree -> small -> color == ESL_RED_BLACK_COLOR_RED ) { printf ( " \n " ) ; return eslFAIL ; } } if ( tree -> large != NULL ) { if ( tree -> large -> color == ESL_RED_BLACK_COLOR_RED ) { printf ( " \n " ) ; return eslFAIL ; } } } if ( tree -> parent != NULL ) { if ( ( tree -> parent -> small != tree ) && ( tree -> parent -> large != tree ) ) { printf ( " \n " ) ; return eslFAIL ; } if ( ( tree -> parent -> small == tree ) && ( tree -> parent -> large == tree ) ) { printf ( " \n " ) ; return eslFAIL ; } } if ( tree -> small != NULL ) { if ( tree -> small -> parent != tree ) { printf ( " \n " ) ; } } if ( tree -> large != NULL ) { if ( tree -> large -> parent != tree ) { printf ( " \n " ) ; } } if ( ( tree -> small != NULL ) && ( esl_red_black_doublekey_check_invariants ( tree -> small ) != eslOK ) ) { return eslFAIL ; } if ( ( tree -> large != NULL ) && ( esl_red_black_doublekey_check_invariants ( tree -> large ) != eslOK ) ) { return eslFAIL ; } return eslOK ; }
Checks a red-black tree to see if it maintains the red-black invaiants
returns eslOK if so, eslFAIL if not
Checks a red - black tree to see if it maintains the red - black invaiants returns eslOK if so eslFAIL if not
// Why are you calling this on a NULL tree? //need to check our parent and children for no-double-red invariant // now, check connectivity of this node //If we get this far, then the current node maintains all the invariants we can easily  //check, so recurse // If we get this far, then we haven't failed any of the checks and therefore have passed 