8000 Possible fix for #914 compactCells failing when passed all res 1 cells by isaacbrodsky · Pull Request #919 · uber/h3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Possible fix for #914 compactCells failing when passed all res 1 cells #919

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 20 commits into from
Oct 1, 2024
Merged

Possible fix for #914 compactCells failing when passed all res 1 cells #919

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
20 commits
Select commit Hold shift + click to select a range
37dac22
stub for new res1 test
ajfriend Sep 26, 2024
a094639
better name
ajfriend Sep 26, 2024
a618a5e
formatting is happening?
ajfriend Sep 26, 2024
63a2723
clean up test for all res 1
ajfriend Sep 26, 2024
e5fa3bb
failing test
ajfriend Sep 26, 2024
8f77829
Demonstrate pass at `numUncompacted = 40`
ajfriend Sep 26, 2024
944a62b
retry: Demonstrate pass at `numUncompacted = 40`
ajfriend Sep 26, 2024
6159f5c
should fix the formatting issue
ajfriend Sep 26, 2024
d811d47
const array sizes to fix windows errors
ajfriend Sep 26, 2024
d29c9b3
bah
ajfriend Sep 26, 2024
fa3b1b8
Demonstrate failure at numUncompacted = 41
ajfriend Sep 26, 2024
e6c47e0
Demonstrate failure at numUncompacted = numRes1 = 842;
ajfriend Sep 26, 2024
a3a28e6
Demonstrate pass at numUncompacted = 40
ajfriend Sep 26, 2024
d97b939
back to the full failing test demonstrating the problem
ajfriend Sep 26, 2024
f199548
proposed fix for compact
isaacbrodsky Sep 29, 2024
663e02a
test other case
isaacbrodsky Sep 29, 2024
a7e07fe
comprehensive test
isaacbrodsky Sep 29, 2024 8000
6eb6ca8
NEVER for parent error
isaacbrodsky Sep 29, 2024
bd81be6
assert that all res 0 cells are found
isaacbrodsky Sep 30, 2024
25eecc5
CHANGELOG
isaacbrodsky Oct 1, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions CHANGELOG.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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)
Expand Down
84 changes: 81 additions & 3 deletions src/apps/testapps/testCompactCells.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -15,6 +15,7 @@
*/

#include <stdlib.h>
#include <string.h>

#include "constants.h"
#include "h3Index.h"
Expand Down Expand Up @@ -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);
}
Comment on lines +143 to +172
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actually, I'm not positive that we need this test. I had code like this previously just to try to generate a minimal example of a failure. I don't think it hurts to add this test, but I don't think there's any reason to think this provides much additional value beyond compacting all the res 1 cells. Happy to go either way with it, based on your judgement @isaacbrodsky .

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's not that strong a test. More convincing might be enumerating all possible sets of res 1 cells, but it might be useful for just ensuring all of these cases are not inadvertently failing.


TEST(res0) {
int hexCount = NUM_BASE_CELLS;

Expand Down Expand Up @@ -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) {
Expand Down
68 changes: 37 additions & 31 deletions src/h3lib/lib/h3Index.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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;
}
6D40 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++;
Expand Down
Loading
0