/*
|
* Copyright (c) 2019-2025 Beijing Hanwei Innovation Technology Ltd. Co. and
|
* its subsidiaries and affiliates (collectly called MKSEMI).
|
*
|
* All rights reserved.
|
*
|
* Redistribution and use in source and binary forms, with or without
|
* modification, are permitted provided that the following conditions are met:
|
*
|
* 1. Redistributions of source code must retain the above copyright notice,
|
* this list of conditions and the following disclaimer.
|
*
|
* 2. Redistributions in binary form, except as embedded into an MKSEMI
|
* integrated circuit in a product or a software update for such product,
|
* must reproduce the above copyright notice, this list of conditions and
|
* the following disclaimer in the documentation and/or other materials
|
* provided with the distribution.
|
*
|
* 3. Neither the name of MKSEMI nor the names of its contributors may be used
|
* to endorse or promote products derived from this software without
|
* specific prior written permission.
|
*
|
* 4. This software, with or without modification, must only be used with a
|
* MKSEMI integrated circuit.
|
*
|
* 5. Any software provided in binary form under this license must not be
|
* reverse engineered, decompiled, modified and/or disassembled.
|
*
|
* THIS SOFTWARE IS PROVIDED BY MKSEMI "AS IS" AND ANY EXPRESS OR IMPLIED
|
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
|
* MERCHANTABILITY, NONINFRINGEMENT, AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
* DISCLAIMED. IN NO EVENT SHALL MKSEMI OR CONTRIBUTORS BE LIABLE FOR ANY
|
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
|
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
|
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
|
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
*/
|
#include "mk_list.h"
|
|
void mk_list_init(struct mk_list *list)
|
{
|
list->first = NULL;
|
list->last = NULL;
|
|
#if (MK_LIST_DEBUG)
|
list->cnt = 0;
|
list->maxcnt = 0;
|
list->mincnt = 0xFFFF;
|
#endif
|
}
|
|
void mk_list_push_back(struct mk_list *list, struct mk_list_hdr *list_hdr)
|
{
|
// Sanity check
|
ASSERT(list_hdr != NULL, "Invalid list");
|
|
// check if list is empty
|
if (mk_list_is_empty(list))
|
{
|
// list empty => pushed element is also head
|
list->first = list_hdr;
|
}
|
else
|
{
|
// list not empty => update next of last
|
list->last->next = list_hdr;
|
}
|
|
// add element at the end of the list
|
list->last = list_hdr;
|
list_hdr->next = NULL;
|
|
#if (MK_LIST_DEBUG)
|
list->cnt++;
|
if (list->maxcnt < list->cnt)
|
{
|
list->maxcnt = list->cnt;
|
}
|
#endif
|
}
|
|
void mk_list_push_back_sublist(struct mk_list *list, struct mk_list_hdr *first_hdr, struct mk_list_hdr *last_hdr)
|
{
|
// Sanity check
|
ASSERT(first_hdr != NULL, "Invalid list");
|
ASSERT(last_hdr != NULL, "Invalid list");
|
|
// check if list is empty
|
if (mk_list_is_empty(list))
|
{
|
// list empty => pushed element is also head
|
list->first = first_hdr;
|
}
|
else
|
{
|
// list not empty => update next of last
|
list->last->next = first_hdr;
|
}
|
|
// Update last pointer
|
list->last = last_hdr;
|
last_hdr->next = NULL;
|
|
#if (MK_LIST_DEBUG)
|
{
|
struct mk_list_hdr *cursor = first_hdr;
|
|
// Count the number of extracted elements
|
while (cursor != NULL)
|
{
|
cursor = cursor->next;
|
}
|
|
list->cnt++;
|
list->maxcnt = (uint16_t)MAX(list->maxcnt, list->cnt);
|
}
|
#endif
|
}
|
|
void mk_list_push_front(struct mk_list *list, struct mk_list_hdr *list_hdr)
|
{
|
// Sanity check
|
ASSERT(list_hdr != NULL, "Invalid list");
|
|
// check if list is empty
|
if (mk_list_is_empty(list))
|
{
|
// list empty => pushed element is also head
|
list->last = list_hdr;
|
}
|
|
// add element at the beginning of the list
|
list_hdr->next = list->first;
|
list->first = list_hdr;
|
|
#if (MK_LIST_DEBUG)
|
list->cnt++;
|
if (list->maxcnt < list->cnt)
|
{
|
list->maxcnt = list->cnt;
|
}
|
#endif
|
}
|
|
struct mk_list_hdr *mk_list_pop_front(struct mk_list *list)
|
{
|
struct mk_list_hdr *element;
|
|
// check if list is empty
|
element = list->first;
|
if (element != NULL)
|
{
|
// The list isn't empty : extract the first element
|
list->first = list->first->next;
|
|
if (list->first == NULL)
|
{
|
list->last = list->first;
|
}
|
|
#if (MK_LIST_DEBUG)
|
list->cnt--;
|
if (list->mincnt > list->cnt)
|
{
|
list->mincnt = list->cnt;
|
}
|
#endif
|
}
|
return element;
|
}
|
|
bool mk_list_extract(struct mk_list *list, struct mk_list_hdr *list_hdr)
|
{
|
bool found = false;
|
|
// sanity check
|
ASSERT(list != NULL, "Invalid list");
|
|
struct mk_list_hdr *prev = NULL;
|
struct mk_list_hdr *curr = list->first;
|
|
// Search for the element
|
while (curr != NULL)
|
{
|
// Check element
|
if (curr == list_hdr)
|
{
|
found = true;
|
break;
|
}
|
|
// Move pointers
|
prev = curr;
|
ASSERT(list->first != curr->next, "Move pointers error %x %x", ((uint32_t)curr) >> 16, ((uint32_t)curr) & 0xFFFF);
|
ASSERT(curr != curr->next, "Move pointers error %x %x", ((uint32_t)curr) >> 16, ((uint32_t)curr) & 0xFFFF);
|
curr = curr->next;
|
}
|
|
if (found)
|
{
|
// Check if the element is first
|
if (prev == NULL)
|
{
|
// Extract element
|
list->first = list_hdr->next;
|
}
|
else
|
{
|
// Extract element
|
prev->next = list_hdr->next;
|
}
|
|
// Check if the element is last
|
if (list_hdr == list->last)
|
{
|
// Update last pointer
|
list->last = prev;
|
}
|
|
#if (MK_LIST_DEBUG)
|
// Reference element extracted
|
list->cnt--;
|
if (list->mincnt > list->cnt)
|
{
|
list->mincnt = list->cnt;
|
}
|
#endif
|
}
|
|
return found;
|
}
|
|
void mk_list_extract_after(struct mk_list *list, struct mk_list_hdr *elt_ref_hdr, struct mk_list_hdr *elt_to_rem_hdr)
|
{
|
// sanity check
|
ASSERT(list != NULL, "Invalid list");
|
ASSERT(elt_to_rem_hdr != NULL, "Invalid list");
|
|
// Check if the element is first
|
if (elt_ref_hdr == NULL)
|
{
|
ASSERT(elt_to_rem_hdr == list->first, "Invalid list");
|
|
// The list isn't empty : extract the first element
|
list->first = list->first->next;
|
}
|
else
|
{
|
ASSERT(elt_to_rem_hdr == elt_ref_hdr->next, "Invalid list");
|
|
// Extract element
|
elt_ref_hdr->next = elt_to_rem_hdr->next;
|
}
|
|
// Check if the element is last
|
if (elt_to_rem_hdr == list->last)
|
{
|
// Update last pointer
|
list->last = elt_ref_hdr;
|
}
|
|
#if (MK_LIST_DEBUG)
|
// Reference element extracted
|
list->cnt--;
|
if (list->mincnt > list->cnt)
|
{
|
list->mincnt = list->cnt;
|
}
|
#endif
|
}
|
|
void mk_list_extract_sublist(struct mk_list *list, struct mk_list_hdr *ref_hdr, struct mk_list_hdr *last_hdr)
|
{
|
// sanity check
|
ASSERT(list != NULL, "Invalid list");
|
ASSERT(last_hdr != NULL, "Invalid list");
|
|
// Check if the element is first
|
if (ref_hdr == NULL)
|
{
|
// Extract the elements
|
list->first = last_hdr->next;
|
}
|
else
|
{
|
// Extract the elements
|
ref_hdr->next = last_hdr->next;
|
}
|
|
// Check if the element is last
|
if (last_hdr == list->last)
|
{
|
// Reference element becomes last
|
list->last = ref_hdr;
|
}
|
}
|
|
bool mk_list_find(struct mk_list *list, struct mk_list_hdr *list_hdr)
|
{
|
struct mk_list_hdr *tmp_list_hdr;
|
|
// Go through the list to find the element
|
tmp_list_hdr = list->first;
|
|
while ((tmp_list_hdr != list_hdr) && (tmp_list_hdr != NULL))
|
{
|
tmp_list_hdr = tmp_list_hdr->next;
|
}
|
|
return (tmp_list_hdr == list_hdr);
|
}
|
|
void mk_list_merge(struct mk_list *list1, struct mk_list *list2)
|
{
|
// Sanity check: list2 is not supposed to be empty
|
ASSERT(!mk_list_is_empty(list2), "Invalid list2");
|
|
// just copy list elements
|
if (mk_list_is_empty(list1))
|
{
|
list1->first = list2->first;
|
list1->last = list2->last;
|
}
|
// merge lists
|
else
|
{
|
// Append list2 to list1
|
list1->last->next = list2->first;
|
list1->last = list2->last;
|
}
|
|
// Empty list2
|
list2->first = NULL;
|
|
#if (MK_LIST_DEBUG)
|
list1->cnt += list2->cnt;
|
list2->cnt = 0;
|
#endif
|
}
|
|
void mk_list_insert_before(struct mk_list *list, struct mk_list_hdr *elt_ref_hdr, struct mk_list_hdr *elt_to_add_hdr)
|
{
|
// Sanity check
|
ASSERT(elt_to_add_hdr != NULL, "Invalid list");
|
|
// If no element referenced
|
if (elt_ref_hdr == NULL)
|
{
|
mk_list_push_front(list, elt_to_add_hdr);
|
}
|
else
|
{
|
struct mk_list_hdr *tmp_list_prev_hdr = NULL;
|
struct mk_list_hdr *tmp_list_curr_hdr;
|
|
// Go through the list to find the element
|
tmp_list_curr_hdr = list->first;
|
|
while ((tmp_list_curr_hdr != elt_ref_hdr) && (tmp_list_curr_hdr != NULL))
|
{
|
// Save previous element
|
tmp_list_prev_hdr = tmp_list_curr_hdr;
|
// Get the next element of the list
|
tmp_list_curr_hdr = tmp_list_curr_hdr->next;
|
}
|
// If only one element is available
|
if (tmp_list_prev_hdr == NULL)
|
{
|
mk_list_push_front(list, elt_to_add_hdr);
|
}
|
else
|
{
|
tmp_list_prev_hdr->next = elt_to_add_hdr;
|
elt_to_add_hdr->next = tmp_list_curr_hdr;
|
#if (MK_LIST_DEBUG)
|
list->cnt++;
|
if (list->maxcnt < list->cnt)
|
{
|
list->maxcnt = list->cnt;
|
}
|
#endif
|
}
|
}
|
}
|
|
void mk_list_insert_after(struct mk_list *list, struct mk_list_hdr *elt_ref_hdr, struct mk_list_hdr *elt_to_add_hdr)
|
{
|
// Sanity check
|
ASSERT(elt_to_add_hdr != NULL, "Invalid list");
|
// If no element referenced
|
if (elt_ref_hdr == NULL)
|
{
|
mk_list_push_back(list, elt_to_add_hdr);
|
}
|
else
|
{
|
struct mk_list_hdr *tmp_list_curr_hdr;
|
|
// Go through the list to find the element
|
tmp_list_curr_hdr = list->first;
|
|
while ((tmp_list_curr_hdr != elt_ref_hdr) && (tmp_list_curr_hdr != NULL))
|
{
|
// Get the next element of the list
|
tmp_list_curr_hdr = tmp_list_curr_hdr->next;
|
}
|
// If only one element is available
|
if (tmp_list_curr_hdr == NULL)
|
{
|
mk_list_push_back(list, elt_to_add_hdr);
|
}
|
else
|
{
|
// Check if the found element was the last of the list
|
if (!tmp_list_curr_hdr->next)
|
{
|
// Update last pointer
|
list->last = elt_to_add_hdr;
|
}
|
|
elt_to_add_hdr->next = tmp_list_curr_hdr->next;
|
tmp_list_curr_hdr->next = elt_to_add_hdr;
|
|
#if (MK_LIST_DEBUG)
|
list->cnt++;
|
if (list->maxcnt < list->cnt)
|
{
|
list->maxcnt = list->cnt;
|
}
|
#endif
|
}
|
}
|
}
|
|
uint16_t mk_list_size(struct mk_list *list)
|
{
|
uint16_t count = 0;
|
struct mk_list_hdr *tmp_list_hdr = list->first;
|
|
// browse list to count number of elements
|
while (tmp_list_hdr != NULL)
|
{
|
tmp_list_hdr = tmp_list_hdr->next;
|
count++;
|
}
|
|
return count;
|
}
|
