Changeset 262167 in webkit

Timestamp:

May 26, 2020, 4:33:09 PM (5 years ago)

Author:

mark.lam@apple.com

Message:

Enhance Bitmap::setEachNthBit() to also take an end index.
​https://bugs.webkit.org/show_bug.cgi?id=212386
<rdar://problem/63643324>

Reviewed by Robin Morisset.

Source/WTF:

Previously, it was only taking the n interval, and the start index.
Also fixed isEmpty() and isFull() to return a bool instead of size_t.

• wtf/Bitmap.h:

(WTF::WordType>::isEmpty const):
(WTF::WordType>::isFull const):
(WTF::WordType>::setEachNthBit):

Tools:

• TestWebKitAPI/Tests/WTF/Bitmap.cpp:

(TestWebKitAPI::testBitmapSetEachNthBitImpl):

Location:

trunk

Files:

• Source/WTF/ChangeLog (modified) (1 diff)
• Source/WTF/wtf/Bitmap.h (modified) (6 diffs)
• Tools/ChangeLog (modified) (1 diff)
• Tools/TestWebKitAPI/Tests/WTF/Bitmap.cpp (modified) (2 diffs)

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2020-05-26  Mark Lam  <mark.lam@apple.com>
+
+        Enhance Bitmap::setEachNthBit() to also take an end index.
+        https://bugs.webkit.org/show_bug.cgi?id=212386
+        <rdar://problem/63643324>
+
+        Reviewed by Robin Morisset.
+
+        Previously, it was only taking the n interval, and the start index.
+        Also fixed isEmpty() and isFull() to return a bool instead of size_t.
+
+        * wtf/Bitmap.h:
+        (WTF::WordType>::isEmpty const):
+        (WTF::WordType>::isFull const):
+        (WTF::WordType>::setEachNthBit):
+
 2020-05-26  Don Olmstead  <don.olmstead@sony.com>
 

trunk/Source/WTF/wtf/Bitmap.h

@@ -59 +59 @@
     int64_t findRunOfZeros(size_t runLength) const;
     size_t count(size_t start = 0) const;
-    size_t isEmpty() const;
-    size_t isFull() const;
+    bool isEmpty() const;
+    bool isFull() const;
     
     void merge(const Bitmap&);
@@ -120 +120 @@
     void setAndClear(Bitmap&);
 
-    void setEachNthBit(size_t start, size_t n);
+    void setEachNthBit(size_t n, size_t start = 0, size_t end = bitmapSize);
 
     bool operator==(const Bitmap&) const;
@@ -294 +294 @@
 
 template<size_t bitmapSize, typename WordType>
-inline size_t Bitmap<bitmapSize, WordType>::isEmpty() const
+inline bool Bitmap<bitmapSize, WordType>::isEmpty() const
 {
     for (size_t i = 0; i < words; ++i)
@@ -303 +303 @@
 
 template<size_t bitmapSize, typename WordType>
-inline size_t Bitmap<bitmapSize, WordType>::isFull() const
+inline bool Bitmap<bitmapSize, WordType>::isFull() const
 {
     for (size_t i = 0; i < words; ++i)
@@ -431 +431 @@
 
 template<size_t bitmapSize, typename WordType>
-inline void Bitmap<bitmapSize, WordType>::setEachNthBit(size_t start, size_t n)
-{
-    size_t index = start;
-    size_t wordIndex = index / wordSize;
-    index = index - wordIndex * wordSize;
-    while (wordIndex < words) {
+inline void Bitmap<bitmapSize, WordType>::setEachNthBit(size_t n, size_t start, size_t end)
+{
+    ASSERT(start <= end);
+    ASSERT(end <= bitmapSize);
+
+    size_t wordIndex = start / wordSize;
+    size_t endWordIndex = end / wordSize;
+    size_t index = start - wordIndex * wordSize;
+    while (wordIndex < endWordIndex) {
         while (index < wordSize) {
             bits[wordIndex] |= (one << index);
@@ -444 +447 @@
         wordIndex++;
     }
+
+    size_t endIndex = end - endWordIndex * wordSize;
+    while (index < endIndex) {
+        bits[wordIndex] |= (one << index);
+        index += n;
+    }
+
     if constexpr (!!(bitmapSize % wordSize)) {
         constexpr size_t remainingBits = bitmapSize % wordSize;

trunk/Tools/ChangeLog

@@ +1 @@
+2020-05-26  Mark Lam  <mark.lam@apple.com>
+
+        Enhance Bitmap::setEachNthBit() to also take an end index.
+        https://bugs.webkit.org/show_bug.cgi?id=212386
+        <rdar://problem/63643324>
+
+        Reviewed by Robin Morisset.
+
+        * TestWebKitAPI/Tests/WTF/Bitmap.cpp:
+        (TestWebKitAPI::testBitmapSetEachNthBitImpl):
+
 2020-05-26  Fujii Hironori  <Hironori.Fujii@sony.com>
 

trunk/Tools/TestWebKitAPI/Tests/WTF/Bitmap.cpp

@@ -982 +982 @@
 
     EXPECT_TRUE(temp == zeroes);
-    temp.setEachNthBit(0, 1);
+    temp.setEachNthBit(1);
     EXPECT_TRUE(temp == ones);
 
@@ -988 +988 @@
     size_t nValuesCount = sizeof(nValues) / sizeof(nValues[0]);
 
-    for (size_t start = 0; start < wordSize; ++start) {
-        for (size_t j = 0; j < nValuesCount; ++j) {
-            size_t n = nValues[j];
-            temp.clearAll();
-            temp.setEachNthBit(start, n);
-
-            for (size_t i = 0; i < start; ++i)
-                EXPECT_FALSE(temp.get(i));
-
-            size_t count = 0;
-            for (size_t i = start; i < size; ++i) {
-                bool expected = !count;
-                EXPECT_TRUE(temp.get(i) == expected);
-                count++;
-                count = count % n;
+    size_t startEndValues[] = { 0, 1, 2, wordSize / 2, wordSize - 1, wordSize, size / 2, size - 1, size };
+    constexpr size_t numberOfStartEndValues = sizeof(startEndValues) / sizeof(startEndValues[0]);
+
+    for (size_t start = 0; start < numberOfStartEndValues; ++start) {
+        for (size_t end = start; end < numberOfStartEndValues; ++end) {
+            size_t startIndex = startEndValues[start];
+            size_t endIndex = startEndValues[end];
+            if (endIndex < startIndex)
+                continue;
+            if (startIndex > size)
+                continue;
+            if (endIndex > size)
+                continue;
+
+            for (size_t j = 0; j < nValuesCount; ++j) {
+                size_t n = nValues[j];
+                temp.clearAll();
+                temp.setEachNthBit(n, startIndex, endIndex);
+
+                for (size_t i = 0; i < startIndex; ++i)
+                    EXPECT_FALSE(temp.get(i));
+
+                size_t count = 0;
+                for (size_t i = startIndex; i < endIndex; ++i) {
+                    bool expected = !count;
+                    EXPECT_TRUE(temp.get(i) == expected);
+                    count++;
+                    count = count % n;
+                }
+
+                for (size_t i = endIndex; i < size; ++i)
+                    EXPECT_FALSE(temp.get(i));
             }
         }