Changeset 75ff31607066f7bcb0b471c3652443662c0f985f

Timestamp:

04/30/08 14:32:42 (8 months ago)

Author:

krayouva <krayouva@…>

Parents:

1c4d613e749d9e677b5d4a13214e93bfee485937

Children:

1bc545c8942b47e034f824644b4834a991178afc

git-committer:

krayouva <krayouva@gmail.com> / 2008-04-30T00:32:42Z-0400

Message:

* Minor code refactoring

- Added the frt_round2() method that rounds to the next 2nd power

Location:

c

Files:

• include/global.h (modified) (2 diffs)
• src/bitvector.c (modified) (6 diffs)

c/include/global.h

@@ -133 +133 @@
 
 /**
+ * Returns the count of leading [MSB] 0 bits in +word+.
+ */
+extern FRT_ATTR_ALWAYS_INLINE FRT_ATTR_CONST
+int frt_count_leading_zeros(frt_u32 word)
+{
+#ifdef __GNUC__
+    return __builtin_clz(word);
+#else
+    static const int count_leading_zeros[] = {
+        8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
+        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+    };
+                if (word & 0xff) return count_leading_zeros[word & 0xff];
+    word >>= 8; if (word & 0xff) return count_leading_zeros[word & 0xff] + 8;
+    word >>= 8; if (word & 0xff) return count_leading_zeros[word & 0xff] + 16;
+    word >>= 8;                  return count_leading_zeros[word & 0xff] + 24;
+#endif
+}
+
+extern FRT_ATTR_ALWAYS_INLINE FRT_ATTR_CONST
+int frt_count_leading_ones(frt_u32 word)
+{
+    return frt_count_leading_zeros(~word);
+}
+
+/**
  * Return the count of trailing [LSB] 0 bits in +word+.
  */
@@ -211 +251 @@
 
 /**
+ * Round up to the next power of 2
+ */
+extern FRT_ATTR_ALWAYS_INLINE FRT_ATTR_CONST
+int frt_round2(frt_u32 word)
+{
+    return 1 << (32 - frt_count_leading_zeros(word));
+}
+
+/**
  * For coverage, we don't want FRT_XEXIT to actually exit on uncaught
  * exceptions.  +frt_x_abort_on_exception+ is +true+ by default, set it to

c/src/bitvector.c

@@ -1 +1 @@
 #include "bitvector.h"
+#include "internal.h"
 #include <string.h>
-#include "internal.h"
 
 BitVector *bv_new_capa(int capa)
@@ -126 +126 @@
         }
     }
-    hash = (hash << 1) | bv->extends_as_ones;
-    return hash;
+    return (hash << 1) | bv->extends_as_ones;
+}
+
+static INLINE void bv_capa(BitVector *bv, int capa, int size)
+{
+    int word_size = (size >> 5) + 1;
+    REALLOC_N(bv->bits, u32, capa);
+    bv->capa = capa;
+    bv->size = size;
+    memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
+           sizeof(u32) * (capa - word_size));
 }
 
@@ -147 +156 @@
     int capa = 4;
 
-    if (bv1->extends_as_ones && bv2->extends_as_ones) {
-        size = max2(bv1->size, bv2->size);
-        bv->extends_as_ones = true;
-    }
-    else if (bv1->extends_as_ones || bv2->extends_as_ones) {
-        size = max2(bv1->size, bv2->size);
-        bv->extends_as_ones = false;
-    }
-    else {
-        size = min2(bv1->size, bv2->size);
-        bv->extends_as_ones = false;
-    }
+    bv->extends_as_ones = (bv1->extends_as_ones & bv2->extends_as_ones);
+
+    if (bv1->extends_as_ones || bv2->extends_as_ones)
+         size = max2(bv1->size, bv2->size);
+    else size = min2(bv1->size, bv2->size);
 
     word_size = (size >> 5) + 1;
-    while (capa < word_size) {
-        capa <<= 1;
-    }
+    capa = max2(frt_round2(word_size), 4);
+
     bv_recapa(bv1, capa);
     bv_recapa(bv2, capa);
-    REALLOC_N(bv->bits, u32, capa);
-    bv->capa = capa;
-    bv->size = size;
-
-    memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
-           sizeof(u32) * (capa - word_size));
+    bv_capa(bv, capa, size);
 
     for (i = 0; i < word_size; i++) {
@@ -196 +192 @@
     int max_size = max2(bv1->size, bv2->size);
     int word_size = (max_size >> 5) + 1;
-    int capa = 4;
-    while (capa < word_size) {
-        capa <<= 1;
-    }
-    REALLOC_N(bv->bits, u32, capa);
-    bv->capa = capa;
-    bv->size = max_size;
-
+    int capa = max2(frt_round2(word_size), 4);
+
+    bv->extends_as_ones = (bv1->extends_as_ones | bv2->extends_as_ones);
     bv_recapa(bv1, capa);
     bv_recapa(bv2, capa);
-
-    if (bv1->extends_as_ones || bv2->extends_as_ones) {
-        bv->extends_as_ones = true;
-    }
-    else {
-        bv->extends_as_ones = false;
-    }
-
-    memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
-           sizeof(u32) * (capa - word_size));
+    bv_capa(bv, capa, max_size);
 
     for (i = 0; i < word_size; i++) {
@@ -239 +221 @@
     int max_size = max2(bv1->size, bv2->size);
     int word_size = (max_size >> 5) + 1;
-    int capa = 4;
-    while (capa < word_size) {
-        capa <<= 1;
-    }
-    REALLOC_N(bv->bits, u32, capa);
-    bv->capa = capa;
-    bv->size = max_size;
-
+    int capa = max2(frt_round2(word_size), 4);
+
+    bv->extends_as_ones = (bv1->extends_as_ones ^ bv2->extends_as_ones);
     bv_recapa(bv1, capa);
     bv_recapa(bv2, capa);
-
-    if (bv1->extends_as_ones != bv2->extends_as_ones) {
-        bv->extends_as_ones = true;
-    }
-    else {
-        bv->extends_as_ones = false;
-    }
-
-    memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
-           sizeof(u32) * (capa - word_size));
+    bv_capa(bv, capa, max_size);
 
     for (i = 0; i < word_size; i++) {
@@ -281 +249 @@
     int i;
     int word_size = (bv1->size >> 5) + 1;
-    int capa = 4;
-    while (capa < word_size) {
-        capa <<= 1;
-    }
-    REALLOC_N(bv->bits, u32, capa);
-    bv->capa = capa;
-    bv->size = bv1->size;
+    int capa = max2(frt_round2(word_size), 4);
+
     bv->extends_as_ones = !bv1->extends_as_ones;
-    memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
-           sizeof(u32) * (capa - word_size));
+    bv_capa(bv, capa, bv1->size);
 
     for (i = 0; i < word_size; i++) {