Rev | Line | |
---|
[176] | 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.