git.cworth.org Git - vogl/blob - src/voglcore/vogl_rh_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_rh_hash_map.cpp
  28 #include "vogl_core.h"
  29 #include "vogl_rh_hash_map.h"
  30 #include "vogl_rand.h"
  31
  32 namespace vogl
  33 {
  34     class rh_counted_obj
  35     {
  36     public:
  37         rh_counted_obj(uint v = 0)
  38             : m_val(v)
  39         {
  40             m_count++;
  41         }
  42
  43         rh_counted_obj(const rh_counted_obj &obj)
  44             : m_val(obj.m_val)
  45         {
  46             m_count++;
  47         }
  48
  49         ~rh_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 rh_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 rh_counted_obj::m_count;
  75
  76 #define VOGL_HASHMAP_VERIFY(x) \
  77     if (!(x))                    \
  78         return false;
  79
  80     bool rh_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::rh_hash_map<rh_counted_obj, rh_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             VOGL_HASHMAP_VERIFY(m.check());
 101
 102             uint count = 0;
 103             for (uint i = 0; i < n; i++)
 104             {
 105                 uint v = r1.urand32() & 0x7FFFFFFF;
 106                 my_hash_map::insert_result res = m.insert(rh_counted_obj(v), rh_counted_obj(v ^ 0xdeadbeef));
 107                 if (res.second)
 108                 {
 109                     count++;
 110                     q.push_back(v);
 111                 }
 112             }
 113
 114             VOGL_HASHMAP_VERIFY(m.check());
 115
 116             VOGL_HASHMAP_VERIFY(m.size() == count);
 117
 118             r1.seed(seed);
 119
 120             my_hash_map cm(m);
 121             VOGL_HASHMAP_VERIFY(m == cm);
 122             VOGL_HASHMAP_VERIFY(!(m != cm));
 123             VOGL_HASHMAP_VERIFY(cm == m);
 124             VOGL_HASHMAP_VERIFY(cm.check());
 125             m.clear();
 126             m = cm;
 127             VOGL_HASHMAP_VERIFY(m.check());
 128             cm.reset();
 129             VOGL_HASHMAP_VERIFY(cm.check());
 130
 131             for (uint i = 0; i < n; i++)
 132             {
 133                 uint v = r1.urand32() & 0x7FFFFFFF;
 134                 my_hash_map::const_iterator it = m.find(rh_counted_obj(v));
 135                 VOGL_HASHMAP_VERIFY(it != m.end());
 136                 VOGL_HASHMAP_VERIFY(it->first == v);
 137                 VOGL_HASHMAP_VERIFY(it->second == (v ^ 0xdeadbeef));
 138             }
 139
 140             for (uint t = 0; t < 2; t++)
 141             {
 142                 const uint nd = r0.irand(1, q.size() + 1);
 143                 for (uint i = 0; i < nd; i++)
 144                 {
 145                     uint p = r0.irand(0, q.size());
 146
 147                     int k = q[p];
 148                     if (k >= 0)
 149                     {
 150                         q[p] = -k - 1;
 151
 152                         if (r0.irand(0, 1) == 0)
 153                         {
 154                             bool s = m.erase(m.find(rh_counted_obj(k)));
 155                             VOGL_HASHMAP_VERIFY(s);
 156                         }
 157                         else
 158                         {
 159                             bool s = m.erase(rh_counted_obj(k));
 160                             VOGL_HASHMAP_VERIFY(s);
 161                         }
 162                     }
 163                 }
 164
 165                 typedef vogl::rh_hash_map<uint, empty_type> uint_hash_set;
 166                 uint_hash_set s;
 167
 168                 for (uint i = 0; i < q.size(); i++)
 169                 {
 170                     int v = q[i];
 171
 172                     if (v >= 0)
 173                     {
 174                         my_hash_map::const_iterator it = m.find(rh_counted_obj(v));
 175                         VOGL_HASHMAP_VERIFY(it != m.end());
 176                         VOGL_HASHMAP_VERIFY(it->first == (uint)v);
 177                         VOGL_HASHMAP_VERIFY(it->second == ((uint)v ^ 0xdeadbeef));
 178
 179                         s.insert(v);
 180                     }
 181                     else
 182                     {
 183                         my_hash_map::const_iterator it = m.find(rh_counted_obj(-v - 1));
 184                         VOGL_HASHMAP_VERIFY(it == m.end());
 185                     }
 186                 }
 187
 188                 uint found_count = 0;
 189                 for (my_hash_map::const_iterator it = m.begin(); it != m.end(); ++it)
 190                 {
 191                     VOGL_HASHMAP_VERIFY(it->second == ((uint)it->first ^ 0xdeadbeef));
 192
 193                     uint_hash_set::const_iterator fit(s.find((uint)it->first));
 194                     VOGL_HASHMAP_VERIFY(fit != s.end());
 195
 196                     VOGL_HASHMAP_VERIFY(fit->first == it->first);
 197
 198                     found_count++;
 199                 }
 200
 201                 VOGL_HASHMAP_VERIFY(found_count == s.size());
 202             }
 203
 204             VOGL_HASHMAP_VERIFY(m.check());
 205
 206             VOGL_HASHMAP_VERIFY(rh_counted_obj::m_count == m.size() * 2);
 207         }
 208
 209         return true;
 210     }
 211
 212 } // namespace vogl