Shlomi Fish avatar Shlomi Fish committed a0ce3d4

Some fixes for the libavl tree in 32-bit.

TODO : test.

Comments (0)

Files changed (4)

fc-solve/source/CMakeLists.txt

 
 INCLUDE (CheckTypeSize)
 CHECK_TYPE_SIZE("int" INT_SIZE_IN_BYTES)
+CHECK_TYPE_SIZE("void*" SIZEOF_VOID_P BUILTIN_TYPES_ONLY)
 
 MATH(EXPR INT_SIZE_IN_BITS "8 * ${INT_SIZE_IN_BYTES}")
 

fc-solve/source/config.h.in

 #cmakedefine FCS_WITH_CONTEXT_VARIABLE
 
 /*
+ * The size of void*.
+ */
+@SIZEOF_VOID_P_CODE@
+
+/*
  * This flag determines whether we are using the more compact but slower,
  * internal move tokens.
  *  */

fc-solve/source/libavl/avl.c

 #include "inline.h"
 #include "alloc_wrap.h"
 
+#ifdef WITH_AVL_BALANCE_FIELD
+static GCC_INLINE signed char avl_get_balance(struct avl_node * node)
+{
+    return node->avl_balance;
+}
+
+static GCC_INLINE struct avl_node * avl_process_link(uintptr_t mylink)
+{
+    return (struct avl_node *)(mylink);
+}
+
+static GCC_INLINE void avl_set_link(struct avl_node * node, int myindex, struct avl_node * val)
+{
+    node->avl_mylink[myindex] = ((uintptr_t)val);
+}
+
+/*
+ * "Be conservative in what you do, be liberal in what you accept from others."
+ * -- http://www.joelonsoftware.com/items/2008/03/17.htm
+ *
+ * Without bounding this, the program fails.
+ * */
+#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_balance = AVL_BOUND(balance);
+}
+#else
 static GCC_INLINE signed char avl_get_balance(struct avl_node * node)
 {
     return (((signed char)(node->avl_mylink[0] & 0x7))-3);
     node->avl_mylink[0] &= (~0x7);
     node->avl_mylink[0] |= (((uintptr_t)(AVL_BOUND(balance)+3))&0x7);
 }
+#endif
 
 static GCC_INLINE void avl_increment_balance(struct avl_node * node)
 {

fc-solve/source/libavl/avl.h

 
 #include <stddef.h>
 #include <stdint.h>
+
+#include "config.h"
 #include "meta_alloc.h"
 
+#if SIZEOF_VOID_P == 4
+#define WITH_AVL_BALANCE_FIELD 1
+#endif
+
 #ifdef FCS_LIBAVL_STORE_WHOLE_KEYS
 #include "delta_states.h"
 #endif
 #define avl_root avl_proto_root.avl_mylink[0]
 #define TREE_AVL_ROOT(tree) ((struct avl_node *)((tree)->avl_root))
 #define SET_TREE_AVL_ROOT(tree, val) ((tree)->avl_root = (uintptr_t)val)
+
 /* An AVL tree node. */
 struct avl_node
   {
     avl_key_t avl_data;                /* Pointer to data. */
     uintptr_t avl_mylink[2];  /* Subtrees. */
-#if 0
+#ifdef WITH_AVL_BALANCE_FIELD
     signed char avl_balance;       /* Balance factor. */
 #endif
   };
 #define L(node, i) (avl_process_link(node->avl_mylink[i]))
 #define SET_L(node, i, val) (avl_set_link(node, i, val))
 #define NODEPTR_GET_BALANCE(p) avl_get_balance(p)
-#define NODE_GET_BALANCE(node) NODEPTR_GET_BALANCE(*(p))
 #define NODEPTR_SET_BALANCE(p, b) avl_set_balance((p), (b))
 /* AVL traverser structure. */
 struct avl_traverser
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.