Create HeapLinkedHashSet and LinkedHashSet, ordered heap-friendly hash sets.

Create HeapLinkedHashSet and LinkedHashSet, ordered heap-friendly hash sets.

R=ager@chromium.org, haraken@chromium.org, jochen@chromium.org, mikhail.pozdnyakov@intel.com, vegorov@chromium.org, wibling@chromium.org, zerny@chromium.org
BUG=

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=171459

[Erik Corry, 2014-04-03 07:52:57]

Some explanation is perhaps in order.

LinkedHashSet has the same name as the corresponding collection in Java and Dart
(C# doesn't have this type).

We already have ListHashSet, and I have a separate change underway to make a
garbage collected HeapListHashSet for that.  However, ListHashSet is almost
impossible to make work with weakness (a HeapListHashSet<WeakMember<T>> where
entries magically disappear when their referents are unreachable).

ListHashSet also allocates with a preallocated pool, falling back to allocating
a node per entry when the pool is exhausted.  This is also a very messy thing to
try to get to work with heap allocation and the heap version will probably not
have it.  Even off-GC-heap it's hard to size the preallocated pool correctly. 
The default is 256, which seems very high (a node is at least 12 bytes on 32 bit
so a small default ListHashSet has around 700 wasted bytes).  It's possible to
tune the preallocated size, and this is done many places in Blink, but the
performance penalty for going over the preallocated limit is likely to be rather
steep so it's hard to pick a number.

ListHashSet has one feature that LinkedHashSet does not: You can modify a
ListHashSet while you iterate over it. We actually use this in Blink, so we
can't do without ListHashSet, but I expect LinkedHashSet to be the normal
ordered set going forward.

(One possibility is to rename ListHashSet to WorkListHashSet, since a work-list
is the main use case for adding to a collection while you iterate over it.  It's
legal to remove from a ListHashSet while iterating over it, but not if you
remove the element at the current iteration point, which seems like a footgun
waiting to go off).

[Mikhail, 2014-04-03 07:56:43]

Could you please give a bit more details on why/how LinkedHashSet is more
beneficial to be used in heap comparing to the existing WTF containers?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h
File Source/wtf/HashTable.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h#n...
Source/wtf/HashTable.h:65: class LinkedHashSet;
Why is LinkedHashSet needs to be declared here?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h#n...
Source/wtf/HashTable.h:386: void checkModifications(int64_t mods) const { }
Looks like the changes in this file are unnecessary (traces of
https://codereview.chromium.org/219413002/ ?)

[Mikhail, 2014-04-03 07:58:07]

On 2014/04/03 07:56:43, mikhail.pozdnyakov wrote:
> Could you please give a bit more details on why/how LinkedHashSet is more
> beneficial to be used in heap comparing to the existing WTF containers?
> 
Ah, I did not see your previous comment. Thanks

[Mads Ager (chromium), 2014-04-03 09:24:34]

First round of comments.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/Heap.h
File Source/heap/Heap.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/heap/Heap.h#newco...
Source/heap/Heap.h:1506: true, // The anchor needs to unlink itself from the
chain.
Maybe update the comment: Needs finalization: the anchor ...

Extra points for replacing the bool here with an enum value along the lines of
NeedsFinalization.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/Heap.h#newco...
Source/heap/Heap.h:1671: // FTT (list hash set node)
The bools here are still blowing my mind. Can you write out in the comment that
this is: needs tracing, is weak and mark weak members strongly?

I would still prefer to have the template parameters be named enum values in all
of these to make it easier to read. The FTT comment doesn't help me. I need to
chase around the source base to see what it means. The enum change doesn't have
to be for this change, but I think it would be good to do it.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp
File Source/heap/HeapTest.cpp (right):

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:317: static void trace(Visitor*) { }
This is off heap, why do you need a trace method (and a static one at that)?

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:2369: typedef const Set& ConstSet;
Remove the typedef for a type you are using only once in a test?

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:2374: Persistent<Set> setX = new Set();
What does the X mean? If it is just a random other set I would just call them
set1 and set2?

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:2376: ConstSet cSet = *set.get();
cSet -> constSetReference

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h
File Source/wtf/HashTable.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h#n...
Source/wtf/HashTable.h:65: class LinkedHashSet;
On 2014/04/03 07:56:44, mikhail.pozdnyakov wrote:
> Why is LinkedHashSet needs to be declared here?

For the friend declaration below?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h#n...
Source/wtf/HashTable.h:386: void checkModifications(int64_t mods) const { }
mods -> modifications.

Also, you should probably move the ASSERT code here where asserts are enabled?
;-)

This is to be able to check from the LinkedHashSet iterator that no changes have
been made to the HashTable while we have a LinkedHashSet iterator, right?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:2: * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012
Apple Inc. All rights reserved.
Ehm, no.

You should use the short copyright notice here for new files.

[Mikhail, 2014-04-03 09:32:17]

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:52: struct LinkedHashSetNodeBase {
this actually better to be class (since it's not a real C-style struct)

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:53: ~LinkedHashSetNodeBase()
Can nodes be deleted via base interface? should the destructor be virtual? (if
should not, I think it's worth making it protected)

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:94: LinkedHashSetNodeBase(const
LinkedHashSetNodeBase& other)
Do we have cases when nodes are copied?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:109: }
If you want 'LinkedHashSetNodeBase' copy constructor to actually work you should
probably define a copy constructor here as well (and it should invoke parent's
copy constructor explicitly)

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:128: typedef HashTable<Node, Node, IdentityExtractor,
Why not "HashTable<Node*, Node*" ?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:196: iterator find(const Value&);
maybe 'ValuePeekInType' is worth using here?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:254: NodeBase m_anchor;
Could you pls explain why not working with pointers (NodeBase* m_anchor;) like
ListHashSet does?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:377: #ifndef NDEBUG
#ifdef ASSERT_ENABLED ? (same in other similar places)

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:427: const LinkedHashSetType* m_container;
I guess m_container can be const pointer: const LinkedHashSetType* const
m_container;

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:473: inline LinkedHashSet<T, U, V,
W>::LinkedHashSet() : m_anchor() { }
well if m_anchor is a class instance, the default ctor will be invoked
implicitly (no need for explicit call)

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:496: using namespace std;
"using std::swap;" is better to use IMHO, so that nothing else from "std" is
picked.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:546: m_impl.remove(m_anchor.m_prev);
shoudl it be m_impl.remove(*m_anchor.m_prev); ?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:561: const_iterator it = begin();
I did not get why this method is so different from the previous one, could you
pls explain?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:684: b.m_next = aNext;
swap(a.m_next, b.m_next) ?

[Mads Ager (chromium), 2014-04-03 09:44:58]

A few more comments.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:52: struct LinkedHashSetNodeBase {
Why not class?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:104: struct LinkedHashSetNode : public
LinkedHashSetNodeBase {
class?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:119: class LinkedHashSet {
Indentation

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:145: , isNewEntry(hashTableAddResult.isNewEntry) { }
When you are using multiple lines you should have the '{}' on separate lines:

...
{
}

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:338: // default copy, assignment and destructor are
OK
Begin comment with capital letter and end with period?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:373: const LinkedHashSetNodeBase* position,
Very strange indentation. Just put this on one line?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:423: #ifdef NDEBUG
These were guarded by ASSERT_ENABLED or something like that in hash table. Do
the same here?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:496: using namespace std;
We decided to not do this style of swap, right. Just use std::swap.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:546: m_impl.remove(m_anchor.m_prev);
Do you have tests for all of these methods? This looks like it is using a
pointer instead of a value object in remove?

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:684: b.m_next = aNext;
Can you just use std::swap(a.m_next, b.m_next) for these?

[Mads Ager (chromium), 2014-04-03 09:45:33]

Oh, Mikhail had some of the same comments here. :)

[Erik Corry, 2014-04-10 10:47:36]

Pretty major update, PTAL

https://codereview.chromium.org/223373002/diff/20001/Source/heap/Heap.h
File Source/heap/Heap.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/heap/Heap.h#newco...
Source/heap/Heap.h:1506: true, // The anchor needs to unlink itself from the
chain.
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> Maybe update the comment: Needs finalization: the anchor ...
> 
> Extra points for replacing the bool here with an enum value along the lines of
> NeedsFinalization.

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/Heap.h#newco...
Source/heap/Heap.h:1671: // FTT (list hash set node)
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> The bools here are still blowing my mind. Can you write out in the comment
that
> this is: needs tracing, is weak and mark weak members strongly?
> 
> I would still prefer to have the template parameters be named enum values in
all
> of these to make it easier to read. The FTT comment doesn't help me. I need to
> chase around the source base to see what it means. The enum change doesn't
have
> to be for this change, but I think it would be good to do it.

I've changed the markWeakMembersStrongly to an enum.  The needsTracing and
isWeak arguments are closely linked to the IsWeak and NeedsTracing templates
from TypeTraits.h. They are bool there like all the other type traits, and it
wouldn't be in keeping with the style to have only these two templates define
their own macro. I've also clarified the comments, and moved vector to the end
since it's a special case.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp
File Source/heap/HeapTest.cpp (right):

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:317: static void trace(Visitor*) { }
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> This is off heap, why do you need a trace method (and a static one at that)?

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:2369: typedef const Set& ConstSet;
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> Remove the typedef for a type you are using only once in a test?

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:2374: Persistent<Set> setX = new Set();
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> What does the X mean? If it is just a random other set I would just call them
> set1 and set2?

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/heap/HeapTest.cpp...
Source/heap/HeapTest.cpp:2376: ConstSet cSet = *set.get();
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> cSet -> constSetReference

constSet

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h
File Source/wtf/HashTable.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h#n...
Source/wtf/HashTable.h:65: class LinkedHashSet;
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> On 2014/04/03 07:56:44, mikhail.pozdnyakov wrote:
> > Why is LinkedHashSet needs to be declared here?
> 
> For the friend declaration below?

Yes.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h#n...
Source/wtf/HashTable.h:386: void checkModifications(int64_t mods) const { }
On 2014/04/03 07:56:44, mikhail.pozdnyakov wrote:
> Looks like the changes in this file are unnecessary (traces of
> https://codereview.chromium.org/219413002/ ?)

No, rather the opposite, the checkModifications methods in the other review were
unnecessary traces of this one.  I now use this and need it.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/HashTable.h#n...
Source/wtf/HashTable.h:386: void checkModifications(int64_t mods) const { }
On 2014/04/03 09:24:35, Mads Ager (chromium) wrote:
> mods -> modifications.
> 
> Also, you should probably move the ASSERT code here where asserts are enabled?
> ;-)
> 
> This is to be able to check from the LinkedHashSet iterator that no changes
have
> been made to the HashTable while we have a LinkedHashSet iterator, right?  

Nice catch!

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:52: struct LinkedHashSetNodeBase {
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> this actually better to be class (since it's not a real C-style struct)

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:52: struct LinkedHashSetNodeBase {
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> Why not class?

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:53: ~LinkedHashSetNodeBase()
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> Can nodes be deleted via base interface? should the destructor be virtual? (if
> should not, I think it's worth making it protected)

There's no virtualness here and we don't want to bloat the object.

There's a base node in the LinkedHashSet, the anchor, so we can't make the
destructor protected.

I moved the destructor to be after the constructor, which is more conventional.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:94: LinkedHashSetNodeBase(const
LinkedHashSetNodeBase& other)
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> Do we have cases when nodes are copied? 

Yes, as explained in the comment.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:104: struct LinkedHashSetNode : public
LinkedHashSetNodeBase {
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> class?

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:109: }
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> If you want 'LinkedHashSetNodeBase' copy constructor to actually work you
should
> probably define a copy constructor here as well (and it should invoke parent's
> copy constructor explicitly)

I made the copy constructor for this class undefined and private instead, since
it's not used.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:119: class LinkedHashSet {
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> Indentation

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:128: typedef HashTable<Node, Node, IdentityExtractor,
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> Why not "HashTable<Node*, Node*" ?

Then we would have to allocate lots of small Node objects.  This way they are
inlined in the backing store.

For the Heap version of LinkedHashSet there is the extra consideration that this
enables the weak processing to work: There is one backing store and the iterator
points into it, causing the weak processing to be disabled while the iterator
exists on the stack.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:145: , isNewEntry(hashTableAddResult.isNewEntry) { }
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> When you are using multiple lines you should have the '{}' on separate lines:
> 
> ...
> {
> }

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:196: iterator find(const Value&);
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> maybe 'ValuePeekInType' is worth using here?

Good idea.  Done.

To do this I had to change the type of the templated lookup function in
HashTable.h.  I checked all the places it was called to make sure that it was
still passing references, and not dereffing, causing ref pointer churn.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:254: NodeBase m_anchor;
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> Could you pls explain why not working with pointers (NodeBase* m_anchor;) like
> ListHashSet does?

Locality of reference, pressure on the allocator, ease of getting the weak
processing support working.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:338: // default copy, assignment and destructor are
OK
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> Begin comment with capital letter and end with period?

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:373: const LinkedHashSetNodeBase* position,
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> Very strange indentation. Just put this on one line?

Done (I had some ifdefs here, but I got rid of them and forgot to normalize the
line breaks)

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:377: #ifndef NDEBUG
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> #ifdef ASSERT_ENABLED ? (same in other similar places)

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:423: #ifdef NDEBUG
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> These were guarded by ASSERT_ENABLED or something like that in hash table. Do
> the same here?

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:427: const LinkedHashSetType* m_container;
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> I guess m_container can be const pointer: const LinkedHashSetType* const
> m_container;

It turns out if you do this then you can't overwrite an iterator with the
assignment operator.  You can do that with the ListHashSet iterators, so I want
to be able to do that with these.  I also removed the const in
m_containerModifications.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:473: inline LinkedHashSet<T, U, V,
W>::LinkedHashSet() : m_anchor() { }
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> well if m_anchor is a class instance, the default ctor will be invoked
> implicitly (no need for explicit call)

Done.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:496: using namespace std;
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> "using std::swap;" is better to use IMHO, so that nothing else from "std" is
> picked.

I removed the using std instead, because in this case we don't want to use
std::swap.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:496: using namespace std;
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> We decided to not do this style of swap, right. Just use std::swap.

Fixed.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:546: m_impl.remove(m_anchor.m_prev);
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> shoudl it be m_impl.remove(*m_anchor.m_prev); ?

Actually it should be m_impl.remove(static_cast<Node*>(m_anchor.m_prev))

Also fixed in removeFirst()

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:546: m_impl.remove(m_anchor.m_prev);
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> Do you have tests for all of these methods? This looks like it is using a
> pointer instead of a value object in remove?

No, I didn't test this and it didn't work (of course).

It should actually use a pointer, so we don't have to do a hash lookup in
removeFirst and removeLast, because we have a direct pointer to the first and
last elements.

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:561: const_iterator it = begin();
On 2014/04/03 09:32:18, mikhail.pozdnyakov wrote:
> I did not get why this method is so different from the previous one, could you
> pls explain?

This was accidentally left in.  My first thought was that the LinkedHashSet
should return the first entry that was equal because it is ordered, but the
whole point of a set is that there are no dupes, so it makes no difference what
order you search.  Replaced with an implementation that looks like the non-const
find()

https://codereview.chromium.org/223373002/diff/20001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:684: b.m_next = aNext;
On 2014/04/03 09:44:58, Mads Ager (chromium) wrote:
> Can you just use std::swap(a.m_next, b.m_next) for these?

swap gets us part of the way, so I refactored to use swap.

[Erik Corry, 2014-04-10 10:53:05]

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:589: iterator endIterator = end();
I need to fix this implementation to not loop.

[Mads Ager (chromium), 2014-04-10 11:12:24]

LGTM

And what you mean by not looping in find is that you just want to do a lookup in
the table, right (not that the implementation hits an infinite loop which I
initially thought when I read your comment).

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:176: void* operator new(size_t size)
Did we now have a macro for this?

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:709: using namespace std;
I thought we were not doing this?

[Mikhail, 2014-04-10 12:25:02]

looks good overall

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:132: LinkedHashSetNode(const LinkedHashSetNode&);
WTF_MAKE_NONCOPYABLE ?

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:260: void checkModifications(int64_t mods) const {
m_impl.checkModifications(mods); }
do we need those in release mode (or you think they will be optimized out)?

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:350: Node* node() const { return
const_cast<Node*>(m_iterator.node()); }
looks like it should not be a const method

[Erik Corry, 2014-04-10 13:47:28]

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:132: LinkedHashSetNode(const LinkedHashSetNode&);
On 2014/04/10 12:25:03, mikhail.pozdnyakov wrote:
> WTF_MAKE_NONCOPYABLE ?

Can't do that because it also overwrites the copy constructor, which I have
customized.

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:176: void* operator new(size_t size)
On 2014/04/10 11:12:25, Mads Ager (chromium) wrote:
> Did we now have a macro for this?

Done.

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:260: void checkModifications(int64_t mods) const {
m_impl.checkModifications(mods); }
On 2014/04/10 12:25:03, mikhail.pozdnyakov wrote:
> do we need those in release mode (or you think they will be optimized out)?

This one is only called from an assert.
The one with no arguments is an empty function in release mode.

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:350: Node* node() const { return
const_cast<Node*>(m_iterator.node()); }
On 2014/04/10 12:25:03, mikhail.pozdnyakov wrote:
> looks like it should not be a const method

Done.

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:589: iterator endIterator = end();
On 2014/04/10 10:53:06, Erik Corry wrote:
> I need to fix this implementation to not loop.

Done.

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:709: using namespace std;
On 2014/04/10 11:12:25, Mads Ager (chromium) wrote:
> I thought we were not doing this?

I was a bit confused too, but the check-webkit-style script says

Source/wtf/LinkedHashSet.h:696:  Use 'using namespace std;' instead of 'using
std::swap;'.  [build/using_std] [4]

[Erik Corry, 2014-04-10 13:53:06]

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet.h
File Source/wtf/LinkedHashSet.h (right):

https://codereview.chromium.org/223373002/diff/40001/Source/wtf/LinkedHashSet...
Source/wtf/LinkedHashSet.h:709: using namespace std;
On 2014/04/10 13:47:29, Erik Corry wrote:
> On 2014/04/10 11:12:25, Mads Ager (chromium) wrote:
> > I thought we were not doing this?
> 
> I was a bit confused too, but the check-webkit-style script says
> 
> Source/wtf/LinkedHashSet.h:696:  Use 'using namespace std;' instead of 'using
> std::swap;'.  [build/using_std] [4]

Or I could just remove the using directive completely, which is what I did now.

[jochen (gone - plz use gerrit), 2014-04-14 09:42:02]

rubberstamp lgtm

[Erik Corry, 2014-04-14 10:19:15]

The CQ bit was checked by erik.corry@gmail.com

[commit-bot: I haz the power, 2014-04-14 10:19:21]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/erik.corry@gmail.com/223373002/90001

[commit-bot: I haz the power, 2014-04-14 10:58:14]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-04-14 10:58:15]

Try jobs failed on following builders:
  tryserver.blink on linux_blink_rel

[Erik Corry, 2014-04-14 11:45:36]

The CQ bit was checked by erik.corry@gmail.com

[commit-bot: I haz the power, 2014-04-14 11:45:50]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/erik.corry@gmail.com/223373002/110001

[commit-bot: I haz the power, 2014-04-14 12:50:30]

Change committed as 171459