cdsa

C 데이터 구조 및 알고리즘

ANSI C의 일반적인 침입 데이터 구조 및 알고리즘 라이브러리

• 배경
• 예
• 설치
• 실행 테스트
• 기여

배경

이 저장소는 ANSI C에서 일반적인 침입 데이터 구조 및 알고리즘을 구현하는 지속적인 프로젝트입니다. 많은 보일러 플레이트 코드가 필요한 동일한 구조물을 사용 하여이 구조물을 구성하고 이러한 구조물을 기존 프로젝트에 쉽게 통합 할 수 있도록이 저장소를 만들었습니다.

이 저장소의 나의 설계 철학은보다 복잡한/틈새 구성을 쉽게 구축하는 데 필요한 모든 도구를 포함하는 각 데이터 구조에 대해 최소한의 API를 제공하는 것입니다. 이식성은 최우선 과제이므로 ANSI C 만 사용되며 헤더/소스 쌍은 다른 헤더/소스 쌍에 의존하지 않습니다. 또한, 임베디드 시스템에서 사용되는 것을 촉진하기 위해, 반복 알고리즘은 재귀 알고리즘보다 독점적으로 사용되며, 각 데이터 구조는 방해 (더 나은 메모리로 위치).

이러한 데이터 구조와 알고리즘을 자신의 방식으로 자유롭게 사용하십시오. 이 코드는 ISC 라이센스 (기능적으로 동일한 BSD 라이센스의 단순화 된 버전)에 따라 라이센스가 부여됩니다. 따라서 독점적이든 오픈 소스이든 모든 프로젝트에서 합법적으로 재사용 될 수 있습니다.

예

각 헤더는 많이 문서화되어 있으며 기능에 관한 모든 질문에 답해야합니다. 각 데이터 구조의 작동 방식에 대한 심층적 인 설명은 헤더 파일 상단에 있습니다.

목록

 // Define your struct somewhere.
struct Object {
    int some_value ;
    ...

    // Don't forget to embed the ListNode!
    ListNode node ;
};

...

// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . some_value = 1 ;
obj2 . some_value = 2 ;

// Create your List.
List my_list ;
list_init ( & my_list );

// Populate your List. Notice how the API abstracts itself and only cares about the ListNode.
list_insert_back ( & my_list , & obj1 . node );
list_insert_back ( & my_list , & obj2 . node );

// Let's see what is stored in the List:
int i = 1 ;
ListNode * n ;
list_for_each ( n , & my_list ) {
    if ( i == 1 ) {
        assert ( n == & obj1 . node );
    } else if ( i == 2 ){
        assert ( n == & obj2 . node );
    }

    ++ i ;
}

...

// Let's get the ListNode at the front of the List.
ListNode * front_node_ptr = list_front ( & my_list );

// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "list_entry":
struct Object * obj_ptr = list_entry ( front_node_ptr , struct Object , node );
assert ( obj_ptr == & obj1 );

rbtree

 // Define your struct somewhere.
struct Object {
    int key ;
    ...

    // Don't forget to embed the RBTreeNode!
    RBTreeNode node ;
};

...

// You must define a compare function which compares a key with the key of a RBTreeNode.
int compare ( const void * some_key , const RBTreeNode * some_node ) {
    return * ( const int * ) some_key - rbtree_entry ( some_node , struct Object , node ) -> key ;
}

// You can OPTIONALLY define a collide function which handles key collisions. When a key
// collision happens, no matter what, the old RBTreeNode will be replaced by the new
// RBTreeNode. If this function is defined, then it will be called after the old
// RBTreeNode is replaced in the RBTree. This function is great if you need to free up
// resources in the Object variable pertaining to the discarded RBTreeNode. This function
// is also great for enabling multi-key functionality in the RBTree.
void collide ( const RBTreeNode * old_node , const RBTreeNode * new_node , void * auxiliary_data ) {
    // When a RBTree is created, we can give it auxiliary data to hold onto. This data is then
    // passed to this function for usage. This data, for example, could be a memory pool struct
    // that is needed to free up the resources used by the Object variable pertaining to the
    // old_node parameter.

    ...
}

...

// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . key = 1 ;
obj2 . key = 2 ;

// Create you RBTree. In this case we don't have any auxiliary data that needs to be used
// in the collide function, so we just pass NULL. As previously mentioned, the collide
// function itself is optional. If you don't need to do any special resource management,
// just pass "NULL" in place of "collide" in the initialize function.
RBTree my_rbtree ;
rbtree_init ( & my_rbtree , compare , collide , NULL );

// Populate your RBTree. Notice how the API abstracts itself and only cares about the
// RBTreeNode and its key. Because red black trees are always ordered in some way, order
// of insertion will never affect the inorderness of the tree.
rbtree_insert ( & my_rbtree , & obj2 . key , & obj2 . node );
rbtree_insert ( & my_rbtree , & obj1 . key , & obj1 . node );

// Because of the way our compare function is designed, the RBTree stores its RBTreeNodes
// inorder from smallest key to greatest key. Let's see what is stored in the RBTree:
int i = 1 ;
RBTreeNode * n ;
rbtree_for_each ( n , & my_rbtree ) {
    if ( i == 1 ) {
        assert ( n == & obj1 . node );
    } else if ( i == 2 ) {
        assert ( n == & obj2 . node );
    }

    ++ i ;
}

...

// Let's get the RBTreeNode with the greatest key.
RBTreeNode * greatest_node_ptr = rbtree_last ( & my_rbtree );

// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "rbtree_entry":
struct Object * obj_ptr = rbtree_entry ( greatest_node_ptr , struct Object , node );
assert ( obj_ptr == & obj2 );

해시 가능

 // Define your struct somewhere.
struct Object {
    int key ;
    ...

    // Don't forget to embed the HashTableNode!
    HashTableNode node ;
};

...

// You must define a hash function which takes in a key and returns its hashcode. In this
// case we aren't going to do anything fancy since this is just an example.
size_t hash ( const void * key ) {
    return * ( const int * ) key ;
}

// You must define an equal function which determines if a key is equal to the key of a HashTableNode.
int equal ( const void * some_key , const HashTableNode * some_node ) {
    return * ( const int * ) some_key == hashtable_entry ( some_node , struct Object , node ) -> key ;
}

// You can OPTIONALLY define a collide function which handles key collisions. When a key
// collision happens, no matter what, the old HashTableNode will be replaced by the new
// HashTableNode. If this function is defined, then it will be called after the old
// HashTableNode is replaced in the HashTable. This function is great if you need to free up
// resources in the Object variable pertaining to the discarded HashTableNode. This function
// is also great for enabling multi-key functionality in the HashTable.
void collide ( const HashTableNode * old_node , const HashTableNode * new_node , void * auxiliary_data ) {
    // When a HashTable is created, we can give it auxiliary data to hold onto. This data is then
    // passed to this function for usage. This data, for example, could be a memory pool struct
    // that is needed to free up the resources used by the Object variable pertaining to the
    // old_node parameter.

    ...
}

...

// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . key = 1 ;
obj2 . key = 2 ;

// You must create a bucket array which is an array of pointers to HashTableNodes. This
// array is used by the HashTable for the duration of its lifetime. In this case we will
// have 50 buckets in the bucket array.
HashTableNode * bucket_array [ 50 ];

// Create you HashTable. In this case we don't have any auxiliary data that needs to be used
// in the collide function, so we just pass NULL. As previously mentioned, the collide
// function itself is optional. If you don't need to do any special resource management,
// just pass "NULL" in place of "collide" in the initialize function.
HashTable my_hashtable ;
hashtable_init ( & my_hashtable , bucket_array , 50 , hash , equal , collide , NULL );

// Populate your HashTable. Notice how the API abstracts itself and only cares about the
// HashTableNode and its key.
hashtable_insert ( & my_hashtable , & obj1 . key , & obj1 . node );
hashtable_insert ( & my_hashtable , & obj2 . key , & obj2 . node );

// HashTable provides no guarantee on the ordering of HashTableNodes in the bucket array.
// Let's see what is stored in the HashTable:
int sum_of_keys = 0 , bucket_index ;
HashTableNode * n ;
hashtable_for_each ( n , bucket_index , & my_hashtable ) {
    sum_of_keys += hashtable_entry ( n , struct Object , node ) -> key ;
}
assert ( sum_of_keys == 3 );

...

// Let's get the HashTableNode with the key that equals 1.
int key = 1 ;
HashTableNode * node_ptr = hashtable_lookup_key ( & my_hashtable , & key );

// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "hashtable_entry":
struct Object * obj_ptr = hashtable_entry ( node_ptr , struct Object , node );
assert ( obj_ptr == & obj1 );

스택

 // Define your struct somewhere.
struct Object {
    int some_value ;
    ...

    // Don't forget to embed the StackNode!
    StackNode node ;
};

...

// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . some_value = 1 ;
obj2 . some_value = 2 ;

// Create your Stack.
Stack my_stack ;
stack_init ( & my_stack );

// Populate your Stack. Notice how the API abstracts itself and only cares about the StackNode.
stack_push ( & my_stack , & obj1 . node );
stack_push ( & my_stack , & obj2 . node );

// Let's see what is stored in the Stack:
int i = 1 ;
StackNode * n ;
stack_for_each ( n , & my_stack ) {
    if ( i == 1 ) {
        assert ( n == & obj2 . node );
    } else if ( i == 2 ){
        assert ( n == & obj1 . node );
    }

    ++ i ;
}

...

// Let's get the StackNode at the top of the Stack.
StackNode * top_node_ptr = stack_peek ( & my_stack );

// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "stack_entry":
struct Object * obj_ptr = stack_entry ( top_node_ptr , struct Object , node );
assert ( obj_ptr == & obj2 );

대기줄

 // Define your struct somewhere.
struct Object {
    int some_value ;
    ...

    // Don't forget to embed the QueueNode!
    QueueNode node ;
};

...

// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . some_value = 1 ;
obj2 . some_value = 2 ;

// Create your Queue.
Queue my_queue ;
queue_init ( & my_queue );

// Populate your Queue. Notice how the API abstracts itself and only cares about the QueueNode.
queue_push ( & my_queue , & obj1 . node );
queue_push ( & my_queue , & obj2 . node );

// Let's see what is stored in the Queue:
int i = 1 ;
QueueNode * n ;
queue_for_each ( n , & my_queue ) {
    if ( i == 1 ) {
        assert ( n == & obj1 . node );
    } else if ( i == 2 ){
        assert ( n == & obj2 . node );
    }

    ++ i ;
}

...

// Let's get the QueueNode at the front of the Queue.
QueueNode * front_node_ptr = queue_peek ( & my_queue );

// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "queue_entry":
struct Object * obj_ptr = queue_entry ( front_node_ptr , struct Object , node );
assert ( obj_ptr == & obj1 );

설치

이 라이브러리는 ANSI C로 작성되므로 코드는 거의 모든 컴파일러와 함께 작동해야합니다. 각 헤더/소스 쌍은 다른 헤더 쌍과 무관합니다. 이것은 개별 데이터 구조를 쉽게 사용합니다. 헤더/소스 쌍을 프로젝트에 직접 끌어 내고 다른 파일과 함께 소스 파일을 컴파일하십시오.

실행 테스트

테스트를 실행하기 위해 GNU 컴파일러를 사용할 수 있어야합니다. 이 라이브러리와 관련된 모든 파일을 다운로드해야합니다.

"테스트"디렉토리 에서이 명령을 한 번 실행하여 모든 테스트를 실행하십시오.

 make

예:

 cd tests/
make
gcc test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -pedantic-errors -std=c89
./test_list C89

PASSED: List C89

rm -f test_list
gcc test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -std=gnu89
./test_list GNU89

PASSED: List GNU89

rm -f test_list
g++ test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -pedantic-errors -std=c++11
./test_list C++11

PASSED: List C++11

rm -f test_list
g++ test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -std=gnu++11
./test_list GNU++11

PASSED: List GNU++11

rm -f test_list
gcc test_rbtree.c ../src/rbtree.c -o test_rbtree -Wall -Wextra -Werror -pedantic-errors -std=c89
./test_rbtree C89

PASSED: RBTree C89

rm -f test_rbtree
gcc test_rbtree.c ../src/rbtree.c -o test_rbtree -Wall -Wextra -Werror -std=gnu89
./test_rbtree GNU89

PASSED: RBTree GNU89

etc... (this goes on for a while)

기여

기부금을 환영합니다!

기능 요청이 있거나 버그를 찾은 경우 새 문제를 자유롭게 열어주십시오. 코드를 기여하려면 철저히 문서화하고 각 기능/매크로에 대한 테스트를 작성하십시오. 코드를 마무리하는 데 도움을 줄 것이며 사용 된 규칙이 일관되도록 도와 드리겠습니다.