datapath: Backport flex_arrays.

[sliver-openvswitch.git] / lib / util.c

diff --git a/lib/util.c b/lib/util.c
index c05c582..639424d 100644 (file)
--- a/lib/util.c
+++ b/lib/util.c
@@ -16,8 +16,11 @@
 
 #include <config.h>
 #include "util.h"
+#include <assert.h>
 #include <errno.h>
+#include <limits.h>
 #include <stdarg.h>
+#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -596,3 +599,46 @@ abs_file_name(const char *dir, const char *file_name)
  * its return value.  (Note that every scalar type can be implicitly
  * converted to bool.) */
 void ignore(bool x OVS_UNUSED) { }
+
+/* Returns an appropriate delimiter for inserting just before the 0-based item
+ * 'index' in a list that has 'total' items in it. */
+const char *
+english_list_delimiter(size_t index, size_t total)
+{
+    return (index == 0 ? ""
+            : index < total - 1 ? ", "
+            : total > 2 ? ", and "
+            : " and ");
+}
+
+/* Given a 32 bit word 'n', calculates floor(log_2('n')).  This is equivalent
+ * to finding the bit position of the most significant one bit in 'n'.  It is
+ * an error to call this function with 'n' == 0. */
+int
+log_2_floor(uint32_t n)
+{
+    assert(n);
+
+#if !defined(UINT_MAX) || !defined(UINT32_MAX)
+#error "Someone screwed up the #includes."
+#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
+    return 31 - __builtin_clz(n);
+#else
+    {
+        int log = 0;
+
+#define BIN_SEARCH_STEP(BITS)                   \
+        if (n >= (1 << BITS)) {                 \
+            log += BITS;                        \
+            n >>= BITS;                         \
+        }
+        BIN_SEARCH_STEP(16);
+        BIN_SEARCH_STEP(8);
+        BIN_SEARCH_STEP(4);
+        BIN_SEARCH_STEP(2);
+        BIN_SEARCH_STEP(1);
+#undef BIN_SEARCH_STEP
+        return log;
+    }
+#endif
+}