Line | |
---|
1 | // -*- C++ -*- |
---|
2 | |
---|
3 | #ifndef _HL_MYHASHMAP_H_ |
---|
4 | #define _HL_MYHASHMAP_H_ |
---|
5 | |
---|
6 | #include <assert.h> |
---|
7 | #include "hash.h" |
---|
8 | |
---|
9 | namespace HL { |
---|
10 | |
---|
11 | template <typename Key, |
---|
12 | typename Value, |
---|
13 | class Allocator> |
---|
14 | class MyHashMap { |
---|
15 | |
---|
16 | public: |
---|
17 | |
---|
18 | MyHashMap (int size = INITIAL_NUM_BINS) |
---|
19 | : num_bins (size) |
---|
20 | { |
---|
21 | bins = new (alloc.malloc (sizeof(ListNodePtr) * num_bins)) ListNodePtr; |
---|
22 | for (int i = 0 ; i < num_bins; i++) { |
---|
23 | bins[i] = NULL; |
---|
24 | } |
---|
25 | } |
---|
26 | |
---|
27 | void set (Key k, Value v) { |
---|
28 | int binIndex = (unsigned int) hash(k) % num_bins; |
---|
29 | ListNode * l = bins[binIndex]; |
---|
30 | while (l != NULL) { |
---|
31 | if (l->key == k) { |
---|
32 | l->value = v; |
---|
33 | return; |
---|
34 | } |
---|
35 | l = l->next; |
---|
36 | } |
---|
37 | // Didn't find it. |
---|
38 | insert (k, v); |
---|
39 | } |
---|
40 | |
---|
41 | Value get (Key k) { |
---|
42 | int binIndex = (unsigned int) hash(k) % num_bins; |
---|
43 | ListNode * l = bins[binIndex]; |
---|
44 | while (l != NULL) { |
---|
45 | if (l->key == k) { |
---|
46 | return l->value; |
---|
47 | } |
---|
48 | l = l->next; |
---|
49 | } |
---|
50 | // Didn't find it. |
---|
51 | return 0; |
---|
52 | } |
---|
53 | |
---|
54 | void erase (Key k) { |
---|
55 | int binIndex = (unsigned int) hash(k) % num_bins; |
---|
56 | ListNode * curr = bins[binIndex]; |
---|
57 | ListNode * prev = NULL; |
---|
58 | while (curr != NULL) { |
---|
59 | if (curr->key == k) { |
---|
60 | // Found it. |
---|
61 | if (curr != bins[binIndex]) { |
---|
62 | assert (prev->next == curr); |
---|
63 | prev->next = prev->next->next; |
---|
64 | alloc.free (curr); |
---|
65 | } else { |
---|
66 | ListNode * n = bins[binIndex]->next; |
---|
67 | alloc.free (bins[binIndex]); |
---|
68 | bins[binIndex] = n; |
---|
69 | } |
---|
70 | return; |
---|
71 | } |
---|
72 | prev = curr; |
---|
73 | curr = curr->next; |
---|
74 | } |
---|
75 | } |
---|
76 | |
---|
77 | |
---|
78 | private: |
---|
79 | |
---|
80 | void insert (Key k, Value v) { |
---|
81 | int binIndex = (unsigned int) hash(k) % num_bins; |
---|
82 | ListNode * l = new (alloc.malloc (sizeof(ListNode))) ListNode; |
---|
83 | l->key = k; |
---|
84 | l->value = v; |
---|
85 | l->next = bins[binIndex]; |
---|
86 | bins[binIndex] = l; |
---|
87 | } |
---|
88 | |
---|
89 | enum { INITIAL_NUM_BINS = 511 }; |
---|
90 | |
---|
91 | class ListNode { |
---|
92 | public: |
---|
93 | ListNode (void) |
---|
94 | : next (NULL) |
---|
95 | {} |
---|
96 | Key key; |
---|
97 | Value value; |
---|
98 | ListNode * next; |
---|
99 | }; |
---|
100 | |
---|
101 | int num_bins; |
---|
102 | |
---|
103 | typedef ListNode * ListNodePtr; |
---|
104 | ListNodePtr * bins; |
---|
105 | Allocator alloc; |
---|
106 | }; |
---|
107 | |
---|
108 | }; |
---|
109 | |
---|
110 | #endif |
---|
Note: See
TracBrowser
for help on using the repository browser.