X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/b37bf2e156556c589aea3e1f58a377f2b1189665..4e4e5a6f2694187498445a6ac6f1634ce8141119:/wtf/HashTraits.h

diff --git a/wtf/HashTraits.h b/wtf/HashTraits.h
index 5f35278..c8d40f7 100644
--- a/wtf/HashTraits.h
+++ b/wtf/HashTraits.h
@@ -1,7 +1,5 @@
-// -*- mode: c++; c-basic-offset: 4 -*-
 /*
- * This file is part of the KDE libraries
- * Copyright (C) 2005, 2006 Apple Computer, Inc.
+ * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -23,8 +21,8 @@
 #ifndef WTF_HashTraits_h
 #define WTF_HashTraits_h
 
-#include "Assertions.h"
 #include "HashFunctions.h"
+#include "TypeTraits.h"
 #include <utility>
 #include <limits>
 
@@ -33,219 +31,82 @@ namespace WTF {
     using std::pair;
     using std::make_pair;
 
-    template<typename T> struct IsInteger           { static const bool value = false; };
-    template<> struct IsInteger<bool>               { static const bool value = true; };
-    template<> struct IsInteger<char>               { static const bool value = true; };
-    template<> struct IsInteger<signed char>        { static const bool value = true; };
-    template<> struct IsInteger<unsigned char>      { static const bool value = true; };
-    template<> struct IsInteger<short>              { static const bool value = true; };
-    template<> struct IsInteger<unsigned short>     { static const bool value = true; };
-    template<> struct IsInteger<int>                { static const bool value = true; };
-    template<> struct IsInteger<unsigned int>       { static const bool value = true; };
-    template<> struct IsInteger<long>               { static const bool value = true; };
-    template<> struct IsInteger<unsigned long>      { static const bool value = true; };
-    template<> struct IsInteger<long long>          { static const bool value = true; };
-    template<> struct IsInteger<unsigned long long> { static const bool value = true; };
-
-    COMPILE_ASSERT(IsInteger<bool>::value, WTF_IsInteger_bool_true);
-    COMPILE_ASSERT(IsInteger<char>::value, WTF_IsInteger_char_true);
-    COMPILE_ASSERT(IsInteger<signed char>::value, WTF_IsInteger_signed_char_true);
-    COMPILE_ASSERT(IsInteger<unsigned char>::value, WTF_IsInteger_unsigned_char_true);
-    COMPILE_ASSERT(IsInteger<short>::value, WTF_IsInteger_short_true);
-    COMPILE_ASSERT(IsInteger<unsigned short>::value, WTF_IsInteger_unsigned_short_true);
-    COMPILE_ASSERT(IsInteger<int>::value, WTF_IsInteger_int_true);
-    COMPILE_ASSERT(IsInteger<unsigned int>::value, WTF_IsInteger_unsigned_int_true);
-    COMPILE_ASSERT(IsInteger<long>::value, WTF_IsInteger_long_true);
-    COMPILE_ASSERT(IsInteger<unsigned long>::value, WTF_IsInteger_unsigned_long_true);
-    COMPILE_ASSERT(IsInteger<long long>::value, WTF_IsInteger_long_long_true);
-    COMPILE_ASSERT(IsInteger<unsigned long long>::value, WTF_IsInteger_unsigned_long_long_true);
-
-    COMPILE_ASSERT(!IsInteger<char*>::value, WTF_IsInteger_char_pointer_false);
-    COMPILE_ASSERT(!IsInteger<const char* >::value, WTF_IsInteger_const_char_pointer_false);
-    COMPILE_ASSERT(!IsInteger<volatile char* >::value, WTF_IsInteger_volatile_char_pointer__false);
-    COMPILE_ASSERT(!IsInteger<double>::value, WTF_IsInteger_double_false);
-    COMPILE_ASSERT(!IsInteger<float>::value, WTF_IsInteger_float_false);
-
     template<typename T> struct HashTraits;
 
     template<bool isInteger, typename T> struct GenericHashTraitsBase;
-    template<typename T> struct GenericHashTraitsBase<true, T> {
-        typedef T TraitType;
-        typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
-        static const bool emptyValueIsZero = true;
-        static const bool needsDestruction = false;
-    };
+
     template<typename T> struct GenericHashTraitsBase<false, T> {
-        typedef T TraitType;
-        typedef HashTraits<T> StorageTraits;
         static const bool emptyValueIsZero = false;
         static const bool needsDestruction = true;
     };
 
+    // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
+    template<typename T> struct GenericHashTraitsBase<true, T> {
+        static const bool emptyValueIsZero = true;
+        static const bool needsDestruction = false;
+        static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); }
+        static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
+    };
+
     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
+        typedef T TraitType;
         static T emptyValue() { return T(); }
-        static const bool needsRef = false;
     };
 
     template<typename T> struct HashTraits : GenericHashTraits<T> { };
 
-    // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
-    template<> struct HashTraits<signed char> : GenericHashTraits<int> {
-        static signed char deletedValue() { return -1; }
-    };
-    template<> struct HashTraits<short> : GenericHashTraits<int> {
-        static short deletedValue() { return -1; }
-    };
-    template<> struct HashTraits<int> : GenericHashTraits<int> {
-        static int deletedValue() { return -1; }
-    };
-    template<> struct HashTraits<unsigned int> : GenericHashTraits<unsigned int> {
-        static unsigned int deletedValue() { return static_cast<unsigned int>(-1); }
-    };
-    template<> struct HashTraits<long> : GenericHashTraits<long> {
-        static long deletedValue() { return -1; }
-    };
-    template<> struct HashTraits<unsigned long> : GenericHashTraits<unsigned long> {
-        static unsigned long deletedValue() { return static_cast<unsigned long>(-1); }
-    };
-    template<> struct HashTraits<long long> : GenericHashTraits<long long> {
-        static long long deletedValue() { return -1; }
-    };
-    template<> struct HashTraits<unsigned long long> : GenericHashTraits<unsigned long long> {
-        static unsigned long long deletedValue() { return static_cast<unsigned long long>(-1); }
-    };
-    
-    template<typename T> struct FloatHashTraits {
-        typedef T TraitType;
-        typedef HashTraits<T> StorageTraits;
+    template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
+        static const bool needsDestruction = false;
         static T emptyValue() { return std::numeric_limits<T>::infinity(); }
-        static T deletedValue() { return -std::numeric_limits<T>::infinity(); }
+        static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); }
+        static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
+    };
+
+    template<> struct HashTraits<float> : FloatHashTraits<float> { };
+    template<> struct HashTraits<double> : FloatHashTraits<double> { };
+
+    // 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 const bool needsDestruction = false;
-        static const bool needsRef = false;
-    };
-    template<> struct HashTraits<float> : FloatHashTraits<float> {
-    };
-    template<> struct HashTraits<double> : FloatHashTraits<double> {
+        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; }
     };
 
     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
-        typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
         static const bool emptyValueIsZero = true;
         static const bool needsDestruction = false;
-        static P* deletedValue() { return reinterpret_cast<P*>(-1); }
+        static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); }
+        static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
     };
 
     template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
-        typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
-        typedef typename StorageTraits::TraitType StorageType;
         static const bool emptyValueIsZero = true;
-        static const bool needsRef = true;
-
-        typedef union { 
-            P* m_p; 
-            StorageType m_s; 
-        } UnionType;
-
-        static void ref(const StorageType& s) 
-        { 
-            if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p) 
-                const_cast<P*>(p)->ref(); 
-        }
-        static void deref(const StorageType& s) 
-        { 
-            if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p) 
-                const_cast<P*>(p)->deref(); 
-        }
-    };
-
-    // template to set deleted values
-
-    template<typename Traits> struct DeletedValueAssigner {
-        static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
+        static void constructDeletedValue(RefPtr<P>& slot) { new (&slot) RefPtr<P>(HashTableDeletedValue); }
+        static bool isDeletedValue(const RefPtr<P>& value) { return value.isHashTableDeletedValue(); }
     };
 
-    template<typename T, typename Traits> inline void assignDeleted(T& location)
-    {
-        DeletedValueAssigner<Traits>::assignDeletedValue(location);
-    }
-
     // special traits for pairs, helpful for their use in HashMap implementation
 
-    template<typename FirstTraits, typename SecondTraits> struct PairHashTraits;
-
     template<typename FirstTraitsArg, typename SecondTraitsArg>
-    struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
+    struct PairHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
         typedef FirstTraitsArg FirstTraits;
         typedef SecondTraitsArg SecondTraits;
         typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
 
-        typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
-
         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
-
-        static TraitType emptyValue()
-        {
-            return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
-        }
-    };
-
-    template<typename FirstTraits, typename SecondTraits>
-    struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
-        typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
+        static TraitType emptyValue() { return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
 
         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
 
-        static TraitType deletedValue()
-        {
-            return TraitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
-        }
-
-        static void assignDeletedValue(TraitType& location)
-        {
-            assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
-            location.second = SecondTraits::emptyValue();
-        }
+        static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
+        static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
     };
 
     template<typename First, typename Second>
     struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
 
-    template<typename FirstTraits, typename SecondTraits>
-    struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
-    {
-        static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
-        {
-            PairHashTraits<FirstTraits, SecondTraits>::assignDeletedValue(location);
-        }
-    };
-
-    template<typename First, typename Second>
-    struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
-    {
-        static void assignDeletedValue(pair<First, Second>& location)
-        {
-            HashTraits<pair<First, Second> >::assignDeletedValue(location);
-        }
-    };
-
-    // hash functions and traits that are equivalent (for code sharing)
-
-    template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
-        typedef HashArg Hash;
-        typedef TraitsArg Traits;
-    };
-    template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
-        typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
-        typedef IntHash<IntType> Hash;
-        typedef HashTraits<IntType> Traits;
-    };
-    template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
-        typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
-        typedef IntHash<IntType> Hash;
-        typedef HashTraits<IntType> Traits;
-    };
-
 } // namespace WTF
 
 using WTF::HashTraits;