Line data    Source code

       1             : /**********************************************************************
       2             :  *
       3             :  * Name:     cpl_list.cpp
       4             :  * Project:  CPL - Common Portability Library
       5             :  * Purpose:  List functions.
       6             :  * Author:   Andrey Kiselev, dron@remotesensing.org
       7             :  *
       8             :  **********************************************************************
       9             :  * Copyright (c) 2003, Andrey Kiselev <dron@remotesensing.org>
      10             :  * Copyright (c) 2008, Even Rouault <even dot rouault at spatialys.com>
      11             :  *
      12             :  * SPDX-License-Identifier: MIT
      13             :  ****************************************************************************/
      14             : 
      15             : #include "cpl_list.h"
      16             : 
      17             : #include <cstddef>
      18             : 
      19             : #include "cpl_conv.h"
      20             : 
      21             : /*=====================================================================
      22             :                     List manipulation functions.
      23             :  =====================================================================*/
      24             : 
      25             : /************************************************************************/
      26             : /*                          CPLListAppend()                             */
      27             : /************************************************************************/
      28             : 
      29             : /**
      30             :  * Append an object list and return a pointer to the modified list.
      31             :  * If the input list is NULL, then a new list is created.
      32             :  *
      33             :  * @param psList pointer to list head.
      34             :  * @param pData pointer to inserted data object. May be NULL.
      35             :  *
      36             :  * @return pointer to the head of modified list.
      37             :  */
      38             : 
      39          11 : CPLList *CPLListAppend(CPLList *psList, void *pData)
      40             : {
      41          11 :     CPLList *psLast = nullptr;
      42             : 
      43             :     // Allocate room for the new object.
      44          11 :     if (psList == nullptr)
      45             :     {
      46           4 :         psLast = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
      47           4 :         psList = psLast;
      48             :     }
      49             :     else
      50             :     {
      51           7 :         psLast = CPLListGetLast(psList);
      52           7 :         psLast = psLast->psNext =
      53           7 :             static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
      54             :     }
      55             : 
      56             :     // Append object to the end of list.
      57          11 :     psLast->pData = pData;
      58          11 :     psLast->psNext = nullptr;
      59             : 
      60          11 :     return psList;
      61             : }
      62             : 
      63             : /************************************************************************/
      64             : /*                          CPLListInsert()                             */
      65             : /************************************************************************/
      66             : 
      67             : /**
      68             :  * Insert an object into list at specified position (zero based).
      69             :  * If the input list is NULL, then a new list is created.
      70             :  *
      71             :  * @param psList pointer to list head.
      72             :  * @param pData pointer to inserted data object. May be NULL.
      73             :  * @param nPosition position number to insert an object.
      74             :  *
      75             :  * @return pointer to the head of modified list.
      76             :  */
      77             : 
      78           7 : CPLList *CPLListInsert(CPLList *psList, void *pData, int nPosition)
      79             : {
      80           7 :     if (nPosition < 0)
      81           0 :         return psList;  // Nothing to do.
      82             : 
      83           7 :     if (nPosition == 0)
      84             :     {
      85           2 :         CPLList *psNew = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
      86           2 :         psNew->pData = pData;
      87           2 :         psNew->psNext = psList;
      88           2 :         psList = psNew;
      89           2 :         return psList;
      90             :     }
      91             : 
      92           5 :     const int nCount = CPLListCount(psList);
      93             : 
      94           5 :     if (nCount < nPosition)
      95             :     {
      96             : #ifdef __COVERITY__
      97             :         CPLError(CE_Failure, CPLE_AppDefined, "Not implemented");
      98             : #else
      99             :         // Allocate room for the new object.
     100           3 :         CPLList *psLast = CPLListGetLast(psList);
     101           7 :         for (int i = nCount; i <= nPosition - 1; i++)
     102             :         {
     103           4 :             psLast = CPLListAppend(psLast, nullptr);
     104           4 :             if (psList == nullptr)
     105           2 :                 psList = psLast;
     106             :             else
     107           2 :                 psLast = psLast->psNext;
     108             :         }
     109           3 :         psLast = CPLListAppend(psLast, pData);
     110           3 :         if (psList == nullptr)
     111           0 :             psList = psLast;
     112             : 
     113             :         /* coverity[leaked_storage] */
     114           3 :         return psList;
     115             : #endif
     116             :     }
     117             : 
     118           2 :     CPLList *psNew = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
     119           2 :     psNew->pData = pData;
     120             : 
     121           2 :     CPLList *psCurrent = psList;
     122           4 :     for (int i = 0; i < nPosition - 1; i++)
     123           2 :         psCurrent = psCurrent->psNext;
     124           2 :     psNew->psNext = psCurrent->psNext;
     125           2 :     psCurrent->psNext = psNew;
     126             : 
     127           2 :     return psList;
     128             : }
     129             : 
     130             : /************************************************************************/
     131             : /*                          CPLListGetLast()                            */
     132             : /************************************************************************/
     133             : 
     134             : /**
     135             :  * Return the pointer to last element in a list.
     136             :  *
     137             :  * @param psList pointer to list head.
     138             :  *
     139             :  * @return pointer to last element in a list.
     140             :  */
     141             : 
     142          10 : CPLList *CPLListGetLast(CPLList *const psList)
     143             : {
     144          10 :     if (psList == nullptr)
     145           2 :         return nullptr;
     146             : 
     147           8 :     CPLList *psCurrent = psList;
     148           9 :     while (psCurrent->psNext)
     149           1 :         psCurrent = psCurrent->psNext;
     150             : 
     151           8 :     return psCurrent;
     152             : }
     153             : 
     154             : /************************************************************************/
     155             : /*                          CPLListGet()                                */
     156             : /************************************************************************/
     157             : 
     158             : /**
     159             :  * Return the pointer to the specified element in a list.
     160             :  *
     161             :  * @param psList pointer to list head.
     162             :  * @param nPosition the index of the element in the list, 0 being the
     163             :  * first element.
     164             :  *
     165             :  * @return pointer to the specified element in a list.
     166             :  */
     167             : 
     168          12 : CPLList *CPLListGet(CPLList *psList, int nPosition)
     169             : {
     170          12 :     if (nPosition < 0)
     171           0 :         return nullptr;
     172             : 
     173          12 :     CPLList *psCurrent = psList;
     174          12 :     int iItem = 0;
     175          27 :     while (iItem < nPosition && psCurrent)
     176             :     {
     177          15 :         psCurrent = psCurrent->psNext;
     178          15 :         iItem++;
     179             :     }
     180             : 
     181          12 :     return psCurrent;
     182             : }
     183             : 
     184             : /************************************************************************/
     185             : /*                          CPLListCount()                              */
     186             : /************************************************************************/
     187             : 
     188             : /**
     189             :  * Return the number of elements in a list.
     190             :  *
     191             :  * @param psList pointer to list head.
     192             :  *
     193             :  * @return number of elements in a list.
     194             :  */
     195             : 
     196          16 : int CPLListCount(const CPLList *psList)
     197             : {
     198          16 :     int nItems = 0;
     199          16 :     const CPLList *psCurrent = psList;
     200             : 
     201          43 :     while (psCurrent)
     202             :     {
     203          27 :         nItems++;
     204          27 :         psCurrent = psCurrent->psNext;
     205             :     }
     206             : 
     207          16 :     return nItems;
     208             : }
     209             : 
     210             : /************************************************************************/
     211             : /*                          CPLListRemove()                             */
     212             : /************************************************************************/
     213             : 
     214             : /**
     215             :  * Remove the element from the specified position (zero based) in a list. Data
     216             :  * object contained in removed element must be freed by the caller first.
     217             :  *
     218             :  * @param psList pointer to list head.
     219             :  * @param nPosition position number to delete an element.
     220             :  *
     221             :  * @return pointer to the head of modified list.
     222             :  */
     223             : 
     224          10 : CPLList *CPLListRemove(CPLList *psList, int nPosition)
     225             : {
     226             : 
     227          10 :     if (psList == nullptr)
     228           0 :         return nullptr;
     229             : 
     230          10 :     if (nPosition < 0)
     231           0 :         return psList; /* Nothing to do. */
     232             : 
     233          10 :     if (nPosition == 0)
     234             :     {
     235           4 :         CPLList *psCurrent = psList->psNext;
     236           4 :         CPLFree(psList);
     237           4 :         psList = psCurrent;
     238           4 :         return psList;
     239             :     }
     240             : 
     241           6 :     CPLList *psCurrent = psList;
     242           7 :     for (int i = 0; i < nPosition - 1; i++)
     243             :     {
     244           2 :         psCurrent = psCurrent->psNext;
     245             :         // psCurrent == NULL if nPosition >= CPLListCount(psList).
     246           2 :         if (psCurrent == nullptr)
     247           1 :             return psList;
     248             :     }
     249           5 :     CPLList *psRemoved = psCurrent->psNext;
     250             :     // psRemoved == NULL if nPosition >= CPLListCount(psList).
     251           5 :     if (psRemoved == nullptr)
     252           1 :         return psList;
     253           4 :     psCurrent->psNext = psRemoved->psNext;
     254           4 :     CPLFree(psRemoved);
     255             : 
     256           4 :     return psList;
     257             : }
     258             : 
     259             : /************************************************************************/
     260             : /*                          CPLListDestroy()                            */
     261             : /************************************************************************/
     262             : 
     263             : /**
     264             :  * Destroy a list. Caller responsible for freeing data objects contained in
     265             :  * list elements.
     266             :  *
     267             :  * @param psList pointer to list head.
     268             :  *
     269             :  */
     270             : 
     271        6295 : void CPLListDestroy(CPLList *psList)
     272             : {
     273        6295 :     CPLList *psCurrent = psList;
     274             : 
     275        9117 :     while (psCurrent)
     276             :     {
     277        2822 :         CPLList *const psNext = psCurrent->psNext;
     278        2822 :         CPLFree(psCurrent);
     279        2822 :         psCurrent = psNext;
     280             :     }
     281        6295 : }
     282             : 
     283             : /************************************************************************/
     284             : /*                          CPLListGetNext()                            */
     285             : /************************************************************************/
     286             : 
     287             : /**
     288             :  * Return the pointer to next element in a list.
     289             :  *
     290             :  * @param psElement pointer to list element.
     291             :  *
     292             :  * @return pointer to the list element preceded by the given element.
     293             :  */
     294             : 
     295           0 : CPLList *CPLListGetNext(const CPLList *psElement)
     296             : {
     297           0 :     if (psElement == nullptr)
     298           0 :         return nullptr;
     299             : 
     300           0 :     return psElement->psNext;
     301             : }
     302             : 
     303             : /************************************************************************/
     304             : /*                          CPLListGetData()                            */
     305             : /************************************************************************/
     306             : 
     307             : /**
     308             :  * Return pointer to the data object contained in given list element.
     309             :  *
     310             :  * @param psElement pointer to list element.
     311             :  *
     312             :  * @return pointer to the data object contained in given list element.
     313             :  */
     314             : 
     315           0 : void *CPLListGetData(const CPLList *psElement)
     316             : {
     317           0 :     if (psElement == nullptr)
     318           0 :         return nullptr;
     319             : 
     320           0 :     return psElement->pData;
     321             : }