diff --git a/modules/include/kc_iterator.h b/modules/include/kc_iterator.h index d164fc1..562fd5e 100644 --- a/modules/include/kc_iterator.h +++ b/modules/include/kc_iterator.h @@ -40,15 +40,6 @@ */ const void *(*next)(struct KcIterator_ *ite, size_t *size); - /** - * 次の要素を取得します。 - * 格納している扱う要素が文字列の場合にのみ利用可能です。 - * - * @param ite Iterator オブジェクト - * @return 次の要素(文字列) - */ - const char *(*nextString)(struct KcIterator_ *ite); - /** 内部情報 */ void *_info; diff --git a/modules/include/kc_iterator.h b/modules/include/kc_iterator.h index d164fc1..562fd5e 100644 --- a/modules/include/kc_iterator.h +++ b/modules/include/kc_iterator.h @@ -40,15 +40,6 @@ */ const void *(*next)(struct KcIterator_ *ite, size_t *size); - /** - * 次の要素を取得します。 - * 格納している扱う要素が文字列の場合にのみ利用可能です。 - * - * @param ite Iterator オブジェクト - * @return 次の要素(文字列) - */ - const char *(*nextString)(struct KcIterator_ *ite); - /** 内部情報 */ void *_info; diff --git a/modules/src/kc_list.c b/modules/src/kc_list.c index a59e643..a5a97ce 100644 --- a/modules/src/kc_list.c +++ b/modules/src/kc_list.c @@ -13,9 +13,6 @@ */ void KcList_delete(KcList *list) { - if (list->cleanup_info) - { - list->cleanup_info(list); - } + list->cleanup_info(list); free(list); } diff --git a/modules/include/kc_iterator.h b/modules/include/kc_iterator.h index d164fc1..562fd5e 100644 --- a/modules/include/kc_iterator.h +++ b/modules/include/kc_iterator.h @@ -40,15 +40,6 @@ */ const void *(*next)(struct KcIterator_ *ite, size_t *size); - /** - * 次の要素を取得します。 - * 格納している扱う要素が文字列の場合にのみ利用可能です。 - * - * @param ite Iterator オブジェクト - * @return 次の要素(文字列) - */ - const char *(*nextString)(struct KcIterator_ *ite); - /** 内部情報 */ void *_info; diff --git a/modules/src/kc_list.c b/modules/src/kc_list.c index a59e643..a5a97ce 100644 --- a/modules/src/kc_list.c +++ b/modules/src/kc_list.c @@ -13,9 +13,6 @@ */ void KcList_delete(KcList *list) { - if (list->cleanup_info) - { - list->cleanup_info(list); - } + list->cleanup_info(list); free(list); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index 9e746a1..a6a41c3 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -3,6 +3,10 @@ * @brief Linked リストモジュール * @copyright 2003 - 2023 Nomura Kei */ +#if defined(__GNUC__) +#define _GNU_SOURCE 1 +#define qsort_s qsort_r +#endif #include #include #include @@ -61,20 +65,6 @@ static KcLinkedListEntry *KcLinkedList_search(KcLinkedListInfo *info, int index); static KcLinkedListEntry *KcLinkedList_new_entry(const void *value, size_t size); -// [内部関数用] For Quick Sort -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2); -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); - /** * LinkedList を構築します。 * @@ -281,12 +271,46 @@ // ----------------------------------------------------------------------------- /** + * [内部利用] + * ソート情報 + */ +typedef struct +{ + int (*comparator)(const void *element1, size_t size1, + const void *element2, size_t size2, void *args); + size_t element_size; + void *user_args; +} KcListSortInfo; + +/** + * [内部利用] + * KcLinkedList_sort にて利用される、qsort_s に渡される comparator です。 + * + * @param x 比較する要素1 + * @param y 比較する要素2 + * @param context コンテキスト(KcListSortInfo) + * @return 比較結果 + */ +static int KcLinkedList_comparator(const void *x, const void *y, void *context) +{ + KcListSortInfo *sort_info = (KcListSortInfo *)context; + const KcLinkedListEntry **entry_x = (const KcLinkedListEntry **)x; + const KcLinkedListEntry **entry_y = (const KcLinkedListEntry **)y; + int ret = sort_info->comparator( + (*entry_x)->value, + (*entry_x)->size, + (*entry_y)->value, + (*entry_y)->size, + sort_info->user_args); + return ret; +} + +/** * 指定された comparator が示す順序に従って、対象リストをソートします。 * * @param list 対象リスト * @param comparator リスト要素を比較するために使用される comparator * @param args comparator の第5引数に渡すオブジェクト - * @return true/false (ソート成功/ソート失敗) */ static void KcLinkedList_sort(KcList *list, int (*comparator)(const void *element1, size_t size1, @@ -294,13 +318,43 @@ void *args) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; + kc_lock_guard(&(info->mutex)) { - KcLinkedList_sort_recur( - info, - info->head->next, - info->tail->prev, - comparator, args); + // Linked List エントリへのポインタを格納する配列を生成する。 + KcLinkedListEntry **ptr_list = (KcLinkedListEntry **)calloc( + info->size, sizeof(KcLinkedListEntry *)); + int idx = 0; + for (KcLinkedListEntry *entry = info->head->next; entry != info->tail; entry = entry->next) + { + ptr_list[idx] = entry; + idx++; + } + + // ソート処理 + KcListSortInfo sort_info; + sort_info.comparator = comparator; + sort_info.user_args = args; + + qsort_s( + ptr_list, + info->size, + sizeof(KcLinkedListEntry *), + KcLinkedList_comparator, + &sort_info); + + // 配列の情報を元にエントリを再構成する。 + KcLinkedListEntry *prev_entry = info->head; + for (int idx2 = 0; idx2 < (int)info->size; idx2++) + { + KcLinkedListEntry *entry = ptr_list[idx2]; + prev_entry->next = entry; + entry->prev = prev_entry; + prev_entry = entry; + } + prev_entry->next = info->tail; + info->tail->prev = prev_entry; + free(ptr_list); } } @@ -386,7 +440,7 @@ void *org_element, size_t *org_size) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; - bool is_success = true; + bool is_success = false; kc_lock_guard(&(info->mutex)) { KcLinkedListEntry *remove_entry = KcLinkedList_search(info, index); @@ -441,7 +495,6 @@ result_index = idx; break; } - entry = entry->next; idx++; } } @@ -467,16 +520,15 @@ int result_index = -1; kc_lock_guard(&(info->mutex)) { - int idx = 0; + int idx = info->size; for (KcLinkedListEntry *entry = info->tail->prev; entry != info->head; entry = entry->prev) { + idx--; if ((size == entry->size) && (memcmp(entry->value, element, entry->size) == 0)) { result_index = idx; break; } - entry = entry->next; - idx++; } } return result_index; @@ -639,83 +691,3 @@ } return entry; } - -//////////////////////////////////////////////////////////////////////////////// -// -// For Quick Sort -// - -/** - * 指定されたエントリを入れ替えます。 - * 同じエントリが渡された場合は何もしません。 - * - * @param entry1 入れ替えるエントリ1 - * @param entry2 入れ替えるエントリ2 - */ -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2) -{ - if (entry1 != entry2) - { - KcLinkedListEntry *temp = entry1->next; - entry1->next = entry2->next; - entry2->next = temp; - temp = entry1->prev; - entry1->prev = entry2->prev; - entry2->prev = temp; - } -} - -/** - * Quick Sort パーティション処理 - * - * @param info LinkedList 情報 - * @param low Low - * @param high High - * @param comparator 比較関数 - * @param args 比較関数に渡されるデータ - */ -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - KcLinkedListEntry *pivot = high; - KcLinkedListEntry *i = low->prev; - - for (KcLinkedListEntry *j = low; j != high; j = j->next) - { - int ret = comparator( - pivot->value, pivot->size, j->value, j->size, args); - if (ret >= 0) - { // j <= pivot - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, j); - } - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, high); - } - return i; -} - -/** - * Quick Sort 再帰処理 - */ -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - if ((high != info->tail) && (low != high) && (low != high->next)) - { - KcLinkedListEntry *p = KcLinkedList_sort_partition(info, low, high, comparator, args); - KcLinkedList_sort_recur(info, low, p->prev, comparator, args); - KcLinkedList_sort_recur(info, p->next, high, comparator, args); - } -} diff --git a/modules/include/kc_iterator.h b/modules/include/kc_iterator.h index d164fc1..562fd5e 100644 --- a/modules/include/kc_iterator.h +++ b/modules/include/kc_iterator.h @@ -40,15 +40,6 @@ */ const void *(*next)(struct KcIterator_ *ite, size_t *size); - /** - * 次の要素を取得します。 - * 格納している扱う要素が文字列の場合にのみ利用可能です。 - * - * @param ite Iterator オブジェクト - * @return 次の要素(文字列) - */ - const char *(*nextString)(struct KcIterator_ *ite); - /** 内部情報 */ void *_info; diff --git a/modules/src/kc_list.c b/modules/src/kc_list.c index a59e643..a5a97ce 100644 --- a/modules/src/kc_list.c +++ b/modules/src/kc_list.c @@ -13,9 +13,6 @@ */ void KcList_delete(KcList *list) { - if (list->cleanup_info) - { - list->cleanup_info(list); - } + list->cleanup_info(list); free(list); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index 9e746a1..a6a41c3 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -3,6 +3,10 @@ * @brief Linked リストモジュール * @copyright 2003 - 2023 Nomura Kei */ +#if defined(__GNUC__) +#define _GNU_SOURCE 1 +#define qsort_s qsort_r +#endif #include #include #include @@ -61,20 +65,6 @@ static KcLinkedListEntry *KcLinkedList_search(KcLinkedListInfo *info, int index); static KcLinkedListEntry *KcLinkedList_new_entry(const void *value, size_t size); -// [内部関数用] For Quick Sort -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2); -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); - /** * LinkedList を構築します。 * @@ -281,12 +271,46 @@ // ----------------------------------------------------------------------------- /** + * [内部利用] + * ソート情報 + */ +typedef struct +{ + int (*comparator)(const void *element1, size_t size1, + const void *element2, size_t size2, void *args); + size_t element_size; + void *user_args; +} KcListSortInfo; + +/** + * [内部利用] + * KcLinkedList_sort にて利用される、qsort_s に渡される comparator です。 + * + * @param x 比較する要素1 + * @param y 比較する要素2 + * @param context コンテキスト(KcListSortInfo) + * @return 比較結果 + */ +static int KcLinkedList_comparator(const void *x, const void *y, void *context) +{ + KcListSortInfo *sort_info = (KcListSortInfo *)context; + const KcLinkedListEntry **entry_x = (const KcLinkedListEntry **)x; + const KcLinkedListEntry **entry_y = (const KcLinkedListEntry **)y; + int ret = sort_info->comparator( + (*entry_x)->value, + (*entry_x)->size, + (*entry_y)->value, + (*entry_y)->size, + sort_info->user_args); + return ret; +} + +/** * 指定された comparator が示す順序に従って、対象リストをソートします。 * * @param list 対象リスト * @param comparator リスト要素を比較するために使用される comparator * @param args comparator の第5引数に渡すオブジェクト - * @return true/false (ソート成功/ソート失敗) */ static void KcLinkedList_sort(KcList *list, int (*comparator)(const void *element1, size_t size1, @@ -294,13 +318,43 @@ void *args) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; + kc_lock_guard(&(info->mutex)) { - KcLinkedList_sort_recur( - info, - info->head->next, - info->tail->prev, - comparator, args); + // Linked List エントリへのポインタを格納する配列を生成する。 + KcLinkedListEntry **ptr_list = (KcLinkedListEntry **)calloc( + info->size, sizeof(KcLinkedListEntry *)); + int idx = 0; + for (KcLinkedListEntry *entry = info->head->next; entry != info->tail; entry = entry->next) + { + ptr_list[idx] = entry; + idx++; + } + + // ソート処理 + KcListSortInfo sort_info; + sort_info.comparator = comparator; + sort_info.user_args = args; + + qsort_s( + ptr_list, + info->size, + sizeof(KcLinkedListEntry *), + KcLinkedList_comparator, + &sort_info); + + // 配列の情報を元にエントリを再構成する。 + KcLinkedListEntry *prev_entry = info->head; + for (int idx2 = 0; idx2 < (int)info->size; idx2++) + { + KcLinkedListEntry *entry = ptr_list[idx2]; + prev_entry->next = entry; + entry->prev = prev_entry; + prev_entry = entry; + } + prev_entry->next = info->tail; + info->tail->prev = prev_entry; + free(ptr_list); } } @@ -386,7 +440,7 @@ void *org_element, size_t *org_size) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; - bool is_success = true; + bool is_success = false; kc_lock_guard(&(info->mutex)) { KcLinkedListEntry *remove_entry = KcLinkedList_search(info, index); @@ -441,7 +495,6 @@ result_index = idx; break; } - entry = entry->next; idx++; } } @@ -467,16 +520,15 @@ int result_index = -1; kc_lock_guard(&(info->mutex)) { - int idx = 0; + int idx = info->size; for (KcLinkedListEntry *entry = info->tail->prev; entry != info->head; entry = entry->prev) { + idx--; if ((size == entry->size) && (memcmp(entry->value, element, entry->size) == 0)) { result_index = idx; break; } - entry = entry->next; - idx++; } } return result_index; @@ -639,83 +691,3 @@ } return entry; } - -//////////////////////////////////////////////////////////////////////////////// -// -// For Quick Sort -// - -/** - * 指定されたエントリを入れ替えます。 - * 同じエントリが渡された場合は何もしません。 - * - * @param entry1 入れ替えるエントリ1 - * @param entry2 入れ替えるエントリ2 - */ -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2) -{ - if (entry1 != entry2) - { - KcLinkedListEntry *temp = entry1->next; - entry1->next = entry2->next; - entry2->next = temp; - temp = entry1->prev; - entry1->prev = entry2->prev; - entry2->prev = temp; - } -} - -/** - * Quick Sort パーティション処理 - * - * @param info LinkedList 情報 - * @param low Low - * @param high High - * @param comparator 比較関数 - * @param args 比較関数に渡されるデータ - */ -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - KcLinkedListEntry *pivot = high; - KcLinkedListEntry *i = low->prev; - - for (KcLinkedListEntry *j = low; j != high; j = j->next) - { - int ret = comparator( - pivot->value, pivot->size, j->value, j->size, args); - if (ret >= 0) - { // j <= pivot - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, j); - } - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, high); - } - return i; -} - -/** - * Quick Sort 再帰処理 - */ -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - if ((high != info->tail) && (low != high) && (low != high->next)) - { - KcLinkedListEntry *p = KcLinkedList_sort_partition(info, low, high, comparator, args); - KcLinkedList_sort_recur(info, low, p->prev, comparator, args); - KcLinkedList_sort_recur(info, p->next, high, comparator, args); - } -} diff --git a/modules/test.c b/modules/test.c deleted file mode 100644 index 12d2d8f..0000000 --- a/modules/test.c +++ /dev/null @@ -1,36 +0,0 @@ -#include -#include -// #include -#include - - -void assert_equals_long(long expected, long actual) -{ - (void) expected; - (void) actual; - printf("-----\n"); -} -int add_i_i(int a, int b) -{ - return (a+b); -} -double add_i_d(int a, double b) -{ - printf("d\n"); - return (a + b); -} - -double add_d_d(double a, double b) -{ - printf("d d\n"); - return (a + b); -} -int main() -{ - // printf("%d\n", add(1,2)); - // printf("%d\n", add(1,2.2)); - // printf("%d\n", add(1.3,2)); - assert_equals(123,123); - return 0; -} - diff --git a/modules/include/kc_iterator.h b/modules/include/kc_iterator.h index d164fc1..562fd5e 100644 --- a/modules/include/kc_iterator.h +++ b/modules/include/kc_iterator.h @@ -40,15 +40,6 @@ */ const void *(*next)(struct KcIterator_ *ite, size_t *size); - /** - * 次の要素を取得します。 - * 格納している扱う要素が文字列の場合にのみ利用可能です。 - * - * @param ite Iterator オブジェクト - * @return 次の要素(文字列) - */ - const char *(*nextString)(struct KcIterator_ *ite); - /** 内部情報 */ void *_info; diff --git a/modules/src/kc_list.c b/modules/src/kc_list.c index a59e643..a5a97ce 100644 --- a/modules/src/kc_list.c +++ b/modules/src/kc_list.c @@ -13,9 +13,6 @@ */ void KcList_delete(KcList *list) { - if (list->cleanup_info) - { - list->cleanup_info(list); - } + list->cleanup_info(list); free(list); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index 9e746a1..a6a41c3 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -3,6 +3,10 @@ * @brief Linked リストモジュール * @copyright 2003 - 2023 Nomura Kei */ +#if defined(__GNUC__) +#define _GNU_SOURCE 1 +#define qsort_s qsort_r +#endif #include #include #include @@ -61,20 +65,6 @@ static KcLinkedListEntry *KcLinkedList_search(KcLinkedListInfo *info, int index); static KcLinkedListEntry *KcLinkedList_new_entry(const void *value, size_t size); -// [内部関数用] For Quick Sort -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2); -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); - /** * LinkedList を構築します。 * @@ -281,12 +271,46 @@ // ----------------------------------------------------------------------------- /** + * [内部利用] + * ソート情報 + */ +typedef struct +{ + int (*comparator)(const void *element1, size_t size1, + const void *element2, size_t size2, void *args); + size_t element_size; + void *user_args; +} KcListSortInfo; + +/** + * [内部利用] + * KcLinkedList_sort にて利用される、qsort_s に渡される comparator です。 + * + * @param x 比較する要素1 + * @param y 比較する要素2 + * @param context コンテキスト(KcListSortInfo) + * @return 比較結果 + */ +static int KcLinkedList_comparator(const void *x, const void *y, void *context) +{ + KcListSortInfo *sort_info = (KcListSortInfo *)context; + const KcLinkedListEntry **entry_x = (const KcLinkedListEntry **)x; + const KcLinkedListEntry **entry_y = (const KcLinkedListEntry **)y; + int ret = sort_info->comparator( + (*entry_x)->value, + (*entry_x)->size, + (*entry_y)->value, + (*entry_y)->size, + sort_info->user_args); + return ret; +} + +/** * 指定された comparator が示す順序に従って、対象リストをソートします。 * * @param list 対象リスト * @param comparator リスト要素を比較するために使用される comparator * @param args comparator の第5引数に渡すオブジェクト - * @return true/false (ソート成功/ソート失敗) */ static void KcLinkedList_sort(KcList *list, int (*comparator)(const void *element1, size_t size1, @@ -294,13 +318,43 @@ void *args) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; + kc_lock_guard(&(info->mutex)) { - KcLinkedList_sort_recur( - info, - info->head->next, - info->tail->prev, - comparator, args); + // Linked List エントリへのポインタを格納する配列を生成する。 + KcLinkedListEntry **ptr_list = (KcLinkedListEntry **)calloc( + info->size, sizeof(KcLinkedListEntry *)); + int idx = 0; + for (KcLinkedListEntry *entry = info->head->next; entry != info->tail; entry = entry->next) + { + ptr_list[idx] = entry; + idx++; + } + + // ソート処理 + KcListSortInfo sort_info; + sort_info.comparator = comparator; + sort_info.user_args = args; + + qsort_s( + ptr_list, + info->size, + sizeof(KcLinkedListEntry *), + KcLinkedList_comparator, + &sort_info); + + // 配列の情報を元にエントリを再構成する。 + KcLinkedListEntry *prev_entry = info->head; + for (int idx2 = 0; idx2 < (int)info->size; idx2++) + { + KcLinkedListEntry *entry = ptr_list[idx2]; + prev_entry->next = entry; + entry->prev = prev_entry; + prev_entry = entry; + } + prev_entry->next = info->tail; + info->tail->prev = prev_entry; + free(ptr_list); } } @@ -386,7 +440,7 @@ void *org_element, size_t *org_size) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; - bool is_success = true; + bool is_success = false; kc_lock_guard(&(info->mutex)) { KcLinkedListEntry *remove_entry = KcLinkedList_search(info, index); @@ -441,7 +495,6 @@ result_index = idx; break; } - entry = entry->next; idx++; } } @@ -467,16 +520,15 @@ int result_index = -1; kc_lock_guard(&(info->mutex)) { - int idx = 0; + int idx = info->size; for (KcLinkedListEntry *entry = info->tail->prev; entry != info->head; entry = entry->prev) { + idx--; if ((size == entry->size) && (memcmp(entry->value, element, entry->size) == 0)) { result_index = idx; break; } - entry = entry->next; - idx++; } } return result_index; @@ -639,83 +691,3 @@ } return entry; } - -//////////////////////////////////////////////////////////////////////////////// -// -// For Quick Sort -// - -/** - * 指定されたエントリを入れ替えます。 - * 同じエントリが渡された場合は何もしません。 - * - * @param entry1 入れ替えるエントリ1 - * @param entry2 入れ替えるエントリ2 - */ -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2) -{ - if (entry1 != entry2) - { - KcLinkedListEntry *temp = entry1->next; - entry1->next = entry2->next; - entry2->next = temp; - temp = entry1->prev; - entry1->prev = entry2->prev; - entry2->prev = temp; - } -} - -/** - * Quick Sort パーティション処理 - * - * @param info LinkedList 情報 - * @param low Low - * @param high High - * @param comparator 比較関数 - * @param args 比較関数に渡されるデータ - */ -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - KcLinkedListEntry *pivot = high; - KcLinkedListEntry *i = low->prev; - - for (KcLinkedListEntry *j = low; j != high; j = j->next) - { - int ret = comparator( - pivot->value, pivot->size, j->value, j->size, args); - if (ret >= 0) - { // j <= pivot - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, j); - } - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, high); - } - return i; -} - -/** - * Quick Sort 再帰処理 - */ -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - if ((high != info->tail) && (low != high) && (low != high->next)) - { - KcLinkedListEntry *p = KcLinkedList_sort_partition(info, low, high, comparator, args); - KcLinkedList_sort_recur(info, low, p->prev, comparator, args); - KcLinkedList_sort_recur(info, p->next, high, comparator, args); - } -} diff --git a/modules/test.c b/modules/test.c deleted file mode 100644 index 12d2d8f..0000000 --- a/modules/test.c +++ /dev/null @@ -1,36 +0,0 @@ -#include -#include -// #include -#include - - -void assert_equals_long(long expected, long actual) -{ - (void) expected; - (void) actual; - printf("-----\n"); -} -int add_i_i(int a, int b) -{ - return (a+b); -} -double add_i_d(int a, double b) -{ - printf("d\n"); - return (a + b); -} - -double add_d_d(double a, double b) -{ - printf("d d\n"); - return (a + b); -} -int main() -{ - // printf("%d\n", add(1,2)); - // printf("%d\n", add(1,2.2)); - // printf("%d\n", add(1.3,2)); - assert_equals(123,123); - return 0; -} - diff --git a/modules/test/src/test_list_linked.c b/modules/test/src/test_list_linked.c new file mode 100644 index 0000000..a542d7b --- /dev/null +++ b/modules/test/src/test_list_linked.c @@ -0,0 +1,523 @@ +#include +#include + +#include +#include +#include +#include +#include + +// プロトタイプ宣言 +static void test_list_linked_new(void); +static void test_list_linked_add(void); +static void test_list_linked_remove(void); +static void test_list_linked_set(void); +static void test_list_linked_search(void); +static void test_list_linked_sort(void); +static void test_list_linked_malloc_error(void); + +/** + * LinkedList 単体テストスイート + */ +void suite_list_linked(void) +{ + KcUt *ut = KcUt_get_instance(); + ut->add(ut, UT_TESTCASE, "list_linked new LinkedList", test_list_linked_new); + ut->add(ut, UT_TESTCASE, "list_linked add/get", test_list_linked_add); + ut->add(ut, UT_TESTCASE, "list_linked remove", test_list_linked_remove); + ut->add(ut, UT_TESTCASE, "list_linked set", test_list_linked_set); + ut->add(ut, UT_TESTCASE, "list_linked search", test_list_linked_search); + ut->add(ut, UT_TESTCASE, "list_linked sort", test_list_linked_sort); + ut->add(ut, UT_TESTCASE, "list_linked malloc error", test_list_linked_malloc_error); +} + +/** + * LinkedList 生成/破棄。 + * + * @process KcList_new_LinkedList を実行する。。 + * @result LinkedList が生成されること。 + * + * @process KcList_delete にて LinkedList を破棄する。 + * @result LinkedList が破棄されること。 + */ +static void test_list_linked_new(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + KcList_delete(list); +} + +/** + * LinkedList データ追加/取得。 + * + * @process 初回追加 (index = 0) + * @process 2つめ追加 (index = 1) + * @process 先頭に追加 (index = 0) + * @process 末尾に追加 (index = 負値(-1)) + * @process 追加(index 不正) + * @process 値取得(サイズ取得あり) + * @process 値取得(サイズ取得なし) + * @process 値取得 (index 不正[負の値を指定]) + * @process 値取得 (index 不正[サイズ以上を指定]) + */ +static void test_list_linked_add(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 空 + bool is_empty = list->is_empty(list); + assert_true(is_empty); + + // 1つめ追加 + int val = 10; + bool res = list->add(list, 0, &val, sizeof(int)); + assert_true(res); + is_empty = list->is_empty(list); + assert_false(is_empty); + + // 2つめ追加 + val = 20; + res = list->add(list, 1, &val, sizeof(int)); + assert_true(res); + + // 先頭に追加 + val = 30; + res = list->add(list, 0, &val, sizeof(int)); + assert_true(res); + + // 末尾に追加 + val = 40; + res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + + // 追加不可位置への追加 + val = 50; + res = list->add(list, 10, &val, sizeof(int)); + assert_false(res); + + // 1つめ取得 + size_t size; + int *res_val = list->get(list, 0, &size); + assert_equals((int)sizeof(int), (int)size); + assert_equals(30, *res_val); + + // 2つめ取得 + res_val = list->get(list, 1, &size); + assert_equals((int)sizeof(int), (int)size); + assert_equals(10, *res_val); + + // 3つめ取得(サイズ取得なし) + res_val = list->get(list, 2, NULL); + assert_equals(20, *res_val); + + // 4つめ取得(サイズ取得なし) + res_val = list->get(list, 3, NULL); + assert_equals(40, *res_val); + + // 値取得 (index 不正[負の値を指定]) + res_val = list->get(list, -1, NULL); + assert_null(res_val); + + // 値取得 (index 不正[サイズを指定]) + res_val = list->get(list, 4, NULL); + assert_null(res_val); + + // 値取得 (index 不正[サイズ以上を指定]) + res_val = list->get(list, 5, NULL); + assert_null(res_val); + + KcList_delete(list); +} + +/** + * LinkedList データ削除。 + * + * @process 末尾削除 + * @process 中間削除 + * @process 先頭削除 + * @process 削除(index 不正[負の値を指定]) + * @process 削除(index 不正[サイズ以上を指定]) + * @process 残っているデータを確認 + * @process 容量調整(初期容量→1/4以下) + */ +static void test_list_linked_remove(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160}; + int default_size = 16; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + + // 末尾削除 (値、サイズ取得あり) + int rval; + size_t rsize = sizeof(int); + bool ret = list->remove(list, (default_size - 1), &rval, &rsize); + assert_true(ret); + assert_equals(vals[(default_size - 1)], rval); + assert_equals((int)sizeof(int), (int)rsize); + int now_size = list->size(list); + assert_equals((default_size - 1), now_size); + + // 値を追加して戻しておく + list->add(list, (default_size - 1), &vals[(default_size - 1)], sizeof(int)); + now_size = list->size(list); + assert_equals(default_size, now_size); + + // 中間削除 (値取得設定あり、サイズ指定なし [=値取得できない]) + // 10, 20, <30>, 40, 50, ... + rval = 9999; + ret = list->remove(list, 2, &rval, NULL); + assert_true(ret); + assert_equals(9999, rval); // size 指定なしのため、値は取得できない。 + now_size = list->size(list); + assert_equals((default_size - 1), now_size); + + // 先頭削除 (値取得なし) + // <10>, 20, 40, 50, ... + ret = list->remove(list, 0, NULL, NULL); + assert_true(ret); + now_size = list->size(list); + assert_equals((default_size - 2), now_size); + + // 削除(index 不正[負の値指定]) + ret = list->remove(list, -1, NULL, NULL); + assert_false(ret); + + // 削除(index 不正[サイズ以上を指定]) + ret = list->remove(list, default_size, NULL, NULL); + assert_false(ret); + + // 残り3つになるまで削除 (3つめを削除) + int rest_size = list->size(list); + while (rest_size > 3) + { + ret = list->remove(list, 3, NULL, NULL); + assert_true(ret); + rest_size = list->size(list); + } + + // 残っているデータの確認 + // 20, 40, 50 + int *res_val_1 = list->get(list, 0, NULL); + int *res_val_2 = list->get(list, 1, NULL); + int *res_val_3 = list->get(list, 2, NULL); + assert_equals(20, *res_val_1); + assert_equals(40, *res_val_2); + assert_equals(50, *res_val_3); + + bool is_empty = list->is_empty(list); + assert_false(is_empty); + + // クリア + list->clear(list); + is_empty = list->is_empty(list); + assert_true(is_empty); + + KcList_delete(list); +} + +/** + * LinkedList データ設定。 + * + * @process 値設定(複数設定) + * @process 値設定(元の値、サイズ取得) + * @process 値設定(元の値取得) + * @process 値設定(不正index[負の値指定]) + * @process 値設定(不正index[サイズ以上指定]) + */ +static void test_list_linked_set(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 20, 30, 40, 50}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(5, now_size); + + // 値設定 (元の値, サイズ取得) + int set_value = 99; + int orig_val = 9999; + size_t orig_size = sizeof(int); + bool ret = list->set(list, 1, &set_value, sizeof(int), &orig_val, &orig_size); + assert_true(ret); + assert_equals(20, orig_val); + assert_equals((int)sizeof(int), (int)orig_size); + int *res_val = list->get(list, 1, NULL); + assert_equals(99, *res_val); + + // 値設定 (元の値取得, サイズ指定なし[=値取得不可]) + set_value = 98; + orig_val = 9999; + ret = list->set(list, 0, &set_value, sizeof(int), &orig_val, NULL); + assert_true(ret); + assert_equals(9999, orig_val); // size 指定なしのため、値取得不可 + res_val = list->get(list, 0, NULL); + assert_equals(98, *res_val); + + // 値設定 (サイズ取得 [=値指定なしのためサイズ取得不可]) + set_value = 97; + orig_size = 0; + ret = list->set(list, 0, &set_value, sizeof(int), NULL, &orig_size); + assert_true(ret); + assert_equals(0, (int)orig_size); // size 取得不可 + res_val = list->get(list, 0, NULL); + assert_equals(97, *res_val); + + now_size = list->size(list); + assert_equals(5, now_size); + + // 値設定(不正index[負の値指定]) + set_value = 96; + ret = list->set(list, -1, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + // 値設定(不正index[サイズ指定]) + set_value = 95; + ret = list->set(list, 5, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + // 値設定(不正index[サイズ以上指定]) + set_value = 95; + ret = list->set(list, 6, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + KcList_delete(list); +} + +/** + * LinkedList 検索。 + * + * @process リスト {10, 30, 50, 40, 20, 10, 30, 60, 20 } を構築する。 + * @result リストが構築されること + * + * @process is_contains でリストに含まれる値を確認する。 + * @result true が返されること。 + * + * @process index_of で各インデックス位置を取得する。 + * @result 先頭からのインデックス位置が正しく取得されること。 + * + * @process last_index_of で各インデックス位置を取得する。 + * @result 末尾からのインデックス位置が正しく取得されること。 + * + * @process リストに含まれない値を指定して、is_contains を実行する。 + * @result false が返されること。 + * + * @process リストに含まれない値を指定して、index_of を実行する。 + * @result -1 が返されること。 + * + * @process リストに含まれない値を指定して、last_index_of を実行する。 + * @result -1 が返されること。 + * + * @process 異なるサイズ指定して、is_contains を実行する。 + * @result -1 が返されること。 + * + */ +static void test_list_linked_search(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 30, 50, 40, 20, 10, 30, 60, 20}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(9, now_size); + + // 値が含まれることの確認 + // index_of, last_index_of の確認 + int c_vals[] = {10, 20, 30, 40, 50, 60}; + int c_vals_index[] = {0, 4, 1, 3, 2, 7}; + int c_vals_lindex[] = {5, 8, 6, 3, 2, 7}; + bool is_contains; + int res_index; + int res_lindex; + for (int i = 0; i < (int)(sizeof(c_vals) / sizeof(int)); i++) + { + is_contains = list->contains(list, &c_vals[i], sizeof(int)); + assert_true(is_contains); + + res_index = list->index_of(list, &c_vals[i], sizeof(int)); + assert_equals(c_vals_index[i], res_index); + + res_lindex = list->last_index_of(list, &c_vals[i], sizeof(int)); + assert_equals(c_vals_lindex[i], res_lindex); + } + + // 値が含まれないことの確認 + int c_val = 99; + is_contains = list->contains(list, &c_val, sizeof(int)); + assert_false(is_contains); + + res_index = list->index_of(list, &c_val, sizeof(int)); + assert_equals(-1, res_index); + + res_lindex = list->last_index_of(list, &c_val, sizeof(int)); + assert_equals(-1, res_lindex); + + // 値が含まれないことの確認(異なるサイズ指定) + c_val = 10; + is_contains = list->contains(list, &c_val, sizeof(int) * 2); + assert_false(is_contains); + + res_index = list->index_of(list, &c_val, sizeof(int) * 2); + assert_equals(-1, res_index); + + res_lindex = list->last_index_of(list, &c_val, sizeof(int) * 2); + assert_equals(-1, res_lindex); + + KcList_delete(list); +} + +// ソート用コンパレータ +static int test_list_linked_sort_comparator( + const void *element1, size_t size1, + const void *element2, size_t size2, + void *args) +{ + int val1 = *((int *)element1); + int val2 = *((int *)element2); + assert_equals((int)sizeof(int), (int)size1); + assert_equals((int)sizeof(int), (int)size2); + assert_equals("ABCDEFG", (const char *)args); + return (val1 - val2); +} + +/** + * LinkedList ソート。 + * + * @process リスト {10, 30, 50, 40, 20, 10, 30, 60, 20} を構築する。 + * @result リストが構築されること。 + * + * @process 昇順用コンパレータを渡し、ソートする。 + * @result リストがソートされること。 + * + * @process Iterator を取得する。 + * @result Iterator にて順次値が取得できること。 + */ +static void test_list_linked_sort(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 30, 50, 40, 20, 10, 30, 60, 20}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(9, now_size); + + // ソート実施 + list->sort(list, test_list_linked_sort_comparator, "ABCDEFG"); + int sorted_vals[] = {10, 10, 20, 20, 30, 30, 40, 50, 60}; + + // Iterator にて値を取得＆確認 + KcIterator *ite = list->iterator(list, 0); + int sorted_index = 0; + while (ite->hasNext(ite)) + { + size_t res_size; + int *res_val = (int *)ite->next(ite, &res_size); + assert_equals((int)sizeof(int), (int)res_size); + assert_equals(sorted_vals[sorted_index], *res_val); + sorted_index++; + } + KcIterator_delete(ite); + + // index = 5 より取得 + ite = list->iterator(list, 5); + sorted_index = 5; + while (ite->hasNext(ite)) + { + int *res_val = (int *)ite->next(ite, NULL); + assert_equals(sorted_vals[sorted_index], *res_val); + sorted_index++; + } + KcIterator_delete(ite); + + KcList_delete(list); +} + +#include "ut.h" +static int UT_ListLinked_can_alloc_counter = 0; +static bool UT_ListLinked_can_alloc( + KcMemoryEntry *entry, size_t alignment, size_t size, + KcMemoryMark mark, const char *file, const char *func, int line) +{ + UNUSED_VARIABLE(entry); + UNUSED_VARIABLE(alignment); + UNUSED_VARIABLE(size); + UNUSED_VARIABLE(mark); + UNUSED_VARIABLE(file); + UNUSED_VARIABLE(func); + UNUSED_VARIABLE(line); + + UT_ListLinked_can_alloc_counter--; + if (UT_ListLinked_can_alloc_counter < 0) + { + return false; + } + return true; +} + +/** + * LinkedList メモリ確保失敗。 + */ +static void test_list_linked_malloc_error(void) +{ + // LinkedList のメモリ確保失敗 + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + KcList *list = KcList_new_LinkedList(); + _UT_KcMemory_can_alloc = NULL; + assert_null(list); + + // LinkedList の add 時のメモリ確保失敗 + list = KcList_new_LinkedList(); + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + bool ret = list->add(list, 0, "ABC", 4); + _UT_KcMemory_can_alloc = NULL; + assert_false(ret); + assert_equals(0, list->size(list)); + + // Iterator 生成時のメモリ確保失敗 + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + KcIterator *ite = list->iterator(list, 0); + _UT_KcMemory_can_alloc = NULL; + assert_null(ite); + + // set 時のメモリ確保失敗 + list->add(list, 0, "ABC", 4); + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + list->set(list, 0, "XYZXYZ", 7, NULL, NULL); + _UT_KcMemory_can_alloc = NULL; + assert_equals("ABC", (const char *)list->get(list, 0, NULL)); + + KcList_delete(list); +} \ No newline at end of file diff --git a/modules/include/kc_iterator.h b/modules/include/kc_iterator.h index d164fc1..562fd5e 100644 --- a/modules/include/kc_iterator.h +++ b/modules/include/kc_iterator.h @@ -40,15 +40,6 @@ */ const void *(*next)(struct KcIterator_ *ite, size_t *size); - /** - * 次の要素を取得します。 - * 格納している扱う要素が文字列の場合にのみ利用可能です。 - * - * @param ite Iterator オブジェクト - * @return 次の要素(文字列) - */ - const char *(*nextString)(struct KcIterator_ *ite); - /** 内部情報 */ void *_info; diff --git a/modules/src/kc_list.c b/modules/src/kc_list.c index a59e643..a5a97ce 100644 --- a/modules/src/kc_list.c +++ b/modules/src/kc_list.c @@ -13,9 +13,6 @@ */ void KcList_delete(KcList *list) { - if (list->cleanup_info) - { - list->cleanup_info(list); - } + list->cleanup_info(list); free(list); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index 9e746a1..a6a41c3 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -3,6 +3,10 @@ * @brief Linked リストモジュール * @copyright 2003 - 2023 Nomura Kei */ +#if defined(__GNUC__) +#define _GNU_SOURCE 1 +#define qsort_s qsort_r +#endif #include #include #include @@ -61,20 +65,6 @@ static KcLinkedListEntry *KcLinkedList_search(KcLinkedListInfo *info, int index); static KcLinkedListEntry *KcLinkedList_new_entry(const void *value, size_t size); -// [内部関数用] For Quick Sort -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2); -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); - /** * LinkedList を構築します。 * @@ -281,12 +271,46 @@ // ----------------------------------------------------------------------------- /** + * [内部利用] + * ソート情報 + */ +typedef struct +{ + int (*comparator)(const void *element1, size_t size1, + const void *element2, size_t size2, void *args); + size_t element_size; + void *user_args; +} KcListSortInfo; + +/** + * [内部利用] + * KcLinkedList_sort にて利用される、qsort_s に渡される comparator です。 + * + * @param x 比較する要素1 + * @param y 比較する要素2 + * @param context コンテキスト(KcListSortInfo) + * @return 比較結果 + */ +static int KcLinkedList_comparator(const void *x, const void *y, void *context) +{ + KcListSortInfo *sort_info = (KcListSortInfo *)context; + const KcLinkedListEntry **entry_x = (const KcLinkedListEntry **)x; + const KcLinkedListEntry **entry_y = (const KcLinkedListEntry **)y; + int ret = sort_info->comparator( + (*entry_x)->value, + (*entry_x)->size, + (*entry_y)->value, + (*entry_y)->size, + sort_info->user_args); + return ret; +} + +/** * 指定された comparator が示す順序に従って、対象リストをソートします。 * * @param list 対象リスト * @param comparator リスト要素を比較するために使用される comparator * @param args comparator の第5引数に渡すオブジェクト - * @return true/false (ソート成功/ソート失敗) */ static void KcLinkedList_sort(KcList *list, int (*comparator)(const void *element1, size_t size1, @@ -294,13 +318,43 @@ void *args) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; + kc_lock_guard(&(info->mutex)) { - KcLinkedList_sort_recur( - info, - info->head->next, - info->tail->prev, - comparator, args); + // Linked List エントリへのポインタを格納する配列を生成する。 + KcLinkedListEntry **ptr_list = (KcLinkedListEntry **)calloc( + info->size, sizeof(KcLinkedListEntry *)); + int idx = 0; + for (KcLinkedListEntry *entry = info->head->next; entry != info->tail; entry = entry->next) + { + ptr_list[idx] = entry; + idx++; + } + + // ソート処理 + KcListSortInfo sort_info; + sort_info.comparator = comparator; + sort_info.user_args = args; + + qsort_s( + ptr_list, + info->size, + sizeof(KcLinkedListEntry *), + KcLinkedList_comparator, + &sort_info); + + // 配列の情報を元にエントリを再構成する。 + KcLinkedListEntry *prev_entry = info->head; + for (int idx2 = 0; idx2 < (int)info->size; idx2++) + { + KcLinkedListEntry *entry = ptr_list[idx2]; + prev_entry->next = entry; + entry->prev = prev_entry; + prev_entry = entry; + } + prev_entry->next = info->tail; + info->tail->prev = prev_entry; + free(ptr_list); } } @@ -386,7 +440,7 @@ void *org_element, size_t *org_size) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; - bool is_success = true; + bool is_success = false; kc_lock_guard(&(info->mutex)) { KcLinkedListEntry *remove_entry = KcLinkedList_search(info, index); @@ -441,7 +495,6 @@ result_index = idx; break; } - entry = entry->next; idx++; } } @@ -467,16 +520,15 @@ int result_index = -1; kc_lock_guard(&(info->mutex)) { - int idx = 0; + int idx = info->size; for (KcLinkedListEntry *entry = info->tail->prev; entry != info->head; entry = entry->prev) { + idx--; if ((size == entry->size) && (memcmp(entry->value, element, entry->size) == 0)) { result_index = idx; break; } - entry = entry->next; - idx++; } } return result_index; @@ -639,83 +691,3 @@ } return entry; } - -//////////////////////////////////////////////////////////////////////////////// -// -// For Quick Sort -// - -/** - * 指定されたエントリを入れ替えます。 - * 同じエントリが渡された場合は何もしません。 - * - * @param entry1 入れ替えるエントリ1 - * @param entry2 入れ替えるエントリ2 - */ -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2) -{ - if (entry1 != entry2) - { - KcLinkedListEntry *temp = entry1->next; - entry1->next = entry2->next; - entry2->next = temp; - temp = entry1->prev; - entry1->prev = entry2->prev; - entry2->prev = temp; - } -} - -/** - * Quick Sort パーティション処理 - * - * @param info LinkedList 情報 - * @param low Low - * @param high High - * @param comparator 比較関数 - * @param args 比較関数に渡されるデータ - */ -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - KcLinkedListEntry *pivot = high; - KcLinkedListEntry *i = low->prev; - - for (KcLinkedListEntry *j = low; j != high; j = j->next) - { - int ret = comparator( - pivot->value, pivot->size, j->value, j->size, args); - if (ret >= 0) - { // j <= pivot - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, j); - } - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, high); - } - return i; -} - -/** - * Quick Sort 再帰処理 - */ -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - if ((high != info->tail) && (low != high) && (low != high->next)) - { - KcLinkedListEntry *p = KcLinkedList_sort_partition(info, low, high, comparator, args); - KcLinkedList_sort_recur(info, low, p->prev, comparator, args); - KcLinkedList_sort_recur(info, p->next, high, comparator, args); - } -} diff --git a/modules/test.c b/modules/test.c deleted file mode 100644 index 12d2d8f..0000000 --- a/modules/test.c +++ /dev/null @@ -1,36 +0,0 @@ -#include -#include -// #include -#include - - -void assert_equals_long(long expected, long actual) -{ - (void) expected; - (void) actual; - printf("-----\n"); -} -int add_i_i(int a, int b) -{ - return (a+b); -} -double add_i_d(int a, double b) -{ - printf("d\n"); - return (a + b); -} - -double add_d_d(double a, double b) -{ - printf("d d\n"); - return (a + b); -} -int main() -{ - // printf("%d\n", add(1,2)); - // printf("%d\n", add(1,2.2)); - // printf("%d\n", add(1.3,2)); - assert_equals(123,123); - return 0; -} - diff --git a/modules/test/src/test_list_linked.c b/modules/test/src/test_list_linked.c new file mode 100644 index 0000000..a542d7b --- /dev/null +++ b/modules/test/src/test_list_linked.c @@ -0,0 +1,523 @@ +#include +#include + +#include +#include +#include +#include +#include + +// プロトタイプ宣言 +static void test_list_linked_new(void); +static void test_list_linked_add(void); +static void test_list_linked_remove(void); +static void test_list_linked_set(void); +static void test_list_linked_search(void); +static void test_list_linked_sort(void); +static void test_list_linked_malloc_error(void); + +/** + * LinkedList 単体テストスイート + */ +void suite_list_linked(void) +{ + KcUt *ut = KcUt_get_instance(); + ut->add(ut, UT_TESTCASE, "list_linked new LinkedList", test_list_linked_new); + ut->add(ut, UT_TESTCASE, "list_linked add/get", test_list_linked_add); + ut->add(ut, UT_TESTCASE, "list_linked remove", test_list_linked_remove); + ut->add(ut, UT_TESTCASE, "list_linked set", test_list_linked_set); + ut->add(ut, UT_TESTCASE, "list_linked search", test_list_linked_search); + ut->add(ut, UT_TESTCASE, "list_linked sort", test_list_linked_sort); + ut->add(ut, UT_TESTCASE, "list_linked malloc error", test_list_linked_malloc_error); +} + +/** + * LinkedList 生成/破棄。 + * + * @process KcList_new_LinkedList を実行する。。 + * @result LinkedList が生成されること。 + * + * @process KcList_delete にて LinkedList を破棄する。 + * @result LinkedList が破棄されること。 + */ +static void test_list_linked_new(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + KcList_delete(list); +} + +/** + * LinkedList データ追加/取得。 + * + * @process 初回追加 (index = 0) + * @process 2つめ追加 (index = 1) + * @process 先頭に追加 (index = 0) + * @process 末尾に追加 (index = 負値(-1)) + * @process 追加(index 不正) + * @process 値取得(サイズ取得あり) + * @process 値取得(サイズ取得なし) + * @process 値取得 (index 不正[負の値を指定]) + * @process 値取得 (index 不正[サイズ以上を指定]) + */ +static void test_list_linked_add(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 空 + bool is_empty = list->is_empty(list); + assert_true(is_empty); + + // 1つめ追加 + int val = 10; + bool res = list->add(list, 0, &val, sizeof(int)); + assert_true(res); + is_empty = list->is_empty(list); + assert_false(is_empty); + + // 2つめ追加 + val = 20; + res = list->add(list, 1, &val, sizeof(int)); + assert_true(res); + + // 先頭に追加 + val = 30; + res = list->add(list, 0, &val, sizeof(int)); + assert_true(res); + + // 末尾に追加 + val = 40; + res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + + // 追加不可位置への追加 + val = 50; + res = list->add(list, 10, &val, sizeof(int)); + assert_false(res); + + // 1つめ取得 + size_t size; + int *res_val = list->get(list, 0, &size); + assert_equals((int)sizeof(int), (int)size); + assert_equals(30, *res_val); + + // 2つめ取得 + res_val = list->get(list, 1, &size); + assert_equals((int)sizeof(int), (int)size); + assert_equals(10, *res_val); + + // 3つめ取得(サイズ取得なし) + res_val = list->get(list, 2, NULL); + assert_equals(20, *res_val); + + // 4つめ取得(サイズ取得なし) + res_val = list->get(list, 3, NULL); + assert_equals(40, *res_val); + + // 値取得 (index 不正[負の値を指定]) + res_val = list->get(list, -1, NULL); + assert_null(res_val); + + // 値取得 (index 不正[サイズを指定]) + res_val = list->get(list, 4, NULL); + assert_null(res_val); + + // 値取得 (index 不正[サイズ以上を指定]) + res_val = list->get(list, 5, NULL); + assert_null(res_val); + + KcList_delete(list); +} + +/** + * LinkedList データ削除。 + * + * @process 末尾削除 + * @process 中間削除 + * @process 先頭削除 + * @process 削除(index 不正[負の値を指定]) + * @process 削除(index 不正[サイズ以上を指定]) + * @process 残っているデータを確認 + * @process 容量調整(初期容量→1/4以下) + */ +static void test_list_linked_remove(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160}; + int default_size = 16; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + + // 末尾削除 (値、サイズ取得あり) + int rval; + size_t rsize = sizeof(int); + bool ret = list->remove(list, (default_size - 1), &rval, &rsize); + assert_true(ret); + assert_equals(vals[(default_size - 1)], rval); + assert_equals((int)sizeof(int), (int)rsize); + int now_size = list->size(list); + assert_equals((default_size - 1), now_size); + + // 値を追加して戻しておく + list->add(list, (default_size - 1), &vals[(default_size - 1)], sizeof(int)); + now_size = list->size(list); + assert_equals(default_size, now_size); + + // 中間削除 (値取得設定あり、サイズ指定なし [=値取得できない]) + // 10, 20, <30>, 40, 50, ... + rval = 9999; + ret = list->remove(list, 2, &rval, NULL); + assert_true(ret); + assert_equals(9999, rval); // size 指定なしのため、値は取得できない。 + now_size = list->size(list); + assert_equals((default_size - 1), now_size); + + // 先頭削除 (値取得なし) + // <10>, 20, 40, 50, ... + ret = list->remove(list, 0, NULL, NULL); + assert_true(ret); + now_size = list->size(list); + assert_equals((default_size - 2), now_size); + + // 削除(index 不正[負の値指定]) + ret = list->remove(list, -1, NULL, NULL); + assert_false(ret); + + // 削除(index 不正[サイズ以上を指定]) + ret = list->remove(list, default_size, NULL, NULL); + assert_false(ret); + + // 残り3つになるまで削除 (3つめを削除) + int rest_size = list->size(list); + while (rest_size > 3) + { + ret = list->remove(list, 3, NULL, NULL); + assert_true(ret); + rest_size = list->size(list); + } + + // 残っているデータの確認 + // 20, 40, 50 + int *res_val_1 = list->get(list, 0, NULL); + int *res_val_2 = list->get(list, 1, NULL); + int *res_val_3 = list->get(list, 2, NULL); + assert_equals(20, *res_val_1); + assert_equals(40, *res_val_2); + assert_equals(50, *res_val_3); + + bool is_empty = list->is_empty(list); + assert_false(is_empty); + + // クリア + list->clear(list); + is_empty = list->is_empty(list); + assert_true(is_empty); + + KcList_delete(list); +} + +/** + * LinkedList データ設定。 + * + * @process 値設定(複数設定) + * @process 値設定(元の値、サイズ取得) + * @process 値設定(元の値取得) + * @process 値設定(不正index[負の値指定]) + * @process 値設定(不正index[サイズ以上指定]) + */ +static void test_list_linked_set(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 20, 30, 40, 50}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(5, now_size); + + // 値設定 (元の値, サイズ取得) + int set_value = 99; + int orig_val = 9999; + size_t orig_size = sizeof(int); + bool ret = list->set(list, 1, &set_value, sizeof(int), &orig_val, &orig_size); + assert_true(ret); + assert_equals(20, orig_val); + assert_equals((int)sizeof(int), (int)orig_size); + int *res_val = list->get(list, 1, NULL); + assert_equals(99, *res_val); + + // 値設定 (元の値取得, サイズ指定なし[=値取得不可]) + set_value = 98; + orig_val = 9999; + ret = list->set(list, 0, &set_value, sizeof(int), &orig_val, NULL); + assert_true(ret); + assert_equals(9999, orig_val); // size 指定なしのため、値取得不可 + res_val = list->get(list, 0, NULL); + assert_equals(98, *res_val); + + // 値設定 (サイズ取得 [=値指定なしのためサイズ取得不可]) + set_value = 97; + orig_size = 0; + ret = list->set(list, 0, &set_value, sizeof(int), NULL, &orig_size); + assert_true(ret); + assert_equals(0, (int)orig_size); // size 取得不可 + res_val = list->get(list, 0, NULL); + assert_equals(97, *res_val); + + now_size = list->size(list); + assert_equals(5, now_size); + + // 値設定(不正index[負の値指定]) + set_value = 96; + ret = list->set(list, -1, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + // 値設定(不正index[サイズ指定]) + set_value = 95; + ret = list->set(list, 5, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + // 値設定(不正index[サイズ以上指定]) + set_value = 95; + ret = list->set(list, 6, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + KcList_delete(list); +} + +/** + * LinkedList 検索。 + * + * @process リスト {10, 30, 50, 40, 20, 10, 30, 60, 20 } を構築する。 + * @result リストが構築されること + * + * @process is_contains でリストに含まれる値を確認する。 + * @result true が返されること。 + * + * @process index_of で各インデックス位置を取得する。 + * @result 先頭からのインデックス位置が正しく取得されること。 + * + * @process last_index_of で各インデックス位置を取得する。 + * @result 末尾からのインデックス位置が正しく取得されること。 + * + * @process リストに含まれない値を指定して、is_contains を実行する。 + * @result false が返されること。 + * + * @process リストに含まれない値を指定して、index_of を実行する。 + * @result -1 が返されること。 + * + * @process リストに含まれない値を指定して、last_index_of を実行する。 + * @result -1 が返されること。 + * + * @process 異なるサイズ指定して、is_contains を実行する。 + * @result -1 が返されること。 + * + */ +static void test_list_linked_search(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 30, 50, 40, 20, 10, 30, 60, 20}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(9, now_size); + + // 値が含まれることの確認 + // index_of, last_index_of の確認 + int c_vals[] = {10, 20, 30, 40, 50, 60}; + int c_vals_index[] = {0, 4, 1, 3, 2, 7}; + int c_vals_lindex[] = {5, 8, 6, 3, 2, 7}; + bool is_contains; + int res_index; + int res_lindex; + for (int i = 0; i < (int)(sizeof(c_vals) / sizeof(int)); i++) + { + is_contains = list->contains(list, &c_vals[i], sizeof(int)); + assert_true(is_contains); + + res_index = list->index_of(list, &c_vals[i], sizeof(int)); + assert_equals(c_vals_index[i], res_index); + + res_lindex = list->last_index_of(list, &c_vals[i], sizeof(int)); + assert_equals(c_vals_lindex[i], res_lindex); + } + + // 値が含まれないことの確認 + int c_val = 99; + is_contains = list->contains(list, &c_val, sizeof(int)); + assert_false(is_contains); + + res_index = list->index_of(list, &c_val, sizeof(int)); + assert_equals(-1, res_index); + + res_lindex = list->last_index_of(list, &c_val, sizeof(int)); + assert_equals(-1, res_lindex); + + // 値が含まれないことの確認(異なるサイズ指定) + c_val = 10; + is_contains = list->contains(list, &c_val, sizeof(int) * 2); + assert_false(is_contains); + + res_index = list->index_of(list, &c_val, sizeof(int) * 2); + assert_equals(-1, res_index); + + res_lindex = list->last_index_of(list, &c_val, sizeof(int) * 2); + assert_equals(-1, res_lindex); + + KcList_delete(list); +} + +// ソート用コンパレータ +static int test_list_linked_sort_comparator( + const void *element1, size_t size1, + const void *element2, size_t size2, + void *args) +{ + int val1 = *((int *)element1); + int val2 = *((int *)element2); + assert_equals((int)sizeof(int), (int)size1); + assert_equals((int)sizeof(int), (int)size2); + assert_equals("ABCDEFG", (const char *)args); + return (val1 - val2); +} + +/** + * LinkedList ソート。 + * + * @process リスト {10, 30, 50, 40, 20, 10, 30, 60, 20} を構築する。 + * @result リストが構築されること。 + * + * @process 昇順用コンパレータを渡し、ソートする。 + * @result リストがソートされること。 + * + * @process Iterator を取得する。 + * @result Iterator にて順次値が取得できること。 + */ +static void test_list_linked_sort(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 30, 50, 40, 20, 10, 30, 60, 20}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(9, now_size); + + // ソート実施 + list->sort(list, test_list_linked_sort_comparator, "ABCDEFG"); + int sorted_vals[] = {10, 10, 20, 20, 30, 30, 40, 50, 60}; + + // Iterator にて値を取得＆確認 + KcIterator *ite = list->iterator(list, 0); + int sorted_index = 0; + while (ite->hasNext(ite)) + { + size_t res_size; + int *res_val = (int *)ite->next(ite, &res_size); + assert_equals((int)sizeof(int), (int)res_size); + assert_equals(sorted_vals[sorted_index], *res_val); + sorted_index++; + } + KcIterator_delete(ite); + + // index = 5 より取得 + ite = list->iterator(list, 5); + sorted_index = 5; + while (ite->hasNext(ite)) + { + int *res_val = (int *)ite->next(ite, NULL); + assert_equals(sorted_vals[sorted_index], *res_val); + sorted_index++; + } + KcIterator_delete(ite); + + KcList_delete(list); +} + +#include "ut.h" +static int UT_ListLinked_can_alloc_counter = 0; +static bool UT_ListLinked_can_alloc( + KcMemoryEntry *entry, size_t alignment, size_t size, + KcMemoryMark mark, const char *file, const char *func, int line) +{ + UNUSED_VARIABLE(entry); + UNUSED_VARIABLE(alignment); + UNUSED_VARIABLE(size); + UNUSED_VARIABLE(mark); + UNUSED_VARIABLE(file); + UNUSED_VARIABLE(func); + UNUSED_VARIABLE(line); + + UT_ListLinked_can_alloc_counter--; + if (UT_ListLinked_can_alloc_counter < 0) + { + return false; + } + return true; +} + +/** + * LinkedList メモリ確保失敗。 + */ +static void test_list_linked_malloc_error(void) +{ + // LinkedList のメモリ確保失敗 + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + KcList *list = KcList_new_LinkedList(); + _UT_KcMemory_can_alloc = NULL; + assert_null(list); + + // LinkedList の add 時のメモリ確保失敗 + list = KcList_new_LinkedList(); + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + bool ret = list->add(list, 0, "ABC", 4); + _UT_KcMemory_can_alloc = NULL; + assert_false(ret); + assert_equals(0, list->size(list)); + + // Iterator 生成時のメモリ確保失敗 + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + KcIterator *ite = list->iterator(list, 0); + _UT_KcMemory_can_alloc = NULL; + assert_null(ite); + + // set 時のメモリ確保失敗 + list->add(list, 0, "ABC", 4); + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + list->set(list, 0, "XYZXYZ", 7, NULL, NULL); + _UT_KcMemory_can_alloc = NULL; + assert_equals("ABC", (const char *)list->get(list, 0, NULL)); + + KcList_delete(list); +} \ No newline at end of file diff --git a/modules/test/src/ut.c b/modules/test/src/ut.c index ed34d55..1af0683 100644 --- a/modules/test/src/ut.c +++ b/modules/test/src/ut.c @@ -10,6 +10,7 @@ // UT Setup suite_assert(); suite_list_array(); + suite_list_linked(); suite_lock_guard(); suite_memory_dump(); suite_memory_entry(); diff --git a/modules/include/kc_iterator.h b/modules/include/kc_iterator.h index d164fc1..562fd5e 100644 --- a/modules/include/kc_iterator.h +++ b/modules/include/kc_iterator.h @@ -40,15 +40,6 @@ */ const void *(*next)(struct KcIterator_ *ite, size_t *size); - /** - * 次の要素を取得します。 - * 格納している扱う要素が文字列の場合にのみ利用可能です。 - * - * @param ite Iterator オブジェクト - * @return 次の要素(文字列) - */ - const char *(*nextString)(struct KcIterator_ *ite); - /** 内部情報 */ void *_info; diff --git a/modules/src/kc_list.c b/modules/src/kc_list.c index a59e643..a5a97ce 100644 --- a/modules/src/kc_list.c +++ b/modules/src/kc_list.c @@ -13,9 +13,6 @@ */ void KcList_delete(KcList *list) { - if (list->cleanup_info) - { - list->cleanup_info(list); - } + list->cleanup_info(list); free(list); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index 9e746a1..a6a41c3 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -3,6 +3,10 @@ * @brief Linked リストモジュール * @copyright 2003 - 2023 Nomura Kei */ +#if defined(__GNUC__) +#define _GNU_SOURCE 1 +#define qsort_s qsort_r +#endif #include #include #include @@ -61,20 +65,6 @@ static KcLinkedListEntry *KcLinkedList_search(KcLinkedListInfo *info, int index); static KcLinkedListEntry *KcLinkedList_new_entry(const void *value, size_t size); -// [内部関数用] For Quick Sort -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2); -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, KcLinkedListEntry *low, KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args); - /** * LinkedList を構築します。 * @@ -281,12 +271,46 @@ // ----------------------------------------------------------------------------- /** + * [内部利用] + * ソート情報 + */ +typedef struct +{ + int (*comparator)(const void *element1, size_t size1, + const void *element2, size_t size2, void *args); + size_t element_size; + void *user_args; +} KcListSortInfo; + +/** + * [内部利用] + * KcLinkedList_sort にて利用される、qsort_s に渡される comparator です。 + * + * @param x 比較する要素1 + * @param y 比較する要素2 + * @param context コンテキスト(KcListSortInfo) + * @return 比較結果 + */ +static int KcLinkedList_comparator(const void *x, const void *y, void *context) +{ + KcListSortInfo *sort_info = (KcListSortInfo *)context; + const KcLinkedListEntry **entry_x = (const KcLinkedListEntry **)x; + const KcLinkedListEntry **entry_y = (const KcLinkedListEntry **)y; + int ret = sort_info->comparator( + (*entry_x)->value, + (*entry_x)->size, + (*entry_y)->value, + (*entry_y)->size, + sort_info->user_args); + return ret; +} + +/** * 指定された comparator が示す順序に従って、対象リストをソートします。 * * @param list 対象リスト * @param comparator リスト要素を比較するために使用される comparator * @param args comparator の第5引数に渡すオブジェクト - * @return true/false (ソート成功/ソート失敗) */ static void KcLinkedList_sort(KcList *list, int (*comparator)(const void *element1, size_t size1, @@ -294,13 +318,43 @@ void *args) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; + kc_lock_guard(&(info->mutex)) { - KcLinkedList_sort_recur( - info, - info->head->next, - info->tail->prev, - comparator, args); + // Linked List エントリへのポインタを格納する配列を生成する。 + KcLinkedListEntry **ptr_list = (KcLinkedListEntry **)calloc( + info->size, sizeof(KcLinkedListEntry *)); + int idx = 0; + for (KcLinkedListEntry *entry = info->head->next; entry != info->tail; entry = entry->next) + { + ptr_list[idx] = entry; + idx++; + } + + // ソート処理 + KcListSortInfo sort_info; + sort_info.comparator = comparator; + sort_info.user_args = args; + + qsort_s( + ptr_list, + info->size, + sizeof(KcLinkedListEntry *), + KcLinkedList_comparator, + &sort_info); + + // 配列の情報を元にエントリを再構成する。 + KcLinkedListEntry *prev_entry = info->head; + for (int idx2 = 0; idx2 < (int)info->size; idx2++) + { + KcLinkedListEntry *entry = ptr_list[idx2]; + prev_entry->next = entry; + entry->prev = prev_entry; + prev_entry = entry; + } + prev_entry->next = info->tail; + info->tail->prev = prev_entry; + free(ptr_list); } } @@ -386,7 +440,7 @@ void *org_element, size_t *org_size) { KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; - bool is_success = true; + bool is_success = false; kc_lock_guard(&(info->mutex)) { KcLinkedListEntry *remove_entry = KcLinkedList_search(info, index); @@ -441,7 +495,6 @@ result_index = idx; break; } - entry = entry->next; idx++; } } @@ -467,16 +520,15 @@ int result_index = -1; kc_lock_guard(&(info->mutex)) { - int idx = 0; + int idx = info->size; for (KcLinkedListEntry *entry = info->tail->prev; entry != info->head; entry = entry->prev) { + idx--; if ((size == entry->size) && (memcmp(entry->value, element, entry->size) == 0)) { result_index = idx; break; } - entry = entry->next; - idx++; } } return result_index; @@ -639,83 +691,3 @@ } return entry; } - -//////////////////////////////////////////////////////////////////////////////// -// -// For Quick Sort -// - -/** - * 指定されたエントリを入れ替えます。 - * 同じエントリが渡された場合は何もしません。 - * - * @param entry1 入れ替えるエントリ1 - * @param entry2 入れ替えるエントリ2 - */ -static void KcLinkedList_swap( - KcLinkedListEntry *entry1, KcLinkedListEntry *entry2) -{ - if (entry1 != entry2) - { - KcLinkedListEntry *temp = entry1->next; - entry1->next = entry2->next; - entry2->next = temp; - temp = entry1->prev; - entry1->prev = entry2->prev; - entry2->prev = temp; - } -} - -/** - * Quick Sort パーティション処理 - * - * @param info LinkedList 情報 - * @param low Low - * @param high High - * @param comparator 比較関数 - * @param args 比較関数に渡されるデータ - */ -static KcLinkedListEntry *KcLinkedList_sort_partition( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - KcLinkedListEntry *pivot = high; - KcLinkedListEntry *i = low->prev; - - for (KcLinkedListEntry *j = low; j != high; j = j->next) - { - int ret = comparator( - pivot->value, pivot->size, j->value, j->size, args); - if (ret >= 0) - { // j <= pivot - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, j); - } - i = (i == info->head) ? low : i->next; - KcLinkedList_swap(i, high); - } - return i; -} - -/** - * Quick Sort 再帰処理 - */ -static void KcLinkedList_sort_recur( - KcLinkedListInfo *info, - KcLinkedListEntry *low, - KcLinkedListEntry *high, - int (*comparator)(const void *element1, size_t size1, - const void *element2, size_t size2, void *args), - void *args) -{ - if ((high != info->tail) && (low != high) && (low != high->next)) - { - KcLinkedListEntry *p = KcLinkedList_sort_partition(info, low, high, comparator, args); - KcLinkedList_sort_recur(info, low, p->prev, comparator, args); - KcLinkedList_sort_recur(info, p->next, high, comparator, args); - } -} diff --git a/modules/test.c b/modules/test.c deleted file mode 100644 index 12d2d8f..0000000 --- a/modules/test.c +++ /dev/null @@ -1,36 +0,0 @@ -#include -#include -// #include -#include - - -void assert_equals_long(long expected, long actual) -{ - (void) expected; - (void) actual; - printf("-----\n"); -} -int add_i_i(int a, int b) -{ - return (a+b); -} -double add_i_d(int a, double b) -{ - printf("d\n"); - return (a + b); -} - -double add_d_d(double a, double b) -{ - printf("d d\n"); - return (a + b); -} -int main() -{ - // printf("%d\n", add(1,2)); - // printf("%d\n", add(1,2.2)); - // printf("%d\n", add(1.3,2)); - assert_equals(123,123); - return 0; -} - diff --git a/modules/test/src/test_list_linked.c b/modules/test/src/test_list_linked.c new file mode 100644 index 0000000..a542d7b --- /dev/null +++ b/modules/test/src/test_list_linked.c @@ -0,0 +1,523 @@ +#include +#include + +#include +#include +#include +#include +#include + +// プロトタイプ宣言 +static void test_list_linked_new(void); +static void test_list_linked_add(void); +static void test_list_linked_remove(void); +static void test_list_linked_set(void); +static void test_list_linked_search(void); +static void test_list_linked_sort(void); +static void test_list_linked_malloc_error(void); + +/** + * LinkedList 単体テストスイート + */ +void suite_list_linked(void) +{ + KcUt *ut = KcUt_get_instance(); + ut->add(ut, UT_TESTCASE, "list_linked new LinkedList", test_list_linked_new); + ut->add(ut, UT_TESTCASE, "list_linked add/get", test_list_linked_add); + ut->add(ut, UT_TESTCASE, "list_linked remove", test_list_linked_remove); + ut->add(ut, UT_TESTCASE, "list_linked set", test_list_linked_set); + ut->add(ut, UT_TESTCASE, "list_linked search", test_list_linked_search); + ut->add(ut, UT_TESTCASE, "list_linked sort", test_list_linked_sort); + ut->add(ut, UT_TESTCASE, "list_linked malloc error", test_list_linked_malloc_error); +} + +/** + * LinkedList 生成/破棄。 + * + * @process KcList_new_LinkedList を実行する。。 + * @result LinkedList が生成されること。 + * + * @process KcList_delete にて LinkedList を破棄する。 + * @result LinkedList が破棄されること。 + */ +static void test_list_linked_new(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + KcList_delete(list); +} + +/** + * LinkedList データ追加/取得。 + * + * @process 初回追加 (index = 0) + * @process 2つめ追加 (index = 1) + * @process 先頭に追加 (index = 0) + * @process 末尾に追加 (index = 負値(-1)) + * @process 追加(index 不正) + * @process 値取得(サイズ取得あり) + * @process 値取得(サイズ取得なし) + * @process 値取得 (index 不正[負の値を指定]) + * @process 値取得 (index 不正[サイズ以上を指定]) + */ +static void test_list_linked_add(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 空 + bool is_empty = list->is_empty(list); + assert_true(is_empty); + + // 1つめ追加 + int val = 10; + bool res = list->add(list, 0, &val, sizeof(int)); + assert_true(res); + is_empty = list->is_empty(list); + assert_false(is_empty); + + // 2つめ追加 + val = 20; + res = list->add(list, 1, &val, sizeof(int)); + assert_true(res); + + // 先頭に追加 + val = 30; + res = list->add(list, 0, &val, sizeof(int)); + assert_true(res); + + // 末尾に追加 + val = 40; + res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + + // 追加不可位置への追加 + val = 50; + res = list->add(list, 10, &val, sizeof(int)); + assert_false(res); + + // 1つめ取得 + size_t size; + int *res_val = list->get(list, 0, &size); + assert_equals((int)sizeof(int), (int)size); + assert_equals(30, *res_val); + + // 2つめ取得 + res_val = list->get(list, 1, &size); + assert_equals((int)sizeof(int), (int)size); + assert_equals(10, *res_val); + + // 3つめ取得(サイズ取得なし) + res_val = list->get(list, 2, NULL); + assert_equals(20, *res_val); + + // 4つめ取得(サイズ取得なし) + res_val = list->get(list, 3, NULL); + assert_equals(40, *res_val); + + // 値取得 (index 不正[負の値を指定]) + res_val = list->get(list, -1, NULL); + assert_null(res_val); + + // 値取得 (index 不正[サイズを指定]) + res_val = list->get(list, 4, NULL); + assert_null(res_val); + + // 値取得 (index 不正[サイズ以上を指定]) + res_val = list->get(list, 5, NULL); + assert_null(res_val); + + KcList_delete(list); +} + +/** + * LinkedList データ削除。 + * + * @process 末尾削除 + * @process 中間削除 + * @process 先頭削除 + * @process 削除(index 不正[負の値を指定]) + * @process 削除(index 不正[サイズ以上を指定]) + * @process 残っているデータを確認 + * @process 容量調整(初期容量→1/4以下) + */ +static void test_list_linked_remove(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160}; + int default_size = 16; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + + // 末尾削除 (値、サイズ取得あり) + int rval; + size_t rsize = sizeof(int); + bool ret = list->remove(list, (default_size - 1), &rval, &rsize); + assert_true(ret); + assert_equals(vals[(default_size - 1)], rval); + assert_equals((int)sizeof(int), (int)rsize); + int now_size = list->size(list); + assert_equals((default_size - 1), now_size); + + // 値を追加して戻しておく + list->add(list, (default_size - 1), &vals[(default_size - 1)], sizeof(int)); + now_size = list->size(list); + assert_equals(default_size, now_size); + + // 中間削除 (値取得設定あり、サイズ指定なし [=値取得できない]) + // 10, 20, <30>, 40, 50, ... + rval = 9999; + ret = list->remove(list, 2, &rval, NULL); + assert_true(ret); + assert_equals(9999, rval); // size 指定なしのため、値は取得できない。 + now_size = list->size(list); + assert_equals((default_size - 1), now_size); + + // 先頭削除 (値取得なし) + // <10>, 20, 40, 50, ... + ret = list->remove(list, 0, NULL, NULL); + assert_true(ret); + now_size = list->size(list); + assert_equals((default_size - 2), now_size); + + // 削除(index 不正[負の値指定]) + ret = list->remove(list, -1, NULL, NULL); + assert_false(ret); + + // 削除(index 不正[サイズ以上を指定]) + ret = list->remove(list, default_size, NULL, NULL); + assert_false(ret); + + // 残り3つになるまで削除 (3つめを削除) + int rest_size = list->size(list); + while (rest_size > 3) + { + ret = list->remove(list, 3, NULL, NULL); + assert_true(ret); + rest_size = list->size(list); + } + + // 残っているデータの確認 + // 20, 40, 50 + int *res_val_1 = list->get(list, 0, NULL); + int *res_val_2 = list->get(list, 1, NULL); + int *res_val_3 = list->get(list, 2, NULL); + assert_equals(20, *res_val_1); + assert_equals(40, *res_val_2); + assert_equals(50, *res_val_3); + + bool is_empty = list->is_empty(list); + assert_false(is_empty); + + // クリア + list->clear(list); + is_empty = list->is_empty(list); + assert_true(is_empty); + + KcList_delete(list); +} + +/** + * LinkedList データ設定。 + * + * @process 値設定(複数設定) + * @process 値設定(元の値、サイズ取得) + * @process 値設定(元の値取得) + * @process 値設定(不正index[負の値指定]) + * @process 値設定(不正index[サイズ以上指定]) + */ +static void test_list_linked_set(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 20, 30, 40, 50}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(5, now_size); + + // 値設定 (元の値, サイズ取得) + int set_value = 99; + int orig_val = 9999; + size_t orig_size = sizeof(int); + bool ret = list->set(list, 1, &set_value, sizeof(int), &orig_val, &orig_size); + assert_true(ret); + assert_equals(20, orig_val); + assert_equals((int)sizeof(int), (int)orig_size); + int *res_val = list->get(list, 1, NULL); + assert_equals(99, *res_val); + + // 値設定 (元の値取得, サイズ指定なし[=値取得不可]) + set_value = 98; + orig_val = 9999; + ret = list->set(list, 0, &set_value, sizeof(int), &orig_val, NULL); + assert_true(ret); + assert_equals(9999, orig_val); // size 指定なしのため、値取得不可 + res_val = list->get(list, 0, NULL); + assert_equals(98, *res_val); + + // 値設定 (サイズ取得 [=値指定なしのためサイズ取得不可]) + set_value = 97; + orig_size = 0; + ret = list->set(list, 0, &set_value, sizeof(int), NULL, &orig_size); + assert_true(ret); + assert_equals(0, (int)orig_size); // size 取得不可 + res_val = list->get(list, 0, NULL); + assert_equals(97, *res_val); + + now_size = list->size(list); + assert_equals(5, now_size); + + // 値設定(不正index[負の値指定]) + set_value = 96; + ret = list->set(list, -1, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + // 値設定(不正index[サイズ指定]) + set_value = 95; + ret = list->set(list, 5, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + // 値設定(不正index[サイズ以上指定]) + set_value = 95; + ret = list->set(list, 6, &set_value, sizeof(int), NULL, NULL); + assert_false(ret); + + KcList_delete(list); +} + +/** + * LinkedList 検索。 + * + * @process リスト {10, 30, 50, 40, 20, 10, 30, 60, 20 } を構築する。 + * @result リストが構築されること + * + * @process is_contains でリストに含まれる値を確認する。 + * @result true が返されること。 + * + * @process index_of で各インデックス位置を取得する。 + * @result 先頭からのインデックス位置が正しく取得されること。 + * + * @process last_index_of で各インデックス位置を取得する。 + * @result 末尾からのインデックス位置が正しく取得されること。 + * + * @process リストに含まれない値を指定して、is_contains を実行する。 + * @result false が返されること。 + * + * @process リストに含まれない値を指定して、index_of を実行する。 + * @result -1 が返されること。 + * + * @process リストに含まれない値を指定して、last_index_of を実行する。 + * @result -1 が返されること。 + * + * @process 異なるサイズ指定して、is_contains を実行する。 + * @result -1 が返されること。 + * + */ +static void test_list_linked_search(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 30, 50, 40, 20, 10, 30, 60, 20}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(9, now_size); + + // 値が含まれることの確認 + // index_of, last_index_of の確認 + int c_vals[] = {10, 20, 30, 40, 50, 60}; + int c_vals_index[] = {0, 4, 1, 3, 2, 7}; + int c_vals_lindex[] = {5, 8, 6, 3, 2, 7}; + bool is_contains; + int res_index; + int res_lindex; + for (int i = 0; i < (int)(sizeof(c_vals) / sizeof(int)); i++) + { + is_contains = list->contains(list, &c_vals[i], sizeof(int)); + assert_true(is_contains); + + res_index = list->index_of(list, &c_vals[i], sizeof(int)); + assert_equals(c_vals_index[i], res_index); + + res_lindex = list->last_index_of(list, &c_vals[i], sizeof(int)); + assert_equals(c_vals_lindex[i], res_lindex); + } + + // 値が含まれないことの確認 + int c_val = 99; + is_contains = list->contains(list, &c_val, sizeof(int)); + assert_false(is_contains); + + res_index = list->index_of(list, &c_val, sizeof(int)); + assert_equals(-1, res_index); + + res_lindex = list->last_index_of(list, &c_val, sizeof(int)); + assert_equals(-1, res_lindex); + + // 値が含まれないことの確認(異なるサイズ指定) + c_val = 10; + is_contains = list->contains(list, &c_val, sizeof(int) * 2); + assert_false(is_contains); + + res_index = list->index_of(list, &c_val, sizeof(int) * 2); + assert_equals(-1, res_index); + + res_lindex = list->last_index_of(list, &c_val, sizeof(int) * 2); + assert_equals(-1, res_lindex); + + KcList_delete(list); +} + +// ソート用コンパレータ +static int test_list_linked_sort_comparator( + const void *element1, size_t size1, + const void *element2, size_t size2, + void *args) +{ + int val1 = *((int *)element1); + int val2 = *((int *)element2); + assert_equals((int)sizeof(int), (int)size1); + assert_equals((int)sizeof(int), (int)size2); + assert_equals("ABCDEFG", (const char *)args); + return (val1 - val2); +} + +/** + * LinkedList ソート。 + * + * @process リスト {10, 30, 50, 40, 20, 10, 30, 60, 20} を構築する。 + * @result リストが構築されること。 + * + * @process 昇順用コンパレータを渡し、ソートする。 + * @result リストがソートされること。 + * + * @process Iterator を取得する。 + * @result Iterator にて順次値が取得できること。 + */ +static void test_list_linked_sort(void) +{ + KcList *list = KcList_new_LinkedList(); + assert_not_null(list); + + // 値設定 + int vals[] = {10, 30, 50, 40, 20, 10, 30, 60, 20}; + for (int i = 0; i < (int)(sizeof(vals) / sizeof(int)); i++) + { + int val = vals[i]; + bool res = list->add(list, -1, &val, sizeof(int)); + assert_true(res); + } + int now_size = list->size(list); + assert_equals(9, now_size); + + // ソート実施 + list->sort(list, test_list_linked_sort_comparator, "ABCDEFG"); + int sorted_vals[] = {10, 10, 20, 20, 30, 30, 40, 50, 60}; + + // Iterator にて値を取得＆確認 + KcIterator *ite = list->iterator(list, 0); + int sorted_index = 0; + while (ite->hasNext(ite)) + { + size_t res_size; + int *res_val = (int *)ite->next(ite, &res_size); + assert_equals((int)sizeof(int), (int)res_size); + assert_equals(sorted_vals[sorted_index], *res_val); + sorted_index++; + } + KcIterator_delete(ite); + + // index = 5 より取得 + ite = list->iterator(list, 5); + sorted_index = 5; + while (ite->hasNext(ite)) + { + int *res_val = (int *)ite->next(ite, NULL); + assert_equals(sorted_vals[sorted_index], *res_val); + sorted_index++; + } + KcIterator_delete(ite); + + KcList_delete(list); +} + +#include "ut.h" +static int UT_ListLinked_can_alloc_counter = 0; +static bool UT_ListLinked_can_alloc( + KcMemoryEntry *entry, size_t alignment, size_t size, + KcMemoryMark mark, const char *file, const char *func, int line) +{ + UNUSED_VARIABLE(entry); + UNUSED_VARIABLE(alignment); + UNUSED_VARIABLE(size); + UNUSED_VARIABLE(mark); + UNUSED_VARIABLE(file); + UNUSED_VARIABLE(func); + UNUSED_VARIABLE(line); + + UT_ListLinked_can_alloc_counter--; + if (UT_ListLinked_can_alloc_counter < 0) + { + return false; + } + return true; +} + +/** + * LinkedList メモリ確保失敗。 + */ +static void test_list_linked_malloc_error(void) +{ + // LinkedList のメモリ確保失敗 + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + KcList *list = KcList_new_LinkedList(); + _UT_KcMemory_can_alloc = NULL; + assert_null(list); + + // LinkedList の add 時のメモリ確保失敗 + list = KcList_new_LinkedList(); + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + bool ret = list->add(list, 0, "ABC", 4); + _UT_KcMemory_can_alloc = NULL; + assert_false(ret); + assert_equals(0, list->size(list)); + + // Iterator 生成時のメモリ確保失敗 + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + KcIterator *ite = list->iterator(list, 0); + _UT_KcMemory_can_alloc = NULL; + assert_null(ite); + + // set 時のメモリ確保失敗 + list->add(list, 0, "ABC", 4); + UT_ListLinked_can_alloc_counter = 0; + _UT_KcMemory_can_alloc = UT_ListLinked_can_alloc; + list->set(list, 0, "XYZXYZ", 7, NULL, NULL); + _UT_KcMemory_can_alloc = NULL; + assert_equals("ABC", (const char *)list->get(list, 0, NULL)); + + KcList_delete(list); +} \ No newline at end of file diff --git a/modules/test/src/ut.c b/modules/test/src/ut.c index ed34d55..1af0683 100644 --- a/modules/test/src/ut.c +++ b/modules/test/src/ut.c @@ -10,6 +10,7 @@ // UT Setup suite_assert(); suite_list_array(); + suite_list_linked(); suite_lock_guard(); suite_memory_dump(); suite_memory_entry(); diff --git a/modules/test/src/ut.h b/modules/test/src/ut.h index 39d014e..1bcbb28 100644 --- a/modules/test/src/ut.h +++ b/modules/test/src/ut.h @@ -6,6 +6,7 @@ extern void suite_assert(void); extern void suite_list_array(void); +extern void suite_list_linked(void); extern void suite_lock_guard(void); extern void suite_memory_dump(void); extern void suite_memory_entry(void);