Reimplement Scheme_hash_table using linear probing. (issue 559790043 by address@hidden)

[dak]

I don't see the point in reinventing the wheel.  This functionality is
provided both by Guile (where an improved implementation could be
submitted) and C++'s STL.  In addition, I don't think that it is used to
a degree where it would significantly affect LilyPond's performance.

Reworking this to a degree where the quality of its dealing with SCM
values matches that of our code base and documenting its inscrutable
inner workings thus do not seem like they would be worth the effort.


https://codereview.appspot.com/559790043/diff/563830043/input/regression/scheme-unit-test.ly
File input/regression/scheme-unit-test.ly (right):

https://codereview.appspot.com/559790043/diff/563830043/input/regression/scheme-unit-test.ly#newcode6
input/regression/scheme-unit-test.ly:6: #(ly:test-scheme-hash-table)
This seems like a rather opaque way of testing functionality.

https://codereview.appspot.com/559790043/diff/563830043/lily/include/scm-hash.hh
File lily/include/scm-hash.hh (right):

https://codereview.appspot.com/559790043/diff/563830043/lily/include/scm-hash.hh#newcode36
lily/include/scm-hash.hh:36: Entry *table_;
Any reason this is not a C++ array?  We don't use C style arrays
elsewhere.

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc
File lily/scm-hash.cc (right):

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode59
lily/scm-hash.cc:59: if (old_table[i].key != NULL)
NULL is not a valid SCM value, nor is it guaranteed not to overlap with
valid SCM values that may be stored here.  Better use SCM_UNDEFINED
here.  Also SCM values should not be compared numerically but by using
scm_is_eq .  That allows making sure that there are no integer/SCM
confusion (there is a #define one can set for that purpose) which are a
typical source for problems.

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode73
lily/scm-hash.cc:73: uintptr_t x = (uintptr_t) (key);
For using the numerical value of an SCM, there is SCM_UNPACK.  Please
don't use C style casts.  They always succeed, even in cases where they
are a very bad idea.

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode81
lily/scm-hash.cc:81: {
This only works for specific cases (uintptr_t == 4 or 8).  Instead of
creating our own implementation, how about submitting a patch to Guile
upstream?  That way there is better review for Guile-specific problems
and we don't have the maintenance cost in our own code.

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode95
lily/scm-hash.cc:95: if (table_[i].key != NULL)
NULL is not a valid SCM value, and SCM values should be compared using
scm_is_eq rather than !=.  Using SCM_UNDEFINED is the proper way of
doing things.

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode111
lily/scm-hash.cc:111: *idx = int (hash (key) % cap_);
If the capacity is going to be one less than a power of 2, it would
appear to make sense to use a power of 2 instead and use a mask rather
than a modulo operation.  In particular since the hash functions look
like they are designed in a manner where the individual bits are
well-distributed.

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode161
lily/scm-hash.cc:161: if (j <= gap)
This stuff is completely inscrutable and without any comment.  It would
appear that it may depend on the capacity being one less than a power of
2 (see above) but without any analysis and any comment or justification,
that is quite unclear.

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode170
lily/scm-hash.cc:170: while (next % cap_ != h);
Fall-through without any assertion making sure that stuff worked right?

https://codereview.appspot.com/559790043/diff/563830043/lily/scm-hash.cc#newcode264
lily/scm-hash.cc:264: class Timestamp
This stuff really has no place in this file.

https://codereview.appspot.com/559790043/