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 "Map.h"
+
+namespace IntMap_internal
+{
+  struct IntSetEntry
+  {
+    typedef int key_type;
+    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;
+
+    int first;
+
+    IntSetEntry()
+        : first(KEY_INVALID)
+    {
+    }
+
+    IntSetEntry(key_type key)
+        : first(key)
+    {
+    }
+
+    bool equals(key_type 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)
+    {
+      return key;
+    }
+  };
+
+  template<typename Value>
+  struct IntMapEntry : IntSetEntry
+  {
+    typedef IntSetEntry super;
+    typedef Value value_type;
+
+    Value second;
+
+    IntMapEntry()
+        : IntSetEntry(), second()
+    {
+    }
+
+    IntMapEntry(key_type key)
+        : IntSetEntry(key), second()
+    {
+    }
+
+    IntMapEntry(key_type key, value_type value)
+        : IntSetEntry(key), second(value)
+    {
+    }
+
+    void erase()
+    {
+      super::erase();
+      second = value_type();
+    }
+  };
+}
+
+class IntSet : public Set<IntMap_internal::IntSetEntry>
+{
+};
+
+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.