Line data    Source code

       1             : /******************************************************************************
       2             :  *
       3             :  * Project:  S-57 Translator
       4             :  * Purpose:  Implements DDFRecordIndex class.  This class is used to cache
       5             :  *           ISO8211 records for spatial objects so they can be efficiently
       6             :  *           assembled later as features.
       7             :  * Author:   Frank Warmerdam, warmerdam@pobox.com
       8             :  *
       9             :  ******************************************************************************
      10             :  * Copyright (c) 1999, 2001, Frank Warmerdam
      11             :  *
      12             :  * SPDX-License-Identifier: MIT
      13             :  ****************************************************************************/
      14             : 
      15             : #include "cpl_conv.h"
      16             : #include "s57.h"
      17             : 
      18             : /************************************************************************/
      19             : /*                           DDFRecordIndex()                           */
      20             : /************************************************************************/
      21             : 
      22         185 : DDFRecordIndex::DDFRecordIndex()
      23             :     : bSorted(false), nRecordCount(0), nRecordMax(0), nLastObjlPos(0),
      24         185 :       nLastObjl(0), pasRecords(nullptr)
      25             : {
      26         185 : }
      27             : 
      28             : /************************************************************************/
      29             : /*                          ~DDFRecordIndex()                           */
      30             : /************************************************************************/
      31             : 
      32         370 : DDFRecordIndex::~DDFRecordIndex()
      33             : 
      34             : {
      35         185 :     Clear();
      36         185 : }
      37             : 
      38             : /************************************************************************/
      39             : /*                               Clear()                                */
      40             : /*                                                                      */
      41             : /*      Clear all entries from the index and deallocate all index       */
      42             : /*      resources.                                                      */
      43             : /************************************************************************/
      44             : 
      45         370 : void DDFRecordIndex::Clear()
      46             : 
      47             : {
      48             :     // Deleting these records is very expensive
      49             :     // due to the linear search in DDFModule::RemoveClone().  For now,
      50             :     // just leave the clones depending on DDFModule::~DDFModule() to clean
      51             :     // them up eventually.
      52             : 
      53             :     // for( int i = 0; i < nRecordCount; i++ )
      54             :     //   delete pasRecords[i].poRecord;
      55             : 
      56         370 :     bSorted = false;
      57             : 
      58         370 :     nRecordCount = 0;
      59         370 :     nRecordMax = 0;
      60             : 
      61         370 :     nLastObjlPos = 0;
      62         370 :     nLastObjl = 0;
      63             : 
      64         370 :     CPLFree(pasRecords);
      65         370 :     pasRecords = nullptr;
      66         370 : }
      67             : 
      68             : /************************************************************************/
      69             : /*                             AddRecord()                              */
      70             : /*                                                                      */
      71             : /*      Add a record to the index.  The index will assume ownership     */
      72             : /*      of the record.  If passing a record just read from a            */
      73             : /*      DDFModule it is imperative that the caller Clone()'s the        */
      74             : /*      record first.                                                   */
      75             : /************************************************************************/
      76             : 
      77        1358 : void DDFRecordIndex::AddRecord(int nKey, DDFRecord *poRecord)
      78             : 
      79             : {
      80        1358 :     if (nRecordCount == nRecordMax)
      81             :     {
      82          70 :         nRecordMax = static_cast<int>(nRecordCount * 1.3 + 100);
      83          70 :         pasRecords = static_cast<DDFIndexedRecord *>(
      84          70 :             CPLRealloc(pasRecords, sizeof(DDFIndexedRecord) * nRecordMax));
      85             :     }
      86             : 
      87        1358 :     bSorted = false;
      88             : 
      89        1358 :     pasRecords[nRecordCount].nKey = nKey;
      90        1358 :     pasRecords[nRecordCount].poRecord = poRecord;
      91        1358 :     pasRecords[nRecordCount].pClientData = nullptr;
      92             : 
      93        1358 :     nRecordCount++;
      94        1358 : }
      95             : 
      96             : /************************************************************************/
      97             : /*                             FindRecord()                             */
      98             : /*                                                                      */
      99             : /*      Though the returned pointer is not const, it should be          */
     100             : /*      considered internal to the index and not modified or freed      */
     101             : /*      by application code.                                            */
     102             : /************************************************************************/
     103             : 
     104        8861 : DDFRecord *DDFRecordIndex::FindRecord(int nKey)
     105             : 
     106             : {
     107        8861 :     if (!bSorted)
     108          17 :         Sort();
     109             : 
     110             :     /* -------------------------------------------------------------------- */
     111             :     /*      Do a binary search based on the key to find the desired record. */
     112             :     /* -------------------------------------------------------------------- */
     113        8861 :     int nMinIndex = 0;
     114        8861 :     int nMaxIndex = nRecordCount - 1;
     115             : 
     116       32067 :     while (nMinIndex <= nMaxIndex)
     117             :     {
     118       32067 :         const int nTestIndex = (nMaxIndex + nMinIndex) / 2;
     119             : 
     120       32067 :         if (pasRecords[nTestIndex].nKey < nKey)
     121       11361 :             nMinIndex = nTestIndex + 1;
     122       20706 :         else if (pasRecords[nTestIndex].nKey > nKey)
     123       11845 :             nMaxIndex = nTestIndex - 1;
     124             :         else
     125        8861 :             return pasRecords[nTestIndex].poRecord;
     126             :     }
     127             : 
     128           0 :     return nullptr;
     129             : }
     130             : 
     131             : /************************************************************************/
     132             : /*                       FindRecordByObjl()                             */
     133             : /*      Rodney Jensen                                                   */
     134             : /*      Though the returned pointer is not const, it should be          */
     135             : /*      considered internal to the index and not modified or freed      */
     136             : /*      by application code.                                            */
     137             : /************************************************************************/
     138             : 
     139           0 : DDFRecord *DDFRecordIndex::FindRecordByObjl(int nObjl)
     140             : {
     141           0 :     if (!bSorted)
     142           0 :         Sort();
     143             : 
     144             :     /* -------------------------------------------------------------------- */
     145             :     /*      Do a linear search based on the nObjl to find the desired record. */
     146             :     /* -------------------------------------------------------------------- */
     147           0 :     int nMinIndex = 0;
     148           0 :     if (nLastObjl != nObjl)
     149           0 :         nLastObjlPos = 0;
     150             : 
     151           0 :     for (nMinIndex = nLastObjlPos; nMinIndex < nRecordCount; nMinIndex++)
     152             :     {
     153           0 :         if (nObjl == pasRecords[nMinIndex].poRecord->GetIntSubfield("FRID", 0,
     154             :                                                                     "OBJL", 0))
     155             :         {
     156             :             // Add 1.  Do not want to look at same again.
     157           0 :             nLastObjlPos = nMinIndex + 1;
     158           0 :             nLastObjl = nObjl;
     159           0 :             return pasRecords[nMinIndex].poRecord;
     160             :         }
     161             :     }
     162             : 
     163           0 :     nLastObjlPos = 0;
     164           0 :     nLastObjl = 0;
     165             : 
     166           0 :     return nullptr;
     167             : }
     168             : 
     169             : /************************************************************************/
     170             : /*                            RemoveRecord()                            */
     171             : /************************************************************************/
     172             : 
     173           0 : bool DDFRecordIndex::RemoveRecord(int nKey)
     174             : 
     175             : {
     176           0 :     if (!bSorted)
     177           0 :         Sort();
     178             : 
     179             :     /* -------------------------------------------------------------------- */
     180             :     /*      Do a binary search based on the key to find the desired record. */
     181             :     /* -------------------------------------------------------------------- */
     182           0 :     int nMinIndex = 0;
     183           0 :     int nMaxIndex = nRecordCount - 1;
     184           0 :     int nTestIndex = 0;
     185             : 
     186           0 :     while (nMinIndex <= nMaxIndex)
     187             :     {
     188           0 :         nTestIndex = (nMaxIndex + nMinIndex) / 2;
     189             : 
     190           0 :         if (pasRecords[nTestIndex].nKey < nKey)
     191           0 :             nMinIndex = nTestIndex + 1;
     192           0 :         else if (pasRecords[nTestIndex].nKey > nKey)
     193           0 :             nMaxIndex = nTestIndex - 1;
     194             :         else
     195           0 :             break;
     196             :     }
     197             : 
     198           0 :     if (nMinIndex > nMaxIndex)
     199           0 :         return false;
     200             : 
     201             :     /* -------------------------------------------------------------------- */
     202             :     /*      Delete this record.                                             */
     203             :     /* -------------------------------------------------------------------- */
     204           0 :     delete pasRecords[nTestIndex].poRecord;
     205             : 
     206             :     /* -------------------------------------------------------------------- */
     207             :     /*      Move all the list entries back one to fill the hole, and        */
     208             :     /*      update the total count.                                         */
     209             :     /* -------------------------------------------------------------------- */
     210           0 :     memmove(pasRecords + nTestIndex, pasRecords + nTestIndex + 1,
     211           0 :             (nRecordCount - nTestIndex - 1) * sizeof(DDFIndexedRecord));
     212             : 
     213           0 :     nRecordCount--;
     214             : 
     215           0 :     return true;
     216             : }
     217             : 
     218             : /************************************************************************/
     219             : /*                             DDFCompare()                             */
     220             : /*                                                                      */
     221             : /*      Compare two DDFIndexedRecord objects for qsort().               */
     222             : /************************************************************************/
     223             : 
     224        2557 : static int DDFCompare(const void *pRec1, const void *pRec2)
     225             : 
     226             : {
     227        2557 :     if (((const DDFIndexedRecord *)pRec1)->nKey ==
     228        2557 :         ((const DDFIndexedRecord *)pRec2)->nKey)
     229           0 :         return 0;
     230        2557 :     if (((const DDFIndexedRecord *)pRec1)->nKey <
     231        2557 :         ((const DDFIndexedRecord *)pRec2)->nKey)
     232        1918 :         return -1;
     233             : 
     234         639 :     return 1;
     235             : }
     236             : 
     237             : /************************************************************************/
     238             : /*                                Sort()                                */
     239             : /*                                                                      */
     240             : /*      Sort the records based on the key.                              */
     241             : /************************************************************************/
     242             : 
     243          42 : void DDFRecordIndex::Sort()
     244             : 
     245             : {
     246          42 :     if (bSorted)
     247           0 :         return;
     248             : 
     249          42 :     qsort(pasRecords, nRecordCount, sizeof(DDFIndexedRecord), DDFCompare);
     250             : 
     251          42 :     bSorted = true;
     252             : }
     253             : 
     254             : /************************************************************************/
     255             : /*                             GetByIndex()                             */
     256             : /************************************************************************/
     257             : 
     258        1618 : DDFRecord *DDFRecordIndex::GetByIndex(int nIndex)
     259             : 
     260             : {
     261        1618 :     if (!bSorted)
     262          25 :         Sort();
     263             : 
     264        1618 :     if (nIndex < 0 || nIndex >= nRecordCount)
     265           0 :         return nullptr;
     266             : 
     267        1618 :     return pasRecords[nIndex].poRecord;
     268             : }
     269             : 
     270             : /************************************************************************/
     271             : /*                        GetClientInfoByIndex()                        */
     272             : /************************************************************************/
     273             : 
     274        8389 : void *DDFRecordIndex::GetClientInfoByIndex(int nIndex)
     275             : 
     276             : {
     277        8389 :     if (!bSorted)
     278           0 :         Sort();
     279             : 
     280        8389 :     if (nIndex < 0 || nIndex >= nRecordCount)
     281           0 :         return nullptr;
     282             : 
     283        8389 :     return pasRecords[nIndex].pClientData;
     284             : }
     285             : 
     286             : /************************************************************************/
     287             : /*                        SetClientInfoByIndex()                        */
     288             : /************************************************************************/
     289             : 
     290         345 : void DDFRecordIndex::SetClientInfoByIndex(int nIndex, void *pClientData)
     291             : 
     292             : {
     293         345 :     if (!bSorted)
     294           0 :         Sort();
     295             : 
     296         345 :     if (nIndex < 0 || nIndex >= nRecordCount)
     297           0 :         return;
     298             : 
     299         345 :     pasRecords[nIndex].pClientData = pClientData;
     300             : }