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             :  * Permission is hereby granted, free of charge, to any person obtaining a
      13             :  * copy of this software and associated documentation files (the "Software"),
      14             :  * to deal in the Software without restriction, including without limitation
      15             :  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
      16             :  * and/or sell copies of the Software, and to permit persons to whom the
      17             :  * Software is furnished to do so, subject to the following conditions:
      18             :  *
      19             :  * The above copyright notice and this permission notice shall be included
      20             :  * in all copies or substantial portions of the Software.
      21             :  *
      22             :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      23             :  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      24             :  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
      25             :  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      26             :  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
      27             :  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
      28             :  * DEALINGS IN THE SOFTWARE.
      29             :  ****************************************************************************/
      30             : 
      31             : #include "cpl_list.h"
      32             : 
      33             : #include <cstddef>
      34             : 
      35             : #include "cpl_conv.h"
      36             : 
      37             : /*=====================================================================
      38             :                     List manipulation functions.
      39             :  =====================================================================*/
      40             : 
      41             : /************************************************************************/
      42             : /*                          CPLListAppend()                             */
      43             : /************************************************************************/
      44             : 
      45             : /**
      46             :  * Append an object list and return a pointer to the modified list.
      47             :  * If the input list is NULL, then a new list is created.
      48             :  *
      49             :  * @param psList pointer to list head.
      50             :  * @param pData pointer to inserted data object. May be NULL.
      51             :  *
      52             :  * @return pointer to the head of modified list.
      53             :  */
      54             : 
      55         137 : CPLList *CPLListAppend(CPLList *psList, void *pData)
      56             : {
      57         137 :     CPLList *psLast = nullptr;
      58             : 
      59             :     // Allocate room for the new object.
      60         137 :     if (psList == nullptr)
      61             :     {
      62          51 :         psLast = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
      63          51 :         psList = psLast;
      64             :     }
      65             :     else
      66             :     {
      67          86 :         psLast = CPLListGetLast(psList);
      68          86 :         psLast = psLast->psNext =
      69          86 :             static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
      70             :     }
      71             : 
      72             :     // Append object to the end of list.
      73         137 :     psLast->pData = pData;
      74         137 :     psLast->psNext = nullptr;
      75             : 
      76         137 :     return psList;
      77             : }
      78             : 
      79             : /************************************************************************/
      80             : /*                          CPLListInsert()                             */
      81             : /************************************************************************/
      82             : 
      83             : /**
      84             :  * Insert an object into list at specified position (zero based).
      85             :  * If the input list is NULL, then a new list is created.
      86             :  *
      87             :  * @param psList pointer to list head.
      88             :  * @param pData pointer to inserted data object. May be NULL.
      89             :  * @param nPosition position number to insert an object.
      90             :  *
      91             :  * @return pointer to the head of modified list.
      92             :  */
      93             : 
      94          10 : CPLList *CPLListInsert(CPLList *psList, void *pData, int nPosition)
      95             : {
      96          10 :     if (nPosition < 0)
      97           0 :         return psList;  // Nothing to do.
      98             : 
      99          10 :     if (nPosition == 0)
     100             :     {
     101           2 :         CPLList *psNew = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
     102           2 :         psNew->pData = pData;
     103           2 :         psNew->psNext = psList;
     104           2 :         psList = psNew;
     105           2 :         return psList;
     106             :     }
     107             : 
     108           8 :     const int nCount = CPLListCount(psList);
     109             : 
     110           8 :     if (nCount < nPosition)
     111             :     {
     112             :         // Allocate room for the new object.
     113           3 :         CPLList *psLast = CPLListGetLast(psList);
     114           7 :         for (int i = nCount; i <= nPosition - 1; i++)
     115             :         {
     116           4 :             psLast = CPLListAppend(psLast, nullptr);
     117           4 :             if (psList == nullptr)
     118           2 :                 psList = psLast;
     119             :             else
     120           2 :                 psLast = psLast->psNext;
     121             :         }
     122           3 :         psLast = CPLListAppend(psLast, pData);
     123           3 :         if (psList == nullptr)
     124           0 :             psList = psLast;
     125             : 
     126             :         /* coverity[leaked_storage] */
     127           3 :         return psList;
     128             :     }
     129             : 
     130           5 :     CPLList *psNew = static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
     131           5 :     psNew->pData = pData;
     132             : 
     133           5 :     CPLList *psCurrent = psList;
     134          22 :     for (int i = 0; i < nPosition - 1; i++)
     135          17 :         psCurrent = psCurrent->psNext;
     136           5 :     psNew->psNext = psCurrent->psNext;
     137           5 :     psCurrent->psNext = psNew;
     138             : 
     139           5 :     return psList;
     140             : }
     141             : 
     142             : /************************************************************************/
     143             : /*                          CPLListGetLast()                            */
     144             : /************************************************************************/
     145             : 
     146             : /**
     147             :  * Return the pointer to last element in a list.
     148             :  *
     149             :  * @param psList pointer to list head.
     150             :  *
     151             :  * @return pointer to last element in a list.
     152             :  */
     153             : 
     154          89 : CPLList *CPLListGetLast(CPLList *const psList)
     155             : {
     156          89 :     if (psList == nullptr)
     157           2 :         return nullptr;
     158             : 
     159          87 :     CPLList *psCurrent = psList;
     160         394 :     while (psCurrent->psNext)
     161         307 :         psCurrent = psCurrent->psNext;
     162             : 
     163          87 :     return psCurrent;
     164             : }
     165             : 
     166             : /************************************************************************/
     167             : /*                          CPLListGet()                                */
     168             : /************************************************************************/
     169             : 
     170             : /**
     171             :  * Return the pointer to the specified element in a list.
     172             :  *
     173             :  * @param psList pointer to list head.
     174             :  * @param nPosition the index of the element in the list, 0 being the
     175             :  * first element.
     176             :  *
     177             :  * @return pointer to the specified element in a list.
     178             :  */
     179             : 
     180         940 : CPLList *CPLListGet(CPLList *psList, int nPosition)
     181             : {
     182         940 :     if (nPosition < 0)
     183           0 :         return nullptr;
     184             : 
     185         940 :     CPLList *psCurrent = psList;
     186         940 :     int iItem = 0;
     187        2178 :     while (iItem < nPosition && psCurrent)
     188             :     {
     189        1238 :         psCurrent = psCurrent->psNext;
     190        1238 :         iItem++;
     191             :     }
     192             : 
     193         940 :     return psCurrent;
     194             : }
     195             : 
     196             : /************************************************************************/
     197             : /*                          CPLListCount()                              */
     198             : /************************************************************************/
     199             : 
     200             : /**
     201             :  * Return the number of elements in a list.
     202             :  *
     203             :  * @param psList pointer to list head.
     204             :  *
     205             :  * @return number of elements in a list.
     206             :  */
     207             : 
     208         444 : int CPLListCount(const CPLList *psList)
     209             : {
     210         444 :     int nItems = 0;
     211         444 :     const CPLList *psCurrent = psList;
     212             : 
     213        1252 :     while (psCurrent)
     214             :     {
     215         808 :         nItems++;
     216         808 :         psCurrent = psCurrent->psNext;
     217             :     }
     218             : 
     219         444 :     return nItems;
     220             : }
     221             : 
     222             : /************************************************************************/
     223             : /*                          CPLListRemove()                             */
     224             : /************************************************************************/
     225             : 
     226             : /**
     227             :  * Remove the element from the specified position (zero based) in a list. Data
     228             :  * object contained in removed element must be freed by the caller first.
     229             :  *
     230             :  * @param psList pointer to list head.
     231             :  * @param nPosition position number to delete an element.
     232             :  *
     233             :  * @return pointer to the head of modified list.
     234             :  */
     235             : 
     236          10 : CPLList *CPLListRemove(CPLList *psList, int nPosition)
     237             : {
     238             : 
     239          10 :     if (psList == nullptr)
     240           0 :         return nullptr;
     241             : 
     242          10 :     if (nPosition < 0)
     243           0 :         return psList; /* Nothing to do. */
     244             : 
     245          10 :     if (nPosition == 0)
     246             :     {
     247           4 :         CPLList *psCurrent = psList->psNext;
     248           4 :         CPLFree(psList);
     249           4 :         psList = psCurrent;
     250           4 :         return psList;
     251             :     }
     252             : 
     253           6 :     CPLList *psCurrent = psList;
     254           7 :     for (int i = 0; i < nPosition - 1; i++)
     255             :     {
     256           2 :         psCurrent = psCurrent->psNext;
     257             :         // psCurrent == NULL if nPosition >= CPLListCount(psList).
     258           2 :         if (psCurrent == nullptr)
     259           1 :             return psList;
     260             :     }
     261           5 :     CPLList *psRemoved = psCurrent->psNext;
     262             :     // psRemoved == NULL if nPosition >= CPLListCount(psList).
     263           5 :     if (psRemoved == nullptr)
     264           1 :         return psList;
     265           4 :     psCurrent->psNext = psRemoved->psNext;
     266           4 :     CPLFree(psRemoved);
     267             : 
     268           4 :     return psList;
     269             : }
     270             : 
     271             : /************************************************************************/
     272             : /*                          CPLListDestroy()                            */
     273             : /************************************************************************/
     274             : 
     275             : /**
     276             :  * Destroy a list. Caller responsible for freeing data objects contained in
     277             :  * list elements.
     278             :  *
     279             :  * @param psList pointer to list head.
     280             :  *
     281             :  */
     282             : 
     283        5458 : void CPLListDestroy(CPLList *psList)
     284             : {
     285        5458 :     CPLList *psCurrent = psList;
     286             : 
     287        7147 :     while (psCurrent)
     288             :     {
     289        1689 :         CPLList *const psNext = psCurrent->psNext;
     290        1689 :         CPLFree(psCurrent);
     291        1689 :         psCurrent = psNext;
     292             :     }
     293        5458 : }
     294             : 
     295             : /************************************************************************/
     296             : /*                          CPLListGetNext()                            */
     297             : /************************************************************************/
     298             : 
     299             : /**
     300             :  * Return the pointer to next element in a list.
     301             :  *
     302             :  * @param psElement pointer to list element.
     303             :  *
     304             :  * @return pointer to the list element preceded by the given element.
     305             :  */
     306             : 
     307           0 : CPLList *CPLListGetNext(const CPLList *psElement)
     308             : {
     309           0 :     if (psElement == nullptr)
     310           0 :         return nullptr;
     311             : 
     312           0 :     return psElement->psNext;
     313             : }
     314             : 
     315             : /************************************************************************/
     316             : /*                          CPLListGetData()                            */
     317             : /************************************************************************/
     318             : 
     319             : /**
     320             :  * Return pointer to the data object contained in given list element.
     321             :  *
     322             :  * @param psElement pointer to list element.
     323             :  *
     324             :  * @return pointer to the data object contained in given list element.
     325             :  */
     326             : 
     327         928 : void *CPLListGetData(const CPLList *psElement)
     328             : {
     329         928 :     if (psElement == nullptr)
     330           0 :         return nullptr;
     331             : 
     332         928 :     return psElement->pData;
     333             : }