c语言实现带LRU机制的哈希表
2024-09-27 19:35:26
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #define HASH_BUCKET_MAX (1024)
#define HASH_BUCKET_CAPACITY_MAX (256)
#define HASHTABLE_DEBUG
#define TRUE 1
#define FALSE 0 #ifdef HASHTABLE_DEBUG
#define DEBUG(format, ...) printf("[%s] [%d] : "format"\n", __FUNCTION__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(format, ...)
#endif struct hash_bucket {
int capacity; /* 桶的容量 */
void *hkey; /* hashtable的key */
void *hdata; /* hashtable的data */
struct hash_bucket *prev;
struct hash_bucket *next;
struct hash_bucket *tail;
}; struct hash {
uint32_t (*hash_key)(void *);
int (*hash_cmp)(const void *, const void*, int len);
struct hash_bucket* bucket[HASH_BUCKET_MAX];
}; uint32_t string_hash_key(void* str);
int string_hash_cmp(const void* src, const void* dst); static struct hash *g_htable = NULL; void hash_create();
void *hash_lookup(void *key);
int hash_add(void *key, void* data);
int hash_delete(void *key);
void hash_destroy();
void hash_iter_print(); #define bucket_free(bucket) \
free(bucket->hkey); \
free(bucket->hdata); \
free(bucket); \
bucket = NULL; uint32_t string_hash_key(void* str) {
char *tmp = (char *)str;
uint32_t key = ;
while(*tmp)
key = (key * ) ^ (uint32_t)(tmp++); DEBUG("string key : %u, index : %d", key, key%HASH_BUCKET_MAX); return key%HASH_BUCKET_MAX;
} int string_hash_cmp(const void* src, const void* dst, int len) {
if (!src || !dst) {
DEBUG("src addr: %p, dst addr: %p", src, dst);
return -;
}
return strncmp((char *)src, (char *)dst, len);
} void hash_create() {
if (g_htable) {
DEBUG("the default hashtable is already created");
return;
} g_htable = (struct hash *)malloc(sizeof(struct hash));
if (!g_htable) {
DEBUG("memory alloc failed.");
return;
} memset(g_htable, , sizeof(struct hash)); g_htable->hash_key = string_hash_key;
g_htable->hash_cmp = string_hash_cmp; return;
} static void bucket_delete(struct hash_bucket** ptr) {
struct hash_bucket *bucket = *ptr;
struct hash_bucket *tmp; while(bucket) {
tmp = bucket;
bucket = bucket->next;
bucket_free(tmp);
}
} void hash_destroy() {
if (g_htable) {
for(int i=; i<HASH_BUCKET_MAX; i++) {
if (g_htable->bucket[i]) {
bucket_delete(&g_htable->bucket[i]);
}
} free(g_htable);
g_htable = NULL;
}
return;
} #define lru_bucket_move(bucket, head) \
bucket->next = head; \
bucket->prev = NULL; \
bucket->capacity = head->capacity; \
\
head->prev = bucket; \
head->tail = NULL; void *hash_lookup(void *key) {
if (!key) {
DEBUG("input para is NULL\n");
return NULL;
} uint32_t index = g_htable->hash_key(key);
struct hash_bucket* head = g_htable->bucket[index];
struct hash_bucket* bucket = head; while(bucket) {
if ( == g_htable->hash_cmp(key, bucket->hkey, strlen((char*)key))) {
if (head != bucket && bucket != head->tail) {
bucket->prev->next = bucket->next;
bucket->next->prev = bucket->prev;
bucket->tail = head->tail; lru_bucket_move(bucket, head);
} else if (bucket == head->tail && head->capacity>) {
bucket->prev->next = NULL;
bucket->tail = bucket->prev; lru_bucket_move(bucket, head);
}
g_htable->bucket[index] = bucket;
return bucket->hdata;
}
bucket = bucket->next;
}
return NULL;
} int hash_add(void *key, void* data) {
if (!key || !data) {
DEBUG("input para is NULL\n");
return FALSE;
} uint32_t index = g_htable->hash_key(key);
struct hash_bucket* head = g_htable->bucket[index]; if (!head) {
head = (struct hash_bucket*)malloc(sizeof(struct hash_bucket));
if (!head) {
DEBUG("no memory for more hash_bucket\n");
return FALSE;
} memset(head, , sizeof(*head));
head->capacity++; head->hkey = strdup((char *)key);
head->hdata = strdup((char *)data);
head->tail = head;
g_htable->bucket[index] = head;
return TRUE;
} int capacity = head->capacity;
struct hash_bucket *new_bucket =
(struct hash_bucket *)malloc(sizeof(struct hash_bucket)); if (!new_bucket) {
DEBUG("no memory for more hash_bucket\n");
return FALSE;
} if (capacity >= HASH_BUCKET_CAPACITY_MAX) {
struct hash_bucket *tail = head->tail;
head->tail = tail->prev; tail->prev->next = NULL;
bucket_free(tail);
} head->prev = new_bucket;
new_bucket->next = head;
new_bucket->capacity = capacity + ;
new_bucket->tail = head->tail;
head->tail = NULL; head->hkey = strdup((char *)key);
head->hdata = strdup((char *)data); g_htable->bucket[index] = new_bucket; return TRUE;
} int hash_delete(void *key) {
if (!key) {
DEBUG("input para is NULL\n");
return FALSE;
} uint32_t index = g_htable->hash_key(key);
struct hash_bucket* head = g_htable->bucket[index];
struct hash_bucket* bkt = head; while(bkt) {
if ( == g_htable->hash_cmp(key, bkt->hkey, strlen((char*)key))) {
if (head != bkt && bkt != head->tail) {
bkt->prev->next = bkt->next;
bkt->next->prev = bkt->prev; } else if (bkt == head->tail && head->capacity>) {
bkt->prev->next = NULL;
bkt->tail = bkt->prev; } else {
if (bkt->next) {
bkt->next->tail = bkt->tail;
bkt->next->capacity = bkt->capacity;
bkt->next->prev = NULL;
g_htable->bucket[index] = bkt->next;
} else {
g_htable->bucket[index] = NULL;
}
} bucket_free(bkt);
if (g_htable->bucket[index]) {
g_htable->bucket[index]->capacity--;
} return TRUE;
}
bkt = bkt->next;
}
return FALSE;
} static void bucket_print(struct hash_bucket** ptr) {
struct hash_bucket *bkt = *ptr;
struct hash_bucket *tmp; while(bkt) {
printf("key=[%s],data=[%s]\n", (char*)bkt->hkey, (char*)bkt->hdata);
bkt = bkt->next;
}
} void hash_iter_print() {
if (g_htable) {
for(int i=; i<HASH_BUCKET_MAX; i++) {
if (g_htable->bucket[i]) {
bucket_print(&g_htable->bucket[i]);
}
}
}
} int main(int argc, char* argv[]) {
hash_create(); hash_add("first", "danxi");
hash_add("second", "test");
hash_add("three", "sad code");
hash_add("four", "let's go"); hash_iter_print(); char * t1 = (char *)hash_lookup("first");
char * t2 = (char *)hash_lookup("second"); printf("%s %s \n", t1, t2);
printf("%s \n", (char*)hash_lookup("four")); hash_delete("four");
hash_iter_print();
hash_destroy(); return ;
}
最新文章
- 4. ValueStack 和 OGNL
- touch事件中的touches、targetTouches和changedTouches详解
- linux系统安装软件方法大全
- android前端开发 布局学习
- 如何限制textarea文本框的输入字数
- PHP程序员最常犯的11个MySQL错误
- JAVA WEB SQLHelper类的封装
- 单台电脑上启动多个Modelsim图形环境窗口的简单办法（windows）
- android string.xml里的空格字符
- Eclipse 4.2 + Tomcat 7.x + JDK 7 搭建Java Web开发环境
- css如何使背景图片水平居中
- （Problem 15）Lattice paths
- loj #6.Guess Number
- sed命令总结-Linux
- cmake安装
- Caused by: java.lang.ClassNotFoundException: Cannot find class解决办法
- 实习医生风云第一至九季/全集Scrubs迅雷下载
- php原生实现图片上传和查看
- 一个罕见的MSSQL注入漏洞案例
- .net core mvc 类库读取配置文件