Kernel Hash Table

구조

커널 해시 테이블은 Linked List로 이루어진 해시 테이블과 유사하다.

키의 해싱을 통해 데이터를 호출하기 때문에 O(1)만에 데이터를 찾을 수 있는 장점이 있다.

Key

커널에서 Key의 배열은 hlist_head로 구현되어있다.

각 키는 해싱 함수를 통해 hlist_node로 연결되어 데이터를 호출한다.

Value

Value는 hlist_node로 구현되어 있으며, 데이터는 hlist_node를 포함하는 자료구조를 통해 저장한다.

충돌이 일어날 경우, hlist_node를 연결하여 데이터를 저장한다.

예제

#include <linux/hashtable.h>

struct hash_entry {
  uint64_t key;
  uint64_t data;
  hlist_node my_hash_list;
}

int main(void)
{
  struct hash_entry *entry;
  struct hash_entry *cur; // this is for searching hash table
  
  /* create hash table
     first param is a table name
     second param is a table size, which is 2^size
   */
  DEFINE_HASHTABLE("hash_table", 3);
  
  // initialize table
  hash_init("hash_table");
  
  // create hash entry
  entry = (struct hash_entry *)kmalloc(sizeof(struct hash_entry *));
  entry->key = 1;
  entry->data = 1;
  
  /* add a entry in hash table
     first param is a table name
     second param is a hlist_node
     third param is a key, which is a hlist_head
   */
  hash_add("hash_table", my_hash_list, entry->key);

  // search for every entry in hash table
  // cur represents each entry.
  hash_for_each("hash_table", cur, my_hash_list) {
    printk(KERN_INFO "current entry key = %d, value = %d\n", cur.key, cur.value);
  }
  
  // search for entry which include special key in hash table
  printk(KERN_INFO "this is a entry list which is include "1"");
  hash_for_each_possible("hash_table", cur, my_hash_list, 1) {
    printk(KERN_INFO "current entry key = %d, value = %d\n", cur.key, cur.value);
  }
}