← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/third_party/rdestl/rdestl_hash_map.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/third_party/rdestl/rdestl_hash_map.h
1
 
// This file is covered by an MIT Copyright in the same directory.
2
 
//
3
 
// Its project home is https://code.google.com/p/rdestl/ where it
4
 
// exists as a small STL replacement.  It has been modified slightly
5
 
// by jmarantz@google.com to make it work better with normal STL:
6
 
//
7
 
// 1. references to rdp::pair has been replaced by std::pair as that
8
 
//    class is exposed at the interface.
9
 
// 2. Tabs & trailing whitespace were removed and the file re-indented by Emacs.
10
 
 
11
 
#ifndef RDESTL_HASH_MAP_H
12
 
#define RDESTL_HASH_MAP_H
13
 
 
14
 
#include <inttypes.h>  // for uintptr_t
15
 
#include <utility>  // for std::pair
16
 
#include "algorithm.h"
17
 
#include "allocator.h"
18
 
#include "functional.h"
19
 
#include "hash.h"
20
 
 
21
 
namespace rde
22
 
{
23
 
 
24
 
// TLoadFactor4 - controls hash map load. 4 means 100% load, ie. hashmap will grow
25
 
// when number of items == capacity. Default value of 6 means it grows when
26
 
// number of items == capacity * 3/2 (6/4). Higher load == tighter maps, but bigger
27
 
// risk of collisions.
28
 
template<typename TKey, typename TValue,
29
 
         class THashFunc = rde::hash<TKey>,
30
 
         int TLoadFactor4 = 6,
31
 
         class TKeyEqualFunc = rde::equal_to<TKey>,
32
 
         class TAllocator = rde::allocator>
33
 
class hash_map
34
 
{
35
 
 public:
36
 
  typedef std::pair<TKey, TValue>         value_type;
37
 
 
38
 
 private:
39
 
  struct node
40
 
  {
41
 
    static const hash_value_t kUnusedHash       = 0xFFFFFFFF;
42
 
    static const hash_value_t kDeletedHash      = 0xFFFFFFFE;
43
 
 
44
 
    node(): hash(kUnusedHash) {}
45
 
 
46
 
    RDE_FORCEINLINE bool is_unused() const  { return hash == kUnusedHash; }
47
 
    RDE_FORCEINLINE bool is_deleted() const     { return hash == kDeletedHash; }
48
 
    RDE_FORCEINLINE bool is_occupied() const { return hash < kDeletedHash; }
49
 
 
50
 
    hash_value_t    hash;
51
 
    value_type      data;
52
 
  };
53
 
  template<typename TNodePtr, typename TPtr, typename TRef>
54
 
  class node_iterator
55
 
  {
56
 
    friend class hash_map;
57
 
   public:
58
 
    typedef forward_iterator_tag    iterator_category;
59
 
 
60
 
    explicit node_iterator(TNodePtr node, const hash_map* map)
61
 
        : m_node(node),
62
 
                m_map(map)
63
 
    {/**/}
64
 
    template<typename UNodePtr, typename UPtr, typename URef>
65
 
    node_iterator(const node_iterator<UNodePtr, UPtr, URef>& rhs)
66
 
        : m_node(rhs.node()),
67
 
                m_map(rhs.get_map())
68
 
    {/**/}
69
 
 
70
 
    TRef operator*() const
71
 
    {
72
 
      RDE_ASSERT(m_node != 0);
73
 
      return m_node->data;
74
 
    }
75
 
    TPtr operator->() const
76
 
    {
77
 
      return &m_node->data;
78
 
    }
79
 
    RDE_FORCEINLINE TNodePtr node() const
80
 
    {
81
 
      return m_node;
82
 
    }
83
 
 
84
 
    node_iterator& operator++()
85
 
    {
86
 
      RDE_ASSERT(m_node != 0);
87
 
      ++m_node;
88
 
      move_to_next_occupied_node();
89
 
      return *this;
90
 
    }
91
 
    node_iterator operator++(int)
92
 
    {
93
 
      node_iterator copy(*this);
94
 
      ++(*this);
95
 
      return copy;
96
 
    }
97
 
 
98
 
    RDE_FORCEINLINE bool operator==(const node_iterator& rhs) const
99
 
    {
100
 
      return rhs.m_node == m_node;
101
 
    }
102
 
    bool operator!=(const node_iterator& rhs) const
103
 
    {
104
 
      return !(rhs == *this);
105
 
    }
106
 
 
107
 
    const hash_map* get_map() const { return m_map; }
108
 
   private:
109
 
    void move_to_next_occupied_node()
110
 
    {
111
 
      // @todo: save nodeEnd in constructor?
112
 
      TNodePtr nodeEnd = m_map->m_nodes + m_map->bucket_count();
113
 
      for (/**/; m_node < nodeEnd; ++m_node)
114
 
      {
115
 
        if (m_node->is_occupied())
116
 
          break;
117
 
      }
118
 
    }
119
 
    TNodePtr  m_node;
120
 
    const hash_map* m_map;
121
 
  };
122
 
 
123
 
 public:
124
 
  typedef TKey                key_type;
125
 
  typedef TValue                mapped_type;
126
 
  typedef TAllocator               allocator_type;
127
 
  typedef node_iterator<node*, value_type*, value_type&>      iterator;
128
 
  typedef node_iterator<const node*, const value_type*, const value_type&> const_iterator;
129
 
  typedef int                 size_type;
130
 
  static const size_type              kNodeSize = sizeof(node);
131
 
  static const size_type              kInitialCapacity = 64;
132
 
 
133
 
  hash_map()
134
 
      : m_nodes(&ms_emptyNode),
135
 
        m_size(0),
136
 
        m_capacity(0),
137
 
        m_capacityMask(0),
138
 
        m_numUsed(0)
139
 
  {
140
 
    RDE_ASSERT((kInitialCapacity & (kInitialCapacity - 1)) == 0); // Must be power-of-two
141
 
  }
142
 
  explicit hash_map(const allocator_type& allocator)
143
 
      : m_nodes(&ms_emptyNode),
144
 
        m_size(0),
145
 
        m_capacity(0),
146
 
        m_capacityMask(0),
147
 
        m_numUsed(0),
148
 
        m_allocator(allocator)
149
 
  {
150
 
    /**/
151
 
  }
152
 
  explicit hash_map(size_type initial_bucket_count,
153
 
                    const allocator_type& allocator = allocator_type())
154
 
      : m_nodes(&ms_emptyNode),
155
 
        m_size(0),
156
 
        m_capacity(0),
157
 
        m_capacityMask(0),
158
 
        m_numUsed(0),
159
 
        m_allocator(allocator)
160
 
  {
161
 
    reserve(initial_bucket_count);
162
 
  }
163
 
  hash_map(size_type initial_bucket_count,
164
 
           const THashFunc& hashFunc,
165
 
           const allocator_type& allocator = allocator_type())
166
 
      : m_nodes(&ms_emptyNode),
167
 
        m_size(0),
168
 
        m_capacity(0),
169
 
        m_capacityMask(0),
170
 
        m_numUsed(0),
171
 
        m_hashFunc(hashFunc),
172
 
        m_allocator(allocator)
173
 
  {
174
 
    reserve(initial_bucket_count);
175
 
  }
176
 
  hash_map(const hash_map& rhs, const allocator_type& allocator = allocator_type())
177
 
      : m_nodes(&ms_emptyNode),
178
 
        m_size(0),
179
 
        m_capacity(0),
180
 
        m_capacityMask(0),
181
 
        m_numUsed(0),
182
 
        m_allocator(allocator)
183
 
  {
184
 
    *this = rhs;
185
 
  }
186
 
  explicit hash_map(e_noinitialize)
187
 
  {
188
 
    /**/
189
 
  }
190
 
  ~hash_map()
191
 
  {
192
 
    delete_nodes();
193
 
  }
194
 
 
195
 
  iterator begin()
196
 
  {
197
 
    iterator it(m_nodes, this);
198
 
    it.move_to_next_occupied_node();
199
 
    return it;
200
 
  }
201
 
  const_iterator begin() const
202
 
  {
203
 
    const_iterator it(m_nodes, this);
204
 
    it.move_to_next_occupied_node();
205
 
    return it;
206
 
  }
207
 
  iterator end()              { return iterator(m_nodes + m_capacity, this); }
208
 
  const_iterator end() const { return const_iterator(m_nodes + m_capacity, this); }
209
 
 
210
 
  // @note: Added for compatiblity sake.
211
 
  //   Personally, I consider it "risky". Use find/insert for more
212
 
  //   explicit operations.
213
 
  mapped_type& operator[](const key_type& key)
214
 
  {
215
 
    hash_value_t hash;
216
 
    node* n = find_for_insert(key, &hash);
217
 
    if (n == 0 || !n->is_occupied())
218
 
    {
219
 
      return insert_at(value_type(key, TValue()), n, hash).first->second;
220
 
    }
221
 
    return n->data.second;
222
 
  }
223
 
  // @note: Doesn't copy allocator.
224
 
  hash_map& operator=(const hash_map& rhs)
225
 
  {
226
 
    RDE_ASSERT(invariant());
227
 
    if (&rhs != this)
228
 
    {
229
 
      clear();
230
 
      if (m_capacity < rhs.bucket_count())
231
 
      {
232
 
        delete_nodes();
233
 
        m_nodes = allocate_nodes(rhs.bucket_count());
234
 
        m_capacity = rhs.bucket_count();
235
 
        m_capacityMask = m_capacity - 1;
236
 
      }
237
 
      rehash(m_capacity, m_nodes, rhs.m_capacity, rhs.m_nodes, false);
238
 
      m_size = rhs.size();
239
 
      m_numUsed = rhs.m_numUsed;
240
 
    }
241
 
    RDE_ASSERT(invariant());
242
 
    return *this;
243
 
  }
244
 
  void swap(hash_map& rhs)
245
 
  {
246
 
    if (&rhs != this)
247
 
    {
248
 
      RDE_ASSERT(invariant());
249
 
      RDE_ASSERT(m_allocator == rhs.m_allocator);
250
 
      rde::swap(m_nodes, rhs.m_nodes);
251
 
      rde::swap(m_size, rhs.m_size);
252
 
      rde::swap(m_capacity, rhs.m_capacity);
253
 
      rde::swap(m_capacityMask, rhs.m_capacityMask);
254
 
      rde::swap(m_numUsed, rhs.m_numUsed);
255
 
      rde::swap(m_hashFunc, rhs.m_hashFunc);
256
 
      rde::swap(m_keyEqualFunc, rhs.m_keyEqualFunc);
257
 
      RDE_ASSERT(invariant());
258
 
    }
259
 
  }
260
 
 
261
 
  std::pair<iterator, bool> insert(const value_type& v)
262
 
  {
263
 
    typedef std::pair<iterator, bool> ret_type_t;
264
 
    RDE_ASSERT(invariant());
265
 
    if (m_numUsed * TLoadFactor4 >= m_capacity * 4)
266
 
      grow();
267
 
 
268
 
    hash_value_t hash = 0;
269
 
    node* n = find_for_insert(v.first, &hash);
270
 
    if (n->is_occupied())
271
 
    {
272
 
      RDE_ASSERT(hash == n->hash && m_keyEqualFunc(v.first, n->data.first));
273
 
      return ret_type_t(iterator(n, this), false);
274
 
    }
275
 
    if (n->is_unused())
276
 
      ++m_numUsed;
277
 
    rde::copy_construct(&n->data, v);
278
 
    n->hash = hash;
279
 
    ++m_size;
280
 
    RDE_ASSERT(invariant());
281
 
    return ret_type_t(iterator(n, this), true);
282
 
  }
283
 
 
284
 
  size_type erase(const key_type& key)
285
 
  {
286
 
    node* n = lookup(key);
287
 
    if (n != (m_nodes + m_capacity) && n->is_occupied())
288
 
    {
289
 
      erase_node(n);
290
 
      return 1;
291
 
    }
292
 
    return 0;
293
 
  }
294
 
  void erase(iterator it)
295
 
  {
296
 
    RDE_ASSERT(it.get_map() == this);
297
 
    if (it != end())
298
 
    {
299
 
      RDE_ASSERT(!empty());
300
 
      erase_node(it.node());
301
 
    }
302
 
  }
303
 
  void erase(iterator from, iterator to)
304
 
  {
305
 
    for (/**/; from != to; ++from)
306
 
    {
307
 
      node* n = from.node();
308
 
      if (n->is_occupied())
309
 
        erase_node(n);
310
 
    }
311
 
  }
312
 
 
313
 
  iterator find(const key_type& key)
314
 
  {
315
 
    node* n = lookup(key);
316
 
    return iterator(n, this);
317
 
  }
318
 
  const_iterator find(const key_type& key) const
319
 
  {
320
 
    const node* n = lookup(key);
321
 
    return const_iterator(n, this);
322
 
  }
323
 
 
324
 
  void clear()
325
 
  {
326
 
    node* endNode = m_nodes + m_capacity;
327
 
    for (node* iter = m_nodes; iter != endNode; ++iter)
328
 
    {
329
 
      if( iter )
330
 
      {
331
 
        if (iter->is_occupied())
332
 
        {
333
 
          rde::destruct(&iter->data);
334
 
        }
335
 
        // We can make them unused, because we clear whole hash_map,
336
 
        // so we can guarantee there'll be no holes.
337
 
        iter->hash = node::kUnusedHash;
338
 
      }
339
 
    }
340
 
    m_size = 0;
341
 
    m_numUsed = 0;
342
 
  }
343
 
 
344
 
  void reserve(size_type min_size)
345
 
  {
346
 
    size_type newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity);
347
 
    while (newCapacity < min_size)
348
 
      newCapacity *= 2;
349
 
    if (newCapacity > m_capacity)
350
 
      grow(newCapacity);
351
 
  }
352
 
 
353
 
  size_type bucket_count() const   { return m_capacity; }
354
 
  size_type size() const     { return m_size; }
355
 
  size_type empty() const     { return size() == 0; }
356
 
  size_type nonempty_bucket_count() const { return m_numUsed; }
357
 
  size_type used_memory() const
358
 
  {
359
 
    return bucket_count() * kNodeSize;
360
 
  }
361
 
 
362
 
  const allocator_type& get_allocator() const { return m_allocator; }
363
 
  void set_allocator(const allocator_type& allocator)
364
 
  {
365
 
    m_allocator = allocator;
366
 
  }
367
 
 
368
 
 private:
369
 
  void grow()
370
 
  {
371
 
    const int newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity * 2);
372
 
    grow(newCapacity);
373
 
  }
374
 
  void grow(int new_capacity)
375
 
  {
376
 
    RDE_ASSERT((new_capacity & (new_capacity - 1)) == 0); // Must be power-of-two
377
 
    node* newNodes = allocate_nodes(new_capacity);
378
 
    rehash(new_capacity, newNodes, m_capacity, m_nodes, true);
379
 
    if (m_nodes != &ms_emptyNode)
380
 
      m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);
381
 
    m_capacity = new_capacity;
382
 
    m_capacityMask = new_capacity - 1;
383
 
    m_nodes = newNodes;
384
 
    m_numUsed = m_size;
385
 
    RDE_ASSERT(m_numUsed < m_capacity);
386
 
  }
387
 
  std::pair<iterator, bool> insert_at(const value_type& v, node* n,
388
 
                                      hash_value_t hash)
389
 
  {
390
 
    RDE_ASSERT(invariant());
391
 
    if (n == 0 || m_numUsed * TLoadFactor4 >= m_capacity * 4)
392
 
      return insert(v);
393
 
 
394
 
    RDE_ASSERT(!n->is_occupied());
395
 
    if (n->is_unused())
396
 
      ++m_numUsed;
397
 
    rde::copy_construct(&n->data, v);
398
 
    n->hash = hash;
399
 
    ++m_size;
400
 
    RDE_ASSERT(invariant());
401
 
    return std::pair<iterator, bool>(iterator(n, this), true);
402
 
  }
403
 
  node* find_for_insert(const key_type& key, hash_value_t* out_hash)
404
 
  {
405
 
    if (m_capacity == 0)
406
 
      return 0;
407
 
 
408
 
    const hash_value_t hash = hash_func(key);
409
 
    *out_hash = hash;
410
 
    uint32 i = hash & m_capacityMask;
411
 
 
412
 
    node* n = m_nodes + i;
413
 
    if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
414
 
      return n;
415
 
 
416
 
    node* freeNode(0);
417
 
    if (n->is_deleted())
418
 
      freeNode = n;
419
 
    uint32 numProbes(0);
420
 
    // Guarantees loop termination.
421
 
    RDE_ASSERT(m_numUsed < m_capacity);
422
 
    while (!n->is_unused())
423
 
    {
424
 
      ++numProbes;
425
 
      i = (i + numProbes) & m_capacityMask;
426
 
      n = m_nodes + i;
427
 
      if (compare_key(n, key, hash))
428
 
        return n;
429
 
      if (n->is_deleted() && freeNode == 0)
430
 
        freeNode = n;
431
 
    }
432
 
    return freeNode ? freeNode : n;
433
 
  }
434
 
  node* lookup(const key_type& key) const
435
 
  {
436
 
    const hash_value_t hash = hash_func(key);
437
 
    uint32 i = hash & m_capacityMask;
438
 
    node* n = m_nodes + i;
439
 
    if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
440
 
      return n;
441
 
 
442
 
    uint32 numProbes(0);
443
 
    // Guarantees loop termination.
444
 
    RDE_ASSERT(m_capacity == 0 || m_numUsed < m_capacity);
445
 
    while (!n->is_unused())
446
 
    {
447
 
      ++numProbes;
448
 
      i = (i + numProbes) & m_capacityMask;
449
 
      n = m_nodes + i;
450
 
 
451
 
      if (compare_key(n, key, hash))
452
 
        return n;
453
 
    }
454
 
    return m_nodes + m_capacity;
455
 
  }
456
 
 
457
 
  static void rehash(int new_capacity, node* new_nodes,
458
 
                     int capacity, const node* nodes, bool destruct_original)
459
 
  {
460
 
    //if (nodes == &ms_emptyNode || new_nodes == &ms_emptyNode)
461
 
    //  return;
462
 
 
463
 
    const node* it = nodes;
464
 
    const node* itEnd = nodes + capacity;
465
 
    const uint32 mask = new_capacity - 1;
466
 
    while (it != itEnd)
467
 
    {
468
 
      if (it->is_occupied())
469
 
      {
470
 
        const hash_value_t hash = it->hash;
471
 
        uint32 i = hash & mask;
472
 
 
473
 
        node* n = new_nodes + i;
474
 
        uint32 numProbes(0);
475
 
        while (!n->is_unused())
476
 
        {
477
 
          ++numProbes;
478
 
          i = (i + numProbes) & mask;
479
 
          n = new_nodes + i;
480
 
        }
481
 
        rde::copy_construct(&n->data, it->data);
482
 
        n->hash = hash;
483
 
        if (destruct_original)
484
 
          rde::destruct(&it->data);
485
 
      }
486
 
      ++it;
487
 
    }
488
 
  }
489
 
 
490
 
  node* allocate_nodes(int n)
491
 
  {
492
 
    node* buckets = static_cast<node*>(m_allocator.allocate(n * sizeof(node)));
493
 
    node* iterBuckets(buckets);
494
 
    node* end = iterBuckets + n;
495
 
    for (/**/; iterBuckets != end; ++iterBuckets)
496
 
      iterBuckets->hash = node::kUnusedHash;
497
 
 
498
 
    return buckets;
499
 
  }
500
 
  void delete_nodes()
501
 
  {
502
 
    node* it = m_nodes;
503
 
    node* itEnd = it + m_capacity;
504
 
    while (it != itEnd)
505
 
    {
506
 
      if (it && it->is_occupied())
507
 
        rde::destruct(&it->data);
508
 
      ++it;
509
 
    }
510
 
    if (m_nodes != &ms_emptyNode)
511
 
      m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);
512
 
 
513
 
    m_capacity = 0;
514
 
    m_capacityMask = 0;
515
 
    m_size = 0;
516
 
  }
517
 
  void erase_node(node* n)
518
 
  {
519
 
    RDE_ASSERT(!empty());
520
 
    RDE_ASSERT(n->is_occupied());
521
 
    rde::destruct(&n->data);
522
 
    n->hash = node::kDeletedHash;
523
 
    --m_size;
524
 
  }
525
 
 
526
 
  RDE_FORCEINLINE hash_value_t hash_func(const key_type& key) const
527
 
  {
528
 
    const hash_value_t h = m_hashFunc(key) & 0xFFFFFFFD;
529
 
    //RDE_ASSERT(h < node::kDeletedHash);
530
 
    return h;
531
 
  }
532
 
  bool invariant() const
533
 
  {
534
 
    RDE_ASSERT((m_capacity & (m_capacity - 1)) == 0);
535
 
    RDE_ASSERT(m_numUsed >= m_size);
536
 
    return true;
537
 
  }
538
 
 
539
 
  RDE_FORCEINLINE bool compare_key(const node* n, const key_type& key, hash_value_t hash) const
540
 
  {
541
 
    return (n->hash == hash && m_keyEqualFunc(key, n->data.first));
542
 
  }
543
 
 
544
 
  node*   m_nodes;
545
 
  int    m_size;
546
 
  int    m_capacity;
547
 
  uint32   m_capacityMask;
548
 
  int    m_numUsed;
549
 
  THashFunc       m_hashFunc;
550
 
  TKeyEqualFunc m_keyEqualFunc;
551
 
  TAllocator      m_allocator;
552
 
 
553
 
  static node  ms_emptyNode;
554
 
};
555
 
 
556
 
 
557
 
// Holy ...
558
 
template<typename TKey, typename TValue,
559
 
         class THashFunc,
560
 
         int TLoadFactor4,
561
 
         class TKeyEqualFunc,
562
 
         class TAllocator>
563
 
typename hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::node hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::ms_emptyNode;
564
 
 
565
 
}
566
 
 
567
 
#endif