1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_PLATFORM_HASHMAP_H_
6#define RUNTIME_PLATFORM_HASHMAP_H_
7
8#include "platform/globals.h"
9
10namespace dart {
11
12class SimpleHashMap {
13 public:
14 typedef bool (*MatchFun)(void* key1, void* key2);
15
16 typedef void (*ClearFun)(void* value);
17
18 // initial_capacity is the size of the initial hash map;
19 // it must be a power of 2 (and thus must not be 0).
20 SimpleHashMap(MatchFun match, uint32_t initial_capacity);
21
22 ~SimpleHashMap();
23
24 static bool SamePointerValue(void* key1, void* key2) { return key1 == key2; }
25
26 static uint32_t StringHash(char* key) {
27 uint32_t hash_ = 0;
28 if (key == NULL) return hash_;
29 int len = strlen(key);
30 for (int i = 0; i < len; i++) {
31 hash_ += key[i];
32 hash_ += hash_ << 10;
33 hash_ ^= hash_ >> 6;
34 }
35 hash_ += hash_ << 3;
36 hash_ ^= hash_ >> 11;
37 hash_ += hash_ << 15;
38 return hash_ == 0 ? 1 : hash_;
39 }
40
41 static bool SameStringValue(void* key1, void* key2) {
42 return strcmp(reinterpret_cast<char*>(key1),
43 reinterpret_cast<char*>(key2)) == 0;
44 }
45
46 // SimpleHashMap entries are (key, value, hash) triplets.
47 // Some clients may not need to use the value slot
48 // (e.g. implementers of sets, where the key is the value).
49 struct Entry {
50 Entry() : key(NULL), value(NULL), hash(0) {}
51 void* key;
52 void* value;
53 uint32_t hash; // The full hash value for key.
54 };
55
56 // If an entry with matching key is found, Lookup()
57 // returns that entry. If no matching entry is found,
58 // but insert is set, a new entry is inserted with
59 // corresponding key, key hash, and NULL value.
60 // Otherwise, NULL is returned.
61 Entry* Lookup(void* key, uint32_t hash, bool insert);
62
63 // Removes the entry with matching key.
64 //
65 // WARNING: This method cannot be called while iterating a `SimpleHashMap`
66 // otherwise the iteration might step over elements!
67 void Remove(void* key, uint32_t hash);
68
69 // Empties the hash map (occupancy() == 0), and calls the function 'clear' on
70 // each of the values if given.
71 void Clear(ClearFun clear = NULL);
72
73 // The number of entries stored in the table.
74 intptr_t size() const { return occupancy_; }
75
76 // The capacity of the table. The implementation
77 // makes sure that occupancy is at most 80% of
78 // the table capacity.
79 intptr_t capacity() const { return capacity_; }
80
81 // Iteration
82 //
83 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
84 // ...
85 // }
86 //
87 // If entries are inserted during iteration, the effect of
88 // calling Next() is undefined.
89 Entry* Start() const;
90 Entry* Next(Entry* p) const;
91
92 private:
93 MatchFun match_;
94 Entry* map_;
95 uint32_t capacity_;
96 uint32_t occupancy_;
97
98 Entry* map_end() const { return map_ + capacity_; }
99 Entry* Probe(void* key, uint32_t hash);
100 void Initialize(uint32_t capacity);
101 void Resize();
102
103 friend class IntSet; // From hashmap_test.cc
104 DISALLOW_COPY_AND_ASSIGN(SimpleHashMap);
105};
106
107} // namespace dart
108
109#endif // RUNTIME_PLATFORM_HASHMAP_H_
110