git.cworth.org Git - vogl/blob - src/voglcore/vogl_hash_map.cpp

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_hash_map.cpp
  28 #include "vogl_core.h"
  29 #include "vogl_hash_map.h"
  30 #include "vogl_rand.h"
  31
  32 namespace vogl
  33 {
  34     class counted_obj
  35     {
  36     public:
  37         counted_obj(uint v = 0)
  38             : m_val(v)
  39         {
  40             m_count++;
  41         }
  42
  43         counted_obj(const counted_obj &obj)
  44             : m_val(obj.m_val)
  45         {
  46             m_count++;
  47         }
  48
  49         ~counted_obj()
  50         {
  51             VOGL_ASSERT(m_count > 0);
  52             m_count--;
  53         }
  54
  55         static uint m_count;
  56
  57         uint m_val;
  58
  59         operator size_t() const
  60         {
  61             return m_val;
  62         }
  63
  64         bool operator==(const counted_obj &rhs) const
  65         {
  66             return m_val == rhs.m_val;
  67         }
  68         bool operator==(const uint rhs) const
  69         {
  70             return m_val == rhs;
  71         }
  72     };
  73
  74     uint counted_obj::m_count;
  75
  76 #define VOGL_HASHMAP_VERIFY(x) \
  77     if (!(x))                    \
  78         return false;
  79
  80     bool hash_map_test()
  81     {
  82         random r0, r1;
  83
  84         uint seed = 0;
  85         for (uint t = 0; t < 2000; t++)
  86         {
  87             seed++;
  88
  89             typedef vogl::hash_map<counted_obj, counted_obj> my_hash_map;
  90             my_hash_map m;
  91
  92             const uint n = r0.irand(1, 100000);
  93
  94             printf("%u\n", n);
  95
  96             r1.seed(seed);
  97
  98             vogl::vector<int> q;
  99
 100             uint count = 0;
 101             for (uint i = 0; i < n; i++)
 102             {
 103                 uint v = r1.urand32() & 0x7FFFFFFF;
 104                 my_hash_map::insert_result res = m.insert(counted_obj(v), counted_obj(v ^ 0xdeadbeef));
 105                 if (res.second)
 106                 {
 107                     count++;
 108                     q.push_back(v);
 109                 }
 110             }
 111
 112             VOGL_HASHMAP_VERIFY(m.size() == count);
 113
 114             r1.seed(seed);
 115
 116             my_hash_map cm(m);
 117             m.clear();
 118             m = cm;
 119             cm.reset();
 120
 121             for (uint i = 0; i < n; i++)
 122             {
 123                 uint v = r1.urand32() & 0x7FFFFFFF;
 124                 my_hash_map::const_iterator it = m.find(counted_obj(v));
 125                 VOGL_HASHMAP_VERIFY(it != m.end());
 126                 VOGL_HASHMAP_VERIFY(it->first == v);
 127                 VOGL_HASHMAP_VERIFY(it->second == (v ^ 0xdeadbeef));
 128             }
 129
 130             for (uint t = 0; t < 2; t++)
 131             {
 132                 const uint nd = r0.irand(1, q.size() + 1);
 133                 for (uint i = 0; i < nd; i++)
 134                 {
 135                     uint p = r0.irand(0, q.size());
 136
 137                     int k = q[p];
 138                     if (k >= 0)
 139                     {
 140                         q[p] = -k - 1;
 141
 142                         bool s = m.erase(counted_obj(k));
 143                         VOGL_HASHMAP_VERIFY(s);
 144                     }
 145                 }
 146
 147                 typedef vogl::hash_map<uint, empty_type> uint_hash_set;
 148                 uint_hash_set s;
 149
 150                 for (uint i = 0; i < q.size(); i++)
 151                 {
 152                     int v = q[i];
 153
 154                     if (v >= 0)
 155                     {
 156                         my_hash_map::const_iterator it = m.find(counted_obj(v));
 157                         VOGL_HASHMAP_VERIFY(it != m.end());
 158                         VOGL_HASHMAP_VERIFY(it->first == (uint)v);
 159                         VOGL_HASHMAP_VERIFY(it->second == ((uint)v ^ 0xdeadbeef));
 160
 161                         s.insert(v);
 162                     }
 163                     else
 164                     {
 165                         my_hash_map::const_iterator it = m.find(counted_obj(-v - 1));
 166                         VOGL_HASHMAP_VERIFY(it == m.end());
 167                     }
 168                 }
 169
 170                 uint found_count = 0;
 171                 for (my_hash_map::const_iterator it = m.begin(); it != m.end(); ++it)
 172                 {
 173                     VOGL_HASHMAP_VERIFY(it->second == ((uint)it->first ^ 0xdeadbeef));
 174
 175                     uint_hash_set::const_iterator fit(s.find((uint)it->first));
 176                     VOGL_HASHMAP_VERIFY(fit != s.end());
 177
 178                     VOGL_HASHMAP_VERIFY(fit->first == it->first);
 179
 180                     found_count++;
 181                 }
 182
 183                 VOGL_HASHMAP_VERIFY(found_count == s.size());
 184             }
 185
 186             VOGL_HASHMAP_VERIFY(counted_obj::m_count == m.size() * 2);
 187         }
 188
 189         return true;
 190     }
 191
 192 } // namespace vogl