hashmap의 간단한 실현

13473 단어
//template 
// id 
struct HashNode {
    int id;
    void* obj;
    struct list_head list_item;
}

struct list_head {
    list_head* prev;
    list_head* next;
}
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while (0)
#define list_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_safe(pos, n, head) for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
static inline void list_add(struct list_head *p,
                              struct list_head *prev,
                              struct list_head *next)
{
    next->prev = p;
    p->next = next;
    p->prev = prev;
    prev->next = p;
}
static inline void list_add_in(struct list_head *p, struct list_head *head)
{
    list_add(p, head, head->next);
}
static inline void list_add_tail(struct list_head *p, struct list_head *head)
{
    list_add(p, head->prev, head);
}
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = 0;
    entry->prev = 0;
}


#ifndef offsetof
#if __GNUC__ >= 4

#define offsetof(type, member)  __builtin_offsetof (type, member);printf("this is gcc > 4
"); #else #define offsetof(type, member) (unsigned long)(&((type *)0)->member);printf("this is gcc < 4
"); #endif #endif #define list_entry(ptr, type, member) ((type *)((char *)(ptr)-offsetof(type, member))) class CHashMap { private: struct HashNode* hash_table; int hash_table_size; public: CHashMap(); ~CHashMap(); int CreateMap(int map_size); int AddMapObj(int id, void* obj); int DelMapObj(int id); void* GetMapObj(int id); int ClearMap(); } CHashMap() { hash_table = NULL; hash_table_size = 0; } ~CHashMap() { if (hash_table) { ClearMap(); } hash_table_size = 0; } int CreateMap(int map_size) { try { hash_table = new HashNode[map_size]; } catch(&bad_alloc) { return -1; } // hash for (int i = 0; i < map_size; i++) { hash_table[i].id = 0; hash_table[i].obj = NULL; INIT_LIST_HEAD(&hash_table[i].list_item); } hash_table_size = map_size; return 0; } int AddMapObj(int id, void* obj) { int bucket_id = id%hash_table_size; HashNode* temp = new struct HashNode(); temp->id = id; temp->obj = obj; list_add_tail(&temp->list_item, &hash_table[bucket_id].list_item); return 0; } int DelMapObj(int id) { int bucket_id = id%hash_table_size; struct list_head* temp1; struct list_head* temp2; struct list_head* head = &hash_table[bucket_id].list_item; struct HashNode* node; list_for_each_safe(temp1, temp2, head) { node = list_entry(temp1, struct HashNode, list_item); if (node->id == id) { list_del(temp1); delete node; return 0; } } return -1; } void* GetMapObj(int id) { int bucket_id = id%hash_table_size; struct list_head* head = &hash_table[bucket_id].list_item; struct list_head* temp ; struct HashNode* node; list_for_each(temp, head) { node = list_entry(temp, struct HashNode, list_item); if (node->id == id) { return node->obj; } } return NULL; } int ClearMap() { struct list_head* _head; struct list_head* _tmp1; struct list_head* _tmp2; struct OBJECTMAP* item; for( int i=0; i ) { _head = &hash_table[i].list_item; //head , list_for_each_safe(_tmp1,_tmp2,_head) { item = list_entry(_tmp1,struct OBJECTMAP,list_item); list_del(_tmp1); delete item; } } delete[] hash_table; hash_table = NULL; hash_table_size = 0; return 0; }

 
template
struct HashListNode
{
    NodeType obj;
    struct list_head list_item;
};
template
int idx =  Traits::GetNodeID(obj)% hash_table_size;

좋은 웹페이지 즐겨찾기