https://firecatlibrary.tistory.com/71
를 보고 끄적인 글

해시 테이블은 구조체 해시로 표현

struct hash;

전체 해시 테이블 나타냅니다. struct hash에 직접 접근 불가능해서, hash table 함수와 매크로를 사용해야함. hash table은 struct hash_elem을 리스트의 인자로 가진다.

struct hash_elem;

해시 테이블을 포함한 구조에 struct hash_elem 멤버를 포함시킵니다. struct hash처럼 구조 struct hash_elem은 접근 불가능함. 해시 테이블 요소에서 작동하기 위한 모든 함수는 실제로 해시 테이블의 실제 요소 유형에 대한 포인터가 아니라 struct hash_elem에 대한 포인터를 가져와서 반환함.

#define hash_entry (elem, type, member) 

elem이 소속되어있는 structure의 포인터반환, 각 hash table element는 elem의 structure를 확인/ 구별할 수 있게 하는 key data를 가진다. hash table안에 있는동안은 이 key data는 변질되선 안된다. 필요한 경우(재삽입할 경우를 대비)에는 hash table로부터 elem을 제거하고 key data를 수정할 수 있다. list_entry랑 같은 맥락인듯.

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

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로 뽑히면 안된다. 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)

integer 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 함수들을 사용하여 hash table을 초기화한다. 성공한다면 true를 반환한다. 이 함수는 malloc을 호출하며 호출에 실패하면 false를 반환한다.

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

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

size_t hash_size (struct hash *hash);

hash 안에 저장되어있는 element를 수를 반환

bool hash_empty (struct hash *hash);

hash가 비어있다면 true 반환

Search Functions

hash에서 주어진 element와 같은 element가 있는지 검사한다. 성공했다면, 해당 함수의 작업을 수행한다.

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

인자 element와 같은 element가 hash안에 있는지를 검색. 만약 없다면 인자 element를 hash에 삽입하고, null 포인터를 반환한다. 만약 같은 element가 있다면 hash를 수정하지 않고 해당 element를 반환한다.

반환된 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안에 있는지 탐색한다. 성공하면 해당 element를, 실패하면 null 포인터를 반환한다.

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

주어진 element와 같은 element가 hash안에 있는지 탐색한다. 찾았다면 hash로부터 삭제하고 주소를 반환한다. 찾지 못했다면 null포인터를 반환하고 hash는 수정하지 않는다.

Iterations Functions

이 함수들은 hash table의 element를 반복작업할 수 있도록 한다. 두 인터페이스가 제공되는데, 첫번째 함수는 writing이랑 각 element에 대해 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들을 무효로 만듭니다.

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()를 호출하지 않고) 이 함수를 호출하면 이상한 결과가 나올 수 있다.