[PintOS] Hash table

Baedonguri·2022년 6월 12일
0
post-thumbnail

Pintos는 lib/kernel/hash.c에 해시 테이블 데이터 구조를 제공한다.
가상 메모리 프로젝트의 대부분의 구현들은 페이지를 프레임으로 변환하기 위해 해시 테이블을 사용한다.

Data Types

Hash Table은 struct hash로 나타내어진다.

struct hash;

struct hash에는 직접 접근할 수 없기 때문에 필요시에는 hash table function과 macro를 사용한다.
hash table은 struct hash_elem을 리스트의 인자로 가진다.


struct hash_elem;

hash table에 관련된 함수들은 hash_elem을 인자로 가지거나 반환한다.
hash table의 real element가 주어졌을 때, hash elem을 가리키는 포인터를 획득하기 위해서는 &
(비트연산자)를 사용해야한다. 다른 방향으로 가고 싶으면 hash_entry()를 사용해야 한다.


#define hash_entry (elem, type, member) {/* Omit details */ }

elem이 소속되어있는 구조체의 포인터를 반환한다. 이 함수를 사용할 때는 구조체의 type을 명시해야한다. 각 hash table element는 elem의 구조체를 확인/구별할 수 있게하는 key data를 가진다.
hash table안에 있는 동안은 이 key data는 변질 되어선 안된다.
필요한 경우에는 (재삽입할 경우를 대비하여) hash table로부터 elem을 제거하고 key data를 수정할 수 있다.


각 hash table에서 key에 대한 hash function과 comparsion function의 두가지 함수를 작성해야한다.

typedef unsigned hash_hash_func (const struct hash_elem *e, void *aux);

elem이 소속되어있는 hash의 unsigned int형 데이터를 반환한다.
이 hash는 key를 기반으로 랜덤으로 뽑힌 hash이며, non-key data나 non-constant data로 뽑히면 안된다.
만약 key가 각 hash 타입에서 유일한 key라면 이 함수들이 반환한 값을 사용해도 좋다.
만약 유일하지 않다면, 여러 함수들이 반환한 값을 ^ (exclusive or) 를 사용하여 조합해야한다.

PintOS는 hash function을 위해 다음 세 개의 함수를 제공한다.

unsigned hash_bytes (const void *buf, size t *size)
  • buf에서 size 크기 만큼의 hash를 반환한다.
unsigned hash_string (const char *s)
  • null 이 제거된 string s의 hash를 반환한다.
unsigned hash_int (int i)

정수형 i의 hash 값을 반환한다.


Basic Function

이 함수들은 hash table을 만들거나, 검사하거나, 제거하기 위해 사용된다.

bool hash_init (struct hash *hash, hash_hash_func *hash_func, hash_less_func *less_func, void *aux)

hash function들을 사용하여 hash table을 초기화한다. 성공한다면 true를 반환한다.
이 함수는 malloc()을 호출하며 호출에 실패하면 false를 반환한다.

void hash_clear (struct hash *hash, hash_action_func *action)

hash에서 모든 elem을 제거한다. (반드시 이 hash는 hash_init()을 거쳤어야 함)
만약 인자 action이 있다면, 이 함수는 table 안의 elem마다 한번씩 불러지며, 이는 각 요소가 사용한 메모리나
타 resources들을 deallocate하기 위한 것이다.
예를 들어, hash table elements이 malloc을 사용하여 동적으로 할당받았다면, 그 후에 인자로 free()를 호출해서 해당 element를 지워야한다.
인자action에 hash_insert()나 hash_delete()같은 hash table을 수정하는 어떠한 함수도 와선 안된다.

void hash_destroy (struct hash *hash, hash_action_func *action);

만약 인자action이 존재한다면, hash안의 각 element마다 호출한다. hash_clear와 다른 점은, hash 자체를 free시킨다는 점이다.

size_t hash_size (struct hash *hash);

hash안에 저장되어있는 element의 수를 반환한다.

bool hash_empty (struct hash *hash);

hash가 비어있다면 True를 반환한다.


Search Functions

struct hash_elem *hash_insert (struct hash *hash, struct hash elem *element);

hash에서 주어진 element와 같은 element가 있는지를 검사한다. 성공했다면, 해당 함수의 작업을 수행한다.
인자 element와 같은 element가 hash안에 있는지 검색한다. 만약 없다면 인자 element를 hash에 삽입하고 null 포인터를 반환한다. 만약 같은 element가 있다면 hash를 수정하지 않고 해당 element를 반환한다.

struct hash_elem *hash_replace (struct hash *hash, struct hash elem *element);

hash에 element를 삽입한다. 만약 동일한 element가 이미 있다면, 이미 있던 elemnt를 삭제하고, 삭제된 element를 반환한고, 없었다면 null 포인터를 반환한다. 호출자는 반환된 element를 free()등을 사용하여 deallocate한다.
반환된 element는 아래 함수들의 인자로 넣는데, 비교하기 위한 목적으로만 사용되어야한다. element안의 key data만 초기화되어야하며, 다른 data들은 쓰이지 않을 것이다. 지역 변수로 element를 선언하고, key를 초기화한 뒤, struct hash_elem의 주소를 hash_find()나 hash_delete()의 인자로 넘길 수 있다.

struct hash_elem *hash_find (struct hash *hash, struct hash elem *element);

주어진 element와 같은 element가 hash안에 있는지 탐색한다.
성공하면 해당 elemnt를, 실패하면 null 포인터를 반환한다.

struct hash_elem *hash_delete (struct hash *hash, struct hash elem *element);

주어진 element와 같은 element가 hash안에 있는지 탐색한다. 찾았다면 hash로부터 삭제하고 주소를 반환한다. 찾지 못했다면 null 포인터를 반환하고 hash는 수정하지 않는다.
replace와 같이 호출자는 반환된 element를 dellocate()해야한다.

Iteration Functions()

이 함수들은 hash table의 element를 반복작업을 할 수 있도록 한다. 두 인터페이스가 제공되는데, 첫번째 함수는 writing이랑 각 elemnt에 대해 hash_Action_func가 작동하도록 도와준다.

void hash_apply (struct hash *hash, hash action func *action);

hash안의 각 element에 대해 인자action을 수행한다. 인자action에는 hash table을 수정하는 함수가 와선 안된다. 또한, 인자action이 element의 데이터를 수정해도, key data는 건들여선 안된다.
두번째 인터페이스는 iterator data type에 의해 결정된다.

struct hash_iterator;

hash table안의 position을 나타낸다. hash_insert()나 hash_delete()와 같이 hash table을 건드리는 함수들은 hash table의 모든 iterator들을 무효로 만든다.
struct hash 나 struct hash_elem처럼 struct hash_iterator도 elem을 통해 간접적으로 다뤄야한다.

void hash_first (struct hash iterator *iterator, struct hash *hash);

hash의 첫번째 element 이전의 iterator를 초기화한다.

struct hash_elem *hash_next (struct hash iterator *iterator);

iterator를 hash의 다음 element로 이동시키거나, 해당 element를 반환한다. 만약 남아있는 element가 없다면 null 포인터를 반환한다. hash_next()가 iterator에 null을 반환한 다음 이 함수를 호출하면 이상한 결과가 나올 수 있다.

struct hash_elem *hash_cur (struct hash iterator *iterator);

가장 최근에 hash_next()에 의해 반환된 value를 iterator에 반환한다. hash_first()를 호출한 직후에 (hash_next()를 호출하지 않고) 이 함수를 호출하면 이상한 결과가 나올 수 있다

profile
Software Engineer

0개의 댓글