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)

貢献

貢献は大歓迎です！

機能リクエストがある場合、またはバグが見つかった場合は、新しい問題を公開してください。コードを紹介したい場合は、徹底的に文書化し、各機能/マクロのテストを必ず書き込みます。私はコードの最終化を支援し、使用される規則が一貫していることを確認するのに役立ちます。