GenericList.c

00001 /*!
00002 * Copyright (c) 2015, Freescale Semiconductor, Inc.
00003 * All rights reserved.
00004 *
00005 * \file GenericList.c
00006 * This is the source file for the linked lists part of the Utils package.
00007 *
00008 * Redistribution and use in source and binary forms, with or without modification,
00009 * are permitted provided that the following conditions are met:
00010 *
00011 * o Redistributions of source code must retain the above copyright notice, this list
00012 *   of conditions and the following disclaimer.
00013 *
00014 * o Redistributions in binary form must reproduce the above copyright notice, this
00015 *   list of conditions and the following disclaimer in the documentation and/or
00016 *   other materials provided with the distribution.
00017 *
00018 * o Neither the name of Freescale Semiconductor, Inc. nor the names of its
00019 *   contributors may be used to endorse or promote products derived from this
00020 *   software without specific prior written permission.
00021 *
00022 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
00023 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00024 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00025 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
00026 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00027 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00028 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
00029 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00030 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00031 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00032 */
00033 
00034 /*! *********************************************************************************
00035 *************************************************************************************
00036 * Include
00037 *************************************************************************************
00038 ********************************************************************************** */
00039 #include "GenericList.h "
00040 #include "mbedAbstraction.h"
00041 
00042 
00043 
00044 /*! *********************************************************************************
00045 *************************************************************************************
00046 * Public functions
00047 *************************************************************************************
00048 ********************************************************************************** */
00049 /*! *********************************************************************************
00050 * \brief     Initialises the list descriptor. 
00051 *
00052 * \param[in] list - List handle to init.
00053 *            max - Maximum number of elements in list. 0 for unlimited.
00054 *
00055 * \return void.
00056 *
00057 * \pre
00058 *
00059 * \post
00060 *
00061 * \remarks
00062 *
00063 ********************************************************************************** */
00064 
00065 void ListInit(listHandle_t list, uint32_t max)
00066 {
00067   list->head = NULL;
00068   list->tail = NULL;
00069   list->max = max;
00070   list->size = 0;
00071 }
00072 
00073 /*! *********************************************************************************
00074 * \brief     Gets the list that contains the given element. 
00075 *
00076 * \param[in] element - Handle of the element.
00077 *
00078 * \return NULL if element is orphan.
00079 *         Handle of the list the element is inserted into.
00080 *
00081 * \pre
00082 *
00083 * \post
00084 *
00085 * \remarks
00086 *
00087 ********************************************************************************** */
00088 listHandle_t ListGetList(listElementHandle_t elementHandle)
00089 {
00090   return elementHandle->list;
00091 }
00092 
00093 /*! *********************************************************************************
00094 * \brief     Links element to the tail of the list. 
00095 *
00096 * \param[in] list - ID of list to insert into.
00097 *            element - element to add
00098 *
00099 * \return gListFull_c if list is full.
00100 *         gListOk_c if insertion was successful.
00101 *
00102 * \pre
00103 *
00104 * \post
00105 *
00106 * \remarks
00107 *
00108 ********************************************************************************** */
00109 listStatus_t  ListAddTail(listHandle_t list, listElementHandle_t element)
00110 {
00111   OSA_EnterCritical(kCriticalDisableInt);
00112 
00113   if( (list->max != 0) && (list->max == list->size) )
00114   {
00115     OSA_ExitCritical(kCriticalDisableInt);
00116     return gListFull_c;
00117   }
00118 
00119   if(list->size == 0)  
00120   {
00121     list->head = element;
00122   }
00123   else
00124   {
00125     list->tail->next = element;
00126   }
00127   element->prev = list->tail;
00128   element->next = NULL;
00129   element->list = list;
00130   list->tail = element;
00131   list->size++;
00132 
00133   OSA_ExitCritical(kCriticalDisableInt);
00134   return gListOk_c;
00135 }
00136 
00137 /*! *********************************************************************************
00138 * \brief     Links element to the head of the list. 
00139 *
00140 * \param[in] list - ID of list to insert into.
00141 *            element - element to add
00142 *
00143 * \return gListFull_c if list is full.
00144 *         gListOk_c if insertion was successful.
00145 *
00146 * \pre
00147 *
00148 * \post
00149 *
00150 * \remarks
00151 *
00152 ********************************************************************************** */
00153 listStatus_t  ListAddHead(listHandle_t list, listElementHandle_t element)
00154 {
00155   OSA_EnterCritical(kCriticalDisableInt);
00156 
00157   if( (list->max != 0) && (list->max == list->size) )
00158   {
00159     OSA_ExitCritical(kCriticalDisableInt);
00160     return gListFull_c;
00161   }
00162   
00163   if(list->size == 0)  
00164   {
00165     list->tail = element;
00166   }
00167   else
00168   {
00169     list->head->prev = element;
00170   }
00171   element->next = list->head;
00172   element->prev = NULL;
00173   element->list = list;
00174   list->head = element;
00175   list->size++;
00176 
00177   OSA_ExitCritical(kCriticalDisableInt);
00178   return gListOk_c;
00179 }
00180 
00181 /*! *********************************************************************************
00182 * \brief     Unlinks element from the head of the list. 
00183 *
00184 * \param[in] list - ID of list to remove from.
00185 *
00186 * \return NULL if list is empty.
00187 *         ID of removed element(pointer) if removal was successful.
00188 *
00189 * \pre
00190 *
00191 * \post
00192 *
00193 * \remarks
00194 *
00195 ********************************************************************************** */
00196 listElementHandle_t ListRemoveHead(listHandle_t list)
00197 {
00198   listElementHandle_t element;
00199   
00200   OSA_EnterCritical(kCriticalDisableInt);
00201 
00202   if(NULL == list || list->size == 0)
00203   {
00204     OSA_ExitCritical(kCriticalDisableInt);
00205     return NULL; /*List is empty*/
00206   }
00207   
00208   element = list->head;
00209   list->size--;
00210   if(list->size == 0)  
00211   {
00212     list->tail = NULL;
00213   }
00214   else
00215   {
00216     element->next->prev = NULL;
00217   }
00218   list->head = element->next; /*Is NULL if element is head*/
00219   element->list = NULL;
00220 
00221   OSA_ExitCritical(kCriticalDisableInt);
00222   return element;
00223 }
00224 
00225 /*! *********************************************************************************
00226 * \brief     Gets head element ID. 
00227 *
00228 * \param[in] list - ID of list.
00229 *
00230 * \return NULL if list is empty.
00231 *         ID of head element if list is not empty.
00232 *
00233 * \pre
00234 *
00235 * \post
00236 *
00237 * \remarks
00238 *
00239 ********************************************************************************** */
00240 listElementHandle_t ListGetHead(listHandle_t list)
00241 {
00242   return list->head;
00243 }
00244 
00245 /*! *********************************************************************************
00246 * \brief     Gets next element ID. 
00247 *
00248 * \param[in] element - ID of the element.
00249 *
00250 * \return NULL if element is tail.
00251 *         ID of next element if exists.
00252 *
00253 * \pre
00254 *
00255 * \post
00256 *
00257 * \remarks
00258 *
00259 ********************************************************************************** */
00260 listElementHandle_t ListGetNext(listElementHandle_t element)
00261 {
00262   return element->next;
00263 }
00264 
00265 /*! *********************************************************************************
00266 * \brief     Gets previous element ID. 
00267 *
00268 * \param[in] element - ID of the element.
00269 *
00270 * \return NULL if element is head.
00271 *         ID of previous element if exists.
00272 *
00273 * \pre
00274 *
00275 * \post
00276 *
00277 * \remarks
00278 *
00279 ********************************************************************************** */
00280 listElementHandle_t ListGetPrev(listElementHandle_t element)
00281 {
00282   return element->prev;
00283 }
00284 
00285 /*! *********************************************************************************
00286 * \brief     Unlinks an element from its list. 
00287 *
00288 * \param[in] element - ID of the element to remove.
00289 *
00290 * \return gOrphanElement_c if element is not part of any list.
00291 *         gListOk_c if removal was successful.
00292 *
00293 * \pre
00294 *
00295 * \post
00296 *
00297 * \remarks
00298 *
00299 ********************************************************************************** */
00300 listStatus_t  ListRemoveElement(listElementHandle_t element)
00301 {
00302   if(element->list == NULL)
00303   {
00304     return gOrphanElement_c; /*Element was previusly removed or never added*/
00305   }
00306   
00307   OSA_EnterCritical(kCriticalDisableInt);
00308 
00309   if(element->prev == NULL) /*Element is head or solo*/
00310   {
00311     element->list->head = element->next; /*is null if solo*/
00312   }
00313   if(element->next == NULL) /*Element is tail or solo*/
00314   {
00315     element->list->tail = element->prev; /*is null if solo*/
00316   }  
00317   if(element->prev != NULL) /*Element is not head*/
00318   {
00319     element->prev->next = element->next;
00320   }
00321   if(element->next != NULL) /*Element is not tail*/
00322   {
00323     element->next->prev = element->prev;
00324   }
00325   element->list->size--;
00326   element->list = NULL;
00327 
00328   OSA_ExitCritical(kCriticalDisableInt);
00329   return gListOk_c;  
00330 }
00331 
00332 /*! *********************************************************************************
00333 * \brief     Links an element in the previous position relative to a given member 
00334 *            of a list. 
00335 *
00336 * \param[in] element - ID of a member of a list.
00337 *            newElement - new element to insert before the given member.
00338 *
00339 * \return gOrphanElement_c if element is not part of any list.
00340 *         gListFull_c if list is full.
00341 *         gListOk_c if insertion was successful.
00342 *
00343 * \pre
00344 *
00345 * \post
00346 *
00347 * \remarks
00348 *
00349 ********************************************************************************** */
00350 listStatus_t  ListAddPrevElement(listElementHandle_t element, listElementHandle_t newElement)
00351 {
00352   if(element->list == NULL)
00353   {
00354     return gOrphanElement_c; /*Element was previusly removed or never added*/
00355   }
00356   OSA_EnterCritical(kCriticalDisableInt);
00357 
00358   if( (element->list->max != 0) && (element->list->max == element->list->size) )
00359   {
00360     OSA_ExitCritical(kCriticalDisableInt);
00361     return gListFull_c;
00362   }
00363   
00364   if(element->prev == NULL) /*Element is list head*/
00365   {
00366     element->list->head = newElement;
00367   }
00368   else
00369   {
00370     element->prev->next = newElement;
00371   }
00372   newElement->list = element->list;
00373   element->list->size++;
00374   newElement->next = element;
00375   newElement->prev = element->prev;
00376   element->prev = newElement;
00377 
00378   OSA_ExitCritical(kCriticalDisableInt);
00379   return gListOk_c;
00380 }
00381 
00382 /*! *********************************************************************************
00383 * \brief     Gets the current size of a list. 
00384 *
00385 * \param[in] list - ID of the list.
00386 *
00387 * \return Current size of the list.
00388 *
00389 * \pre
00390 *
00391 * \post
00392 *
00393 * \remarks
00394 *
00395 ********************************************************************************** */
00396 uint32_t ListGetSize(listHandle_t list)
00397 {
00398   return list->size;
00399 }
00400 
00401 /*! *********************************************************************************
00402 * \brief     Gets the number of free places in the list. 
00403 *
00404 * \param[in] list - ID of the list.
00405 *
00406 * \return Available size of the list.
00407 *
00408 * \pre
00409 *
00410 * \post
00411 *
00412 * \remarks
00413 *
00414 ********************************************************************************** */
00415 uint32_t ListGetAvailable(listHandle_t list)
00416 {
00417   return (list->max - list->size);
00418 }
00419 
00420 /*! *********************************************************************************
00421 * \brief     Creates, tests and deletes a list. Any error that occurs will trap the 
00422 *            CPU in a while(1) loop.
00423 *
00424 * \param[in] void.
00425 *
00426 * \return gListOk_c.
00427 *
00428 * \pre
00429 *
00430 * \post
00431 *
00432 * \remarks
00433 *
00434 ********************************************************************************** */
00435 // To be removed or rewritten to remove MemManager dependency.
00436 #if 0
00437 listStatus_t  ListTest()
00438 {
00439   listHandle_t list;
00440   listElementHandle_t element, newElement;
00441   uint32_t i,freeBlocks;
00442   const uint32_t max = 10;
00443   
00444   freeBlocks = MEM_GetAvailableFwkBlocks(0);
00445   /*create list*/
00446   list = ListCreate(max); 
00447   LIST_ASSERT(list != NULL);
00448   
00449   /*add elements*/
00450   for(i=0; i<max; i++)
00451   {
00452     element = (listElementHandle_t)MEM_BufferFwkAlloc(sizeof(listElement_t));
00453     LIST_ASSERT(element != NULL);
00454     LIST_ASSERT(ListAddHead(list, element) == gListOk_c);
00455     LIST_ASSERT(list->head == element)
00456     ListRemoveHead(list);
00457     LIST_ASSERT(ListAddTail(list, element) == gListOk_c);
00458     LIST_ASSERT(list->tail == element);
00459     if(ListGetSize(list) == 1)
00460     {
00461       LIST_ASSERT(list->head == element);
00462     }
00463     else
00464     {
00465       LIST_ASSERT(list->head != element);
00466     }
00467   }
00468   LIST_ASSERT(ListGetSize(list) == max);
00469   
00470   /*add one more element*/
00471   element = (listElementHandle_t)MEM_BufferFwkAlloc(sizeof(listElement_t));
00472   LIST_ASSERT(element != NULL);
00473   LIST_ASSERT(ListAddTail(list, element) == gListFull_c);
00474   list->max = 0;
00475   LIST_ASSERT(ListAddTail(list, element) == gListOk_c);
00476   LIST_ASSERT(ListGetSize(list) == max+1);
00477   /*remove the extra element*/
00478   element = ListRemoveHead(list);
00479   LIST_ASSERT(element != NULL);
00480   LIST_ASSERT(ListGetSize(list) == max);
00481   LIST_ASSERT(MEM_BufferFree(element) == MEM_SUCCESS_c);
00482   list->max = max;
00483   
00484   /*parse elements*/
00485   element = ListGetHead(list);
00486   LIST_ASSERT(element != NULL);
00487   for(i=0; i<(max-1); i++)
00488   {
00489     element = ListGetNext(element);
00490     LIST_ASSERT(element != NULL);
00491   }
00492   LIST_ASSERT(element == list->tail);
00493   LIST_ASSERT(ListGetNext(element) == NULL);
00494   
00495   /*Reverse parse elements*/
00496   for(i=0; i<(max-1); i++)
00497   {
00498     element = ListGetPrev(element);
00499     LIST_ASSERT(element != NULL);
00500   }
00501   LIST_ASSERT(element == list->head);
00502   LIST_ASSERT(ListGetPrev(element) == NULL);
00503   
00504   /*Add prev*/
00505   element = ListGetHead(list);
00506   LIST_ASSERT(element != NULL);
00507   newElement = (listElementHandle_t)MEM_BufferFwkAlloc(sizeof(listElement_t));
00508   LIST_ASSERT(newElement != NULL);
00509   LIST_ASSERT(ListAddPrevElement(element, newElement) == gListFull_c);
00510   LIST_ASSERT(ListGetHead(list) == element);
00511   list->max = 0;
00512   LIST_ASSERT(ListAddPrevElement(element, newElement) == gListOk_c);
00513   LIST_ASSERT(ListGetHead(list) == newElement);
00514   newElement = (listElementHandle_t)MEM_BufferFwkAlloc(sizeof(listElement_t));
00515   LIST_ASSERT(newElement != NULL);
00516   element = list->head->next->next;
00517   LIST_ASSERT(ListAddPrevElement(element, newElement) == gListOk_c); 
00518   LIST_ASSERT(list->head->next->next == newElement);
00519   newElement = (listElementHandle_t)MEM_BufferFwkAlloc(sizeof(listElement_t));
00520   LIST_ASSERT(newElement != NULL);
00521   element = list->tail;
00522   LIST_ASSERT(ListAddPrevElement(element, newElement) == gListOk_c); 
00523   LIST_ASSERT(list->tail->prev == newElement);
00524   newElement = (listElementHandle_t)MEM_BufferFwkAlloc(sizeof(listElement_t));
00525   LIST_ASSERT(newElement != NULL);
00526   element = (listElementHandle_t)MEM_BufferFwkAlloc(sizeof(listElement_t));
00527   LIST_ASSERT(element != NULL);
00528   element->list = NULL;
00529   LIST_ASSERT(ListAddPrevElement(element, newElement) == gOrphanElement_c); 
00530   MEM_BufferFree(newElement);
00531   MEM_BufferFree(element);
00532   LIST_ASSERT(ListGetSize(list) == max+3);
00533   
00534   /*Remove element*/
00535   element = ListGetHead(list);
00536   LIST_ASSERT(element == list->head);
00537   LIST_ASSERT(ListRemoveElement(element) == gListOk_c);
00538   LIST_ASSERT(list->head != element);
00539   LIST_ASSERT(ListRemoveElement(element) == gOrphanElement_c);
00540   MEM_BufferFree(element);
00541   element = ListGetHead(list)->next->next;
00542   LIST_ASSERT(ListRemoveElement(element) == gListOk_c);
00543   MEM_BufferFree(element);
00544   element = list->tail;
00545   LIST_ASSERT(ListRemoveElement(element) == gListOk_c);
00546   LIST_ASSERT(list->tail != element);
00547   MEM_BufferFree(element);
00548   LIST_ASSERT(ListGetSize(list) == max);
00549   list->max = max;
00550   
00551   for(i=0; i<(max-1); i++)
00552   {
00553     element = ListRemoveHead(list);
00554     LIST_ASSERT(element != NULL);
00555     MEM_BufferFree(element);
00556   }
00557   element = ListGetHead(list);
00558   LIST_ASSERT(element != NULL);
00559   LIST_ASSERT(ListRemoveElement(element) == gListOk_c);
00560   LIST_ASSERT(list->head == NULL);
00561   LIST_ASSERT(list->tail == NULL);
00562   LIST_ASSERT(element->list == NULL);
00563   MEM_BufferFree(element);
00564   
00565   /*List is empty here.*/
00566   LIST_ASSERT(ListGetSize(list) == 0);
00567   element = ListRemoveHead(list);
00568   LIST_ASSERT(element == NULL);
00569   element = ListGetHead(list);
00570   LIST_ASSERT(element == NULL);
00571   
00572   MEM_BufferFree(list);
00573   /*Did we produce a memory leak?*/
00574   LIST_ASSERT(freeBlocks == MEM_GetAvailableFwkBlocks(0));
00575   
00576   return gListOk_c;
00577 }
00578 #else
00579 listStatus_t  ListTest()
00580 {
00581   return gListOk_c;
00582 }
00583 #endif