'자료구조'에 해당되는 글 2건

  1. 2007/11/27 hash 기본 구현.
  2. 2007/11/27 환형 리스트를 범용적으로 구현..

hash 기본 구현.

from Study/자료구조 2007/11/27 19:19 view 28229
해쉬 구조를 알기 위해선 아래 문서를 읽어 보고...c로 해쉬를 구성해보자.
http://lxr.linux.no/source/include/linux/hash.h


1. 해쉬 함수는 여러가지 알고리즘이 있으나 커널에서는 간단하면서도 우수한 folding exclusive 방식을 사용.

#define PIDHASH_SZ  16
#define
pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

pid_hashfn(777)

( ( 777 >> 8 ) ^ 777 ) & ( 16 - 1 )

777                                           => 1100001001
777 >> 8                                   => 0000000011
( 777 >> 8 ) ^ 777                      => 1100001010
16 - 1                                       => 0000001111
( ( 777 >> 8 ) ^ 777 ) & ( 16 - 1 )  => 0000001010

2. 해쉬는 탐색을 위한 자료구조라고도 할 수 있다. 자료를 효율적으로 분산하여 저장할 수 있게 된다.
사용자 삽입 이미지
사용자 삽입 이미지


전체 소스~

more..

List를 C로만 구성하기 위해서 공개된 list 를 참고해 본다.
일단  http://lxr.linux.no/source/include/linux/list.h 를 참조.

1. 보통 리스트를 구현할 때 리스트와 자료형을 같이 사용하지만 이런 구현은 매번 리스트를 따로 구현해야하는 아픔이 있다.
사용자 삽입 이미지


2. 그래서 리스트의 구조를 구조체를 만들때 그 밑에 구현 해 놓는 방식을 사용하도록 한다.
3. 이렇게 되면 리스트를 포함 시켜놓으면 헤더 파일을 중심으로 리스트를 가질수 있다.

사용자 삽입 이미지

4. 리스트의 추가는 앞뒤의 객체에게 알려주면 된다.
void __list_add(struct list_head *new=0x3004,

            struct list_head *prev=0x1000,

            struct list_head *next=0x2004)

{

  next->prev = new;

  new->next = next;

  new->prev = prev;

  prev->next = new;

}


5. 구조체의 내용을 읽기 위해선 시작위치를 0으로 시작한다는 개념을 잡아야 한다. 

#define  list_entry( temp, type, list ) \

((type *)((char*)temp (unsigned long)(&((type *)0)->list)))

TASK *p = list_entry( temp, TASK, list );

p->pid;


전체 소스 ~

more..