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