hash 사용 방법 - Week12-13-GOAT/pintos-vm GitHub Wiki
Pintos의 hash.h
와 hash.c
는 커널 내에서 사용할 수 있는 범용 해시 테이블 구현을 제공합니다. 이 구조는 특히 supplemental page table (SPT) 같은 VM 구현에서 자주 사용되며, 아래에 그 사용법을 구조체 설계부터 삽입/탐색/삭제까지 전반적으로 설명하겠습니다.
해시 테이블에 삽입될 구조체는 반드시 struct hash_elem
멤버를 포함해야 합니다.
#include "threads/synch.h"
#include "lib/kernel/hash.h"
struct my_entry {
int key;
int value;
struct hash_elem elem; // 필수
};
// 해시 함수
static uint64_t my_hash(const struct hash_elem *e, void *aux UNUSED) {
struct my_entry *entry = hash_entry(e, struct my_entry, elem);
return hash_int(entry->key);
}
// 비교 함수 (정렬 기준)
static bool my_less(const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED) {
struct my_entry *ea = hash_entry(a, struct my_entry, elem);
struct my_entry *eb = hash_entry(b, struct my_entry, elem);
return ea->key < eb->key;
}
struct hash my_hash_table;
void init_table(void) {
hash_init(&my_hash_table, my_hash, my_less, NULL);
}
struct my_entry *e = malloc(sizeof(struct my_entry));
e->key = 42;
e->value = 100;
struct hash_elem *prev = hash_insert(&my_hash_table, &e->elem);
if (prev != NULL) {
// 기존 키가 있었다면 prev가 반환됨 → e는 삽입되지 않음
free(e);
}
struct my_entry lookup;
lookup.key = 42;
struct hash_elem *found = hash_find(&my_hash_table, &lookup.elem);
if (found != NULL) {
struct my_entry *e = hash_entry(found, struct my_entry, elem);
printf("Found value: %d\n", e->value);
}
struct hash_elem *deleted = hash_delete(&my_hash_table, &lookup.elem);
if (deleted != NULL) {
struct my_entry *e = hash_entry(deleted, struct my_entry, elem);
free(e); // 직접 메모리 해제 필요
}
struct hash_iterator i;
hash_first(&i, &my_hash_table);
while (hash_next(&i)) {
struct my_entry *e = hash_entry(hash_cur(&i), struct my_entry, elem);
printf("key=%d, value=%d\n", e->key, e->value);
}
// 요소 하나를 정리하는 함수
void my_destructor(struct hash_elem *e, void *aux UNUSED) {
struct my_entry *entry = hash_entry(e, struct my_entry, elem);
free(entry);
}
hash_clear(&my_hash_table, my_destructor);
hash_destroy(&my_hash_table, my_destructor);
동작 | 함수 |
---|---|
초기화 | hash_init() |
삽입 | hash_insert() / hash_replace() |
탐색 | hash_find() |
삭제 | hash_delete() |
반복 | hash_first() + hash_next() |
전체 제거 | hash_clear() / hash_destroy() |
이 인터페이스는 대부분의 커널 데이터 구조 (e.g. SPT, FD Table 등)에 유용하며, 성능상 배열보다 월등히 유리한 경우가 많습니다. hash_entry()
매크로 사용법이 핵심이니 익숙해져야 합니다.