[webkit-dev] Hash table empty value

[Michael Catanzaro]

On Tue, Dec 18, 2018 at 2:31 PM, Ryosuke Niwa <rniwa at webkit.org> wrote:
> I tend to agree but then we'd come up with other numbers for the 
> empty & deleted values.
> I've been thinking that we could use -1 and -2 but that's also 
> somewhat arbitrary restriction.

Using min/max values seems much safer. E.g. we already have in 
HashTraits.h:

// Default unsigned traits disallow both 0 and max as keys -- use these 
traits to allow zero and disallow max - 1.
template<typename T> struct UnsignedWithZeroKeyHashTraits : 
GenericHashTraits<T> {
    static const bool emptyValueIsZero = false;
    static T emptyValue() { return std::numeric_limits<T>::max(); }
    static void constructDeletedValue(T& slot) { slot = 
std::numeric_limits<T>::max() - 1; }
    static bool isDeletedValue(T value) { return value == 
std::numeric_limits<T>::max() - 1; }
};

And:

template<typename T> struct SignedWithZeroKeyHashTraits : 
GenericHashTraits<T> {
    static const bool emptyValueIsZero = false;
    static T emptyValue() { return std::numeric_limits<T>::min(); }
    static void constructDeletedValue(T& slot) { slot = 
std::numeric_limits<T>::max(); }
    static bool isDeletedValue(T value) { return value == 
std::numeric_limits<T>::max(); }
};

Which both seem much safer than the current default:

// Default integer traits disallow both 0 and -1 as keys (max value 
instead of -1 for unsigned).
template<typename T> struct GenericHashTraitsBase<true, T> : 
GenericHashTraitsBase<false, T> {
    static const bool emptyValueIsZero = true;
    static void constructDeletedValue(T& slot) { slot = 
static_cast<T>(-1); }
    static bool isDeletedValue(T value) { return value == 
static_cast<T>(-1); }
};

Michael