Commits

Shlomi Fish committed ab305dc

Fix a bug in the AVL tree.

It went out of balance, because the balance can temporarily be under -1
or over 1.

  • Participants
  • Parent commits 08b1149
  • Tags depth_dbm_fc_solver_100K_to_400k_run_with_500GB_with_fixed_avl_tree

Comments (0)

Files changed (1)

File fc-solve/source/libavl/avl.c

 
 static GCC_INLINE signed char avl_get_balance(struct avl_node * node)
 {
-    return (((signed char)(node->avl_mylink[0] & 0x3))-1);
+    return (((signed char)(node->avl_mylink[0] & 0x7))-3);
 }
 
 static GCC_INLINE struct avl_node * avl_process_link(uintptr_t mylink)
 {
-    return (struct avl_node *)(mylink & (~((uintptr_t)0x3)));
+    return (struct avl_node *)(mylink & (~((uintptr_t)0x7)));
 }
 
 static GCC_INLINE void avl_set_link(struct avl_node * node, int myindex, struct avl_node * val)
 {
-    node->avl_mylink[myindex] = (((uintptr_t)val) | (node->avl_mylink[myindex] & 0x3));
+    node->avl_mylink[myindex] = (((uintptr_t)val) | (node->avl_mylink[myindex] & 0x7));
 }
 
 /*
  *
  * Without bounding this, the program fails.
  * */
-#define AVL_BOUND(x) (((x) >= 1) ? 1 : ((x) <= (-1)) ? -1 : 0)
+#define AVL_BOUND(x) (((x) >= 3) ? 3 : ((x) <= (-3)) ? -3 : x)
 static GCC_INLINE void avl_set_balance(struct avl_node * node, signed char balance)
 {
-    node->avl_mylink[0] &= (~0x3);
-    node->avl_mylink[0] |= (((uintptr_t)(AVL_BOUND(balance)+1))&0x3);
+    node->avl_mylink[0] &= (~0x7);
+    node->avl_mylink[0] |= (((uintptr_t)(AVL_BOUND(balance)+3))&0x7);
 }
 
 static GCC_INLINE void avl_increment_balance(struct avl_node * node)