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