Eneboo - Documentación para desarrolladores
src/hoard/src/heaplayers/util/myhashmap.h
Ir a la documentación de este archivo.
00001 // -*- C++ -*-
00002 
00003 #ifndef _HL_MYHASHMAP_H_
00004 #define _HL_MYHASHMAP_H_
00005 
00006 #include <assert.h>
00007 #include "hash.h"
00008 
00009 namespace HL {
00010 
00011 template <typename Key,
00012           typename Value,
00013           class Allocator>
00014 class MyHashMap {
00015 
00016 public:
00017 
00018   MyHashMap (int size = INITIAL_NUM_BINS)
00019     : num_bins (size)
00020   {
00021     bins = new (alloc.malloc (sizeof(ListNodePtr) * num_bins)) ListNodePtr;
00022     for (int i = 0 ; i < num_bins; i++) {
00023       bins[i] = NULL;
00024     }
00025   }
00026 
00027   void set (Key k, Value v) {
00028     int binIndex = (unsigned int) hash(k) % num_bins;
00029     ListNode * l = bins[binIndex];
00030     while (l != NULL) {
00031       if (l->key == k) {
00032         l->value = v;
00033         return;
00034       }
00035       l = l->next;
00036     }
00037     // Didn't find it.
00038     insert (k, v);
00039   }
00040 
00041   Value get (Key k) {
00042     int binIndex = (unsigned int) hash(k) % num_bins;
00043     ListNode * l = bins[binIndex];
00044     while (l != NULL) {
00045       if (l->key == k) {
00046         return l->value;
00047       }
00048       l = l->next;
00049     }
00050     // Didn't find it.
00051     return 0;
00052   }
00053 
00054   void erase (Key k) {
00055     int binIndex = (unsigned int) hash(k) % num_bins;
00056     ListNode * curr = bins[binIndex];
00057     ListNode * prev = NULL;
00058     while (curr != NULL) {
00059       if (curr->key == k) {
00060         // Found it.
00061         if (curr != bins[binIndex]) {
00062           assert (prev->next == curr);
00063           prev->next = prev->next->next;
00064           alloc.free (curr);
00065         } else {
00066           ListNode * n = bins[binIndex]->next;
00067           alloc.free (bins[binIndex]);
00068           bins[binIndex] = n;
00069         }
00070         return;
00071       }
00072       prev = curr;
00073       curr = curr->next;
00074     }
00075   }
00076 
00077 
00078 private:
00079 
00080   void insert (Key k, Value v) {
00081     int binIndex = (unsigned int) hash(k) % num_bins;
00082     ListNode * l = new (alloc.malloc (sizeof(ListNode))) ListNode;
00083     l->key = k;
00084     l->value = v;
00085     l->next = bins[binIndex];
00086     bins[binIndex] = l;
00087   }
00088 
00089   enum { INITIAL_NUM_BINS = 511 };
00090 
00091   class ListNode {
00092   public:
00093     ListNode (void)
00094       : next (NULL)
00095     {}
00096     Key key;
00097     Value value;
00098     ListNode * next;
00099   };
00100 
00101   int num_bins;
00102 
00103   typedef ListNode * ListNodePtr;
00104   ListNodePtr * bins;
00105   Allocator alloc;
00106 };
00107 
00108 }
00109 
00110 #endif
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Enumeraciones Valores de enumeraciones Propiedades Amigas 'defines'