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