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         195 : DDFRecordIndex::DDFRecordIndex()
      23         195 :     : bSorted(false), nRecordCount(0), nRecordMax(0), pasRecords(nullptr)
      24             : {
      25         195 : }
      26             : 
      27             : /************************************************************************/
      28             : /*                          ~DDFRecordIndex()                           */
      29             : /************************************************************************/
      30             : 
      31         390 : DDFRecordIndex::~DDFRecordIndex()
      32             : 
      33             : {
      34         195 :     Clear();
      35         195 : }
      36             : 
      37             : /************************************************************************/
      38             : /*                               Clear()                                */
      39             : /*                                                                      */
      40             : /*      Clear all entries from the index and deallocate all index       */
      41             : /*      resources.                                                      */
      42             : /************************************************************************/
      43             : 
      44         390 : void DDFRecordIndex::Clear()
      45             : 
      46             : {
      47             :     // Deleting these records is very expensive
      48             :     // due to the linear search in DDFModule::RemoveClone().  For now,
      49             :     // just leave the clones depending on DDFModule::~DDFModule() to clean
      50             :     // them up eventually.
      51             : 
      52             :     // for( int i = 0; i < nRecordCount; i++ )
      53             :     //   delete pasRecords[i].poRecord;
      54             : 
      55         390 :     bSorted = false;
      56             : 
      57         390 :     nRecordCount = 0;
      58         390 :     nRecordMax = 0;
      59             : 
      60         390 :     CPLFree(pasRecords);
      61         390 :     pasRecords = nullptr;
      62         390 : }
      63             : 
      64             : /************************************************************************/
      65             : /*                             AddRecord()                              */
      66             : /*                                                                      */
      67             : /*      Add a record to the index.  The index will assume ownership     */
      68             : /*      of the record.  If passing a record just read from a            */
      69             : /*      DDFModule it is imperative that the caller Clone()'s the        */
      70             : /*      record first.                                                   */
      71             : /************************************************************************/
      72             : 
      73       27573 : void DDFRecordIndex::AddRecord(int nKey, DDFRecord *poRecord)
      74             : 
      75             : {
      76       27573 :     if (nRecordCount == nRecordMax)
      77             :     {
      78         134 :         nRecordMax = static_cast<int>(nRecordCount * 1.3 + 100);
      79         134 :         pasRecords = static_cast<DDFIndexedRecord *>(
      80         134 :             CPLRealloc(pasRecords, sizeof(DDFIndexedRecord) * nRecordMax));
      81             :     }
      82             : 
      83       27573 :     bSorted = false;
      84             : 
      85       27573 :     pasRecords[nRecordCount].nKey = nKey;
      86       27573 :     pasRecords[nRecordCount].poRecord = poRecord;
      87       27573 :     pasRecords[nRecordCount].pClientData = nullptr;
      88             : 
      89       27573 :     nRecordCount++;
      90       27573 : }
      91             : 
      92             : /************************************************************************/
      93             : /*                             FindRecord()                             */
      94             : /*                                                                      */
      95             : /*      Though the returned pointer is not const, it should be          */
      96             : /*      considered internal to the index and not modified or freed      */
      97             : /*      by application code.                                            */
      98             : /************************************************************************/
      99             : 
     100      116645 : DDFRecord *DDFRecordIndex::FindRecord(int nKey)
     101             : 
     102             : {
     103      116645 :     if (!bSorted)
     104          30 :         Sort();
     105             : 
     106             :     /* -------------------------------------------------------------------- */
     107             :     /*      Do a binary search based on the key to find the desired record. */
     108             :     /* -------------------------------------------------------------------- */
     109      116645 :     int nMinIndex = 0;
     110      116645 :     int nMaxIndex = nRecordCount - 1;
     111             : 
     112     1296390 :     while (nMinIndex <= nMaxIndex)
     113             :     {
     114     1296390 :         const int nTestIndex = (nMaxIndex + nMinIndex) / 2;
     115             : 
     116     1296390 :         if (pasRecords[nTestIndex].nKey < nKey)
     117      594482 :             nMinIndex = nTestIndex + 1;
     118      701910 :         else if (pasRecords[nTestIndex].nKey > nKey)
     119      585265 :             nMaxIndex = nTestIndex - 1;
     120             :         else
     121      116645 :             return pasRecords[nTestIndex].poRecord;
     122             :     }
     123             : 
     124           0 :     return nullptr;
     125             : }
     126             : 
     127             : /************************************************************************/
     128             : /*                            RemoveRecord()                            */
     129             : /************************************************************************/
     130             : 
     131          18 : bool DDFRecordIndex::RemoveRecord(int nKey)
     132             : 
     133             : {
     134          18 :     if (!bSorted)
     135           0 :         Sort();
     136             : 
     137             :     /* -------------------------------------------------------------------- */
     138             :     /*      Do a binary search based on the key to find the desired record. */
     139             :     /* -------------------------------------------------------------------- */
     140          18 :     int nMinIndex = 0;
     141          18 :     int nMaxIndex = nRecordCount - 1;
     142          18 :     int nTestIndex = 0;
     143             : 
     144         145 :     while (nMinIndex <= nMaxIndex)
     145             :     {
     146         145 :         nTestIndex = (nMaxIndex + nMinIndex) / 2;
     147             : 
     148         145 :         if (pasRecords[nTestIndex].nKey < nKey)
     149         110 :             nMinIndex = nTestIndex + 1;
     150          35 :         else if (pasRecords[nTestIndex].nKey > nKey)
     151          17 :             nMaxIndex = nTestIndex - 1;
     152             :         else
     153          18 :             break;
     154             :     }
     155             : 
     156          18 :     if (nMinIndex > nMaxIndex)
     157           0 :         return false;
     158             : 
     159             :     /* -------------------------------------------------------------------- */
     160             :     /*      Delete this record.                                             */
     161             :     /* -------------------------------------------------------------------- */
     162          18 :     delete pasRecords[nTestIndex].poRecord;
     163             : 
     164             :     /* -------------------------------------------------------------------- */
     165             :     /*      Move all the list entries back one to fill the hole, and        */
     166             :     /*      update the total count.                                         */
     167             :     /* -------------------------------------------------------------------- */
     168          18 :     memmove(pasRecords + nTestIndex, pasRecords + nTestIndex + 1,
     169          18 :             (nRecordCount - nTestIndex - 1) * sizeof(DDFIndexedRecord));
     170             : 
     171          18 :     nRecordCount--;
     172             : 
     173          18 :     return true;
     174             : }
     175             : 
     176             : /************************************************************************/
     177             : /*                             DDFCompare()                             */
     178             : /*                                                                      */
     179             : /*      Compare two DDFIndexedRecord objects for qsort().               */
     180             : /************************************************************************/
     181             : 
     182      204729 : static int DDFCompare(const void *pRec1, const void *pRec2)
     183             : 
     184             : {
     185      204729 :     if (((const DDFIndexedRecord *)pRec1)->nKey ==
     186      204729 :         ((const DDFIndexedRecord *)pRec2)->nKey)
     187           0 :         return 0;
     188      204729 :     if (((const DDFIndexedRecord *)pRec1)->nKey <
     189      204729 :         ((const DDFIndexedRecord *)pRec2)->nKey)
     190      186005 :         return -1;
     191             : 
     192       18724 :     return 1;
     193             : }
     194             : 
     195             : /************************************************************************/
     196             : /*                                Sort()                                */
     197             : /*                                                                      */
     198             : /*      Sort the records based on the key.                              */
     199             : /************************************************************************/
     200             : 
     201          57 : void DDFRecordIndex::Sort()
     202             : 
     203             : {
     204          57 :     if (bSorted)
     205           0 :         return;
     206             : 
     207          57 :     qsort(pasRecords, nRecordCount, sizeof(DDFIndexedRecord), DDFCompare);
     208             : 
     209          57 :     bSorted = true;
     210             : }
     211             : 
     212             : /************************************************************************/
     213             : /*                             GetByIndex()                             */
     214             : /************************************************************************/
     215             : 
     216       23215 : DDFRecord *DDFRecordIndex::GetByIndex(int nIndex)
     217             : 
     218             : {
     219       23215 :     if (!bSorted)
     220          27 :         Sort();
     221             : 
     222       23215 :     if (nIndex < 0 || nIndex >= nRecordCount)
     223           0 :         return nullptr;
     224             : 
     225       23215 :     return pasRecords[nIndex].poRecord;
     226             : }
     227             : 
     228             : /************************************************************************/
     229             : /*                        GetClientInfoByIndex()                        */
     230             : /************************************************************************/
     231             : 
     232      331300 : void *DDFRecordIndex::GetClientInfoByIndex(int nIndex)
     233             : 
     234             : {
     235      331300 :     if (!bSorted)
     236           0 :         Sort();
     237             : 
     238      331300 :     if (nIndex < 0 || nIndex >= nRecordCount)
     239           0 :         return nullptr;
     240             : 
     241      331300 :     return pasRecords[nIndex].pClientData;
     242             : }
     243             : 
     244             : /************************************************************************/
     245             : /*                        SetClientInfoByIndex()                        */
     246             : /************************************************************************/
     247             : 
     248        7207 : void DDFRecordIndex::SetClientInfoByIndex(int nIndex, void *pClientData)
     249             : 
     250             : {
     251        7207 :     if (!bSorted)
     252           0 :         Sort();
     253             : 
     254        7207 :     if (nIndex < 0 || nIndex >= nRecordCount)
     255           0 :         return;
     256             : 
     257        7207 :     pasRecords[nIndex].pClientData = pClientData;
     258             : }