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;

[sergei, 2017/10/11 10:03:21]

can it be more specific, e.g. uint32_t or int32_t or be a template parameter? It
might also affect the name of the final class, even if there is a generic
container with integer keys, the final one would be UInt32Map.

[Wladimir Palant, 2017/10/11 18:28:30]

Done. Not going to add any template parameters however - this would complicate
the choice of sentinel values, not worth it at the moment.

For reference, I chose int32_t here originally because I assume signed
operations to map better to JavaScript code. However, this is premature
optimization. So I changed it into uint32_t which is more natural here, we can
still test the performance and optimize once that code path is actually used.

[sergei, 2017/10/17 12:58:06]

Acknowledged.

+  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

[sergei, 2017/10/11 10:03:21]

I would remove these comment, having a couple of reserved values are better then
removing the half of the possible values range. This comment would make sense if
the implementation of is_invalid be like return key < 0;.

[Wladimir Palant, 2017/10/11 18:28:30]

Done. However, we need sentinel values at the edge of the valid range then.

-    static const int KEY_INVALID = -1;

[sergei, 2017/10/11 10:03:21]

the type should be key_type, not int.

[Wladimir Palant, 2017/10/11 18:28:30]

Done.

-    static const int KEY_DELETED = -2;

[hub, 2017/10/10 20:37:53]

Do these two const need to be public?

[Wladimir Palant, 2017/10/11 18:28:31]

Done.

+  protected:
+    static const key_type KEY_INVALID = 0xFFFFFFFF;
+    static const key_type KEY_DELETED = 0xFFFFFFFE;
 
-    int first;

[sergei, 2017/10/11 10:03:21]

it should be key_type

[Wladimir Palant, 2017/10/11 18:28:30]

Done.

+  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

[sergei, 2017/10/11 10:03:21]

Maybe it's a premature generalization but I would make a MapEntry generic and
below say
template<typename Value>
using IntMap = Map<Map_internal::MapEntry<Map_internal::IntSetEntry, Value>>;
or taking into account the type of integer
using UInt32Map =
Map<Map_internal::MapEntry<Map_internal::IntSetEntry<uint32_t>, Value>>;

[sergei, 2017/10/11 10:05:11]

IntSetEntry is of course from IntMap_internal.

[Wladimir Palant, 2017/10/11 18:28:30]

Yes, probably premature generalization. Trouble is, strings are passed by
reference, integers are not. While generalizing and passing integers by
reference to constructors isn't the worst thing that can happen, I'd rather not.

[sergei, 2017/10/17 12:58:06]

Acknowledged.

+  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();
     }
   };
 }
 
-using IntSet = Set<IntMap_internal::IntSetEntry>;
+using Uint32Set = Set<Uint32Map_internal::Uint32SetEntry>;
 
 template<typename Value>
-using IntMap = Map<IntMap_internal::IntMapEntry<Value>, Value>;
+using Uint32Map = Map<Uint32Map_internal::Uint32MapEntry<Value>>;