diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index a6a41c3..30575b9 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -611,7 +611,9 @@ */ static void KcLinkedList_cleanup_info(KcList *list) { + KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; list->clear(list); + mtx_destroy(&(info->mutex)); } //////////////////////////////////////////////////////////////////////////////// diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index a6a41c3..30575b9 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -611,7 +611,9 @@ */ static void KcLinkedList_cleanup_info(KcList *list) { + KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; list->clear(list); + mtx_destroy(&(info->mutex)); } //////////////////////////////////////////////////////////////////////////////// diff --git a/modules/src/kc_queue.c b/modules/src/kc_queue.c new file mode 100644 index 0000000..544d763 --- /dev/null +++ b/modules/src/kc_queue.c @@ -0,0 +1,312 @@ +/** + * @file kc_queue.c + * @brief キューモジュール + * @copyright 2003 - 2023 Nomura Kei + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/** + * KcQueue 管理情報 + */ +typedef struct +{ + mtx_t mutex; //!< ロック用j + cnd_t not_empty; //!< 条件変数(Empty) + cnd_t not_full; //!< 条件変数(Full) + int queue_size; //!< キューサイズ + KcList *list; //!< キュー内部で利用するリスト +} KcQueueInfo; + +// ============================================================================= +// プロトタイプ宣言 +// ============================================================================= +static int KcQueue_size(struct KcQueue_ *queue); +static bool KcQueue_is_empty(struct KcQueue_ *queue); +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size); +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size); +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size); +static void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size); +static void KcQueue_clear(struct KcQueue_ *queue); +static void KcQueue_cleanup_info(struct KcQueue_ *queue); + +// ============================================================================= +// new +// ============================================================================= +/** + * Queue を構築します。 + * + * @param size キューのサイズ + * @return Queue + */ +KcQueue *KcQueue_new(int size) +{ + // KcQueue の管理構造 + // +--------------+ + // | KcQueue | + // | ... | + // | _info -----------+ + // +--------------+ | + // | <_info> | <---+ + // | list | + // +--------------+ + KcQueue *queue = (KcQueue *)malloc(sizeof(KcQueue) + sizeof(KcQueueInfo)); + KcList *list = KcList_new_LinkedList(); + if ((queue != NULL) && (list != NULL)) + { + queue->size = KcQueue_size; + queue->is_empty = KcQueue_is_empty; + queue->contains = KcQueue_contains; + queue->offer = KcQueue_offer; + queue->poll = KcQueue_poll; + queue->peek = KcQueue_peek; + queue->put = KcQueue_put; + queue->take = KcQueue_take; + queue->clear = KcQueue_clear; + queue->cleanup_info = KcQueue_cleanup_info; + queue->_info = (queue + 1); + + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + info->list = list; + info->queue_size = (size == 0) ? INT_MAX : size; + mtx_init(&(info->mutex), mtx_plain); + cnd_init(&(info->not_empty)); + cnd_init(&(info->not_full)); + } + else + { // 何れかのメモリ確保に失敗したら、メモリを解放する。 + free(queue); + queue = NULL; + free(list); + list = NULL; + } + return queue; +} + +// ============================================================================= +// delete +// ============================================================================= +/** + * Queue をします。 + * + * @param queue 破棄するキュー + */ +void KcQueue_delete(KcQueue *queue) +{ + queue->cleanup_info(queue); + free(queue); +} + +// ============================================================================= +// size +// ============================================================================= +/** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ +static int KcQueue_size(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + size_t size = info->list->size(info->list); + return (int)size; +} + +// ============================================================================= +// is_empty +// ============================================================================= +/** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ +static bool KcQueue_is_empty(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->is_empty(info->list); +} + +// ============================================================================= +// contains +// ============================================================================= +/** + * 指定の要素が対象キューに含まれている場合に true を返します。 + * + * @param queue 対象キュー + * @param element 対象キュー内にあるかどうか判定される要素 + * @param size 要素のサイズ + * @return 指定された要素が対象キュー内にある場合は true + */ +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->contains(info->list, element, size); +} + +// ============================================================================= +// offer +// ============================================================================= +/** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + int now_size = (int)info->list->size(info->list); + if (now_size < info->queue_size) + { + is_success = info->list->add(info->list, -1, element, size); + if (is_success) + { + cnd_signal(&(info->not_empty)); + } + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// poll +// ============================================================================= +/** + * キューより要素を取り出します。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + bool is_empty = info->list->is_empty(info->list); + if (!is_empty) + { + is_success = info->list->remove(info->list, 0, element, size); + // is_success は常に true + cnd_signal(&(info->not_full)); + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// peek +// ============================================================================= +/** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素 + */ +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->get(info->list, 0, size); +} + +// ============================================================================= +// put +// ============================================================================= +/** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while ((int)info->list->size(info->list) == info->queue_size) + { + cnd_wait(&(info->not_full), &(info->mutex)); + } + info->list->add(info->list, -1, element, size); + cnd_signal(&(info->not_empty)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// take +// ============================================================================= +/** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ +void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while (info->list->is_empty(info->list)) + { + cnd_wait(&(info->not_empty), &(info->mutex)); + } + info->list->remove(info->list, 0, element, size); + cnd_signal(&(info->not_full)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clear +// ============================================================================= +/** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ +void KcQueue_clear(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + info->list->clear(info->list); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clearnup_info +// ============================================================================= +/** + * クリア + * + * @param queue 対象キュー + */ +static void KcQueue_cleanup_info(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + KcList_delete(info->list); + mtx_destroy(&(info->mutex)); + cnd_destroy(&(info->not_empty)); + cnd_destroy(&(info->not_full)); +} diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index a6a41c3..30575b9 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -611,7 +611,9 @@ */ static void KcLinkedList_cleanup_info(KcList *list) { + KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; list->clear(list); + mtx_destroy(&(info->mutex)); } //////////////////////////////////////////////////////////////////////////////// diff --git a/modules/src/kc_queue.c b/modules/src/kc_queue.c new file mode 100644 index 0000000..544d763 --- /dev/null +++ b/modules/src/kc_queue.c @@ -0,0 +1,312 @@ +/** + * @file kc_queue.c + * @brief キューモジュール + * @copyright 2003 - 2023 Nomura Kei + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/** + * KcQueue 管理情報 + */ +typedef struct +{ + mtx_t mutex; //!< ロック用j + cnd_t not_empty; //!< 条件変数(Empty) + cnd_t not_full; //!< 条件変数(Full) + int queue_size; //!< キューサイズ + KcList *list; //!< キュー内部で利用するリスト +} KcQueueInfo; + +// ============================================================================= +// プロトタイプ宣言 +// ============================================================================= +static int KcQueue_size(struct KcQueue_ *queue); +static bool KcQueue_is_empty(struct KcQueue_ *queue); +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size); +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size); +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size); +static void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size); +static void KcQueue_clear(struct KcQueue_ *queue); +static void KcQueue_cleanup_info(struct KcQueue_ *queue); + +// ============================================================================= +// new +// ============================================================================= +/** + * Queue を構築します。 + * + * @param size キューのサイズ + * @return Queue + */ +KcQueue *KcQueue_new(int size) +{ + // KcQueue の管理構造 + // +--------------+ + // | KcQueue | + // | ... | + // | _info -----------+ + // +--------------+ | + // | <_info> | <---+ + // | list | + // +--------------+ + KcQueue *queue = (KcQueue *)malloc(sizeof(KcQueue) + sizeof(KcQueueInfo)); + KcList *list = KcList_new_LinkedList(); + if ((queue != NULL) && (list != NULL)) + { + queue->size = KcQueue_size; + queue->is_empty = KcQueue_is_empty; + queue->contains = KcQueue_contains; + queue->offer = KcQueue_offer; + queue->poll = KcQueue_poll; + queue->peek = KcQueue_peek; + queue->put = KcQueue_put; + queue->take = KcQueue_take; + queue->clear = KcQueue_clear; + queue->cleanup_info = KcQueue_cleanup_info; + queue->_info = (queue + 1); + + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + info->list = list; + info->queue_size = (size == 0) ? INT_MAX : size; + mtx_init(&(info->mutex), mtx_plain); + cnd_init(&(info->not_empty)); + cnd_init(&(info->not_full)); + } + else + { // 何れかのメモリ確保に失敗したら、メモリを解放する。 + free(queue); + queue = NULL; + free(list); + list = NULL; + } + return queue; +} + +// ============================================================================= +// delete +// ============================================================================= +/** + * Queue をします。 + * + * @param queue 破棄するキュー + */ +void KcQueue_delete(KcQueue *queue) +{ + queue->cleanup_info(queue); + free(queue); +} + +// ============================================================================= +// size +// ============================================================================= +/** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ +static int KcQueue_size(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + size_t size = info->list->size(info->list); + return (int)size; +} + +// ============================================================================= +// is_empty +// ============================================================================= +/** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ +static bool KcQueue_is_empty(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->is_empty(info->list); +} + +// ============================================================================= +// contains +// ============================================================================= +/** + * 指定の要素が対象キューに含まれている場合に true を返します。 + * + * @param queue 対象キュー + * @param element 対象キュー内にあるかどうか判定される要素 + * @param size 要素のサイズ + * @return 指定された要素が対象キュー内にある場合は true + */ +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->contains(info->list, element, size); +} + +// ============================================================================= +// offer +// ============================================================================= +/** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + int now_size = (int)info->list->size(info->list); + if (now_size < info->queue_size) + { + is_success = info->list->add(info->list, -1, element, size); + if (is_success) + { + cnd_signal(&(info->not_empty)); + } + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// poll +// ============================================================================= +/** + * キューより要素を取り出します。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + bool is_empty = info->list->is_empty(info->list); + if (!is_empty) + { + is_success = info->list->remove(info->list, 0, element, size); + // is_success は常に true + cnd_signal(&(info->not_full)); + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// peek +// ============================================================================= +/** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素 + */ +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->get(info->list, 0, size); +} + +// ============================================================================= +// put +// ============================================================================= +/** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while ((int)info->list->size(info->list) == info->queue_size) + { + cnd_wait(&(info->not_full), &(info->mutex)); + } + info->list->add(info->list, -1, element, size); + cnd_signal(&(info->not_empty)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// take +// ============================================================================= +/** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ +void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while (info->list->is_empty(info->list)) + { + cnd_wait(&(info->not_empty), &(info->mutex)); + } + info->list->remove(info->list, 0, element, size); + cnd_signal(&(info->not_full)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clear +// ============================================================================= +/** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ +void KcQueue_clear(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + info->list->clear(info->list); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clearnup_info +// ============================================================================= +/** + * クリア + * + * @param queue 対象キュー + */ +static void KcQueue_cleanup_info(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + KcList_delete(info->list); + mtx_destroy(&(info->mutex)); + cnd_destroy(&(info->not_empty)); + cnd_destroy(&(info->not_full)); +} diff --git a/modules/test/src/test_list_array.c b/modules/test/src/test_list_array.c index 1dec74e..bfdf199 100644 --- a/modules/test/src/test_list_array.c +++ b/modules/test/src/test_list_array.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_array_new(void); static void test_list_array_add(void); @@ -445,71 +447,48 @@ KcList_delete(list); } -#include "ut.h" -static int UT_ListArray_can_alloc_counter = 0; -static bool UT_ListArray_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_ListArray_can_alloc_counter--; - if (UT_ListArray_can_alloc_counter < 0) - { - return false; - } - return true; -} - /** * ArrayList メモリ確保失敗。 */ static void test_list_array_malloc_error(void) { // ArrayList のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcList *list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(0) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // ArrayList のデータ用メモリ確保失敗 - UT_ListArray_can_alloc_counter = 1; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(1) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // Array Size 拡張時のメモリ確保失敗 - list = KcList_new_ArrayList(sizeof(int), 3); + KcList *list = KcList_new_ArrayList(sizeof(int), 3); int val = 10; list->add(list, 0, &val, sizeof(int)); list->add(list, 1, &val, sizeof(int)); list->add(list, 2, &val, sizeof(int)); - bool ret; - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - // size 以上 - ret = list->add(list, 3, &val, sizeof(int)); - assert_false(ret); - // 0 指定 - ret = list->add(list, 0, &val, sizeof(int)); - assert_false(ret); - _UT_KcMemory_can_alloc = NULL; + ut_alloc_control(0) + { + // size 以上 + bool ret = list->add(list, 3, &val, sizeof(int)); + assert_false(ret); + // 0 指定 + ret = list->add(list, 0, &val, sizeof(int)); + assert_false(ret); + } // Iterator 生成時のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcIterator *ite = list->iterator(list, 0); - _UT_KcMemory_can_alloc = NULL; - assert_null(ite); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + assert_null(ite); + } KcList_delete(list); } \ No newline at end of file diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index a6a41c3..30575b9 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -611,7 +611,9 @@ */ static void KcLinkedList_cleanup_info(KcList *list) { + KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; list->clear(list); + mtx_destroy(&(info->mutex)); } //////////////////////////////////////////////////////////////////////////////// diff --git a/modules/src/kc_queue.c b/modules/src/kc_queue.c new file mode 100644 index 0000000..544d763 --- /dev/null +++ b/modules/src/kc_queue.c @@ -0,0 +1,312 @@ +/** + * @file kc_queue.c + * @brief キューモジュール + * @copyright 2003 - 2023 Nomura Kei + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/** + * KcQueue 管理情報 + */ +typedef struct +{ + mtx_t mutex; //!< ロック用j + cnd_t not_empty; //!< 条件変数(Empty) + cnd_t not_full; //!< 条件変数(Full) + int queue_size; //!< キューサイズ + KcList *list; //!< キュー内部で利用するリスト +} KcQueueInfo; + +// ============================================================================= +// プロトタイプ宣言 +// ============================================================================= +static int KcQueue_size(struct KcQueue_ *queue); +static bool KcQueue_is_empty(struct KcQueue_ *queue); +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size); +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size); +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size); +static void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size); +static void KcQueue_clear(struct KcQueue_ *queue); +static void KcQueue_cleanup_info(struct KcQueue_ *queue); + +// ============================================================================= +// new +// ============================================================================= +/** + * Queue を構築します。 + * + * @param size キューのサイズ + * @return Queue + */ +KcQueue *KcQueue_new(int size) +{ + // KcQueue の管理構造 + // +--------------+ + // | KcQueue | + // | ... | + // | _info -----------+ + // +--------------+ | + // | <_info> | <---+ + // | list | + // +--------------+ + KcQueue *queue = (KcQueue *)malloc(sizeof(KcQueue) + sizeof(KcQueueInfo)); + KcList *list = KcList_new_LinkedList(); + if ((queue != NULL) && (list != NULL)) + { + queue->size = KcQueue_size; + queue->is_empty = KcQueue_is_empty; + queue->contains = KcQueue_contains; + queue->offer = KcQueue_offer; + queue->poll = KcQueue_poll; + queue->peek = KcQueue_peek; + queue->put = KcQueue_put; + queue->take = KcQueue_take; + queue->clear = KcQueue_clear; + queue->cleanup_info = KcQueue_cleanup_info; + queue->_info = (queue + 1); + + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + info->list = list; + info->queue_size = (size == 0) ? INT_MAX : size; + mtx_init(&(info->mutex), mtx_plain); + cnd_init(&(info->not_empty)); + cnd_init(&(info->not_full)); + } + else + { // 何れかのメモリ確保に失敗したら、メモリを解放する。 + free(queue); + queue = NULL; + free(list); + list = NULL; + } + return queue; +} + +// ============================================================================= +// delete +// ============================================================================= +/** + * Queue をします。 + * + * @param queue 破棄するキュー + */ +void KcQueue_delete(KcQueue *queue) +{ + queue->cleanup_info(queue); + free(queue); +} + +// ============================================================================= +// size +// ============================================================================= +/** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ +static int KcQueue_size(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + size_t size = info->list->size(info->list); + return (int)size; +} + +// ============================================================================= +// is_empty +// ============================================================================= +/** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ +static bool KcQueue_is_empty(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->is_empty(info->list); +} + +// ============================================================================= +// contains +// ============================================================================= +/** + * 指定の要素が対象キューに含まれている場合に true を返します。 + * + * @param queue 対象キュー + * @param element 対象キュー内にあるかどうか判定される要素 + * @param size 要素のサイズ + * @return 指定された要素が対象キュー内にある場合は true + */ +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->contains(info->list, element, size); +} + +// ============================================================================= +// offer +// ============================================================================= +/** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + int now_size = (int)info->list->size(info->list); + if (now_size < info->queue_size) + { + is_success = info->list->add(info->list, -1, element, size); + if (is_success) + { + cnd_signal(&(info->not_empty)); + } + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// poll +// ============================================================================= +/** + * キューより要素を取り出します。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + bool is_empty = info->list->is_empty(info->list); + if (!is_empty) + { + is_success = info->list->remove(info->list, 0, element, size); + // is_success は常に true + cnd_signal(&(info->not_full)); + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// peek +// ============================================================================= +/** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素 + */ +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->get(info->list, 0, size); +} + +// ============================================================================= +// put +// ============================================================================= +/** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while ((int)info->list->size(info->list) == info->queue_size) + { + cnd_wait(&(info->not_full), &(info->mutex)); + } + info->list->add(info->list, -1, element, size); + cnd_signal(&(info->not_empty)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// take +// ============================================================================= +/** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ +void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while (info->list->is_empty(info->list)) + { + cnd_wait(&(info->not_empty), &(info->mutex)); + } + info->list->remove(info->list, 0, element, size); + cnd_signal(&(info->not_full)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clear +// ============================================================================= +/** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ +void KcQueue_clear(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + info->list->clear(info->list); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clearnup_info +// ============================================================================= +/** + * クリア + * + * @param queue 対象キュー + */ +static void KcQueue_cleanup_info(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + KcList_delete(info->list); + mtx_destroy(&(info->mutex)); + cnd_destroy(&(info->not_empty)); + cnd_destroy(&(info->not_full)); +} diff --git a/modules/test/src/test_list_array.c b/modules/test/src/test_list_array.c index 1dec74e..bfdf199 100644 --- a/modules/test/src/test_list_array.c +++ b/modules/test/src/test_list_array.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_array_new(void); static void test_list_array_add(void); @@ -445,71 +447,48 @@ KcList_delete(list); } -#include "ut.h" -static int UT_ListArray_can_alloc_counter = 0; -static bool UT_ListArray_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_ListArray_can_alloc_counter--; - if (UT_ListArray_can_alloc_counter < 0) - { - return false; - } - return true; -} - /** * ArrayList メモリ確保失敗。 */ static void test_list_array_malloc_error(void) { // ArrayList のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcList *list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(0) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // ArrayList のデータ用メモリ確保失敗 - UT_ListArray_can_alloc_counter = 1; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(1) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // Array Size 拡張時のメモリ確保失敗 - list = KcList_new_ArrayList(sizeof(int), 3); + KcList *list = KcList_new_ArrayList(sizeof(int), 3); int val = 10; list->add(list, 0, &val, sizeof(int)); list->add(list, 1, &val, sizeof(int)); list->add(list, 2, &val, sizeof(int)); - bool ret; - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - // size 以上 - ret = list->add(list, 3, &val, sizeof(int)); - assert_false(ret); - // 0 指定 - ret = list->add(list, 0, &val, sizeof(int)); - assert_false(ret); - _UT_KcMemory_can_alloc = NULL; + ut_alloc_control(0) + { + // size 以上 + bool ret = list->add(list, 3, &val, sizeof(int)); + assert_false(ret); + // 0 指定 + ret = list->add(list, 0, &val, sizeof(int)); + assert_false(ret); + } // Iterator 生成時のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcIterator *ite = list->iterator(list, 0); - _UT_KcMemory_can_alloc = NULL; - assert_null(ite); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + assert_null(ite); + } KcList_delete(list); } \ No newline at end of file diff --git a/modules/test/src/test_list_linked.c b/modules/test/src/test_list_linked.c index a542d7b..27ac267 100644 --- a/modules/test/src/test_list_linked.c +++ b/modules/test/src/test_list_linked.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_linked_new(void); static void test_list_linked_add(void); @@ -461,63 +463,41 @@ 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); + ut_alloc_control(0) + { + KcList *list = KcList_new_LinkedList(); + 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)); + KcList *list = KcList_new_LinkedList(); + ut_alloc_control(0) + { + bool ret = list->add(list, 0, "ABC", 4); + 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); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + 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)); + ut_alloc_control(0) + { + list->set(list, 0, "XYZXYZ", 7, NULL, 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_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index a6a41c3..30575b9 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -611,7 +611,9 @@ */ static void KcLinkedList_cleanup_info(KcList *list) { + KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; list->clear(list); + mtx_destroy(&(info->mutex)); } //////////////////////////////////////////////////////////////////////////////// diff --git a/modules/src/kc_queue.c b/modules/src/kc_queue.c new file mode 100644 index 0000000..544d763 --- /dev/null +++ b/modules/src/kc_queue.c @@ -0,0 +1,312 @@ +/** + * @file kc_queue.c + * @brief キューモジュール + * @copyright 2003 - 2023 Nomura Kei + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/** + * KcQueue 管理情報 + */ +typedef struct +{ + mtx_t mutex; //!< ロック用j + cnd_t not_empty; //!< 条件変数(Empty) + cnd_t not_full; //!< 条件変数(Full) + int queue_size; //!< キューサイズ + KcList *list; //!< キュー内部で利用するリスト +} KcQueueInfo; + +// ============================================================================= +// プロトタイプ宣言 +// ============================================================================= +static int KcQueue_size(struct KcQueue_ *queue); +static bool KcQueue_is_empty(struct KcQueue_ *queue); +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size); +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size); +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size); +static void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size); +static void KcQueue_clear(struct KcQueue_ *queue); +static void KcQueue_cleanup_info(struct KcQueue_ *queue); + +// ============================================================================= +// new +// ============================================================================= +/** + * Queue を構築します。 + * + * @param size キューのサイズ + * @return Queue + */ +KcQueue *KcQueue_new(int size) +{ + // KcQueue の管理構造 + // +--------------+ + // | KcQueue | + // | ... | + // | _info -----------+ + // +--------------+ | + // | <_info> | <---+ + // | list | + // +--------------+ + KcQueue *queue = (KcQueue *)malloc(sizeof(KcQueue) + sizeof(KcQueueInfo)); + KcList *list = KcList_new_LinkedList(); + if ((queue != NULL) && (list != NULL)) + { + queue->size = KcQueue_size; + queue->is_empty = KcQueue_is_empty; + queue->contains = KcQueue_contains; + queue->offer = KcQueue_offer; + queue->poll = KcQueue_poll; + queue->peek = KcQueue_peek; + queue->put = KcQueue_put; + queue->take = KcQueue_take; + queue->clear = KcQueue_clear; + queue->cleanup_info = KcQueue_cleanup_info; + queue->_info = (queue + 1); + + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + info->list = list; + info->queue_size = (size == 0) ? INT_MAX : size; + mtx_init(&(info->mutex), mtx_plain); + cnd_init(&(info->not_empty)); + cnd_init(&(info->not_full)); + } + else + { // 何れかのメモリ確保に失敗したら、メモリを解放する。 + free(queue); + queue = NULL; + free(list); + list = NULL; + } + return queue; +} + +// ============================================================================= +// delete +// ============================================================================= +/** + * Queue をします。 + * + * @param queue 破棄するキュー + */ +void KcQueue_delete(KcQueue *queue) +{ + queue->cleanup_info(queue); + free(queue); +} + +// ============================================================================= +// size +// ============================================================================= +/** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ +static int KcQueue_size(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + size_t size = info->list->size(info->list); + return (int)size; +} + +// ============================================================================= +// is_empty +// ============================================================================= +/** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ +static bool KcQueue_is_empty(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->is_empty(info->list); +} + +// ============================================================================= +// contains +// ============================================================================= +/** + * 指定の要素が対象キューに含まれている場合に true を返します。 + * + * @param queue 対象キュー + * @param element 対象キュー内にあるかどうか判定される要素 + * @param size 要素のサイズ + * @return 指定された要素が対象キュー内にある場合は true + */ +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->contains(info->list, element, size); +} + +// ============================================================================= +// offer +// ============================================================================= +/** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + int now_size = (int)info->list->size(info->list); + if (now_size < info->queue_size) + { + is_success = info->list->add(info->list, -1, element, size); + if (is_success) + { + cnd_signal(&(info->not_empty)); + } + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// poll +// ============================================================================= +/** + * キューより要素を取り出します。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + bool is_empty = info->list->is_empty(info->list); + if (!is_empty) + { + is_success = info->list->remove(info->list, 0, element, size); + // is_success は常に true + cnd_signal(&(info->not_full)); + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// peek +// ============================================================================= +/** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素 + */ +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->get(info->list, 0, size); +} + +// ============================================================================= +// put +// ============================================================================= +/** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while ((int)info->list->size(info->list) == info->queue_size) + { + cnd_wait(&(info->not_full), &(info->mutex)); + } + info->list->add(info->list, -1, element, size); + cnd_signal(&(info->not_empty)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// take +// ============================================================================= +/** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ +void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while (info->list->is_empty(info->list)) + { + cnd_wait(&(info->not_empty), &(info->mutex)); + } + info->list->remove(info->list, 0, element, size); + cnd_signal(&(info->not_full)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clear +// ============================================================================= +/** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ +void KcQueue_clear(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + info->list->clear(info->list); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clearnup_info +// ============================================================================= +/** + * クリア + * + * @param queue 対象キュー + */ +static void KcQueue_cleanup_info(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + KcList_delete(info->list); + mtx_destroy(&(info->mutex)); + cnd_destroy(&(info->not_empty)); + cnd_destroy(&(info->not_full)); +} diff --git a/modules/test/src/test_list_array.c b/modules/test/src/test_list_array.c index 1dec74e..bfdf199 100644 --- a/modules/test/src/test_list_array.c +++ b/modules/test/src/test_list_array.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_array_new(void); static void test_list_array_add(void); @@ -445,71 +447,48 @@ KcList_delete(list); } -#include "ut.h" -static int UT_ListArray_can_alloc_counter = 0; -static bool UT_ListArray_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_ListArray_can_alloc_counter--; - if (UT_ListArray_can_alloc_counter < 0) - { - return false; - } - return true; -} - /** * ArrayList メモリ確保失敗。 */ static void test_list_array_malloc_error(void) { // ArrayList のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcList *list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(0) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // ArrayList のデータ用メモリ確保失敗 - UT_ListArray_can_alloc_counter = 1; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(1) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // Array Size 拡張時のメモリ確保失敗 - list = KcList_new_ArrayList(sizeof(int), 3); + KcList *list = KcList_new_ArrayList(sizeof(int), 3); int val = 10; list->add(list, 0, &val, sizeof(int)); list->add(list, 1, &val, sizeof(int)); list->add(list, 2, &val, sizeof(int)); - bool ret; - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - // size 以上 - ret = list->add(list, 3, &val, sizeof(int)); - assert_false(ret); - // 0 指定 - ret = list->add(list, 0, &val, sizeof(int)); - assert_false(ret); - _UT_KcMemory_can_alloc = NULL; + ut_alloc_control(0) + { + // size 以上 + bool ret = list->add(list, 3, &val, sizeof(int)); + assert_false(ret); + // 0 指定 + ret = list->add(list, 0, &val, sizeof(int)); + assert_false(ret); + } // Iterator 生成時のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcIterator *ite = list->iterator(list, 0); - _UT_KcMemory_can_alloc = NULL; - assert_null(ite); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + assert_null(ite); + } KcList_delete(list); } \ No newline at end of file diff --git a/modules/test/src/test_list_linked.c b/modules/test/src/test_list_linked.c index a542d7b..27ac267 100644 --- a/modules/test/src/test_list_linked.c +++ b/modules/test/src/test_list_linked.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_linked_new(void); static void test_list_linked_add(void); @@ -461,63 +463,41 @@ 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); + ut_alloc_control(0) + { + KcList *list = KcList_new_LinkedList(); + 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)); + KcList *list = KcList_new_LinkedList(); + ut_alloc_control(0) + { + bool ret = list->add(list, 0, "ABC", 4); + 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); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + 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)); + ut_alloc_control(0) + { + list->set(list, 0, "XYZXYZ", 7, NULL, 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/test_queue.c b/modules/test/src/test_queue.c new file mode 100644 index 0000000..cbec7e0 --- /dev/null +++ b/modules/test/src/test_queue.c @@ -0,0 +1,328 @@ +#include +#include +#include + +#include +#include +#include +#include +#include + +#include "ut.h" + +// プロトタイプ宣言 +static void test_queue_new(void); +static void test_queue_offer(void); +static void test_queue_put(void); +static void test_queue_size(void); +static void test_queue_offer_ng(void); +static void test_queue_malloc_error(void); + +/** + * KcQueue 単体テストスイート + */ +void suite_queue(void) +{ + KcUt *ut = KcUt_get_instance(); + ut->add(ut, UT_TESTCASE, "queue new/delete", test_queue_new); + ut->add(ut, UT_TESTCASE, "queue offer/peek/poll", test_queue_offer); + ut->add(ut, UT_TESTCASE, "queue put/take", test_queue_put); + ut->add(ut, UT_TESTCASE, "queue size", test_queue_size); + ut->add(ut, UT_TESTCASE, "queue offer ng", test_queue_offer_ng); + ut->add(ut, UT_TESTCASE, "queue malloc error", test_queue_malloc_error); +} + +/** + * Queue 生成/破棄。 + * + * @process KcQueue_new を実行する。。 + * @result KcQueue が生成されること。 + * + * @process KcQueue_delete にて Queue を破棄する。 + * @result Queue が破棄されること。 + */ +static void test_queue_new(void) +{ + KcQueue *queue = KcQueue_new(0); + assert_not_null(queue); + KcQueue_delete(queue); + + // リストが残った状態での削除 + queue = KcQueue_new(0); + queue->offer(queue, "ABC", 4); + assert_not_null(queue); + KcQueue_delete(queue); +} + +// for offer thread +static int test_queue_offer_thread(void *arg) +{ + KcQueue *queue = (KcQueue *)arg; + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + for (int i = 0; i < 100; i++) + { + printf("offer: %d\n", i); + queue->offer(queue, &i, sizeof(int)); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for poll thread +static int test_queue_poll_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int *val = queue->peek(queue, NULL); + if (val == NULL) + { + printf("peek: (null)\n"); + } + else + { + printf("peek: %d\n", *val); + } + + int element; + size_t size = sizeof(int); + bool is_success = queue->poll(queue, &element, &size); + if (is_success) + { + printf("poll: %d\n", element); + } + else + { + printf("poll: (null)\n"); + } + thrd_sleep(&spec, NULL); + } + return 0; +} + +/** + * キューへの値追加/取得。 + */ +static void test_queue_offer(void) +{ + KcQueue *queue = KcQueue_new(10); + + thrd_t offer_thread, poll_thread; + + thrd_create(&offer_thread, test_queue_offer_thread, queue); + thrd_create(&poll_thread, test_queue_poll_thread, queue); + + thrd_join(offer_thread, NULL); + thrd_join(poll_thread, NULL); + KcQueue_delete(queue); +} + +// for put thread +static int test_queue_put_thread(void *arg) +{ + KcQueue *queue = (KcQueue *)arg; + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1 * 1000; + for (int i = 0; i < 100; i++) + { + queue->put(queue, &i, sizeof(int)); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for take thread +static int test_queue_take_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int element; + size_t size = sizeof(int); + queue->take(queue, &element, &size); + assert_equals(i, element); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for take thread +static int test_queue_take2_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 100 * 1000; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int element; + size_t size = sizeof(int); + queue->take(queue, &element, &size); + assert_equals(i, element); + thrd_sleep(&spec, NULL); + } + return 0; +} + +/** + * キューへの値追加/取得。 + */ +static void test_queue_put(void) +{ + { + KcQueue *queue = KcQueue_new(0); + thrd_t put_thread, take_thread; + thrd_create(&put_thread, test_queue_put_thread, queue); + thrd_create(&take_thread, test_queue_take_thread, queue); + thrd_join(put_thread, NULL); + thrd_join(take_thread, NULL); + KcQueue_delete(queue); + } + + // PUT ブロックパターン + { + KcQueue *queue = KcQueue_new(5); + thrd_t put_thread, take_thread; + thrd_create(&put_thread, test_queue_put_thread, queue); + thrd_create(&take_thread, test_queue_take2_thread, queue); + thrd_join(put_thread, NULL); + thrd_join(take_thread, NULL); + KcQueue_delete(queue); + } +} + +/** + * キューサイズ取得 + */ +static void test_queue_size(void) +{ + KcQueue *queue = KcQueue_new(0); + + // キューへ追加 + bool ret = queue->offer(queue, "ABC", 4); + assert_true(ret); + ret = queue->offer(queue, "DEFG", 5); + int size = queue->size(queue); + assert_equals(2, size); + bool is_empty = queue->is_empty(queue); + assert_false(is_empty); + + bool is_contains = queue->contains(queue, "ABC", 4); + assert_true(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_true(is_contains); + + char buffer[10]; + size_t element_size; + // 取り出し [peek] + const char *val = (const char *)queue->peek(queue, &element_size); + assert_equals(4, element_size); + assert_equals("ABC", val); + size = queue->size(queue); + assert_equals(2, size); + is_empty = queue->is_empty(queue); + assert_false(is_empty); + // 取り出し [poll] (サイズ不足) + for (int i = 0; i < 10; i++) + { + buffer[i] = 'X'; + } + buffer[9] = '\0'; + element_size = 2; + queue->poll(queue, buffer, &element_size); + assert_equals("ABXXXXXXX", buffer); + assert_equals(4, element_size); + size = queue->size(queue); + assert_equals(1, size); + is_empty = queue->is_empty(queue); + assert_false(is_empty); + is_contains = queue->contains(queue, "ABC", 4); + assert_false(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_true(is_contains); + + // 取り出し [poll] + for (int i = 0; i < 10; i++) + { + buffer[i] = 'X'; + } + buffer[9] = '\0'; + element_size = 10; + queue->poll(queue, buffer, &element_size); + assert_equals("DEFG", buffer); + assert_equals(5, element_size); + size = queue->size(queue); + assert_equals(0, size); + is_empty = queue->is_empty(queue); + assert_true(is_empty); + is_contains = queue->contains(queue, "ABC", 4); + assert_false(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_false(is_contains); + + KcQueue_delete(queue); +} + +/** + * offer 失敗。 + */ +static void test_queue_offer_ng(void) +{ + KcQueue *queue = KcQueue_new(3); + + bool ret; + ret = queue->offer(queue, "ABC", 4); + assert_true(ret); + ret = queue->offer(queue, "DEF", 4); + assert_true(ret); + ret = queue->offer(queue, "GHI", 4); + assert_true(ret); + ret = queue->offer(queue, "JKL", 4); + assert_false(ret); + + queue->clear(queue); + ret = queue->is_empty(queue); + assert_true(ret); + + KcQueue_delete(queue); +} + +/** + * Queue メモリ確保失敗。 + */ +static void test_queue_malloc_error(void) +{ + // メモリ確保失敗 + KcQueue *queue; + ut_alloc_control(0) + { + queue = KcQueue_new(0); + } + assert_null(queue); + + // 内部管理のリストメモリ確保失敗 + ut_alloc_control(1) + { + queue = KcQueue_new(0); + } + assert_null(queue); + + // 追加時のメモリ確保失敗 + + queue = KcQueue_new(10); + ut_alloc_control(0) + { + bool ret = queue->offer(queue, "XYZ", 4); + assert_false(ret); + } + KcQueue_delete(queue); +} diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index a6a41c3..30575b9 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -611,7 +611,9 @@ */ static void KcLinkedList_cleanup_info(KcList *list) { + KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; list->clear(list); + mtx_destroy(&(info->mutex)); } //////////////////////////////////////////////////////////////////////////////// diff --git a/modules/src/kc_queue.c b/modules/src/kc_queue.c new file mode 100644 index 0000000..544d763 --- /dev/null +++ b/modules/src/kc_queue.c @@ -0,0 +1,312 @@ +/** + * @file kc_queue.c + * @brief キューモジュール + * @copyright 2003 - 2023 Nomura Kei + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/** + * KcQueue 管理情報 + */ +typedef struct +{ + mtx_t mutex; //!< ロック用j + cnd_t not_empty; //!< 条件変数(Empty) + cnd_t not_full; //!< 条件変数(Full) + int queue_size; //!< キューサイズ + KcList *list; //!< キュー内部で利用するリスト +} KcQueueInfo; + +// ============================================================================= +// プロトタイプ宣言 +// ============================================================================= +static int KcQueue_size(struct KcQueue_ *queue); +static bool KcQueue_is_empty(struct KcQueue_ *queue); +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size); +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size); +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size); +static void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size); +static void KcQueue_clear(struct KcQueue_ *queue); +static void KcQueue_cleanup_info(struct KcQueue_ *queue); + +// ============================================================================= +// new +// ============================================================================= +/** + * Queue を構築します。 + * + * @param size キューのサイズ + * @return Queue + */ +KcQueue *KcQueue_new(int size) +{ + // KcQueue の管理構造 + // +--------------+ + // | KcQueue | + // | ... | + // | _info -----------+ + // +--------------+ | + // | <_info> | <---+ + // | list | + // +--------------+ + KcQueue *queue = (KcQueue *)malloc(sizeof(KcQueue) + sizeof(KcQueueInfo)); + KcList *list = KcList_new_LinkedList(); + if ((queue != NULL) && (list != NULL)) + { + queue->size = KcQueue_size; + queue->is_empty = KcQueue_is_empty; + queue->contains = KcQueue_contains; + queue->offer = KcQueue_offer; + queue->poll = KcQueue_poll; + queue->peek = KcQueue_peek; + queue->put = KcQueue_put; + queue->take = KcQueue_take; + queue->clear = KcQueue_clear; + queue->cleanup_info = KcQueue_cleanup_info; + queue->_info = (queue + 1); + + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + info->list = list; + info->queue_size = (size == 0) ? INT_MAX : size; + mtx_init(&(info->mutex), mtx_plain); + cnd_init(&(info->not_empty)); + cnd_init(&(info->not_full)); + } + else + { // 何れかのメモリ確保に失敗したら、メモリを解放する。 + free(queue); + queue = NULL; + free(list); + list = NULL; + } + return queue; +} + +// ============================================================================= +// delete +// ============================================================================= +/** + * Queue をします。 + * + * @param queue 破棄するキュー + */ +void KcQueue_delete(KcQueue *queue) +{ + queue->cleanup_info(queue); + free(queue); +} + +// ============================================================================= +// size +// ============================================================================= +/** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ +static int KcQueue_size(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + size_t size = info->list->size(info->list); + return (int)size; +} + +// ============================================================================= +// is_empty +// ============================================================================= +/** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ +static bool KcQueue_is_empty(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->is_empty(info->list); +} + +// ============================================================================= +// contains +// ============================================================================= +/** + * 指定の要素が対象キューに含まれている場合に true を返します。 + * + * @param queue 対象キュー + * @param element 対象キュー内にあるかどうか判定される要素 + * @param size 要素のサイズ + * @return 指定された要素が対象キュー内にある場合は true + */ +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->contains(info->list, element, size); +} + +// ============================================================================= +// offer +// ============================================================================= +/** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + int now_size = (int)info->list->size(info->list); + if (now_size < info->queue_size) + { + is_success = info->list->add(info->list, -1, element, size); + if (is_success) + { + cnd_signal(&(info->not_empty)); + } + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// poll +// ============================================================================= +/** + * キューより要素を取り出します。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + bool is_empty = info->list->is_empty(info->list); + if (!is_empty) + { + is_success = info->list->remove(info->list, 0, element, size); + // is_success は常に true + cnd_signal(&(info->not_full)); + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// peek +// ============================================================================= +/** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素 + */ +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->get(info->list, 0, size); +} + +// ============================================================================= +// put +// ============================================================================= +/** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while ((int)info->list->size(info->list) == info->queue_size) + { + cnd_wait(&(info->not_full), &(info->mutex)); + } + info->list->add(info->list, -1, element, size); + cnd_signal(&(info->not_empty)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// take +// ============================================================================= +/** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ +void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while (info->list->is_empty(info->list)) + { + cnd_wait(&(info->not_empty), &(info->mutex)); + } + info->list->remove(info->list, 0, element, size); + cnd_signal(&(info->not_full)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clear +// ============================================================================= +/** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ +void KcQueue_clear(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + info->list->clear(info->list); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clearnup_info +// ============================================================================= +/** + * クリア + * + * @param queue 対象キュー + */ +static void KcQueue_cleanup_info(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + KcList_delete(info->list); + mtx_destroy(&(info->mutex)); + cnd_destroy(&(info->not_empty)); + cnd_destroy(&(info->not_full)); +} diff --git a/modules/test/src/test_list_array.c b/modules/test/src/test_list_array.c index 1dec74e..bfdf199 100644 --- a/modules/test/src/test_list_array.c +++ b/modules/test/src/test_list_array.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_array_new(void); static void test_list_array_add(void); @@ -445,71 +447,48 @@ KcList_delete(list); } -#include "ut.h" -static int UT_ListArray_can_alloc_counter = 0; -static bool UT_ListArray_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_ListArray_can_alloc_counter--; - if (UT_ListArray_can_alloc_counter < 0) - { - return false; - } - return true; -} - /** * ArrayList メモリ確保失敗。 */ static void test_list_array_malloc_error(void) { // ArrayList のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcList *list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(0) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // ArrayList のデータ用メモリ確保失敗 - UT_ListArray_can_alloc_counter = 1; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(1) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // Array Size 拡張時のメモリ確保失敗 - list = KcList_new_ArrayList(sizeof(int), 3); + KcList *list = KcList_new_ArrayList(sizeof(int), 3); int val = 10; list->add(list, 0, &val, sizeof(int)); list->add(list, 1, &val, sizeof(int)); list->add(list, 2, &val, sizeof(int)); - bool ret; - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - // size 以上 - ret = list->add(list, 3, &val, sizeof(int)); - assert_false(ret); - // 0 指定 - ret = list->add(list, 0, &val, sizeof(int)); - assert_false(ret); - _UT_KcMemory_can_alloc = NULL; + ut_alloc_control(0) + { + // size 以上 + bool ret = list->add(list, 3, &val, sizeof(int)); + assert_false(ret); + // 0 指定 + ret = list->add(list, 0, &val, sizeof(int)); + assert_false(ret); + } // Iterator 生成時のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcIterator *ite = list->iterator(list, 0); - _UT_KcMemory_can_alloc = NULL; - assert_null(ite); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + assert_null(ite); + } KcList_delete(list); } \ No newline at end of file diff --git a/modules/test/src/test_list_linked.c b/modules/test/src/test_list_linked.c index a542d7b..27ac267 100644 --- a/modules/test/src/test_list_linked.c +++ b/modules/test/src/test_list_linked.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_linked_new(void); static void test_list_linked_add(void); @@ -461,63 +463,41 @@ 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); + ut_alloc_control(0) + { + KcList *list = KcList_new_LinkedList(); + 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)); + KcList *list = KcList_new_LinkedList(); + ut_alloc_control(0) + { + bool ret = list->add(list, 0, "ABC", 4); + 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); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + 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)); + ut_alloc_control(0) + { + list->set(list, 0, "XYZXYZ", 7, NULL, 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/test_queue.c b/modules/test/src/test_queue.c new file mode 100644 index 0000000..cbec7e0 --- /dev/null +++ b/modules/test/src/test_queue.c @@ -0,0 +1,328 @@ +#include +#include +#include + +#include +#include +#include +#include +#include + +#include "ut.h" + +// プロトタイプ宣言 +static void test_queue_new(void); +static void test_queue_offer(void); +static void test_queue_put(void); +static void test_queue_size(void); +static void test_queue_offer_ng(void); +static void test_queue_malloc_error(void); + +/** + * KcQueue 単体テストスイート + */ +void suite_queue(void) +{ + KcUt *ut = KcUt_get_instance(); + ut->add(ut, UT_TESTCASE, "queue new/delete", test_queue_new); + ut->add(ut, UT_TESTCASE, "queue offer/peek/poll", test_queue_offer); + ut->add(ut, UT_TESTCASE, "queue put/take", test_queue_put); + ut->add(ut, UT_TESTCASE, "queue size", test_queue_size); + ut->add(ut, UT_TESTCASE, "queue offer ng", test_queue_offer_ng); + ut->add(ut, UT_TESTCASE, "queue malloc error", test_queue_malloc_error); +} + +/** + * Queue 生成/破棄。 + * + * @process KcQueue_new を実行する。。 + * @result KcQueue が生成されること。 + * + * @process KcQueue_delete にて Queue を破棄する。 + * @result Queue が破棄されること。 + */ +static void test_queue_new(void) +{ + KcQueue *queue = KcQueue_new(0); + assert_not_null(queue); + KcQueue_delete(queue); + + // リストが残った状態での削除 + queue = KcQueue_new(0); + queue->offer(queue, "ABC", 4); + assert_not_null(queue); + KcQueue_delete(queue); +} + +// for offer thread +static int test_queue_offer_thread(void *arg) +{ + KcQueue *queue = (KcQueue *)arg; + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + for (int i = 0; i < 100; i++) + { + printf("offer: %d\n", i); + queue->offer(queue, &i, sizeof(int)); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for poll thread +static int test_queue_poll_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int *val = queue->peek(queue, NULL); + if (val == NULL) + { + printf("peek: (null)\n"); + } + else + { + printf("peek: %d\n", *val); + } + + int element; + size_t size = sizeof(int); + bool is_success = queue->poll(queue, &element, &size); + if (is_success) + { + printf("poll: %d\n", element); + } + else + { + printf("poll: (null)\n"); + } + thrd_sleep(&spec, NULL); + } + return 0; +} + +/** + * キューへの値追加/取得。 + */ +static void test_queue_offer(void) +{ + KcQueue *queue = KcQueue_new(10); + + thrd_t offer_thread, poll_thread; + + thrd_create(&offer_thread, test_queue_offer_thread, queue); + thrd_create(&poll_thread, test_queue_poll_thread, queue); + + thrd_join(offer_thread, NULL); + thrd_join(poll_thread, NULL); + KcQueue_delete(queue); +} + +// for put thread +static int test_queue_put_thread(void *arg) +{ + KcQueue *queue = (KcQueue *)arg; + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1 * 1000; + for (int i = 0; i < 100; i++) + { + queue->put(queue, &i, sizeof(int)); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for take thread +static int test_queue_take_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int element; + size_t size = sizeof(int); + queue->take(queue, &element, &size); + assert_equals(i, element); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for take thread +static int test_queue_take2_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 100 * 1000; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int element; + size_t size = sizeof(int); + queue->take(queue, &element, &size); + assert_equals(i, element); + thrd_sleep(&spec, NULL); + } + return 0; +} + +/** + * キューへの値追加/取得。 + */ +static void test_queue_put(void) +{ + { + KcQueue *queue = KcQueue_new(0); + thrd_t put_thread, take_thread; + thrd_create(&put_thread, test_queue_put_thread, queue); + thrd_create(&take_thread, test_queue_take_thread, queue); + thrd_join(put_thread, NULL); + thrd_join(take_thread, NULL); + KcQueue_delete(queue); + } + + // PUT ブロックパターン + { + KcQueue *queue = KcQueue_new(5); + thrd_t put_thread, take_thread; + thrd_create(&put_thread, test_queue_put_thread, queue); + thrd_create(&take_thread, test_queue_take2_thread, queue); + thrd_join(put_thread, NULL); + thrd_join(take_thread, NULL); + KcQueue_delete(queue); + } +} + +/** + * キューサイズ取得 + */ +static void test_queue_size(void) +{ + KcQueue *queue = KcQueue_new(0); + + // キューへ追加 + bool ret = queue->offer(queue, "ABC", 4); + assert_true(ret); + ret = queue->offer(queue, "DEFG", 5); + int size = queue->size(queue); + assert_equals(2, size); + bool is_empty = queue->is_empty(queue); + assert_false(is_empty); + + bool is_contains = queue->contains(queue, "ABC", 4); + assert_true(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_true(is_contains); + + char buffer[10]; + size_t element_size; + // 取り出し [peek] + const char *val = (const char *)queue->peek(queue, &element_size); + assert_equals(4, element_size); + assert_equals("ABC", val); + size = queue->size(queue); + assert_equals(2, size); + is_empty = queue->is_empty(queue); + assert_false(is_empty); + // 取り出し [poll] (サイズ不足) + for (int i = 0; i < 10; i++) + { + buffer[i] = 'X'; + } + buffer[9] = '\0'; + element_size = 2; + queue->poll(queue, buffer, &element_size); + assert_equals("ABXXXXXXX", buffer); + assert_equals(4, element_size); + size = queue->size(queue); + assert_equals(1, size); + is_empty = queue->is_empty(queue); + assert_false(is_empty); + is_contains = queue->contains(queue, "ABC", 4); + assert_false(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_true(is_contains); + + // 取り出し [poll] + for (int i = 0; i < 10; i++) + { + buffer[i] = 'X'; + } + buffer[9] = '\0'; + element_size = 10; + queue->poll(queue, buffer, &element_size); + assert_equals("DEFG", buffer); + assert_equals(5, element_size); + size = queue->size(queue); + assert_equals(0, size); + is_empty = queue->is_empty(queue); + assert_true(is_empty); + is_contains = queue->contains(queue, "ABC", 4); + assert_false(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_false(is_contains); + + KcQueue_delete(queue); +} + +/** + * offer 失敗。 + */ +static void test_queue_offer_ng(void) +{ + KcQueue *queue = KcQueue_new(3); + + bool ret; + ret = queue->offer(queue, "ABC", 4); + assert_true(ret); + ret = queue->offer(queue, "DEF", 4); + assert_true(ret); + ret = queue->offer(queue, "GHI", 4); + assert_true(ret); + ret = queue->offer(queue, "JKL", 4); + assert_false(ret); + + queue->clear(queue); + ret = queue->is_empty(queue); + assert_true(ret); + + KcQueue_delete(queue); +} + +/** + * Queue メモリ確保失敗。 + */ +static void test_queue_malloc_error(void) +{ + // メモリ確保失敗 + KcQueue *queue; + ut_alloc_control(0) + { + queue = KcQueue_new(0); + } + assert_null(queue); + + // 内部管理のリストメモリ確保失敗 + ut_alloc_control(1) + { + queue = KcQueue_new(0); + } + assert_null(queue); + + // 追加時のメモリ確保失敗 + + queue = KcQueue_new(10); + ut_alloc_control(0) + { + bool ret = queue->offer(queue, "XYZ", 4); + assert_false(ret); + } + KcQueue_delete(queue); +} diff --git a/modules/test/src/ut.c b/modules/test/src/ut.c index 1af0683..c84b7b9 100644 --- a/modules/test/src/ut.c +++ b/modules/test/src/ut.c @@ -17,6 +17,7 @@ suite_memory_listener(); suite_memory_mark(); suite_memory(); + suite_queue(); KcMemory_start(false); KcMemory_start(true); @@ -25,3 +26,30 @@ return 0; } + +// メモリテスト用 +static int ut_can_alloc_counter = 0; +static bool ut_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_can_alloc_counter--; + if (ut_can_alloc_counter < 0) + { + return false; + } + return true; +} +UT_KcMemory_can_alloc_func _ut_can_alloc_func(int counter) +{ + ut_can_alloc_counter = counter; + return ut_can_alloc; +} \ No newline at end of file diff --git a/modules/include/kc_queue.h b/modules/include/kc_queue.h new file mode 100644 index 0000000..1fc92ae --- /dev/null +++ b/modules/include/kc_queue.h @@ -0,0 +1,148 @@ +/** + * @file kc_queue.h + * @brief Queue モジュールヘッダファイル + * @copyright 2002 - 2023 Nomura Kei + * @depends + * kc.h + */ +#ifndef KC_QUEUE_H +#define KC_QUEUE_H + +#include + +#ifdef __cplusplus +extern "C" +{ + namespace kc + { + using namespace std; +#endif + + /** + * キュー。 + */ + typedef struct KcQueue_ + { + + /** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ + int (*size)(struct KcQueue_ *queue); + + /** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ + bool (*is_empty)(struct KcQueue_ *queue); + + /** + * キューに指定された要素が含まれる場合に true を返します。 + * + * @param queue 対象キュー + * @param element 要素 + * @param size 要素のサイズ + */ + bool (*contains)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ + bool (*offer)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ + bool (*poll)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素へのポインタ + */ + void *(*peek)(struct KcQueue_ *queue, size_t *size); + + /** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ + void (*put)(struct KcQueue_ *queue, const void *element, size_t size); + + /** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * size が取り出す要素のサイズより小さい場合、element には、指定されたサイズまでがコピーされます。 + * size には、実際の要素のサイズが格納されます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ + void (*take)(struct KcQueue_ *queue, void *element, size_t *size); + + /** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ + void (*clear)(struct KcQueue_ *queue); + + /** + * キュー管理情報クリア用関数 + * + * @param queue 対象キュー + */ + void (*cleanup_info)(struct KcQueue_ *queue); + + /** + * キュー管理情報 + * 本オブジェクトはリスト実装者が利用するための情報へのポインタとなります。 + */ + void *_info; + + } KcQueue; + + /** + * Queue を構築します。 + * size に 0 が指定された場合、キューサイズ INT_MAX として処理されます。 + * + * @param size キューのサイズ + * @return Queue + */ + KcQueue *KcQueue_new(int size); + + /** + * KcQueue を破棄します。 + * + * @param queue 破棄するキュー + */ + void KcQueue_delete(KcQueue *queue); + +#ifdef __cplusplus + } // namespace kc +} // extern "C" +#endif +#endif // KC_QUEUE_H diff --git a/modules/src/kc_list_array.c b/modules/src/kc_list_array.c index 99a171f..246ed14 100644 --- a/modules/src/kc_list_array.c +++ b/modules/src/kc_list_array.c @@ -597,6 +597,7 @@ static void KcArrayList_cleanup_info(KcList *list) { KcArrayListInfo *info = (KcArrayListInfo *)list->_info; + mtx_destroy(&(info->mutex)); free(info->data); } diff --git a/modules/src/kc_list_linked.c b/modules/src/kc_list_linked.c index a6a41c3..30575b9 100644 --- a/modules/src/kc_list_linked.c +++ b/modules/src/kc_list_linked.c @@ -611,7 +611,9 @@ */ static void KcLinkedList_cleanup_info(KcList *list) { + KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info; list->clear(list); + mtx_destroy(&(info->mutex)); } //////////////////////////////////////////////////////////////////////////////// diff --git a/modules/src/kc_queue.c b/modules/src/kc_queue.c new file mode 100644 index 0000000..544d763 --- /dev/null +++ b/modules/src/kc_queue.c @@ -0,0 +1,312 @@ +/** + * @file kc_queue.c + * @brief キューモジュール + * @copyright 2003 - 2023 Nomura Kei + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/** + * KcQueue 管理情報 + */ +typedef struct +{ + mtx_t mutex; //!< ロック用j + cnd_t not_empty; //!< 条件変数(Empty) + cnd_t not_full; //!< 条件変数(Full) + int queue_size; //!< キューサイズ + KcList *list; //!< キュー内部で利用するリスト +} KcQueueInfo; + +// ============================================================================= +// プロトタイプ宣言 +// ============================================================================= +static int KcQueue_size(struct KcQueue_ *queue); +static bool KcQueue_is_empty(struct KcQueue_ *queue); +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size); +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size); +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size); +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size); +static void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size); +static void KcQueue_clear(struct KcQueue_ *queue); +static void KcQueue_cleanup_info(struct KcQueue_ *queue); + +// ============================================================================= +// new +// ============================================================================= +/** + * Queue を構築します。 + * + * @param size キューのサイズ + * @return Queue + */ +KcQueue *KcQueue_new(int size) +{ + // KcQueue の管理構造 + // +--------------+ + // | KcQueue | + // | ... | + // | _info -----------+ + // +--------------+ | + // | <_info> | <---+ + // | list | + // +--------------+ + KcQueue *queue = (KcQueue *)malloc(sizeof(KcQueue) + sizeof(KcQueueInfo)); + KcList *list = KcList_new_LinkedList(); + if ((queue != NULL) && (list != NULL)) + { + queue->size = KcQueue_size; + queue->is_empty = KcQueue_is_empty; + queue->contains = KcQueue_contains; + queue->offer = KcQueue_offer; + queue->poll = KcQueue_poll; + queue->peek = KcQueue_peek; + queue->put = KcQueue_put; + queue->take = KcQueue_take; + queue->clear = KcQueue_clear; + queue->cleanup_info = KcQueue_cleanup_info; + queue->_info = (queue + 1); + + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + info->list = list; + info->queue_size = (size == 0) ? INT_MAX : size; + mtx_init(&(info->mutex), mtx_plain); + cnd_init(&(info->not_empty)); + cnd_init(&(info->not_full)); + } + else + { // 何れかのメモリ確保に失敗したら、メモリを解放する。 + free(queue); + queue = NULL; + free(list); + list = NULL; + } + return queue; +} + +// ============================================================================= +// delete +// ============================================================================= +/** + * Queue をします。 + * + * @param queue 破棄するキュー + */ +void KcQueue_delete(KcQueue *queue) +{ + queue->cleanup_info(queue); + free(queue); +} + +// ============================================================================= +// size +// ============================================================================= +/** + * キューに格納されている要素の数を返します。 + * + * @param queue 対象キュー + * @return 対象キュー内の要素数 + */ +static int KcQueue_size(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + size_t size = info->list->size(info->list); + return (int)size; +} + +// ============================================================================= +// is_empty +// ============================================================================= +/** + * キューに要素がない場合に true を返します。 + * + * @param queue 対象キュー + * @return 対象キューに要素が含まれていない場合は true + */ +static bool KcQueue_is_empty(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->is_empty(info->list); +} + +// ============================================================================= +// contains +// ============================================================================= +/** + * 指定の要素が対象キューに含まれている場合に true を返します。 + * + * @param queue 対象キュー + * @param element 対象キュー内にあるかどうか判定される要素 + * @param size 要素のサイズ + * @return 指定された要素が対象キュー内にある場合は true + */ +static bool KcQueue_contains(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->contains(info->list, element, size); +} + +// ============================================================================= +// offer +// ============================================================================= +/** + * キューに要素を追加します。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + * @return true/false (追加成功/失敗) + */ +static bool KcQueue_offer(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + int now_size = (int)info->list->size(info->list); + if (now_size < info->queue_size) + { + is_success = info->list->add(info->list, -1, element, size); + if (is_success) + { + cnd_signal(&(info->not_empty)); + } + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// poll +// ============================================================================= +/** + * キューより要素を取り出します。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + * @return true/false (要素の取り出し成功/失敗[要素がない]) + */ +static bool KcQueue_poll(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + bool is_success = false; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + bool is_empty = info->list->is_empty(info->list); + if (!is_empty) + { + is_success = info->list->remove(info->list, 0, element, size); + // is_success は常に true + cnd_signal(&(info->not_full)); + } + mtx_unlock(&(info->mutex)); // ===== Lock End =============== + return is_success; +} + +// ============================================================================= +// peek +// ============================================================================= +/** + * キューより要素を取得しますが、削除しません。 + * + * @param queue 対象キュー + * @param size 取り出された要素のサイズが格納されます。 + * @return 要素 + */ +static void *KcQueue_peek(struct KcQueue_ *queue, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + return info->list->get(info->list, 0, size); +} + +// ============================================================================= +// put +// ============================================================================= +/** + * キューに要素を追加します。 + * キューが一杯の状態で追加できない場合、追加できるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 追加する要素 + * @param size 要素のサイズ + */ +static void KcQueue_put(struct KcQueue_ *queue, const void *element, size_t size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while ((int)info->list->size(info->list) == info->queue_size) + { + cnd_wait(&(info->not_full), &(info->mutex)); + } + info->list->add(info->list, -1, element, size); + cnd_signal(&(info->not_empty)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// take +// ============================================================================= +/** + * キューより要素を取り出します。 + * 必要に応じて、要素が利用可能になるまでブロックされます。 + * + * @param queue 対象キュー + * @param element 取り出された要素が格納されます。 + * @param size element のバッファサイズを指定します。また、取り出された要素のサイズが格納されます。 + */ +void KcQueue_take(struct KcQueue_ *queue, void *element, size_t *size) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + while (info->list->is_empty(info->list)) + { + cnd_wait(&(info->not_empty), &(info->mutex)); + } + info->list->remove(info->list, 0, element, size); + cnd_signal(&(info->not_full)); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clear +// ============================================================================= +/** + * すべての要素をキューより削除します。 + * + * @param queue 対象キュー + */ +void KcQueue_clear(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + mtx_lock(&(info->mutex)); // ===== Lock Start =============== + info->list->clear(info->list); + mtx_unlock(&(info->mutex)); // ===== Lock End =============== +} + +// ============================================================================= +// clearnup_info +// ============================================================================= +/** + * クリア + * + * @param queue 対象キュー + */ +static void KcQueue_cleanup_info(struct KcQueue_ *queue) +{ + KcQueueInfo *info = (KcQueueInfo *)queue->_info; + KcList_delete(info->list); + mtx_destroy(&(info->mutex)); + cnd_destroy(&(info->not_empty)); + cnd_destroy(&(info->not_full)); +} diff --git a/modules/test/src/test_list_array.c b/modules/test/src/test_list_array.c index 1dec74e..bfdf199 100644 --- a/modules/test/src/test_list_array.c +++ b/modules/test/src/test_list_array.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_array_new(void); static void test_list_array_add(void); @@ -445,71 +447,48 @@ KcList_delete(list); } -#include "ut.h" -static int UT_ListArray_can_alloc_counter = 0; -static bool UT_ListArray_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_ListArray_can_alloc_counter--; - if (UT_ListArray_can_alloc_counter < 0) - { - return false; - } - return true; -} - /** * ArrayList メモリ確保失敗。 */ static void test_list_array_malloc_error(void) { // ArrayList のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcList *list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(0) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // ArrayList のデータ用メモリ確保失敗 - UT_ListArray_can_alloc_counter = 1; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - list = KcList_new_ArrayList(sizeof(int), 3); - _UT_KcMemory_can_alloc = NULL; - assert_null(list); + ut_alloc_control(1) + { + KcList *list = KcList_new_ArrayList(sizeof(int), 3); + assert_null(list); + } // Array Size 拡張時のメモリ確保失敗 - list = KcList_new_ArrayList(sizeof(int), 3); + KcList *list = KcList_new_ArrayList(sizeof(int), 3); int val = 10; list->add(list, 0, &val, sizeof(int)); list->add(list, 1, &val, sizeof(int)); list->add(list, 2, &val, sizeof(int)); - bool ret; - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - // size 以上 - ret = list->add(list, 3, &val, sizeof(int)); - assert_false(ret); - // 0 指定 - ret = list->add(list, 0, &val, sizeof(int)); - assert_false(ret); - _UT_KcMemory_can_alloc = NULL; + ut_alloc_control(0) + { + // size 以上 + bool ret = list->add(list, 3, &val, sizeof(int)); + assert_false(ret); + // 0 指定 + ret = list->add(list, 0, &val, sizeof(int)); + assert_false(ret); + } // Iterator 生成時のメモリ確保失敗 - UT_ListArray_can_alloc_counter = 0; - _UT_KcMemory_can_alloc = UT_ListArray_can_alloc; - KcIterator *ite = list->iterator(list, 0); - _UT_KcMemory_can_alloc = NULL; - assert_null(ite); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + assert_null(ite); + } KcList_delete(list); } \ No newline at end of file diff --git a/modules/test/src/test_list_linked.c b/modules/test/src/test_list_linked.c index a542d7b..27ac267 100644 --- a/modules/test/src/test_list_linked.c +++ b/modules/test/src/test_list_linked.c @@ -7,6 +7,8 @@ #include #include +#include "ut.h" + // プロトタイプ宣言 static void test_list_linked_new(void); static void test_list_linked_add(void); @@ -461,63 +463,41 @@ 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); + ut_alloc_control(0) + { + KcList *list = KcList_new_LinkedList(); + 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)); + KcList *list = KcList_new_LinkedList(); + ut_alloc_control(0) + { + bool ret = list->add(list, 0, "ABC", 4); + 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); + ut_alloc_control(0) + { + KcIterator *ite = list->iterator(list, 0); + 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)); + ut_alloc_control(0) + { + list->set(list, 0, "XYZXYZ", 7, NULL, 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/test_queue.c b/modules/test/src/test_queue.c new file mode 100644 index 0000000..cbec7e0 --- /dev/null +++ b/modules/test/src/test_queue.c @@ -0,0 +1,328 @@ +#include +#include +#include + +#include +#include +#include +#include +#include + +#include "ut.h" + +// プロトタイプ宣言 +static void test_queue_new(void); +static void test_queue_offer(void); +static void test_queue_put(void); +static void test_queue_size(void); +static void test_queue_offer_ng(void); +static void test_queue_malloc_error(void); + +/** + * KcQueue 単体テストスイート + */ +void suite_queue(void) +{ + KcUt *ut = KcUt_get_instance(); + ut->add(ut, UT_TESTCASE, "queue new/delete", test_queue_new); + ut->add(ut, UT_TESTCASE, "queue offer/peek/poll", test_queue_offer); + ut->add(ut, UT_TESTCASE, "queue put/take", test_queue_put); + ut->add(ut, UT_TESTCASE, "queue size", test_queue_size); + ut->add(ut, UT_TESTCASE, "queue offer ng", test_queue_offer_ng); + ut->add(ut, UT_TESTCASE, "queue malloc error", test_queue_malloc_error); +} + +/** + * Queue 生成/破棄。 + * + * @process KcQueue_new を実行する。。 + * @result KcQueue が生成されること。 + * + * @process KcQueue_delete にて Queue を破棄する。 + * @result Queue が破棄されること。 + */ +static void test_queue_new(void) +{ + KcQueue *queue = KcQueue_new(0); + assert_not_null(queue); + KcQueue_delete(queue); + + // リストが残った状態での削除 + queue = KcQueue_new(0); + queue->offer(queue, "ABC", 4); + assert_not_null(queue); + KcQueue_delete(queue); +} + +// for offer thread +static int test_queue_offer_thread(void *arg) +{ + KcQueue *queue = (KcQueue *)arg; + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + for (int i = 0; i < 100; i++) + { + printf("offer: %d\n", i); + queue->offer(queue, &i, sizeof(int)); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for poll thread +static int test_queue_poll_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int *val = queue->peek(queue, NULL); + if (val == NULL) + { + printf("peek: (null)\n"); + } + else + { + printf("peek: %d\n", *val); + } + + int element; + size_t size = sizeof(int); + bool is_success = queue->poll(queue, &element, &size); + if (is_success) + { + printf("poll: %d\n", element); + } + else + { + printf("poll: (null)\n"); + } + thrd_sleep(&spec, NULL); + } + return 0; +} + +/** + * キューへの値追加/取得。 + */ +static void test_queue_offer(void) +{ + KcQueue *queue = KcQueue_new(10); + + thrd_t offer_thread, poll_thread; + + thrd_create(&offer_thread, test_queue_offer_thread, queue); + thrd_create(&poll_thread, test_queue_poll_thread, queue); + + thrd_join(offer_thread, NULL); + thrd_join(poll_thread, NULL); + KcQueue_delete(queue); +} + +// for put thread +static int test_queue_put_thread(void *arg) +{ + KcQueue *queue = (KcQueue *)arg; + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1 * 1000; + for (int i = 0; i < 100; i++) + { + queue->put(queue, &i, sizeof(int)); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for take thread +static int test_queue_take_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 1; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int element; + size_t size = sizeof(int); + queue->take(queue, &element, &size); + assert_equals(i, element); + thrd_sleep(&spec, NULL); + } + return 0; +} + +// for take thread +static int test_queue_take2_thread(void *arg) +{ + struct timespec spec; + spec.tv_sec = 0; + spec.tv_nsec = 100 * 1000; + KcQueue *queue = (KcQueue *)arg; + for (int i = 0; i < 100; i++) + { + int element; + size_t size = sizeof(int); + queue->take(queue, &element, &size); + assert_equals(i, element); + thrd_sleep(&spec, NULL); + } + return 0; +} + +/** + * キューへの値追加/取得。 + */ +static void test_queue_put(void) +{ + { + KcQueue *queue = KcQueue_new(0); + thrd_t put_thread, take_thread; + thrd_create(&put_thread, test_queue_put_thread, queue); + thrd_create(&take_thread, test_queue_take_thread, queue); + thrd_join(put_thread, NULL); + thrd_join(take_thread, NULL); + KcQueue_delete(queue); + } + + // PUT ブロックパターン + { + KcQueue *queue = KcQueue_new(5); + thrd_t put_thread, take_thread; + thrd_create(&put_thread, test_queue_put_thread, queue); + thrd_create(&take_thread, test_queue_take2_thread, queue); + thrd_join(put_thread, NULL); + thrd_join(take_thread, NULL); + KcQueue_delete(queue); + } +} + +/** + * キューサイズ取得 + */ +static void test_queue_size(void) +{ + KcQueue *queue = KcQueue_new(0); + + // キューへ追加 + bool ret = queue->offer(queue, "ABC", 4); + assert_true(ret); + ret = queue->offer(queue, "DEFG", 5); + int size = queue->size(queue); + assert_equals(2, size); + bool is_empty = queue->is_empty(queue); + assert_false(is_empty); + + bool is_contains = queue->contains(queue, "ABC", 4); + assert_true(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_true(is_contains); + + char buffer[10]; + size_t element_size; + // 取り出し [peek] + const char *val = (const char *)queue->peek(queue, &element_size); + assert_equals(4, element_size); + assert_equals("ABC", val); + size = queue->size(queue); + assert_equals(2, size); + is_empty = queue->is_empty(queue); + assert_false(is_empty); + // 取り出し [poll] (サイズ不足) + for (int i = 0; i < 10; i++) + { + buffer[i] = 'X'; + } + buffer[9] = '\0'; + element_size = 2; + queue->poll(queue, buffer, &element_size); + assert_equals("ABXXXXXXX", buffer); + assert_equals(4, element_size); + size = queue->size(queue); + assert_equals(1, size); + is_empty = queue->is_empty(queue); + assert_false(is_empty); + is_contains = queue->contains(queue, "ABC", 4); + assert_false(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_true(is_contains); + + // 取り出し [poll] + for (int i = 0; i < 10; i++) + { + buffer[i] = 'X'; + } + buffer[9] = '\0'; + element_size = 10; + queue->poll(queue, buffer, &element_size); + assert_equals("DEFG", buffer); + assert_equals(5, element_size); + size = queue->size(queue); + assert_equals(0, size); + is_empty = queue->is_empty(queue); + assert_true(is_empty); + is_contains = queue->contains(queue, "ABC", 4); + assert_false(is_contains); + is_contains = queue->contains(queue, "DEFG", 5); + assert_false(is_contains); + + KcQueue_delete(queue); +} + +/** + * offer 失敗。 + */ +static void test_queue_offer_ng(void) +{ + KcQueue *queue = KcQueue_new(3); + + bool ret; + ret = queue->offer(queue, "ABC", 4); + assert_true(ret); + ret = queue->offer(queue, "DEF", 4); + assert_true(ret); + ret = queue->offer(queue, "GHI", 4); + assert_true(ret); + ret = queue->offer(queue, "JKL", 4); + assert_false(ret); + + queue->clear(queue); + ret = queue->is_empty(queue); + assert_true(ret); + + KcQueue_delete(queue); +} + +/** + * Queue メモリ確保失敗。 + */ +static void test_queue_malloc_error(void) +{ + // メモリ確保失敗 + KcQueue *queue; + ut_alloc_control(0) + { + queue = KcQueue_new(0); + } + assert_null(queue); + + // 内部管理のリストメモリ確保失敗 + ut_alloc_control(1) + { + queue = KcQueue_new(0); + } + assert_null(queue); + + // 追加時のメモリ確保失敗 + + queue = KcQueue_new(10); + ut_alloc_control(0) + { + bool ret = queue->offer(queue, "XYZ", 4); + assert_false(ret); + } + KcQueue_delete(queue); +} diff --git a/modules/test/src/ut.c b/modules/test/src/ut.c index 1af0683..c84b7b9 100644 --- a/modules/test/src/ut.c +++ b/modules/test/src/ut.c @@ -17,6 +17,7 @@ suite_memory_listener(); suite_memory_mark(); suite_memory(); + suite_queue(); KcMemory_start(false); KcMemory_start(true); @@ -25,3 +26,30 @@ return 0; } + +// メモリテスト用 +static int ut_can_alloc_counter = 0; +static bool ut_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_can_alloc_counter--; + if (ut_can_alloc_counter < 0) + { + return false; + } + return true; +} +UT_KcMemory_can_alloc_func _ut_can_alloc_func(int counter) +{ + ut_can_alloc_counter = counter; + return ut_can_alloc; +} \ No newline at end of file diff --git a/modules/test/src/ut.h b/modules/test/src/ut.h index 1bcbb28..224e63b 100644 --- a/modules/test/src/ut.h +++ b/modules/test/src/ut.h @@ -13,9 +13,30 @@ extern void suite_memory_listener(void); extern void suite_memory_mark(void); extern void suite_memory(void); +extern void suite_queue(void); extern bool (*_UT_KcMemory_can_alloc)( KcMemoryEntry *entry, size_t alignment, size_t size, KcMemoryMark mark, const char *file, const char *func, int line); +typedef bool (*UT_KcMemory_can_alloc_func)( + KcMemoryEntry *entry, size_t alignment, size_t size, + KcMemoryMark mark, const char *file, const char *func, int line); + +UT_KcMemory_can_alloc_func _ut_can_alloc_func(int counter); + +/** + * ut_alloc_control(0) + * { + * // メモリ確保失敗させたい処理 + * } + * + * ut_alloc_control(1) + * { + * // 2回目にメモリ確保失敗させたい処理 + * } + */ +#define ut_alloc_control(counter) \ + for (_UT_KcMemory_can_alloc = _ut_can_alloc_func(counter); _UT_KcMemory_can_alloc != NULL; _UT_KcMemory_can_alloc = NULL) + #endif // UT_H \ No newline at end of file