Introduce LiteralSet

Introduce LiteralSet

This CL introduces WTF::LiteralSet, an implementation of a set based on a sorted
table. TableSet is more memory efficient than HashSet for static sets because
it doesn't allocate any memory.

This CL deploys LiteralSet in ReplaceSelectionCommand.cpp and FormatBlockCommand.cpp.
Future CLs will use LiteralSet in more locations.

[eseidel, 2013-05-22 00:40:14]

Seems OK.  It's not as polished as some of the other pieces of WTF, but I can
see us using this a lot.

Your most compelling argument is probably binary size.  Do you happen to have
any concept of how much this saves? Presumably not much yet.

My biggest concern is that the name should be scarier, or at least more obvious
that it does not own its storage.  Not owning your storage is scary.

LiteralSet is fine.

https://codereview.chromium.org/15622005/diff/6001/Source/core/dom/QualifiedN...
File Source/core/dom/QualifiedName.h (right):

https://codereview.chromium.org/15622005/diff/6001/Source/core/dom/QualifiedN...
Source/core/dom/QualifiedName.h:127: bool lessThanByImplAddress(const
QualifiedName* const&, const QualifiedName* const&);
I think these probably belong as static class methods on QualifiedName.  Or
traits-style?  traits might be cleaner.  Up to you.  Free methods don't make
much sense to me though.

https://codereview.chromium.org/15622005/diff/6001/Source/core/editing/Replac...
File Source/core/editing/ReplaceSelectionCommand.cpp (right):

https://codereview.chromium.org/15622005/diff/6001/Source/core/editing/Replac...
Source/core/editing/ReplaceSelectionCommand.cpp:567: static const QualifiedName*
elementNames[] = {
Why not just make this AtomicString-based?  If you go the Traits-path, you could
use a translator.

https://codereview.chromium.org/15622005/diff/6001/Source/core/editing/Replac...
Source/core/editing/ReplaceSelectionCommand.cpp:632: if
(isProhibitedParagraphChild(toHTMLElement(node.get())->tagQName())) {
Is this intentional?

https://codereview.chromium.org/15622005/diff/6001/Source/wtf/TableSet.h
File Source/wtf/TableSet.h (right):

https://codereview.chromium.org/15622005/diff/6001/Source/wtf/TableSet.h#newc...
Source/wtf/TableSet.h:41: class TableSet {
This needs to be more scary.  And I would add a header-level comment explaining
this pattern.

https://codereview.chromium.org/15622005/diff/6001/Source/wtf/TableSet.h#newc...
Source/wtf/TableSet.h:62: ASSERT(!isEmpty());
Do you also want to ASSERT That value is never null?

https://codereview.chromium.org/15622005/diff/6001/Source/wtf/TableSet.h#newc...
Source/wtf/TableSet.h:66: bool isEmpty() { return !m_size; }
This is really isInitialized, no?

[abarth-chromium, 2013-05-22 00:54:15]

On 2013/05/22 00:40:14, eseidel wrote:
> Your most compelling argument is probably binary size.  Do you happen to have
> any concept of how much this saves? Presumably not much yet.

It saves a few bytes, but nothing to write home about.

[abarth-chromium, 2013-05-22 00:58:25]

https://codereview.chromium.org/15622005/diff/6001/Source/core/editing/Replac...
File Source/core/editing/ReplaceSelectionCommand.cpp (right):

https://codereview.chromium.org/15622005/diff/6001/Source/core/editing/Replac...
Source/core/editing/ReplaceSelectionCommand.cpp:567: static const QualifiedName*
elementNames[] = {
On 2013/05/22 00:40:14, eseidel wrote:
> Why not just make this AtomicString-based?  If you go the Traits-path, you
could
> use a translator.

The table needs to be computable by the linker.  We could expose the symbols for
the underlying atomic strings from HTMLNames now that they're created at
compile-time, but that seemed undesirable.

https://codereview.chromium.org/15622005/diff/6001/Source/core/editing/Replac...
Source/core/editing/ReplaceSelectionCommand.cpp:632: if
(isProhibitedParagraphChild(toHTMLElement(node.get())->tagQName())) {
On 2013/05/22 00:40:14, eseidel wrote:
> Is this intentional?

Yes.  We need to pass a const QualifiedName* to contains.  We could make a new
one, but we might as well use the one that's already here.

https://codereview.chromium.org/15622005/diff/6001/Source/wtf/TableSet.h
File Source/wtf/TableSet.h (right):

https://codereview.chromium.org/15622005/diff/6001/Source/wtf/TableSet.h#newc...
Source/wtf/TableSet.h:62: ASSERT(!isEmpty());
On 2013/05/22 00:40:14, eseidel wrote:
> Do you also want to ASSERT That value is never null?

It's a const reference.  There's no way for a const reference to be null.

https://codereview.chromium.org/15622005/diff/6001/Source/wtf/TableSet.h#newc...
Source/wtf/TableSet.h:66: bool isEmpty() { return !m_size; }
On 2013/05/22 00:40:14, eseidel wrote:
> This is really isInitialized, no?

Yep.

[eseidel, 2013-05-22 19:44:46]

lgtm

I think "literal" is more descriptive in this case than "static".  Static
implies to me that the set doesn't change (which it doesn't).  Literal implies
to me that the compiler owns the data (which it does).

You should also leave a comment about how this code is broken for XHTML.

[commit-bot: I haz the power, 2013-05-22 19:53:23]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/abarth@chromium.org/15622005/15006

[commit-bot: I haz the power, 2013-06-05 07:43:40]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/abarth@chromium.org/15622005/15006

[commit-bot: I haz the power, 2013-06-05 07:43:41]

Failed to apply patch for Source/wtf/LiteralSet.h:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  A         Source/wtf/LiteralSet.h
  Copied Source/core/platform/Task.h -> Source/wtf/LiteralSet.h
  patching file Source/wtf/LiteralSet.h
  Hunk #1 FAILED at 28.
  1 out of 1 hunk FAILED -- saving rejects to file Source/wtf/LiteralSet.h.rej

Patch:   NR  Source/core/platform/Task.h->Source/wtf/LiteralSet.h
Index: Source/wtf/LiteralSet.h
diff --git a/Source/core/platform/Task.h b/Source/wtf/LiteralSet.h
similarity index 68%
copy from Source/core/platform/Task.h
copy to Source/wtf/LiteralSet.h
index
fe0270a8ec78113c954aa5a1fd5d2758d23a89eb..3dd52b40e582f65237c212de064cdb54e03dfe92
100644
--- a/Source/core/platform/Task.h
+++ b/Source/wtf/LiteralSet.h
@@ -28,30 +28,47 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-#ifndef Task_h
-#define Task_h
+#ifndef WTF_LiteralSet_h
+#define WTF_LiteralSet_h
 
-#include "wtf/Functional.h"
-#include <public/WebThread.h>
+#include "wtf/NonCopyingSort.h"
 
-namespace WebCore {
+#include <algorithm>
 
-class Task : public WebKit::WebThread::Task {
+namespace WTF {
+
+template<typename T, typename Comparer>
+class LiteralSet {
 public:
-    explicit Task(const Closure& closure)
-        : m_closure(closure)
+    LiteralSet()
+        : m_values(0)
+        , m_size(0)
+    {
+    }
+
+    void init(T values[], size_t size)
     {
+        ASSERT(!isInitialized());
+        m_values = values;
+        m_size = size;
+        nonCopyingSort(m_values, m_values + m_size, Comparer::lessThan);
     }
 
-    virtual void run() OVERRIDE
+    bool contains(const T& value)
     {
-        m_closure();
+        ASSERT(isInitialized());
+        return std::binary_search(m_values, m_values + m_size, value,
Comparer::lessThan);
     }
 
+    bool isInitialized() { return !m_size; }
+
 private:
-    Closure m_closure;
+    T* m_values;
+    size_t m_size;
 };
 
-} // namespace WebCore
+} // namespace WTF
+
+using WTF::LiteralSet;
 
-#endif // Task_h
+#endif