diff --git a/CHANGELOG.md b/CHANGELOG.md index d29dd51d9..d60ee4241 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -6,6 +6,9 @@ The public API of this library consists of the functions declared in file [h3api.h.in](./src/h3lib/include/h3api.h.in). ## [Unreleased] +### Fixed +- Fixed compacting all or many resolution 1 cells (#919) + ### Changed - Replace internal algorithm for `polygonToCells` with a new version that is more memory-efficient (#785) - Reorganize tests into public / internal. (#762) diff --git a/src/apps/testapps/testCompactCells.c b/src/apps/testapps/testCompactCells.c index 94e1d01e8..bab73abc2 100644 --- a/src/apps/testapps/testCompactCells.c +++ b/src/apps/testapps/testCompactCells.c @@ -15,6 +15,7 @@ */ #include +#include #include "constants.h" #include "h3Index.h" @@ -91,6 +92,85 @@ SUITE(compactCells) { free(children); } + TEST(allRes1) { + const int64_t numRes0 = 122; + const int64_t numRes1 = 842; + H3Index *cells0 = calloc(numRes0, sizeof(H3Index)); + H3Index *cells1 = calloc(numRes1, sizeof(H3Index)); + H3Index *out = calloc(numRes1, sizeof(H3Index)); + + H3_EXPORT(getRes0Cells)(cells0); + t_assert(cells0[0] == 0x8001fffffffffff, + "got expected first res0 cell"); + + t_assertSuccess( + H3_EXPORT(uncompactCells)(cells0, numRes0, cells1, numRes1, 1)); + + int64_t numUncompacted = numRes1; + t_assertSuccess(H3_EXPORT(compactCells)(cells1, out, numUncompacted)); + + // Assert that the output of this function matches exactly the set of + // res 0 cells + size_t foundCount = 0; + for (size_t res1Idx = 0; res1Idx < numRes1; res1Idx++) { + H3Index compactedCell = out[res1Idx]; + + if (compactedCell) { + for (size_t res1DupIdx = 0; res1DupIdx < res1Idx; + res1DupIdx++) { + t_assert(out[res1DupIdx] != compactedCell, + "Duplicated output found"); + } + + bool found = false; + for (size_t res0Idx = 0; res0Idx < numRes0; res0Idx++) { + if (cells0[res0Idx] == compactedCell) { + found = true; + break; + } + } + t_assert(found, "Res 0 cell is found"); + foundCount++; + } + } + t_assert(foundCount == numRes0, "all res 0 cells found"); + + free(cells0); + free(cells1); + free(out); + } + + TEST(allRes1_variousRanges) { + const int64_t numRes0 = 122; + const int64_t numRes1 = 842; + H3Index *cells0 = calloc(numRes0, sizeof(H3Index)); + H3Index *cells1 = calloc(numRes1, sizeof(H3Index)); + H3Index *out = calloc(numRes1, sizeof(H3Index)); + + H3_EXPORT(getRes0Cells)(cells0); + t_assert(cells0[0] == 0x8001fffffffffff, + "got expected first res0 cell"); + + t_assertSuccess( + H3_EXPORT(uncompactCells)(cells0, numRes0, cells1, numRes1, 1)); + + // Test various (but not all possible combinations) ranges of res 1 + // cells + for (int64_t offset = 0; offset < numRes1; offset++) { + for (int64_t numUncompacted = numRes1 - offset; numUncompacted >= 0; + numUncompacted--) { + memset(out, 0, sizeof(H3Index) * numRes1); + + t_assertSuccess(H3_EXPORT(compactCells)(&cells1[offset], out, + numUncompacted)); + } + } + + free(cells0); + free(cells1); + free(out); + } + TEST(res0) { int hexCount = NUM_BASE_CELLS; @@ -358,9 +438,7 @@ SUITE(compactCells) { 0x7, 0x400000000}; H3Index output[43] = {0}; - t_assert(H3_EXPORT(compactCells)(bad, output, numHex) == E_RES_DOMAIN, - "compactCells returns E_RES_DOMAIN on bad input (parent " - "error #2)"); + t_assertSuccess(H3_EXPORT(compactCells)(bad, output, numHex)); } TEST(uncompactCells_wrongRes) { diff --git a/src/h3lib/lib/h3Index.c b/src/h3lib/lib/h3Index.c index 193622caf..489421e85 100644 --- a/src/h3lib/lib/h3Index.c +++ b/src/h3lib/lib/h3Index.c @@ -480,43 +480,49 @@ H3Error H3_EXPORT(compactCells)(const H3Index *h3Set, H3Index *compactedSet, H3Index currIndex = remainingHexes[i]; // TODO: This case is coverable (reachable by fuzzer) if (currIndex != H3_NULL) { - H3Index parent; - H3Error parentError = - H3_EXPORT(cellToParent)(currIndex, parentRes, &parent); - if (parentError) { - H3_MEMORY(free)(compactableHexes); - H3_MEMORY(free)(remainingHexes); - H3_MEMORY(free)(hashSetArray); - return parentError; - } - // Modulus hash the parent into the temp array - // to determine if this index was included in - // the compactableHexes array - int loc = (int)(parent % numRemainingHexes); - int loopCount = 0; bool isUncompactable = true; - do { - if (NEVER(loopCount > numRemainingHexes)) { - // This case should not be possible because at most one - // index is placed into hashSetArray per input hexagon. + // Resolution 0 cells always uncompactable, and trying to take + // the res -1 parent of a cell is invalid. + if (parentRes >= 0) { + H3Index parent; + H3Error parentError = + H3_EXPORT(cellToParent)(currIndex, parentRes, &parent); + if (NEVER(parentError)) { H3_MEMORY(free)(compactableHexes); H3_MEMORY(free)(remainingHexes); H3_MEMORY(free)(hashSetArray); - return E_FAILED; + return parentError; } - H3Index tempIndex = - hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE; - if (tempIndex == parent) { - int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1; - if (count == 7) { - isUncompactable = false; + // Modulus hash the parent into the temp array + // to determine if this index was included in + // the compactableHexes array + int loc = (int)(parent % numRemainingHexes); + int loopCount = 0; + do { + if (NEVER(loopCount > numRemainingHexes)) { + // This case should not be possible because at most + // one index is placed into hashSetArray per input + // hexagon. + H3_MEMORY(free)(compactableHexes); + H3_MEMORY(free)(remainingHexes); + H3_MEMORY(free)(hashSetArray); + return E_FAILED; } - break; - } else { - loc = (loc + 1) % numRemainingHexes; - } - loopCount++; - } while (hashSetArray[loc] != parent); + H3Index tempIndex = + hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE; + if (tempIndex == parent) { + int count = + H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1; + if (count == 7) { + isUncompactable = false; + } + break; + } else { + loc = (loc + 1) % numRemainingHexes; + } + loopCount++; + } while (hashSetArray[loc] != parent); + } if (isUncompactable) { compactedSetOffset[uncompactableCount] = remainingHexes[i]; uncompactableCount++;