/**
* @file kc_list_linked.c
* @brief Linked リストモジュール
* @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>
/**
* KcLinkedList Entry 情報
*/
typedef struct KcLinkedListEntry_
{
void *value; //!< 値
size_t size; //!< 値のサイズ
struct KcLinkedListEntry_ *next; //!< 次のエントリ
struct KcLinkedListEntry_ *prev; //!< 前のエントリ
} KcLinkedListEntry;
/**
* KcLinkedList 管理情報
*/
typedef struct
{
mtx_t mutex; //!< ロック用
size_t size; //!< エントリ数
KcLinkedListEntry *head; //!< 先頭エントリ
KcLinkedListEntry *tail; //!< 末尾エントリ
} KcLinkedListInfo;
// =============================================================================
// プロトタイプ宣言
// =============================================================================
static int KcLinkedList_size(KcList *list);
static bool KcLinkedList_is_empty(KcList *list);
static bool KcLinkedList_contains(KcList *list, const void *element, size_t size);
static bool KcLinkedList_add(KcList *list, int index, const void *element, size_t size);
static bool KcLinkedList_remove(KcList *list, int index, void *element, size_t *size);
static void KcLinkedList_sort(KcList *list,
int (*comparator)(const void *element1, size_t size1,
const void *element2, size_t size2, void *args),
void *args);
static void KcLinkedList_clear(KcList *list);
static void *KcLinkedList_get(KcList *list, int index, size_t *size);
static bool KcLinkedList_set(KcList *list, int index, const void *element, size_t size,
void *org_element, size_t *org_size);
static int KcLinkedList_index_of(KcList *list, const void *element, size_t size);
static int KcLinkedList_last_index_of(KcList *list, const void *element, size_t size);
static KcIterator *KcLinkedList_iterator(KcList *list, int index);
static void KcLinkedList_cleanup_info(KcList *list);
// [内部関数用]
static KcLinkedListEntry *KcLinkedList_search(KcLinkedListInfo *info, int index);
static KcLinkedListEntry *KcLinkedList_new_entry(const void *value, size_t size);
/**
* LinkedList を構築します。
*
* @return LinkedList
*/
KcList *KcList_new_LinkedList(void)
{
// KcLinkedList の管理構造
// +--------------+
// | KcList |
// | ... |
// | _info -----------+
// +--------------+ |
// | <_info> | <---+
// | next --------+
// | prev --------|--+
// +--------------+ | |
// | <Entry> |<-+ |
// | <Entry> |<----+
// +--------------+
KcList *list = (KcList *)malloc(
sizeof(KcList) + sizeof(KcLinkedListInfo) + (sizeof(KcLinkedListEntry) * 2));
if (list != NULL)
{
list->size = KcLinkedList_size;
list->is_empty = KcLinkedList_is_empty;
list->contains = KcLinkedList_contains;
list->add = KcLinkedList_add;
list->remove = KcLinkedList_remove;
list->sort = KcLinkedList_sort;
list->clear = KcLinkedList_clear;
list->get = KcLinkedList_get;
list->set = KcLinkedList_set;
list->index_of = KcLinkedList_index_of;
list->last_index_of = KcLinkedList_last_index_of;
list->iterator = KcLinkedList_iterator;
list->cleanup_info = KcLinkedList_cleanup_info;
list->_info = (list + 1);
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
mtx_init(&(info->mutex), mtx_plain | mtx_recursive);
info->head = (KcLinkedListEntry *)(info + 1);
info->tail = info->head + 1;
info->size = 0;
info->head->next = info->head->prev = info->tail;
info->tail->next = info->tail->prev = info->head;
info->head->value = info->tail->value = NULL;
}
return list;
}
// -----------------------------------------------------------------------------
// size
// -----------------------------------------------------------------------------
/**
* 対象リスト内にある要素の数を返します。
*
* @param list 対象リスト
* @return 対象リスト内の要素数
*/
static int KcLinkedList_size(KcList *list)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
int size = -1;
kc_lock_guard(&(info->mutex))
{
size = info->size;
}
return size;
}
// -----------------------------------------------------------------------------
// is_empty
// -----------------------------------------------------------------------------
/**
* 対象リストに要素がない場合に true を返します。
*
* @param list 対象リスト
* @return 対象リストに要素が含まれていない場合は true
*/
static bool KcLinkedList_is_empty(KcList *list)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)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 KcLinkedList_contains(KcList *list, const void *element, size_t size)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
bool is_contains = false;
kc_lock_guard(&(info->mutex))
{
KcLinkedListEntry *entry = info->head->next;
while (entry != info->tail)
{
if ((entry->size == size) && (memcmp(entry->value, element, size) == 0))
{
is_contains = true;
break;
}
entry = entry->next;
}
}
return is_contains;
}
// -----------------------------------------------------------------------------
// add
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置に、指定された要素を挿入します。
* index に負値を指定した場合、末尾に要素を追加します。
* その位置の現在の要素(ある場合)とそれ以降の要素を右に移動します。(インデックスに1を加算)。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
*
* @param list 対象リスト
* @param index 指定の要素が挿入される位置のインデックス
* @param element 挿入される要素
* @param size 要素のサイズ
* @return true/false (格納成功/失敗)
*/
static bool KcLinkedList_add(KcList *list, int index, const void *element, size_t size)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
bool is_success = false;
kc_lock_guard(&(info->mutex))
{
KcLinkedListEntry *insert_pos = KcLinkedList_search(info, index);
if (insert_pos != NULL)
{ // エントリ作成
KcLinkedListEntry *entry = KcLinkedList_new_entry(element, size);
if (entry != NULL)
{ // リストに追加 (insert_pos の一つ前に追加)
info->size++;
entry->next = insert_pos;
entry->prev = insert_pos->prev;
insert_pos->prev->next = entry;
insert_pos->prev = entry;
is_success = true;
}
}
}
return is_success;
}
// -----------------------------------------------------------------------------
// remove
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置にある要素を削除します。
* 後続の要素を左に移動します(インデックスから1を減算)。
* element と size が共に NULL でない場合、削除された要素のコピーが格納されます。
*
* @param list 対象リスト
* @param index 削除される要素のインデックス
* @param element 削除された要素をコピーが格納されます。
* @param size element のバッファサイズを指定します。また、削除された要素のサイズが格納されます。
* @return true/false (削除成功/失敗)
*/
static bool KcLinkedList_remove(KcList *list, int index, void *element, size_t *size)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
bool is_success = false;
kc_lock_guard(&(info->mutex))
{
KcLinkedListEntry *entry = KcLinkedList_search(info, index);
if ((entry != NULL) && (entry != info->tail))
{
if ((element != NULL) && (size != NULL))
{
size_t copy_size = (entry->size < *size) ? entry->size : *size;
memcpy(element, entry->value, copy_size);
*size = entry->size;
}
entry->prev->next = entry->next;
entry->next->prev = entry->prev;
free(entry);
info->size--;
is_success = true;
}
}
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;
/**
* [内部利用]
* KcLinkedList_sort にて利用される、qsort_s に渡される comparator です。
*
* @param x 比較する要素1
* @param y 比較する要素2
* @param context コンテキスト(KcListSortInfo)
* @return 比較結果
*/
#if (KC_IS_WINDOWS)
static int KcLinkedList_comparator(void *context, const void *x, const void *y)
#else
static int KcLinkedList_comparator(const void *x, const void *y, void *context)
#endif // KC_IS_WINDOWS
{
KcListSortInfo *sort_info = (KcListSortInfo *)context;
const KcLinkedListEntry **entry_x = (const KcLinkedListEntry **)x;
const KcLinkedListEntry **entry_y = (const KcLinkedListEntry **)y;
int ret = sort_info->comparator(
(*entry_x)->value,
(*entry_x)->size,
(*entry_y)->value,
(*entry_y)->size,
sort_info->user_args);
return ret;
}
/**
* 指定された comparator が示す順序に従って、対象リストをソートします。
*
* @param list 対象リスト
* @param comparator リスト要素を比較するために使用される comparator
* @param args comparator の第5引数に渡すオブジェクト
*/
static void KcLinkedList_sort(KcList *list,
int (*comparator)(const void *element1, size_t size1,
const void *element2, size_t size2, void *args),
void *args)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
kc_lock_guard(&(info->mutex))
{
// Linked List エントリへのポインタを格納する配列を生成する。
KcLinkedListEntry **ptr_list = (KcLinkedListEntry **)calloc(
info->size, sizeof(KcLinkedListEntry *));
int idx = 0;
for (KcLinkedListEntry *entry = info->head->next; entry != info->tail; entry = entry->next)
{
ptr_list[idx] = entry;
idx++;
}
// ソート処理
KcListSortInfo sort_info;
sort_info.comparator = comparator;
sort_info.user_args = args;
qsort_s(
ptr_list,
info->size,
sizeof(KcLinkedListEntry *),
KcLinkedList_comparator,
&sort_info);
// 配列の情報を元にエントリを再構成する。
KcLinkedListEntry *prev_entry = info->head;
for (int idx2 = 0; idx2 < (int)info->size; idx2++)
{
KcLinkedListEntry *entry = ptr_list[idx2];
prev_entry->next = entry;
entry->prev = prev_entry;
prev_entry = entry;
}
prev_entry->next = info->tail;
info->tail->prev = prev_entry;
printf("---free(ptr_list) %p---\n", ptr_list);
free(ptr_list);
printf("---end---\n");
}
}
// -----------------------------------------------------------------------------
// clear
// -----------------------------------------------------------------------------
/**
* すべての要素を対象リストから削除します。
*
* @param list 対象リスト
*/
static void KcLinkedList_clear(KcList *list)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
kc_lock_guard(&(info->mutex))
{
KcLinkedListEntry *entry;
entry = info->head->next;
while (entry != info->tail)
{
entry = entry->next;
free(entry->prev);
}
info->size = 0;
info->head->next = info->head->prev = info->tail;
info->tail->next = info->tail->prev = info->head;
info->head->value = info->tail->value = NULL;
}
}
// -----------------------------------------------------------------------------
// get
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置にある要素を返します。
*
* @param list 対象リスト
* @param index 取得する要素のインデックス
* @param size 要素のサイズを格納するポインタ
* @return 対象リスト内の指定された位置にある要素
*/
static void *KcLinkedList_get(KcList *list, int index, size_t *size)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
void *res = NULL;
kc_lock_guard(&(info->mutex))
{
KcLinkedListEntry *entry = KcLinkedList_search(info, index);
if ((entry != NULL) && (entry != info->tail))
{
res = entry->value;
if (size)
{
*size = entry->size;
}
}
else
{
errno = EINVAL;
}
}
return res;
}
// -----------------------------------------------------------------------------
// set
// -----------------------------------------------------------------------------
/**
* 対象リスト内の指定された位置にある要素を、指定された要素に置き換えます。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
* org_element と org_size が共にNULL でない場合、置き換え前の要素のコピーが格納されます。
*
* @param list 対象リスト
* @param index 置換される要素のインデックス
* @param element 指定された位置に格納される要素
* @param size 指定された位置に格納される要素のサイズ
* @param org_element 指定された位置に以前あった要素のコピーが格納されます。
* @param org_size org_element のサイズを指定します。また、指定された位置に以前あった要素のサイズが格納されます。
* @return true/false (置換成功/失敗)
*/
static bool KcLinkedList_set(KcList *list, int index, const void *element, size_t size,
void *org_element, size_t *org_size)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
bool is_success = false;
kc_lock_guard(&(info->mutex))
{
KcLinkedListEntry *remove_entry = KcLinkedList_search(info, index);
if ((remove_entry != NULL) && (remove_entry != info->tail))
{
KcLinkedListEntry *new_entry = KcLinkedList_new_entry(element, size);
if (new_entry)
{
if ((org_element != NULL) && (org_size != NULL))
{
size_t copy_size = (remove_entry->size < *org_size) ? remove_entry->size : *org_size;
memcpy(org_element, remove_entry->value, copy_size);
*org_size = remove_entry->size;
}
// 削除する位置に新たなエントリを追加
new_entry->next = remove_entry->next;
new_entry->prev = remove_entry->prev;
remove_entry->prev->next = new_entry;
remove_entry->next->prev = new_entry;
free(remove_entry);
is_success = true;
}
}
}
return is_success;
}
// -----------------------------------------------------------------------------
// index_of
// -----------------------------------------------------------------------------
/**
* 指定された要素がこのリスト内で最初に検出された位置のインデックスを返します。
* 指定された要素がこのリストにない場合は -1 を返します。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
*
* @param list 対象リスト
* @param element 検索する要素
* @param size 検索する要素のサイズ
* @return 指定された要素がこのリスト内で最初に検出された位置のインデックス
*/
static int KcLinkedList_index_of(KcList *list, const void *element, size_t size)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
int result_index = -1;
kc_lock_guard(&(info->mutex))
{
int idx = 0;
for (KcLinkedListEntry *entry = info->head->next; entry != info->tail; entry = entry->next)
{
if ((size == entry->size) && (memcmp(entry->value, element, entry->size) == 0))
{
result_index = idx;
break;
}
idx++;
}
}
return result_index;
}
// -----------------------------------------------------------------------------
// last_index_of
// -----------------------------------------------------------------------------
/**
* 指定された要素がこのリスト内で最後に検出された位置のインデックスを返します。
* 指定された要素がこのリストにない場合は -1 を返します。
* 要素サイズ固定のリストを扱う場合、size の値は無視されます。
*
* @param list 対象リスト
* @param element 検索する要素
* @param size 検索する要素のサイズ
* @return 指定された要素がこのリスト内で最後に検出された位置のインデックス
*/
static int KcLinkedList_last_index_of(KcList *list, const void *element, size_t size)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
int result_index = -1;
kc_lock_guard(&(info->mutex))
{
int idx = info->size;
for (KcLinkedListEntry *entry = info->tail->prev; entry != info->head; entry = entry->prev)
{
idx--;
if ((size == entry->size) && (memcmp(entry->value, element, entry->size) == 0))
{
result_index = idx;
break;
}
}
}
return result_index;
}
////////////////////////////////////////////////////////////////////////////////
//
// Iterator
//
/**
* LinkedListe の Iterator 管理用構造体
*/
typedef struct KcLinkedListIteratorEntry_
{
KcLinkedListInfo *info; //!< ArrayList情報
KcLinkedListEntry *current; //!< 現在のエントリ
} KcLinkedListIteratorEntry;
/**
* 次の要素があるか否かを返します。
*
* @param ite Iterator
* @return true/false (次の要素が存在する/存在しない)
*/
static bool KcLinkedListIterator_hasNext(KcIterator *ite)
{
KcLinkedListIteratorEntry *entry = (KcLinkedListIteratorEntry *)ite->_info;
return (entry->current != entry->info->tail);
}
/**
* 次の要素を取得します。
* size が指定されている場合、次の要素が size に格納されます。
* 次の要素がない場合、NULL を返します。
*
* @param ite Iterator
* @param size 要素のサイズ格納用
* @return 次の要素
*/
static const void *KcLinkedListIterator_next(KcIterator *ite, size_t *size)
{
KcLinkedListIteratorEntry *entry = (KcLinkedListIteratorEntry *)ite->_info;
if (size != NULL)
{
*size = entry->current->size;
}
entry->current = entry->current->next;
return (entry->current->prev->value);
}
/**
* このリスト内の指定された位置で始まる、リスト内の要素を反復するイテレータを返します。
*
* @param list 対象リスト
* @param index イテレータから返される最初の要素のインデックス
* @return リスト内の指定された位置で始まる、リスト内の要素を反復するイテレータ
*/
static KcIterator *KcLinkedList_iterator(KcList *list, int index)
{
size_t ite_size = sizeof(KcIterator) + sizeof(KcLinkedListIteratorEntry);
KcIterator *ite = (KcIterator *)malloc(ite_size);
if (ite)
{
ite->hasNext = KcLinkedListIterator_hasNext;
ite->next = KcLinkedListIterator_next;
KcLinkedListIteratorEntry *entry = (KcLinkedListIteratorEntry *)(((KcIterator *)ite) + 1);
ite->_info = entry;
entry->info = list->_info;
entry->current = KcLinkedList_search(entry->info, index);
}
return ite;
}
/**
* リスト情報をクリアします。
*
* @param list 対象リスト
*/
static void KcLinkedList_cleanup_info(KcList *list)
{
KcLinkedListInfo *info = (KcLinkedListInfo *)list->_info;
list->clear(list);
mtx_destroy(&(info->mutex));
}
////////////////////////////////////////////////////////////////////////////////
//
// 内部関数
//
/**
* [内部関数] リストより指定されたインデックスのエントリを取得します。
* インデックスが -1 または、現在の size 位置の場合、 tail を返します。
* インデックス位置が不正な場合、エラーコード EINVAL がセットされ NULL を返します。
*
* @param info リスト情報
* @param index インデックス
* @return エントリ
*/
static KcLinkedListEntry *KcLinkedList_search(KcLinkedListInfo *info, int index)
{
KcLinkedListEntry *entry = NULL;
kc_lock_guard(&(info->mutex))
{
if (index > (int)info->size)
{ // インデックス不正のためエラーを設定
errno = EINVAL;
}
else if ((index == -1) || (index == (int)info->size))
{ // インデックス -1 or 末尾のため、tail を返す。
entry = info->tail;
}
else
{
int half_size = info->size / 2;
if (index < half_size)
{ // 前半のindexのため、前方より検索
entry = info->head;
for (int idx = 0; idx <= index; idx++)
{
entry = entry->next;
}
}
else
{ // 後半のindexのため、後方より検索
// head 0 1 2 3 tail
entry = info->tail;
for (int idx = info->size; idx > index; idx--)
{
entry = entry->prev;
}
}
}
}
return entry;
}
/**
* 新たなエントリを生成します。
* 生成に失敗した場合、errno に ENOMEM がセットされ、NULL が返されます。
*
* @param value 値
* @param size サイズ
* @return 生成したエントリ
*/
static KcLinkedListEntry *KcLinkedList_new_entry(const void *value, size_t size)
{
size_t entry_size = size + sizeof(KcLinkedListEntry);
KcLinkedListEntry *entry = (KcLinkedListEntry *)malloc(entry_size);
if (entry != NULL)
{
entry->value = (entry + 1);
entry->size = size;
memcpy(entry->value, value, size);
}
else
{ // メモリ確保失敗
errno = ENOMEM;
}
return entry;
}
