Spin off SkTHashTable, SkTHashMap, SkTHashSet

Spin off SkTHashTable, SkTHashMap, SkTHashSet

SkTHashTable is very similar to SkTDynamicHash, except it's generalized to support non-pointer value types.

It doesn't support remove(), just to keep things simple (it's not hard to add).
Instead of an iterator, it has foreach(), again, to keep things simple.

SkTHashMap<K,V> and SkTHashSet<T> build a friendlier experience on top of SkTHashTable.

BUG=skia:

Committed: https://skia.googlesource.com/skia/+/979e0eacbd59327654d0c8d4216d6732413ef2a0

[mtklein_C, 2015-02-12 18:46:07]

mtklein@chromium.org changed reviewers:
+ fmalita@google.com

[mtklein_C, 2015-02-12 18:46:08]

We are sorely lacking in easy-to-use maps and sets.  See if this works for you? 
If not, how can we make it work for you?

[f(malita), 2015-02-12 19:37:10]

fmalita@chromium.org changed reviewers:
+ fmalita@chromium.org

[f(malita), 2015-02-12 19:37:11]

Thanks, SkTHashSet is exactly what I need atm.

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h
File src/core/SkTHash.h (right):

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode28
src/core/SkTHash.h:28: T* set(T val) {
Shouldn't all these return const T* (if anything)? Mutating an item in the table
is likely to change its key/hash and break the hashtable invariants.

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode195
src/core/SkTHash.h:195: T* find(T item) {
const

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode195
src/core/SkTHash.h:195: T* find(T item) {
Nit: I think we could use an even simpler interface for sets:

void add(T)
bool contains(T)

(this also avoids all mutability issues)

[reed1, 2015-02-12 19:49:14]

reed@google.com changed reviewers:
+ reed@google.com

[reed1, 2015-02-12 19:49:15]

SkTemplates.h seems good

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h
File src/core/SkTHash.h (right):

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode28
src/core/SkTHash.h:28: T* set(T val) {
When is (const T& val) better or worse?

[mtklein, 2015-02-12 20:09:52]

mtklein@google.com changed reviewers:
+ mtklein@google.com

[mtklein, 2015-02-12 20:09:52]

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h
File src/core/SkTHash.h (right):

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode28
src/core/SkTHash.h:28: T* set(T val) {
On 2015/02/12 19:49:15, reed1 wrote:
> When is (const T& val) better or worse?

So far, I haven't seen it matter.  This all being a template, everything here is
elided except the final copy into the table.

There are a few places where we might want to add const& if we see unnecessary
copying (here, the key passed to find, the signature of GetKey and Hash), but I
think we can probably leave that until we see a problem.

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode28
src/core/SkTHash.h:28: T* set(T val) {
On 2015/02/12 19:37:11, f(malita) wrote:
> Shouldn't all these return const T* (if anything)? Mutating an item in the
table
> is likely to change its key/hash and break the hashtable invariants.

Yeah, that's one of the sharp edges of why we don't want to generally use
SkTHashTable.  It's the same problem as foreach()... you want to be able to
modify parts of the T, but you need to be careful not to affect the Key.  We
actually need the mutability here to be able to implement things like SkTHashMap
that allow mutating the value but not the key.

I've expanded the warnings.  How's this look?

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode195
src/core/SkTHash.h:195: T* find(T item) {
On 2015/02/12 19:37:11, f(malita) wrote:
> Nit: I think we could use an even simpler interface for sets:
> 
> void add(T)
> bool contains(T)
> 
> (this also avoids all mutability issues)

Done.

https://codereview.chromium.org/925613002/diff/1/src/core/SkTHash.h#newcode195
src/core/SkTHash.h:195: T* find(T item) {
On 2015/02/12 19:37:11, f(malita) wrote:
> const

Done.

[f(malita), 2015-02-12 20:39:02]

The value params make me nervous, but I trust your template-fu :)

lgtm

https://codereview.chromium.org/925613002/diff/20001/src/core/SkTHash.h
File src/core/SkTHash.h (right):

https://codereview.chromium.org/925613002/diff/20001/src/core/SkTHash.h#newco...
src/core/SkTHash.h:117: // Both of these stragegies are valid:
strategies

[mtklein_C, 2015-02-12 20:39:48]

New patchsets have been uploaded after l-g-t-m from fmalita@chromium.org

[mtklein, 2015-02-12 20:40:24]

On 2015/02/12 20:39:02, f(malita) wrote:
> The value params make me nervous, but I trust your template-fu :)

The wonderful thing about testing and profilers is that you never have to trust
anyone (except your tests and profiler).

[mtklein, 2015-02-12 20:40:30]

https://codereview.chromium.org/925613002/diff/20001/src/core/SkTHash.h
File src/core/SkTHash.h (right):

https://codereview.chromium.org/925613002/diff/20001/src/core/SkTHash.h#newco...
src/core/SkTHash.h:117: // Both of these stragegies are valid:
On 2015/02/12 20:39:02, f(malita) wrote:
> strategies

Done.

[reed1, 2015-02-12 20:42:57]

lgtm

https://codereview.chromium.org/925613002/diff/40001/src/core/SkTHash.h
File src/core/SkTHash.h (right):

https://codereview.chromium.org/925613002/diff/40001/src/core/SkTHash.h#newco...
src/core/SkTHash.h:10: // T and K are treated as ordinary copyable C++ types.
btw -- this form of comment will not get scooped by Doxygen, but /** ... */
will.

[f(malita), 2015-02-12 20:44:06]

On 2015/02/12 20:40:24, mtklein wrote:
> On 2015/02/12 20:39:02, f(malita) wrote:
> > The value params make me nervous, but I trust your template-fu :)
> 
> The wonderful thing about testing and profilers is that you never have to
trust
> anyone (except your tests and profiler).

But the wonderful thing about working with people you trust is that you don't
have to double-check all their statements :P

[mtklein, 2015-02-12 20:46:45]

The CQ bit was checked by mtklein@google.com

[commit-bot: I haz the power, 2015-02-12 20:47:35]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/925613002/40001

[mtklein, 2015-02-12 20:47:45]

>
https://codereview.chromium.org/925613002/diff/40001/src/core/SkTHash.h#newco...
> src/core/SkTHash.h:10: // T and K are treated as ordinary copyable C++ types.
> btw -- this form of comment will not get scooped by Doxygen, but /** ... */
> will.

https://www.google.com/search?q=grumpy+cat+good&tbm=isch

[commit-bot: I haz the power, 2015-02-12 20:59:15]

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

[commit-bot: I haz the power, 2015-02-12 20:59:16]

Try jobs failed on following builders:
  Build-Win-VS2013-x86-Debug-Trybot on client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Win-VS2013-x86...)

[mtklein_C, 2015-02-12 21:02:59]

New patchsets have been uploaded after l-g-t-m from reed@google.com

[mtklein, 2015-02-12 21:03:25]

The CQ bit was checked by mtklein@google.com

[commit-bot: I haz the power, 2015-02-12 21:03:45]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/925613002/60001

[commit-bot: I haz the power, 2015-02-12 21:20:11]

Committed patchset #4 (id:60001) as
https://skia.googlesource.com/skia/+/979e0eacbd59327654d0c8d4216d6732413ef2a0