hashmap의 간단한 실현
//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;
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.