SeExpr
immutable_hash_map.h
Go to the documentation of this file.
1/*
2 Copyright Disney Enterprises, Inc. All rights reserved.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License
6 and the following modification to it: Section 6 Trademarks.
7 deleted and replaced with:
8
9 6. Trademarks. This License does not grant permission to use the
10 trade names, trademarks, service marks, or product names of the
11 Licensor and its affiliates, except as required for reproducing
12 the content of the NOTICE file.
13
14 You may obtain a copy of the License at
15 http://www.apache.org/licenses/LICENSE-2.0
16*/
17#ifndef immutable_hash_map_h
18#define immutable_hash_map_h
19
20// a simple hash map optimized for simple, immutable data
21
22#include <inttypes.h>
23#include <math.h>
24#include <vector>
25
26template <typename key_type, typename value_type>
27class immutable_hash_map {
28 public:
29 std::vector<key_type> _keys;
30 std::vector<value_type> _values;
31 int _size;
32 int _mask;
33
34 immutable_hash_map(key_type* keys, value_type* values, int size) : _size(size) {
35 if (size <= 0) {
36 _keys.resize(1, "");
37 _values.resize(1);
38 _mask = 0;
39 return;
40 }
41
42 // build table, size = (nearest power of two >= size*2)
43 int table_size = 1 << int(ceil(log(size * 2) * (1 / M_LN2)));
44 _mask = table_size - 1;
45
46 _keys.resize(table_size);
47 _values.resize(table_size);
48
49 key_type* kp = keys, *end = kp + size;
50 value_type* vp = values;
51 while (kp != end) {
52 int pos = find(*kp);
53 _keys[pos] = *kp++;
54 _values[pos] = *vp++;
55 }
56 }
57
58 const value_type& operator[](const key_type& key) const { return _values[find(key)]; }
59
60 int size() const { return _size; }
61
62 private:
63 int find(const key_type& key) const {
64 uint32_t hash = intptr_t(key) ^ (intptr_t(key) >> 32);
65 // hash function from Thomas Wang (wang@cup.hp.com)
66 hash = ~hash + (hash << 15);
67 hash = hash ^ (hash >> 12);
68 hash = hash + (hash << 2);
69 hash = hash ^ (hash >> 4);
70 hash = hash * 2057;
71 hash = hash ^ (hash >> 16);
72 while (1) {
73 int pos = hash & _mask;
74 const key_type& k = _keys[pos];
75 if (k == key || !k) return pos; // found key or blank
76 hash++; // collision, keep looking
77 }
78 }
79};
80
81#endif
double hash(int n, double *args)