/**
* @file kc_list_array.c
* @brief 配列リストモジュール
* @copyright 2003 - 2023 Nomura Kei
*/
#include <kc.h>
#if defined(__GNUC__)
#define _GNU_SOURCE 1
#if !(KC_IS_WINDOWS)
#define qsort_s qsort_r
#endif
#endif // defined(__GNUC__)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <kc_lock_guard.h>
#include <kc_memory.h>
#include <kc_list.h>
#include <kc_iterator.h>
/**
* KcArrayList 管理情報
*/
typedef struct
{
mtx_t mutex; //!< ロック用
size_t element_size; //!< 要素のサイズ
int init_capacity; //!< 初期指定容量
int capacity; //!< 現在の容量
int size; //!< 現在の要素数
int padding[2]; //!< パディング
void *data; //!< データ格納用バッファ
} KcArrayListInfo;
// =============================================================================
// プロトタイプ宣言
// =============================================================================
static int KcArrayList_size(KcList *list);
static bool KcArrayList_is_empty(KcList *list);
static bool KcArrayList_contains(KcList *list, const void *element, size_t size);
static bool KcArrayList_add(KcList *list, int index, const void *element, size_t size);
static bool KcArrayList_remove(KcList *list, int index, void *element, size_t *size);
static void KcArrayList_sort(KcList *list,
int (*comparator)(const void *element1, size_t size1,
const void *element2, size_t size2, void *args),
void *args);
static void KcArrayList_clear(KcList *list);
static void *KcArrayList_get(KcList *list, int index, size_t *size);
static bool KcArrayList_set(KcList *list, int index, const void *element, size_t size,
void *org_element, size_t *org_size);
static int KcArrayList_index_of(KcList *list, const void *element, size_t size);
static int KcArrayList_last_index_of(KcList *list, const void *element, size_t size);
static KcIterator *KcArrayList_iterator(KcList *list, int index);
static void KcArrayList_cleanup_info(KcList *list);
static bool KcArrayList_increase_capacity(KcArrayListInfo *info);
static void KcArrayList_reduce_capacity(KcArrayListInfo *info);
static bool KcArrayList_set_capacity(KcArrayListInfo *info, int capacity);
/**
* 指定されたサイズの要素を扱う ArrayList を構築します。
*
* @param size 要素のサイズ
* @param cap リストの初期容量
* @return ArrayList
*/
KcList *KcList_new_ArrayList(size_t size, int cap)
{
// KcArrayList の管理構造
// +--------------+
// | KcList |
// | ... |
// | _info -----------+
// +--------------+ |
// | <_info> | <---+
// | element_size |
// | capacity |
// | data ----------->+--------------+
// +--------------+ |<data> |
// | element[0] |
// | : |
KcList *list = (KcList *)malloc(sizeof(KcList) + sizeof(KcArrayListInfo));
void *data = malloc(size * cap);
if ((list != NULL) && (data != NULL))
{
list->size = KcArrayList_size;
list->is_empty = KcArrayList_is_empty;
list->contains = KcArrayList_contains;
list->add = KcArrayList_add;
list->remove = KcArrayList_remove;
list->sort = KcArrayList_sort;
list->clear = KcArrayList_clear;
list->get = KcArrayList_get;
list->set = KcArrayList_set;
list->index_of = KcArrayList_index_of;
list->last_index_of = KcArrayList_last_index_of;
list->iterator = KcArrayList_iterator;
list->cleanup_info = KcArrayList_cleanup_info;
list->_info = (list + 1);
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
mtx_init(&(info->mutex), mtx_plain | mtx_recursive);
info->element_size = size;
info->init_capacity = cap;
info->capacity = cap;
info->size = 0;
info->data = data;
}
else
{ // 何れかのメモリ確保に失敗したら、メモリを解放する。
free(list);
list = NULL;
free(data);
data = NULL;
}
return list;
}
// -----------------------------------------------------------------------------
// size
// -----------------------------------------------------------------------------
/**
* 対象リスト内にある要素の数を返します。
*
* @param list 対象リスト
* @return 対象リスト内の要素数
*/
static int KcArrayList_size(KcList *list)
{
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
int size = -1;
kc_lock_guard(&(info->mutex))
{
size = info->size;
}
return size;
}
// -----------------------------------------------------------------------------
// is_empty
// -----------------------------------------------------------------------------
/**
* 対象リストに要素がない場合に true を返します。
*
* @param list 対象リスト
* @return 対象リストに要素が含まれていない場合は true
*/
static bool KcArrayList_is_empty(KcList *list)
{
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
bool is_empty = true;
kc_lock_guard(&(info->mutex))
{
is_empty = (info->size == 0);
}
return is_empty;
}
// -----------------------------------------------------------------------------
// contains
// -----------------------------------------------------------------------------
/**
* 指定の要素が対象リストに含まれている場合に true を返します。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
*
* @param list 対象リスト
* @param element 対象リスト内にあるかどうか判定される要素
* @param size 要素のサイズ
* @return 指定された要素が対象リスト内にある場合は true
*/
static bool KcArrayList_contains(KcList *list, const void *element, size_t size)
{
UNUSED_VARIABLE(size);
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
element_type *info_data = (element_type *)info->data;
bool is_contains = false;
kc_lock_guard(&(info->mutex))
{
for (int idx = 0; idx < info->size; idx++)
{
if (memcmp(&info_data[idx], element, info->element_size) == 0)
{
is_contains = true;
break;
}
}
}
return is_contains;
}
// -----------------------------------------------------------------------------
// add
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置に、指定された要素を挿入します。
* index に負値を指定した場合、末尾に要素を追加します。
* その位置の現在の要素(ある場合)とそれ以降の要素を右に移動します。(インデックスに1を加算)。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
*
* @param list 対象リスト
* @param index 指定の要素が挿入される位置のインデックス
* @param element 挿入される要素
* @param size 要素のサイズ
* @return true/false (格納成功/失敗)
*/
static bool KcArrayList_add(KcList *list, int index, const void *element, size_t size)
{
UNUSED_VARIABLE(size);
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
// insert_index は常に 0 以上
int insert_index = (index < 0) ? info->size : index;
bool is_success = true;
kc_lock_guard(&(info->mutex))
{
is_success = (insert_index <= info->size) && KcArrayList_increase_capacity(info);
element_type *info_data = (element_type *)info->data;
if (is_success)
{
if (insert_index < info->size)
{ // index 以降の要素を右に移動
size_t n = (info->size - insert_index) * info->element_size;
memmove(&info_data[insert_index + 1], &info_data[insert_index], n);
}
// データを追加
memcpy(&info_data[insert_index], element, info->element_size);
info->size++;
}
}
return is_success;
}
// -----------------------------------------------------------------------------
// remove
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置にある要素を削除します。
* 後続の要素を左に移動します(インデックスから1を減算)。
* element が NULL でない場合、削除された要素のコピーが格納されます。
* size が NULL でない場合、削除された要素のサイズが格納されます。
*
* @param list 対象リスト
* @param index 削除される要素のインデックス
* @param element 削除された要素をコピーが格納されます。
* @param size 削除された要素のサイズが格納されます。
* @return true/false (削除成功/失敗)
*/
static bool KcArrayList_remove(KcList *list, int index, void *element, size_t *size)
{
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
element_type *info_data = (element_type *)info->data;
bool is_success = false;
kc_lock_guard(&(info->mutex))
{
is_success = ((0 <= index) && (index < info->size));
if (is_success)
{
if (element != NULL)
{
memcpy(element, &info_data[index], info->element_size);
}
if (size != NULL)
{
*size = info->element_size;
}
if (index != (info->size - 1))
{ // index 以降の要素を左に移動
size_t n = (info->size - (index + 1)) * info->element_size;
memmove(&info_data[index], &info_data[index + 1], n);
}
info->size--;
}
// 容量削減
KcArrayList_reduce_capacity(info);
}
return is_success;
}
// -----------------------------------------------------------------------------
// sort
// -----------------------------------------------------------------------------
/**
* [内部利用]
* ソート情報
*/
typedef struct
{
int (*comparator)(const void *element1, size_t size1,
const void *element2, size_t size2, void *args);
size_t element_size;
void *user_args;
} KcListSortInfo;
/**
* [内部利用]
* KcArrayList_sort にて利用される、qsort_s に渡される comparator です。
*
* @param x 比較する要素1
* @param y 比較する要素2
* @param context コンテキスト(KcListSortInfo)
* @return 比較結果
*/
#if (KC_IS_WINDOWS)
static int KcArrayList_comparator(void *context, const void *x, const void *y)
#else
static int KcArrayList_comparator(const void *x, const void *y, void *context)
#endif
{
KcListSortInfo *sort_info = (KcListSortInfo *)context;
int ret = sort_info->comparator(x, sort_info->element_size, y, sort_info->element_size, sort_info->user_args);
return ret;
}
/**
* 指定された comparator が示す順序に従って、対象リストをソートします。
*
* @param list 対象リスト
* @param comparator リスト要素を比較するために使用される comparator
* @param args comparator の第5引数に渡すオブジェクト
*/
static void KcArrayList_sort(KcList *list,
int (*comparator)(const void *element1, size_t size1,
const void *element2, size_t size2, void *args),
void *args)
{
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
element_type *info_data = (element_type *)info->data;
kc_lock_guard(&(info->mutex))
{
KcListSortInfo sort_info;
sort_info.comparator = comparator;
sort_info.element_size = info->element_size;
sort_info.user_args = args;
qsort_s(
info_data,
info->size,
info->element_size,
KcArrayList_comparator,
&sort_info);
}
}
// -----------------------------------------------------------------------------
// clear
// -----------------------------------------------------------------------------
/**
* すべての要素を対象リストから削除します。
*
* @param list 対象リスト
*/
static void KcArrayList_clear(KcList *list)
{
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
kc_lock_guard(&(info->mutex))
{
((KcArrayListInfo *)list->_info)->size = 0;
KcArrayList_set_capacity(info, info->init_capacity);
}
}
// -----------------------------------------------------------------------------
// get
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置にある要素を返します。
*
* @param list 対象リスト
* @param index 取得する要素のインデックス
* @param size 要素のサイズを格納するポインタ
* @return 対象リスト内の指定された位置にある要素
*/
static void *KcArrayList_get(KcList *list, int index, size_t *size)
{
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
element_type *info_data = (element_type *)info->data;
element_type *res = NULL;
kc_lock_guard(&(info->mutex))
{
if ((0 <= index) && (index < info->size))
{
res = &info_data[index];
if (size != NULL)
{
*size = info->element_size;
}
}
else
{
errno = EINVAL;
}
}
return res;
}
// -----------------------------------------------------------------------------
// set
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置にある要素を、指定された要素に置き換えます。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
* org_element が NULL でない場合、置き換え前の要素のコピーが格納されます。
* org_size が NULL でない場合、置き換え前の要素のサイズが格納されます。
*
* @param list 対象リスト
* @param index 置換される要素のインデックス
* @param element 指定された位置に格納される要素
* @param size 指定された位置に格納される要素のサイズ
* @param org_element 指定された位置に以前あった要素のコピーが格納されます。
* @param org_size 指定された位置に以前あった要素のサイズが格納されます。
* @return true/false (置換成功/失敗)
*/
static bool KcArrayList_set(KcList *list, int index, const void *element, size_t size,
void *org_element, size_t *org_size)
{
UNUSED_VARIABLE(size);
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
element_type *info_data = (element_type *)info->data;
bool is_success = false;
kc_lock_guard(&(info->mutex))
{
is_success = ((0 <= index) && (index < info->size));
if (is_success)
{
if (org_element != NULL)
{
memcpy(org_element, &info_data[index], info->element_size);
}
if (org_size != NULL)
{
*org_size = info->element_size;
}
memcpy(&info_data[index], element, info->element_size);
}
}
return is_success;
}
// -----------------------------------------------------------------------------
// index_of
// -----------------------------------------------------------------------------
/**
* 指定された要素がこのリスト内で最初に検出された位置のインデックスを返します。
* 指定された要素がこのリストにない場合は -1 を返します。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
*
* @param list 対象リスト
* @param element 検索する要素
* @param size 検索する要素のサイズ
* @return 指定された要素がこのリスト内で最初に検出された位置のインデックス
*/
static int KcArrayList_index_of(KcList *list, const void *element, size_t size)
{
UNUSED_VARIABLE(size);
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
element_type *info_data = (element_type *)info->data;
int result_index = -1;
kc_lock_guard(&(info->mutex))
{
for (int idx = 0; idx < info->size; idx++)
{
if (memcmp(&info_data[idx], element, info->element_size) == 0)
{
result_index = idx;
break;
}
}
}
return result_index;
}
// -----------------------------------------------------------------------------
// last_index_of
// -----------------------------------------------------------------------------
/**
* 指定された要素がこのリスト内で最後に検出された位置のインデックスを返します。
* 指定された要素がこのリストにない場合は -1 を返します。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
*
* @param list 対象リスト
* @param element 検索する要素
* @param size 検索する要素のサイズ
* @return 指定された要素がこのリスト内で最後に検出された位置のインデックス
*/
static int KcArrayList_last_index_of(KcList *list, const void *element, size_t size)
{
UNUSED_VARIABLE(size);
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
typedef uint8_t element_type[info->element_size];
element_type *info_data = (element_type *)info->data;
int result_index = -1;
kc_lock_guard(&(info->mutex))
{
for (int idx = (info->size - 1); idx >= 0; idx--)
{
if (memcmp(&info_data[idx], element, info->element_size) == 0)
{
result_index = idx;
break;
}
}
}
return result_index;
}
////////////////////////////////////////////////////////////////////////////////
//
// Iterator
//
/**
* ArrayListe の Iterator 管理用構造体
*/
typedef struct KcArrayListIteratorEntry_
{
KcArrayListInfo *info; //!< ArrayList情報
int current; //!< 現在のインデックス
int size; //!< リストのサイズ
} KcArrayListIteratorEntry;
/**
* 次の要素があるか否かを返します。
*
* @param ite Iterator
* @return true/false (次の要素が存在する/存在しない)
*/
static bool KcArrayListIterator_hasNext(KcIterator *ite)
{
KcArrayListIteratorEntry *entry = (KcArrayListIteratorEntry *)ite->_info;
return (entry->current < entry->size);
}
/**
* 次の要素を取得します。
* size が指定されている場合、次の要素が size に格納されます。
* 次の要素がない場合、NULL を返します。
*
* @param ite Iterator
* @param size 要素のサイズ格納用
* @return 次の要素
*/
static const void *KcArrayListIterator_next(KcIterator *ite, size_t *size)
{
KcArrayListIteratorEntry *entry = (KcArrayListIteratorEntry *)ite->_info;
typedef uint8_t element_type[entry->info->element_size];
element_type *info_data = (element_type *)entry->info->data;
if (size != NULL)
{
*size = entry->info->element_size;
}
int tmp_index = entry->current;
entry->current++;
return info_data[tmp_index];
}
/**
* このリスト内の指定された位置で始まる、リスト内の要素を反復するイテレータを返します。
*
* @param list 対象リスト
* @param index イテレータから返される最初の要素のインデックス
* @return リスト内の指定された位置で始まる、リスト内の要素を反復するイテレータ
*/
static KcIterator *KcArrayList_iterator(KcList *list, int index)
{
size_t ite_size = sizeof(KcIterator) + sizeof(KcArrayListIteratorEntry);
KcIterator *ite = (KcIterator *)malloc(ite_size);
if (ite)
{
ite->hasNext = KcArrayListIterator_hasNext;
ite->next = KcArrayListIterator_next;
KcArrayListIteratorEntry *entry = (KcArrayListIteratorEntry *)(((KcIterator *)ite) + 1);
ite->_info = entry;
entry->info = list->_info;
entry->current = index;
entry->size = list->size(list);
}
return ite;
}
/**
* リスト情報をクリアします。
*
* @param list 対象リスト
*/
static void KcArrayList_cleanup_info(KcList *list)
{
KcArrayListInfo *info = (KcArrayListInfo *)list->_info;
mtx_destroy(&(info->mutex));
free(info->data);
}
/**
* 指定されたリスト情報のデータ容量を増やします。
* 容量を増やす必要がない場合、何もせず true を返します。
* 容量を増やすことができない場合、false を返します。
*
* @param list リスト
* @param info 配列リスト情報
* @return true/false (成功/失敗)
*/
static bool KcArrayList_increase_capacity(KcArrayListInfo *info)
{
bool is_success = true;
if (info->size >= info->capacity)
{
int new_capacity = info->capacity * 2;
is_success = KcArrayList_set_capacity(info, new_capacity);
}
return is_success;
}
/**
* 指定されたリスト情報のデータ容量を削減します。
*
* @param list リスト
* @param info 配列リスト情報
*/
static void KcArrayList_reduce_capacity(KcArrayListInfo *info)
{
if ((info->capacity > info->init_capacity) && (info->size <= (info->capacity / 4)))
{ // 初期容量より大きく、要素数が容量の1/4以下となった場合、容量を1/2に減らす。
int new_capacity = info->capacity / 2;
KcArrayList_set_capacity(info, new_capacity);
}
}
/**
* 指定されたリスト情報のデータ容量を指定された capacity に変更します。
*
* @param info 配列リスト情報
* @return true/false (成功/失敗)
*/
static bool KcArrayList_set_capacity(KcArrayListInfo *info, int capacity)
{
void *ptr = realloc(info->data, (info->element_size * capacity));
if (ptr != NULL)
{
info->data = ptr;
info->capacity = capacity;
return true;
}
return false;
}
