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         137 : CPLList *CPLListAppend(CPLList *psList, void *pData)
      40             : {
      41         137 :     CPLList *psLast = nullptr;
      42             : 
      43             :     // Allocate room for the new object.
      44         137 :     if (psList == nullptr)
      45             :     {
      46          51 :         psLast = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
      47          51 :         psList = psLast;
      48             :     }
      49             :     else
      50             :     {
      51          86 :         psLast = CPLListGetLast(psList);
      52          86 :         psLast = psLast->psNext =
      53          86 :             static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
      54             :     }
      55             : 
      56             :     // Append object to the end of list.
      57         137 :     psLast->pData = pData;
      58         137 :     psLast->psNext = nullptr;
      59             : 
      60         137 :     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          10 : CPLList *CPLListInsert(CPLList *psList, void *pData, int nPosition)
      79             : {
      80          10 :     if (nPosition < 0)
      81           0 :         return psList;  // Nothing to do.
      82             : 
      83          10 :     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           8 :     const int nCount = CPLListCount(psList);
      93             : 
      94           8 :     if (nCount < nPosition)
      95             :     {
      96             :         // Allocate room for the new object.
      97           3 :         CPLList *psLast = CPLListGetLast(psList);
      98           7 :         for (int i = nCount; i <= nPosition - 1; i++)
      99             :         {
     100           4 :             psLast = CPLListAppend(psLast, nullptr);
     101           4 :             if (psList == nullptr)
     102           2 :                 psList = psLast;
     103             :             else
     104           2 :                 psLast = psLast->psNext;
     105             :         }
     106           3 :         psLast = CPLListAppend(psLast, pData);
     107           3 :         if (psList == nullptr)
     108           0 :             psList = psLast;
     109             : 
     110             :         /* coverity[leaked_storage] */
     111           3 :         return psList;
     112             :     }
     113             : 
     114           5 :     CPLList *psNew = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
     115           5 :     psNew->pData = pData;
     116             : 
     117           5 :     CPLList *psCurrent = psList;
     118          22 :     for (int i = 0; i < nPosition - 1; i++)
     119          17 :         psCurrent = psCurrent->psNext;
     120           5 :     psNew->psNext = psCurrent->psNext;
     121           5 :     psCurrent->psNext = psNew;
     122             : 
     123           5 :     return psList;
     124             : }
     125             : 
     126             : /************************************************************************/
     127             : /*                          CPLListGetLast()                            */
     128             : /************************************************************************/
     129             : 
     130             : /**
     131             :  * Return the pointer to last element in a list.
     132             :  *
     133             :  * @param psList pointer to list head.
     134             :  *
     135             :  * @return pointer to last element in a list.
     136             :  */
     137             : 
     138          89 : CPLList *CPLListGetLast(CPLList *const psList)
     139             : {
     140          89 :     if (psList == nullptr)
     141           2 :         return nullptr;
     142             : 
     143          87 :     CPLList *psCurrent = psList;
     144         394 :     while (psCurrent->psNext)
     145         307 :         psCurrent = psCurrent->psNext;
     146             : 
     147          87 :     return psCurrent;
     148             : }
     149             : 
     150             : /************************************************************************/
     151             : /*                          CPLListGet()                                */
     152             : /************************************************************************/
     153             : 
     154             : /**
     155             :  * Return the pointer to the specified element in a list.
     156             :  *
     157             :  * @param psList pointer to list head.
     158             :  * @param nPosition the index of the element in the list, 0 being the
     159             :  * first element.
     160             :  *
     161             :  * @return pointer to the specified element in a list.
     162             :  */
     163             : 
     164         940 : CPLList *CPLListGet(CPLList *psList, int nPosition)
     165             : {
     166         940 :     if (nPosition < 0)
     167           0 :         return nullptr;
     168             : 
     169         940 :     CPLList *psCurrent = psList;
     170         940 :     int iItem = 0;
     171        2178 :     while (iItem < nPosition && psCurrent)
     172             :     {
     173        1238 :         psCurrent = psCurrent->psNext;
     174        1238 :         iItem++;
     175             :     }
     176             : 
     177         940 :     return psCurrent;
     178             : }
     179             : 
     180             : /************************************************************************/
     181             : /*                          CPLListCount()                              */
     182             : /************************************************************************/
     183             : 
     184             : /**
     185             :  * Return the number of elements in a list.
     186             :  *
     187             :  * @param psList pointer to list head.
     188             :  *
     189             :  * @return number of elements in a list.
     190             :  */
     191             : 
     192         444 : int CPLListCount(const CPLList *psList)
     193             : {
     194         444 :     int nItems = 0;
     195         444 :     const CPLList *psCurrent = psList;
     196             : 
     197        1252 :     while (psCurrent)
     198             :     {
     199         808 :         nItems++;
     200         808 :         psCurrent = psCurrent->psNext;
     201             :     }
     202             : 
     203         444 :     return nItems;
     204             : }
     205             : 
     206             : /************************************************************************/
     207             : /*                          CPLListRemove()                             */
     208             : /************************************************************************/
     209             : 
     210             : /**
     211             :  * Remove the element from the specified position (zero based) in a list. Data
     212             :  * object contained in removed element must be freed by the caller first.
     213             :  *
     214             :  * @param psList pointer to list head.
     215             :  * @param nPosition position number to delete an element.
     216             :  *
     217             :  * @return pointer to the head of modified list.
     218             :  */
     219             : 
     220          10 : CPLList *CPLListRemove(CPLList *psList, int nPosition)
     221             : {
     222             : 
     223          10 :     if (psList == nullptr)
     224           0 :         return nullptr;
     225             : 
     226          10 :     if (nPosition < 0)
     227           0 :         return psList; /* Nothing to do. */
     228             : 
     229          10 :     if (nPosition == 0)
     230             :     {
     231           4 :         CPLList *psCurrent = psList->psNext;
     232           4 :         CPLFree(psList);
     233           4 :         psList = psCurrent;
     234           4 :         return psList;
     235             :     }
     236             : 
     237           6 :     CPLList *psCurrent = psList;
     238           7 :     for (int i = 0; i < nPosition - 1; i++)
     239             :     {
     240           2 :         psCurrent = psCurrent->psNext;
     241             :         // psCurrent == NULL if nPosition >= CPLListCount(psList).
     242           2 :         if (psCurrent == nullptr)
     243           1 :             return psList;
     244             :     }
     245           5 :     CPLList *psRemoved = psCurrent->psNext;
     246             :     // psRemoved == NULL if nPosition >= CPLListCount(psList).
     247           5 :     if (psRemoved == nullptr)
     248           1 :         return psList;
     249           4 :     psCurrent->psNext = psRemoved->psNext;
     250           4 :     CPLFree(psRemoved);
     251             : 
     252           4 :     return psList;
     253             : }
     254             : 
     255             : /************************************************************************/
     256             : /*                          CPLListDestroy()                            */
     257             : /************************************************************************/
     258             : 
     259             : /**
     260             :  * Destroy a list. Caller responsible for freeing data objects contained in
     261             :  * list elements.
     262             :  *
     263             :  * @param psList pointer to list head.
     264             :  *
     265             :  */
     266             : 
     267        6493 : void CPLListDestroy(CPLList *psList)
     268             : {
     269        6493 :     CPLList *psCurrent = psList;
     270             : 
     271        9960 :     while (psCurrent)
     272             :     {
     273        3467 :         CPLList *const psNext = psCurrent->psNext;
     274        3467 :         CPLFree(psCurrent);
     275        3467 :         psCurrent = psNext;
     276             :     }
     277        6493 : }
     278             : 
     279             : /************************************************************************/
     280             : /*                          CPLListGetNext()                            */
     281             : /************************************************************************/
     282             : 
     283             : /**
     284             :  * Return the pointer to next element in a list.
     285             :  *
     286             :  * @param psElement pointer to list element.
     287             :  *
     288             :  * @return pointer to the list element preceded by the given element.
     289             :  */
     290             : 
     291           0 : CPLList *CPLListGetNext(const CPLList *psElement)
     292             : {
     293           0 :     if (psElement == nullptr)
     294           0 :         return nullptr;
     295             : 
     296           0 :     return psElement->psNext;
     297             : }
     298             : 
     299             : /************************************************************************/
     300             : /*                          CPLListGetData()                            */
     301             : /************************************************************************/
     302             : 
     303             : /**
     304             :  * Return pointer to the data object contained in given list element.
     305             :  *
     306             :  * @param psElement pointer to list element.
     307             :  *
     308             :  * @return pointer to the data object contained in given list element.
     309             :  */
     310             : 
     311         928 : void *CPLListGetData(const CPLList *psElement)
     312             : {
     313         928 :     if (psElement == nullptr)
     314           0 :         return nullptr;
     315             : 
     316         928 :     return psElement->pData;
     317             : }