Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <crater/avl.h>
       4             : 
       5  1380638767 : inline static int cr8r_avl_check_links(cr8r_avl_node *n){
       6  1380638767 :     if(!n)return 1;
       7  1355237166 :     if(n->left){
       8   522163837 :         if(n->left->parent != n)return 0;
       9   522163837 :         if(!cr8r_avl_check_links(n->left))return 0;
      10             :     }
      11  1355237166 :     if(n->right){
      12   502845358 :         if(n->right->parent != n)return 0;
      13   502845358 :         if(!cr8r_avl_check_links(n->right))return 0;
      14             :     }
      15             :     return 1;
      16             : }
      17             : 
      18  3066103904 : inline static int cr8r_avl_check_balance(cr8r_avl_node *n){
      19  3066103904 :     if(!n)return 0;
      20  1355237166 :     int l, r;
      21  1355237166 :     if((l = cr8r_avl_check_balance(n->left)) == -1)return -1;
      22  1355237166 :     if((r = cr8r_avl_check_balance(n->right)) == -1)return -1;
      23  1355237166 :     if(r - l == n->balance)return 1 + (l > r ? l : r);
      24             :     return -1;
      25             : }
      26             : 
      27             : #ifdef DEBUG
      28             : #include <assert.h>
      29             : #define CR8R_AVL_ASSERT_LINKS(n) assert(cr8r_avl_check_links(n))
      30             : #define CR8R_AVL_ASSERT_BALANCE(n) assert(cr8r_avl_check_balance(n) != -1)
      31             : #define CR8R_AVL_ASSERT_ALL(n) do{CR8R_AVL_ASSERT_LINKS(n);CR8R_AVL_ASSERT_BALANCE(n);}while(0)
      32             : #else
      33             : #define CR8R_AVL_ASSERT_LINKS(n)
      34             : #define CR8R_AVL_ASSERT_BALANCE(n)
      35             : #define CR8R_AVL_ASSERT_ALL(n)
      36             : #endif
      37             :