Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: OpenGIS Simple Features Reference Implementation
4 : * Purpose: Implements writing of FileGDB indices
5 : * Author: Even Rouault, <even dot rouault at spatialys.com>
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2022, Even Rouault <even dot rouault at spatialys.com>
9 : *
10 : * Permission is hereby granted, free of charge, to any person obtaining a
11 : * copy of this software and associated documentation files (the "Software"),
12 : * to deal in the Software without restriction, including without limitation
13 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 : * and/or sell copies of the Software, and to permit persons to whom the
15 : * Software is furnished to do so, subject to the following conditions:
16 : *
17 : * The above copyright notice and this permission notice shall be included
18 : * in all copies or substantial portions of the Software.
19 : *
20 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 : * DEALINGS IN THE SOFTWARE.
27 : ****************************************************************************/
28 :
29 : #include "cpl_port.h"
30 :
31 : #include "filegdbtable.h"
32 : #include "filegdbtable_priv.h"
33 :
34 : #include <cctype>
35 : #include <cstdint>
36 : #include <algorithm>
37 : #include <limits>
38 :
39 : #include "cpl_string.h"
40 :
41 : namespace OpenFileGDB
42 : {
43 :
44 : /************************************************************************/
45 : /* RemoveIndices() */
46 : /************************************************************************/
47 :
48 2700 : void FileGDBTable::RemoveIndices()
49 : {
50 2700 : if (!m_bUpdate)
51 0 : return;
52 :
53 2700 : CPLString osUCGeomFieldName;
54 2700 : if (m_iGeomField >= 0)
55 : {
56 743 : osUCGeomFieldName = m_apoFields[m_iGeomField]->GetName();
57 743 : osUCGeomFieldName.toupper();
58 : }
59 :
60 2700 : GetIndexCount();
61 3189 : for (const auto &poIndex : m_apoIndexes)
62 : {
63 978 : if (m_iObjectIdField >= 0 &&
64 489 : m_apoFields[m_iObjectIdField]->m_poIndex == poIndex.get())
65 : {
66 273 : continue;
67 : }
68 :
69 432 : CPLString osUCIndexFieldName(poIndex->GetExpression());
70 216 : osUCIndexFieldName.toupper();
71 216 : if (osUCIndexFieldName == osUCGeomFieldName)
72 : {
73 197 : VSIUnlink(CPLResetExtension(m_osFilename.c_str(), "spx"));
74 : }
75 : else
76 : {
77 19 : VSIUnlink(
78 : CPLResetExtension(m_osFilename.c_str(),
79 38 : (poIndex->GetIndexName() + ".atx").c_str()));
80 : }
81 : }
82 :
83 2700 : m_nHasSpatialIndex = false;
84 : }
85 :
86 : /************************************************************************/
87 : /* RefreshIndices() */
88 : /************************************************************************/
89 :
90 2655 : void FileGDBTable::RefreshIndices()
91 : {
92 2655 : if (!m_bUpdate)
93 0 : return;
94 :
95 2655 : RemoveIndices();
96 :
97 3048 : for (const auto &poIndex : m_apoIndexes)
98 : {
99 786 : if (m_iObjectIdField >= 0 &&
100 393 : m_apoFields[m_iObjectIdField]->m_poIndex == poIndex.get())
101 : {
102 228 : continue;
103 : }
104 :
105 163 : if (m_iGeomField >= 0 &&
106 328 : m_apoFields[m_iGeomField]->m_poIndex == poIndex.get() &&
107 153 : m_eTableGeomType != FGTGT_MULTIPATCH)
108 : {
109 151 : CreateSpatialIndex();
110 : }
111 : else
112 : {
113 28 : const std::string osFieldName = poIndex->GetFieldName();
114 14 : const int iField = GetFieldIdx(osFieldName);
115 14 : if (iField >= 0)
116 : {
117 14 : const auto eFieldType = m_apoFields[iField]->GetType();
118 14 : if (eFieldType == FGFT_INT16 || eFieldType == FGFT_INT32 ||
119 11 : eFieldType == FGFT_FLOAT32 || eFieldType == FGFT_FLOAT64 ||
120 8 : eFieldType == FGFT_STRING || eFieldType == FGFT_DATETIME)
121 : {
122 7 : CreateAttributeIndex(poIndex.get());
123 : }
124 : }
125 : }
126 : }
127 : }
128 :
129 : /************************************************************************/
130 : /* CreateIndex() */
131 : /************************************************************************/
132 :
133 474 : bool FileGDBTable::CreateIndex(const std::string &osIndexName,
134 : const std::string &osExpression)
135 : {
136 474 : if (!m_bUpdate)
137 0 : return false;
138 :
139 948 : if (osIndexName.empty() ||
140 474 : !((osIndexName[0] >= 'a' && osIndexName[0] <= 'z') ||
141 457 : (osIndexName[0] >= 'A' && osIndexName[0] <= 'Z')))
142 : {
143 1 : CPLError(CE_Failure, CPLE_AppDefined,
144 : "Invalid index name: must start with a letter");
145 1 : return false;
146 : }
147 :
148 5561 : for (const char ch : osIndexName)
149 : {
150 5089 : if (!isalnum(static_cast<unsigned char>(ch)) && ch != '_')
151 : {
152 1 : CPLError(CE_Failure, CPLE_AppDefined,
153 : "Invalid index name: must contain only alpha numeric "
154 : "character or _");
155 1 : return false;
156 : }
157 : }
158 :
159 472 : if (osIndexName.size() > 16)
160 : {
161 1 : CPLError(CE_Failure, CPLE_AppDefined,
162 : "Invalid index name: cannot be greater than 16 characters");
163 1 : return false;
164 : }
165 :
166 729 : for (const auto &poIndex : m_apoIndexes)
167 : {
168 259 : if (EQUAL(poIndex->GetIndexName().c_str(), osIndexName.c_str()))
169 : {
170 1 : CPLError(CE_Failure, CPLE_AppDefined,
171 : "An index with same name already exists");
172 1 : return false;
173 : }
174 : }
175 :
176 : const std::string osFieldName =
177 940 : FileGDBIndex::GetFieldNameFromExpression(osExpression);
178 470 : const int iField = GetFieldIdx(osFieldName);
179 470 : if (iField < 0)
180 : {
181 1 : CPLError(CE_Failure, CPLE_AppDefined, "Cannot find field %s",
182 : osFieldName.c_str());
183 1 : return false;
184 : }
185 :
186 469 : if (m_apoFields[iField]->m_poIndex != nullptr)
187 : {
188 2 : CPLError(CE_Failure, CPLE_AppDefined,
189 : "Field %s has already a registered index",
190 : osFieldName.c_str());
191 2 : return false;
192 : }
193 :
194 467 : const auto eFieldType = m_apoFields[iField]->GetType();
195 467 : if (eFieldType != FGFT_OBJECTID && eFieldType != FGFT_GEOMETRY &&
196 10 : eFieldType != FGFT_INT16 && eFieldType != FGFT_INT32 &&
197 8 : eFieldType != FGFT_FLOAT32 && eFieldType != FGFT_FLOAT64 &&
198 5 : eFieldType != FGFT_STRING && eFieldType != FGFT_DATETIME &&
199 3 : eFieldType != FGFT_INT64 && eFieldType != FGFT_DATE &&
200 1 : eFieldType != FGFT_TIME && eFieldType != FGFT_DATETIME_WITH_OFFSET)
201 : {
202 : // FGFT_GUID could potentially be added (cf a00000007.gdbindexes /
203 : // GDBItemRelationshipTypes ) Not sure about FGFT_GLOBALID, FGFT_XML or
204 : // FGFT_RASTER
205 0 : CPLError(CE_Failure, CPLE_AppDefined,
206 : "Unsupported field type for index creation");
207 0 : return false;
208 : }
209 :
210 467 : m_bDirtyGdbIndexesFile = true;
211 :
212 934 : auto poIndex = std::make_unique<FileGDBIndex>();
213 467 : poIndex->m_osIndexName = osIndexName;
214 467 : poIndex->m_osExpression = osExpression;
215 :
216 467 : if (iField != m_iObjectIdField && iField != m_iGeomField)
217 : {
218 11 : if (!CreateAttributeIndex(poIndex.get()))
219 0 : return false;
220 : }
221 :
222 467 : m_apoFields[iField]->m_poIndex = poIndex.get();
223 :
224 467 : m_apoIndexes.push_back(std::move(poIndex));
225 :
226 467 : return true;
227 : }
228 :
229 : /************************************************************************/
230 : /* CreateGdbIndexesFile() */
231 : /************************************************************************/
232 :
233 268 : void FileGDBTable::CreateGdbIndexesFile()
234 : {
235 268 : std::vector<GByte> abyBuffer;
236 :
237 268 : WriteUInt32(abyBuffer, static_cast<uint32_t>(m_apoIndexes.size()));
238 754 : for (const auto &poIndex : m_apoIndexes)
239 : {
240 486 : const FileGDBField *poField = nullptr;
241 793 : for (size_t i = 0; i < m_apoFields.size(); i++)
242 : {
243 793 : if (CPLString(poIndex->GetFieldName()).toupper() ==
244 1586 : CPLString(m_apoFields[i]->GetName()).toupper())
245 : {
246 486 : poField = m_apoFields[i].get();
247 486 : break;
248 : }
249 : }
250 486 : if (poField == nullptr)
251 : {
252 0 : CPLError(CE_Failure, CPLE_AppDefined,
253 : "Cannot find field corresponding to index field name %s",
254 0 : poIndex->GetFieldName().c_str());
255 0 : return;
256 : }
257 :
258 486 : WriteUTF16String(abyBuffer, poIndex->GetIndexName().c_str(),
259 : NUMBER_OF_CHARS_ON_UINT32);
260 486 : WriteUInt16(abyBuffer, 0); // unknown semantics
261 486 : if (poField->GetType() == FGFT_OBJECTID)
262 : {
263 267 : WriteUInt32(abyBuffer, 16); // unknown semantics
264 267 : WriteUInt16(abyBuffer, 0xFFFF); // unknown semantics
265 : }
266 219 : else if (poField->GetType() == FGFT_GEOMETRY)
267 : {
268 195 : WriteUInt32(abyBuffer, 4); // unknown semantics
269 195 : WriteUInt16(abyBuffer, 0); // unknown semantics
270 : }
271 : else
272 : {
273 24 : WriteUInt32(abyBuffer, 2); // unknown semantics
274 24 : WriteUInt16(abyBuffer, 0); // unknown semantics
275 : }
276 486 : WriteUInt32(abyBuffer, 1); // unknown semantics
277 486 : WriteUTF16String(abyBuffer, poIndex->GetExpression().c_str(),
278 : NUMBER_OF_CHARS_ON_UINT32);
279 486 : WriteUInt16(abyBuffer, 0); // unknown semantics
280 : }
281 :
282 : VSILFILE *fp =
283 268 : VSIFOpenL(CPLResetExtension(m_osFilename.c_str(), "gdbindexes"), "wb");
284 268 : if (fp == nullptr)
285 0 : return;
286 268 : CPL_IGNORE_RET_VAL(VSIFWriteL(abyBuffer.data(), abyBuffer.size(), 1, fp));
287 268 : VSIFCloseL(fp);
288 : }
289 :
290 : /************************************************************************/
291 : /* ComputeOptimalSpatialIndexGridResolution() */
292 : /************************************************************************/
293 :
294 151 : void FileGDBTable::ComputeOptimalSpatialIndexGridResolution()
295 : {
296 302 : if (m_nValidRecordCount == 0 || m_iGeomField < 0 ||
297 151 : m_adfSpatialIndexGridResolution.size() != 1)
298 : {
299 0 : return;
300 : }
301 :
302 : auto poGeomField =
303 151 : cpl::down_cast<FileGDBGeomField *>(m_apoFields[m_iGeomField].get());
304 151 : if (m_eTableGeomType == FGTGT_POINT)
305 : {
306 : // For point, use the density as the grid resolution
307 70 : int nValid = 0;
308 3901 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
309 : {
310 3831 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
311 3831 : if (iCurFeat < 0)
312 0 : break;
313 3831 : const OGRField *psField = GetFieldValue(m_iGeomField);
314 3831 : if (psField != nullptr)
315 3785 : nValid++;
316 : }
317 70 : if (nValid > 0)
318 : {
319 : const double dfArea =
320 53 : (poGeomField->GetXMax() - poGeomField->GetXMin()) *
321 53 : (poGeomField->GetYMax() - poGeomField->GetYMin());
322 53 : if (dfArea != 0)
323 : {
324 33 : m_adfSpatialIndexGridResolution[0] = sqrt(dfArea / nValid);
325 : }
326 20 : else if (poGeomField->GetXMax() > poGeomField->GetXMin())
327 : {
328 0 : m_adfSpatialIndexGridResolution[0] =
329 0 : (poGeomField->GetXMax() - poGeomField->GetXMin()) / nValid;
330 : }
331 20 : else if (poGeomField->GetYMax() > poGeomField->GetYMin())
332 : {
333 0 : m_adfSpatialIndexGridResolution[0] =
334 0 : (poGeomField->GetYMax() - poGeomField->GetYMin()) / nValid;
335 : }
336 : else
337 : {
338 20 : return;
339 : }
340 33 : m_bDirtyGeomFieldSpatialIndexGridRes = true;
341 : poGeomField->m_adfSpatialIndexGridResolution =
342 33 : m_adfSpatialIndexGridResolution;
343 : }
344 : }
345 :
346 81 : else if (m_eTableGeomType == FGTGT_MULTIPOINT)
347 : {
348 : // For multipoint, use the density as the grid resolution
349 9 : int64_t nValid = 0;
350 : auto poGeomConverter = std::unique_ptr<FileGDBOGRGeometryConverter>(
351 9 : FileGDBOGRGeometryConverter::BuildConverter(poGeomField));
352 22 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
353 : {
354 13 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
355 13 : if (iCurFeat < 0)
356 0 : break;
357 13 : const OGRField *psField = GetFieldValue(m_iGeomField);
358 13 : if (psField != nullptr)
359 : {
360 : auto poGeom = std::unique_ptr<OGRGeometry>(
361 18 : poGeomConverter->GetAsGeometry(psField));
362 18 : if (poGeom != nullptr &&
363 9 : wkbFlatten(poGeom->getGeometryType()) == wkbMultiPoint)
364 : {
365 9 : nValid += poGeom->toMultiPoint()->getNumGeometries();
366 : }
367 : }
368 : }
369 9 : if (nValid > 0)
370 : {
371 : const double dfArea =
372 9 : (poGeomField->GetXMax() - poGeomField->GetXMin()) *
373 9 : (poGeomField->GetYMax() - poGeomField->GetYMin());
374 9 : if (dfArea != 0)
375 : {
376 4 : m_adfSpatialIndexGridResolution[0] = sqrt(dfArea / nValid);
377 : }
378 5 : else if (poGeomField->GetXMax() > poGeomField->GetXMin())
379 : {
380 0 : m_adfSpatialIndexGridResolution[0] =
381 0 : (poGeomField->GetXMax() - poGeomField->GetXMin()) / nValid;
382 : }
383 5 : else if (poGeomField->GetYMax() > poGeomField->GetYMin())
384 : {
385 0 : m_adfSpatialIndexGridResolution[0] =
386 0 : (poGeomField->GetYMax() - poGeomField->GetYMin()) / nValid;
387 : }
388 : else
389 : {
390 5 : return;
391 : }
392 4 : m_bDirtyGeomFieldSpatialIndexGridRes = true;
393 : poGeomField->m_adfSpatialIndexGridResolution =
394 4 : m_adfSpatialIndexGridResolution;
395 : }
396 : }
397 :
398 : else
399 : {
400 72 : CPLDebug("OpenFileGDB", "Computing optimal grid size...");
401 :
402 : // For other types of geometries, just take the maximum extent along x/y
403 : // of all geometries
404 72 : double dfMaxSize = 0;
405 72 : OGREnvelope sEnvelope;
406 182 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
407 : {
408 110 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
409 110 : if (iCurFeat < 0)
410 0 : break;
411 110 : const OGRField *psField = GetFieldValue(m_iGeomField);
412 110 : if (psField != nullptr)
413 : {
414 87 : if (GetFeatureExtent(psField, &sEnvelope))
415 : {
416 87 : dfMaxSize =
417 87 : std::max(dfMaxSize, sEnvelope.MaxX - sEnvelope.MinX);
418 87 : dfMaxSize =
419 87 : std::max(dfMaxSize, sEnvelope.MaxY - sEnvelope.MinY);
420 : }
421 : }
422 : }
423 72 : CPLDebug("OpenFileGDB", "Optimal grid size = %f", dfMaxSize);
424 :
425 72 : if (dfMaxSize > 0)
426 : {
427 58 : m_bDirtyGeomFieldSpatialIndexGridRes = true;
428 58 : m_adfSpatialIndexGridResolution[0] = dfMaxSize;
429 : poGeomField->m_adfSpatialIndexGridResolution =
430 58 : m_adfSpatialIndexGridResolution;
431 : }
432 : }
433 : }
434 :
435 : /************************************************************************/
436 : /* WriteIndex() */
437 : /************************************************************************/
438 :
439 : template <class ValueOIDPair>
440 114 : static bool WriteIndex(
441 : VSILFILE *fp, std::vector<ValueOIDPair> &asValues,
442 : void (*writeValueFunc)(std::vector<GByte> &abyPage,
443 : const typename ValueOIDPair::first_type &value,
444 : int maxStrSize),
445 : int &nDepth, int maxStrSize = 0)
446 : {
447 114 : constexpr int IDX_PAGE_SIZE = 4096;
448 114 : constexpr int HEADER_SIZE_PAGE_REFERENCING_FEATURES = 12; // 3 * int32
449 114 : constexpr int SIZEOF_FEATURE_ID = 4; // sizeof(int)
450 114 : const int SIZEOF_INDEXED_VALUE =
451 4 : maxStrSize ? sizeof(uint16_t) * maxStrSize
452 : : sizeof(typename ValueOIDPair::first_type);
453 114 : const int NUM_MAX_FEATURES_PER_PAGE =
454 : (IDX_PAGE_SIZE - HEADER_SIZE_PAGE_REFERENCING_FEATURES) /
455 114 : (SIZEOF_FEATURE_ID + SIZEOF_INDEXED_VALUE);
456 : // static_assert(NUM_MAX_FEATURES_PER_PAGE == 340,
457 : // "NUM_MAX_FEATURES_PER_PAGE == 340");
458 114 : const int OFFSET_FIRST_VAL_IN_PAGE =
459 114 : HEADER_SIZE_PAGE_REFERENCING_FEATURES +
460 : NUM_MAX_FEATURES_PER_PAGE * SIZEOF_FEATURE_ID;
461 :
462 : // Configurable only for debugging & autotest purposes
463 228 : const int numMaxFeaturesPerPage = [NUM_MAX_FEATURES_PER_PAGE]()
464 : {
465 114 : const int nVal = atoi(
466 : CPLGetConfigOption("OPENFILEGDB_MAX_FEATURES_PER_SPX_PAGE",
467 : CPLSPrintf("%d", NUM_MAX_FEATURES_PER_PAGE)));
468 114 : if (nVal < 2)
469 0 : return 2;
470 114 : if (nVal > NUM_MAX_FEATURES_PER_PAGE)
471 0 : return NUM_MAX_FEATURES_PER_PAGE;
472 114 : return nVal;
473 114 : }();
474 :
475 228 : if (asValues.size() > static_cast<size_t>(INT_MAX) ||
476 : // Maximum number of values for depth == 4: this evaluates to ~ 13
477 : // billion values (~ features)
478 114 : asValues.size() > (((static_cast<uint64_t>(numMaxFeaturesPerPage) + 1) *
479 114 : numMaxFeaturesPerPage +
480 114 : 1) *
481 114 : numMaxFeaturesPerPage +
482 114 : 1) *
483 114 : numMaxFeaturesPerPage)
484 : {
485 1 : CPLError(CE_Failure, CPLE_NotSupported,
486 : "More values in spatial index than can be handled");
487 1 : return false;
488 : }
489 :
490 : // Sort by ascending values, and for same value by ascending OID
491 113 : std::sort(asValues.begin(), asValues.end(),
492 45468 : [](const ValueOIDPair &a, const ValueOIDPair &b) {
493 62584 : return a.first < b.first ||
494 62584 : (a.first == b.first && a.second < b.second);
495 : });
496 :
497 113 : bool bRet = true;
498 226 : std::vector<GByte> abyPage;
499 113 : abyPage.reserve(IDX_PAGE_SIZE);
500 :
501 113 : const auto WriteRootPageNonLeaf =
502 240 : [=, &bRet, &asValues, &abyPage](int nNumDirectChildren,
503 : int nSubPageIdxToFeatIdxMultiplier)
504 : {
505 : // Write root page (level 1)
506 18 : WriteUInt32(abyPage, 0); // id of next page at same level
507 36 : WriteUInt32(abyPage,
508 18 : nNumDirectChildren == 1 ? 1 : nNumDirectChildren - 1);
509 :
510 68 : for (int i = 0; i < nNumDirectChildren; i++)
511 : {
512 50 : WriteUInt32(abyPage, 2 + i); // id of subpage
513 : }
514 :
515 : // Add padding
516 18 : abyPage.resize(OFFSET_FIRST_VAL_IN_PAGE);
517 :
518 18 : if (nNumDirectChildren == 1)
519 : {
520 : // Should only happen if OPENFILEGDB_FORCE_SPX_DEPTH is forced
521 0 : writeValueFunc(abyPage, asValues.back().first, maxStrSize);
522 : }
523 : else
524 : {
525 50 : for (int i = 0; i < nNumDirectChildren - 1; i++)
526 : {
527 32 : const int nFeatIdx =
528 32 : (i + 1) * nSubPageIdxToFeatIdxMultiplier - 1;
529 32 : writeValueFunc(abyPage, asValues[nFeatIdx].first, maxStrSize);
530 : }
531 : }
532 18 : abyPage.resize(IDX_PAGE_SIZE);
533 18 : bRet &= VSIFWriteL(abyPage.data(), abyPage.size(), 1, fp) == 1;
534 : };
535 :
536 13307 : const auto WriteLeafPages = [=, &bRet, &asValues, &abyPage](
537 : int pageBaseOffset, int nNumFeaturePages)
538 : {
539 : // Write leaf pages
540 128 : for (int i = 0; i < nNumFeaturePages; ++i)
541 : {
542 110 : abyPage.clear();
543 110 : int nNumFeaturesInPage = numMaxFeaturesPerPage;
544 110 : if (i + 1 < nNumFeaturePages)
545 : {
546 92 : WriteUInt32(abyPage, pageBaseOffset + i +
547 : 1); // id of next page at same level
548 : }
549 : else
550 : {
551 18 : WriteUInt32(abyPage, 0);
552 18 : nNumFeaturesInPage = static_cast<int>(asValues.size()) -
553 18 : i * numMaxFeaturesPerPage;
554 : }
555 110 : CPLAssert(nNumFeaturesInPage > 0 &&
556 : nNumFeaturesInPage <= NUM_MAX_FEATURES_PER_PAGE);
557 110 : WriteUInt32(abyPage, nNumFeaturesInPage);
558 110 : WriteUInt32(abyPage, 0); // unknown semantics
559 :
560 : // Write features' ID
561 3143 : for (int j = 0; j < nNumFeaturesInPage; j++)
562 : {
563 3033 : WriteUInt32(
564 : abyPage,
565 : static_cast<uint32_t>(
566 3033 : asValues[i * numMaxFeaturesPerPage + j].second));
567 : }
568 :
569 : // Add padding
570 110 : abyPage.resize(OFFSET_FIRST_VAL_IN_PAGE);
571 :
572 : // Write features' spatial index value
573 3143 : for (int j = 0; j < nNumFeaturesInPage; j++)
574 : {
575 3033 : writeValueFunc(abyPage,
576 3033 : asValues[i * numMaxFeaturesPerPage + j].first,
577 : maxStrSize);
578 : }
579 :
580 110 : abyPage.resize(IDX_PAGE_SIZE);
581 110 : bRet &= VSIFWriteL(abyPage.data(), abyPage.size(), 1, fp) == 1;
582 : }
583 : };
584 :
585 113 : const auto WriteIntermediatePages =
586 804 : [=, &bRet, &asValues,
587 : &abyPage](int pageBaseOffset, int nNumPagesThisLevel,
588 : int nNumPagesNextLevel, int nSubPageIdxToFeatIdxMultiplier)
589 : {
590 68 : for (int i = 0; i < nNumPagesThisLevel; ++i)
591 : {
592 52 : abyPage.clear();
593 52 : int nNumItemsInPage = numMaxFeaturesPerPage;
594 52 : if (i + 1 < nNumPagesThisLevel)
595 : {
596 36 : WriteUInt32(abyPage, pageBaseOffset + i +
597 : 1); // id of next page at same level
598 : }
599 : else
600 : {
601 16 : WriteUInt32(abyPage, 0);
602 16 : nNumItemsInPage =
603 16 : nNumPagesNextLevel - i * numMaxFeaturesPerPage;
604 16 : CPLAssert(nNumItemsInPage > 1 &&
605 : nNumItemsInPage <= NUM_MAX_FEATURES_PER_PAGE + 1);
606 16 : nNumItemsInPage--;
607 : }
608 52 : CPLAssert(nNumItemsInPage > 0 &&
609 : nNumItemsInPage <= NUM_MAX_FEATURES_PER_PAGE);
610 52 : WriteUInt32(abyPage, nNumItemsInPage);
611 :
612 : // Write subpages' ID
613 200 : for (int j = 0; j < 1 + nNumItemsInPage; j++)
614 : {
615 148 : WriteUInt32(abyPage, pageBaseOffset + nNumPagesThisLevel +
616 148 : i * numMaxFeaturesPerPage + j);
617 : }
618 :
619 : // Add padding
620 52 : abyPage.resize(OFFSET_FIRST_VAL_IN_PAGE);
621 :
622 : // Write features' spatial index value
623 148 : for (int j = 0; j < nNumItemsInPage; j++)
624 : {
625 96 : const int nFeatIdx = (i * numMaxFeaturesPerPage + j + 1) *
626 : nSubPageIdxToFeatIdxMultiplier -
627 : 1;
628 96 : writeValueFunc(abyPage, asValues[nFeatIdx].first, maxStrSize);
629 : }
630 :
631 52 : abyPage.resize(IDX_PAGE_SIZE);
632 52 : bRet &= VSIFWriteL(abyPage.data(), abyPage.size(), 1, fp) == 1;
633 : }
634 : };
635 :
636 113 : const auto WriteLastTwoLevelPages =
637 24 : [numMaxFeaturesPerPage, WriteIntermediatePages,
638 : WriteLeafPages](int pageBaseOffset, int nNumPagesBeforeLastLevel,
639 : int nNumFeaturePages)
640 : {
641 : // Write pages at level depth-1 (referencing pages of level depth)
642 12 : WriteIntermediatePages(pageBaseOffset, nNumPagesBeforeLastLevel,
643 : nNumFeaturePages, numMaxFeaturesPerPage);
644 :
645 : // Write leaf pages
646 12 : WriteLeafPages(pageBaseOffset + nNumPagesBeforeLastLevel,
647 : nNumFeaturePages);
648 : };
649 :
650 221 : if (asValues.empty() || nDepth == 1 ||
651 108 : (nDepth == 0 &&
652 108 : static_cast<int>(asValues.size()) <= numMaxFeaturesPerPage))
653 : {
654 95 : nDepth = 1;
655 :
656 95 : WriteUInt32(abyPage, 0); // id of next page
657 95 : WriteUInt32(abyPage, static_cast<uint32_t>(asValues.size()));
658 95 : WriteUInt32(abyPage, 0); // unknown semantics
659 :
660 : // Write features' ID
661 1019 : for (const auto &pair : asValues)
662 924 : WriteUInt32(abyPage, static_cast<uint32_t>(pair.second));
663 :
664 : // Add padding
665 95 : abyPage.resize(OFFSET_FIRST_VAL_IN_PAGE);
666 :
667 : // Write features' spatial index value
668 1019 : for (const auto &pair : asValues)
669 924 : writeValueFunc(abyPage, pair.first, maxStrSize);
670 :
671 95 : abyPage.resize(IDX_PAGE_SIZE);
672 95 : bRet &= VSIFWriteL(abyPage.data(), abyPage.size(), 1, fp) == 1;
673 : }
674 36 : else if (nDepth == 2 || (nDepth == 0 && static_cast<int>(asValues.size()) <=
675 18 : (numMaxFeaturesPerPage + 1) *
676 : numMaxFeaturesPerPage))
677 : {
678 6 : nDepth = 2;
679 :
680 18 : const int nNumFeaturePages = static_cast<int>(
681 6 : DIV_ROUND_UP(asValues.size(), numMaxFeaturesPerPage));
682 6 : CPLAssert(nNumFeaturePages - 1 <= NUM_MAX_FEATURES_PER_PAGE);
683 :
684 : // Write root page (level 1)
685 6 : WriteRootPageNonLeaf(nNumFeaturePages, numMaxFeaturesPerPage);
686 :
687 : // Write leaf pages (level 2)
688 6 : WriteLeafPages(2, nNumFeaturePages);
689 : }
690 24 : else if (nDepth == 3 ||
691 12 : (nDepth == 0 &&
692 12 : static_cast<int>(asValues.size()) <=
693 12 : ((numMaxFeaturesPerPage + 1) * numMaxFeaturesPerPage + 1) *
694 : numMaxFeaturesPerPage))
695 : {
696 8 : nDepth = 3;
697 :
698 : // imagine simpler case: NUM_MAX_FEATURES_PER_PAGE = 2 and 9 values
699 : // ==> nNumFeaturePages = ceil(9 / 2) = 5
700 : // ==> nNumPagesLevel2 = ceil((5-1) / 2) = 2
701 : // level 1:
702 : // page 1: point to page 2(, 3)
703 : // level 2:
704 : // page 2: point to page 4, 5(, 6)
705 : // page 3: point to page 6, 7(, 8)
706 : // level 3:
707 : // page 4: point to feature 1, 2
708 : // page 5: point to feature 3, 4
709 : // page 6: point to feature 5, 6
710 : // page 7: point to feature 7, 8
711 : // page 8: point to feature 9
712 :
713 : // or NUM_MAX_FEATURES_PER_PAGE = 2 and 11 values
714 : // ==> nNumFeaturePages = ceil(11 / 2) = 6
715 : // ==> nNumPagesLevel2 = ceil((6-1) / 2) = 3
716 : // level 1:
717 : // page 1: point to page 2, 3(, 4)
718 : // level 2:
719 : // page 2: point to page 5, 6(, 7)
720 : // page 3: point to page 7, 8(, 9)
721 : // page 4: point to page 9(, 10)
722 : // level 3:
723 : // page 5: point to feature 1, 2
724 : // page 6: point to feature 3, 4
725 : // page 7: point to feature 5, 6
726 : // page 8: point to feature 7, 8
727 : // page 9: point to feature 9, 10
728 : // page 10: point to feature 11
729 :
730 : // or NUM_MAX_FEATURES_PER_PAGE = 2 and 14 values
731 : // ==> nNumFeaturePages = ceil(14 / 2) = 7
732 : // ==> nNumPagesLevel2 = ceil((7-1) / 2) = 3
733 : // level 1:
734 : // page 1: point to page 2, 3(, 4)
735 : // level 2:
736 : // page 2: point to page 5, 6(, 7)
737 : // page 3: point to page 7, 8(, 9)
738 : // page 4: point to page 9, 10(, 11)
739 : // level 3:
740 : // page 5: point to feature 1, 2
741 : // page 6: point to feature 3, 4
742 : // page 7: point to feature 5, 6
743 : // page 8: point to feature 7, 8
744 : // page 9: point to feature 9, 10
745 : // page 10: point to feature 11, 12
746 : // page 11: point to feature 13, 14
747 :
748 24 : const int nNumFeaturePages = static_cast<int>(
749 8 : DIV_ROUND_UP(asValues.size(), numMaxFeaturesPerPage));
750 16 : const int nNumPagesLevel2 =
751 : nNumFeaturePages == 1
752 : ? 1
753 8 : : DIV_ROUND_UP(nNumFeaturePages - 1, numMaxFeaturesPerPage);
754 8 : CPLAssert(nNumPagesLevel2 - 1 <= NUM_MAX_FEATURES_PER_PAGE);
755 :
756 : // Write root page (level 1)
757 8 : WriteRootPageNonLeaf(nNumPagesLevel2,
758 : numMaxFeaturesPerPage * numMaxFeaturesPerPage);
759 :
760 : // Write level 2 and level 3 pages
761 8 : WriteLastTwoLevelPages(2, nNumPagesLevel2, nNumFeaturePages);
762 : }
763 : else
764 : {
765 4 : nDepth = 4;
766 :
767 12 : const int nNumFeaturePages = static_cast<int>(
768 4 : DIV_ROUND_UP(asValues.size(), numMaxFeaturesPerPage));
769 8 : const int nNumPagesLevel3 =
770 : nNumFeaturePages == 1
771 : ? 1
772 4 : : DIV_ROUND_UP(nNumFeaturePages - 1, numMaxFeaturesPerPage);
773 8 : const int nNumPagesLevel2 =
774 : nNumPagesLevel3 == 1
775 : ? 1
776 4 : : DIV_ROUND_UP(nNumPagesLevel3 - 1, numMaxFeaturesPerPage);
777 4 : CPLAssert(nNumPagesLevel2 - 1 <= NUM_MAX_FEATURES_PER_PAGE);
778 :
779 : // Write root page (level 1)
780 4 : WriteRootPageNonLeaf(nNumPagesLevel2, numMaxFeaturesPerPage *
781 : numMaxFeaturesPerPage *
782 : numMaxFeaturesPerPage);
783 :
784 : // Write pages at level 2 (referencing pages of level 3)
785 4 : WriteIntermediatePages(2, nNumPagesLevel2, nNumPagesLevel3,
786 : numMaxFeaturesPerPage * numMaxFeaturesPerPage);
787 :
788 : // Write pages at level 3 and 4
789 4 : WriteLastTwoLevelPages(2 + nNumPagesLevel2, nNumPagesLevel3,
790 : nNumFeaturePages);
791 : }
792 :
793 : // Write trailer
794 113 : std::vector<GByte> abyTrailer;
795 113 : CPLAssert(SIZEOF_INDEXED_VALUE <= 255);
796 113 : WriteUInt8(abyTrailer, static_cast<uint8_t>(SIZEOF_INDEXED_VALUE));
797 113 : WriteUInt8(abyTrailer, maxStrSize ? 0x20 : 0x40); // unknown semantics
798 113 : WriteUInt32(abyTrailer, 1); // unknown semantics
799 113 : WriteUInt32(abyTrailer, nDepth); // index depth
800 113 : WriteUInt32(abyTrailer, static_cast<uint32_t>(asValues.size()));
801 113 : WriteUInt32(abyTrailer, 0); // unknown semantics
802 113 : WriteUInt32(abyTrailer, 1); // unknown semantics
803 113 : bRet &= VSIFWriteL(abyTrailer.data(), abyTrailer.size(), 1, fp) == 1;
804 :
805 113 : return bRet;
806 : }
807 :
808 : /************************************************************************/
809 : /* CreateSpatialIndex() */
810 : /************************************************************************/
811 :
812 151 : bool FileGDBTable::CreateSpatialIndex()
813 : {
814 302 : if (m_iGeomField < 0 || m_adfSpatialIndexGridResolution.empty() ||
815 151 : m_adfSpatialIndexGridResolution.size() > 3)
816 : {
817 0 : return false;
818 : }
819 :
820 151 : if (m_eTableGeomType == FGTGT_MULTIPATCH)
821 : {
822 0 : CPLError(CE_Failure, CPLE_NotSupported,
823 : "Multipatch not supported for spatial index generation");
824 0 : return false;
825 : }
826 :
827 : auto poGeomField =
828 151 : cpl::down_cast<FileGDBGeomField *>(m_apoFields[m_iGeomField].get());
829 151 : if (m_adfSpatialIndexGridResolution.size() == 1)
830 : {
831 : // Debug only
832 : const char *pszGridSize =
833 151 : CPLGetConfigOption("OPENFILEGDB_GRID_SIZE", nullptr);
834 151 : if (pszGridSize)
835 : {
836 0 : m_bDirtyGeomFieldSpatialIndexGridRes = true;
837 0 : m_adfSpatialIndexGridResolution[0] = CPLAtof(pszGridSize);
838 : poGeomField->m_adfSpatialIndexGridResolution =
839 0 : m_adfSpatialIndexGridResolution;
840 : }
841 : else
842 : {
843 151 : ComputeOptimalSpatialIndexGridResolution();
844 151 : if (m_adfSpatialIndexGridResolution[0] == 0)
845 55 : return false;
846 : }
847 : }
848 : auto poGeomConverter = std::unique_ptr<FileGDBOGRGeometryConverter>(
849 192 : FileGDBOGRGeometryConverter::BuildConverter(poGeomField));
850 : typedef std::pair<int64_t, int> ValueOIDPair;
851 192 : std::vector<ValueOIDPair> asValues;
852 :
853 96 : const double dfGridStep = m_adfSpatialIndexGridResolution.back();
854 : const double dfShift =
855 96 : (1 << 29) / (dfGridStep / m_adfSpatialIndexGridResolution[0]);
856 :
857 : double dfYMinClamped;
858 : double dfYMaxClamped;
859 96 : GetMinMaxProjYForSpatialIndex(dfYMinClamped, dfYMaxClamped);
860 :
861 : const auto AddPointToIndex =
862 3773 : [this, dfGridStep, dfShift, dfYMinClamped, dfYMaxClamped](
863 7546 : double dfX, double dfY, std::vector<int64_t> &aSetValues)
864 : {
865 3773 : dfY = std::min(std::max(dfY, dfYMinClamped), dfYMaxClamped);
866 :
867 3773 : const double dfXShifted = dfX / dfGridStep + dfShift;
868 3773 : const double dfYShifted = dfY / dfGridStep + dfShift;
869 : // Each value must fit on 31 bit (sign included)
870 7546 : if (std::abs(dfXShifted) < (1 << 30) &&
871 3773 : std::abs(dfYShifted) < (1 << 30))
872 : {
873 3773 : const unsigned nX =
874 3773 : static_cast<unsigned>(static_cast<int>(std::floor(dfXShifted)));
875 3773 : const unsigned nY =
876 3773 : static_cast<unsigned>(static_cast<int>(std::floor(dfYShifted)));
877 : const uint64_t nVal =
878 3773 : ((static_cast<uint64_t>(m_adfSpatialIndexGridResolution.size() -
879 : 1))
880 3773 : << 62) |
881 3773 : ((static_cast<uint64_t>(nX)) << 31) | nY;
882 3773 : aSetValues.push_back(static_cast<int64_t>(nVal));
883 3773 : return true;
884 : }
885 0 : return false;
886 96 : };
887 :
888 : // Adapted from GDALdllImageLineAllTouched() of alg/llrasterize.cpp
889 : const auto AddLineStringToIndex =
890 94 : [this, dfGridStep, dfShift, dfYMinClamped, dfYMaxClamped](
891 6327 : const OGRLineString *poLS, std::vector<int64_t> &aSetValues)
892 : {
893 94 : const int nNumPoints = poLS->getNumPoints();
894 94 : if (nNumPoints < 2)
895 0 : return;
896 94 : OGREnvelope sEnvelope;
897 94 : poLS->getEnvelope(&sEnvelope);
898 94 : double dfYShift = 0;
899 94 : if (sEnvelope.MaxY > dfYMaxClamped)
900 10 : dfYShift = dfYMaxClamped - sEnvelope.MaxY;
901 84 : else if (sEnvelope.MinY < dfYMinClamped)
902 0 : dfYShift = dfYMinClamped - sEnvelope.MinY;
903 1295 : for (int i = 0; i < nNumPoints - 1; i++)
904 : {
905 1201 : double dfX = poLS->getX(i) / dfGridStep + dfShift;
906 1201 : double dfY = (poLS->getY(i) + dfYShift) / dfGridStep + dfShift;
907 1201 : double dfXEnd = poLS->getX(i + 1) / dfGridStep + dfShift;
908 : double dfYEnd =
909 1201 : (poLS->getY(i + 1) + dfYShift) / dfGridStep + dfShift;
910 2402 : if (!(std::abs(dfX) < (1 << 30) && std::abs(dfY) < (1 << 30) &&
911 1201 : std::abs(dfXEnd) < (1 << 30) && std::abs(dfYEnd) < (1 << 30)))
912 : {
913 0 : return;
914 : }
915 :
916 : // Swap if needed so we can proceed from left2right (X increasing)
917 1201 : if (dfX > dfXEnd)
918 : {
919 402 : std::swap(dfX, dfXEnd);
920 402 : std::swap(dfY, dfYEnd);
921 : }
922 :
923 : // Special case for vertical lines.
924 1201 : if (floor(dfX) == floor(dfXEnd) || fabs(dfX - dfXEnd) < .01)
925 : {
926 1099 : if (dfYEnd < dfY)
927 : {
928 480 : std::swap(dfY, dfYEnd);
929 : }
930 :
931 1099 : const int iX = static_cast<int>(floor(dfXEnd));
932 1099 : int iY = static_cast<int>(floor(dfY));
933 1099 : int iYEnd = static_cast<int>(floor(dfYEnd));
934 :
935 2246 : for (; iY <= iYEnd; iY++)
936 : {
937 1147 : const unsigned nX = static_cast<unsigned>(iX);
938 1147 : const unsigned nY = static_cast<unsigned>(iY);
939 : const uint64_t nVal =
940 : ((static_cast<uint64_t>(
941 1147 : m_adfSpatialIndexGridResolution.size() - 1))
942 1147 : << 62) |
943 1147 : ((static_cast<uint64_t>(nX)) << 31) | nY;
944 1147 : aSetValues.push_back(static_cast<int64_t>(nVal));
945 : }
946 :
947 1169 : continue; // Next segment.
948 : }
949 :
950 : // Special case for horizontal lines.
951 102 : if (floor(dfY) == floor(dfYEnd) || fabs(dfY - dfYEnd) < .01)
952 : {
953 70 : if (dfXEnd < dfX)
954 : {
955 0 : std::swap(dfX, dfXEnd);
956 : }
957 :
958 70 : int iX = static_cast<int>(floor(dfX));
959 70 : const int iY = static_cast<int>(floor(dfY));
960 70 : int iXEnd = static_cast<int>(floor(dfXEnd));
961 :
962 210 : for (; iX <= iXEnd; iX++)
963 : {
964 140 : const unsigned nX = static_cast<unsigned>(iX);
965 140 : const unsigned nY = static_cast<unsigned>(iY);
966 : const uint64_t nVal =
967 : ((static_cast<uint64_t>(
968 140 : m_adfSpatialIndexGridResolution.size() - 1))
969 140 : << 62) |
970 140 : ((static_cast<uint64_t>(nX)) << 31) | nY;
971 140 : aSetValues.push_back(static_cast<int64_t>(nVal));
972 : }
973 :
974 70 : continue; // Next segment.
975 : }
976 :
977 : /* --------------------------------------------------------------------
978 : */
979 : /* General case - left to right sloped. */
980 : /* --------------------------------------------------------------------
981 : */
982 :
983 : // Recenter coordinates to avoid numeric precision issues
984 : // particularly the tests against a small epsilon below that could
985 : // lead to infinite looping otherwise.
986 32 : const int nXShift = static_cast<int>(floor(dfX));
987 32 : const int nYShift = static_cast<int>(floor(dfY));
988 32 : dfX -= nXShift;
989 32 : dfY -= nYShift;
990 32 : dfXEnd -= nXShift;
991 32 : dfYEnd -= nYShift;
992 :
993 32 : const double dfSlope = (dfYEnd - dfY) / (dfXEnd - dfX);
994 :
995 : // Step from pixel to pixel.
996 80 : while (dfX < dfXEnd)
997 : {
998 48 : const int iX = static_cast<int>(floor(dfX));
999 48 : const int iY = static_cast<int>(floor(dfY));
1000 :
1001 : // Burn in the current point.
1002 48 : const unsigned nX = static_cast<unsigned>(iX + nXShift);
1003 48 : const unsigned nY = static_cast<unsigned>(iY + nYShift);
1004 : const uint64_t nVal =
1005 : ((static_cast<uint64_t>(
1006 48 : m_adfSpatialIndexGridResolution.size() - 1))
1007 48 : << 62) |
1008 48 : ((static_cast<uint64_t>(nX)) << 31) | nY;
1009 48 : aSetValues.push_back(static_cast<int64_t>(nVal));
1010 :
1011 48 : double dfStepX = floor(dfX + 1.0) - dfX;
1012 48 : double dfStepY = dfStepX * dfSlope;
1013 :
1014 : // Step to right pixel without changing scanline?
1015 48 : if (static_cast<int>(floor(dfY + dfStepY)) == iY)
1016 : {
1017 8 : dfX += dfStepX;
1018 8 : dfY += dfStepY;
1019 : }
1020 40 : else if (dfSlope < 0)
1021 : {
1022 0 : dfStepY = iY - dfY;
1023 0 : if (dfStepY > -0.000000001)
1024 0 : dfStepY = -0.000000001;
1025 :
1026 0 : dfStepX = dfStepY / dfSlope;
1027 0 : dfX += dfStepX;
1028 0 : dfY += dfStepY;
1029 : }
1030 : else
1031 : {
1032 40 : dfStepY = (iY + 1) - dfY;
1033 40 : if (dfStepY < 0.000000001)
1034 0 : dfStepY = 0.000000001;
1035 :
1036 40 : dfStepX = dfStepY / dfSlope;
1037 40 : dfX += dfStepX;
1038 40 : dfY += dfStepY;
1039 : }
1040 : } // Next step along segment.
1041 : }
1042 96 : };
1043 :
1044 : // Adapted from GDALdllImageFilledPolygon() of alg/llrasterize.cpp
1045 : const auto AddPolygonToIndex =
1046 60 : [this, dfGridStep, dfShift, dfYMinClamped, dfYMaxClamped,
1047 : AddLineStringToIndex](const OGRPolygon *poPoly,
1048 3943 : std::vector<int64_t> &aSetValues)
1049 : {
1050 60 : if (poPoly->IsEmpty())
1051 0 : return;
1052 :
1053 : // Burn contour of exterior ring, because burning the interior
1054 : // can often result in nothing
1055 60 : AddLineStringToIndex(poPoly->getExteriorRing(), aSetValues);
1056 :
1057 60 : OGREnvelope sEnvelope;
1058 60 : poPoly->getEnvelope(&sEnvelope);
1059 :
1060 60 : double dfYShift = 0;
1061 60 : if (sEnvelope.MaxY > dfYMaxClamped)
1062 10 : dfYShift = dfYMaxClamped - sEnvelope.MaxY;
1063 50 : else if (sEnvelope.MinY < dfYMinClamped)
1064 0 : dfYShift = dfYMinClamped - sEnvelope.MinY;
1065 :
1066 60 : const int miny = static_cast<int>(
1067 60 : floor((sEnvelope.MinY + dfYShift) / dfGridStep + dfShift));
1068 60 : const int maxy = static_cast<int>(
1069 60 : floor((sEnvelope.MaxY + dfYShift) / dfGridStep + dfShift));
1070 120 : std::vector<double> intersections;
1071 :
1072 : // Burn interior of polygon
1073 150 : for (int iY = miny; iY <= maxy; iY++)
1074 : {
1075 90 : const double dy = iY + 0.5;
1076 90 : intersections.clear();
1077 199 : for (const auto *poRing : *poPoly)
1078 : {
1079 109 : const int nNumPoints = poRing->getNumPoints();
1080 1878 : for (int i = 0; i < nNumPoints - 1; ++i)
1081 : {
1082 : double dy1 =
1083 1769 : (poRing->getY(i) + dfYShift) / dfGridStep + dfShift;
1084 : double dy2 =
1085 1769 : (poRing->getY(i + 1) + dfYShift) / dfGridStep + dfShift;
1086 1769 : if ((dy1 < dy && dy2 < dy) || (dy1 > dy && dy2 > dy))
1087 1687 : continue;
1088 :
1089 84 : double dx1 = 0.0;
1090 84 : double dx2 = 0.0;
1091 84 : if (dy1 < dy2)
1092 : {
1093 40 : dx1 = poRing->getX(i) / dfGridStep + dfShift;
1094 40 : dx2 = poRing->getX(i + 1) / dfGridStep + dfShift;
1095 : }
1096 44 : else if (dy1 > dy2)
1097 : {
1098 42 : std::swap(dy1, dy2);
1099 42 : dx2 = poRing->getX(i) / dfGridStep + dfShift;
1100 42 : dx1 = poRing->getX(i + 1) / dfGridStep + dfShift;
1101 : }
1102 : else // if( fabs(dy1-dy2) < 1.e-6 )
1103 : {
1104 2 : const int iX1 = static_cast<int>(floor(
1105 2 : std::min(poRing->getX(i), poRing->getX(i + 1)) /
1106 : dfGridStep +
1107 2 : dfShift));
1108 2 : const int iX2 = static_cast<int>(floor(
1109 2 : std::max(poRing->getX(i), poRing->getX(i + 1)) /
1110 : dfGridStep +
1111 2 : dfShift));
1112 :
1113 : // Fill the horizontal segment (separately from the
1114 : // rest).
1115 6 : for (int iX = iX1; iX <= iX2; ++iX)
1116 : {
1117 4 : const unsigned nX = static_cast<unsigned>(iX);
1118 4 : const unsigned nY = static_cast<unsigned>(iY);
1119 : const uint64_t nVal =
1120 : ((static_cast<uint64_t>(
1121 4 : m_adfSpatialIndexGridResolution.size() -
1122 : 1))
1123 4 : << 62) |
1124 4 : ((static_cast<uint64_t>(nX)) << 31) | nY;
1125 4 : aSetValues.push_back(static_cast<int64_t>(nVal));
1126 : }
1127 2 : continue;
1128 : }
1129 :
1130 82 : if (dy < dy2 && dy >= dy1)
1131 : {
1132 78 : const double intersect =
1133 78 : (dy - dy1) * (dx2 - dx1) / (dy2 - dy1) + dx1;
1134 78 : intersections.emplace_back(intersect);
1135 : }
1136 : }
1137 : }
1138 :
1139 90 : std::sort(intersections.begin(), intersections.end());
1140 :
1141 129 : for (size_t i = 0; i + 1 < intersections.size(); i += 2)
1142 : {
1143 39 : const int iX1 = static_cast<int>(floor(intersections[i]));
1144 39 : const int iX2 = static_cast<int>(floor(intersections[i + 1]));
1145 :
1146 92 : for (int iX = iX1; iX <= iX2; ++iX)
1147 : {
1148 53 : const unsigned nX = static_cast<unsigned>(iX);
1149 53 : const unsigned nY = static_cast<unsigned>(iY);
1150 : const uint64_t nVal =
1151 : ((static_cast<uint64_t>(
1152 53 : m_adfSpatialIndexGridResolution.size() - 1))
1153 53 : << 62) |
1154 53 : ((static_cast<uint64_t>(nX)) << 31) | nY;
1155 53 : aSetValues.push_back(static_cast<int64_t>(nVal));
1156 : }
1157 : }
1158 : }
1159 96 : };
1160 :
1161 192 : std::vector<int64_t> aSetValues;
1162 96 : int iLastReported = 0;
1163 96 : const auto nReportIncrement = m_nTotalRecordCount / 20;
1164 : try
1165 : {
1166 3967 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
1167 : {
1168 3871 : if (m_nTotalRecordCount > 10000 &&
1169 0 : (iCurFeat + 1 == m_nTotalRecordCount ||
1170 0 : iCurFeat - iLastReported >= nReportIncrement))
1171 : {
1172 0 : CPLDebug("OpenFileGDB", "Spatial index building: %02.2f %%",
1173 0 : 100 * double(iCurFeat + 1) /
1174 0 : double(m_nTotalRecordCount));
1175 0 : iLastReported = iCurFeat;
1176 : }
1177 3871 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
1178 3871 : if (iCurFeat < 0)
1179 0 : break;
1180 3871 : const OGRField *psField = GetFieldValue(m_iGeomField);
1181 3871 : if (psField != nullptr)
1182 : {
1183 : auto poGeom = std::unique_ptr<OGRGeometry>(
1184 7692 : poGeomConverter->GetAsGeometry(psField));
1185 3846 : if (poGeom != nullptr && !poGeom->IsEmpty())
1186 : {
1187 3842 : aSetValues.clear();
1188 : const auto eGeomType =
1189 3842 : wkbFlatten(poGeom->getGeometryType());
1190 3842 : if (eGeomType == wkbPoint)
1191 : {
1192 3761 : const auto poPoint = poGeom->toPoint();
1193 3761 : AddPointToIndex(poPoint->getX(), poPoint->getY(),
1194 : aSetValues);
1195 : }
1196 81 : else if (eGeomType == wkbMultiPoint)
1197 : {
1198 16 : for (const auto poPoint : *(poGeom->toMultiPoint()))
1199 : {
1200 12 : AddPointToIndex(poPoint->getX(), poPoint->getY(),
1201 : aSetValues);
1202 : }
1203 : }
1204 77 : else if (eGeomType == wkbLineString)
1205 : {
1206 15 : AddLineStringToIndex(poGeom->toLineString(),
1207 : aSetValues);
1208 : }
1209 62 : else if (eGeomType == wkbMultiLineString)
1210 : {
1211 18 : for (const auto poLS : *(poGeom->toMultiLineString()))
1212 : {
1213 12 : AddLineStringToIndex(poLS, aSetValues);
1214 : }
1215 : }
1216 56 : else if (eGeomType == wkbCircularString ||
1217 : eGeomType == wkbCompoundCurve)
1218 : {
1219 4 : poGeom.reset(poGeom->getLinearGeometry());
1220 4 : if (poGeom)
1221 4 : AddLineStringToIndex(poGeom->toLineString(),
1222 : aSetValues);
1223 : }
1224 52 : else if (eGeomType == wkbMultiCurve)
1225 : {
1226 1 : poGeom.reset(poGeom->getLinearGeometry());
1227 1 : if (poGeom)
1228 : {
1229 3 : for (const auto poLS :
1230 4 : *(poGeom->toMultiLineString()))
1231 : {
1232 3 : AddLineStringToIndex(poLS, aSetValues);
1233 : }
1234 : }
1235 : }
1236 51 : else if (eGeomType == wkbPolygon)
1237 : {
1238 36 : AddPolygonToIndex(poGeom->toPolygon(), aSetValues);
1239 : }
1240 15 : else if (eGeomType == wkbCurvePolygon)
1241 : {
1242 6 : poGeom.reset(poGeom->getLinearGeometry());
1243 6 : if (poGeom)
1244 6 : AddPolygonToIndex(poGeom->toPolygon(), aSetValues);
1245 : }
1246 9 : else if (eGeomType == wkbMultiPolygon)
1247 : {
1248 24 : for (const auto poPoly : *(poGeom->toMultiPolygon()))
1249 : {
1250 16 : AddPolygonToIndex(poPoly, aSetValues);
1251 : }
1252 : }
1253 1 : else if (eGeomType == wkbMultiSurface)
1254 : {
1255 1 : poGeom.reset(poGeom->getLinearGeometry());
1256 1 : if (poGeom)
1257 : {
1258 2 : for (const auto poPoly :
1259 3 : *(poGeom->toMultiPolygon()))
1260 : {
1261 2 : AddPolygonToIndex(poPoly, aSetValues);
1262 : }
1263 : }
1264 : }
1265 :
1266 3842 : std::sort(aSetValues.begin(), aSetValues.end());
1267 :
1268 3842 : int64_t nLastVal = std::numeric_limits<int64_t>::min();
1269 9007 : for (auto nVal : aSetValues)
1270 : {
1271 5165 : if (nVal != nLastVal)
1272 : {
1273 3959 : asValues.push_back(
1274 3959 : ValueOIDPair(nVal, iCurFeat + 1));
1275 3959 : nLastVal = nVal;
1276 : }
1277 : }
1278 : }
1279 : }
1280 : }
1281 : }
1282 0 : catch (const std::exception &e)
1283 : {
1284 0 : CPLError(CE_Failure, CPLE_OutOfMemory, "%s", e.what());
1285 0 : return false;
1286 : }
1287 :
1288 : const std::string osSPXFilename(
1289 192 : CPLResetExtension(m_osFilename.c_str(), "spx"));
1290 96 : VSILFILE *fp = VSIFOpenL(osSPXFilename.c_str(), "wb");
1291 96 : if (fp == nullptr)
1292 0 : return false;
1293 :
1294 : // Configurable only for debugging purposes
1295 96 : int nDepth = atoi(CPLGetConfigOption("OPENFILEGDB_FORCE_SPX_DEPTH", "0"));
1296 :
1297 96 : const auto writeValueFunc =
1298 4056 : +[](std::vector<GByte> &abyPage,
1299 : const typename ValueOIDPair::first_type &nval, int /* maxStrSize */)
1300 4056 : { WriteUInt64(abyPage, static_cast<uint64_t>(nval)); };
1301 :
1302 96 : bool bRet = WriteIndex(fp, asValues, writeValueFunc, nDepth);
1303 :
1304 96 : CPLDebug("OpenFileGDB", "Spatial index of depth %d", nDepth);
1305 :
1306 96 : VSIFCloseL(fp);
1307 :
1308 96 : if (!bRet)
1309 : {
1310 1 : CPLError(CE_Failure, CPLE_FileIO, "Write error during .spx generation");
1311 1 : VSIUnlink(osSPXFilename.c_str());
1312 : }
1313 :
1314 96 : return bRet;
1315 : }
1316 :
1317 : /************************************************************************/
1318 : /* CreateAttributeIndex() */
1319 : /************************************************************************/
1320 :
1321 18 : bool FileGDBTable::CreateAttributeIndex(const FileGDBIndex *poIndex)
1322 : {
1323 36 : const std::string osFieldName = poIndex->GetFieldName();
1324 18 : const int iField = GetFieldIdx(osFieldName);
1325 18 : if (iField < 0)
1326 : {
1327 0 : CPLError(CE_Failure, CPLE_AppDefined, "Cannot find field %s",
1328 : osFieldName.c_str());
1329 0 : return false;
1330 : }
1331 :
1332 : const std::string osIdxFilename(CPLResetExtension(
1333 54 : m_osFilename.c_str(), (poIndex->GetIndexName() + ".atx").c_str()));
1334 18 : VSILFILE *fp = VSIFOpenL(osIdxFilename.c_str(), "wb");
1335 18 : if (fp == nullptr)
1336 0 : return false;
1337 :
1338 : bool bRet;
1339 18 : int nDepth = 0;
1340 :
1341 : try
1342 : {
1343 18 : const auto eFieldType = m_apoFields[iField]->GetType();
1344 18 : if (eFieldType == FGFT_INT16)
1345 : {
1346 : typedef std::pair<int16_t, int> ValueOIDPair;
1347 2 : std::vector<ValueOIDPair> asValues;
1348 8 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
1349 : {
1350 6 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
1351 6 : if (iCurFeat < 0)
1352 0 : break;
1353 6 : const OGRField *psField = GetFieldValue(iField);
1354 6 : if (psField != nullptr)
1355 : {
1356 2 : asValues.push_back(ValueOIDPair(
1357 4 : static_cast<int16_t>(psField->Integer), iCurFeat + 1));
1358 : }
1359 : }
1360 :
1361 2 : const auto writeValueFunc =
1362 2 : +[](std::vector<GByte> &abyPage,
1363 : const typename ValueOIDPair::first_type &val,
1364 : int /* maxStrSize */)
1365 2 : { WriteUInt16(abyPage, static_cast<uint16_t>(val)); };
1366 :
1367 2 : bRet = WriteIndex(fp, asValues, writeValueFunc, nDepth);
1368 : }
1369 16 : else if (eFieldType == FGFT_INT32)
1370 : {
1371 : typedef std::pair<int32_t, int> ValueOIDPair;
1372 2 : std::vector<ValueOIDPair> asValues;
1373 8 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
1374 : {
1375 6 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
1376 6 : if (iCurFeat < 0)
1377 0 : break;
1378 6 : const OGRField *psField = GetFieldValue(iField);
1379 6 : if (psField != nullptr)
1380 : {
1381 2 : asValues.push_back(
1382 4 : ValueOIDPair(psField->Integer, iCurFeat + 1));
1383 : }
1384 : }
1385 :
1386 2 : const auto writeValueFunc =
1387 2 : +[](std::vector<GByte> &abyPage,
1388 : const typename ValueOIDPair::first_type &val,
1389 : int /* maxStrSize */)
1390 2 : { WriteUInt32(abyPage, static_cast<uint32_t>(val)); };
1391 :
1392 2 : bRet = WriteIndex(fp, asValues, writeValueFunc, nDepth);
1393 : }
1394 14 : else if (eFieldType == FGFT_INT64)
1395 : {
1396 : typedef std::pair<int64_t, int> ValueOIDPair;
1397 1 : std::vector<ValueOIDPair> asValues;
1398 3 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
1399 : {
1400 2 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
1401 2 : if (iCurFeat < 0)
1402 0 : break;
1403 2 : const OGRField *psField = GetFieldValue(iField);
1404 2 : if (psField != nullptr)
1405 : {
1406 2 : asValues.push_back(
1407 4 : ValueOIDPair(psField->Integer64, iCurFeat + 1));
1408 : }
1409 : }
1410 :
1411 1 : const auto writeValueFunc =
1412 2 : +[](std::vector<GByte> &abyPage,
1413 : const typename ValueOIDPair::first_type &val,
1414 : int /* maxStrSize */)
1415 2 : { WriteUInt64(abyPage, static_cast<uint64_t>(val)); };
1416 :
1417 1 : bRet = WriteIndex(fp, asValues, writeValueFunc, nDepth);
1418 : }
1419 13 : else if (eFieldType == FGFT_FLOAT32)
1420 : {
1421 : typedef std::pair<float, int> ValueOIDPair;
1422 2 : std::vector<ValueOIDPair> asValues;
1423 8 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
1424 : {
1425 6 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
1426 6 : if (iCurFeat < 0)
1427 0 : break;
1428 6 : const OGRField *psField = GetFieldValue(iField);
1429 6 : if (psField != nullptr)
1430 : {
1431 2 : asValues.push_back(ValueOIDPair(
1432 4 : static_cast<float>(psField->Real), iCurFeat + 1));
1433 : }
1434 : }
1435 :
1436 2 : const auto writeValueFunc =
1437 2 : +[](std::vector<GByte> &abyPage,
1438 : const typename ValueOIDPair::first_type &val,
1439 2 : int /* maxStrSize */) { WriteFloat32(abyPage, val); };
1440 :
1441 2 : bRet = WriteIndex(fp, asValues, writeValueFunc, nDepth);
1442 : }
1443 11 : else if (eFieldType == FGFT_FLOAT64 || eFieldType == FGFT_DATETIME ||
1444 6 : eFieldType == FGFT_DATE || eFieldType == FGFT_TIME ||
1445 : eFieldType == FGFT_DATETIME_WITH_OFFSET)
1446 : {
1447 : typedef std::pair<double, int> ValueOIDPair;
1448 7 : std::vector<ValueOIDPair> asValues;
1449 : // Hack to force reading DateTime as double
1450 7 : m_apoFields[iField]->m_bReadAsDouble = true;
1451 28 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
1452 : {
1453 21 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
1454 21 : if (iCurFeat < 0)
1455 0 : break;
1456 21 : const OGRField *psField = GetFieldValue(iField);
1457 21 : if (psField != nullptr)
1458 : {
1459 13 : asValues.push_back(
1460 26 : ValueOIDPair(psField->Real, iCurFeat + 1));
1461 : }
1462 : }
1463 7 : m_apoFields[iField]->m_bReadAsDouble = false;
1464 :
1465 7 : const auto writeValueFunc =
1466 13 : +[](std::vector<GByte> &abyPage,
1467 : const typename ValueOIDPair::first_type &val,
1468 13 : int /* maxStrSize */) { WriteFloat64(abyPage, val); };
1469 :
1470 7 : bRet = WriteIndex(fp, asValues, writeValueFunc, nDepth);
1471 : }
1472 4 : else if (eFieldType == FGFT_STRING)
1473 : {
1474 : typedef std::pair<std::vector<std::uint16_t>, int> ValueOIDPair;
1475 8 : std::vector<ValueOIDPair> asValues;
1476 4 : bRet = true;
1477 : const bool bIsLower =
1478 4 : STARTS_WITH_CI(poIndex->GetExpression().c_str(), "LOWER(");
1479 4 : int maxStrSize = 0;
1480 16 : for (int iCurFeat = 0; iCurFeat < m_nTotalRecordCount; ++iCurFeat)
1481 : {
1482 12 : iCurFeat = GetAndSelectNextNonEmptyRow(iCurFeat);
1483 12 : if (iCurFeat < 0)
1484 0 : break;
1485 12 : const OGRField *psField = GetFieldValue(iField);
1486 12 : if (psField != nullptr)
1487 : {
1488 16 : wchar_t *pWide = CPLRecodeToWChar(
1489 8 : psField->String, CPL_ENC_UTF8, CPL_ENC_UCS2);
1490 8 : if (pWide == nullptr)
1491 : {
1492 0 : bRet = false;
1493 0 : break;
1494 : }
1495 8 : int nCount = 0;
1496 8 : std::vector<std::uint16_t> asUTF16Str;
1497 352 : while (nCount < MAX_CAR_COUNT_INDEXED_STR &&
1498 348 : pWide[nCount] != 0)
1499 : {
1500 344 : nCount++;
1501 : }
1502 8 : if (nCount > maxStrSize)
1503 6 : maxStrSize = nCount;
1504 8 : asUTF16Str.reserve(nCount);
1505 352 : for (int i = 0; i < nCount; ++i)
1506 : {
1507 344 : if (bIsLower && pWide[i] >= 'A' && pWide[i] <= 'Z')
1508 10 : asUTF16Str.push_back(
1509 10 : static_cast<uint16_t>(pWide[i] + ('a' - 'A')));
1510 : else
1511 334 : asUTF16Str.push_back(
1512 334 : static_cast<uint16_t>(pWide[i]));
1513 : }
1514 8 : CPLFree(pWide);
1515 :
1516 8 : asValues.push_back(ValueOIDPair(asUTF16Str, iCurFeat + 1));
1517 : }
1518 : }
1519 4 : if (maxStrSize < MAX_CAR_COUNT_INDEXED_STR)
1520 2 : maxStrSize++;
1521 :
1522 4 : const auto writeValueFunc =
1523 8 : +[](std::vector<GByte> &abyPage,
1524 : const typename ValueOIDPair::first_type &val,
1525 : int l_maxStrSize)
1526 : {
1527 352 : for (size_t i = 0; i < val.size(); ++i)
1528 344 : WriteUInt16(abyPage, val[i]);
1529 158 : for (size_t i = val.size();
1530 158 : i < static_cast<size_t>(l_maxStrSize); ++i)
1531 150 : WriteUInt16(abyPage, 32); // space
1532 8 : };
1533 :
1534 4 : if (bRet)
1535 : {
1536 4 : bRet = WriteIndex(fp, asValues, writeValueFunc, nDepth,
1537 : maxStrSize);
1538 : }
1539 : }
1540 : else
1541 : {
1542 0 : CPLError(CE_Failure, CPLE_AppDefined,
1543 : "CreateAttributeIndex(%s): "
1544 : "Unsupported field type for index creation",
1545 : osFieldName.c_str());
1546 0 : bRet = false;
1547 : }
1548 : }
1549 0 : catch (const std::exception &e)
1550 : {
1551 0 : CPLError(CE_Failure, CPLE_OutOfMemory, "%s", e.what());
1552 0 : bRet = false;
1553 : }
1554 :
1555 18 : VSIFCloseL(fp);
1556 :
1557 18 : if (!bRet)
1558 : {
1559 0 : CPLError(CE_Failure, CPLE_FileIO, "Write error during %s generation",
1560 : osIdxFilename.c_str());
1561 0 : VSIUnlink(osIdxFilename.c_str());
1562 : }
1563 :
1564 18 : return bRet;
1565 : }
1566 :
1567 : } /* namespace OpenFileGDB */
|