include/am-hashmap.h
author David Anderson <dvander@alliedmods.net>
Sat Aug 24 02:36:11 2013 -0700 (2013-08-24)
changeset 9 4cd655ff4c2c
parent 8 73549b7f37f5
child 10 0ac292cc1467
permissions -rw-r--r--
Fix HashTable/HashMap bugs, and add a clear() method.
dvander@2
     1
// vim: set sts=8 ts=2 sw=2 tw=99 et:
dvander@2
     2
//
dvander@2
     3
// Copyright (C) 2013, David Anderson and AlliedModders LLC
dvander@2
     4
// All rights reserved.
dvander@2
     5
// 
dvander@2
     6
// Redistribution and use in source and binary forms, with or without
dvander@2
     7
// modification, are permitted provided that the following conditions are met:
dvander@2
     8
// 
dvander@2
     9
//  * Redistributions of source code must retain the above copyright notice, this
dvander@2
    10
//  list of conditions and the following disclaimer.
dvander@2
    11
//  * Redistributions in binary form must reproduce the above copyright notice,
dvander@2
    12
//  this list of conditions and the following disclaimer in the documentation
dvander@2
    13
//  and/or other materials provided with the distribution.
dvander@2
    14
//  * Neither the name of AlliedModders LLC nor the names of its contributors
dvander@2
    15
//  may be used to endorse or promote products derived from this software
dvander@2
    16
//  without specific prior written permission.
dvander@2
    17
//
dvander@2
    18
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
dvander@2
    19
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
dvander@2
    20
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
dvander@2
    21
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
dvander@2
    22
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
dvander@2
    23
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
dvander@2
    24
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
dvander@2
    25
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
dvander@2
    26
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
dvander@2
    27
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
dvander@2
    28
// POSSIBILITY OF SUCH DAMAGE.
dvander@2
    29
dvander@2
    30
#ifndef _include_amtl_hashmap_h_
dvander@2
    31
#define _include_amtl_hashmap_h_
dvander@2
    32
dvander@2
    33
#include <am-hashtable.h>
dvander@2
    34
dvander@2
    35
namespace ke {
dvander@2
    36
dvander@2
    37
// Template parameters:
dvander@2
    38
//
dvander@2
    39
// K - Key type.
dvander@2
    40
// V - Value type.
dvander@2
    41
// HashPolicy - A struct with a hash and comparator function for each lookup type:
dvander@2
    42
//     static uint32_t hash(const Type &value);
dvander@2
    43
//     static bool matches(const Type &value, const K &key);
dvander@2
    44
//
dvander@2
    45
// All types that match a given key, must compute the same hash.
dvander@2
    46
//
dvander@2
    47
// Note that like HashTable, a HashMap is not usable until init() has been called.
dvander@2
    48
template <typename K,
dvander@2
    49
          typename V,
dvander@2
    50
          typename HashPolicy,
dvander@2
    51
          typename AllocPolicy = SystemAllocatorPolicy>
dvander@2
    52
class HashMap : public AllocPolicy
dvander@2
    53
{
dvander@2
    54
 private:
dvander@2
    55
  struct Entry
dvander@2
    56
  {
dvander@2
    57
    K key;
dvander@2
    58
    V value;
dvander@2
    59
dvander@8
    60
    Entry()
dvander@8
    61
    {
dvander@8
    62
    }
dvander@8
    63
dvander@2
    64
    Entry(const K &aKey, const V &aValue)
dvander@2
    65
     : key(aKey),
dvander@2
    66
       value(aValue)
dvander@2
    67
    {
dvander@2
    68
    }
dvander@2
    69
  };
dvander@2
    70
dvander@2
    71
  struct Policy
dvander@2
    72
  {
dvander@2
    73
    typedef Entry Payload;
dvander@2
    74
dvander@2
    75
    template <typename Lookup>
dvander@2
    76
    static uint32_t hash(const Lookup &key) {
dvander@2
    77
      return HashPolicy::hash(key);
dvander@2
    78
    }
dvander@2
    79
dvander@2
    80
    template <typename Lookup>
dvander@2
    81
    static bool matches(const Lookup &key, const Payload &payload) {
dvander@2
    82
      return HashPolicy::matches(key, payload.key);
dvander@2
    83
    }
dvander@2
    84
  };
dvander@2
    85
dvander@2
    86
  typedef HashTable<Policy, AllocPolicy> Internal;
dvander@2
    87
dvander@2
    88
 public:
dvander@2
    89
  HashMap(AllocPolicy ap = AllocPolicy())
dvander@2
    90
    : table_(ap)
dvander@2
    91
  {
dvander@2
    92
  }
dvander@2
    93
dvander@2
    94
  // capacity must be a power of two.
dvander@2
    95
  bool init(size_t capacity = 16) {
dvander@2
    96
    return table_.init(capacity);
dvander@2
    97
  }
dvander@2
    98
dvander@2
    99
  typedef typename Internal::Result Result;
dvander@2
   100
  typedef typename Internal::Insert Insert;
dvander@2
   101
dvander@2
   102
  template <typename Lookup>
dvander@2
   103
  Result find(const Lookup &key) {
dvander@2
   104
    return table_.find(key);
dvander@2
   105
  }
dvander@2
   106
dvander@2
   107
  template <typename Lookup>
dvander@2
   108
  Insert findForAdd(const Lookup &key) {
dvander@2
   109
    return table_.findForAdd(key);
dvander@2
   110
  }
dvander@2
   111
dvander@2
   112
  template <typename Lookup>
dvander@2
   113
  void removeIfExists(const Lookup &key) {
dvander@2
   114
    return table_.remove(key);
dvander@2
   115
  }
dvander@2
   116
dvander@2
   117
  void remove(Result &r) {
dvander@2
   118
    table_.remove(r);
dvander@2
   119
  }
dvander@2
   120
dvander@2
   121
  // The map must not have been mutated in between findForAdd() and add().
dvander@2
   122
  // The Insert object is still valid after add() returns, however.
dvander@2
   123
  bool add(Insert &i, const K &key, const V &value) {
dvander@2
   124
    return table_.add(i, Entry(key, value));
dvander@2
   125
  }
dvander@2
   126
dvander@8
   127
  // This can be used to avoid compiler constructed temporaries, since AMTL
dvander@8
   128
  // does not yet support move semantics. If you use this, the key and value
dvander@8
   129
  // must be set after.
dvander@8
   130
  bool add(Insert &i) {
dvander@8
   131
    return table_.add(i);
dvander@8
   132
  }
dvander@8
   133
dvander@9
   134
  void clear() {
dvander@9
   135
    table_.clear();
dvander@9
   136
  }
dvander@9
   137
dvander@2
   138
  size_t estimateMemoryUse() const {
dvander@2
   139
    return table_.estimateMemoryUse();
dvander@2
   140
  }
dvander@2
   141
dvander@2
   142
 private:
dvander@2
   143
  Internal table_;
dvander@2
   144
};
dvander@2
   145
dvander@2
   146
}
dvander@2
   147
dvander@2
   148
#endif // _include_amtl_hashmap_h_