Hash table empty value

# Michael Catanzaro (19 hours ago)

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

Contact us to advertise here
# Maciej Stachowiak (18 hours ago)

On Dec 19, 2018, at 12:54 PM, Michael Catanzaro <mcatanzaro at igalia.com> wrote:

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:

I think that’s true for integers, but for pointers, 0 and -1 are likely safer (if you don’t need to store null pointers) or -1 and -2 if you do, since all 1 bits is less likely to be a valid address. There’s also some optimization for the special case where the empty value is 0, but probably not that important if we often need to store null pointers.

Want more features?

Request early access to our private beta of readable email premium.