[prev in list] [next in list] [prev in thread] [next in thread]
List: webkit-dev
Subject: Re: [webkit-dev] Hash table empty value
From: Maciej Stachowiak <mjs () apple ! com>
Date: 2018-12-19 22:39:52
Message-ID: 1F433BD1-946D-4C28-9844-3837CAD39298 () apple ! com
[Download RAW message or body]
> On Dec 19, 2018, at 12:54 PM, Michael Catanzaro <mcatanzaro@igalia.com> wrote:
>
> On Tue, Dec 18, 2018 at 2:31 PM, Ryosuke Niwa <rniwa@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.
> // 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
>
> _______________________________________________
> webkit-dev mailing list
> webkit-dev@lists.webkit.org
> https://lists.webkit.org/mailman/listinfo/webkit-dev
_______________________________________________
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic