/* * MOST NetServices "Light" V3.2.7.0.1796 MultiInstance Patch * * Copyright (C) 2015 Microchip Technology Germany II GmbH & Co. KG * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. * * You may also obtain this software under a propriety license from Microchip. * Please contact Microchip for further information. * */ /*! * \file * \brief Implementation of the doubly linked list. * * \cond MNS_INTERNAL_DOC * \addtogroup G_DL * @{ */ /*------------------------------------------------------------------------------------------------*/ /* Includes */ /*------------------------------------------------------------------------------------------------*/ #include "mns_dl.h" #include "mns_trace.h" /*------------------------------------------------------------------------------------------------*/ /* Implementation of class CDlList */ /*------------------------------------------------------------------------------------------------*/ /*! \brief Constructor of the doubly linked list class. * \param self Instance pointer * \param mns_inst_id MOST NetServices instance ID */ void Dl_Ctor(CDlList *self, uint8_t mns_inst_id) { self->head = NULL; self->tail = NULL; self->size = 0U; self->mns_inst_id = mns_inst_id; } /*! \brief Inserts a new node after an arbitrary node. * \param self Instance pointer * \param node Reference of the initial node * \param new_node Reference of the new node are to be inserted */ void Dl_InsertAfter(CDlList *self, CDlNode *node, CDlNode *new_node) { TR_ASSERT(self->mns_inst_id, "[DL]", (self->size <= 0xFFFFU)); new_node->prev = node; new_node->next = node->next; if(node->next == NULL) /* Is initial node last node in list? */ { self->tail = new_node; /* Set new node as tail of list */ } else { node->next->prev = new_node; /* Adjust follower node */ } node->next = new_node; /* Adjust parent node */ new_node->in_use = true; /* Signals that node is part of a list */ self->size++; /* Increment number of nodes */ } /*! \brief Inserts a new node before an arbitrary node. * \param self Instance pointer * \param node Reference of the initial node * \param new_node Reference of the new node are to be inserted */ void Dl_InsertBefore(CDlList *self, CDlNode *node, CDlNode *new_node) { TR_ASSERT(self->mns_inst_id, "[DL]", (self->size <= 0xFFFFU)); new_node->prev = node->prev; new_node->next = node; if(node->prev == NULL) /* Is initial node first node in list? */ { self->head = new_node; /* Set new node as head of list */ } else { node->prev->next = new_node; /* Adjust parent node */ } node->prev = new_node; /* Adjust follower node */ new_node->in_use = true; /* Signals that node is part of a list */ self->size++; /* Increment number of nodes */ } /*! \brief Sets the new node as head of a doubly linked list. * \param self Instance pointer * \param new_node Reference of the new node are to be placed as head of the list */ void Dl_InsertHead(CDlList *self, CDlNode *new_node) { if(self->head == NULL) /* Is list empty? */ { TR_ASSERT(self->mns_inst_id, "[DL]", (self->size <= 0xFFFFU)); self->head = new_node; self->tail = new_node; new_node->prev = NULL; new_node->next = NULL; new_node->in_use = true; /* Signals that node is part of a list */ self->size++; /* Increment number of nodes */ } else { Dl_InsertBefore(self, self->head, new_node); } } /*! \brief Inserts the new node at the end of a doubly linked list. * \param self Instance pointer * \param new_node Reference of the new node are to be placed at the end of the list */ void Dl_InsertTail(CDlList *self, CDlNode *new_node) { if(self->tail == NULL) /* Is list empty? */ { Dl_InsertHead(self, new_node); } else { Dl_InsertAfter(self, self->tail, new_node); } } /*! \brief Removes an arbitrary node from a doubly linked list. * \param self Instance pointer * \param node Reference of the node are to be removed from the list * \return \c DL_OK: No error * \return \c DL_UNKNOWN_NODE: Given node is not part of this list */ Dl_Ret_t Dl_Remove(CDlList *self, CDlNode *node) { Dl_Ret_t ret_val = DL_UNKNOWN_NODE; if(Dl_IsNodeInList(self, node) != false) /* Is node part of list? */ { TR_ASSERT(self->mns_inst_id, "[DL]", (self->size > 0U)); if(node->prev == NULL) /* First node in list? */ { self->head = node->next; /* Replace head node with next node in list */ } else /* -> Not first node in list */ { node->prev->next = node->next; /* Set next pointer of previous node to next node */ } if(node->next == NULL) /* Last node in list? */ { self->tail = node->prev; /* Replace tail node with previous node in list */ } else /* -> Not last node in list */ { node->next->prev = node->prev; /* Set previous ptr of next node to previous node */ } node->prev = NULL; node->next = NULL; node->in_use = false; /* Signals that node is not part of a list */ ret_val = DL_OK; self->size--; /* Decrement number of nodes */ } return ret_val; } /*! \brief Removes the first node in a doubly linked list. * \param self Instance pointer * \return The reference of the removed head node or \c NULL if the list is empty. */ CDlNode * Dl_PopHead(CDlList *self) { CDlNode *node = self->head; if(NULL != node) /* Is list not empty? */ { TR_ASSERT(self->mns_inst_id, "[DL]", (self->size > 0U)); self->head = node->next; /* Replace head node with next node in list */ if(node->next == NULL) /* Last node in list? */ { self->tail = NULL; /* Replace tail node and set list's tail pointer * to NULL */ } else /* -> Not last node in list */ { node->next->prev = NULL; /* Set previous pointer of next node to NULL */ } node->prev = NULL; node->next = NULL; node->in_use = false; /* Signals that node is not part of a list */ self->size--; /* Decrement number of nodes */ } return node; } /*! \brief Removes the last node in a doubly linked list. * \param self Instance pointer * \return The reference of the removed tail node or \c NULL if the list is empty. */ CDlNode * Dl_PopTail(CDlList *self) { CDlNode *node = self->tail; if(NULL != node) /* Is list not empty? */ { TR_ASSERT(self->mns_inst_id, "[DL]", (self->size > 0U)); if(node->prev == NULL) /* First node in list? */ { self->head = NULL; /* Replace head node and set list's head pointer * to NULL */ } else /* -> Not first node in list */ { node->prev->next = NULL; /* Set next pointer of previous node to NULL */ } self->tail = node->prev; /* Replace tail node with previous node in list */ node->prev = NULL; node->next = NULL; node->in_use = false; /* Signals that node is not part of a list */ self->size--; /* Decrement number of nodes */ } return node; } /*! \brief Returns the reference of the first node in a doubly linked list. * \param self Instance pointer * \return The reference of the head node or \c NULL if the list is empty. */ CDlNode * Dl_PeekHead(CDlList *self) { return self->head; } /*! \brief Returns the reference of the last node in a doubly linked list. * \param self Instance pointer * \return The reference of the tail node or NULL if the list is empty. */ CDlNode * Dl_PeekTail(CDlList *self) { return self->tail; } /*! \brief Calls the given function for each node in the doubly linked list. If the func_ptr * returns true the loop is stopped and the current node will be returned. * \param self Instance pointer * \param func_ptr Reference of the callback function which is called for each node * \param user_data_ptr Reference of optional user data given to func_ptr * \return Returns the current node or \c NULL if the whole list is processed. */ CDlNode * Dl_Foreach(CDlList *self, Dl_ForeachFunc_t func_ptr, void *user_data_ptr) { CDlNode *ret_val = NULL; CDlNode *node = self->head; while(NULL != node) /* End of list reached? */ { if(func_ptr(node->data_ptr, user_data_ptr) != false) /* Data found? */ { ret_val = node; break; } node = node->next; } return ret_val; } /*! \brief Checks if a node is part of the given doubly linked list. * \param self Instance pointer * \param node Reference of the searched node * \return \c true: Node is part of the given list * \return \c false: Node is not part of the given list */ bool Dl_IsNodeInList(CDlList *self, const CDlNode *node) { bool ret_val = false; CDlNode *current_node = self->head; while(NULL != current_node) /* End of list reached? */ { if(current_node == node) /* Is current node the searched one */ { ret_val = true; break; } current_node = current_node->next; } return ret_val; } /*! \brief Appends one doubly linked list to another doubly linked list. * \param self Instance pointer * \param list_ptr Reference to the doubly linked list */ void Dl_AppendList(CDlList *self, CDlList *list_ptr) { TR_ASSERT(self->mns_inst_id, "[DL]", (list_ptr != NULL)); if(list_ptr->head != NULL) { if(self->tail == NULL) /* Is list empty? */ { self->head = list_ptr->head; self->tail = list_ptr->tail; self->size = list_ptr->size; } else { list_ptr->head->prev = self->tail; self->tail->next = list_ptr->head; self->tail = list_ptr->tail; self->size += list_ptr->size; } list_ptr->head = NULL; list_ptr->tail = NULL; list_ptr->size = 0U; } } /*! \brief Interface function to retrieve the list size. * \param self Instance pointer * \return Size of the list */ uint16_t Dl_GetSize(CDlList *self) { return self->size; } /*------------------------------------------------------------------------------------------------*/ /* Implementation of class CDlNode */ /*------------------------------------------------------------------------------------------------*/ /*! \brief Constructor of doubly linked list nodes. * \param self Instance pointer * \param data_ptr Optional reference to data */ void Dln_Ctor(CDlNode *self, void *data_ptr) { self->next = NULL; self->prev = NULL; self->in_use = false; self->data_ptr = data_ptr; } /*! \brief Interface function to set the data pointer of the given node. * \param self Instance pointer * \param data_ptr Reference of the new data */ void Dln_SetData(CDlNode *self, void *data_ptr) { self->data_ptr = data_ptr; } /*! \brief Interface function to request the data pointer of the given node. * \param self Instance pointer */ void * Dln_GetData(CDlNode *self) { return self->data_ptr; } /*! \brief Checks if a node is part of a doubly linked list. * \param self Instance pointer of the searched node * \return \c true: Node is part of a list * \return \c false: Node is not part of a list */ bool Dln_IsNodePartOfAList(CDlNode *self) { return self->in_use; } /*! * @} * \endcond */ /*------------------------------------------------------------------------------------------------*/ /* End of file */ /*------------------------------------------------------------------------------------------------*/