CoCalc -- basisu_containers

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

GitHub Repository: hrydgard/ppsspp
Path: blob/master/ext/basis_universal/basisu_containers_impl.h
Views: ¹⁴⁰¹
1
// basisu_containers_impl.h
2
// Do not include directly
3

4
#ifdef _MSC_VER
5
#pragma warning (disable:4127) // warning C4127: conditional expression is constant
6
#endif
7

8
namespace basisu
9
{
10
   bool elemental_vector::increase_capacity(uint32_t min_new_capacity, bool grow_hint, uint32_t element_size, object_mover pMover, bool nofail)
11
   {
12
      assert(m_size <= m_capacity);
13

14
      if (sizeof(void *) == sizeof(uint64_t))
15
         assert(min_new_capacity < (0x400000000ULL / element_size));
16
      else
17
         assert(min_new_capacity < (0x7FFF0000U / element_size));
18

19
      if (m_capacity >= min_new_capacity)
20
         return true;
21

22
      size_t new_capacity = min_new_capacity;
23
      if ((grow_hint) && (!helpers::is_power_of_2((uint64_t)new_capacity)))
24
      {
25
         new_capacity = (size_t)helpers::next_pow2((uint64_t)new_capacity);
26

27
         assert(new_capacity && (new_capacity > m_capacity));
28

29
         if (new_capacity < min_new_capacity)
30
         {
31
            if (nofail)
32
               return false;
33
            fprintf(stderr, "vector too large\n");
34
            abort();
35
         }
36
      }
37
            
38
      const size_t desired_size = element_size * new_capacity;
39
      size_t actual_size = 0;
40
      if (!pMover)
41
      {
42
         void* new_p = realloc(m_p, desired_size);
43
         if (!new_p)
44
         {
45
            if (nofail)
46
               return false;
47

48
            char buf[256];
49
#ifdef _MSC_VER
50
            sprintf_s(buf, sizeof(buf), "vector: realloc() failed allocating %u bytes", (uint32_t)desired_size);
51
#else
52
            sprintf(buf, "vector: realloc() failed allocating %u bytes", (uint32_t)desired_size);
53
#endif
54
            fprintf(stderr, "%s", buf);
55
            abort();
56
         }
57

58
#if BASISU_VECTOR_DETERMINISTIC
59
         actual_size = desired_size;
60
#elif defined(_MSC_VER)
61
         actual_size = _msize(new_p);
62
#elif HAS_MALLOC_USABLE_SIZE
63
         actual_size = malloc_usable_size(new_p);
64
#else
65
         actual_size = desired_size;
66
#endif
67
         m_p = new_p;
68
      }
69
      else
70
      {
71
         void* new_p = malloc(desired_size);
72
         if (!new_p)
73
         {
74
            if (nofail)
75
               return false;
76

77
            char buf[256];
78
#ifdef _MSC_VER
79
            sprintf_s(buf, sizeof(buf), "vector: malloc() failed allocating %u bytes", (uint32_t)desired_size);
80
#else
81
            sprintf(buf, "vector: malloc() failed allocating %u bytes", (uint32_t)desired_size);
82
#endif
83
            fprintf(stderr, "%s", buf);
84
            abort();
85
         }
86

87
#if BASISU_VECTOR_DETERMINISTIC
88
         actual_size = desired_size;
89
#elif defined(_MSC_VER)
90
         actual_size = _msize(new_p);
91
#elif HAS_MALLOC_USABLE_SIZE
92
         actual_size = malloc_usable_size(new_p);
93
#else
94
         actual_size = desired_size;
95
#endif
96

97
         (*pMover)(new_p, m_p, m_size);
98

99
         if (m_p)
100
            free(m_p);
101
         
102
         m_p = new_p;
103
      }
104

105
      if (actual_size > desired_size)
106
         m_capacity = static_cast<uint32_t>(actual_size / element_size);
107
      else
108
         m_capacity = static_cast<uint32_t>(new_capacity);
109

110
      return true;
111
   }
112

113
#if BASISU_HASHMAP_TEST
114

115
#define HASHMAP_TEST_VERIFY(c) do { if (!(c)) handle_hashmap_test_verify_failure(__LINE__); } while(0)
116

117
   static void handle_hashmap_test_verify_failure(int line)
118
   {
119
      fprintf(stderr, "HASHMAP_TEST_VERIFY() faild on line %i\n", line);
120
      abort();
121
   }
122

123
   class counted_obj
124
   {
125
   public:
126
      counted_obj(uint32_t v = 0) :
127
         m_val(v)
128
      {
129
         m_count++;
130
      }
131

132
      counted_obj(const counted_obj& obj) :
133
         m_val(obj.m_val)
134
      {
135
         m_count++;
136
      }
137

138
      ~counted_obj()
139
      {
140
         assert(m_count > 0);
141
         m_count--;
142
      }
143

144
      static uint32_t m_count;
145

146
      uint32_t m_val;
147

148
      operator size_t() const { return m_val; }
149

150
      bool operator== (const counted_obj& rhs) const { return m_val == rhs.m_val; }
151
      bool operator== (const uint32_t rhs) const { return m_val == rhs; }
152

153
   };
154

155
   uint32_t counted_obj::m_count;
156

157
   static uint32_t urand32()
158
   {
159
      uint32_t a = rand();
160
      uint32_t b = rand() << 15;
161
      uint32_t c = rand() << (32 - 15);
162
      return a ^ b ^ c;
163
   }
164

165
   static int irand32(int l, int h)
166
   {
167
      assert(l < h);
168
      if (l >= h)
169
         return l;
170

171
      uint32_t range = static_cast<uint32_t>(h - l);
172

173
      uint32_t rnd = urand32();
174

175
      uint32_t rnd_range = static_cast<uint32_t>((((uint64_t)range) * ((uint64_t)rnd)) >> 32U);
176

177
      int result = l + rnd_range;
178
      assert((result >= l) && (result < h));
179
      return result;
180
   }
181

182
   void hash_map_test()
183
   {
184
      {
185
         basisu::hash_map<uint64_t, uint64_t> k;
186
         basisu::hash_map<uint64_t, uint64_t> l;
187
         std::swap(k, l);
188

189
         k.begin();
190
         k.end();
191
         k.clear();
192
         k.empty();
193
         k.erase(0);
194
         k.insert(0, 1);
195
         k.find(0);
196
         k.get_equals();
197
         k.get_hasher();
198
         k.get_table_size();
199
         k.reset();
200
         k.reserve(1);
201
         k = l;
202
         k.set_equals(l.get_equals());
203
         k.set_hasher(l.get_hasher());
204
         k.get_table_size();
205
      }
206

207
      uint32_t seed = 0;
208
      for (; ; )
209
      {
210
         seed++;
211

212
         typedef basisu::hash_map<counted_obj, counted_obj> my_hash_map;
213
         my_hash_map m;
214

215
         const uint32_t n = irand32(0, 100000);
216

217
         printf("%u\n", n);
218

219
         srand(seed); // r1.seed(seed);
220

221
         basisu::vector<int> q;
222

223
         uint32_t count = 0;
224
         for (uint32_t i = 0; i < n; i++)
225
         {
226
            uint32_t v = urand32() & 0x7FFFFFFF;
227
            my_hash_map::insert_result res = m.insert(counted_obj(v), counted_obj(v ^ 0xdeadbeef));
228
            if (res.second)
229
            {
230
               count++;
231
               q.push_back(v);
232
            }
233
         }
234

235
         HASHMAP_TEST_VERIFY(m.size() == count);
236

237
         srand(seed);
238

239
         my_hash_map cm(m);
240
         m.clear();
241
         m = cm;
242
         cm.reset();
243

244
         for (uint32_t i = 0; i < n; i++)
245
         {
246
            uint32_t v = urand32() & 0x7FFFFFFF;
247
            my_hash_map::const_iterator it = m.find(counted_obj(v));
248
            HASHMAP_TEST_VERIFY(it != m.end());
249
            HASHMAP_TEST_VERIFY(it->first == v);
250
            HASHMAP_TEST_VERIFY(it->second == (v ^ 0xdeadbeef));
251
         }
252

253
         for (uint32_t t = 0; t < 2; t++)
254
         {
255
            const uint32_t nd = irand32(1, q.size() + 1);
256
            for (uint32_t i = 0; i < nd; i++)
257
            {
258
               uint32_t p = irand32(0, q.size());
259

260
               int k = q[p];
261
               if (k >= 0)
262
               {
263
                  q[p] = -k - 1;
264

265
                  bool s = m.erase(counted_obj(k));
266
                  HASHMAP_TEST_VERIFY(s);
267
               }
268
            }
269

270
            typedef basisu::hash_map<uint32_t, empty_type> uint_hash_set;
271
            uint_hash_set s;
272

273
            for (uint32_t i = 0; i < q.size(); i++)
274
            {
275
               int v = q[i];
276

277
               if (v >= 0)
278
               {
279
                  my_hash_map::const_iterator it = m.find(counted_obj(v));
280
                  HASHMAP_TEST_VERIFY(it != m.end());
281
                  HASHMAP_TEST_VERIFY(it->first == (uint32_t)v);
282
                  HASHMAP_TEST_VERIFY(it->second == ((uint32_t)v ^ 0xdeadbeef));
283

284
                  s.insert(v);
285
               }
286
               else
287
               {
288
                  my_hash_map::const_iterator it = m.find(counted_obj(-v - 1));
289
                  HASHMAP_TEST_VERIFY(it == m.end());
290
               }
291
            }
292

293
            uint32_t found_count = 0;
294
            for (my_hash_map::const_iterator it = m.begin(); it != m.end(); ++it)
295
            {
296
               HASHMAP_TEST_VERIFY(it->second == ((uint32_t)it->first ^ 0xdeadbeef));
297

298
               uint_hash_set::const_iterator fit(s.find((uint32_t)it->first));
299
               HASHMAP_TEST_VERIFY(fit != s.end());
300

301
               HASHMAP_TEST_VERIFY(fit->first == it->first);
302

303
               found_count++;
304
            }
305

306
            HASHMAP_TEST_VERIFY(found_count == s.size());
307
         }
308

309
         HASHMAP_TEST_VERIFY(counted_obj::m_count == m.size() * 2);
310
      }
311
   }
312

313
#endif // BASISU_HASHMAP_TEST
314

315
} // namespace basisu
316

317
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

Product

Resources

Company
