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