Linux 커 널 데이터 구조

개술
        Linux 커 널 은 자주 사용 하 는 데이터 구 조 를 제공 하고 개발 자 에 게 가능 한 한 재 활용 하 라 고 건의 하 며 유사 한 데이터 구 조 를 실현 할 필요 가 없습니다.이 블 로 그 는 주로 리 눅 스 커 널 이 제공 하 는 링크, 큐, 맵 과 이 진 트 리 등 네 가지 상용 데이터 구 조 를 묘사 하고 있다.물론 여기 서 언급 한 모든 데이터 구 조 는 명확 하 게 말 하려 면 많은 지면 이 필요 하 다. 이 박문 은 리 눅 스 커 널 디자인 의 이념 을 간략하게 분석 하여 선택 할 때 자신 이 가지 고 있 는 것 을 할 수 있 도록 해 야 한다.
링크
        링크 는 일련의 데 이 터 를 구성 하 는 데 가장 자주 사용 되 는 데이터 구조 이다.링크 는 정적 배열 과 다 르 고 길이 가 변 할 수 있 으 며 포인터 로 앞 이나 뒤의 노드 요 소 를 가리 키 기 때문에 모든 노드 간 의 메모리 가 연속 되 지 않 을 수 있 습 니 다. 이것 은 그의 삽입 과 삭제 작업 을 매우 간단 하 게 만 들 수 있 습 니 다.
        리 눅 스 커 널 은 자신의 링크 데이터 구 조 를 정의 했다. 다른 시스템 과 달리 링크 의 앞 뒤 지침 을 특정한 구조 체 에 심 었 다. 리 눅 스 는 링크 의 구조 체 (list head) 를 링크 를 구성 해 야 하 는 노드 구조 체 에 심 었 다.다음 과 같은 형식:

struct list_head{
    struct list_head *prev;
    struct list_head *next;
};

struct myNode{
    void * data;
    struct list_head list;  /*   myNode       */
};

        Linux container 통과of () 매크로 로 list 획득head 링크 에 포 함 된 inode 포인터 로 inode 요소 에 대한 링크 조직 을 실현 합 니 다.
        LInux 는 링크 의 함수 정 의 를 < linux/list. h > 헤더 파일 에 제공 합 니 다. 추가, 삭제, 옮 겨 다 니 기 등 일반적인 작업 을 포함 합 니 다.
        LInux 라 는 링크 조직 형식 은 통 일 된 조작 방법 을 제공 하여 커 널 프로 그래 밍 시 링크 의 다양한 디자인 이 가 져 온 곤혹 을 피 할 수 있 고 개발 엔지니어 들 이 다른 디자인 에 더 집중 할 수 있 으 며 대량의 인 코딩 작업 을 줄 일 수 있다. 이런 디자인 이념 은 배 울 가치 가 있다.사실 이런 디자인 은 생활 속 에서 도 살 아 있 는 예 가 존재 한다. 예 를 들 어 후크 식 커튼 이 레일 과 링 단 추 를 만 든 후에 서로 다른 커튼 을 마음대로 걸 수 있 고 커튼 을 교체 해 야 할 때 레일 을 뜯 지 않 아 도 되 는 등 다시 만 들 지 않 고 커튼 천 을 교체 하면 된다.
대열
        그 어떠한 운영 체제 도 하나의 모델 이 빠 질 수 없다. 그것 이 바로 생산자 인 소비자 모델 이다. 대열 은 바로 이런 모델 의 기초 데이터 구 조 를 실현 하 는 것 이다. 이것 은 FIFO 모델 로 생산 소비의 관 계 를 완벽 하 게 해결 하 는 데 사용 된다.Linux 커 널 유 니 버 설 대기 열 은 kfifo 라 고 합 니 다./kernel/kfifo. c 에 정의 되 어 있 으 며, 성명 은 파일 < linux/kfifo. h > 에 있 습 니 다.
        리 눅 스 의 대기 열 은 다른 시스템 이 정의 하 는 대기 열 과 차이 가 많 지 않 습 니 다. 개발 자 에 게 호출 할 수 있 는 함 수 를 제공 합 니 다. 초기 화, 데이터 추출, peek 데이터 추출, 대기 열 폐기 및 대기 열 상태 조회 등 함 수 를 포함 합 니 다.구체 적 으로 kfifo. c 소스 파일 참조.
반사
        맵 은 보통 관련 배열 이 라 고도 부 릅 니 다. 사실은 하나의 유일한 키 로 구 성 된 집합 입 니 다. 모든 키 는 반드시 특정한 값 과 관련 되 어야 합 니 다. 맵 은 다음 과 같은 세 가지 조작 함 수 를 제공 해 야 합 니 다. add (key, value).remove(key); value = lookup(key);