Issue 5141 - Generalize Map class to allow non-strings as keys

compiled/IntMap.h

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #pragma once
 
 #include <cstddef>
+#include <climits>
 
 #include "Map.h"
 
-namespace IntMap_internal
+namespace Uint32Map_internal
 {
-  struct IntSetEntry
+  struct Uint32SetEntry
   {
-    typedef int key_type;
+  public:
+    typedef uint32_t key_type;
+    typedef key_type key_type_cref;
     typedef size_t size_type;
 
-    // The assumption here is that valid keys will always be non-negative
-    static const int KEY_INVALID = -1;
-    static const int KEY_DELETED = -2;
+  protected:
+    static const key_type KEY_INVALID = 0xFFFFFFFF;
+    static const key_type KEY_DELETED = 0xFFFFFFFE;
 
-    int first;
+  public:
+    key_type first;
 
-    IntSetEntry()
-        : first(KEY_INVALID)
-    {
-    }
-
-    IntSetEntry(key_type key)
+    Uint32SetEntry(key_type_cref key = KEY_INVALID)
         : first(key)
     {
     }
 
-    bool equals(key_type other) const
+    bool equals(key_type_cref other) const
     {
       return first == other;
     }
 
     bool is_invalid() const
     {
       return first == KEY_INVALID;
     }
 
     bool is_deleted() const
     {
       return first == KEY_DELETED;
     }
 
     void erase()
     {
       first = KEY_INVALID;
     }
 
-    static size_type hash(key_type key)
+    static size_type hash(key_type_cref key)
     {
       return key;
     }
   };
 
   template<typename Value>
-  struct IntMapEntry : IntSetEntry
+  struct Uint32MapEntry : Uint32SetEntry
   {
-    typedef IntSetEntry super;
+    typedef Uint32SetEntry super;
     typedef Value value_type;
 
-    Value second;
+    value_type second;
 
-    IntMapEntry()
-        : IntSetEntry(), second()
-    {
-    }
-
-    IntMapEntry(key_type key)
-        : IntSetEntry(key), second()
-    {
-    }
-
-    IntMapEntry(key_type key, value_type value)
-        : IntSetEntry(key), second(value)
+    Uint32MapEntry(key_type_cref key = KEY_INVALID, value_type value = value_type())
+        : Uint32SetEntry(key), second(value)
     {
     }
 
     void erase()
     {
       super::erase();
       second = value_type();
     }
   };
 }
 
-class IntSet : public Set<IntMap_internal::IntSetEntry>
-{
-};
+using Uint32Set = Set<Uint32Map_internal::Uint32SetEntry>;
 
 template<typename Value>
-class IntMap : public Map<IntMap_internal::IntMapEntry<Value>, Value>
-{
-};

[Wladimir Palant, 2017/10/10 14:33:58]

This class hasn't been tested yet beyond the fact that it compiles.

+using Uint32Map = Map<Uint32Map_internal::Uint32MapEntry<Value>>;